Skip to main content

naga/proc/
constant_evaluator.rs

1// Code in this file intentionally uses `for` loops and `.push()` rather than
2// `ArrayVec::from_iter`, because the latter is monomorphized by all three of
3// the item type, the capacity, and the iterator type, which can easily bloat
4// the compiled executable (by ~260 KiB, when it was removed).
5
6use alloc::{
7    format,
8    string::{String, ToString},
9    vec,
10    vec::Vec,
11};
12use core::iter;
13
14use arrayvec::ArrayVec;
15use half::f16;
16use num_traits::{real::Real, FromPrimitive, One, ToPrimitive, Zero};
17
18use crate::{
19    arena::{Arena, Handle, HandleVec, UniqueArena},
20    ArraySize, BinaryOperator, Constant, Expression, Literal, Override, RelationalFunction,
21    ScalarKind, Span, Type, TypeInner, UnaryOperator,
22};
23
24#[cfg(feature = "wgsl-in")]
25use crate::common::wgsl::TryToWgsl;
26
27/// A macro that allows dollar signs (`$`) to be emitted by other macros. Useful for generating
28/// `macro_rules!` items that, in turn, emit their own `macro_rules!` items.
29///
30/// Technique stolen directly from
31/// <https://github.com/rust-lang/rust/issues/35853#issuecomment-415993963>.
32macro_rules! with_dollar_sign {
33    ($($body:tt)*) => {
34        macro_rules! __with_dollar_sign { $($body)* }
35        __with_dollar_sign!($);
36    }
37}
38
39macro_rules! gen_component_wise_extractor {
40    (
41        $ident:ident -> $target:ident,
42        literals: [$( $literal:ident => $mapping:ident: $ty:ident ),+ $(,)?],
43        scalar_kinds: [$( $scalar_kind:ident ),* $(,)?],
44    ) => {
45        /// A subset of [`Literal`]s intended to be used for implementing numeric built-ins.
46        #[derive(Debug)]
47        #[cfg_attr(test, derive(PartialEq))]
48        enum $target<const N: usize> {
49            $(
50                #[doc = concat!(
51                    "Maps to [`Literal::",
52                    stringify!($literal),
53                    "`]",
54                )]
55                $mapping([$ty; N]),
56            )+
57        }
58
59        impl From<$target<1>> for Expression {
60            fn from(value: $target<1>) -> Self {
61                match value {
62                    $(
63                        $target::$mapping([value]) => {
64                            Expression::Literal(Literal::$literal(value))
65                        }
66                    )+
67                }
68            }
69        }
70
71        #[doc = concat!(
72            "Attempts to evaluate multiple `exprs` as a combined [`",
73            stringify!($target),
74            "`] to pass to `handler`. ",
75        )]
76        /// If `exprs` are vectors of the same length, `handler` is called for each corresponding
77        /// component of each vector.
78        ///
79        /// `handler`'s output is registered as a new expression. If `exprs` are vectors of the
80        /// same length, a new vector expression is registered, composed of each component emitted
81        /// by `handler`.
82        fn $ident<const N: usize, const M: usize>(
83            eval: &mut ConstantEvaluator<'_>,
84            span: Span,
85            exprs: [Handle<Expression>; N],
86            handler: fn($target<N>) -> Result<$target<M>, ConstantEvaluatorError>,
87        ) -> Result<Handle<Expression>, ConstantEvaluatorError>
88        where
89            $target<M>: Into<Expression>,
90        {
91            assert!(N > 0);
92            let err = ConstantEvaluatorError::InvalidMathArg;
93            let mut exprs = exprs.into_iter();
94
95            macro_rules! sanitize {
96                ($expr:expr) => {
97                    eval.eval_zero_value_and_splat($expr, span)
98                        .map(|expr| &eval.expressions[expr])
99                };
100            }
101
102            let new_expr: Result<Expression, ConstantEvaluatorError> = match sanitize!(exprs.next().unwrap())? {
103                $(
104                    &Expression::Literal(Literal::$literal(x)) => {
105                        let mut arr = ArrayVec::<_, N>::new();
106                        arr.push(x);
107                        for expr in exprs {
108                            match sanitize!(expr)? {
109                                &Expression::Literal(Literal::$literal(val)) => arr.push(val),
110                                _ => return Err(err),
111                            }
112                        }
113                        let comps = $target::$mapping(arr.into_inner().unwrap());
114                        Ok(handler(comps)?.into())
115                    },
116                )+
117                &Expression::Compose { ty, ref components } => match &eval.types[ty].inner {
118                    &TypeInner::Vector { size, scalar } => match scalar.kind {
119                        $(ScalarKind::$scalar_kind)|* => {
120                            let first_ty = ty;
121                            let mut component_groups =
122                                ArrayVec::<ArrayVec<_, { crate::VectorSize::MAX }>, N>::new();
123                            {
124                                let mut inner = ArrayVec::new();
125                                for item in crate::proc::flatten_compose(
126                                    first_ty,
127                                    components,
128                                    eval.expressions,
129                                    eval.types,
130                                ) {
131                                    inner.push(item);
132                                }
133                                component_groups.push(inner);
134                            }
135                            for expr in exprs {
136                                match sanitize!(expr)? {
137                                    &Expression::Compose { ty, ref components }
138                                        if &eval.types[ty].inner
139                                            == &eval.types[first_ty].inner =>
140                                    {
141                                        let mut inner = ArrayVec::new();
142                                        for item in crate::proc::flatten_compose(
143                                            ty,
144                                            components,
145                                            eval.expressions,
146                                            eval.types,
147                                        ) {
148                                            inner.push(item);
149                                        }
150                                        component_groups.push(inner);
151                                    }
152                                    _ => return Err(err),
153                                }
154                            }
155                            let component_groups = component_groups.into_inner().unwrap();
156                            let mut new_components =
157                                ArrayVec::<_, { crate::VectorSize::MAX }>::new();
158                            for idx in 0..(size as u8).into() {
159                                let mut group_arr = ArrayVec::<_, N>::new();
160                                for cs in component_groups.iter() {
161                                    group_arr.push(
162                                        cs.get(idx).cloned().ok_or_else(|| err.clone())?,
163                                    );
164                                }
165                                let group = group_arr.into_inner().unwrap();
166                                new_components.push($ident(
167                                    eval,
168                                    span,
169                                    group,
170                                    handler,
171                                )?);
172                            }
173                            Ok(Expression::Compose {
174                                ty: first_ty,
175                                components: new_components.into_iter().collect(),
176                            })
177                        }
178                        _ => return Err(err),
179                    },
180                    _ => return Err(err),
181                },
182                _ => return Err(err),
183            };
184            eval.register_evaluated_expr(new_expr?, span)
185        }
186
187        with_dollar_sign! {
188            ($d:tt) => {
189                #[allow(unused)]
190                #[doc = concat!(
191                    "A convenience macro for using the same RHS for each [`",
192                    stringify!($target),
193                    "`] variant in a call to [`",
194                    stringify!($ident),
195                    "`].",
196                )]
197                macro_rules! $ident {
198                    (
199                        $eval:expr,
200                        $span:expr,
201                        [$d ($d expr:expr),+ $d (,)?],
202                        |$d ($d arg:ident),+| $d tt:tt
203                    ) => {
204                        $ident($eval, $span, [$d ($d expr),+], |args| match args {
205                            $(
206                                $target::$mapping([$d ($d arg),+]) => {
207                                    let res = $d tt;
208                                    Result::map(res, $target::$mapping)
209                                },
210                            )+
211                        })
212                    };
213                }
214            };
215        }
216    };
217}
218
219gen_component_wise_extractor! {
220    component_wise_scalar -> Scalar,
221    literals: [
222        AbstractFloat => AbstractFloat: f64,
223        F32 => F32: f32,
224        F16 => F16: f16,
225        AbstractInt => AbstractInt: i64,
226        U32 => U32: u32,
227        I32 => I32: i32,
228        U64 => U64: u64,
229        I64 => I64: i64,
230    ],
231    scalar_kinds: [
232        Float,
233        AbstractFloat,
234        Sint,
235        Uint,
236        AbstractInt,
237    ],
238}
239
240gen_component_wise_extractor! {
241    component_wise_float -> Float,
242    literals: [
243        AbstractFloat => Abstract: f64,
244        F32 => F32: f32,
245        F16 => F16: f16,
246    ],
247    scalar_kinds: [
248        Float,
249        AbstractFloat,
250    ],
251}
252
253gen_component_wise_extractor! {
254    component_wise_concrete_int -> ConcreteInt,
255    literals: [
256        U32 => U32: u32,
257        I32 => I32: i32,
258    ],
259    scalar_kinds: [
260        Sint,
261        Uint,
262    ],
263}
264
265gen_component_wise_extractor! {
266    component_wise_signed -> Signed,
267    literals: [
268        AbstractFloat => AbstractFloat: f64,
269        AbstractInt => AbstractInt: i64,
270        F32 => F32: f32,
271        F16 => F16: f16,
272        I32 => I32: i32,
273    ],
274    scalar_kinds: [
275        Sint,
276        AbstractInt,
277        Float,
278        AbstractFloat,
279    ],
280}
281
282/// Vectors with a concrete element type.
283#[derive(Debug)]
284enum LiteralVector {
285    F64(ArrayVec<f64, { crate::VectorSize::MAX }>),
286    F32(ArrayVec<f32, { crate::VectorSize::MAX }>),
287    F16(ArrayVec<f16, { crate::VectorSize::MAX }>),
288    U16(ArrayVec<u16, { crate::VectorSize::MAX }>),
289    I16(ArrayVec<i16, { crate::VectorSize::MAX }>),
290    U32(ArrayVec<u32, { crate::VectorSize::MAX }>),
291    I32(ArrayVec<i32, { crate::VectorSize::MAX }>),
292    U64(ArrayVec<u64, { crate::VectorSize::MAX }>),
293    I64(ArrayVec<i64, { crate::VectorSize::MAX }>),
294    Bool(ArrayVec<bool, { crate::VectorSize::MAX }>),
295    AbstractInt(ArrayVec<i64, { crate::VectorSize::MAX }>),
296    AbstractFloat(ArrayVec<f64, { crate::VectorSize::MAX }>),
297}
298
299impl LiteralVector {
300    #[allow(clippy::missing_const_for_fn, reason = "MSRV")]
301    fn len(&self) -> usize {
302        match *self {
303            LiteralVector::F64(ref v) => v.len(),
304            LiteralVector::F32(ref v) => v.len(),
305            LiteralVector::F16(ref v) => v.len(),
306            LiteralVector::U16(ref v) => v.len(),
307            LiteralVector::I16(ref v) => v.len(),
308            LiteralVector::U32(ref v) => v.len(),
309            LiteralVector::I32(ref v) => v.len(),
310            LiteralVector::U64(ref v) => v.len(),
311            LiteralVector::I64(ref v) => v.len(),
312            LiteralVector::Bool(ref v) => v.len(),
313            LiteralVector::AbstractInt(ref v) => v.len(),
314            LiteralVector::AbstractFloat(ref v) => v.len(),
315        }
316    }
317
318    /// Creates [`LiteralVector`] of size 1 from single [`Literal`]
319    fn from_literal(literal: Literal) -> Self {
320        fn arrayvec_of<T, const N: usize>(val: T) -> ArrayVec<T, N> {
321            let mut v = ArrayVec::new();
322            v.push(val);
323            v
324        }
325        match literal {
326            Literal::F64(e) => Self::F64(arrayvec_of(e)),
327            Literal::F32(e) => Self::F32(arrayvec_of(e)),
328            Literal::U16(e) => Self::U16(arrayvec_of(e)),
329            Literal::I16(e) => Self::I16(arrayvec_of(e)),
330            Literal::U32(e) => Self::U32(arrayvec_of(e)),
331            Literal::I32(e) => Self::I32(arrayvec_of(e)),
332            Literal::U64(e) => Self::U64(arrayvec_of(e)),
333            Literal::I64(e) => Self::I64(arrayvec_of(e)),
334            Literal::Bool(e) => Self::Bool(arrayvec_of(e)),
335            Literal::AbstractInt(e) => Self::AbstractInt(arrayvec_of(e)),
336            Literal::AbstractFloat(e) => Self::AbstractFloat(arrayvec_of(e)),
337            Literal::F16(e) => Self::F16(arrayvec_of(e)),
338        }
339    }
340
341    /// Creates [`LiteralVector`] from [`ArrayVec`] of [`Literal`]s.
342    /// Returns error if components types do not match.
343    /// # Panics
344    /// Panics if vector is empty
345    fn from_literal_vec(
346        components: ArrayVec<Literal, { crate::VectorSize::MAX }>,
347    ) -> Result<Self, ConstantEvaluatorError> {
348        assert!(!components.is_empty());
349        // TODO: should a vector of i32 be constructible from abstract int?
350        macro_rules! compose_literals {
351            ($components:expr, $variant:ident, $self_variant:ident) => {{
352                let mut out = ArrayVec::new();
353                for l in &$components {
354                    match l {
355                        &Literal::$variant(v) => out.push(v),
356                        _ => return Err(ConstantEvaluatorError::InvalidMathArg),
357                    }
358                }
359                Self::$self_variant(out)
360            }};
361        }
362        Ok(match components[0] {
363            Literal::I16(_) => compose_literals!(components, I16, I16),
364            Literal::U16(_) => compose_literals!(components, U16, U16),
365            Literal::I32(_) => compose_literals!(components, I32, I32),
366            Literal::U32(_) => compose_literals!(components, U32, U32),
367            Literal::I64(_) => compose_literals!(components, I64, I64),
368            Literal::U64(_) => compose_literals!(components, U64, U64),
369            Literal::F32(_) => compose_literals!(components, F32, F32),
370            Literal::F64(_) => compose_literals!(components, F64, F64),
371            Literal::Bool(_) => compose_literals!(components, Bool, Bool),
372            Literal::AbstractInt(_) => compose_literals!(components, AbstractInt, AbstractInt),
373            Literal::AbstractFloat(_) => {
374                compose_literals!(components, AbstractFloat, AbstractFloat)
375            }
376            Literal::F16(_) => compose_literals!(components, F16, F16),
377        })
378    }
379
380    #[allow(dead_code)]
381    /// Returns [`ArrayVec`] of [`Literal`]s
382    fn to_literal_vec(&self) -> ArrayVec<Literal, { crate::VectorSize::MAX }> {
383        macro_rules! decompose_literals {
384            ($v:expr, $variant:ident) => {{
385                let mut out = ArrayVec::new();
386                for e in $v {
387                    out.push(Literal::$variant(*e));
388                }
389                out
390            }};
391        }
392        match *self {
393            LiteralVector::F64(ref v) => decompose_literals!(v, F64),
394            LiteralVector::F32(ref v) => decompose_literals!(v, F32),
395            LiteralVector::F16(ref v) => decompose_literals!(v, F16),
396            LiteralVector::U16(ref v) => decompose_literals!(v, U16),
397            LiteralVector::I16(ref v) => decompose_literals!(v, I16),
398            LiteralVector::U32(ref v) => decompose_literals!(v, U32),
399            LiteralVector::I32(ref v) => decompose_literals!(v, I32),
400            LiteralVector::U64(ref v) => decompose_literals!(v, U64),
401            LiteralVector::I64(ref v) => decompose_literals!(v, I64),
402            LiteralVector::Bool(ref v) => decompose_literals!(v, Bool),
403            LiteralVector::AbstractInt(ref v) => decompose_literals!(v, AbstractInt),
404            LiteralVector::AbstractFloat(ref v) => decompose_literals!(v, AbstractFloat),
405        }
406    }
407
408    #[allow(dead_code)]
409    /// Puts self into eval's expressions arena and returns handle to it
410    fn register_as_evaluated_expr(
411        &self,
412        eval: &mut ConstantEvaluator<'_>,
413        span: Span,
414    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
415        let lit_vec = self.to_literal_vec();
416        assert!(!lit_vec.is_empty());
417        let expr = if lit_vec.len() == 1 {
418            Expression::Literal(lit_vec[0])
419        } else {
420            Expression::Compose {
421                ty: eval.types.insert(
422                    Type {
423                        name: None,
424                        inner: TypeInner::Vector {
425                            size: match lit_vec.len() {
426                                2 => crate::VectorSize::Bi,
427                                3 => crate::VectorSize::Tri,
428                                4 => crate::VectorSize::Quad,
429                                _ => unreachable!(),
430                            },
431                            scalar: lit_vec[0].scalar(),
432                        },
433                    },
434                    Span::UNDEFINED,
435                ),
436                components: lit_vec
437                    .iter()
438                    .map(|&l| eval.register_evaluated_expr(Expression::Literal(l), span))
439                    .collect::<Result<_, _>>()?,
440            }
441        };
442        eval.register_evaluated_expr(expr, span)
443    }
444}
445
446/// A macro for matching on [`LiteralVector`] variants.
447///
448/// `Float` variant expands to `F16`, `F32`, `F64` and `AbstractFloat`.
449/// `Integer` variant expands to `I32`, `I64`, `U32`, `U64` and `AbstractInt`.
450///
451/// For output both [`Literal`] (fold) and [`LiteralVector`] (map) are supported.
452///
453/// Example usage:
454///
455/// ```rust,ignore
456/// match_literal_vector!(match v => Literal {
457///     F16 => |v| {v.sum()},
458///     Integer => |v| {v.sum()},
459///     U32 => |v| -> I32 {v.sum()}, // optionally override return type
460/// })
461/// ```
462///
463/// ```rust,ignore
464/// match_literal_vector!(match (e1, e2) => LiteralVector {
465///     F16 => |e1, e2| {e1+e2},
466///     Integer => |e1, e2| {e1+e2},
467///     U32 => |e1, e2| -> I32 {e1+e2}, // optionally override return type
468/// })
469/// ```
470macro_rules! match_literal_vector {
471    (match $lit_vec:expr => $out:ident {
472        $(
473            $ty:ident => |$($var:ident),+| $(-> $ret:ident)? { $body:expr }
474        ),+
475        $(,)?
476    }) => {
477        match_literal_vector!(@inner_start $lit_vec; $out; [$($ty),+]; [$({ $($var),+ ; $($ret)? ; $body }),+])
478    };
479
480    (@inner_start
481        $lit_vec:expr;
482        $out:ident;
483        [$($ty:ident),+];
484        [$({ $($var:ident),+ ; $($ret:ident)? ; $body:expr }),+]
485    ) => {
486        match_literal_vector!(@inner
487            $lit_vec;
488            $out;
489            [$($ty),+];
490            [] <> [$({ $($var),+ ; $($ret)? ; $body }),+]
491        )
492    };
493
494    (@inner
495        $lit_vec:expr;
496        $out:ident;
497        [$ty:ident $(, $ty1:ident)*];
498        [$({$_ty:ident ; $($_var:ident),+ ; $($_ret:ident)? ; $_body:expr}),*] <>
499        [$({ $($var:ident),+ ; $($ret:ident)? ; $body:expr }),+]
500    ) => {
501        match_literal_vector!(@inner
502            $ty;
503            $lit_vec;
504            $out;
505            [$($ty1),*];
506            [$({$_ty ; $($_var),+ ; $($_ret)? ; $_body}),*] <>
507            [$({ $($var),+ ; $($ret)? ; $body }),+]
508        )
509    };
510    (@inner
511        Integer;
512        $lit_vec:expr;
513        $out:ident;
514        [$($ty:ident),*];
515        [$({$_ty:ident ; $($_var:ident),+ ; $($_ret:ident)? ; $_body:expr}),*] <>
516        [
517            { $($var:ident),+ ; $($ret:ident)? ; $body:expr }
518            $(,{ $($var1:ident),+ ; $($ret1:ident)? ; $body1:expr })*
519        ]
520    ) => {
521        match_literal_vector!(@inner
522            $lit_vec;
523            $out;
524            [U32, I32, U64, I64, AbstractInt $(, $ty)*];
525            [$({$_ty ; $($_var),+ ; $($_ret)? ; $_body}),*] <>
526            [
527                { $($var),+ ; $($ret)? ; $body }, // U32
528                { $($var),+ ; $($ret)? ; $body }, // I32
529                { $($var),+ ; $($ret)? ; $body }, // U64
530                { $($var),+ ; $($ret)? ; $body }, // I64
531                { $($var),+ ; $($ret)? ; $body }  // AbstractInt
532                $(,{ $($var1),+ ; $($ret1)? ; $body1 })*
533            ]
534        )
535    };
536    (@inner
537        Float;
538        $lit_vec:expr;
539        $out:ident;
540        [$($ty:ident),*];
541        [$({$_ty:ident ; $($_var:ident),+ ; $($_ret:ident)? ; $_body:expr}),*] <>
542        [
543            { $($var:ident),+ ; $($ret:ident)? ; $body:expr }
544            $(,{ $($var1:ident),+ ; $($ret1:ident)? ; $body1:expr })*
545        ]
546    ) => {
547        match_literal_vector!(@inner
548            $lit_vec;
549            $out;
550            [F16, F32, F64, AbstractFloat $(, $ty)*];
551            [$({$_ty ; $($_var),+ ; $($_ret)? ; $_body}),*] <>
552            [
553                { $($var),+ ; $($ret)? ; $body }, // F16
554                { $($var),+ ; $($ret)? ; $body }, // F32
555                { $($var),+ ; $($ret)? ; $body }, // F64
556                { $($var),+ ; $($ret)? ; $body }  // AbstractFloat
557                $(,{ $($var1),+ ; $($ret1)? ; $body1 })*
558            ]
559        )
560    };
561    (@inner
562        $ty:ident;
563        $lit_vec:expr;
564        $out:ident;
565        [$ty1:ident $(,$ty2:ident)*];
566        [$({$_ty:ident ; $($_var:ident),+ ; $($_ret:ident)? ; $_body:expr}),*] <> [
567            { $($var:ident),+ ; $($ret:ident)? ; $body:expr }
568            $(, { $($var1:ident),+ ; $($ret1:ident)? ; $body1:expr })*
569        ]
570    ) => {
571        match_literal_vector!(@inner
572            $ty1;
573            $lit_vec;
574            $out;
575            [$($ty2),*];
576            [
577                $({$_ty ; $($_var),+ ; $($_ret)? ; $_body},)*
578                { $ty; $($var),+ ; $($ret)? ; $body }
579            ] <>
580            [$({ $($var1),+ ; $($ret1)? ; $body1 }),*]
581
582        )
583    };
584    (@inner
585        $ty:ident;
586        $lit_vec:expr;
587        $out:ident;
588        [];
589        [$({$_ty:ident ; $($_var:ident),+ ; $($_ret:ident)? ; $_body:expr}),*] <>
590        [{ $($var:ident),+ ; $($ret:ident)? ; $body:expr }]
591    ) => {
592        match_literal_vector!(@inner_finish
593            $lit_vec;
594            $out;
595            [
596                $({ $_ty ; $($_var),+ ; $($_ret)? ; $_body },)*
597                { $ty; $($var),+ ; $($ret)? ; $body }
598            ]
599        )
600    };
601    (@inner_finish
602        $lit_vec:expr;
603        $out:ident;
604        [$({$ty:ident ; $($var:ident),+ ; $($ret:ident)? ; $body:expr}),+]
605    ) => {
606        match $lit_vec {
607            $(
608                #[allow(unused_parens)]
609                ($(LiteralVector::$ty(ref $var)),+) => { Ok(match_literal_vector!(@expand_ret $out; $ty $(; $ret)? ; $body)) }
610            )+
611            _ => Err(ConstantEvaluatorError::InvalidMathArg),
612        }
613    };
614    (@expand_ret $out:ident; $ty:ident; $body:expr) => {
615        $out::$ty($body)
616    };
617    (@expand_ret $out:ident; $_ty:ident; $ret:ident; $body:expr) => {
618        $out::$ret($body)
619    };
620}
621
622fn float_length<F>(e: &[F]) -> Option<F>
623where
624    F: core::ops::Mul<F> + num_traits::Float + iter::Sum,
625{
626    if e.len() == 1 {
627        // Avoids possible overflow in squaring
628        Some(e[0].abs())
629    } else {
630        let result = e.iter().map(|&ei| ei * ei).sum::<F>().sqrt();
631        result.is_finite().then_some(result)
632    }
633}
634
635/// The dot product of `a` and `b`.  Return `None` if it is not finite.
636fn float_dot<F>(a: &[F], b: &[F]) -> Option<F>
637where
638    F: num_traits::Float,
639{
640    let result = a
641        .iter()
642        .zip(b.iter())
643        .map(|(&aa, &bb)| aa * bb)
644        .fold(F::zero(), |acc, x| acc + x);
645    result.is_finite().then_some(result)
646}
647
648#[derive(Debug)]
649enum Behavior<'a> {
650    Wgsl(WgslRestrictions<'a>),
651    Glsl(GlslRestrictions<'a>),
652}
653
654impl Behavior<'_> {
655    /// Returns `true` if the inner WGSL/GLSL restrictions are runtime restrictions.
656    const fn has_runtime_restrictions(&self) -> bool {
657        matches!(
658            self,
659            &Behavior::Wgsl(WgslRestrictions::Runtime(_))
660                | &Behavior::Glsl(GlslRestrictions::Runtime(_))
661        )
662    }
663}
664
665/// A context for evaluating constant expressions.
666///
667/// A `ConstantEvaluator` points at an expression arena to which it can append
668/// newly evaluated expressions: you pass [`try_eval_and_append`] whatever kind
669/// of Naga [`Expression`] you like, and if its value can be computed at compile
670/// time, `try_eval_and_append` appends an expression representing the computed
671/// value - a tree of [`Literal`], [`Compose`], [`ZeroValue`], and [`Swizzle`]
672/// expressions - to the arena. See the [`try_eval_and_append`] method for details.
673///
674/// A `ConstantEvaluator` also holds whatever information we need to carry out
675/// that evaluation: types, other constants, and so on.
676///
677/// [`try_eval_and_append`]: ConstantEvaluator::try_eval_and_append
678/// [`Compose`]: Expression::Compose
679/// [`ZeroValue`]: Expression::ZeroValue
680/// [`Literal`]: Expression::Literal
681/// [`Swizzle`]: Expression::Swizzle
682#[derive(Debug)]
683pub struct ConstantEvaluator<'a> {
684    /// Which language's evaluation rules we should follow.
685    behavior: Behavior<'a>,
686
687    /// The module's type arena.
688    ///
689    /// Because expressions like [`Splat`] contain type handles, we need to be
690    /// able to add new types to produce those expressions.
691    ///
692    /// [`Splat`]: Expression::Splat
693    types: &'a mut UniqueArena<Type>,
694
695    /// The module's constant arena.
696    constants: &'a Arena<Constant>,
697
698    /// The module's override arena.
699    overrides: &'a Arena<Override>,
700
701    /// The arena to which we are contributing expressions.
702    expressions: &'a mut Arena<Expression>,
703
704    /// Tracks the constness of expressions residing in [`Self::expressions`]
705    expression_kind_tracker: &'a mut ExpressionKindTracker,
706
707    layouter: &'a mut crate::proc::Layouter,
708}
709
710#[derive(Debug)]
711enum WgslRestrictions<'a> {
712    /// - const-expressions will be evaluated and inserted in the arena
713    Const(Option<FunctionLocalData<'a>>),
714    /// - const-expressions will be evaluated and inserted in the arena
715    /// - override-expressions will be inserted in the arena
716    Override,
717    /// - const-expressions will be evaluated and inserted in the arena
718    /// - override-expressions will be inserted in the arena
719    /// - runtime-expressions will be inserted in the arena
720    Runtime(FunctionLocalData<'a>),
721}
722
723#[derive(Debug)]
724enum GlslRestrictions<'a> {
725    /// - const-expressions will be evaluated and inserted in the arena
726    Const,
727    /// - const-expressions will be evaluated and inserted in the arena
728    /// - override-expressions will be inserted in the arena
729    /// - runtime-expressions will be inserted in the arena
730    Runtime(FunctionLocalData<'a>),
731}
732
733#[derive(Debug)]
734struct FunctionLocalData<'a> {
735    /// Global constant expressions
736    global_expressions: &'a Arena<Expression>,
737    emitter: &'a mut super::Emitter,
738    block: &'a mut crate::Block,
739}
740
741#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
742pub enum ExpressionKind {
743    Const,
744    Override,
745    Runtime,
746}
747
748#[derive(Debug)]
749pub struct ExpressionKindTracker {
750    inner: HandleVec<Expression, ExpressionKind>,
751}
752
753impl ExpressionKindTracker {
754    pub const fn new() -> Self {
755        Self {
756            inner: HandleVec::new(),
757        }
758    }
759
760    /// Forces the the expression to not be const
761    pub fn force_non_const(&mut self, value: Handle<Expression>) {
762        self.inner[value] = ExpressionKind::Runtime;
763    }
764
765    pub fn insert(&mut self, value: Handle<Expression>, expr_type: ExpressionKind) {
766        self.inner.insert(value, expr_type);
767    }
768
769    pub fn is_const(&self, h: Handle<Expression>) -> bool {
770        matches!(self.type_of(h), ExpressionKind::Const)
771    }
772
773    pub fn is_const_or_override(&self, h: Handle<Expression>) -> bool {
774        matches!(
775            self.type_of(h),
776            ExpressionKind::Const | ExpressionKind::Override
777        )
778    }
779
780    fn type_of(&self, value: Handle<Expression>) -> ExpressionKind {
781        self.inner[value]
782    }
783
784    pub fn from_arena(arena: &Arena<Expression>) -> Self {
785        let mut tracker = Self {
786            inner: HandleVec::with_capacity(arena.len()),
787        };
788        for (handle, expr) in arena.iter() {
789            tracker
790                .inner
791                .insert(handle, tracker.type_of_with_expr(expr));
792        }
793        tracker
794    }
795
796    fn type_of_with_expr(&self, expr: &Expression) -> ExpressionKind {
797        match *expr {
798            Expression::Literal(_) | Expression::ZeroValue(_) | Expression::Constant(_) => {
799                ExpressionKind::Const
800            }
801            Expression::Override(_) => ExpressionKind::Override,
802            Expression::Compose { ref components, .. } => {
803                let mut expr_type = ExpressionKind::Const;
804                for component in components {
805                    expr_type = expr_type.max(self.type_of(*component))
806                }
807                expr_type
808            }
809            Expression::Splat { value, .. } => self.type_of(value),
810            Expression::AccessIndex { base, .. } => self.type_of(base),
811            Expression::Access { base, index } => self.type_of(base).max(self.type_of(index)),
812            Expression::Swizzle { vector, .. } => self.type_of(vector),
813            Expression::Unary { expr, .. } => self.type_of(expr),
814            Expression::Binary { left, right, .. } => self.type_of(left).max(self.type_of(right)),
815            Expression::Math {
816                arg,
817                arg1,
818                arg2,
819                arg3,
820                ..
821            } => self
822                .type_of(arg)
823                .max(
824                    arg1.map(|arg| self.type_of(arg))
825                        .unwrap_or(ExpressionKind::Const),
826                )
827                .max(
828                    arg2.map(|arg| self.type_of(arg))
829                        .unwrap_or(ExpressionKind::Const),
830                )
831                .max(
832                    arg3.map(|arg| self.type_of(arg))
833                        .unwrap_or(ExpressionKind::Const),
834                ),
835            Expression::As { expr, .. } | Expression::Bitcast { expr, .. } => self.type_of(expr),
836            Expression::Select {
837                condition,
838                accept,
839                reject,
840            } => self
841                .type_of(condition)
842                .max(self.type_of(accept))
843                .max(self.type_of(reject)),
844            Expression::Relational { argument, .. } => self.type_of(argument),
845            Expression::ArrayLength(expr) => self.type_of(expr),
846            _ => ExpressionKind::Runtime,
847        }
848    }
849}
850
851#[derive(Clone, Debug, thiserror::Error)]
852#[cfg_attr(test, derive(PartialEq))]
853pub enum ConstantEvaluatorError {
854    #[error("Constants cannot access function arguments")]
855    FunctionArg,
856    #[error("Constants cannot access global variables")]
857    GlobalVariable,
858    #[error("Constants cannot access local variables")]
859    LocalVariable,
860    #[error("Cannot get the array length of a non array type")]
861    InvalidArrayLengthArg,
862    #[error("Constants cannot get the array length of a dynamically sized array")]
863    ArrayLengthDynamic,
864    #[error("Cannot call arrayLength on array sized by override-expression")]
865    ArrayLengthOverridden,
866    #[error("Constants cannot call functions")]
867    Call,
868    #[error("Constants don't support workGroupUniformLoad")]
869    WorkGroupUniformLoadResult,
870    #[error("Constants don't support atomic functions")]
871    Atomic,
872    #[error("Constants don't support derivative functions")]
873    Derivative,
874    #[error("Constants don't support load expressions")]
875    Load,
876    #[error("Constants don't support image expressions")]
877    ImageExpression,
878    #[error("Constants don't support ray query expressions")]
879    RayQueryExpression,
880    #[error("Constants don't support subgroup expressions")]
881    SubgroupExpression,
882    #[error("Cannot access the type")]
883    InvalidAccessBase,
884    #[error("Cannot access at the index")]
885    InvalidAccessIndex,
886    #[error("Cannot access with index of type")]
887    InvalidAccessIndexTy,
888    #[error("Constants don't support array length expressions")]
889    ArrayLength,
890    #[error("Cannot cast scalar components of expression `{from}` to type `{to}`")]
891    InvalidCastArg { from: String, to: String },
892    #[error("Cannot apply the unary op to the argument")]
893    InvalidUnaryOpArg,
894    #[error("Cannot apply the binary op to the arguments")]
895    InvalidBinaryOpArgs,
896    #[error("Cannot apply math function to type")]
897    InvalidMathArg,
898    #[error("{0:?} built-in function expects {1:?} arguments but {2:?} were supplied")]
899    InvalidMathArgCount(crate::MathFunction, usize, usize),
900    #[error("{0} built-in function argument is out of valid range")]
901    InvalidMathArgValue(String),
902    #[error(
903        "`offset` + `count` must be at most {width}, the bit width of the operand of the \
904         {builtin} built-in function, but {offset} + {count} is greater"
905    )]
906    BitfieldRangeTooLarge {
907        builtin: &'static str,
908        offset: u32,
909        count: u32,
910        width: u32,
911    },
912    #[error("Cannot apply relational function to type")]
913    InvalidRelationalArg(RelationalFunction),
914    #[error("value of `low` is greater than `high` for clamp built-in function")]
915    InvalidClamp,
916    #[error("Constructor expects {expected} components, found {actual}")]
917    InvalidVectorComposeLength { expected: usize, actual: usize },
918    #[error("Constructor must only contain vector or scalar arguments")]
919    InvalidVectorComposeComponent,
920    #[error("Splat is defined only on scalar values")]
921    SplatScalarOnly,
922    #[error("Can only swizzle vector constants")]
923    SwizzleVectorOnly,
924    #[error("swizzle component not present in source expression")]
925    SwizzleOutOfBounds,
926    #[error("Type is not constructible")]
927    TypeNotConstructible,
928    #[error("Subexpression(s) are not constant")]
929    SubexpressionsAreNotConstant,
930    #[error("Not implemented as constant expression: {0}")]
931    NotImplemented(String),
932    #[error("{0} operation overflowed")]
933    Overflow(String),
934    #[error(
935        "the concrete type `{to_type}` cannot represent the abstract value `{value}` accurately"
936    )]
937    AutomaticConversionLossy {
938        value: String,
939        to_type: &'static str,
940    },
941    #[error("Division by zero")]
942    DivisionByZero,
943    #[error("Remainder by zero")]
944    RemainderByZero,
945    #[error("RHS of shift operation is greater than or equal to 32")]
946    ShiftedMoreThan32Bits,
947    #[error(transparent)]
948    Literal(#[from] crate::valid::LiteralError),
949    #[error("Can't use pipeline-overridable constants in const-expressions")]
950    Override,
951    #[error("Unexpected runtime-expression")]
952    RuntimeExpr,
953    #[error("Unexpected override-expression")]
954    OverrideExpr,
955    #[error("Expected boolean expression for condition argument of `select`, got something else")]
956    SelectScalarConditionNotABool,
957    #[error(
958        "Expected vectors of the same size for reject and accept args., got {:?} and {:?}",
959        reject,
960        accept
961    )]
962    SelectVecRejectAcceptSizeMismatch {
963        reject: crate::VectorSize,
964        accept: crate::VectorSize,
965    },
966    #[error("Expected boolean vector for condition arg., got something else")]
967    SelectConditionNotAVecBool,
968    #[error(
969        "Expected same number of vector components between condition, accept, and reject args., got something else",
970    )]
971    SelectConditionVecSizeMismatch,
972    #[error(
973        "Expected reject and accept args. to be scalars of vectors of the same type, got something else",
974    )]
975    SelectAcceptRejectTypeMismatch,
976    #[error("Cooperative operations can't be constant")]
977    CooperativeOperation,
978    #[error("Type is too large")]
979    TypeTooLarge(Handle<Type>),
980}
981
982impl<'a> ConstantEvaluator<'a> {
983    /// Return a [`ConstantEvaluator`] that will add expressions to `module`'s
984    /// constant expression arena.
985    ///
986    /// Report errors according to WGSL's rules for constant evaluation.
987    pub const fn for_wgsl_module(
988        module: &'a mut crate::Module,
989        global_expression_kind_tracker: &'a mut ExpressionKindTracker,
990        layouter: &'a mut crate::proc::Layouter,
991        in_override_ctx: bool,
992    ) -> Self {
993        Self::for_module(
994            Behavior::Wgsl(if in_override_ctx {
995                WgslRestrictions::Override
996            } else {
997                WgslRestrictions::Const(None)
998            }),
999            module,
1000            global_expression_kind_tracker,
1001            layouter,
1002        )
1003    }
1004
1005    /// Return a [`ConstantEvaluator`] that will add expressions to `module`'s
1006    /// constant expression arena.
1007    ///
1008    /// Report errors according to GLSL's rules for constant evaluation.
1009    pub const fn for_glsl_module(
1010        module: &'a mut crate::Module,
1011        global_expression_kind_tracker: &'a mut ExpressionKindTracker,
1012        layouter: &'a mut crate::proc::Layouter,
1013    ) -> Self {
1014        Self::for_module(
1015            Behavior::Glsl(GlslRestrictions::Const),
1016            module,
1017            global_expression_kind_tracker,
1018            layouter,
1019        )
1020    }
1021
1022    const fn for_module(
1023        behavior: Behavior<'a>,
1024        module: &'a mut crate::Module,
1025        global_expression_kind_tracker: &'a mut ExpressionKindTracker,
1026        layouter: &'a mut crate::proc::Layouter,
1027    ) -> Self {
1028        Self {
1029            behavior,
1030            types: &mut module.types,
1031            constants: &module.constants,
1032            overrides: &module.overrides,
1033            expressions: &mut module.global_expressions,
1034            expression_kind_tracker: global_expression_kind_tracker,
1035            layouter,
1036        }
1037    }
1038
1039    /// Return a [`ConstantEvaluator`] that will add expressions to `function`'s
1040    /// expression arena.
1041    ///
1042    /// Report errors according to WGSL's rules for constant evaluation.
1043    pub const fn for_wgsl_function(
1044        module: &'a mut crate::Module,
1045        expressions: &'a mut Arena<Expression>,
1046        local_expression_kind_tracker: &'a mut ExpressionKindTracker,
1047        layouter: &'a mut crate::proc::Layouter,
1048        emitter: &'a mut super::Emitter,
1049        block: &'a mut crate::Block,
1050        is_const: bool,
1051    ) -> Self {
1052        let local_data = FunctionLocalData {
1053            global_expressions: &module.global_expressions,
1054            emitter,
1055            block,
1056        };
1057        Self {
1058            behavior: Behavior::Wgsl(if is_const {
1059                WgslRestrictions::Const(Some(local_data))
1060            } else {
1061                WgslRestrictions::Runtime(local_data)
1062            }),
1063            types: &mut module.types,
1064            constants: &module.constants,
1065            overrides: &module.overrides,
1066            expressions,
1067            expression_kind_tracker: local_expression_kind_tracker,
1068            layouter,
1069        }
1070    }
1071
1072    /// Return a [`ConstantEvaluator`] that will add expressions to `function`'s
1073    /// expression arena.
1074    ///
1075    /// Report errors according to GLSL's rules for constant evaluation.
1076    pub const fn for_glsl_function(
1077        module: &'a mut crate::Module,
1078        expressions: &'a mut Arena<Expression>,
1079        local_expression_kind_tracker: &'a mut ExpressionKindTracker,
1080        layouter: &'a mut crate::proc::Layouter,
1081        emitter: &'a mut super::Emitter,
1082        block: &'a mut crate::Block,
1083    ) -> Self {
1084        Self {
1085            behavior: Behavior::Glsl(GlslRestrictions::Runtime(FunctionLocalData {
1086                global_expressions: &module.global_expressions,
1087                emitter,
1088                block,
1089            })),
1090            types: &mut module.types,
1091            constants: &module.constants,
1092            overrides: &module.overrides,
1093            expressions,
1094            expression_kind_tracker: local_expression_kind_tracker,
1095            layouter,
1096        }
1097    }
1098
1099    pub const fn to_ctx(&self) -> crate::proc::GlobalCtx<'_> {
1100        crate::proc::GlobalCtx {
1101            types: self.types,
1102            constants: self.constants,
1103            overrides: self.overrides,
1104            global_expressions: match self.function_local_data() {
1105                Some(data) => data.global_expressions,
1106                None => self.expressions,
1107            },
1108        }
1109    }
1110
1111    fn check(&self, expr: Handle<Expression>) -> Result<(), ConstantEvaluatorError> {
1112        if !self.expression_kind_tracker.is_const(expr) {
1113            log::debug!("check: SubexpressionsAreNotConstant");
1114            return Err(ConstantEvaluatorError::SubexpressionsAreNotConstant);
1115        }
1116        Ok(())
1117    }
1118
1119    fn check_and_get(
1120        &mut self,
1121        expr: Handle<Expression>,
1122    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
1123        match self.expressions[expr] {
1124            Expression::Constant(c) => {
1125                // Are we working in a function's expression arena, or the
1126                // module's constant expression arena?
1127                if let Some(function_local_data) = self.function_local_data() {
1128                    // Deep-copy the constant's value into our arena.
1129                    self.copy_from(
1130                        self.constants[c].init,
1131                        function_local_data.global_expressions,
1132                    )
1133                } else {
1134                    // "See through" the constant and use its initializer.
1135                    Ok(self.constants[c].init)
1136                }
1137            }
1138            _ => {
1139                self.check(expr)?;
1140                Ok(expr)
1141            }
1142        }
1143    }
1144
1145    /// Try to evaluate `expr` at compile time.
1146    ///
1147    /// The `expr` argument can be any sort of Naga [`Expression`] you like. If
1148    /// we can determine its value at compile time, we append an expression
1149    /// representing its value - a tree of [`Literal`], [`Compose`],
1150    /// [`ZeroValue`], and [`Swizzle`] expressions - to the expression arena
1151    /// `self` contributes to.
1152    ///
1153    /// If `expr`'s value cannot be determined at compile time, and `self` is
1154    /// contributing to some function's expression arena, then append `expr` to
1155    /// that arena unchanged (and thus unevaluated). Otherwise, `self` must be
1156    /// contributing to the module's constant expression arena; since `expr`'s
1157    /// value is not a constant, return an error.
1158    ///
1159    /// We only consider `expr` itself, without recursing into its operands. Its
1160    /// operands must all have been produced by prior calls to
1161    /// `try_eval_and_append`, to ensure that they have already been reduced to
1162    /// an evaluated form if possible.
1163    ///
1164    /// [`Literal`]: Expression::Literal
1165    /// [`Compose`]: Expression::Compose
1166    /// [`ZeroValue`]: Expression::ZeroValue
1167    /// [`Swizzle`]: Expression::Swizzle
1168    pub fn try_eval_and_append(
1169        &mut self,
1170        expr: Expression,
1171        span: Span,
1172    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
1173        match self.expression_kind_tracker.type_of_with_expr(&expr) {
1174            ExpressionKind::Const => {
1175                let eval_result = self.try_eval_and_append_impl(&expr, span);
1176                // We should be able to evaluate `Const` expressions at this
1177                // point. If we failed to, then that probably means we just
1178                // haven't implemented that part of constant evaluation. Work
1179                // around this by simply emitting it as a run-time expression.
1180                if self.behavior.has_runtime_restrictions()
1181                    && matches!(
1182                        eval_result,
1183                        Err(ConstantEvaluatorError::NotImplemented(_)
1184                            | ConstantEvaluatorError::InvalidBinaryOpArgs,)
1185                    )
1186                {
1187                    Ok(self.append_expr(expr, span, ExpressionKind::Runtime))
1188                } else {
1189                    eval_result
1190                }
1191            }
1192            ExpressionKind::Override => match self.behavior {
1193                Behavior::Wgsl(WgslRestrictions::Override | WgslRestrictions::Runtime(_)) => {
1194                    Ok(self.append_expr(expr, span, ExpressionKind::Override))
1195                }
1196                Behavior::Wgsl(WgslRestrictions::Const(_)) => {
1197                    Err(ConstantEvaluatorError::OverrideExpr)
1198                }
1199
1200                // GLSL specialization constants (constant_id) become Override expressions
1201                Behavior::Glsl(GlslRestrictions::Runtime(_)) => {
1202                    Ok(self.append_expr(expr, span, ExpressionKind::Override))
1203                }
1204                Behavior::Glsl(GlslRestrictions::Const) => {
1205                    Err(ConstantEvaluatorError::OverrideExpr)
1206                }
1207            },
1208            ExpressionKind::Runtime => {
1209                if self.behavior.has_runtime_restrictions() {
1210                    Ok(self.append_expr(expr, span, ExpressionKind::Runtime))
1211                } else {
1212                    Err(ConstantEvaluatorError::RuntimeExpr)
1213                }
1214            }
1215        }
1216    }
1217
1218    /// Is the [`Self::expressions`] arena the global module expression arena?
1219    const fn is_global_arena(&self) -> bool {
1220        matches!(
1221            self.behavior,
1222            Behavior::Wgsl(WgslRestrictions::Const(None) | WgslRestrictions::Override)
1223                | Behavior::Glsl(GlslRestrictions::Const)
1224        )
1225    }
1226
1227    const fn function_local_data(&self) -> Option<&FunctionLocalData<'a>> {
1228        match self.behavior {
1229            Behavior::Wgsl(
1230                WgslRestrictions::Runtime(ref function_local_data)
1231                | WgslRestrictions::Const(Some(ref function_local_data)),
1232            )
1233            | Behavior::Glsl(GlslRestrictions::Runtime(ref function_local_data)) => {
1234                Some(function_local_data)
1235            }
1236            _ => None,
1237        }
1238    }
1239
1240    fn try_eval_and_append_impl(
1241        &mut self,
1242        expr: &Expression,
1243        span: Span,
1244    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
1245        log::trace!("try_eval_and_append: {expr:?}");
1246        match *expr {
1247            Expression::Constant(c) if self.is_global_arena() => {
1248                // "See through" the constant and use its initializer.
1249                // This is mainly done to avoid having constants pointing to other constants.
1250                Ok(self.constants[c].init)
1251            }
1252            Expression::Override(_) => Err(ConstantEvaluatorError::Override),
1253            Expression::Literal(_) | Expression::ZeroValue(_) | Expression::Constant(_) => {
1254                self.register_evaluated_expr(expr.clone(), span)
1255            }
1256            Expression::Compose { ty, ref components } => {
1257                let components = components
1258                    .iter()
1259                    .map(|component| self.check_and_get(*component))
1260                    .collect::<Result<Vec<_>, _>>()?;
1261                self.register_evaluated_expr(Expression::Compose { ty, components }, span)
1262            }
1263            Expression::Splat { size, value } => {
1264                let value = self.check_and_get(value)?;
1265                self.register_evaluated_expr(Expression::Splat { size, value }, span)
1266            }
1267            Expression::AccessIndex { base, index } => {
1268                let base = self.check_and_get(base)?;
1269
1270                self.access(base, index as usize, span)
1271            }
1272            Expression::Access { base, index } => {
1273                let base = self.check_and_get(base)?;
1274                let index = self.check_and_get(index)?;
1275
1276                let index_val: u32 = self
1277                    .to_ctx()
1278                    .get_const_val_from(index, self.expressions)
1279                    .map_err(|_| ConstantEvaluatorError::InvalidAccessIndexTy)?;
1280                self.access(base, index_val as usize, span)
1281            }
1282            Expression::Swizzle {
1283                size,
1284                vector,
1285                pattern,
1286            } => {
1287                let vector = self.check_and_get(vector)?;
1288
1289                self.swizzle(size, span, vector, pattern)
1290            }
1291            Expression::Unary { expr, op } => {
1292                let expr = self.check_and_get(expr)?;
1293
1294                self.unary_op(op, expr, span)
1295            }
1296            Expression::Binary { left, right, op } => {
1297                let left = self.check_and_get(left)?;
1298                let right = self.check_and_get(right)?;
1299
1300                self.binary_op(op, left, right, span)
1301            }
1302            Expression::Math {
1303                fun,
1304                arg,
1305                arg1,
1306                arg2,
1307                arg3,
1308            } => {
1309                let arg = self.check_and_get(arg)?;
1310                let arg1 = arg1.map(|arg| self.check_and_get(arg)).transpose()?;
1311                let arg2 = arg2.map(|arg| self.check_and_get(arg)).transpose()?;
1312                let arg3 = arg3.map(|arg| self.check_and_get(arg)).transpose()?;
1313
1314                self.math(arg, arg1, arg2, arg3, fun, span)
1315            }
1316            Expression::As { expr, target } => {
1317                let expr = self.check_and_get(expr)?;
1318                self.cast(expr, target, span)
1319            }
1320            Expression::Bitcast { .. } => Err(ConstantEvaluatorError::NotImplemented(
1321                "bitcast built-in function".into(),
1322            )),
1323            Expression::Select {
1324                reject,
1325                accept,
1326                condition,
1327            } => {
1328                let mut arg = |expr| self.check_and_get(expr);
1329
1330                let reject = arg(reject)?;
1331                let accept = arg(accept)?;
1332                let condition = arg(condition)?;
1333
1334                self.select(reject, accept, condition, span)
1335            }
1336            Expression::Relational { fun, argument } => {
1337                let argument = self.check_and_get(argument)?;
1338                self.relational(fun, argument, span)
1339            }
1340            Expression::ArrayLength(expr) => match self.behavior {
1341                Behavior::Wgsl(_) => Err(ConstantEvaluatorError::ArrayLength),
1342                Behavior::Glsl(_) => {
1343                    let expr = self.check_and_get(expr)?;
1344                    self.array_length(expr, span)
1345                }
1346            },
1347            Expression::Load { .. } => Err(ConstantEvaluatorError::Load),
1348            Expression::LocalVariable(_) => Err(ConstantEvaluatorError::LocalVariable),
1349            Expression::Derivative { .. } => Err(ConstantEvaluatorError::Derivative),
1350            Expression::CallResult { .. } => Err(ConstantEvaluatorError::Call),
1351            Expression::WorkGroupUniformLoadResult { .. } => {
1352                Err(ConstantEvaluatorError::WorkGroupUniformLoadResult)
1353            }
1354            Expression::AtomicResult { .. } => Err(ConstantEvaluatorError::Atomic),
1355            Expression::FunctionArgument(_) => Err(ConstantEvaluatorError::FunctionArg),
1356            Expression::GlobalVariable(_) => Err(ConstantEvaluatorError::GlobalVariable),
1357            Expression::ImageSample { .. }
1358            | Expression::ImageLoad { .. }
1359            | Expression::ImageQuery { .. } => Err(ConstantEvaluatorError::ImageExpression),
1360            Expression::RayQueryProceedResult
1361            | Expression::RayQueryGetIntersection { .. }
1362            | Expression::RayQueryVertexPositions { .. }
1363            | Expression::HitObjectQuery { .. } => Err(ConstantEvaluatorError::RayQueryExpression),
1364            Expression::SubgroupBallotResult => Err(ConstantEvaluatorError::SubgroupExpression),
1365            Expression::SubgroupOperationResult { .. } => {
1366                Err(ConstantEvaluatorError::SubgroupExpression)
1367            }
1368            Expression::CooperativeLoad { .. } | Expression::CooperativeMultiplyAdd { .. } => {
1369                Err(ConstantEvaluatorError::CooperativeOperation)
1370            }
1371        }
1372    }
1373
1374    /// Splat `value` to `size`, without using [`Splat`] expressions.
1375    ///
1376    /// This constructs [`Compose`] or [`ZeroValue`] expressions to
1377    /// build a vector with the given `size` whose components are all
1378    /// `value`.
1379    ///
1380    /// Use `span` as the span of the inserted expressions and
1381    /// resulting types.
1382    ///
1383    /// [`Splat`]: Expression::Splat
1384    /// [`Compose`]: Expression::Compose
1385    /// [`ZeroValue`]: Expression::ZeroValue
1386    fn splat(
1387        &mut self,
1388        value: Handle<Expression>,
1389        size: crate::VectorSize,
1390        span: Span,
1391    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
1392        match self.expressions[value] {
1393            Expression::Literal(literal) => {
1394                let scalar = literal.scalar();
1395                let ty = self.types.insert(
1396                    Type {
1397                        name: None,
1398                        inner: TypeInner::Vector { size, scalar },
1399                    },
1400                    span,
1401                );
1402                let expr = Expression::Compose {
1403                    ty,
1404                    components: vec![value; size as usize],
1405                };
1406                self.register_evaluated_expr(expr, span)
1407            }
1408            Expression::ZeroValue(ty) => {
1409                let inner = match self.types[ty].inner {
1410                    TypeInner::Scalar(scalar) => TypeInner::Vector { size, scalar },
1411                    _ => return Err(ConstantEvaluatorError::SplatScalarOnly),
1412                };
1413                let res_ty = self.types.insert(Type { name: None, inner }, span);
1414                let expr = Expression::ZeroValue(res_ty);
1415                self.register_evaluated_expr(expr, span)
1416            }
1417            _ => Err(ConstantEvaluatorError::SplatScalarOnly),
1418        }
1419    }
1420
1421    fn swizzle(
1422        &mut self,
1423        size: crate::VectorSize,
1424        span: Span,
1425        src_constant: Handle<Expression>,
1426        pattern: [crate::SwizzleComponent; 4],
1427    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
1428        let mut get_dst_ty = |ty| match self.types[ty].inner {
1429            TypeInner::Vector { size: _, scalar } => Ok(self.types.insert(
1430                Type {
1431                    name: None,
1432                    inner: TypeInner::Vector { size, scalar },
1433                },
1434                span,
1435            )),
1436            _ => Err(ConstantEvaluatorError::SwizzleVectorOnly),
1437        };
1438
1439        match self.expressions[src_constant] {
1440            Expression::ZeroValue(ty) => {
1441                let dst_ty = get_dst_ty(ty)?;
1442                let expr = Expression::ZeroValue(dst_ty);
1443                self.register_evaluated_expr(expr, span)
1444            }
1445            Expression::Splat { value, .. } => {
1446                let expr = Expression::Splat { size, value };
1447                self.register_evaluated_expr(expr, span)
1448            }
1449            Expression::Compose { ty, ref components } => {
1450                let dst_ty = get_dst_ty(ty)?;
1451
1452                let mut flattened = [src_constant; 4]; // dummy value
1453                let len =
1454                    crate::proc::flatten_compose(ty, components, self.expressions, self.types)
1455                        .zip(flattened.iter_mut())
1456                        .map(|(component, elt)| *elt = component)
1457                        .count();
1458                let flattened = &flattened[..len];
1459
1460                let swizzled_components = pattern[..size as usize]
1461                    .iter()
1462                    .map(|&sc| {
1463                        let sc = sc as usize;
1464                        if let Some(elt) = flattened.get(sc) {
1465                            Ok(*elt)
1466                        } else {
1467                            Err(ConstantEvaluatorError::SwizzleOutOfBounds)
1468                        }
1469                    })
1470                    .collect::<Result<Vec<Handle<Expression>>, _>>()?;
1471                let expr = Expression::Compose {
1472                    ty: dst_ty,
1473                    components: swizzled_components,
1474                };
1475                self.register_evaluated_expr(expr, span)
1476            }
1477            _ => Err(ConstantEvaluatorError::SwizzleVectorOnly),
1478        }
1479    }
1480
1481    fn math(
1482        &mut self,
1483        arg: Handle<Expression>,
1484        arg1: Option<Handle<Expression>>,
1485        arg2: Option<Handle<Expression>>,
1486        arg3: Option<Handle<Expression>>,
1487        fun: crate::MathFunction,
1488        span: Span,
1489    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
1490        let expected = fun.argument_count();
1491        let given = Some(arg)
1492            .into_iter()
1493            .chain(arg1)
1494            .chain(arg2)
1495            .chain(arg3)
1496            .count();
1497        if expected != given {
1498            return Err(ConstantEvaluatorError::InvalidMathArgCount(
1499                fun, expected, given,
1500            ));
1501        }
1502
1503        // NOTE: We try to match the declaration order of `MathFunction` here.
1504        match fun {
1505            // comparison
1506            crate::MathFunction::Abs => {
1507                component_wise_scalar(self, span, [arg], |args| match args {
1508                    Scalar::AbstractFloat([e]) => Ok(Scalar::AbstractFloat([e.abs()])),
1509                    Scalar::F32([e]) => Ok(Scalar::F32([e.abs()])),
1510                    Scalar::F16([e]) => Ok(Scalar::F16([e.abs()])),
1511                    Scalar::AbstractInt([e]) => Ok(Scalar::AbstractInt([e.wrapping_abs()])),
1512                    Scalar::I32([e]) => Ok(Scalar::I32([e.wrapping_abs()])),
1513                    Scalar::U32([e]) => Ok(Scalar::U32([e])), // TODO: just re-use the expression, ezpz
1514                    Scalar::I64([e]) => Ok(Scalar::I64([e.wrapping_abs()])),
1515                    Scalar::U64([e]) => Ok(Scalar::U64([e])),
1516                })
1517            }
1518            crate::MathFunction::Min => {
1519                component_wise_scalar!(self, span, [arg, arg1.unwrap()], |e1, e2| {
1520                    Ok([e1.min(e2)])
1521                })
1522            }
1523            crate::MathFunction::Max => {
1524                component_wise_scalar!(self, span, [arg, arg1.unwrap()], |e1, e2| {
1525                    Ok([e1.max(e2)])
1526                })
1527            }
1528            crate::MathFunction::Clamp => {
1529                component_wise_scalar!(
1530                    self,
1531                    span,
1532                    [arg, arg1.unwrap(), arg2.unwrap()],
1533                    |e, low, high| {
1534                        if low > high {
1535                            Err(ConstantEvaluatorError::InvalidClamp)
1536                        } else {
1537                            Ok([e.clamp(low, high)])
1538                        }
1539                    }
1540                )
1541            }
1542            crate::MathFunction::Saturate => component_wise_float(self, span, [arg], |e| match e {
1543                Float::F16([e]) => Ok(Float::F16(
1544                    [e.clamp(f16::from_f32(0.0), f16::from_f32(1.0))],
1545                )),
1546                Float::F32([e]) => Ok(Float::F32([e.clamp(0., 1.)])),
1547                Float::Abstract([e]) => Ok(Float::Abstract([e.clamp(0., 1.)])),
1548            }),
1549
1550            // trigonometry
1551            crate::MathFunction::Cos => {
1552                component_wise_float!(self, span, [arg], |e| { Ok([e.cos()]) })
1553            }
1554            crate::MathFunction::Cosh => {
1555                component_wise_float!(self, span, [arg], |e| {
1556                    let result = e.cosh();
1557                    if result.is_finite() {
1558                        Ok([result])
1559                    } else {
1560                        Err(ConstantEvaluatorError::Overflow("cosh".into()))
1561                    }
1562                })
1563            }
1564            crate::MathFunction::Sin => {
1565                component_wise_float!(self, span, [arg], |e| { Ok([e.sin()]) })
1566            }
1567            crate::MathFunction::Sinh => {
1568                component_wise_float!(self, span, [arg], |e| {
1569                    let result = e.sinh();
1570                    if result.is_finite() {
1571                        Ok([result])
1572                    } else {
1573                        Err(ConstantEvaluatorError::Overflow("sinh".into()))
1574                    }
1575                })
1576            }
1577            crate::MathFunction::Tan => {
1578                component_wise_float!(self, span, [arg], |e| { Ok([e.tan()]) })
1579            }
1580            crate::MathFunction::Tanh => {
1581                component_wise_float!(self, span, [arg], |e| { Ok([e.tanh()]) })
1582            }
1583            crate::MathFunction::Acos => {
1584                component_wise_float!(self, span, [arg], |e| {
1585                    if e.abs() <= One::one() {
1586                        Ok([e.acos()])
1587                    } else {
1588                        Err(ConstantEvaluatorError::InvalidMathArgValue("acos".into()))
1589                    }
1590                })
1591            }
1592            crate::MathFunction::Asin => {
1593                component_wise_float!(self, span, [arg], |e| {
1594                    if e.abs() <= One::one() {
1595                        Ok([e.asin()])
1596                    } else {
1597                        Err(ConstantEvaluatorError::InvalidMathArgValue("asin".into()))
1598                    }
1599                })
1600            }
1601            crate::MathFunction::Atan => {
1602                component_wise_float!(self, span, [arg], |e| { Ok([e.atan()]) })
1603            }
1604            crate::MathFunction::Atan2 => {
1605                component_wise_float!(self, span, [arg, arg1.unwrap()], |y, x| {
1606                    Ok([y.atan2(x)])
1607                })
1608            }
1609            crate::MathFunction::Asinh => component_wise_float(self, span, [arg], |e| match e {
1610                Float::Abstract([e]) => Ok(Float::Abstract([libm::asinh(e)])),
1611                Float::F32([e]) => Ok(Float::F32([(e as f64).asinh() as f32])),
1612                Float::F16([e]) => Ok(Float::F16([e.asinh()])),
1613            }),
1614            crate::MathFunction::Acosh => component_wise_float(self, span, [arg], |e| match e {
1615                Float::Abstract([e]) if e >= One::one() => Ok(Float::Abstract([libm::acosh(e)])),
1616                Float::F32([e]) if e >= One::one() => Ok(Float::F32([(e as f64).acosh() as f32])),
1617                Float::F16([e]) if e >= One::one() => Ok(Float::F16([e.acosh()])),
1618                _ => Err(ConstantEvaluatorError::InvalidMathArgValue("acosh".into())),
1619            }),
1620            crate::MathFunction::Atanh => {
1621                component_wise_float!(self, span, [arg], |e| {
1622                    if e.abs() < One::one() {
1623                        Ok([e.atanh()])
1624                    } else {
1625                        Err(ConstantEvaluatorError::InvalidMathArgValue("atanh".into()))
1626                    }
1627                })
1628            }
1629            crate::MathFunction::Radians => {
1630                component_wise_float!(self, span, [arg], |e1| { Ok([e1.to_radians()]) })
1631            }
1632            crate::MathFunction::Degrees => {
1633                component_wise_float!(self, span, [arg], |e| {
1634                    let result = e.to_degrees();
1635                    if result.is_finite() {
1636                        Ok([result])
1637                    } else {
1638                        Err(ConstantEvaluatorError::Overflow("degrees".into()))
1639                    }
1640                })
1641            }
1642
1643            // decomposition
1644            crate::MathFunction::Ceil => {
1645                component_wise_float!(self, span, [arg], |e| { Ok([e.ceil()]) })
1646            }
1647            crate::MathFunction::Floor => {
1648                component_wise_float!(self, span, [arg], |e| { Ok([e.floor()]) })
1649            }
1650            crate::MathFunction::Round => {
1651                component_wise_float(self, span, [arg], |e| match e {
1652                    Float::Abstract([e]) => Ok(Float::Abstract([libm::rint(e)])),
1653                    Float::F32([e]) => Ok(Float::F32([libm::rintf(e)])),
1654                    Float::F16([e]) => {
1655                        // TODO: `round_ties_even` is not available on `half::f16` yet.
1656                        //
1657                        // This polyfill is shamelessly [~~stolen from~~ inspired by `ndarray-image`][polyfill source],
1658                        // which has licensing compatible with ours. See also
1659                        // <https://github.com/rust-lang/rust/issues/96710>.
1660                        //
1661                        // [polyfill source]: https://github.com/imeka/ndarray-ndimage/blob/8b14b4d6ecfbc96a8a052f802e342a7049c68d8f/src/lib.rs#L98
1662                        fn round_ties_even(x: f64) -> f64 {
1663                            let i = x as i64;
1664                            let f = (x - i as f64).abs();
1665                            if f == 0.5 {
1666                                if i & 1 == 1 {
1667                                    // -1.5, 1.5, 3.5, ...
1668                                    (x.abs() + 0.5).copysign(x)
1669                                } else {
1670                                    (x.abs() - 0.5).copysign(x)
1671                                }
1672                            } else {
1673                                x.round()
1674                            }
1675                        }
1676
1677                        Ok(Float::F16([(f16::from_f64(round_ties_even(f64::from(e))))]))
1678                    }
1679                })
1680            }
1681            crate::MathFunction::Fract => {
1682                component_wise_float!(self, span, [arg], |e| {
1683                    // N.B., Rust's definition of `fract` is `e - e.trunc()`, so we can't use that
1684                    // here.
1685                    Ok([e - e.floor()])
1686                })
1687            }
1688            crate::MathFunction::Trunc => {
1689                component_wise_float!(self, span, [arg], |e| { Ok([e.trunc()]) })
1690            }
1691
1692            // exponent
1693            crate::MathFunction::Exp => {
1694                component_wise_float!(self, span, [arg], |e| {
1695                    let result = e.exp();
1696                    if result.is_finite() {
1697                        Ok([result])
1698                    } else {
1699                        Err(ConstantEvaluatorError::Overflow("exp".into()))
1700                    }
1701                })
1702            }
1703            crate::MathFunction::Exp2 => {
1704                component_wise_float!(self, span, [arg], |e| {
1705                    let result = e.exp2();
1706                    if result.is_finite() {
1707                        Ok([result])
1708                    } else {
1709                        Err(ConstantEvaluatorError::Overflow("exp2".into()))
1710                    }
1711                })
1712            }
1713            crate::MathFunction::Log => {
1714                component_wise_float!(self, span, [arg], |e| {
1715                    if e > Zero::zero() {
1716                        Ok([e.ln()])
1717                    } else {
1718                        Err(ConstantEvaluatorError::InvalidMathArgValue("log".into()))
1719                    }
1720                })
1721            }
1722            crate::MathFunction::Log2 => {
1723                component_wise_float!(self, span, [arg], |e| {
1724                    if e > Zero::zero() {
1725                        Ok([e.log2()])
1726                    } else {
1727                        Err(ConstantEvaluatorError::InvalidMathArgValue("log2".into()))
1728                    }
1729                })
1730            }
1731            crate::MathFunction::Pow => {
1732                component_wise_float!(self, span, [arg, arg1.unwrap()], |e1, e2| {
1733                    // 0.pow(0) is an error since exp2(0 * log2(0)) is NaN.
1734                    // https://www.w3.org/TR/WGSL/#pow-builtin
1735                    if e1 < Zero::zero()
1736                        || e1.is_one() && e2.is_infinite()
1737                        || e1.is_infinite() && e2.is_zero()
1738                        || e1.is_zero() && e2.is_zero()
1739                    {
1740                        Err(ConstantEvaluatorError::InvalidMathArgValue("pow".into()))
1741                    } else {
1742                        let result = e1.powf(e2);
1743                        if result.is_finite() {
1744                            Ok([result])
1745                        } else {
1746                            Err(ConstantEvaluatorError::Overflow("pow".into()))
1747                        }
1748                    }
1749                })
1750            }
1751
1752            // computational
1753            crate::MathFunction::Sign => {
1754                component_wise_signed!(self, span, [arg], |e| {
1755                    Ok([if e.is_zero() {
1756                        Zero::zero()
1757                    } else {
1758                        e.signum()
1759                    }])
1760                })
1761            }
1762            crate::MathFunction::Fma => {
1763                component_wise_float!(
1764                    self,
1765                    span,
1766                    [arg, arg1.unwrap(), arg2.unwrap()],
1767                    |e1, e2, e3| { Ok([e1.mul_add(e2, e3)]) }
1768                )
1769            }
1770            crate::MathFunction::Step => {
1771                component_wise_float(self, span, [arg, arg1.unwrap()], |x| match x {
1772                    Float::Abstract([edge, x]) => {
1773                        Ok(Float::Abstract([if edge <= x { 1.0 } else { 0.0 }]))
1774                    }
1775                    Float::F32([edge, x]) => Ok(Float::F32([if edge <= x { 1.0 } else { 0.0 }])),
1776                    Float::F16([edge, x]) => Ok(Float::F16([if edge <= x {
1777                        f16::one()
1778                    } else {
1779                        f16::zero()
1780                    }])),
1781                })
1782            }
1783            crate::MathFunction::Sqrt => {
1784                component_wise_float!(self, span, [arg], |e| {
1785                    if e >= Zero::zero() {
1786                        Ok([e.sqrt()])
1787                    } else {
1788                        Err(ConstantEvaluatorError::InvalidMathArgValue("sqrt".into()))
1789                    }
1790                })
1791            }
1792            crate::MathFunction::InverseSqrt => {
1793                component_wise_float(self, span, [arg], |e| match e {
1794                    Float::Abstract([e]) => Ok(Float::Abstract([1. / e.sqrt()])),
1795                    Float::F32([e]) => Ok(Float::F32([1. / e.sqrt()])),
1796                    Float::F16([e]) => Ok(Float::F16([f16::from_f32(1. / f32::from(e).sqrt())])),
1797                })
1798            }
1799
1800            // bits
1801            crate::MathFunction::CountTrailingZeros => {
1802                component_wise_concrete_int!(self, span, [arg], |e| {
1803                    #[allow(clippy::useless_conversion)]
1804                    Ok([e
1805                        .trailing_zeros()
1806                        .try_into()
1807                        .expect("bit count overflowed 32 bits, somehow!?")])
1808                })
1809            }
1810            crate::MathFunction::CountLeadingZeros => {
1811                component_wise_concrete_int!(self, span, [arg], |e| {
1812                    #[allow(clippy::useless_conversion)]
1813                    Ok([e
1814                        .leading_zeros()
1815                        .try_into()
1816                        .expect("bit count overflowed 32 bits, somehow!?")])
1817                })
1818            }
1819            crate::MathFunction::CountOneBits => {
1820                component_wise_concrete_int!(self, span, [arg], |e| {
1821                    #[allow(clippy::useless_conversion)]
1822                    Ok([e
1823                        .count_ones()
1824                        .try_into()
1825                        .expect("bit count overflowed 32 bits, somehow!?")])
1826                })
1827            }
1828            crate::MathFunction::ReverseBits => {
1829                component_wise_concrete_int!(self, span, [arg], |e| { Ok([e.reverse_bits()]) })
1830            }
1831            crate::MathFunction::ExtractBits => {
1832                // https://www.w3.org/TR/WGSL/#extractBits-signed-builtin
1833                let (offset, count) = self.bitfield_range(arg1.unwrap(), arg2.unwrap(), span)?;
1834                let e = self.extract_vec(arg, true)?;
1835
1836                let result = match_literal_vector!(match e => LiteralVector {
1837                    I16 => |e| { extract_bits(e, offset, count)? },
1838                    U16 => |e| { extract_bits(e, offset, count)? },
1839                    I32 => |e| { extract_bits(e, offset, count)? },
1840                    U32 => |e| { extract_bits(e, offset, count)? },
1841                    I64 => |e| { extract_bits(e, offset, count)? },
1842                    U64 => |e| { extract_bits(e, offset, count)? },
1843                })?;
1844                result.register_as_evaluated_expr(self, span)
1845            }
1846            crate::MathFunction::InsertBits => {
1847                // https://www.w3.org/TR/WGSL/#insertBits-builtin
1848                let (offset, count) = self.bitfield_range(arg2.unwrap(), arg3.unwrap(), span)?;
1849                let e = self.extract_vec(arg, true)?;
1850                let newbits = self.extract_vec(arg1.unwrap(), true)?;
1851                if e.len() != newbits.len() {
1852                    return Err(ConstantEvaluatorError::InvalidMathArg);
1853                }
1854
1855                let result = match_literal_vector!(match (e, newbits) => LiteralVector {
1856                    I16 => |e, n| { insert_bits(e, n, offset, count)? },
1857                    U16 => |e, n| { insert_bits(e, n, offset, count)? },
1858                    I32 => |e, n| { insert_bits(e, n, offset, count)? },
1859                    U32 => |e, n| { insert_bits(e, n, offset, count)? },
1860                    I64 => |e, n| { insert_bits(e, n, offset, count)? },
1861                    U64 => |e, n| { insert_bits(e, n, offset, count)? },
1862                })?;
1863                result.register_as_evaluated_expr(self, span)
1864            }
1865            crate::MathFunction::FirstTrailingBit => {
1866                component_wise_concrete_int(self, span, [arg], |ci| Ok(first_trailing_bit(ci)))
1867            }
1868            crate::MathFunction::FirstLeadingBit => {
1869                component_wise_concrete_int(self, span, [arg], |ci| Ok(first_leading_bit(ci)))
1870            }
1871
1872            // vector
1873            crate::MathFunction::Dot4I8Packed => {
1874                self.packed_dot_product(arg, arg1.unwrap(), span, true)
1875            }
1876            crate::MathFunction::Dot4U8Packed => {
1877                self.packed_dot_product(arg, arg1.unwrap(), span, false)
1878            }
1879            crate::MathFunction::Cross => self.cross_product(arg, arg1.unwrap(), span),
1880            crate::MathFunction::Dot => {
1881                // https://www.w3.org/TR/WGSL/#dot-builtin
1882                let e1 = self.extract_vec(arg, false)?;
1883                let e2 = self.extract_vec(arg1.unwrap(), false)?;
1884                if e1.len() != e2.len() {
1885                    return Err(ConstantEvaluatorError::InvalidMathArg);
1886                }
1887
1888                fn int_dot_checked<P>(a: &[P], b: &[P]) -> Result<P, ConstantEvaluatorError>
1889                where
1890                    P: num_traits::PrimInt + num_traits::CheckedAdd + num_traits::CheckedMul,
1891                {
1892                    a.iter()
1893                        .zip(b.iter())
1894                        .map(|(&aa, bb)| aa.checked_mul(bb))
1895                        .try_fold(P::zero(), |acc, x| {
1896                            if let Some(x) = x {
1897                                acc.checked_add(&x)
1898                            } else {
1899                                None
1900                            }
1901                        })
1902                        .ok_or(ConstantEvaluatorError::Overflow(
1903                            "in dot built-in".to_string(),
1904                        ))
1905                }
1906
1907                fn int_dot_wrapping<P>(a: &[P], b: &[P]) -> P
1908                where
1909                    P: num_traits::PrimInt + num_traits::WrappingAdd + num_traits::WrappingMul,
1910                {
1911                    a.iter()
1912                        .zip(b.iter())
1913                        .map(|(&aa, bb)| aa.wrapping_mul(bb))
1914                        .fold(P::zero(), |acc, x| acc.wrapping_add(&x))
1915                }
1916
1917                let result = match_literal_vector!(match (e1, e2) => Literal {
1918                    Float => |e1, e2| {
1919                        float_dot(e1, e2).ok_or_else(|| {
1920                            ConstantEvaluatorError::Overflow("in mathfunction::dot".into())
1921                        })?
1922                    },
1923                    AbstractInt => |e1, e2 | { int_dot_checked(e1, e2)? },
1924                    I32 => |e1, e2| { int_dot_wrapping(e1, e2) },
1925                    U32 => |e1, e2| { int_dot_wrapping(e1, e2) },
1926                })?;
1927                self.register_evaluated_expr(Expression::Literal(result), span)
1928            }
1929            crate::MathFunction::Length => {
1930                // https://www.w3.org/TR/WGSL/#length-builtin
1931                let e1 = self.extract_vec(arg, true)?;
1932
1933                let result = match_literal_vector!(match e1 => Literal {
1934                    Float => |e1| {
1935                        float_length(e1).ok_or_else(|| ConstantEvaluatorError::Overflow("length".into()))?
1936                    },
1937                })?;
1938                self.register_evaluated_expr(Expression::Literal(result), span)
1939            }
1940            crate::MathFunction::Distance => {
1941                // https://www.w3.org/TR/WGSL/#distance-builtin
1942                let e1 = self.extract_vec(arg, true)?;
1943                let e2 = self.extract_vec(arg1.unwrap(), true)?;
1944                if e1.len() != e2.len() {
1945                    return Err(ConstantEvaluatorError::InvalidMathArg);
1946                }
1947
1948                fn float_distance<F>(a: &[F], b: &[F]) -> F
1949                where
1950                    F: core::ops::Mul<F>,
1951                    F: num_traits::Float + iter::Sum + core::ops::Sub,
1952                {
1953                    if a.len() == 1 {
1954                        // Avoids possible overflow in squaring
1955                        (a[0] - b[0]).abs()
1956                    } else {
1957                        a.iter()
1958                            .zip(b.iter())
1959                            .map(|(&aa, &bb)| aa - bb)
1960                            .map(|ei| ei * ei)
1961                            .sum::<F>()
1962                            .sqrt()
1963                    }
1964                }
1965                let result = match_literal_vector!(match (e1, e2) => Literal {
1966                    Float => |e1, e2| { float_distance(e1, e2) },
1967                })?;
1968                self.register_evaluated_expr(Expression::Literal(result), span)
1969            }
1970            crate::MathFunction::Normalize => {
1971                // https://www.w3.org/TR/WGSL/#normalize-builtin
1972                let e1 = self.extract_vec(arg, true)?;
1973
1974                fn float_normalize<F>(
1975                    e: &[F],
1976                ) -> Result<ArrayVec<F, { crate::VectorSize::MAX }>, ConstantEvaluatorError>
1977                where
1978                    F: core::ops::Mul<F>,
1979                    F: num_traits::Float + iter::Sum,
1980                {
1981                    let len = match float_length(e) {
1982                        Some(len) if !len.is_zero() => Ok(len),
1983                        Some(_) => Err(ConstantEvaluatorError::InvalidMathArgValue(
1984                            "normalize".into(),
1985                        )),
1986                        None => Err(ConstantEvaluatorError::Overflow("normalize".into())),
1987                    }?;
1988
1989                    let mut out = ArrayVec::new();
1990                    for &ei in e {
1991                        out.push(ei / len);
1992                    }
1993                    Ok(out)
1994                }
1995
1996                let result = match_literal_vector!(match e1 => LiteralVector {
1997                    Float => |e1| { float_normalize(e1)? },
1998                })?;
1999                result.register_as_evaluated_expr(self, span)
2000            }
2001            crate::MathFunction::FaceForward => {
2002                // https://www.w3.org/TR/WGSL/#faceForward-builtin
2003                let e1 = self.extract_vec(arg, false)?;
2004                let e2 = self.extract_vec(arg1.unwrap(), false)?;
2005                let e3 = self.extract_vec(arg2.unwrap(), false)?;
2006                if e1.len() != e2.len() || e1.len() != e3.len() {
2007                    return Err(ConstantEvaluatorError::InvalidMathArg);
2008                }
2009
2010                let result = match_literal_vector!(match (e1, e2, e3) => LiteralVector {
2011                    Float => |e1, e2, e3| {
2012                        float_face_forward(e1, e2, e3).ok_or_else(|| {
2013                            ConstantEvaluatorError::Overflow("in mathfunction::faceforward".into())
2014                        })?
2015                    },
2016                })?;
2017                result.register_as_evaluated_expr(self, span)
2018            }
2019            crate::MathFunction::Reflect => {
2020                // https://www.w3.org/TR/WGSL/#reflect-builtin
2021                let e1 = self.extract_vec(arg, false)?;
2022                let e2 = self.extract_vec(arg1.unwrap(), false)?;
2023                if e1.len() != e2.len() {
2024                    return Err(ConstantEvaluatorError::InvalidMathArg);
2025                }
2026
2027                let result = match_literal_vector!(match (e1, e2) => LiteralVector {
2028                    Float => |e1, e2| {
2029                        float_reflect(e1, e2)
2030                            .ok_or_else(|| ConstantEvaluatorError::Overflow("in mathfunction::reflect".into()))?
2031                    },
2032                })?;
2033                result.register_as_evaluated_expr(self, span)
2034            }
2035            crate::MathFunction::Refract => {
2036                // https://www.w3.org/TR/WGSL/#refract-builtin
2037                let e1 = self.extract_vec(arg, false)?;
2038                let e2 = self.extract_vec(arg1.unwrap(), false)?;
2039                // `e3` is the scalar ratio of indices of refraction, extracted
2040                // as a LiteralVector like `e1` and `e2`.
2041                let e3 = self.extract_vec(arg2.unwrap(), true)?;
2042                if e1.len() != e2.len() || e3.len() != 1 {
2043                    return Err(ConstantEvaluatorError::InvalidMathArg);
2044                }
2045
2046                let result = match_literal_vector!(match (e1, e2, e3) => LiteralVector {
2047                    Float => |e1, e2, e3| {
2048                        float_refract(e1, e2, e3[0])
2049                            .ok_or_else(|| ConstantEvaluatorError::Overflow("in mathfunction::refract".into()))?
2050                    },
2051                })?;
2052                result.register_as_evaluated_expr(self, span)
2053            }
2054
2055            // unimplemented
2056            crate::MathFunction::Modf
2057            | crate::MathFunction::Frexp
2058            | crate::MathFunction::Ldexp
2059            | crate::MathFunction::Outer
2060            | crate::MathFunction::Mix
2061            | crate::MathFunction::SmoothStep
2062            | crate::MathFunction::Inverse
2063            | crate::MathFunction::Transpose
2064            | crate::MathFunction::Determinant
2065            | crate::MathFunction::QuantizeToF16
2066            | crate::MathFunction::Pack4x8snorm
2067            | crate::MathFunction::Pack4x8unorm
2068            | crate::MathFunction::Pack2x16snorm
2069            | crate::MathFunction::Pack2x16unorm
2070            | crate::MathFunction::Pack2x16float
2071            | crate::MathFunction::Pack4xI8
2072            | crate::MathFunction::Pack4xU8
2073            | crate::MathFunction::Pack4xI8Clamp
2074            | crate::MathFunction::Pack4xU8Clamp
2075            | crate::MathFunction::Unpack4x8snorm
2076            | crate::MathFunction::Unpack4x8unorm
2077            | crate::MathFunction::Unpack2x16snorm
2078            | crate::MathFunction::Unpack2x16unorm
2079            | crate::MathFunction::Unpack2x16float
2080            | crate::MathFunction::Unpack4xI8
2081            | crate::MathFunction::Unpack4xU8 => Err(ConstantEvaluatorError::NotImplemented(
2082                format!("{fun:?} built-in function"),
2083            )),
2084        }
2085    }
2086
2087    /// Dot product of two packed vectors (`dot4I8Packed` and `dot4U8Packed`)
2088    fn packed_dot_product(
2089        &mut self,
2090        a: Handle<Expression>,
2091        b: Handle<Expression>,
2092        span: Span,
2093        signed: bool,
2094    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
2095        let Expression::Literal(Literal::U32(a)) = self.expressions[a] else {
2096            return Err(ConstantEvaluatorError::InvalidMathArg);
2097        };
2098        let Expression::Literal(Literal::U32(b)) = self.expressions[b] else {
2099            return Err(ConstantEvaluatorError::InvalidMathArg);
2100        };
2101
2102        let result = if signed {
2103            Literal::I32(
2104                (a & 0xFF) as i8 as i32 * (b & 0xFF) as i8 as i32
2105                    + ((a >> 8) & 0xFF) as i8 as i32 * ((b >> 8) & 0xFF) as i8 as i32
2106                    + ((a >> 16) & 0xFF) as i8 as i32 * ((b >> 16) & 0xFF) as i8 as i32
2107                    + ((a >> 24) & 0xFF) as i8 as i32 * ((b >> 24) & 0xFF) as i8 as i32,
2108            )
2109        } else {
2110            Literal::U32(
2111                (a & 0xFF) * (b & 0xFF)
2112                    + ((a >> 8) & 0xFF) * ((b >> 8) & 0xFF)
2113                    + ((a >> 16) & 0xFF) * ((b >> 16) & 0xFF)
2114                    + ((a >> 24) & 0xFF) * ((b >> 24) & 0xFF),
2115            )
2116        };
2117
2118        self.register_evaluated_expr(Expression::Literal(result), span)
2119    }
2120
2121    /// Vector cross product.
2122    fn cross_product(
2123        &mut self,
2124        a: Handle<Expression>,
2125        b: Handle<Expression>,
2126        span: Span,
2127    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
2128        use Literal as Li;
2129
2130        let (a, ty) = self.extract_vec_with_size::<3>(a)?;
2131        let (b, _) = self.extract_vec_with_size::<3>(b)?;
2132
2133        let product = match (a, b) {
2134            (
2135                [Li::AbstractInt(a0), Li::AbstractInt(a1), Li::AbstractInt(a2)],
2136                [Li::AbstractInt(b0), Li::AbstractInt(b1), Li::AbstractInt(b2)],
2137            ) => {
2138                // `cross` has no overload for AbstractInt, so AbstractInt
2139                // arguments are automatically converted to AbstractFloat. Since
2140                // `f64` has a much wider range than `i64`, there's no danger of
2141                // overflow here.
2142                let p = cross_product(
2143                    [a0 as f64, a1 as f64, a2 as f64],
2144                    [b0 as f64, b1 as f64, b2 as f64],
2145                );
2146                [
2147                    Li::AbstractFloat(p[0]),
2148                    Li::AbstractFloat(p[1]),
2149                    Li::AbstractFloat(p[2]),
2150                ]
2151            }
2152            (
2153                [Li::AbstractFloat(a0), Li::AbstractFloat(a1), Li::AbstractFloat(a2)],
2154                [Li::AbstractFloat(b0), Li::AbstractFloat(b1), Li::AbstractFloat(b2)],
2155            ) => {
2156                let p = cross_product([a0, a1, a2], [b0, b1, b2]);
2157                [
2158                    Li::AbstractFloat(p[0]),
2159                    Li::AbstractFloat(p[1]),
2160                    Li::AbstractFloat(p[2]),
2161                ]
2162            }
2163            ([Li::F16(a0), Li::F16(a1), Li::F16(a2)], [Li::F16(b0), Li::F16(b1), Li::F16(b2)]) => {
2164                let p = cross_product([a0, a1, a2], [b0, b1, b2]);
2165                [Li::F16(p[0]), Li::F16(p[1]), Li::F16(p[2])]
2166            }
2167            ([Li::F32(a0), Li::F32(a1), Li::F32(a2)], [Li::F32(b0), Li::F32(b1), Li::F32(b2)]) => {
2168                let p = cross_product([a0, a1, a2], [b0, b1, b2]);
2169                [Li::F32(p[0]), Li::F32(p[1]), Li::F32(p[2])]
2170            }
2171            ([Li::F64(a0), Li::F64(a1), Li::F64(a2)], [Li::F64(b0), Li::F64(b1), Li::F64(b2)]) => {
2172                let p = cross_product([a0, a1, a2], [b0, b1, b2]);
2173                [Li::F64(p[0]), Li::F64(p[1]), Li::F64(p[2])]
2174            }
2175            _ => return Err(ConstantEvaluatorError::InvalidMathArg),
2176        };
2177
2178        let p0 = self.register_evaluated_expr(Expression::Literal(product[0]), span)?;
2179        let p1 = self.register_evaluated_expr(Expression::Literal(product[1]), span)?;
2180        let p2 = self.register_evaluated_expr(Expression::Literal(product[2]), span)?;
2181
2182        self.register_evaluated_expr(
2183            Expression::Compose {
2184                ty,
2185                components: vec![p0, p1, p2],
2186            },
2187            span,
2188        )
2189    }
2190
2191    /// Extract the values of a `vecN` from `expr`.
2192    ///
2193    /// Return the value of `expr`, whose type is `vecN<S>` for some
2194    /// vector size `N` and scalar `S`, as an array of `N` [`Literal`]
2195    /// values.
2196    ///
2197    /// Also return the type handle from the `Compose` expression.
2198    fn extract_vec_with_size<const N: usize>(
2199        &mut self,
2200        expr: Handle<Expression>,
2201    ) -> Result<([Literal; N], Handle<Type>), ConstantEvaluatorError> {
2202        let span = self.expressions.get_span(expr);
2203        let expr = self.eval_zero_value_and_splat(expr, span)?;
2204        let Expression::Compose { ty, ref components } = self.expressions[expr] else {
2205            return Err(ConstantEvaluatorError::InvalidMathArg);
2206        };
2207
2208        let mut value = [Literal::Bool(false); N];
2209        for (component, elt) in
2210            crate::proc::flatten_compose(ty, components, self.expressions, self.types)
2211                .zip(value.iter_mut())
2212        {
2213            let Expression::Literal(literal) = self.expressions[component] else {
2214                return Err(ConstantEvaluatorError::InvalidMathArg);
2215            };
2216            *elt = literal;
2217        }
2218
2219        Ok((value, ty))
2220    }
2221
2222    /// Extract the values of a `vecN` from `expr`.
2223    ///
2224    /// Return the value of `expr`, whose type is `vecN<S>` for some
2225    /// vector size `N` and scalar `S`, as an array of `N` [`Literal`]
2226    /// values.
2227    ///
2228    /// Also return the type handle from the `Compose` expression.
2229    fn extract_vec(
2230        &mut self,
2231        expr: Handle<Expression>,
2232        allow_single: bool,
2233    ) -> Result<LiteralVector, ConstantEvaluatorError> {
2234        let span = self.expressions.get_span(expr);
2235        let expr = self.eval_zero_value_and_splat(expr, span)?;
2236
2237        match self.expressions[expr] {
2238            Expression::Literal(literal) if allow_single => {
2239                Ok(LiteralVector::from_literal(literal))
2240            }
2241            Expression::Compose { ty, ref components } => {
2242                let mut components_out = ArrayVec::<Literal, { crate::VectorSize::MAX }>::new();
2243                for expr in
2244                    crate::proc::flatten_compose(ty, components, self.expressions, self.types)
2245                {
2246                    match self.expressions[expr] {
2247                        Expression::Literal(l) => components_out.push(l),
2248                        _ => return Err(ConstantEvaluatorError::InvalidMathArg),
2249                    }
2250                }
2251                LiteralVector::from_literal_vec(components_out)
2252            }
2253            _ => Err(ConstantEvaluatorError::InvalidMathArg),
2254        }
2255    }
2256
2257    /// Extract the `offset` and `count` arguments shared by the `extractBits`
2258    /// and `insertBits` built ins, both of which are `u32` scalars.
2259    fn bitfield_range(
2260        &mut self,
2261        offset: Handle<Expression>,
2262        count: Handle<Expression>,
2263        span: Span,
2264    ) -> Result<(u32, u32), ConstantEvaluatorError> {
2265        let offset = self.eval_zero_value_and_splat(offset, span)?;
2266        let count = self.eval_zero_value_and_splat(count, span)?;
2267
2268        match (&self.expressions[offset], &self.expressions[count]) {
2269            (
2270                &Expression::Literal(Literal::U32(offset)),
2271                &Expression::Literal(Literal::U32(count)),
2272            ) => Ok((offset, count)),
2273            _ => Err(ConstantEvaluatorError::InvalidMathArg),
2274        }
2275    }
2276
2277    fn array_length(
2278        &mut self,
2279        array: Handle<Expression>,
2280        span: Span,
2281    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
2282        match self.expressions[array] {
2283            Expression::ZeroValue(ty) | Expression::Compose { ty, .. } => {
2284                match self.types[ty].inner {
2285                    TypeInner::Array { size, .. } => match size {
2286                        ArraySize::Constant(len) => {
2287                            let expr = Expression::Literal(Literal::U32(len.get()));
2288                            self.register_evaluated_expr(expr, span)
2289                        }
2290                        ArraySize::Pending(_) => Err(ConstantEvaluatorError::ArrayLengthOverridden),
2291                        ArraySize::Dynamic => Err(ConstantEvaluatorError::ArrayLengthDynamic),
2292                    },
2293                    _ => Err(ConstantEvaluatorError::InvalidArrayLengthArg),
2294                }
2295            }
2296            _ => Err(ConstantEvaluatorError::InvalidArrayLengthArg),
2297        }
2298    }
2299
2300    fn access(
2301        &mut self,
2302        base: Handle<Expression>,
2303        index: usize,
2304        span: Span,
2305    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
2306        match self.expressions[base] {
2307            Expression::ZeroValue(ty) => {
2308                let ty_inner = &self.types[ty].inner;
2309                let components = ty_inner
2310                    .components()
2311                    .ok_or(ConstantEvaluatorError::InvalidAccessBase)?;
2312
2313                if index >= components as usize {
2314                    Err(ConstantEvaluatorError::InvalidAccessBase)
2315                } else {
2316                    let ty_res = ty_inner
2317                        .component_type(index)
2318                        .ok_or(ConstantEvaluatorError::InvalidAccessIndex)?;
2319                    let ty = match ty_res {
2320                        crate::proc::TypeResolution::Handle(ty) => ty,
2321                        crate::proc::TypeResolution::Value(inner) => {
2322                            self.types.insert(Type { name: None, inner }, span)
2323                        }
2324                    };
2325                    self.register_evaluated_expr(Expression::ZeroValue(ty), span)
2326                }
2327            }
2328            Expression::Splat { size, value } => {
2329                if index >= size as usize {
2330                    Err(ConstantEvaluatorError::InvalidAccessBase)
2331                } else {
2332                    Ok(value)
2333                }
2334            }
2335            Expression::Compose { ty, ref components } => {
2336                let _ = self.types[ty]
2337                    .inner
2338                    .components()
2339                    .ok_or(ConstantEvaluatorError::InvalidAccessBase)?;
2340
2341                crate::proc::flatten_compose(ty, components, self.expressions, self.types)
2342                    .nth(index)
2343                    .ok_or(ConstantEvaluatorError::InvalidAccessIndex)
2344            }
2345            _ => Err(ConstantEvaluatorError::InvalidAccessBase),
2346        }
2347    }
2348
2349    /// Lower [`ZeroValue`] and [`Splat`] expressions to [`Literal`] and [`Compose`] expressions.
2350    ///
2351    /// [`ZeroValue`]: Expression::ZeroValue
2352    /// [`Splat`]: Expression::Splat
2353    /// [`Literal`]: Expression::Literal
2354    /// [`Compose`]: Expression::Compose
2355    fn eval_zero_value_and_splat(
2356        &mut self,
2357        mut expr: Handle<Expression>,
2358        span: Span,
2359    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
2360        // If expr is a Compose expression, eliminate ZeroValue and Splat expressions for
2361        // each of its components.
2362        if let Expression::Compose { ty, ref components } = self.expressions[expr] {
2363            let components = components
2364                .clone()
2365                .iter()
2366                .map(|component| self.eval_zero_value_and_splat(*component, span))
2367                .collect::<Result<_, _>>()?;
2368            expr = self.register_evaluated_expr(Expression::Compose { ty, components }, span)?;
2369        }
2370
2371        // The result of the splat() for a Splat of a scalar ZeroValue is a
2372        // vector ZeroValue, so we must call eval_zero_value_impl() after
2373        // splat() in order to ensure we have no ZeroValues remaining.
2374        if let Expression::Splat { size, value } = self.expressions[expr] {
2375            expr = self.splat(value, size, span)?;
2376        }
2377        if let Expression::ZeroValue(ty) = self.expressions[expr] {
2378            expr = self.eval_zero_value_impl(ty, span)?;
2379        }
2380        Ok(expr)
2381    }
2382
2383    /// Lower [`ZeroValue`] expressions to [`Literal`] and [`Compose`] expressions.
2384    ///
2385    /// [`ZeroValue`]: Expression::ZeroValue
2386    /// [`Literal`]: Expression::Literal
2387    /// [`Compose`]: Expression::Compose
2388    fn eval_zero_value(
2389        &mut self,
2390        expr: Handle<Expression>,
2391        span: Span,
2392    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
2393        match self.expressions[expr] {
2394            Expression::ZeroValue(ty) => self.eval_zero_value_impl(ty, span),
2395            _ => Ok(expr),
2396        }
2397    }
2398
2399    /// Lower [`ZeroValue`] expressions to [`Literal`] and [`Compose`] expressions.
2400    ///
2401    /// [`ZeroValue`]: Expression::ZeroValue
2402    /// [`Literal`]: Expression::Literal
2403    /// [`Compose`]: Expression::Compose
2404    fn eval_zero_value_impl(
2405        &mut self,
2406        ty: Handle<Type>,
2407        span: Span,
2408    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
2409        match self.types[ty].inner {
2410            TypeInner::Scalar(scalar) => {
2411                let expr = Expression::Literal(
2412                    Literal::zero(scalar).ok_or(ConstantEvaluatorError::TypeNotConstructible)?,
2413                );
2414                self.register_evaluated_expr(expr, span)
2415            }
2416            TypeInner::Vector { size, scalar } => {
2417                let scalar_ty = self.types.insert(
2418                    Type {
2419                        name: None,
2420                        inner: TypeInner::Scalar(scalar),
2421                    },
2422                    span,
2423                );
2424                let el = self.eval_zero_value_impl(scalar_ty, span)?;
2425                let expr = Expression::Compose {
2426                    ty,
2427                    components: vec![el; size as usize],
2428                };
2429                self.register_evaluated_expr(expr, span)
2430            }
2431            TypeInner::Matrix {
2432                columns,
2433                rows,
2434                scalar,
2435            } => {
2436                let vec_ty = self.types.insert(
2437                    Type {
2438                        name: None,
2439                        inner: TypeInner::Vector { size: rows, scalar },
2440                    },
2441                    span,
2442                );
2443                let el = self.eval_zero_value_impl(vec_ty, span)?;
2444                let expr = Expression::Compose {
2445                    ty,
2446                    components: vec![el; columns as usize],
2447                };
2448                self.register_evaluated_expr(expr, span)
2449            }
2450            TypeInner::Array {
2451                base,
2452                size: ArraySize::Constant(size),
2453                ..
2454            } => {
2455                let el = self.eval_zero_value_impl(base, span)?;
2456                let expr = Expression::Compose {
2457                    ty,
2458                    components: vec![el; size.get() as usize],
2459                };
2460                self.register_evaluated_expr(expr, span)
2461            }
2462            TypeInner::Struct { ref members, .. } => {
2463                let types: Vec<_> = members.iter().map(|m| m.ty).collect();
2464                let mut components = Vec::with_capacity(members.len());
2465                for ty in types {
2466                    components.push(self.eval_zero_value_impl(ty, span)?);
2467                }
2468                let expr = Expression::Compose { ty, components };
2469                self.register_evaluated_expr(expr, span)
2470            }
2471            _ => Err(ConstantEvaluatorError::TypeNotConstructible),
2472        }
2473    }
2474
2475    /// Convert the scalar components of `expr` to `target`.
2476    ///
2477    /// Treat `span` as the location of the resulting expression.
2478    pub fn cast(
2479        &mut self,
2480        expr: Handle<Expression>,
2481        target: crate::Scalar,
2482        span: Span,
2483    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
2484        use crate::Scalar as Sc;
2485
2486        let expr = self.eval_zero_value(expr, span)?;
2487
2488        let make_error = || -> Result<_, ConstantEvaluatorError> {
2489            let from = format!("{:?} {:?}", expr, self.expressions[expr]);
2490
2491            #[cfg(feature = "wgsl-in")]
2492            let to = target.to_wgsl_for_diagnostics();
2493
2494            #[cfg(not(feature = "wgsl-in"))]
2495            let to = format!("{target:?}");
2496
2497            Err(ConstantEvaluatorError::InvalidCastArg { from, to })
2498        };
2499
2500        use crate::proc::type_methods::IntFloatLimits;
2501
2502        let expr = match self.expressions[expr] {
2503            Expression::Literal(literal) => {
2504                let literal = match target {
2505                    Sc::I16 => Literal::I16(match literal {
2506                        Literal::I16(v) => v,
2507                        Literal::U16(v) => v as i16,
2508                        Literal::I32(v) => v as i16,
2509                        Literal::U32(v) => v as i16,
2510                        Literal::F32(v) => v.clamp(i16::MIN as f32, i16::MAX as f32) as i16,
2511                        Literal::F16(v) => {
2512                            f16::to_f32(v).clamp(i16::MIN as f32, i16::MAX as f32) as i16
2513                        }
2514                        Literal::Bool(v) => v as i16,
2515                        Literal::F64(_) | Literal::I64(_) | Literal::U64(_) => {
2516                            return make_error();
2517                        }
2518                        Literal::AbstractInt(v) => v as i16,
2519                        Literal::AbstractFloat(v) => v as i16,
2520                    }),
2521                    Sc::U16 => Literal::U16(match literal {
2522                        Literal::I16(v) => v as u16,
2523                        Literal::U16(v) => v,
2524                        Literal::I32(v) => v as u16,
2525                        Literal::U32(v) => v as u16,
2526                        Literal::F32(v) => v.clamp(u16::MIN as f32, u16::MAX as f32) as u16,
2527                        Literal::F16(v) => f16::to_u16(&v.max(f16::ZERO)).unwrap(),
2528                        Literal::Bool(v) => v as u16,
2529                        Literal::F64(_) | Literal::I64(_) | Literal::U64(_) => {
2530                            return make_error();
2531                        }
2532                        Literal::AbstractInt(v) => v as u16,
2533                        Literal::AbstractFloat(v) => v as u16,
2534                    }),
2535                    Sc::I32 => Literal::I32(match literal {
2536                        Literal::I16(v) => v as i32,
2537                        Literal::U16(v) => v as i32,
2538                        Literal::I32(v) => v,
2539                        Literal::U32(v) => v as i32,
2540                        Literal::F32(v) => v.clamp(i32::min_float(), i32::max_float()) as i32,
2541                        Literal::F16(v) => f16::to_i32(&v).unwrap(), //Only None on NaN or Inf
2542                        Literal::Bool(v) => v as i32,
2543                        Literal::F64(_) | Literal::I64(_) | Literal::U64(_) => {
2544                            return make_error();
2545                        }
2546                        Literal::AbstractInt(v) => i32::try_from_abstract(v)?,
2547                        Literal::AbstractFloat(v) => i32::try_from_abstract(v)?,
2548                    }),
2549                    Sc::U32 => Literal::U32(match literal {
2550                        Literal::I16(v) => v as u32,
2551                        Literal::U16(v) => v as u32,
2552                        Literal::I32(v) => v as u32,
2553                        Literal::U32(v) => v,
2554                        Literal::F32(v) => v.clamp(u32::min_float(), u32::max_float()) as u32,
2555                        // max(0) avoids None due to negative, therefore only None on NaN or Inf
2556                        Literal::F16(v) => f16::to_u32(&v.max(f16::ZERO)).unwrap(),
2557                        Literal::Bool(v) => v as u32,
2558                        Literal::F64(_) | Literal::I64(_) | Literal::U64(_) => {
2559                            return make_error();
2560                        }
2561                        Literal::AbstractInt(v) => u32::try_from_abstract(v)?,
2562                        Literal::AbstractFloat(v) => u32::try_from_abstract(v)?,
2563                    }),
2564                    Sc::I64 => Literal::I64(match literal {
2565                        Literal::I16(v) => v as i64,
2566                        Literal::U16(v) => v as i64,
2567                        Literal::I32(v) => v as i64,
2568                        Literal::U32(v) => v as i64,
2569                        Literal::F32(v) => v.clamp(i64::min_float(), i64::max_float()) as i64,
2570                        Literal::Bool(v) => v as i64,
2571                        Literal::F64(v) => v.clamp(i64::min_float(), i64::max_float()) as i64,
2572                        Literal::I64(v) => v,
2573                        Literal::U64(v) => v as i64,
2574                        Literal::F16(v) => f16::to_i64(&v).unwrap(), //Only None on NaN or Inf
2575                        Literal::AbstractInt(v) => i64::try_from_abstract(v)?,
2576                        Literal::AbstractFloat(v) => i64::try_from_abstract(v)?,
2577                    }),
2578                    Sc::U64 => Literal::U64(match literal {
2579                        Literal::I16(v) => v as u64,
2580                        Literal::U16(v) => v as u64,
2581                        Literal::I32(v) => v as u64,
2582                        Literal::U32(v) => v as u64,
2583                        Literal::F32(v) => v.clamp(u64::min_float(), u64::max_float()) as u64,
2584                        Literal::Bool(v) => v as u64,
2585                        Literal::F64(v) => v.clamp(u64::min_float(), u64::max_float()) as u64,
2586                        Literal::I64(v) => v as u64,
2587                        Literal::U64(v) => v,
2588                        // max(0) avoids None due to negative, therefore only None on NaN or Inf
2589                        Literal::F16(v) => f16::to_u64(&v.max(f16::ZERO)).unwrap(),
2590                        Literal::AbstractInt(v) => u64::try_from_abstract(v)?,
2591                        Literal::AbstractFloat(v) => u64::try_from_abstract(v)?,
2592                    }),
2593                    Sc::F16 => Literal::F16(match literal {
2594                        Literal::F16(v) => v,
2595                        Literal::F32(v) => f16::from_f32(v),
2596                        Literal::F64(v) => f16::from_f64(v),
2597                        Literal::Bool(v) => f16::from_u32(v as u32).unwrap(),
2598                        Literal::I16(v) => f16::from_f32(v as f32),
2599                        Literal::U16(v) => f16::from_f32(v as f32),
2600                        Literal::I64(v) => f16::from_i64(v).unwrap(),
2601                        Literal::U64(v) => f16::from_u64(v).unwrap(),
2602                        Literal::I32(v) => f16::from_i32(v).unwrap(),
2603                        Literal::U32(v) => f16::from_u32(v).unwrap(),
2604                        Literal::AbstractFloat(v) => f16::try_from_abstract(v)?,
2605                        Literal::AbstractInt(v) => f16::try_from_abstract(v)?,
2606                    }),
2607                    Sc::F32 => Literal::F32(match literal {
2608                        Literal::I16(v) => v as f32,
2609                        Literal::U16(v) => v as f32,
2610                        Literal::I32(v) => v as f32,
2611                        Literal::U32(v) => v as f32,
2612                        Literal::F32(v) => v,
2613                        Literal::Bool(v) => v as u32 as f32,
2614                        Literal::F64(_) | Literal::I64(_) | Literal::U64(_) => {
2615                            return make_error();
2616                        }
2617                        Literal::F16(v) => f16::to_f32(v),
2618                        Literal::AbstractInt(v) => f32::try_from_abstract(v)?,
2619                        Literal::AbstractFloat(v) => f32::try_from_abstract(v)?,
2620                    }),
2621                    Sc::F64 => Literal::F64(match literal {
2622                        Literal::I16(v) => v as f64,
2623                        Literal::U16(v) => v as f64,
2624                        Literal::I32(v) => v as f64,
2625                        Literal::U32(v) => v as f64,
2626                        Literal::F16(v) => f16::to_f64(v),
2627                        Literal::F32(v) => v as f64,
2628                        Literal::F64(v) => v,
2629                        Literal::Bool(v) => v as u32 as f64,
2630                        Literal::I64(_) | Literal::U64(_) => return make_error(),
2631                        Literal::AbstractInt(v) => f64::try_from_abstract(v)?,
2632                        Literal::AbstractFloat(v) => f64::try_from_abstract(v)?,
2633                    }),
2634                    Sc::BOOL => Literal::Bool(match literal {
2635                        Literal::I16(v) => v != 0,
2636                        Literal::U16(v) => v != 0,
2637                        Literal::I32(v) => v != 0,
2638                        Literal::U32(v) => v != 0,
2639                        Literal::F32(v) => v != 0.0,
2640                        Literal::F16(v) => v != f16::zero(),
2641                        Literal::Bool(v) => v,
2642                        Literal::AbstractInt(v) => v != 0,
2643                        Literal::AbstractFloat(v) => v != 0.0,
2644                        Literal::F64(_) | Literal::I64(_) | Literal::U64(_) => {
2645                            return make_error();
2646                        }
2647                    }),
2648                    Sc::ABSTRACT_FLOAT => Literal::AbstractFloat(match literal {
2649                        Literal::AbstractInt(v) => {
2650                            // Overflow is forbidden, but inexact conversions
2651                            // are fine. The range of f64 is far larger than
2652                            // that of i64, so we don't have to check anything
2653                            // here.
2654                            v as f64
2655                        }
2656                        Literal::AbstractFloat(v) => v,
2657                        _ => return make_error(),
2658                    }),
2659                    Sc::ABSTRACT_INT => Literal::AbstractInt(match literal {
2660                        Literal::AbstractInt(v) => v,
2661                        _ => return make_error(),
2662                    }),
2663                    _ => {
2664                        log::debug!("Constant evaluator refused to convert value to {target:?}");
2665                        return make_error();
2666                    }
2667                };
2668                Expression::Literal(literal)
2669            }
2670            Expression::Compose {
2671                ty,
2672                components: ref src_components,
2673            } => {
2674                let ty_inner = match self.types[ty].inner {
2675                    TypeInner::Vector { size, .. } => TypeInner::Vector {
2676                        size,
2677                        scalar: target,
2678                    },
2679                    TypeInner::Matrix { columns, rows, .. } => TypeInner::Matrix {
2680                        columns,
2681                        rows,
2682                        scalar: target,
2683                    },
2684                    _ => return make_error(),
2685                };
2686
2687                let mut components = src_components.clone();
2688                for component in &mut components {
2689                    *component = self.cast(*component, target, span)?;
2690                }
2691
2692                let ty = self.types.insert(
2693                    Type {
2694                        name: None,
2695                        inner: ty_inner,
2696                    },
2697                    span,
2698                );
2699
2700                Expression::Compose { ty, components }
2701            }
2702            Expression::Splat { size, value } => {
2703                let value_span = self.expressions.get_span(value);
2704                let cast_value = self.cast(value, target, value_span)?;
2705                Expression::Splat {
2706                    size,
2707                    value: cast_value,
2708                }
2709            }
2710            _ => return make_error(),
2711        };
2712
2713        self.register_evaluated_expr(expr, span)
2714    }
2715
2716    /// Convert the scalar leaves of  `expr` to `target`, handling arrays.
2717    ///
2718    /// `expr` must be a `Compose` expression whose type is a scalar, vector,
2719    /// matrix, or nested arrays of such.
2720    ///
2721    /// This is basically the same as the [`cast`] method, except that that
2722    /// should only handle Naga [`As`] expressions, which cannot convert arrays.
2723    ///
2724    /// Treat `span` as the location of the resulting expression.
2725    ///
2726    /// [`cast`]: ConstantEvaluator::cast
2727    /// [`As`]: crate::Expression::As
2728    pub fn cast_array(
2729        &mut self,
2730        expr: Handle<Expression>,
2731        target: crate::Scalar,
2732        span: Span,
2733    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
2734        let expr = self.check_and_get(expr)?;
2735
2736        let Expression::Compose { ty, ref components } = self.expressions[expr] else {
2737            return self.cast(expr, target, span);
2738        };
2739
2740        let TypeInner::Array {
2741            base: _,
2742            size,
2743            stride: _,
2744        } = self.types[ty].inner
2745        else {
2746            return self.cast(expr, target, span);
2747        };
2748
2749        let mut components = components.clone();
2750        for component in &mut components {
2751            *component = self.cast_array(*component, target, span)?;
2752        }
2753
2754        let first = components.first().unwrap();
2755        let new_base = match self.resolve_type(*first)? {
2756            crate::proc::TypeResolution::Handle(ty) => ty,
2757            crate::proc::TypeResolution::Value(inner) => {
2758                self.types.insert(Type { name: None, inner }, span)
2759            }
2760        };
2761        let mut layouter = core::mem::take(self.layouter);
2762        layouter.update(self.to_ctx()).map_err(|err| {
2763            // The layouter operates lazily, so the error
2764            // could be for any pending type.
2765            let crate::proc::LayoutErrorInner::TooLarge = err.inner else {
2766                unreachable!("unexpected layout error: {err:?}");
2767            };
2768            ConstantEvaluatorError::TypeTooLarge(err.ty)
2769        })?;
2770        *self.layouter = layouter;
2771
2772        let new_base_stride = self.layouter[new_base].to_stride();
2773        let new_array_ty = self.types.insert(
2774            Type {
2775                name: None,
2776                inner: TypeInner::Array {
2777                    base: new_base,
2778                    size,
2779                    stride: new_base_stride,
2780                },
2781            },
2782            span,
2783        );
2784
2785        let compose = Expression::Compose {
2786            ty: new_array_ty,
2787            components,
2788        };
2789        self.register_evaluated_expr(compose, span)
2790    }
2791
2792    fn unary_op(
2793        &mut self,
2794        op: UnaryOperator,
2795        expr: Handle<Expression>,
2796        span: Span,
2797    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
2798        let expr = self.eval_zero_value_and_splat(expr, span)?;
2799
2800        let expr = match self.expressions[expr] {
2801            Expression::Literal(value) => Expression::Literal(match op {
2802                UnaryOperator::Negate => match value {
2803                    Literal::I16(v) => Literal::I16(v.wrapping_neg()),
2804                    Literal::I32(v) => Literal::I32(v.wrapping_neg()),
2805                    Literal::I64(v) => Literal::I64(v.wrapping_neg()),
2806                    Literal::F32(v) => Literal::F32(-v),
2807                    Literal::F16(v) => Literal::F16(-v),
2808                    Literal::F64(v) => Literal::F64(-v),
2809                    Literal::AbstractInt(v) => Literal::AbstractInt(v.wrapping_neg()),
2810                    Literal::AbstractFloat(v) => Literal::AbstractFloat(-v),
2811                    _ => return Err(ConstantEvaluatorError::InvalidUnaryOpArg),
2812                },
2813                UnaryOperator::LogicalNot => match value {
2814                    Literal::Bool(v) => Literal::Bool(!v),
2815                    _ => return Err(ConstantEvaluatorError::InvalidUnaryOpArg),
2816                },
2817                UnaryOperator::BitwiseNot => match value {
2818                    Literal::I16(v) => Literal::I16(!v),
2819                    Literal::I32(v) => Literal::I32(!v),
2820                    Literal::I64(v) => Literal::I64(!v),
2821                    Literal::U16(v) => Literal::U16(!v),
2822                    Literal::U32(v) => Literal::U32(!v),
2823                    Literal::U64(v) => Literal::U64(!v),
2824                    Literal::AbstractInt(v) => Literal::AbstractInt(!v),
2825                    _ => return Err(ConstantEvaluatorError::InvalidUnaryOpArg),
2826                },
2827            }),
2828            Expression::Compose {
2829                ty,
2830                components: ref src_components,
2831            } => {
2832                match self.types[ty].inner {
2833                    TypeInner::Vector { .. } => (),
2834                    _ => return Err(ConstantEvaluatorError::InvalidUnaryOpArg),
2835                }
2836
2837                let mut components = src_components.clone();
2838                for component in &mut components {
2839                    *component = self.unary_op(op, *component, span)?;
2840                }
2841
2842                Expression::Compose { ty, components }
2843            }
2844            _ => return Err(ConstantEvaluatorError::InvalidUnaryOpArg),
2845        };
2846
2847        self.register_evaluated_expr(expr, span)
2848    }
2849
2850    fn binary_op(
2851        &mut self,
2852        op: BinaryOperator,
2853        left: Handle<Expression>,
2854        right: Handle<Expression>,
2855        span: Span,
2856    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
2857        let left = self.eval_zero_value_and_splat(left, span)?;
2858        let right = self.eval_zero_value_and_splat(right, span)?;
2859
2860        // Note: in most cases constant evaluation checks for overflow, but for
2861        // i32/u32, it uses wrapping arithmetic. See
2862        // <https://gpuweb.github.io/gpuweb/wgsl/#integer-types>.
2863
2864        let expr = match (&self.expressions[left], &self.expressions[right]) {
2865            (&Expression::Literal(left_value), &Expression::Literal(right_value)) => {
2866                if !matches!(op, BinaryOperator::ShiftLeft | BinaryOperator::ShiftRight)
2867                    && core::mem::discriminant(&left_value) != core::mem::discriminant(&right_value)
2868                {
2869                    return Err(ConstantEvaluatorError::InvalidBinaryOpArgs);
2870                }
2871
2872                if matches!(
2873                    (left_value, op),
2874                    (
2875                        Literal::Bool(_),
2876                        BinaryOperator::Less
2877                            | BinaryOperator::LessEqual
2878                            | BinaryOperator::Greater
2879                            | BinaryOperator::GreaterEqual
2880                    )
2881                ) {
2882                    return Err(ConstantEvaluatorError::InvalidBinaryOpArgs);
2883                }
2884
2885                let literal = match op {
2886                    BinaryOperator::Equal => Literal::Bool(left_value == right_value),
2887                    BinaryOperator::NotEqual => Literal::Bool(left_value != right_value),
2888                    BinaryOperator::Less => Literal::Bool(left_value < right_value),
2889                    BinaryOperator::LessEqual => Literal::Bool(left_value <= right_value),
2890                    BinaryOperator::Greater => Literal::Bool(left_value > right_value),
2891                    BinaryOperator::GreaterEqual => Literal::Bool(left_value >= right_value),
2892
2893                    _ => match (left_value, right_value) {
2894                        (Literal::I16(a), Literal::I16(b)) => Literal::I16(match op {
2895                            BinaryOperator::Add => a.wrapping_add(b),
2896                            BinaryOperator::Subtract => a.wrapping_sub(b),
2897                            BinaryOperator::Multiply => a.wrapping_mul(b),
2898                            BinaryOperator::Divide => a.checked_div(b).ok_or_else(|| {
2899                                if b == 0 {
2900                                    ConstantEvaluatorError::DivisionByZero
2901                                } else {
2902                                    ConstantEvaluatorError::Overflow("division".into())
2903                                }
2904                            })?,
2905                            BinaryOperator::Modulo => a.checked_rem(b).ok_or_else(|| {
2906                                if b == 0 {
2907                                    ConstantEvaluatorError::RemainderByZero
2908                                } else {
2909                                    ConstantEvaluatorError::Overflow("remainder".into())
2910                                }
2911                            })?,
2912                            BinaryOperator::And => a & b,
2913                            BinaryOperator::ExclusiveOr => a ^ b,
2914                            BinaryOperator::InclusiveOr => a | b,
2915                            _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
2916                        }),
2917                        (Literal::I16(a), Literal::U32(b)) => Literal::I16(match op {
2918                            BinaryOperator::ShiftLeft => {
2919                                if (if a.is_negative() { !a } else { a }).leading_zeros() <= b {
2920                                    return Err(ConstantEvaluatorError::Overflow("<<".to_string()));
2921                                }
2922                                a.checked_shl(b)
2923                                    .ok_or(ConstantEvaluatorError::ShiftedMoreThan32Bits)?
2924                            }
2925                            BinaryOperator::ShiftRight => a
2926                                .checked_shr(b)
2927                                .ok_or(ConstantEvaluatorError::ShiftedMoreThan32Bits)?,
2928                            _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
2929                        }),
2930                        (Literal::U16(a), Literal::U16(b)) => Literal::U16(match op {
2931                            BinaryOperator::Add => a.wrapping_add(b),
2932                            BinaryOperator::Subtract => a.wrapping_sub(b),
2933                            BinaryOperator::Multiply => a.wrapping_mul(b),
2934                            BinaryOperator::Divide => a
2935                                .checked_div(b)
2936                                .ok_or(ConstantEvaluatorError::DivisionByZero)?,
2937                            BinaryOperator::Modulo => a
2938                                .checked_rem(b)
2939                                .ok_or(ConstantEvaluatorError::RemainderByZero)?,
2940                            BinaryOperator::And => a & b,
2941                            BinaryOperator::ExclusiveOr => a ^ b,
2942                            BinaryOperator::InclusiveOr => a | b,
2943                            _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
2944                        }),
2945                        (Literal::U16(a), Literal::U32(b)) => Literal::U16(match op {
2946                            BinaryOperator::ShiftLeft => a
2947                                .checked_mul(
2948                                    1u16.checked_shl(b)
2949                                        .ok_or(ConstantEvaluatorError::ShiftedMoreThan32Bits)?,
2950                                )
2951                                .ok_or(ConstantEvaluatorError::Overflow("<<".to_string()))?,
2952                            BinaryOperator::ShiftRight => a
2953                                .checked_shr(b)
2954                                .ok_or(ConstantEvaluatorError::ShiftedMoreThan32Bits)?,
2955                            _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
2956                        }),
2957                        (Literal::I32(a), Literal::I32(b)) => Literal::I32(match op {
2958                            BinaryOperator::Add => a.wrapping_add(b),
2959                            BinaryOperator::Subtract => a.wrapping_sub(b),
2960                            BinaryOperator::Multiply => a.wrapping_mul(b),
2961                            BinaryOperator::Divide => a.checked_div(b).ok_or_else(|| {
2962                                if b == 0 {
2963                                    ConstantEvaluatorError::DivisionByZero
2964                                } else {
2965                                    ConstantEvaluatorError::Overflow("division".into())
2966                                }
2967                            })?,
2968                            BinaryOperator::Modulo => a.checked_rem(b).ok_or_else(|| {
2969                                if b == 0 {
2970                                    ConstantEvaluatorError::RemainderByZero
2971                                } else {
2972                                    ConstantEvaluatorError::Overflow("remainder".into())
2973                                }
2974                            })?,
2975                            BinaryOperator::And => a & b,
2976                            BinaryOperator::ExclusiveOr => a ^ b,
2977                            BinaryOperator::InclusiveOr => a | b,
2978                            _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
2979                        }),
2980                        (Literal::I32(a), Literal::U32(b)) => Literal::I32(match op {
2981                            BinaryOperator::ShiftLeft => {
2982                                if (if a.is_negative() { !a } else { a }).leading_zeros() <= b {
2983                                    return Err(ConstantEvaluatorError::Overflow("<<".to_string()));
2984                                }
2985                                a.checked_shl(b)
2986                                    .ok_or(ConstantEvaluatorError::ShiftedMoreThan32Bits)?
2987                            }
2988                            BinaryOperator::ShiftRight => a
2989                                .checked_shr(b)
2990                                .ok_or(ConstantEvaluatorError::ShiftedMoreThan32Bits)?,
2991                            _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
2992                        }),
2993                        (Literal::U32(a), Literal::U32(b)) => Literal::U32(match op {
2994                            BinaryOperator::Add => a.wrapping_add(b),
2995                            BinaryOperator::Subtract => a.wrapping_sub(b),
2996                            BinaryOperator::Multiply => a.wrapping_mul(b),
2997                            BinaryOperator::Divide => a
2998                                .checked_div(b)
2999                                .ok_or(ConstantEvaluatorError::DivisionByZero)?,
3000                            BinaryOperator::Modulo => a
3001                                .checked_rem(b)
3002                                .ok_or(ConstantEvaluatorError::RemainderByZero)?,
3003                            BinaryOperator::And => a & b,
3004                            BinaryOperator::ExclusiveOr => a ^ b,
3005                            BinaryOperator::InclusiveOr => a | b,
3006                            BinaryOperator::ShiftLeft => a
3007                                .checked_mul(
3008                                    1u32.checked_shl(b)
3009                                        .ok_or(ConstantEvaluatorError::ShiftedMoreThan32Bits)?,
3010                                )
3011                                .ok_or(ConstantEvaluatorError::Overflow("<<".to_string()))?,
3012                            BinaryOperator::ShiftRight => a
3013                                .checked_shr(b)
3014                                .ok_or(ConstantEvaluatorError::ShiftedMoreThan32Bits)?,
3015                            _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
3016                        }),
3017                        (Literal::F32(a), Literal::F32(b)) => Literal::F32(match op {
3018                            BinaryOperator::Add => a + b,
3019                            BinaryOperator::Subtract => a - b,
3020                            BinaryOperator::Multiply => a * b,
3021                            BinaryOperator::Divide => a / b,
3022                            BinaryOperator::Modulo => a % b,
3023                            _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
3024                        }),
3025                        (Literal::AbstractInt(a), Literal::U32(b)) => {
3026                            Literal::AbstractInt(match op {
3027                                BinaryOperator::ShiftLeft => {
3028                                    if (if a.is_negative() { !a } else { a }).leading_zeros() <= b {
3029                                        return Err(ConstantEvaluatorError::Overflow(
3030                                            "<<".to_string(),
3031                                        ));
3032                                    }
3033                                    a.checked_shl(b).unwrap_or(0)
3034                                }
3035                                BinaryOperator::ShiftRight => a.checked_shr(b).unwrap_or(0),
3036                                _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
3037                            })
3038                        }
3039                        (Literal::F16(a), Literal::F16(b)) => {
3040                            let result = match op {
3041                                BinaryOperator::Add => a + b,
3042                                BinaryOperator::Subtract => a - b,
3043                                BinaryOperator::Multiply => a * b,
3044                                BinaryOperator::Divide => a / b,
3045                                BinaryOperator::Modulo => a % b,
3046                                _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
3047                            };
3048                            if !result.is_finite() {
3049                                return Err(ConstantEvaluatorError::Overflow(format!("{op:?}")));
3050                            }
3051                            Literal::F16(result)
3052                        }
3053                        (Literal::AbstractInt(a), Literal::AbstractInt(b)) => {
3054                            Literal::AbstractInt(match op {
3055                                BinaryOperator::Add => a.checked_add(b).ok_or_else(|| {
3056                                    ConstantEvaluatorError::Overflow("addition".into())
3057                                })?,
3058                                BinaryOperator::Subtract => a.checked_sub(b).ok_or_else(|| {
3059                                    ConstantEvaluatorError::Overflow("subtraction".into())
3060                                })?,
3061                                BinaryOperator::Multiply => a.checked_mul(b).ok_or_else(|| {
3062                                    ConstantEvaluatorError::Overflow("multiplication".into())
3063                                })?,
3064                                BinaryOperator::Divide => a.checked_div(b).ok_or_else(|| {
3065                                    if b == 0 {
3066                                        ConstantEvaluatorError::DivisionByZero
3067                                    } else {
3068                                        ConstantEvaluatorError::Overflow("division".into())
3069                                    }
3070                                })?,
3071                                BinaryOperator::Modulo => a.checked_rem(b).ok_or_else(|| {
3072                                    if b == 0 {
3073                                        ConstantEvaluatorError::RemainderByZero
3074                                    } else {
3075                                        ConstantEvaluatorError::Overflow("remainder".into())
3076                                    }
3077                                })?,
3078                                BinaryOperator::And => a & b,
3079                                BinaryOperator::ExclusiveOr => a ^ b,
3080                                BinaryOperator::InclusiveOr => a | b,
3081                                _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
3082                            })
3083                        }
3084                        (Literal::AbstractFloat(a), Literal::AbstractFloat(b)) => {
3085                            let result = match op {
3086                                BinaryOperator::Add => a + b,
3087                                BinaryOperator::Subtract => a - b,
3088                                BinaryOperator::Multiply => a * b,
3089                                BinaryOperator::Divide => a / b,
3090                                BinaryOperator::Modulo => a % b,
3091                                _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
3092                            };
3093                            if !result.is_finite() {
3094                                return Err(ConstantEvaluatorError::Overflow(format!("{op:?}")));
3095                            }
3096                            Literal::AbstractFloat(result)
3097                        }
3098                        (Literal::Bool(a), Literal::Bool(b)) => Literal::Bool(match op {
3099                            BinaryOperator::LogicalAnd => a && b,
3100                            BinaryOperator::LogicalOr => a || b,
3101                            BinaryOperator::And => a & b,
3102                            BinaryOperator::InclusiveOr => a | b,
3103                            _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
3104                        }),
3105                        _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
3106                    },
3107                };
3108                Expression::Literal(literal)
3109            }
3110            (
3111                &Expression::Compose {
3112                    components: ref src_components,
3113                    ty,
3114                },
3115                &Expression::Literal(_),
3116            ) => {
3117                if !is_allowed_compose_literal_op(&self.types[ty].inner, op) {
3118                    return Err(ConstantEvaluatorError::InvalidBinaryOpArgs);
3119                }
3120                let mut components = src_components.clone();
3121                for component in &mut components {
3122                    *component = self.binary_op(op, *component, right, span)?;
3123                }
3124                Expression::Compose { ty, components }
3125            }
3126            (
3127                &Expression::Literal(_),
3128                &Expression::Compose {
3129                    components: ref src_components,
3130                    ty,
3131                },
3132            ) => {
3133                if !is_allowed_compose_literal_op(&self.types[ty].inner, op) {
3134                    return Err(ConstantEvaluatorError::InvalidBinaryOpArgs);
3135                }
3136                let mut components = src_components.clone();
3137                for component in &mut components {
3138                    *component = self.binary_op(op, left, *component, span)?;
3139                }
3140                Expression::Compose { ty, components }
3141            }
3142            (
3143                &Expression::Compose {
3144                    components: ref left_components,
3145                    ty: left_ty,
3146                },
3147                &Expression::Compose {
3148                    components: ref right_components,
3149                    ty: right_ty,
3150                },
3151            ) => {
3152                // We have to make a copy of the component lists, because the
3153                // call to `binary_op_vector` needs `&mut self`, but `self` owns
3154                // the component lists.
3155                let left_flattened = crate::proc::flatten_compose(
3156                    left_ty,
3157                    left_components,
3158                    self.expressions,
3159                    self.types,
3160                )
3161                .collect::<Vec<_>>();
3162                let right_flattened = crate::proc::flatten_compose(
3163                    right_ty,
3164                    right_components,
3165                    self.expressions,
3166                    self.types,
3167                )
3168                .collect::<Vec<_>>();
3169
3170                self.binary_op_compose(
3171                    op,
3172                    &left_flattened,
3173                    &right_flattened,
3174                    left_ty,
3175                    right_ty,
3176                    span,
3177                )?
3178            }
3179            _ => return Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
3180        };
3181
3182        return self.register_evaluated_expr(expr, span);
3183
3184        fn is_allowed_compose_literal_op(compose_ty: &TypeInner, op: BinaryOperator) -> bool {
3185            let is_numeric_vec = matches!(
3186                compose_ty, TypeInner::Vector { scalar, .. }
3187                if scalar.kind != ScalarKind::Bool
3188            );
3189            let is_allowed_vec_scalar_op = matches!(
3190                op,
3191                BinaryOperator::Add
3192                    | BinaryOperator::Subtract
3193                    | BinaryOperator::Multiply
3194                    | BinaryOperator::Divide
3195                    | BinaryOperator::Modulo
3196            );
3197            let is_mat = matches!(compose_ty, TypeInner::Matrix { .. });
3198            let is_allowed_mat_scalar_op = matches!(op, BinaryOperator::Multiply);
3199            is_numeric_vec && is_allowed_vec_scalar_op || is_mat && is_allowed_mat_scalar_op
3200        }
3201    }
3202
3203    fn binary_op_compose(
3204        &mut self,
3205        op: BinaryOperator,
3206        left_components: &[Handle<Expression>],
3207        right_components: &[Handle<Expression>],
3208        left_ty: Handle<Type>,
3209        right_ty: Handle<Type>,
3210        span: Span,
3211    ) -> Result<Expression, ConstantEvaluatorError> {
3212        match (&self.types[left_ty].inner, &self.types[right_ty].inner) {
3213            // Binary operation on vector-vector
3214            (
3215                &TypeInner::Vector {
3216                    size: left_size, ..
3217                },
3218                &TypeInner::Vector {
3219                    size: right_size, ..
3220                },
3221            ) if left_size == right_size => self.binary_op_vector(
3222                op,
3223                left_size,
3224                left_components,
3225                right_components,
3226                left_ty,
3227                span,
3228            ),
3229            // Binary operation on vector-matrix
3230            (
3231                &TypeInner::Vector { size, .. },
3232                &TypeInner::Matrix {
3233                    columns,
3234                    rows,
3235                    scalar,
3236                },
3237            ) if op == BinaryOperator::Multiply && size == rows => self.multiply_vector_matrix(
3238                left_components,
3239                right_components,
3240                columns,
3241                scalar,
3242                span,
3243            ),
3244            // Binary operation on matrix-vector
3245            (
3246                &TypeInner::Matrix {
3247                    columns,
3248                    rows,
3249                    scalar,
3250                },
3251                &TypeInner::Vector { size, .. },
3252            ) if op == BinaryOperator::Multiply && size == columns => {
3253                self.multiply_matrix_vector(left_components, right_components, rows, scalar, span)
3254            }
3255            // Binary operation on matrix-matrix
3256            (
3257                &TypeInner::Matrix {
3258                    columns: left_columns,
3259                    rows: left_rows,
3260                    scalar,
3261                },
3262                &TypeInner::Matrix {
3263                    columns: right_columns,
3264                    rows: right_rows,
3265                    ..
3266                },
3267            ) => match op {
3268                BinaryOperator::Add | BinaryOperator::Subtract
3269                    if left_columns == right_columns && left_rows == right_rows =>
3270                {
3271                    let components = left_components
3272                        .iter()
3273                        .zip(right_components)
3274                        .map(|(&left, &right)| self.binary_op(op, left, right, span))
3275                        .collect::<Result<Vec<_>, _>>()?;
3276                    Ok(Expression::Compose {
3277                        ty: left_ty,
3278                        components,
3279                    })
3280                }
3281                BinaryOperator::Multiply if left_columns == right_rows => self
3282                    .multiply_matrix_matrix(
3283                        left_components,
3284                        right_components,
3285                        left_rows,
3286                        right_columns,
3287                        scalar,
3288                        span,
3289                    ),
3290                _ => Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
3291            },
3292            _ => Err(ConstantEvaluatorError::InvalidBinaryOpArgs),
3293        }
3294    }
3295
3296    fn binary_op_vector(
3297        &mut self,
3298        op: BinaryOperator,
3299        size: crate::VectorSize,
3300        left_components: &[Handle<Expression>],
3301        right_components: &[Handle<Expression>],
3302        left_ty: Handle<Type>,
3303        span: Span,
3304    ) -> Result<Expression, ConstantEvaluatorError> {
3305        let ty = match op {
3306            // Relational operators produce vectors of booleans.
3307            BinaryOperator::Equal
3308            | BinaryOperator::NotEqual
3309            | BinaryOperator::Less
3310            | BinaryOperator::LessEqual
3311            | BinaryOperator::Greater
3312            | BinaryOperator::GreaterEqual => self.types.insert(
3313                Type {
3314                    name: None,
3315                    inner: TypeInner::Vector {
3316                        size,
3317                        scalar: crate::Scalar::BOOL,
3318                    },
3319                },
3320                span,
3321            ),
3322
3323            // Other operators produce the same type as their left
3324            // operand.
3325            BinaryOperator::Add
3326            | BinaryOperator::Subtract
3327            | BinaryOperator::Multiply
3328            | BinaryOperator::Divide
3329            | BinaryOperator::Modulo
3330            | BinaryOperator::And
3331            | BinaryOperator::ExclusiveOr
3332            | BinaryOperator::InclusiveOr
3333            | BinaryOperator::ShiftLeft
3334            | BinaryOperator::ShiftRight => left_ty,
3335
3336            BinaryOperator::LogicalAnd | BinaryOperator::LogicalOr => {
3337                // Not supported on vectors
3338                return Err(ConstantEvaluatorError::InvalidBinaryOpArgs);
3339            }
3340        };
3341
3342        let components = left_components
3343            .iter()
3344            .zip(right_components)
3345            .map(|(&left, &right)| self.binary_op(op, left, right, span))
3346            .collect::<Result<Vec<_>, _>>()?;
3347
3348        Ok(Expression::Compose { ty, components })
3349    }
3350
3351    fn multiply_vector_matrix(
3352        &mut self,
3353        vec_components: &[Handle<Expression>],
3354        mat_components: &[Handle<Expression>],
3355        mat_columns: crate::VectorSize,
3356        scalar: crate::Scalar,
3357        span: Span,
3358    ) -> Result<Expression, ConstantEvaluatorError> {
3359        let ty = self.types.insert(
3360            Type {
3361                name: None,
3362                inner: TypeInner::Vector {
3363                    size: mat_columns,
3364                    scalar,
3365                },
3366            },
3367            span,
3368        );
3369        let components = mat_components
3370            .iter()
3371            .map(|&column| {
3372                let Expression::Compose { ref components, .. } = self.expressions[column] else {
3373                    unreachable!()
3374                };
3375                self.dot_exprs(
3376                    vec_components.iter().cloned(),
3377                    components.clone().into_iter(),
3378                    span,
3379                )
3380            })
3381            .collect::<Result<Vec<_>, _>>()?;
3382        Ok(Expression::Compose { ty, components })
3383    }
3384
3385    fn multiply_matrix_vector(
3386        &mut self,
3387        mat_components: &[Handle<Expression>],
3388        vec_components: &[Handle<Expression>],
3389        mat_rows: crate::VectorSize,
3390        scalar: crate::Scalar,
3391        span: Span,
3392    ) -> Result<Expression, ConstantEvaluatorError> {
3393        let ty = self.types.insert(
3394            Type {
3395                name: None,
3396                inner: TypeInner::Vector {
3397                    size: mat_rows,
3398                    scalar,
3399                },
3400            },
3401            span,
3402        );
3403
3404        let flatten = self.flatten_matrix(mat_components);
3405        let nr = mat_rows as usize;
3406        let components = (0..nr)
3407            .map(|r| {
3408                let row = flatten.iter().skip(r).step_by(nr).cloned();
3409                self.dot_exprs(row, vec_components.iter().cloned(), span)
3410            })
3411            .collect::<Result<Vec<_>, _>>()?;
3412        Ok(Expression::Compose { ty, components })
3413    }
3414
3415    fn multiply_matrix_matrix(
3416        &mut self,
3417        left_components: &[Handle<Expression>],
3418        right_components: &[Handle<Expression>],
3419        left_rows: crate::VectorSize,
3420        right_columns: crate::VectorSize,
3421        scalar: crate::Scalar,
3422        span: Span,
3423    ) -> Result<Expression, ConstantEvaluatorError> {
3424        let left_nc = left_components.len();
3425        let left_nr = left_rows as usize;
3426        let right_nc = right_columns as usize;
3427        let right_nr = left_nc;
3428
3429        let mut result = Vec::with_capacity(right_nc);
3430        let result_ty = self.types.insert(
3431            Type {
3432                name: None,
3433                inner: TypeInner::Matrix {
3434                    columns: right_columns,
3435                    rows: left_rows,
3436                    scalar,
3437                },
3438            },
3439            span,
3440        );
3441        let result_column_ty = self.types.insert(
3442            Type {
3443                name: None,
3444                inner: TypeInner::Vector {
3445                    size: left_rows,
3446                    scalar,
3447                },
3448            },
3449            span,
3450        );
3451
3452        let left_flattened = self.flatten_matrix(left_components);
3453        let right_flattened = self.flatten_matrix(right_components);
3454        for c in 0..right_nc {
3455            let result_column = (0..left_nr)
3456                .map(|r| {
3457                    let row = left_flattened.iter().skip(r).step_by(left_nr);
3458                    let column = right_flattened.iter().skip(c * right_nr).take(right_nr);
3459                    self.dot_exprs(row.cloned(), column.cloned(), span)
3460                })
3461                .collect::<Result<Vec<_>, _>>()?;
3462            let expr = Expression::Compose {
3463                ty: result_column_ty,
3464                components: result_column,
3465            };
3466            let handle = self.register_evaluated_expr(expr, span)?;
3467            result.push(handle);
3468        }
3469        Ok(Expression::Compose {
3470            ty: result_ty,
3471            components: result,
3472        })
3473    }
3474
3475    fn flatten_matrix(&self, columns: &[Handle<Expression>]) -> ArrayVec<Handle<Expression>, 16> {
3476        let mut flattened = ArrayVec::<_, 16>::new();
3477        for &column in columns {
3478            let Expression::Compose { ref components, .. } = self.expressions[column] else {
3479                unreachable!()
3480            };
3481            flattened.extend(components.iter().cloned());
3482        }
3483        flattened
3484    }
3485
3486    fn dot_exprs(
3487        &mut self,
3488        left: impl Iterator<Item = Handle<Expression>>,
3489        right: impl Iterator<Item = Handle<Expression>>,
3490        span: Span,
3491    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
3492        let mut acc = None;
3493        for (l, r) in left.zip(right) {
3494            let result = self.binary_op(BinaryOperator::Multiply, l, r, span)?;
3495            match acc.as_mut() {
3496                Some(acc) => *acc = self.binary_op(BinaryOperator::Add, *acc, result, span)?,
3497                None => acc = Some(result),
3498            }
3499        }
3500        Ok(acc.unwrap())
3501    }
3502
3503    fn relational(
3504        &mut self,
3505        fun: RelationalFunction,
3506        arg: Handle<Expression>,
3507        span: Span,
3508    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
3509        let arg = self.eval_zero_value_and_splat(arg, span)?;
3510        match fun {
3511            RelationalFunction::All | RelationalFunction::Any => match self.expressions[arg] {
3512                Expression::Literal(Literal::Bool(_)) => Ok(arg),
3513                Expression::Compose { ty, ref components }
3514                    if matches!(self.types[ty].inner, TypeInner::Vector { .. }) =>
3515                {
3516                    let mut bool_components = ArrayVec::<bool, { crate::VectorSize::MAX }>::new();
3517                    for component in
3518                        crate::proc::flatten_compose(ty, components, self.expressions, self.types)
3519                    {
3520                        match self.expressions[component] {
3521                            Expression::Literal(Literal::Bool(val)) => {
3522                                bool_components.push(val);
3523                            }
3524                            _ => {
3525                                return Err(ConstantEvaluatorError::InvalidRelationalArg(fun));
3526                            }
3527                        }
3528                    }
3529                    let components = bool_components;
3530                    let result = match fun {
3531                        RelationalFunction::All => components.iter().all(|c| *c),
3532                        RelationalFunction::Any => components.iter().any(|c| *c),
3533                        _ => unreachable!(),
3534                    };
3535                    self.register_evaluated_expr(Expression::Literal(Literal::Bool(result)), span)
3536                }
3537                _ => Err(ConstantEvaluatorError::InvalidRelationalArg(fun)),
3538            },
3539            _ => Err(ConstantEvaluatorError::NotImplemented(format!(
3540                "{fun:?} built-in function"
3541            ))),
3542        }
3543    }
3544
3545    /// Deep copy `expr` from `expressions` into `self.expressions`.
3546    ///
3547    /// Return the root of the new copy.
3548    ///
3549    /// This is used when we're evaluating expressions in a function's
3550    /// expression arena that refer to a constant: we need to copy the
3551    /// constant's value into the function's arena so we can operate on it.
3552    fn copy_from(
3553        &mut self,
3554        expr: Handle<Expression>,
3555        expressions: &Arena<Expression>,
3556    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
3557        let span = expressions.get_span(expr);
3558        match expressions[expr] {
3559            ref expr @ (Expression::Literal(_)
3560            | Expression::Constant(_)
3561            | Expression::ZeroValue(_)) => self.register_evaluated_expr(expr.clone(), span),
3562            Expression::Compose { ty, ref components } => {
3563                let mut components = components.clone();
3564                for component in &mut components {
3565                    *component = self.copy_from(*component, expressions)?;
3566                }
3567                self.register_evaluated_expr(Expression::Compose { ty, components }, span)
3568            }
3569            Expression::Splat { size, value } => {
3570                let value = self.copy_from(value, expressions)?;
3571                self.register_evaluated_expr(Expression::Splat { size, value }, span)
3572            }
3573            _ => {
3574                log::debug!("copy_from: SubexpressionsAreNotConstant");
3575                Err(ConstantEvaluatorError::SubexpressionsAreNotConstant)
3576            }
3577        }
3578    }
3579
3580    /// Returns the total number of components, after flattening, of a vector compose expression.
3581    fn vector_compose_flattened_size(
3582        &self,
3583        components: &[Handle<Expression>],
3584    ) -> Result<usize, ConstantEvaluatorError> {
3585        components
3586            .iter()
3587            .try_fold(0, |acc, c| -> Result<_, ConstantEvaluatorError> {
3588                let size = match *self.resolve_type(*c)?.inner_with(self.types) {
3589                    TypeInner::Scalar(_) => 1,
3590                    // We trust that the vector size of `component` is correct,
3591                    // as it will have already been validated when `component`
3592                    // was registered.
3593                    TypeInner::Vector { size, .. } => size as usize,
3594                    _ => return Err(ConstantEvaluatorError::InvalidVectorComposeComponent),
3595                };
3596                Ok(acc + size)
3597            })
3598    }
3599
3600    fn register_evaluated_expr(
3601        &mut self,
3602        expr: Expression,
3603        span: Span,
3604    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
3605        // It suffices to only check_literal_value() for `Literal` expressions,
3606        // since we only register one expression at a time, `Compose`
3607        // expressions can only refer to other expressions, and `ZeroValue`
3608        // expressions are always okay.
3609        if let Expression::Literal(literal) = expr {
3610            crate::valid::check_literal_value(literal)?;
3611        }
3612
3613        // Ensure vector composes contain the correct number of components. We
3614        // do so here when each compose is registered to avoid having to deal
3615        // with the mess each time the compose is used in another expression.
3616        if let Expression::Compose { ty, ref components } = expr {
3617            if let TypeInner::Vector { size, scalar: _ } = self.types[ty].inner {
3618                let expected = size as usize;
3619                let actual = self.vector_compose_flattened_size(components)?;
3620                if expected != actual {
3621                    return Err(ConstantEvaluatorError::InvalidVectorComposeLength {
3622                        expected,
3623                        actual,
3624                    });
3625                }
3626            }
3627        }
3628
3629        Ok(self.append_expr(expr, span, ExpressionKind::Const))
3630    }
3631
3632    fn append_expr(
3633        &mut self,
3634        expr: Expression,
3635        span: Span,
3636        expr_type: ExpressionKind,
3637    ) -> Handle<Expression> {
3638        let h = match self.behavior {
3639            Behavior::Wgsl(
3640                WgslRestrictions::Runtime(ref mut function_local_data)
3641                | WgslRestrictions::Const(Some(ref mut function_local_data)),
3642            )
3643            | Behavior::Glsl(GlslRestrictions::Runtime(ref mut function_local_data)) => {
3644                let is_running = function_local_data.emitter.is_running();
3645                let needs_pre_emit = expr.needs_pre_emit();
3646                if is_running && needs_pre_emit {
3647                    function_local_data
3648                        .block
3649                        .extend(function_local_data.emitter.finish(self.expressions));
3650                    let h = self.expressions.append(expr, span);
3651                    function_local_data.emitter.start(self.expressions);
3652                    h
3653                } else {
3654                    self.expressions.append(expr, span)
3655                }
3656            }
3657            _ => self.expressions.append(expr, span),
3658        };
3659        self.expression_kind_tracker.insert(h, expr_type);
3660        h
3661    }
3662
3663    /// Resolve the type of `expr` if it is a constant expression.
3664    ///
3665    /// If `expr` was evaluated to a constant, returns its type.
3666    /// Otherwise, returns an error.
3667    fn resolve_type(
3668        &self,
3669        expr: Handle<Expression>,
3670    ) -> Result<crate::proc::TypeResolution, ConstantEvaluatorError> {
3671        use crate::proc::TypeResolution as Tr;
3672        use crate::Expression as Ex;
3673        let resolution = match self.expressions[expr] {
3674            Ex::Literal(ref literal) => Tr::Value(literal.ty_inner()),
3675            Ex::Constant(c) => Tr::Handle(self.constants[c].ty),
3676            Ex::ZeroValue(ty) | Ex::Compose { ty, .. } => Tr::Handle(ty),
3677            Ex::Splat { size, value } => {
3678                let Tr::Value(TypeInner::Scalar(scalar)) = self.resolve_type(value)? else {
3679                    return Err(ConstantEvaluatorError::SplatScalarOnly);
3680                };
3681                Tr::Value(TypeInner::Vector { scalar, size })
3682            }
3683            _ => {
3684                log::debug!("resolve_type: SubexpressionsAreNotConstant");
3685                return Err(ConstantEvaluatorError::SubexpressionsAreNotConstant);
3686            }
3687        };
3688
3689        Ok(resolution)
3690    }
3691
3692    fn select(
3693        &mut self,
3694        reject: Handle<Expression>,
3695        accept: Handle<Expression>,
3696        condition: Handle<Expression>,
3697        span: Span,
3698    ) -> Result<Handle<Expression>, ConstantEvaluatorError> {
3699        let mut arg = |arg| self.eval_zero_value_and_splat(arg, span);
3700
3701        let reject = arg(reject)?;
3702        let accept = arg(accept)?;
3703        let condition = arg(condition)?;
3704
3705        let select_single_component =
3706            |this: &mut Self, reject_scalar, reject, accept, condition| {
3707                let accept = this.cast(accept, reject_scalar, span)?;
3708                if condition {
3709                    Ok(accept)
3710                } else {
3711                    Ok(reject)
3712                }
3713            };
3714
3715        match (&self.expressions[reject], &self.expressions[accept]) {
3716            (&Expression::Literal(reject_lit), &Expression::Literal(_accept_lit)) => {
3717                let reject_scalar = reject_lit.scalar();
3718                let &Expression::Literal(Literal::Bool(condition)) = &self.expressions[condition]
3719                else {
3720                    return Err(ConstantEvaluatorError::SelectScalarConditionNotABool);
3721                };
3722                select_single_component(self, reject_scalar, reject, accept, condition)
3723            }
3724            (
3725                &Expression::Compose {
3726                    ty: reject_ty,
3727                    components: ref reject_components,
3728                },
3729                &Expression::Compose {
3730                    ty: accept_ty,
3731                    components: ref accept_components,
3732                },
3733            ) => {
3734                let ty_deets = |ty| {
3735                    self.types[ty]
3736                        .inner
3737                        .vector_size_and_scalar()
3738                        .map(|(size, scalar)| {
3739                            (size.expect("expected vector type, not scalar type"), scalar)
3740                        })
3741                };
3742
3743                let expected_vec_size = {
3744                    let [(reject_vec_size, _), (accept_vec_size, _)] =
3745                        [reject_ty, accept_ty].map(|ty| ty_deets(ty).unwrap());
3746
3747                    if reject_vec_size != accept_vec_size {
3748                        return Err(ConstantEvaluatorError::SelectVecRejectAcceptSizeMismatch {
3749                            reject: reject_vec_size,
3750                            accept: accept_vec_size,
3751                        });
3752                    }
3753                    reject_vec_size
3754                };
3755
3756                let condition_components = match self.expressions[condition] {
3757                    Expression::Literal(Literal::Bool(condition)) => {
3758                        vec![condition; (expected_vec_size as u8).into()]
3759                    }
3760                    Expression::Compose {
3761                        ty: condition_ty,
3762                        components: ref condition_components,
3763                    } => {
3764                        let Some((condition_vec_size, condition_scalar)) = ty_deets(condition_ty)
3765                        else {
3766                            return Err(ConstantEvaluatorError::SelectConditionNotAVecBool);
3767                        };
3768                        if condition_scalar.kind != ScalarKind::Bool {
3769                            return Err(ConstantEvaluatorError::SelectConditionNotAVecBool);
3770                        }
3771                        if condition_vec_size != expected_vec_size {
3772                            return Err(ConstantEvaluatorError::SelectConditionVecSizeMismatch);
3773                        }
3774                        condition_components
3775                            .iter()
3776                            .copied()
3777                            .map(|component| match &self.expressions[component] {
3778                                &Expression::Literal(Literal::Bool(condition)) => condition,
3779                                _ => unreachable!(),
3780                            })
3781                            .collect()
3782                    }
3783
3784                    _ => return Err(ConstantEvaluatorError::SelectConditionNotAVecBool),
3785                };
3786
3787                let evaluated = Expression::Compose {
3788                    ty: reject_ty,
3789                    components: reject_components
3790                        .clone()
3791                        .into_iter()
3792                        .zip(accept_components.clone())
3793                        .zip(condition_components)
3794                        .map(|((reject, accept), condition)| {
3795                            let reject_scalar = match &self.expressions[reject] {
3796                                &Expression::Literal(lit) => lit.scalar(),
3797                                _ => unreachable!(),
3798                            };
3799                            select_single_component(self, reject_scalar, reject, accept, condition)
3800                        })
3801                        .collect::<Result<_, _>>()?,
3802                };
3803                self.register_evaluated_expr(evaluated, span)
3804            }
3805            _ => Err(ConstantEvaluatorError::SelectAcceptRejectTypeMismatch),
3806        }
3807    }
3808}
3809
3810/// If `dot(e2, e3)` is negative, `e1` returns, otherwise `-e1`.
3811fn float_face_forward<F>(
3812    e1: &[F],
3813    e2: &[F],
3814    e3: &[F],
3815) -> Option<ArrayVec<F, { crate::VectorSize::MAX }>>
3816where
3817    F: num_traits::Float,
3818{
3819    let d = float_dot(e2, e3)?;
3820
3821    let mut out = ArrayVec::new();
3822    for &e in e1 {
3823        out.push(if d < F::zero() { e } else { -e });
3824    }
3825    Some(out)
3826}
3827
3828/// The reflection of incident vector `e1` off a surface oriented `e2`,
3829/// `e1 - 2 * dot(e2, e1) * e2`.
3830fn float_reflect<F>(e1: &[F], e2: &[F]) -> Option<ArrayVec<F, { crate::VectorSize::MAX }>>
3831where
3832    F: num_traits::Float,
3833{
3834    let d = float_dot(e2, e1)?;
3835    let two = F::one() + F::one();
3836
3837    let mut out = ArrayVec::new();
3838    for (&a, &b) in e1.iter().zip(e2) {
3839        let r = a - two * d * b;
3840        if !r.is_finite() {
3841            return None;
3842        }
3843        out.push(r);
3844    }
3845    Some(out)
3846}
3847
3848/// The refraction of incident vector `e1` through a surface with normal `e2`,
3849/// for a ratio of indices of refraction `e3`.
3850fn float_refract<F>(e1: &[F], e2: &[F], e3: F) -> Option<ArrayVec<F, { crate::VectorSize::MAX }>>
3851where
3852    F: num_traits::Float,
3853{
3854    let d = float_dot(e2, e1)?;
3855    let one = F::one();
3856
3857    let k = one - e3 * e3 * (one - d * d);
3858    if !k.is_finite() {
3859        return None;
3860    }
3861
3862    let mut out = ArrayVec::new();
3863
3864    // If there is total internal reflection, returns zero vector.
3865    if k < F::zero() {
3866        for _ in e1 {
3867            out.push(F::zero());
3868        }
3869        return Some(out);
3870    }
3871
3872    let scale = e3 * d + k.sqrt();
3873    for (&a, &b) in e1.iter().zip(e2) {
3874        let r = e3 * a - scale * b;
3875        if !r.is_finite() {
3876            return None;
3877        }
3878        out.push(r);
3879    }
3880    Some(out)
3881}
3882
3883#[test]
3884fn face_forward_smoke() {
3885    #[track_caller]
3886    fn ff(e1: &[f32], e2: &[f32], e3: &[f32]) -> Vec<f32> {
3887        float_face_forward(e1, e2, e3).unwrap().to_vec()
3888    }
3889
3890    // If `dot(e2, e3)` is negative, return `e1`, otherwise return `-e1`.
3891    assert_eq!(ff(&[1.0, 2.0], &[-1.0, 0.0], &[1.0, 0.0]), [1.0, 2.0]);
3892    assert_eq!(ff(&[1.0, 2.0], &[1.0, 0.0], &[1.0, 0.0]), [-1.0, -2.0]);
3893
3894    // Zero = flip `e1`.
3895    assert_eq!(ff(&[1.0, 2.0], &[0.0, 1.0], &[1.0, 0.0]), [-1.0, -2.0]);
3896
3897    assert_eq!(
3898        ff(&[1.0, 2.0, 3.0], &[-1.0, 0.0, 0.0], &[1.0, 0.0, 0.0]),
3899        [1.0, 2.0, 3.0]
3900    );
3901
3902    // Return None if `dot(e2, e3)` is too big to compute.
3903    assert!(float_face_forward(&[1.0f32, 0.0], &[f32::MAX, 0.0], &[f32::MAX, 0.0]).is_none());
3904}
3905
3906#[test]
3907fn reflect_smoke() {
3908    #[track_caller]
3909    fn rf(e1: &[f32], e2: &[f32]) -> Vec<f32> {
3910        float_reflect(e1, e2).unwrap().to_vec()
3911    }
3912
3913    // Bouncing off a floor flips the component along the normal.
3914    assert_eq!(rf(&[1.0, -1.0], &[0.0, 1.0]), [1.0, 1.0]);
3915    assert_eq!(rf(&[1.0, -1.0, 0.0], &[0.0, 1.0, 0.0]), [1.0, 1.0, 0.0]);
3916
3917    // Head-on reverses the vector entirely.
3918    assert_eq!(rf(&[1.0, 0.0], &[1.0, 0.0]), [-1.0, 0.0]);
3919
3920    // A surface parallel to the incident vector leaves it alone.
3921    assert_eq!(rf(&[1.0, 0.0], &[0.0, 1.0]), [1.0, 0.0]);
3922
3923    assert!(float_reflect(&[1.0f32, 0.0], &[f32::MAX, 0.0]).is_none());
3924}
3925
3926#[test]
3927fn refract_smoke() {
3928    #[track_caller]
3929    fn rr(e1: &[f32], e2: &[f32], e3: f32) -> Vec<f32> {
3930        float_refract(e1, e2, e3).unwrap().to_vec()
3931    }
3932
3933    // No change if blending ratio is 1 and a straight surface collision.
3934    assert_eq!(rr(&[0.0, -1.0], &[0.0, 1.0], 1.0), [0.0, -1.0]);
3935    assert_eq!(rr(&[0.5, -0.5], &[0.0, 1.0], 1.0), [0.5, -0.5]);
3936
3937    // A normal facing the opposite way will bend vector to other side.
3938    assert_eq!(rr(&[0.5, -0.5], &[0.0, -1.0], 1.0), [0.5, 0.5]);
3939
3940    // Ratios below 1 shorten the transmitted vector.
3941    assert_eq!(rr(&[0.0, -1.0], &[0.0, 1.0], 0.5), [0.0, -1.0]);
3942
3943    // ‘no refraction possible’ means k goes negative and result is zero.
3944    assert_eq!(rr(&[0.8, -0.6], &[0.0, 1.0], 2.0), [0.0, 0.0]);
3945    assert_eq!(
3946        rr(&[0.8, -0.6, 0.0], &[0.0, 1.0, 0.0], 2.0),
3947        [0.0, 0.0, 0.0]
3948    );
3949
3950    assert!(float_refract(&[1.0f32, 0.0], &[f32::MAX, 0.0], 1.0).is_none());
3951    assert!(float_refract(&[1.0f32, 0.0], &[0.0, 1.0], f32::MAX).is_none());
3952}
3953
3954/// Return a u32 according to the number of bits in `T`, the `w` of the
3955/// `extractBits` and `insertBits` specifications.
3956const fn bit_width<T>() -> u32 {
3957    size_of::<T>() as u32 * 8
3958}
3959
3960/// Reject the `offset` and `count` arguments of `extractBits` and `insertBits`
3961/// if they select bits outside an operand `width` bits wide.
3962///
3963/// The WGSL specification says that this is a shader creation error if `offset`
3964/// and `count` are const expressions, *even if the operand is not*, so the WGSL
3965/// front end will fail immediately if it sees both are const.
3966pub fn check_bitfield_range(
3967    builtin: &'static str,
3968    offset: u32,
3969    count: u32,
3970    width: u32,
3971) -> Result<(), ConstantEvaluatorError> {
3972    if u64::from(offset) + u64::from(count) > u64::from(width) {
3973        return Err(ConstantEvaluatorError::BitfieldRangeTooLarge {
3974            builtin,
3975            offset,
3976            count,
3977            width,
3978        });
3979    }
3980    Ok(())
3981}
3982
3983fn extract_bits<T>(
3984    e: &[T],
3985    offset: u32,
3986    count: u32,
3987) -> Result<ArrayVec<T, { crate::VectorSize::MAX }>, ConstantEvaluatorError>
3988where
3989    T: num_traits::PrimInt,
3990{
3991    check_bitfield_range("extractBits", offset, count, bit_width::<T>())?;
3992    let w = bit_width::<T>();
3993
3994    let mut out = ArrayVec::new();
3995    for &e in e {
3996        out.push(if count == 0 {
3997            T::zero()
3998        } else {
3999            // Shift field up then shift back down.
4000            // - if signed, the empty space fills with the field's top bit
4001            // - if unsigned, the empty space will fill with zeroes
4002            // count is never zero here
4003            (e << (w - offset - count) as usize) >> (w - count) as usize
4004        });
4005    }
4006    Ok(out)
4007}
4008
4009fn insert_bits<T>(
4010    e: &[T],
4011    newbits: &[T],
4012    offset: u32,
4013    count: u32,
4014) -> Result<ArrayVec<T, { crate::VectorSize::MAX }>, ConstantEvaluatorError>
4015where
4016    T: num_traits::PrimInt,
4017{
4018    check_bitfield_range("insertBits", offset, count, bit_width::<T>())?;
4019    let w = bit_width::<T>();
4020
4021    let mut out = ArrayVec::new();
4022    for (&e, &newbits) in e.iter().zip(newbits) {
4023        out.push(if count == 0 {
4024            e
4025        } else {
4026            let mask = (!T::zero()).unsigned_shr(w - count) << offset as usize;
4027            (e & !mask) | ((newbits << offset as usize) & mask)
4028        });
4029    }
4030    Ok(out)
4031}
4032
4033#[cfg(test)]
4034fn extract_bits_scalar<T: num_traits::PrimInt>(e: T, offset: u32, count: u32) -> T {
4035    extract_bits(&[e], offset, count).unwrap()[0]
4036}
4037
4038#[cfg(test)]
4039fn insert_bits_scalar<T: num_traits::PrimInt>(e: T, newbits: T, offset: u32, count: u32) -> T {
4040    insert_bits(&[e], &[newbits], offset, count).unwrap()[0]
4041}
4042
4043#[test]
4044fn extract_bits_smoke() {
4045    // `count` of zero always yields zero, whatever `offset` selects.
4046    assert_eq!(extract_bits_scalar(0xffffffff_u32, 0, 0), 0);
4047    assert_eq!(extract_bits_scalar(-1_i32, 32, 0), 0);
4048
4049    // Selecting the whole width is the identity.
4050    assert_eq!(extract_bits_scalar(0x12345678_u32, 0, 32), 0x12345678);
4051    assert_eq!(extract_bits_scalar(i32::MIN, 0, 32), i32::MIN);
4052
4053    // Unsigned extraction fills the bits above the field with zero.
4054    assert_eq!(extract_bits_scalar(0x12345678_u32, 8, 8), 0x56);
4055    assert_eq!(extract_bits_scalar(0xf0000000_u32, 28, 4), 0xf);
4056    assert_eq!(extract_bits_scalar(0x12345678_u32, 31, 1), 0);
4057
4058    // Signed extraction fills them from the top bit of the field instead.
4059    assert_eq!(extract_bits_scalar(0x12345678_i32, 8, 8), 0x56);
4060    assert_eq!(extract_bits_scalar(0x8_i32, 3, 1), -1);
4061    assert_eq!(extract_bits_scalar(0xf0000000_u32 as i32, 28, 4), -1);
4062    assert_eq!(extract_bits_scalar(0x70000000_i32, 28, 4), 7);
4063
4064    // Widths other than 32 use their own `w`.
4065    assert_eq!(extract_bits_scalar(0x1234_u16, 4, 8), 0x23);
4066    assert_eq!(extract_bits_scalar(-1_i16, 0, 16), -1);
4067    assert_eq!(
4068        extract_bits_scalar(0x123456789abcdef0_u64, 32, 32),
4069        0x12345678
4070    );
4071    assert_eq!(extract_bits_scalar(-1_i64, 63, 1), -1);
4072
4073    // `offset + count` past the end of the type is a shader creation error.
4074    assert!(extract_bits(&[0_u32], 30, 8).is_err());
4075    assert!(extract_bits(&[0_u32], 33, 0).is_err());
4076    assert!(extract_bits(&[0_u16], 8, 16).is_err());
4077    assert!(extract_bits(&[0_u32], u32::MAX, u32::MAX).is_err());
4078    assert!(extract_bits(&[0_u32], 32, 0).is_ok());
4079}
4080
4081#[test]
4082fn insert_bits_smoke() {
4083    // `count` of zero leaves `e` untouched.
4084    assert_eq!(
4085        insert_bits_scalar(0x12345678_u32, 0xffffffff, 0, 0),
4086        0x12345678
4087    );
4088    assert_eq!(insert_bits_scalar(-1_i32, 0, 32, 0), -1);
4089
4090    // Covering the whole width will replace `e` entirely.
4091    assert_eq!(
4092        insert_bits_scalar(0x12345678_u32, 0xdeadbeef, 0, 32),
4093        0xdeadbeef
4094    );
4095    assert_eq!(insert_bits_scalar(0_i32, i32::MIN, 0, 32), i32::MIN);
4096
4097    // Only bits `offset..offset + count` are taken from `newbits`, and only its
4098    // low `count` bits are used.
4099    assert_eq!(insert_bits_scalar(0x12345678_u32, 0xff, 8, 8), 0x1234ff78);
4100    assert_eq!(insert_bits_scalar(0x12345678_u32, 0xabcd, 8, 8), 0x1234cd78);
4101    assert_eq!(insert_bits_scalar(0_u32, 0xf, 28, 4), 0xf0000000);
4102    assert_eq!(insert_bits_scalar(0_u32, 1, 31, 1), 0x80000000);
4103
4104    // Signed operands set the sign bit like any other.
4105    assert_eq!(insert_bits_scalar(0_i32, -1, 31, 1), i32::MIN);
4106    assert_eq!(insert_bits_scalar(-1_i32, 0, 0, 31), i32::MIN);
4107
4108    // Widths other than 32 use their own `w`.
4109    assert_eq!(insert_bits_scalar(0x1234_u16, 0xf, 4, 4), 0x12f4);
4110    assert_eq!(insert_bits_scalar(0_i16, -1, 15, 1), i16::MIN);
4111    assert_eq!(
4112        insert_bits_scalar(0_u64, 0xffffffff, 32, 32),
4113        0xffffffff00000000
4114    );
4115
4116    // `offset + count` past the end of the type is a shader creation error.
4117    assert!(insert_bits(&[0_u32], &[0], 30, 8).is_err());
4118    assert!(insert_bits(&[0_u32], &[0], 33, 0).is_err());
4119    assert!(insert_bits(&[0_u16], &[0], 8, 16).is_err());
4120    assert!(insert_bits(&[0_u32], &[0], u32::MAX, u32::MAX).is_err());
4121    assert!(insert_bits(&[0_u32], &[0], 32, 0).is_ok());
4122}
4123
4124fn first_trailing_bit(concrete_int: ConcreteInt<1>) -> ConcreteInt<1> {
4125    // NOTE: Bit indices for this built-in start at 0 at the "right" (or LSB). For example, a value
4126    // of 1 means the least significant bit is set. Therefore, an input of `0x[80 00…]` would
4127    // return a right-to-left bit index of 0.
4128    let trailing_zeros_to_bit_idx = |e: u32| -> u32 {
4129        match e {
4130            idx @ 0..=31 => idx,
4131            32 => u32::MAX,
4132            _ => unreachable!(),
4133        }
4134    };
4135    match concrete_int {
4136        ConcreteInt::U32([e]) => ConcreteInt::U32([trailing_zeros_to_bit_idx(e.trailing_zeros())]),
4137        ConcreteInt::I32([e]) => {
4138            ConcreteInt::I32([trailing_zeros_to_bit_idx(e.trailing_zeros()) as i32])
4139        }
4140    }
4141}
4142
4143#[test]
4144fn first_trailing_bit_smoke() {
4145    assert_eq!(
4146        first_trailing_bit(ConcreteInt::I32([0])),
4147        ConcreteInt::I32([-1])
4148    );
4149    assert_eq!(
4150        first_trailing_bit(ConcreteInt::I32([1])),
4151        ConcreteInt::I32([0])
4152    );
4153    assert_eq!(
4154        first_trailing_bit(ConcreteInt::I32([2])),
4155        ConcreteInt::I32([1])
4156    );
4157    assert_eq!(
4158        first_trailing_bit(ConcreteInt::I32([-1])),
4159        ConcreteInt::I32([0]),
4160    );
4161    assert_eq!(
4162        first_trailing_bit(ConcreteInt::I32([i32::MIN])),
4163        ConcreteInt::I32([31]),
4164    );
4165    assert_eq!(
4166        first_trailing_bit(ConcreteInt::I32([i32::MAX])),
4167        ConcreteInt::I32([0]),
4168    );
4169    for idx in 0..32 {
4170        assert_eq!(
4171            first_trailing_bit(ConcreteInt::I32([1 << idx])),
4172            ConcreteInt::I32([idx])
4173        )
4174    }
4175
4176    assert_eq!(
4177        first_trailing_bit(ConcreteInt::U32([0])),
4178        ConcreteInt::U32([u32::MAX])
4179    );
4180    assert_eq!(
4181        first_trailing_bit(ConcreteInt::U32([1])),
4182        ConcreteInt::U32([0])
4183    );
4184    assert_eq!(
4185        first_trailing_bit(ConcreteInt::U32([2])),
4186        ConcreteInt::U32([1])
4187    );
4188    assert_eq!(
4189        first_trailing_bit(ConcreteInt::U32([1 << 31])),
4190        ConcreteInt::U32([31]),
4191    );
4192    assert_eq!(
4193        first_trailing_bit(ConcreteInt::U32([u32::MAX])),
4194        ConcreteInt::U32([0]),
4195    );
4196    for idx in 0..32 {
4197        assert_eq!(
4198            first_trailing_bit(ConcreteInt::U32([1 << idx])),
4199            ConcreteInt::U32([idx])
4200        )
4201    }
4202}
4203
4204fn first_leading_bit(concrete_int: ConcreteInt<1>) -> ConcreteInt<1> {
4205    // NOTE: Bit indices for this built-in start at 0 at the "right" (or LSB). For example, 1 means
4206    // the least significant bit is set. Therefore, an input of 1 would return a right-to-left bit
4207    // index of 0.
4208    let rtl_to_ltr_bit_idx = |e: u32| -> u32 {
4209        match e {
4210            idx @ 0..=31 => 31 - idx,
4211            32 => u32::MAX,
4212            _ => unreachable!(),
4213        }
4214    };
4215    match concrete_int {
4216        ConcreteInt::I32([e]) => ConcreteInt::I32([{
4217            let rtl_bit_index = if e.is_negative() {
4218                e.leading_ones()
4219            } else {
4220                e.leading_zeros()
4221            };
4222            rtl_to_ltr_bit_idx(rtl_bit_index) as i32
4223        }]),
4224        ConcreteInt::U32([e]) => ConcreteInt::U32([rtl_to_ltr_bit_idx(e.leading_zeros())]),
4225    }
4226}
4227
4228#[test]
4229fn first_leading_bit_smoke() {
4230    assert_eq!(
4231        first_leading_bit(ConcreteInt::I32([-1])),
4232        ConcreteInt::I32([-1])
4233    );
4234    assert_eq!(
4235        first_leading_bit(ConcreteInt::I32([0])),
4236        ConcreteInt::I32([-1])
4237    );
4238    assert_eq!(
4239        first_leading_bit(ConcreteInt::I32([1])),
4240        ConcreteInt::I32([0])
4241    );
4242    assert_eq!(
4243        first_leading_bit(ConcreteInt::I32([-2])),
4244        ConcreteInt::I32([0])
4245    );
4246    assert_eq!(
4247        first_leading_bit(ConcreteInt::I32([1234 + 4567])),
4248        ConcreteInt::I32([12])
4249    );
4250    assert_eq!(
4251        first_leading_bit(ConcreteInt::I32([i32::MAX])),
4252        ConcreteInt::I32([30])
4253    );
4254    assert_eq!(
4255        first_leading_bit(ConcreteInt::I32([i32::MIN])),
4256        ConcreteInt::I32([30])
4257    );
4258    // NOTE: Ignore the sign bit, which is a separate (above) case.
4259    for idx in 0..(32 - 1) {
4260        assert_eq!(
4261            first_leading_bit(ConcreteInt::I32([1 << idx])),
4262            ConcreteInt::I32([idx])
4263        );
4264    }
4265    for idx in 1..(32 - 1) {
4266        assert_eq!(
4267            first_leading_bit(ConcreteInt::I32([-(1 << idx)])),
4268            ConcreteInt::I32([idx - 1])
4269        );
4270    }
4271
4272    assert_eq!(
4273        first_leading_bit(ConcreteInt::U32([0])),
4274        ConcreteInt::U32([u32::MAX])
4275    );
4276    assert_eq!(
4277        first_leading_bit(ConcreteInt::U32([1])),
4278        ConcreteInt::U32([0])
4279    );
4280    assert_eq!(
4281        first_leading_bit(ConcreteInt::U32([u32::MAX])),
4282        ConcreteInt::U32([31])
4283    );
4284    for idx in 0..32 {
4285        assert_eq!(
4286            first_leading_bit(ConcreteInt::U32([1 << idx])),
4287            ConcreteInt::U32([idx])
4288        )
4289    }
4290}
4291
4292/// Trait for conversions of abstract values to concrete types.
4293trait TryFromAbstract<T>: Sized {
4294    /// Convert an abstract literal `value` to `Self`.
4295    ///
4296    /// Since Naga's [`AbstractInt`] and [`AbstractFloat`] exist to support
4297    /// WGSL, we follow WGSL's conversion rules here:
4298    ///
4299    /// - WGSL §6.1.2. Conversion Rank says that automatic conversions
4300    ///   from [`AbstractInt`] to an integer type are either lossless or an
4301    ///   error.
4302    ///
4303    /// - WGSL §15.7.6 Floating Point Conversion says that conversions
4304    ///   to floating point in constant expressions and override
4305    ///   expressions are errors if the value is out of range for the
4306    ///   destination type, but rounding is okay.
4307    ///
4308    /// - WGSL §17.1.2 i32()/u32() constructors treat AbstractFloat as any
4309    ///   other floating point type, following the scalar floating point to
4310    ///   integral conversion algorithm (§15.7.6). There is no automatic
4311    ///   conversion from AbstractFloat to integer types.
4312    ///
4313    /// [`AbstractInt`]: crate::Literal::AbstractInt
4314    /// [`AbstractFloat`]: crate::Literal::AbstractFloat
4315    fn try_from_abstract(value: T) -> Result<Self, ConstantEvaluatorError>;
4316}
4317
4318impl TryFromAbstract<i64> for i32 {
4319    fn try_from_abstract(value: i64) -> Result<i32, ConstantEvaluatorError> {
4320        i32::try_from(value).map_err(|_| ConstantEvaluatorError::AutomaticConversionLossy {
4321            value: format!("{value:?}"),
4322            to_type: "i32",
4323        })
4324    }
4325}
4326
4327impl TryFromAbstract<i64> for u32 {
4328    fn try_from_abstract(value: i64) -> Result<u32, ConstantEvaluatorError> {
4329        u32::try_from(value).map_err(|_| ConstantEvaluatorError::AutomaticConversionLossy {
4330            value: format!("{value:?}"),
4331            to_type: "u32",
4332        })
4333    }
4334}
4335
4336impl TryFromAbstract<i64> for u64 {
4337    fn try_from_abstract(value: i64) -> Result<u64, ConstantEvaluatorError> {
4338        u64::try_from(value).map_err(|_| ConstantEvaluatorError::AutomaticConversionLossy {
4339            value: format!("{value:?}"),
4340            to_type: "u64",
4341        })
4342    }
4343}
4344
4345impl TryFromAbstract<i64> for i64 {
4346    fn try_from_abstract(value: i64) -> Result<i64, ConstantEvaluatorError> {
4347        Ok(value)
4348    }
4349}
4350
4351impl TryFromAbstract<i64> for f32 {
4352    fn try_from_abstract(value: i64) -> Result<Self, ConstantEvaluatorError> {
4353        let f = value as f32;
4354        // The range of `i64` is roughly ±18 × 10¹⁸, whereas the range of
4355        // `f32` is roughly ±3.4 × 10³⁸, so there's no opportunity for
4356        // overflow here.
4357        Ok(f)
4358    }
4359}
4360
4361impl TryFromAbstract<f64> for f32 {
4362    fn try_from_abstract(value: f64) -> Result<f32, ConstantEvaluatorError> {
4363        let f = value as f32;
4364        if f.is_infinite() {
4365            return Err(ConstantEvaluatorError::AutomaticConversionLossy {
4366                value: format!("{value:?}"),
4367                to_type: "f32",
4368            });
4369        }
4370        Ok(f)
4371    }
4372}
4373
4374impl TryFromAbstract<i64> for f64 {
4375    fn try_from_abstract(value: i64) -> Result<Self, ConstantEvaluatorError> {
4376        let f = value as f64;
4377        // The range of `i64` is roughly ±18 × 10¹⁸, whereas the range of
4378        // `f64` is roughly ±1.8 × 10³⁰⁸, so there's no opportunity for
4379        // overflow here.
4380        Ok(f)
4381    }
4382}
4383
4384impl TryFromAbstract<f64> for f64 {
4385    fn try_from_abstract(value: f64) -> Result<f64, ConstantEvaluatorError> {
4386        Ok(value)
4387    }
4388}
4389
4390impl TryFromAbstract<f64> for i32 {
4391    fn try_from_abstract(value: f64) -> Result<Self, ConstantEvaluatorError> {
4392        // https://www.w3.org/TR/WGSL/#floating-point-conversion
4393        // To convert a floating point scalar value X to an integer scalar type T:
4394        // * If X is a NaN, the result is an indeterminate value in T.
4395        // * If X is exactly representable in the target type T, then the
4396        //   result is that value.
4397        // * Otherwise, the result is the value in T closest to truncate(X) and
4398        //   also exactly representable in the original floating point type.
4399        //
4400        // A rust cast satisfies these requirements apart from "the result
4401        // is... exactly representable in the original floating point type".
4402        // However, i32::MIN and i32::MAX are exactly representable by f64, so
4403        // we're all good.
4404        Ok(value as i32)
4405    }
4406}
4407
4408impl TryFromAbstract<f64> for u32 {
4409    fn try_from_abstract(value: f64) -> Result<Self, ConstantEvaluatorError> {
4410        // As above, u32::MIN and u32::MAX are exactly representable by f64,
4411        // so a simple rust cast is sufficient.
4412        Ok(value as u32)
4413    }
4414}
4415
4416impl TryFromAbstract<f64> for i64 {
4417    fn try_from_abstract(value: f64) -> Result<Self, ConstantEvaluatorError> {
4418        // As above, except we clamp to the minimum and maximum values
4419        // representable by both f64 and i64.
4420        use crate::proc::type_methods::IntFloatLimits;
4421        Ok(value.clamp(i64::min_float(), i64::max_float()) as i64)
4422    }
4423}
4424
4425impl TryFromAbstract<f64> for u64 {
4426    fn try_from_abstract(value: f64) -> Result<Self, ConstantEvaluatorError> {
4427        // As above, this time clamping to the minimum and maximum values
4428        // representable by both f64 and u64.
4429        use crate::proc::type_methods::IntFloatLimits;
4430        Ok(value.clamp(u64::min_float(), u64::max_float()) as u64)
4431    }
4432}
4433
4434impl TryFromAbstract<f64> for f16 {
4435    fn try_from_abstract(value: f64) -> Result<f16, ConstantEvaluatorError> {
4436        let f = f16::from_f64(value);
4437        if f.is_infinite() {
4438            return Err(ConstantEvaluatorError::AutomaticConversionLossy {
4439                value: format!("{value:?}"),
4440                to_type: "f16",
4441            });
4442        }
4443        Ok(f)
4444    }
4445}
4446
4447impl TryFromAbstract<i64> for f16 {
4448    fn try_from_abstract(value: i64) -> Result<f16, ConstantEvaluatorError> {
4449        let f = f16::from_i64(value);
4450        if f.is_none() {
4451            return Err(ConstantEvaluatorError::AutomaticConversionLossy {
4452                value: format!("{value:?}"),
4453                to_type: "f16",
4454            });
4455        }
4456        Ok(f.unwrap())
4457    }
4458}
4459
4460fn cross_product<T>(a: [T; 3], b: [T; 3]) -> [T; 3]
4461where
4462    T: Copy,
4463    T: core::ops::Mul<T, Output = T>,
4464    T: core::ops::Sub<T, Output = T>,
4465{
4466    [
4467        a[1] * b[2] - a[2] * b[1],
4468        a[2] * b[0] - a[0] * b[2],
4469        a[0] * b[1] - a[1] * b[0],
4470    ]
4471}
4472
4473#[cfg(test)]
4474mod tests {
4475    use alloc::{vec, vec::Vec};
4476
4477    use crate::{
4478        Arena, BinaryOperator, Constant, Expression, FastHashMap, Handle, Literal, Type, TypeInner,
4479        UnaryOperator, UniqueArena, VectorSize,
4480    };
4481
4482    use super::{Behavior, ConstantEvaluator, ExpressionKindTracker, WgslRestrictions};
4483
4484    #[test]
4485    fn unary_op() {
4486        let mut types = UniqueArena::new();
4487        let mut constants = Arena::new();
4488        let overrides = Arena::new();
4489        let mut global_expressions = Arena::new();
4490
4491        let scalar_ty = types.insert(
4492            Type {
4493                name: None,
4494                inner: TypeInner::Scalar(crate::Scalar::I32),
4495            },
4496            Default::default(),
4497        );
4498
4499        let vec_ty = types.insert(
4500            Type {
4501                name: None,
4502                inner: TypeInner::Vector {
4503                    size: VectorSize::Bi,
4504                    scalar: crate::Scalar::I32,
4505                },
4506            },
4507            Default::default(),
4508        );
4509
4510        let h = constants.append(
4511            Constant {
4512                name: None,
4513                ty: scalar_ty,
4514                init: global_expressions
4515                    .append(Expression::Literal(Literal::I32(4)), Default::default()),
4516            },
4517            Default::default(),
4518        );
4519
4520        let h1 = constants.append(
4521            Constant {
4522                name: None,
4523                ty: scalar_ty,
4524                init: global_expressions
4525                    .append(Expression::Literal(Literal::I32(8)), Default::default()),
4526            },
4527            Default::default(),
4528        );
4529
4530        let vec_h = constants.append(
4531            Constant {
4532                name: None,
4533                ty: vec_ty,
4534                init: global_expressions.append(
4535                    Expression::Compose {
4536                        ty: vec_ty,
4537                        components: vec![constants[h].init, constants[h1].init],
4538                    },
4539                    Default::default(),
4540                ),
4541            },
4542            Default::default(),
4543        );
4544
4545        let expr = global_expressions.append(Expression::Constant(h), Default::default());
4546        let expr1 = global_expressions.append(Expression::Constant(vec_h), Default::default());
4547
4548        let expr2 = Expression::Unary {
4549            op: UnaryOperator::Negate,
4550            expr,
4551        };
4552
4553        let expr3 = Expression::Unary {
4554            op: UnaryOperator::BitwiseNot,
4555            expr,
4556        };
4557
4558        let expr4 = Expression::Unary {
4559            op: UnaryOperator::BitwiseNot,
4560            expr: expr1,
4561        };
4562
4563        let expression_kind_tracker = &mut ExpressionKindTracker::from_arena(&global_expressions);
4564        let mut solver = ConstantEvaluator {
4565            behavior: Behavior::Wgsl(WgslRestrictions::Const(None)),
4566            types: &mut types,
4567            constants: &constants,
4568            overrides: &overrides,
4569            expressions: &mut global_expressions,
4570            expression_kind_tracker,
4571            layouter: &mut crate::proc::Layouter::default(),
4572        };
4573
4574        let res1 = solver
4575            .try_eval_and_append(expr2, Default::default())
4576            .unwrap();
4577        let res2 = solver
4578            .try_eval_and_append(expr3, Default::default())
4579            .unwrap();
4580        let res3 = solver
4581            .try_eval_and_append(expr4, Default::default())
4582            .unwrap();
4583
4584        assert_eq!(
4585            global_expressions[res1],
4586            Expression::Literal(Literal::I32(-4))
4587        );
4588
4589        assert_eq!(
4590            global_expressions[res2],
4591            Expression::Literal(Literal::I32(!4))
4592        );
4593
4594        let res3_inner = &global_expressions[res3];
4595
4596        match *res3_inner {
4597            Expression::Compose {
4598                ref ty,
4599                ref components,
4600            } => {
4601                assert_eq!(*ty, vec_ty);
4602                let mut components_iter = components.iter().copied();
4603                assert_eq!(
4604                    global_expressions[components_iter.next().unwrap()],
4605                    Expression::Literal(Literal::I32(!4))
4606                );
4607                assert_eq!(
4608                    global_expressions[components_iter.next().unwrap()],
4609                    Expression::Literal(Literal::I32(!8))
4610                );
4611                assert!(components_iter.next().is_none());
4612            }
4613            _ => panic!("Expected vector"),
4614        }
4615    }
4616
4617    #[test]
4618    fn matrix_op() {
4619        let mut helper = MatrixTestHelper::new();
4620
4621        for nc in 2..=4 {
4622            for nr in 2..=4 {
4623                // Validates multiplication on vector-matrix.
4624                // vecR(0, 1, .., r) * matCxR(0, 1, .., nc * nr)
4625                let evaluated = helper.eval_vector_multiply_matrix(nc, nr);
4626                let expected = (0..nc)
4627                    .map(|c| (0..nr).map(|r| (r * (c * nr + r)) as f32).sum())
4628                    .collect::<Vec<f32>>();
4629                assert_eq!(evaluated, expected);
4630
4631                // Validates multiplication on matrix-vector.
4632                // matCxR(0, 1, .., nc * nr) * vecC(0, 1, .., nc)
4633                let evaluated = helper.eval_matrix_multiply_vector(nc, nr);
4634                let expected = (0..nr)
4635                    .map(|r| (0..nc).map(|c| (c * (c * nr + r)) as f32).sum())
4636                    .collect::<Vec<f32>>();
4637                assert_eq!(evaluated, expected);
4638
4639                for k in 2..=4 {
4640                    // Validates multiplication on matrix-matrix.
4641                    // matKxR(0, 1, .., k * nr) * matCxK(0, 1, .., nc * k)
4642                    let evaluated = helper.eval_matrix_multiply_matrix(nr, nc, k);
4643                    let expected = (0..nc)
4644                        .flat_map(|c| {
4645                            (0..nr).map(move |r| {
4646                                (0..k).map(|v| ((v * nr + r) * (c * k + v)) as f32).sum()
4647                            })
4648                        })
4649                        .collect::<Vec<f32>>();
4650                    assert_eq!(evaluated, expected);
4651                }
4652            }
4653        }
4654    }
4655
4656    /// Test fixture providing pre-built f32 vector and matrix constant
4657    /// expressions with sequential element values, used to evaluate and verify
4658    /// matrix operations.
4659    struct MatrixTestHelper {
4660        types: UniqueArena<Type>,
4661        expressions: Arena<Expression>,
4662        /// Vector expressions from [0, 1] to [0, 1, 2, 3].
4663        vec_exprs: FastHashMap<usize, Handle<Expression>>,
4664        /// Matrix expressions from [0, .., 3] to [0, .., 15].
4665        mat_exprs: FastHashMap<(usize, usize), Handle<Expression>>,
4666    }
4667
4668    impl MatrixTestHelper {
4669        fn new() -> Self {
4670            let mut types = UniqueArena::new();
4671            let mut expressions = Arena::new();
4672            let span = crate::Span::default();
4673
4674            let (mut vec_tys, mut mat_tys) = (FastHashMap::default(), FastHashMap::default());
4675            for c in 2..=4 {
4676                let vec_ty = types.insert(
4677                    Type {
4678                        name: None,
4679                        inner: TypeInner::Vector {
4680                            size: Self::int_to_vector_size(c),
4681                            scalar: crate::Scalar::F32,
4682                        },
4683                    },
4684                    span,
4685                );
4686                vec_tys.insert(c, vec_ty);
4687                for r in 2..=4 {
4688                    let mat_ty = types.insert(
4689                        Type {
4690                            name: None,
4691                            inner: TypeInner::Matrix {
4692                                columns: Self::int_to_vector_size(c),
4693                                rows: Self::int_to_vector_size(r),
4694                                scalar: crate::Scalar::F32,
4695                            },
4696                        },
4697                        span,
4698                    );
4699                    mat_tys.insert((c, r), mat_ty);
4700                }
4701            }
4702
4703            let mut lit_exprs = FastHashMap::default();
4704            for i in 0..16 {
4705                let expr = expressions.append(Expression::Literal(Literal::F32(i as f32)), span);
4706                lit_exprs.insert(i, expr);
4707            }
4708
4709            let mut vec_exprs = FastHashMap::default();
4710            for c in 2..=4 {
4711                let expr = expressions.append(
4712                    Expression::Compose {
4713                        ty: *vec_tys.get(&c).unwrap(),
4714                        components: (0..c)
4715                            .map(|i| *lit_exprs.get(&i).unwrap())
4716                            .collect::<Vec<_>>(),
4717                    },
4718                    span,
4719                );
4720                vec_exprs.insert(c, expr);
4721            }
4722
4723            let mut mat_exprs = FastHashMap::default();
4724            for c in 2..=4 {
4725                for r in 2..=4 {
4726                    let mut columns = Vec::with_capacity(c);
4727                    for cc in 0..c {
4728                        let start = cc * r;
4729                        let expr = expressions.append(
4730                            Expression::Compose {
4731                                ty: *vec_tys.get(&r).unwrap(),
4732                                components: (start..start + r)
4733                                    .map(|i| *lit_exprs.get(&i).unwrap())
4734                                    .collect::<Vec<_>>(),
4735                            },
4736                            span,
4737                        );
4738                        columns.push(expr);
4739                    }
4740
4741                    let expr = expressions.append(
4742                        Expression::Compose {
4743                            ty: *mat_tys.get(&(c, r)).unwrap(),
4744                            components: columns,
4745                        },
4746                        span,
4747                    );
4748                    mat_exprs.insert((c, r), expr);
4749                }
4750            }
4751
4752            Self {
4753                types,
4754                expressions,
4755                vec_exprs,
4756                mat_exprs,
4757            }
4758        }
4759
4760        /// Evaluates vec[0..nr] * mat[0..nc*nr] and returns the result as f32s.
4761        fn eval_vector_multiply_matrix(&mut self, nc: usize, nr: usize) -> Vec<f32> {
4762            let expression_kind_tracker = &mut ExpressionKindTracker::from_arena(&self.expressions);
4763            let mut solver = ConstantEvaluator {
4764                behavior: Behavior::Wgsl(WgslRestrictions::Const(None)),
4765                types: &mut self.types,
4766                constants: &Arena::new(),
4767                overrides: &Arena::new(),
4768                expressions: &mut self.expressions,
4769                expression_kind_tracker,
4770                layouter: &mut crate::proc::Layouter::default(),
4771            };
4772
4773            let result = solver
4774                .try_eval_and_append(
4775                    Expression::Binary {
4776                        op: BinaryOperator::Multiply,
4777                        left: *self.vec_exprs.get(&nr).unwrap(),
4778                        right: *self.mat_exprs.get(&(nc, nr)).unwrap(),
4779                    },
4780                    Default::default(),
4781                )
4782                .unwrap();
4783            self.flatten(result)
4784        }
4785
4786        /// Evaluates mat[0..nc*nr] * vec[0..nc] and returns the result as f32s.
4787        fn eval_matrix_multiply_vector(&mut self, nc: usize, nr: usize) -> Vec<f32> {
4788            let expression_kind_tracker = &mut ExpressionKindTracker::from_arena(&self.expressions);
4789            let mut solver = ConstantEvaluator {
4790                behavior: Behavior::Wgsl(WgslRestrictions::Const(None)),
4791                types: &mut self.types,
4792                constants: &Arena::new(),
4793                overrides: &Arena::new(),
4794                expressions: &mut self.expressions,
4795                expression_kind_tracker,
4796                layouter: &mut crate::proc::Layouter::default(),
4797            };
4798
4799            let result = solver
4800                .try_eval_and_append(
4801                    Expression::Binary {
4802                        op: BinaryOperator::Multiply,
4803                        left: *self.mat_exprs.get(&(nc, nr)).unwrap(),
4804                        right: *self.vec_exprs.get(&nc).unwrap(),
4805                    },
4806                    Default::default(),
4807                )
4808                .unwrap();
4809            self.flatten(result)
4810        }
4811
4812        /// Evaluates mat[0..k*l_nr] * mat[0..r_nc*k] and returns the result as
4813        /// f32s.
4814        fn eval_matrix_multiply_matrix(&mut self, l_nr: usize, r_nc: usize, k: usize) -> Vec<f32> {
4815            let expression_kind_tracker = &mut ExpressionKindTracker::from_arena(&self.expressions);
4816            let mut solver = ConstantEvaluator {
4817                behavior: Behavior::Wgsl(WgslRestrictions::Const(None)),
4818                types: &mut self.types,
4819                constants: &Arena::new(),
4820                overrides: &Arena::new(),
4821                expressions: &mut self.expressions,
4822                expression_kind_tracker,
4823                layouter: &mut crate::proc::Layouter::default(),
4824            };
4825
4826            let result = solver
4827                .try_eval_and_append(
4828                    Expression::Binary {
4829                        op: BinaryOperator::Multiply,
4830                        left: *self.mat_exprs.get(&(k, l_nr)).unwrap(),
4831                        right: *self.mat_exprs.get(&(r_nc, k)).unwrap(),
4832                    },
4833                    Default::default(),
4834                )
4835                .unwrap();
4836            self.flatten(result)
4837        }
4838
4839        fn flatten(&self, expr: Handle<Expression>) -> Vec<f32> {
4840            let Expression::Compose {
4841                ref components,
4842                ref ty,
4843            } = self.expressions[expr]
4844            else {
4845                unreachable!()
4846            };
4847
4848            match self.types[*ty].inner {
4849                TypeInner::Vector { .. } => components
4850                    .iter()
4851                    .map(|&comp| {
4852                        let Expression::Literal(Literal::F32(v)) = self.expressions[comp] else {
4853                            unreachable!()
4854                        };
4855                        v
4856                    })
4857                    .collect(),
4858                TypeInner::Matrix { .. } => components
4859                    .iter()
4860                    .flat_map(|&comp| self.flatten(comp))
4861                    .collect(),
4862                _ => unreachable!(),
4863            }
4864        }
4865
4866        fn int_to_vector_size(int: usize) -> VectorSize {
4867            match int {
4868                2 => VectorSize::Bi,
4869                3 => VectorSize::Tri,
4870                4 => VectorSize::Quad,
4871                _ => unreachable!(),
4872            }
4873        }
4874    }
4875
4876    #[test]
4877    fn cast() {
4878        let mut types = UniqueArena::new();
4879        let mut constants = Arena::new();
4880        let overrides = Arena::new();
4881        let mut global_expressions = Arena::new();
4882
4883        let scalar_ty = types.insert(
4884            Type {
4885                name: None,
4886                inner: TypeInner::Scalar(crate::Scalar::I32),
4887            },
4888            Default::default(),
4889        );
4890
4891        let h = constants.append(
4892            Constant {
4893                name: None,
4894                ty: scalar_ty,
4895                init: global_expressions
4896                    .append(Expression::Literal(Literal::I32(4)), Default::default()),
4897            },
4898            Default::default(),
4899        );
4900
4901        let expr = global_expressions.append(Expression::Constant(h), Default::default());
4902
4903        let root = Expression::As {
4904            expr,
4905            target: crate::Scalar::BOOL,
4906        };
4907
4908        let expression_kind_tracker = &mut ExpressionKindTracker::from_arena(&global_expressions);
4909        let mut solver = ConstantEvaluator {
4910            behavior: Behavior::Wgsl(WgslRestrictions::Const(None)),
4911            types: &mut types,
4912            constants: &constants,
4913            overrides: &overrides,
4914            expressions: &mut global_expressions,
4915            expression_kind_tracker,
4916            layouter: &mut crate::proc::Layouter::default(),
4917        };
4918
4919        let res = solver
4920            .try_eval_and_append(root, Default::default())
4921            .unwrap();
4922
4923        assert_eq!(
4924            global_expressions[res],
4925            Expression::Literal(Literal::Bool(true))
4926        );
4927    }
4928
4929    #[test]
4930    fn access() {
4931        let mut types = UniqueArena::new();
4932        let mut constants = Arena::new();
4933        let overrides = Arena::new();
4934        let mut global_expressions = Arena::new();
4935
4936        let matrix_ty = types.insert(
4937            Type {
4938                name: None,
4939                inner: TypeInner::Matrix {
4940                    columns: VectorSize::Bi,
4941                    rows: VectorSize::Tri,
4942                    scalar: crate::Scalar::F32,
4943                },
4944            },
4945            Default::default(),
4946        );
4947
4948        let vec_ty = types.insert(
4949            Type {
4950                name: None,
4951                inner: TypeInner::Vector {
4952                    size: VectorSize::Tri,
4953                    scalar: crate::Scalar::F32,
4954                },
4955            },
4956            Default::default(),
4957        );
4958
4959        let mut vec1_components = Vec::with_capacity(3);
4960        let mut vec2_components = Vec::with_capacity(3);
4961
4962        for i in 0..3 {
4963            let h = global_expressions.append(
4964                Expression::Literal(Literal::F32(i as f32)),
4965                Default::default(),
4966            );
4967
4968            vec1_components.push(h)
4969        }
4970
4971        for i in 3..6 {
4972            let h = global_expressions.append(
4973                Expression::Literal(Literal::F32(i as f32)),
4974                Default::default(),
4975            );
4976
4977            vec2_components.push(h)
4978        }
4979
4980        let vec1 = constants.append(
4981            Constant {
4982                name: None,
4983                ty: vec_ty,
4984                init: global_expressions.append(
4985                    Expression::Compose {
4986                        ty: vec_ty,
4987                        components: vec1_components,
4988                    },
4989                    Default::default(),
4990                ),
4991            },
4992            Default::default(),
4993        );
4994
4995        let vec2 = constants.append(
4996            Constant {
4997                name: None,
4998                ty: vec_ty,
4999                init: global_expressions.append(
5000                    Expression::Compose {
5001                        ty: vec_ty,
5002                        components: vec2_components,
5003                    },
5004                    Default::default(),
5005                ),
5006            },
5007            Default::default(),
5008        );
5009
5010        let h = constants.append(
5011            Constant {
5012                name: None,
5013                ty: matrix_ty,
5014                init: global_expressions.append(
5015                    Expression::Compose {
5016                        ty: matrix_ty,
5017                        components: vec![constants[vec1].init, constants[vec2].init],
5018                    },
5019                    Default::default(),
5020                ),
5021            },
5022            Default::default(),
5023        );
5024
5025        let base = global_expressions.append(Expression::Constant(h), Default::default());
5026
5027        let expression_kind_tracker = &mut ExpressionKindTracker::from_arena(&global_expressions);
5028        let mut solver = ConstantEvaluator {
5029            behavior: Behavior::Wgsl(WgslRestrictions::Const(None)),
5030            types: &mut types,
5031            constants: &constants,
5032            overrides: &overrides,
5033            expressions: &mut global_expressions,
5034            expression_kind_tracker,
5035            layouter: &mut crate::proc::Layouter::default(),
5036        };
5037
5038        let root1 = Expression::AccessIndex { base, index: 1 };
5039
5040        let res1 = solver
5041            .try_eval_and_append(root1, Default::default())
5042            .unwrap();
5043
5044        let root2 = Expression::AccessIndex {
5045            base: res1,
5046            index: 2,
5047        };
5048
5049        let res2 = solver
5050            .try_eval_and_append(root2, Default::default())
5051            .unwrap();
5052
5053        match global_expressions[res1] {
5054            Expression::Compose {
5055                ref ty,
5056                ref components,
5057            } => {
5058                assert_eq!(*ty, vec_ty);
5059                let mut components_iter = components.iter().copied();
5060                assert_eq!(
5061                    global_expressions[components_iter.next().unwrap()],
5062                    Expression::Literal(Literal::F32(3.))
5063                );
5064                assert_eq!(
5065                    global_expressions[components_iter.next().unwrap()],
5066                    Expression::Literal(Literal::F32(4.))
5067                );
5068                assert_eq!(
5069                    global_expressions[components_iter.next().unwrap()],
5070                    Expression::Literal(Literal::F32(5.))
5071                );
5072                assert!(components_iter.next().is_none());
5073            }
5074            _ => panic!("Expected vector"),
5075        }
5076
5077        assert_eq!(
5078            global_expressions[res2],
5079            Expression::Literal(Literal::F32(5.))
5080        );
5081    }
5082
5083    #[test]
5084    fn compose_of_constants() {
5085        let mut types = UniqueArena::new();
5086        let mut constants = Arena::new();
5087        let overrides = Arena::new();
5088        let mut global_expressions = Arena::new();
5089
5090        let i32_ty = types.insert(
5091            Type {
5092                name: None,
5093                inner: TypeInner::Scalar(crate::Scalar::I32),
5094            },
5095            Default::default(),
5096        );
5097
5098        let vec2_i32_ty = types.insert(
5099            Type {
5100                name: None,
5101                inner: TypeInner::Vector {
5102                    size: VectorSize::Bi,
5103                    scalar: crate::Scalar::I32,
5104                },
5105            },
5106            Default::default(),
5107        );
5108
5109        let h = constants.append(
5110            Constant {
5111                name: None,
5112                ty: i32_ty,
5113                init: global_expressions
5114                    .append(Expression::Literal(Literal::I32(4)), Default::default()),
5115            },
5116            Default::default(),
5117        );
5118
5119        let h_expr = global_expressions.append(Expression::Constant(h), Default::default());
5120
5121        let expression_kind_tracker = &mut ExpressionKindTracker::from_arena(&global_expressions);
5122        let mut solver = ConstantEvaluator {
5123            behavior: Behavior::Wgsl(WgslRestrictions::Const(None)),
5124            types: &mut types,
5125            constants: &constants,
5126            overrides: &overrides,
5127            expressions: &mut global_expressions,
5128            expression_kind_tracker,
5129            layouter: &mut crate::proc::Layouter::default(),
5130        };
5131
5132        let solved_compose = solver
5133            .try_eval_and_append(
5134                Expression::Compose {
5135                    ty: vec2_i32_ty,
5136                    components: vec![h_expr, h_expr],
5137                },
5138                Default::default(),
5139            )
5140            .unwrap();
5141        let solved_negate = solver
5142            .try_eval_and_append(
5143                Expression::Unary {
5144                    op: UnaryOperator::Negate,
5145                    expr: solved_compose,
5146                },
5147                Default::default(),
5148            )
5149            .unwrap();
5150
5151        let pass = match global_expressions[solved_negate] {
5152            Expression::Compose { ty, ref components } => {
5153                ty == vec2_i32_ty
5154                    && components.iter().all(|&component| {
5155                        let component = &global_expressions[component];
5156                        matches!(*component, Expression::Literal(Literal::I32(-4)))
5157                    })
5158            }
5159            _ => false,
5160        };
5161        if !pass {
5162            panic!("unexpected evaluation result")
5163        }
5164    }
5165
5166    #[test]
5167    fn splat_of_constant() {
5168        let mut types = UniqueArena::new();
5169        let mut constants = Arena::new();
5170        let overrides = Arena::new();
5171        let mut global_expressions = Arena::new();
5172
5173        let i32_ty = types.insert(
5174            Type {
5175                name: None,
5176                inner: TypeInner::Scalar(crate::Scalar::I32),
5177            },
5178            Default::default(),
5179        );
5180
5181        let vec2_i32_ty = types.insert(
5182            Type {
5183                name: None,
5184                inner: TypeInner::Vector {
5185                    size: VectorSize::Bi,
5186                    scalar: crate::Scalar::I32,
5187                },
5188            },
5189            Default::default(),
5190        );
5191
5192        let h = constants.append(
5193            Constant {
5194                name: None,
5195                ty: i32_ty,
5196                init: global_expressions
5197                    .append(Expression::Literal(Literal::I32(4)), Default::default()),
5198            },
5199            Default::default(),
5200        );
5201
5202        let h_expr = global_expressions.append(Expression::Constant(h), Default::default());
5203
5204        let expression_kind_tracker = &mut ExpressionKindTracker::from_arena(&global_expressions);
5205        let mut solver = ConstantEvaluator {
5206            behavior: Behavior::Wgsl(WgslRestrictions::Const(None)),
5207            types: &mut types,
5208            constants: &constants,
5209            overrides: &overrides,
5210            expressions: &mut global_expressions,
5211            expression_kind_tracker,
5212            layouter: &mut crate::proc::Layouter::default(),
5213        };
5214
5215        let solved_compose = solver
5216            .try_eval_and_append(
5217                Expression::Splat {
5218                    size: VectorSize::Bi,
5219                    value: h_expr,
5220                },
5221                Default::default(),
5222            )
5223            .unwrap();
5224        let solved_negate = solver
5225            .try_eval_and_append(
5226                Expression::Unary {
5227                    op: UnaryOperator::Negate,
5228                    expr: solved_compose,
5229                },
5230                Default::default(),
5231            )
5232            .unwrap();
5233
5234        let pass = match global_expressions[solved_negate] {
5235            Expression::Compose { ty, ref components } => {
5236                ty == vec2_i32_ty
5237                    && components.iter().all(|&component| {
5238                        let component = &global_expressions[component];
5239                        matches!(*component, Expression::Literal(Literal::I32(-4)))
5240                    })
5241            }
5242            _ => false,
5243        };
5244        if !pass {
5245            panic!("unexpected evaluation result")
5246        }
5247    }
5248
5249    #[test]
5250    fn splat_of_zero_value() {
5251        let mut types = UniqueArena::new();
5252        let constants = Arena::new();
5253        let overrides = Arena::new();
5254        let mut global_expressions = Arena::new();
5255
5256        let f32_ty = types.insert(
5257            Type {
5258                name: None,
5259                inner: TypeInner::Scalar(crate::Scalar::F32),
5260            },
5261            Default::default(),
5262        );
5263
5264        let vec2_f32_ty = types.insert(
5265            Type {
5266                name: None,
5267                inner: TypeInner::Vector {
5268                    size: VectorSize::Bi,
5269                    scalar: crate::Scalar::F32,
5270                },
5271            },
5272            Default::default(),
5273        );
5274
5275        let five =
5276            global_expressions.append(Expression::Literal(Literal::F32(5.0)), Default::default());
5277        let five_splat = global_expressions.append(
5278            Expression::Splat {
5279                size: VectorSize::Bi,
5280                value: five,
5281            },
5282            Default::default(),
5283        );
5284        let zero = global_expressions.append(Expression::ZeroValue(f32_ty), Default::default());
5285        let zero_splat = global_expressions.append(
5286            Expression::Splat {
5287                size: VectorSize::Bi,
5288                value: zero,
5289            },
5290            Default::default(),
5291        );
5292
5293        let expression_kind_tracker = &mut ExpressionKindTracker::from_arena(&global_expressions);
5294        let mut solver = ConstantEvaluator {
5295            behavior: Behavior::Wgsl(WgslRestrictions::Const(None)),
5296            types: &mut types,
5297            constants: &constants,
5298            overrides: &overrides,
5299            expressions: &mut global_expressions,
5300            expression_kind_tracker,
5301            layouter: &mut crate::proc::Layouter::default(),
5302        };
5303
5304        let solved_add = solver
5305            .try_eval_and_append(
5306                Expression::Binary {
5307                    op: BinaryOperator::Add,
5308                    left: zero_splat,
5309                    right: five_splat,
5310                },
5311                Default::default(),
5312            )
5313            .unwrap();
5314
5315        let pass = match global_expressions[solved_add] {
5316            Expression::Compose { ty, ref components } => {
5317                ty == vec2_f32_ty
5318                    && components.iter().all(|&component| {
5319                        let component = &global_expressions[component];
5320                        matches!(*component, Expression::Literal(Literal::F32(5.0)))
5321                    })
5322            }
5323            _ => false,
5324        };
5325        if !pass {
5326            panic!("unexpected evaluation result")
5327        }
5328    }
5329}