Skip to main content

naga/valid/
handles.rs

1//! Implementation of `Validator::validate_module_handles`.
2
3use alloc::boxed::Box;
4use core::{convert::TryInto, hash::Hash};
5
6use super::{TypeError, ValidationError};
7use crate::non_max_u32::NonMaxU32;
8use crate::{
9    arena::{BadHandle, BadRangeError},
10    diagnostic_filter::DiagnosticFilterNode,
11    EntryPoint, Handle,
12};
13use crate::{Arena, UniqueArena};
14
15use alloc::string::ToString;
16
17impl super::Validator {
18    /// Validates that all handles within `module` are:
19    ///
20    /// * Valid, in the sense that they contain indices within each arena structure inside the
21    ///   [`crate::Module`] type.
22    /// * No arena contents contain any items that have forward dependencies; that is, the value
23    ///   associated with a handle only may contain references to handles in the same arena that
24    ///   were constructed before it.
25    ///
26    /// By validating the above conditions, we free up subsequent logic to assume that handle
27    /// accesses are infallible.
28    ///
29    /// # Errors
30    ///
31    /// Errors returned by this method are intentionally sparse, for simplicity of implementation.
32    /// It is expected that only buggy frontends or fuzzers should ever emit IR that fails this
33    /// validation pass.
34    pub(super) fn validate_module_handles(
35        module: &crate::Module,
36    ) -> Result<(), Box<ValidationError>> {
37        let &crate::Module {
38            ref constants,
39            ref overrides,
40            ref entry_points,
41            ref functions,
42            ref global_variables,
43            ref types,
44            ref special_types,
45            ref global_expressions,
46            ref diagnostic_filters,
47            ref diagnostic_filter_leaf,
48            ref doc_comments,
49        } = module;
50
51        // Because types can refer to global expressions and vice versa, to
52        // ensure the overall structure is free of cycles, we must traverse them
53        // both in tandem.
54        //
55        // Try to visit all types and global expressions in an order such that
56        // each item refers only to previously visited items. If we succeed,
57        // that shows that there cannot be any cycles, since walking any edge
58        // advances you towards the beginning of the visiting order.
59        //
60        // Validate all the handles in types and expressions as we traverse the
61        // arenas.
62        let mut global_exprs_iter = global_expressions.iter().peekable();
63        for (th, t) in types.iter() {
64            // Imagine the `for` loop and `global_exprs_iter` as two fingers
65            // walking the type and global expression arenas. They don't visit
66            // elements at the same rate: sometimes one processes a bunch of
67            // elements while the other one stays still. But at each point, they
68            // check that the two ranges of elements they've visited only refer
69            // to other elements in those ranges.
70            //
71            // For brevity, we'll say 'handles behind `global_exprs_iter`' to
72            // mean handles that have already been produced by
73            // `global_exprs_iter`. Once `global_exprs_iter` returns `None`, all
74            // global expression handles are 'behind' it.
75            //
76            // At this point:
77            //
78            // - All types visited by prior iterations (that is, before
79            //   `th`/`t`) refer only to expressions behind `global_exprs_iter`.
80            //
81            //   On the first iteration, this is obviously true: there are no
82            //   prior iterations, and `global_exprs_iter` hasn't produced
83            //   anything yet. At the bottom of the loop, we'll claim that it's
84            //   true for `th`/`t` as well, so the condition remains true when
85            //   we advance to the next type.
86            //
87            // - All expressions behind `global_exprs_iter` refer only to
88            //   previously visited types.
89            //
90            //   Again, trivially true at the start, and we'll show it's true
91            //   about each expression that `global_exprs_iter` produces.
92            //
93            // Once we also check that arena elements only refer to prior
94            // elements in that arena, we can see that `th`/`t` does not
95            // participate in a cycle: it only refers to previously visited
96            // types and expressions behind `global_exprs_iter`, and none of
97            // those refer to `th`/`t`, because they passed the same checks
98            // before we reached `th`/`t`.
99            if let Some(max_expr) = Self::validate_type_handles((th, t), overrides)? {
100                max_expr.check_valid_for(global_expressions)?;
101                // Since `t` refers to `max_expr`, if we want our invariants to
102                // remain true, we must advance `global_exprs_iter` beyond
103                // `max_expr`.
104                while let Some((eh, e)) = global_exprs_iter.next_if(|&(eh, _)| eh <= max_expr) {
105                    if let Some(max_type) =
106                        Self::validate_const_expression_handles((eh, e), constants, overrides)?
107                    {
108                        // Show that `eh` refers only to previously visited types.
109                        th.check_dep(max_type)?;
110                    }
111                    // We've advanced `global_exprs_iter` past `eh` already. But
112                    // since we now know that `eh` refers only to previously
113                    // visited types, it is again true that all expressions
114                    // behind `global_exprs_iter` refer only to previously
115                    // visited types. So we can continue to the next expression.
116                }
117            }
118
119            // Here we know that if `th` refers to any expressions at all,
120            // `max_expr` is the latest one. And we know that `max_expr` is
121            // behind `global_exprs_iter`. So `th` refers only to expressions
122            // behind `global_exprs_iter`, and the invariants will still be
123            // true on the next iteration.
124        }
125
126        // Since we also enforced the usual intra-arena rules that expressions
127        // refer only to prior expressions, expressions can only form cycles if
128        // they include types. But we've shown that all types are acyclic, so
129        // all expressions must be acyclic as well.
130        //
131        // Validate the remaining expressions normally.
132        for handle_and_expr in global_exprs_iter {
133            Self::validate_const_expression_handles(handle_and_expr, constants, overrides)?;
134        }
135
136        let validate_type = |handle| Self::validate_type_handle(handle, types);
137        let validate_const_expr =
138            |handle| Self::validate_expression_handle(handle, global_expressions);
139
140        for (_handle, constant) in constants.iter() {
141            let &crate::Constant { name: _, ty, init } = constant;
142            validate_type(ty)?;
143            validate_const_expr(init)?;
144        }
145
146        for (_handle, r#override) in overrides.iter() {
147            let &crate::Override {
148                name: _,
149                id: _,
150                ty,
151                init,
152            } = r#override;
153            validate_type(ty)?;
154            if let Some(init_expr) = init {
155                validate_const_expr(init_expr)?;
156            }
157        }
158
159        for (_handle, global_variable) in global_variables.iter() {
160            let &crate::GlobalVariable {
161                name: _,
162                space: _,
163                binding: _,
164                ty,
165                init,
166                memory_decorations: _,
167            } = global_variable;
168            validate_type(ty)?;
169            if let Some(init_expr) = init {
170                validate_const_expr(init_expr)?;
171            }
172        }
173
174        let validate_function = |function_handle, function: &_| -> Result<_, InvalidHandleError> {
175            let &crate::Function {
176                name: _,
177                ref arguments,
178                ref result,
179                ref local_variables,
180                ref expressions,
181                ref named_expressions,
182                ref body,
183                ref diagnostic_filter_leaf,
184            } = function;
185
186            for arg in arguments.iter() {
187                let &crate::FunctionArgument {
188                    name: _,
189                    ty,
190                    binding: _,
191                } = arg;
192                validate_type(ty)?;
193            }
194
195            if let &Some(crate::FunctionResult { ty, binding: _ }) = result {
196                validate_type(ty)?;
197            }
198
199            for (_handle, local_variable) in local_variables.iter() {
200                let &crate::LocalVariable { name: _, ty, init } = local_variable;
201                validate_type(ty)?;
202                if let Some(init) = init {
203                    Self::validate_expression_handle(init, expressions)?;
204                }
205            }
206
207            for handle in named_expressions.keys().copied() {
208                Self::validate_expression_handle(handle, expressions)?;
209            }
210
211            for handle_and_expr in expressions.iter() {
212                Self::validate_expression_handles(
213                    handle_and_expr,
214                    constants,
215                    overrides,
216                    types,
217                    local_variables,
218                    global_variables,
219                    functions,
220                    function_handle,
221                )?;
222            }
223
224            Self::validate_block_handles(body, expressions, functions)?;
225
226            if let Some(handle) = *diagnostic_filter_leaf {
227                handle.check_valid_for(diagnostic_filters)?;
228            }
229
230            Ok(())
231        };
232
233        for entry_point in entry_points.iter() {
234            validate_function(None, &entry_point.function)?;
235            if let Some(sizes) = entry_point.workgroup_size_overrides {
236                for size in sizes.iter().filter_map(|x| *x) {
237                    validate_const_expr(size)?;
238                }
239            }
240            if let Some(task_payload) = entry_point.task_payload {
241                Self::validate_global_variable_handle(task_payload, global_variables)?;
242            }
243            if let Some(ref mesh_info) = entry_point.mesh_info {
244                Self::validate_global_variable_handle(mesh_info.output_variable, global_variables)?;
245                validate_type(mesh_info.vertex_output_type)?;
246                validate_type(mesh_info.primitive_output_type)?;
247                for ov in mesh_info
248                    .max_vertices_override
249                    .iter()
250                    .chain(mesh_info.max_primitives_override.iter())
251                {
252                    validate_const_expr(*ov)?;
253                }
254            }
255        }
256
257        for (function_handle, function) in functions.iter() {
258            validate_function(Some(function_handle), function)?;
259        }
260
261        if let Some(ty) = special_types.ray_desc {
262            validate_type(ty)?;
263        }
264        if let Some(ty) = special_types.ray_intersection {
265            validate_type(ty)?;
266        }
267        if let Some(ty) = special_types.ray_vertex_return {
268            validate_type(ty)?;
269        }
270
271        for (handle, _node) in diagnostic_filters.iter() {
272            let DiagnosticFilterNode { inner: _, parent } = diagnostic_filters[handle];
273            handle.check_dep_opt(parent)?;
274        }
275        if let Some(handle) = *diagnostic_filter_leaf {
276            handle.check_valid_for(diagnostic_filters)?;
277        }
278
279        if let Some(doc_comments) = doc_comments.as_ref() {
280            let crate::DocComments {
281                module: _,
282                types: ref doc_comments_for_types,
283                struct_members: ref doc_comments_for_struct_members,
284                entry_points: ref doc_comments_for_entry_points,
285                functions: ref doc_comments_for_functions,
286                constants: ref doc_comments_for_constants,
287                global_variables: ref doc_comments_for_global_variables,
288            } = **doc_comments;
289
290            for (&ty, _) in doc_comments_for_types.iter() {
291                validate_type(ty)?;
292            }
293
294            for (&(ty, struct_member_index), _) in doc_comments_for_struct_members.iter() {
295                validate_type(ty)?;
296                let struct_type = types.get_handle(ty).unwrap();
297                match struct_type.inner {
298                    crate::TypeInner::Struct {
299                        ref members,
300                        span: ref _span,
301                    } => {
302                        (0..members.len())
303                            .contains(&struct_member_index)
304                            .then_some(())
305                            // TODO: what errors should this be?
306                            .ok_or_else(|| ValidationError::Type {
307                                handle: ty,
308                                name: struct_type.name.as_ref().map_or_else(
309                                    || "members length incorrect".to_string(),
310                                    |name| name.to_string(),
311                                ),
312                                source: TypeError::InvalidData(ty),
313                            })?;
314                    }
315                    _ => {
316                        // TODO: internal error ? We should never get here.
317                        // If entering there, it's probably that we forgot to adjust a handle in the compact phase.
318                        return Err(Box::new(ValidationError::Type {
319                            handle: ty,
320                            name: struct_type
321                                .name
322                                .as_ref()
323                                .map_or_else(|| "Unknown".to_string(), |name| name.to_string()),
324                            source: TypeError::InvalidData(ty),
325                        }));
326                    }
327                }
328                for (&function, _) in doc_comments_for_functions.iter() {
329                    Self::validate_function_handle(function, functions)?;
330                }
331                for (&entry_point_index, _) in doc_comments_for_entry_points.iter() {
332                    Self::validate_entry_point_index(entry_point_index, entry_points)?;
333                }
334                for (&constant, _) in doc_comments_for_constants.iter() {
335                    Self::validate_constant_handle(constant, constants)?;
336                }
337                for (&global_variable, _) in doc_comments_for_global_variables.iter() {
338                    Self::validate_global_variable_handle(global_variable, global_variables)?;
339                }
340            }
341        }
342
343        Ok(())
344    }
345
346    fn validate_type_handle(
347        handle: Handle<crate::Type>,
348        types: &UniqueArena<crate::Type>,
349    ) -> Result<(), InvalidHandleError> {
350        handle.check_valid_for_uniq(types).map(|_| ())
351    }
352
353    fn validate_constant_handle(
354        handle: Handle<crate::Constant>,
355        constants: &Arena<crate::Constant>,
356    ) -> Result<(), InvalidHandleError> {
357        handle.check_valid_for(constants).map(|_| ())
358    }
359
360    fn validate_global_variable_handle(
361        handle: Handle<crate::GlobalVariable>,
362        global_variables: &Arena<crate::GlobalVariable>,
363    ) -> Result<(), InvalidHandleError> {
364        handle.check_valid_for(global_variables).map(|_| ())
365    }
366
367    fn validate_override_handle(
368        handle: Handle<crate::Override>,
369        overrides: &Arena<crate::Override>,
370    ) -> Result<(), InvalidHandleError> {
371        handle.check_valid_for(overrides).map(|_| ())
372    }
373
374    fn validate_expression_handle(
375        handle: Handle<crate::Expression>,
376        expressions: &Arena<crate::Expression>,
377    ) -> Result<(), InvalidHandleError> {
378        handle.check_valid_for(expressions).map(|_| ())
379    }
380
381    fn validate_function_handle(
382        handle: Handle<crate::Function>,
383        functions: &Arena<crate::Function>,
384    ) -> Result<(), InvalidHandleError> {
385        handle.check_valid_for(functions).map(|_| ())
386    }
387
388    /// Validate all handles that occur in `ty`, whose handle is `handle`.
389    ///
390    /// If `ty` refers to any expressions, return the highest-indexed expression
391    /// handle that it uses. This is used for detecting cycles between the
392    /// expression and type arenas.
393    fn validate_type_handles(
394        (handle, ty): (Handle<crate::Type>, &crate::Type),
395        overrides: &Arena<crate::Override>,
396    ) -> Result<Option<Handle<crate::Expression>>, InvalidHandleError> {
397        let max_expr = match ty.inner {
398            crate::TypeInner::Scalar { .. }
399            | crate::TypeInner::Vector { .. }
400            | crate::TypeInner::Matrix { .. }
401            | crate::TypeInner::CooperativeMatrix { .. }
402            | crate::TypeInner::ValuePointer { .. }
403            | crate::TypeInner::Atomic { .. }
404            | crate::TypeInner::Image { .. }
405            | crate::TypeInner::Sampler { .. }
406            | crate::TypeInner::AccelerationStructure { .. }
407            | crate::TypeInner::RayQuery { .. }
408            | crate::TypeInner::HitObject => None,
409            crate::TypeInner::Pointer { base, space: _ } => {
410                handle.check_dep(base)?;
411                None
412            }
413            crate::TypeInner::Array { base, size, .. }
414            | crate::TypeInner::BindingArray { base, size, .. } => {
415                handle.check_dep(base)?;
416                match size {
417                    crate::ArraySize::Pending(h) => {
418                        Self::validate_override_handle(h, overrides)?;
419                        let r#override = &overrides[h];
420                        handle.check_dep(r#override.ty)?;
421                        r#override.init
422                    }
423                    crate::ArraySize::Constant(_) | crate::ArraySize::Dynamic => None,
424                }
425            }
426            crate::TypeInner::Struct {
427                ref members,
428                span: _,
429            } => {
430                handle.check_dep_iter(members.iter().map(|m| m.ty))?;
431                None
432            }
433        };
434
435        Ok(max_expr)
436    }
437
438    fn validate_entry_point_index(
439        entry_point_index: usize,
440        entry_points: &[EntryPoint],
441    ) -> Result<(), InvalidHandleError> {
442        (0..entry_points.len())
443            .contains(&entry_point_index)
444            .then_some(())
445            .ok_or_else(|| {
446                BadHandle {
447                    kind: "EntryPoint",
448                    index: entry_point_index,
449                }
450                .into()
451            })
452    }
453
454    /// Validate all handles that occur in `expression`, whose handle is `handle`.
455    ///
456    /// If `expression` refers to any `Type`s, return the highest-indexed type
457    /// handle that it uses. This is used for detecting cycles between the
458    /// expression and type arenas.
459    fn validate_const_expression_handles(
460        (handle, expression): (Handle<crate::Expression>, &crate::Expression),
461        constants: &Arena<crate::Constant>,
462        overrides: &Arena<crate::Override>,
463    ) -> Result<Option<Handle<crate::Type>>, InvalidHandleError> {
464        let validate_constant = |handle| Self::validate_constant_handle(handle, constants);
465        let validate_override = |handle| Self::validate_override_handle(handle, overrides);
466
467        let max_type = match *expression {
468            crate::Expression::Literal(_) => None,
469            crate::Expression::Constant(constant) => {
470                validate_constant(constant)?;
471                handle.check_dep(constants[constant].init)?;
472                None
473            }
474            crate::Expression::Override(r#override) => {
475                validate_override(r#override)?;
476                if let Some(init) = overrides[r#override].init {
477                    handle.check_dep(init)?;
478                }
479                None
480            }
481            crate::Expression::ZeroValue(ty) => Some(ty),
482            crate::Expression::Compose { ty, ref components } => {
483                handle.check_dep_iter(components.iter().copied())?;
484                Some(ty)
485            }
486            crate::Expression::Bitcast { expr, ty } => {
487                handle.check_dep(expr)?;
488                Some(ty)
489            }
490            _ => None,
491        };
492        Ok(max_type)
493    }
494
495    #[allow(clippy::too_many_arguments)]
496    fn validate_expression_handles(
497        (handle, expression): (Handle<crate::Expression>, &crate::Expression),
498        constants: &Arena<crate::Constant>,
499        overrides: &Arena<crate::Override>,
500        types: &UniqueArena<crate::Type>,
501        local_variables: &Arena<crate::LocalVariable>,
502        global_variables: &Arena<crate::GlobalVariable>,
503        functions: &Arena<crate::Function>,
504        // The handle of the current function or `None` if it's an entry point
505        current_function: Option<Handle<crate::Function>>,
506    ) -> Result<(), InvalidHandleError> {
507        let validate_constant = |handle| Self::validate_constant_handle(handle, constants);
508        let validate_override = |handle| Self::validate_override_handle(handle, overrides);
509        let validate_type = |handle| Self::validate_type_handle(handle, types);
510
511        match *expression {
512            crate::Expression::Access { base, index } => {
513                handle.check_dep(base)?.check_dep(index)?;
514            }
515            crate::Expression::AccessIndex { base, .. } => {
516                handle.check_dep(base)?;
517            }
518            crate::Expression::Splat { value, .. } => {
519                handle.check_dep(value)?;
520            }
521            crate::Expression::Swizzle { vector, .. } => {
522                handle.check_dep(vector)?;
523            }
524            crate::Expression::Literal(_) => {}
525            crate::Expression::Constant(constant) => {
526                validate_constant(constant)?;
527            }
528            crate::Expression::Override(r#override) => {
529                validate_override(r#override)?;
530            }
531            crate::Expression::ZeroValue(ty) => {
532                validate_type(ty)?;
533            }
534            crate::Expression::Compose { ty, ref components } => {
535                validate_type(ty)?;
536                handle.check_dep_iter(components.iter().copied())?;
537            }
538            crate::Expression::FunctionArgument(_arg_idx) => (),
539            crate::Expression::GlobalVariable(global_variable) => {
540                global_variable.check_valid_for(global_variables)?;
541            }
542            crate::Expression::LocalVariable(local_variable) => {
543                local_variable.check_valid_for(local_variables)?;
544            }
545            crate::Expression::Load { pointer } => {
546                handle.check_dep(pointer)?;
547            }
548            crate::Expression::ImageSample {
549                image,
550                sampler,
551                gather: _,
552                coordinate,
553                array_index,
554                offset,
555                level,
556                depth_ref,
557                clamp_to_edge: _,
558            } => {
559                handle
560                    .check_dep(image)?
561                    .check_dep(sampler)?
562                    .check_dep(coordinate)?
563                    .check_dep_opt(array_index)?
564                    .check_dep_opt(offset)?;
565
566                match level {
567                    crate::SampleLevel::Auto | crate::SampleLevel::Zero => (),
568                    crate::SampleLevel::Exact(expr) => {
569                        handle.check_dep(expr)?;
570                    }
571                    crate::SampleLevel::Bias(expr) => {
572                        handle.check_dep(expr)?;
573                    }
574                    crate::SampleLevel::Gradient { x, y } => {
575                        handle.check_dep(x)?.check_dep(y)?;
576                    }
577                };
578
579                handle.check_dep_opt(depth_ref)?;
580            }
581            crate::Expression::ImageLoad {
582                image,
583                coordinate,
584                array_index,
585                sample,
586                level,
587            } => {
588                handle
589                    .check_dep(image)?
590                    .check_dep(coordinate)?
591                    .check_dep_opt(array_index)?
592                    .check_dep_opt(sample)?
593                    .check_dep_opt(level)?;
594            }
595            crate::Expression::ImageQuery { image, query } => {
596                handle.check_dep(image)?;
597                match query {
598                    crate::ImageQuery::Size { level } => {
599                        handle.check_dep_opt(level)?;
600                    }
601                    crate::ImageQuery::NumLevels
602                    | crate::ImageQuery::NumLayers
603                    | crate::ImageQuery::NumSamples => (),
604                };
605            }
606            crate::Expression::Unary {
607                op: _,
608                expr: operand,
609            } => {
610                handle.check_dep(operand)?;
611            }
612            crate::Expression::Binary { op: _, left, right } => {
613                handle.check_dep(left)?.check_dep(right)?;
614            }
615            crate::Expression::Select {
616                condition,
617                accept,
618                reject,
619            } => {
620                handle
621                    .check_dep(condition)?
622                    .check_dep(accept)?
623                    .check_dep(reject)?;
624            }
625            crate::Expression::Derivative { expr: argument, .. } => {
626                handle.check_dep(argument)?;
627            }
628            crate::Expression::Relational { fun: _, argument } => {
629                handle.check_dep(argument)?;
630            }
631            crate::Expression::Math {
632                fun: _,
633                arg,
634                arg1,
635                arg2,
636                arg3,
637            } => {
638                handle
639                    .check_dep(arg)?
640                    .check_dep_opt(arg1)?
641                    .check_dep_opt(arg2)?
642                    .check_dep_opt(arg3)?;
643            }
644            crate::Expression::As {
645                expr: input,
646                target: _,
647            } => {
648                handle.check_dep(input)?;
649            }
650            crate::Expression::Bitcast { expr: input, ty } => {
651                validate_type(ty)?;
652                handle.check_dep(input)?;
653            }
654            crate::Expression::CallResult(function) => {
655                Self::validate_function_handle(function, functions)?;
656                if let Some(handle) = current_function {
657                    handle.check_dep(function)?;
658                }
659            }
660            crate::Expression::AtomicResult { .. }
661            | crate::Expression::RayQueryProceedResult
662            | crate::Expression::SubgroupBallotResult
663            | crate::Expression::SubgroupOperationResult { .. }
664            | crate::Expression::WorkGroupUniformLoadResult { .. } => (),
665            crate::Expression::ArrayLength(array) => {
666                handle.check_dep(array)?;
667            }
668            crate::Expression::RayQueryGetIntersection {
669                query,
670                committed: _,
671            }
672            | crate::Expression::RayQueryVertexPositions {
673                query,
674                committed: _,
675            } => {
676                handle.check_dep(query)?;
677            }
678            crate::Expression::HitObjectQuery {
679                hit_object,
680                query: _,
681            } => {
682                handle.check_dep(hit_object)?;
683            }
684            crate::Expression::CooperativeLoad { ref data, .. } => {
685                handle.check_dep(data.pointer)?.check_dep(data.stride)?;
686            }
687            crate::Expression::CooperativeMultiplyAdd { a, b, c } => {
688                handle.check_dep(a)?.check_dep(b)?.check_dep(c)?;
689            }
690        }
691        Ok(())
692    }
693
694    fn validate_block_handles(
695        block: &crate::Block,
696        expressions: &Arena<crate::Expression>,
697        functions: &Arena<crate::Function>,
698    ) -> Result<(), InvalidHandleError> {
699        let validate_block = |block| Self::validate_block_handles(block, expressions, functions);
700        let validate_expr = |handle| Self::validate_expression_handle(handle, expressions);
701        let validate_expr_opt = |handle_opt| {
702            if let Some(handle) = handle_opt {
703                validate_expr(handle)?;
704            }
705            Ok(())
706        };
707        let validate_reorder_hint =
708            |hint: Option<crate::ReorderHint>| -> Result<(), InvalidHandleError> {
709                if let Some(crate::ReorderHint { hint, bits }) = hint {
710                    validate_expr(hint)?;
711                    validate_expr(bits)?;
712                }
713                Ok(())
714            };
715
716        block.iter().try_for_each(|stmt| match *stmt {
717            crate::Statement::Emit(ref expr_range) => {
718                expr_range.check_valid_for(expressions)?;
719                Ok(())
720            }
721            crate::Statement::Block(ref block) => {
722                validate_block(block)?;
723                Ok(())
724            }
725            crate::Statement::If {
726                condition,
727                ref accept,
728                ref reject,
729            } => {
730                validate_expr(condition)?;
731                validate_block(accept)?;
732                validate_block(reject)?;
733                Ok(())
734            }
735            crate::Statement::Switch {
736                selector,
737                ref cases,
738            } => {
739                validate_expr(selector)?;
740                for &crate::SwitchCase {
741                    value: _,
742                    ref body,
743                    fall_through: _,
744                } in cases
745                {
746                    validate_block(body)?;
747                }
748                Ok(())
749            }
750            crate::Statement::Loop {
751                ref body,
752                ref continuing,
753                break_if,
754            } => {
755                validate_block(body)?;
756                validate_block(continuing)?;
757                validate_expr_opt(break_if)?;
758                Ok(())
759            }
760            crate::Statement::Return { value } => validate_expr_opt(value),
761            crate::Statement::Store { pointer, value } => {
762                validate_expr(pointer)?;
763                validate_expr(value)?;
764                Ok(())
765            }
766            crate::Statement::ImageStore {
767                image,
768                coordinate,
769                array_index,
770                value,
771            } => {
772                validate_expr(image)?;
773                validate_expr(coordinate)?;
774                validate_expr_opt(array_index)?;
775                validate_expr(value)?;
776                Ok(())
777            }
778            crate::Statement::Atomic {
779                pointer,
780                fun,
781                value,
782                result,
783            } => {
784                validate_expr(pointer)?;
785                match fun {
786                    crate::AtomicFunction::Add
787                    | crate::AtomicFunction::Subtract
788                    | crate::AtomicFunction::And
789                    | crate::AtomicFunction::ExclusiveOr
790                    | crate::AtomicFunction::InclusiveOr
791                    | crate::AtomicFunction::Min
792                    | crate::AtomicFunction::Max => (),
793                    crate::AtomicFunction::Exchange { compare } => validate_expr_opt(compare)?,
794                };
795                validate_expr(value)?;
796                if let Some(result) = result {
797                    validate_expr(result)?;
798                }
799                Ok(())
800            }
801            crate::Statement::ImageAtomic {
802                image,
803                coordinate,
804                array_index,
805                fun: _,
806                value,
807            } => {
808                validate_expr(image)?;
809                validate_expr(coordinate)?;
810                validate_expr_opt(array_index)?;
811                validate_expr(value)?;
812                Ok(())
813            }
814            crate::Statement::WorkGroupUniformLoad { pointer, result } => {
815                validate_expr(pointer)?;
816                validate_expr(result)?;
817                Ok(())
818            }
819            crate::Statement::Call {
820                function,
821                ref arguments,
822                result,
823            } => {
824                Self::validate_function_handle(function, functions)?;
825                for arg in arguments.iter().copied() {
826                    validate_expr(arg)?;
827                }
828                validate_expr_opt(result)?;
829                Ok(())
830            }
831            crate::Statement::RayQuery { query, ref fun } => {
832                validate_expr(query)?;
833                match *fun {
834                    crate::RayQueryFunction::Initialize {
835                        acceleration_structure,
836                        descriptor,
837                    } => {
838                        validate_expr(acceleration_structure)?;
839                        validate_expr(descriptor)?;
840                    }
841                    crate::RayQueryFunction::Proceed { result } => {
842                        validate_expr(result)?;
843                    }
844                    crate::RayQueryFunction::GenerateIntersection { hit_t } => {
845                        validate_expr(hit_t)?;
846                    }
847                    crate::RayQueryFunction::ConfirmIntersection => {}
848                    crate::RayQueryFunction::Terminate => {}
849                    crate::RayQueryFunction::Begin => {}
850                }
851                Ok(())
852            }
853            crate::Statement::SubgroupBallot { result, predicate } => {
854                validate_expr_opt(predicate)?;
855                validate_expr(result)?;
856                Ok(())
857            }
858            crate::Statement::SubgroupCollectiveOperation {
859                op: _,
860                collective_op: _,
861                argument,
862                result,
863            } => {
864                validate_expr(argument)?;
865                validate_expr(result)?;
866                Ok(())
867            }
868            crate::Statement::SubgroupGather {
869                mode,
870                argument,
871                result,
872            } => {
873                validate_expr(argument)?;
874                match mode {
875                    crate::GatherMode::BroadcastFirst => {}
876                    crate::GatherMode::Broadcast(index)
877                    | crate::GatherMode::Shuffle(index)
878                    | crate::GatherMode::ShuffleDown(index)
879                    | crate::GatherMode::ShuffleUp(index)
880                    | crate::GatherMode::ShuffleXor(index)
881                    | crate::GatherMode::QuadBroadcast(index) => validate_expr(index)?,
882                    crate::GatherMode::QuadSwap(_) => {}
883                }
884                validate_expr(result)?;
885                Ok(())
886            }
887            crate::Statement::SubgroupBallotFindBit {
888                order: _,
889                argument,
890                result,
891            } => {
892                validate_expr(argument)?;
893                validate_expr(result)?;
894                Ok(())
895            }
896            crate::Statement::CooperativeStore { target, ref data } => {
897                validate_expr(target)?;
898                validate_expr(data.pointer)?;
899                validate_expr(data.stride)?;
900                Ok(())
901            }
902            crate::Statement::RayPipelineFunction(fun) => match fun {
903                crate::RayPipelineFunction::TraceRay {
904                    acceleration_structure,
905                    descriptor,
906                    payload,
907                } => {
908                    validate_expr(acceleration_structure)?;
909                    validate_expr(descriptor)?;
910                    validate_expr(payload)?;
911                    Ok(())
912                }
913                crate::RayPipelineFunction::ReorderThread { hint, bits } => {
914                    validate_expr(hint)?;
915                    validate_expr(bits)?;
916                    Ok(())
917                }
918            },
919            crate::Statement::HitObject { hit_object, fun } => {
920                validate_expr(hit_object)?;
921                match fun {
922                    crate::HitObjectFunction::TraceRay {
923                        acceleration_structure,
924                        descriptor,
925                        payload,
926                    } => {
927                        validate_expr(acceleration_structure)?;
928                        validate_expr(descriptor)?;
929                        validate_expr(payload)?;
930                    }
931                    crate::HitObjectFunction::RecordMiss { descriptor } => {
932                        validate_expr(descriptor)?;
933                    }
934                    crate::HitObjectFunction::RecordFromQuery { query } => {
935                        validate_expr(query)?;
936                    }
937                    crate::HitObjectFunction::RecordEmpty => {}
938                    crate::HitObjectFunction::ExecuteShader { payload } => {
939                        validate_expr(payload)?;
940                    }
941                    crate::HitObjectFunction::Reorder { hint } => {
942                        validate_reorder_hint(hint)?;
943                    }
944                }
945                Ok(())
946            }
947            crate::Statement::DebugPrintf {
948                format: _,
949                ref arguments,
950            } => {
951                for &arg in arguments {
952                    validate_expr(arg)?;
953                }
954                Ok(())
955            }
956            crate::Statement::Break
957            | crate::Statement::Continue
958            | crate::Statement::Kill
959            | crate::Statement::ControlBarrier(_)
960            | crate::Statement::MemoryBarrier(_) => Ok(()),
961        })
962    }
963}
964
965impl From<BadHandle> for Box<ValidationError> {
966    fn from(source: BadHandle) -> Self {
967        Box::new(ValidationError::InvalidHandle(source.into()))
968    }
969}
970
971impl From<FwdDepError> for Box<ValidationError> {
972    fn from(source: FwdDepError) -> Self {
973        Box::new(ValidationError::InvalidHandle(source.into()))
974    }
975}
976
977impl From<BadRangeError> for Box<ValidationError> {
978    fn from(source: BadRangeError) -> Self {
979        Box::new(ValidationError::InvalidHandle(source.into()))
980    }
981}
982
983impl From<InvalidHandleError> for Box<ValidationError> {
984    fn from(source: InvalidHandleError) -> Self {
985        Box::new(ValidationError::InvalidHandle(source))
986    }
987}
988
989#[derive(Clone, Debug, thiserror::Error)]
990#[cfg_attr(test, derive(PartialEq))]
991pub enum InvalidHandleError {
992    #[error(transparent)]
993    BadHandle(#[from] BadHandle),
994    #[error(transparent)]
995    ForwardDependency(#[from] FwdDepError),
996    #[error(transparent)]
997    BadRange(#[from] BadRangeError),
998}
999
1000#[derive(Clone, Debug, thiserror::Error)]
1001#[cfg_attr(test, derive(PartialEq))]
1002#[error(
1003    "{subject:?} of kind {subject_kind:?} depends on {depends_on:?} of kind {depends_on_kind}, \
1004    which has not been processed yet"
1005)]
1006pub struct FwdDepError {
1007    // This error is used for many `Handle` types, but there's no point in making this generic, so
1008    // we just flatten them all to `Handle<()>` here.
1009    subject: Handle<()>,
1010    subject_kind: &'static str,
1011    depends_on: Handle<()>,
1012    depends_on_kind: &'static str,
1013}
1014
1015impl<T> Handle<T> {
1016    /// Check that `self` is valid within `arena` using [`Arena::check_contains_handle`].
1017    pub(self) fn check_valid_for(self, arena: &Arena<T>) -> Result<(), InvalidHandleError> {
1018        arena.check_contains_handle(self)?;
1019        Ok(())
1020    }
1021
1022    /// Check that `self` is valid within `arena` using [`UniqueArena::check_contains_handle`].
1023    pub(self) fn check_valid_for_uniq(
1024        self,
1025        arena: &UniqueArena<T>,
1026    ) -> Result<(), InvalidHandleError>
1027    where
1028        T: Eq + Hash,
1029    {
1030        arena.check_contains_handle(self)?;
1031        Ok(())
1032    }
1033
1034    /// Check that `depends_on` was constructed before `self` by comparing handle indices.
1035    ///
1036    /// If `self` is a valid handle (i.e., it has been validated using [`Self::check_valid_for`])
1037    /// and this function returns [`Ok`], then it may be assumed that `depends_on` is also valid.
1038    /// In [`naga`](crate)'s current arena-based implementation, this is useful for validating
1039    /// recursive definitions of arena-based values in linear time.
1040    ///
1041    /// # Errors
1042    ///
1043    /// If `depends_on`'s handle is from the same [`Arena`] as `self'`s, but not constructed earlier
1044    /// than `self`'s, this function returns an error.
1045    pub(self) fn check_dep(self, depends_on: Self) -> Result<Self, FwdDepError> {
1046        if depends_on < self {
1047            Ok(self)
1048        } else {
1049            let erase_handle_type = |handle: Handle<_>| {
1050                Handle::new(NonMaxU32::new((handle.index()).try_into().unwrap()).unwrap())
1051            };
1052            Err(FwdDepError {
1053                subject: erase_handle_type(self),
1054                subject_kind: core::any::type_name::<T>(),
1055                depends_on: erase_handle_type(depends_on),
1056                depends_on_kind: core::any::type_name::<T>(),
1057            })
1058        }
1059    }
1060
1061    /// Like [`Self::check_dep`], except for [`Option`]al handle values.
1062    pub(self) fn check_dep_opt(self, depends_on: Option<Self>) -> Result<Self, FwdDepError> {
1063        self.check_dep_iter(depends_on.into_iter())
1064    }
1065
1066    /// Like [`Self::check_dep`], except for [`Iterator`]s over handle values.
1067    pub(self) fn check_dep_iter(
1068        self,
1069        depends_on: impl Iterator<Item = Self>,
1070    ) -> Result<Self, FwdDepError> {
1071        for handle in depends_on {
1072            self.check_dep(handle)?;
1073        }
1074        Ok(self)
1075    }
1076}
1077
1078impl<T> crate::arena::Range<T> {
1079    pub(self) fn check_valid_for(&self, arena: &Arena<T>) -> Result<(), BadRangeError> {
1080        arena.check_contains_range(self)
1081    }
1082}
1083
1084#[test]
1085fn constant_deps() {
1086    use crate::{Constant, Expression, Literal, Span, Type, TypeInner};
1087
1088    let nowhere = Span::default();
1089
1090    let mut types = UniqueArena::new();
1091    let mut const_exprs = Arena::new();
1092    let mut fun_exprs = Arena::new();
1093    let mut constants = Arena::new();
1094    let overrides = Arena::new();
1095
1096    let i32_handle = types.insert(
1097        Type {
1098            name: None,
1099            inner: TypeInner::Scalar(crate::Scalar::I32),
1100        },
1101        nowhere,
1102    );
1103
1104    // Construct a self-referential constant by misusing a handle to
1105    // fun_exprs as a constant initializer.
1106    let fun_expr = fun_exprs.append(Expression::Literal(Literal::I32(42)), nowhere);
1107    let self_referential_const = constants.append(
1108        Constant {
1109            name: None,
1110            ty: i32_handle,
1111            init: fun_expr,
1112        },
1113        nowhere,
1114    );
1115    let _self_referential_expr =
1116        const_exprs.append(Expression::Constant(self_referential_const), nowhere);
1117
1118    for handle_and_expr in const_exprs.iter() {
1119        assert!(super::Validator::validate_const_expression_handles(
1120            handle_and_expr,
1121            &constants,
1122            &overrides,
1123        )
1124        .is_err());
1125    }
1126}
1127
1128#[test]
1129fn array_size_deps() {
1130    use super::Validator;
1131    use crate::{ArraySize, Expression, Override, Scalar, Span, Type, TypeInner};
1132
1133    let nowhere = Span::default();
1134
1135    let mut m = crate::Module::default();
1136
1137    let ty_u32 = m.types.insert(
1138        Type {
1139            name: Some("u32".to_string()),
1140            inner: TypeInner::Scalar(Scalar::U32),
1141        },
1142        nowhere,
1143    );
1144    let ex_zero = m
1145        .global_expressions
1146        .append(Expression::ZeroValue(ty_u32), nowhere);
1147    let ty_handle = m.overrides.append(
1148        Override {
1149            name: None,
1150            id: None,
1151            ty: ty_u32,
1152            init: Some(ex_zero),
1153        },
1154        nowhere,
1155    );
1156    let ty_arr = m.types.insert(
1157        Type {
1158            name: Some("bad_array".to_string()),
1159            inner: TypeInner::Array {
1160                base: ty_u32,
1161                size: ArraySize::Pending(ty_handle),
1162                stride: 4,
1163            },
1164        },
1165        nowhere,
1166    );
1167
1168    // Everything should be okay now.
1169    assert!(Validator::validate_module_handles(&m).is_ok());
1170
1171    // Mutate `ex_zero`'s type to `ty_arr`, introducing a cycle.
1172    // Validation should catch the cycle.
1173    m.global_expressions[ex_zero] = Expression::ZeroValue(ty_arr);
1174    assert!(Validator::validate_module_handles(&m).is_err());
1175}
1176
1177#[test]
1178fn array_size_override() {
1179    use super::Validator;
1180    use crate::{ArraySize, Override, Scalar, Span, Type, TypeInner};
1181
1182    let nowhere = Span::default();
1183
1184    let mut m = crate::Module::default();
1185
1186    let ty_u32 = m.types.insert(
1187        Type {
1188            name: Some("u32".to_string()),
1189            inner: TypeInner::Scalar(Scalar::U32),
1190        },
1191        nowhere,
1192    );
1193
1194    let bad_override: Handle<Override> = Handle::new(NonMaxU32::new(1000).unwrap());
1195    let _ty_arr = m.types.insert(
1196        Type {
1197            name: Some("bad_array".to_string()),
1198            inner: TypeInner::Array {
1199                base: ty_u32,
1200                size: ArraySize::Pending(bad_override),
1201                stride: 4,
1202            },
1203        },
1204        nowhere,
1205    );
1206
1207    assert!(Validator::validate_module_handles(&m).is_err());
1208}
1209
1210#[test]
1211fn override_init_deps() {
1212    use super::Validator;
1213    use crate::{ArraySize, Expression, Override, Scalar, Span, Type, TypeInner};
1214
1215    let nowhere = Span::default();
1216
1217    let mut m = crate::Module::default();
1218
1219    let ty_u32 = m.types.insert(
1220        Type {
1221            name: Some("u32".to_string()),
1222            inner: TypeInner::Scalar(Scalar::U32),
1223        },
1224        nowhere,
1225    );
1226    let ex_zero = m
1227        .global_expressions
1228        .append(Expression::ZeroValue(ty_u32), nowhere);
1229    let r#override = m.overrides.append(
1230        Override {
1231            name: Some("bad_override".into()),
1232            id: None,
1233            ty: ty_u32,
1234            init: Some(ex_zero),
1235        },
1236        nowhere,
1237    );
1238    let ty_arr = m.types.insert(
1239        Type {
1240            name: Some("bad_array".to_string()),
1241            inner: TypeInner::Array {
1242                base: ty_u32,
1243                size: ArraySize::Pending(r#override),
1244                stride: 4,
1245            },
1246        },
1247        nowhere,
1248    );
1249    let ex_arr = m
1250        .global_expressions
1251        .append(Expression::ZeroValue(ty_arr), nowhere);
1252
1253    assert!(Validator::validate_module_handles(&m).is_ok());
1254
1255    // Mutate `r#override`'s initializer to `ex_arr`, introducing a cycle.
1256    // Validation should catch the cycle.
1257    m.overrides[r#override].init = Some(ex_arr);
1258    assert!(Validator::validate_module_handles(&m).is_err());
1259}