1//! Types relating to type information provided by validation.
2
3use super::core::Module;
4#[cfg(feature = "component-model")]
5use crate::validator::component::ComponentState;
6#[cfg(feature = "component-model")]
7use crate::validator::component_types::{ComponentTypeAlloc, ComponentTypeList};
8use crate::{collections::map::Entry, AbstractHeapType};
9use crate::{prelude::*, CompositeInnerType};
10use crate::{
11 Export, ExternalKind, GlobalType, Import, Matches, MemoryType, PackedIndex, RecGroup, RefType,
12 Result, SubType, TableType, TypeRef, UnpackedIndex, ValType, WithRecGroup,
13};
14use crate::{FuncType, HeapType, ValidatorId};
15use alloc::sync::Arc;
16use core::ops::{Deref, DerefMut, Index, Range};
17use core::{hash::Hash, mem};
18
19/// A trait shared by all type identifiers.
20///
21/// Any id that can be used to get a type from a `Types`.
22//
23// Or, internally, from a `TypeList`.
24pub trait TypeIdentifier: core::fmt::Debug + Copy + Eq + Sized + 'static {
25 /// The data pointed to by this type of id.
26 type Data: TypeData<Id = Self>;
27
28 /// Create a type id from an index.
29 #[doc(hidden)]
30 fn from_index(index: u32) -> Self;
31
32 /// Get a shared reference to the list where this id's type data is stored
33 /// within.
34 #[doc(hidden)]
35 fn list(types: &TypeList) -> &SnapshotList<Self::Data>;
36
37 /// Get an exclusive reference to the list where this id's type data is
38 /// stored within.
39 #[doc(hidden)]
40 fn list_mut(types: &mut TypeList) -> &mut SnapshotList<Self::Data>;
41
42 /// The raw index of this id.
43 #[doc(hidden)]
44 fn index(&self) -> usize;
45}
46
47/// A trait shared by all types within a `Types`.
48///
49/// This is the data that can be retreived by indexing with the associated
50/// [`TypeIdentifier`].
51pub trait TypeData: core::fmt::Debug {
52 /// The identifier for this type data.
53 type Id: TypeIdentifier<Data = Self>;
54
55 /// Get the info for this type.
56 #[doc(hidden)]
57 fn type_info(&self, types: &TypeList) -> TypeInfo;
58}
59
60macro_rules! define_type_id {
61 ($name:ident, $data:ty, $($list:ident).*, $type_str:expr) => {
62 #[doc = "Represents a unique identifier for a "]
63 #[doc = $type_str]
64 #[doc = " type known to a [`crate::Validator`]."]
65 #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
66 #[repr(C)] // Use fixed field layout to ensure minimal size.
67 pub struct $name {
68 /// The index into the associated list of types.
69 index: u32,
70 }
71
72 impl TypeIdentifier for $name {
73 type Data = $data;
74
75 fn from_index(index: u32) -> Self {
76 $name { index }
77 }
78
79 fn list(types: &TypeList) -> &SnapshotList<Self::Data> {
80 &types.$($list).*
81 }
82
83 fn list_mut(types: &mut TypeList) -> &mut SnapshotList<Self::Data> {
84 &mut types.$($list).*
85 }
86
87 fn index(&self) -> usize {
88 usize::try_from(self.index).unwrap()
89 }
90 }
91
92
93 // The size of type IDs was seen to have a large-ish impact in #844, so
94 // this assert ensures that it stays relatively small.
95 const _: () = {
96 assert!(core::mem::size_of::<$name>() <= 4);
97 };
98 };
99}
100pub(crate) use define_type_id;
101
102/// Represents a unique identifier for a core type type known to a
103/// [`crate::Validator`].
104#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
105#[repr(C)]
106pub struct CoreTypeId {
107 index: u32,
108}
109
110#[test]
111fn assert_core_type_id_small() {
112 assert!(core::mem::size_of::<CoreTypeId>() <= 4);
113}
114
115impl TypeIdentifier for CoreTypeId {
116 type Data = SubType;
117
118 fn from_index(index: u32) -> Self {
119 CoreTypeId { index }
120 }
121
122 fn list(types: &TypeList) -> &SnapshotList<Self::Data> {
123 &types.core_types
124 }
125
126 fn list_mut(types: &mut TypeList) -> &mut SnapshotList<Self::Data> {
127 &mut types.core_types
128 }
129
130 fn index(&self) -> usize {
131 usize::try_from(self.index).unwrap()
132 }
133}
134
135impl TypeData for SubType {
136 type Id = CoreTypeId;
137
138 fn type_info(&self, _types: &TypeList) -> TypeInfo {
139 // TODO(#1036): calculate actual size for func, array, struct.
140 let size: u32 = 1 + match &self.composite_type.inner {
141 CompositeInnerType::Func(ty: &FuncType) => 1 + (ty.params().len() + ty.results().len()) as u32,
142 CompositeInnerType::Array(_) => 2,
143 CompositeInnerType::Struct(ty: &StructType) => 1 + 2 * ty.fields.len() as u32,
144 CompositeInnerType::Cont(_) => 1,
145 };
146 TypeInfo::core(size)
147 }
148}
149
150define_type_id!(
151 RecGroupId,
152 Range<CoreTypeId>,
153 rec_group_elements,
154 "recursion group"
155);
156
157impl TypeData for Range<CoreTypeId> {
158 type Id = RecGroupId;
159
160 fn type_info(&self, _types: &TypeList) -> TypeInfo {
161 let size: usize = self.end.index() - self.start.index();
162 TypeInfo::core(size:u32::try_from(size).unwrap())
163 }
164}
165
166/// Metadata about a type and its transitive structure.
167///
168/// Currently contains two properties:
169///
170/// * The "size" of a type - a proxy to the recursive size of a type if
171/// everything in the type were unique (e.g. no shared references). Not an
172/// approximation of runtime size, but instead of type-complexity size if
173/// someone were to visit each element of the type individually. For example
174/// `u32` has size 1 and `(list u32)` has size 2 (roughly). Used to prevent
175/// massive trees of types.
176///
177/// * Whether or not a type contains a "borrow" transitively inside of it. For
178/// example `(borrow $t)` and `(list (borrow $t))` both contain borrows, but
179/// `(list u32)` does not. Used to validate that component function results do
180/// not contain borrows.
181///
182/// Currently this is represented as a compact 32-bit integer to ensure that
183/// `TypeId`, which this is stored in, remains relatively small. The maximum
184/// type size allowed in wasmparser is 1M at this time which is 20 bits of
185/// information, and then one more bit is used for whether or not a borrow is
186/// used. Currently this uses the low 24 bits for the type size and the MSB for
187/// the borrow bit.
188#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
189// Only public because it shows up in a public trait's `doc(hidden)` method.
190#[doc(hidden)]
191pub struct TypeInfo(u32);
192
193impl TypeInfo {
194 /// Creates a new blank set of type information.
195 ///
196 /// Defaults to size 1 to ensure that this consumes space in the final type
197 /// structure.
198 pub(crate) fn new() -> TypeInfo {
199 TypeInfo::_new(1, false)
200 }
201
202 /// Creates a new blank set of information about a leaf "borrow" type which
203 /// has size 1.
204 #[cfg(feature = "component-model")]
205 pub(crate) fn borrow() -> TypeInfo {
206 TypeInfo::_new(1, true)
207 }
208
209 /// Creates type information corresponding to a core type of the `size`
210 /// specified, meaning no borrows are contained within.
211 pub(crate) fn core(size: u32) -> TypeInfo {
212 TypeInfo::_new(size, false)
213 }
214
215 fn _new(size: u32, contains_borrow: bool) -> TypeInfo {
216 assert!(size < (1 << 24));
217 TypeInfo(size | ((contains_borrow as u32) << 31))
218 }
219
220 /// Combines another set of type information into this one, for example if
221 /// this is a record which has `other` as a field.
222 ///
223 /// Updates the size of `self` and whether or not this type contains a
224 /// borrow based on whether `other` contains a borrow.
225 ///
226 /// Returns an error if the type size would exceed this crate's static limit
227 /// of a type size.
228 #[cfg(feature = "component-model")]
229 pub(crate) fn combine(&mut self, other: TypeInfo, offset: usize) -> Result<()> {
230 *self = TypeInfo::_new(
231 super::combine_type_sizes(self.size(), other.size(), offset)?,
232 self.contains_borrow() || other.contains_borrow(),
233 );
234 Ok(())
235 }
236
237 pub(crate) fn size(&self) -> u32 {
238 self.0 & 0xffffff
239 }
240
241 #[cfg(feature = "component-model")]
242 pub(crate) fn contains_borrow(&self) -> bool {
243 (self.0 >> 31) != 0
244 }
245}
246
247/// The entity type for imports and exports of a module.
248#[derive(Debug, Clone, Copy)]
249pub enum EntityType {
250 /// The entity is a function.
251 Func(CoreTypeId),
252 /// The entity is a table.
253 Table(TableType),
254 /// The entity is a memory.
255 Memory(MemoryType),
256 /// The entity is a global.
257 Global(GlobalType),
258 /// The entity is a tag.
259 Tag(CoreTypeId),
260}
261
262impl EntityType {
263 #[cfg(feature = "component-model")]
264 pub(crate) fn desc(&self) -> &'static str {
265 match self {
266 Self::Func(_) => "func",
267 Self::Table(_) => "table",
268 Self::Memory(_) => "memory",
269 Self::Global(_) => "global",
270 Self::Tag(_) => "tag",
271 }
272 }
273
274 pub(crate) fn info(&self, types: &TypeList) -> TypeInfo {
275 match self {
276 Self::Func(id: &CoreTypeId) | Self::Tag(id: &CoreTypeId) => types[*id].type_info(types),
277 Self::Table(_) | Self::Memory(_) | Self::Global(_) => TypeInfo::new(),
278 }
279 }
280}
281
282#[allow(clippy::large_enum_variant)]
283pub(super) enum TypesKind {
284 Module(Arc<Module>),
285 #[cfg(feature = "component-model")]
286 Component(ComponentState),
287}
288
289/// Represents the types known to a [`crate::Validator`] once validation has completed.
290///
291/// The type information is returned via the [`crate::Validator::end`] method.
292pub struct Types {
293 id: ValidatorId,
294 pub(super) list: TypeList,
295 pub(super) kind: TypesKind,
296}
297
298#[derive(Clone, Copy)]
299pub(super) enum TypesRefKind<'a> {
300 Module(&'a Module),
301 #[cfg(feature = "component-model")]
302 Component(&'a ComponentState),
303}
304
305/// Represents the types known to a [`crate::Validator`] during validation.
306///
307/// Retrieved via the [`crate::Validator::types`] method.
308#[derive(Clone, Copy)]
309pub struct TypesRef<'a> {
310 id: ValidatorId,
311 pub(super) list: &'a TypeList,
312 pub(super) kind: TypesRefKind<'a>,
313}
314
315impl<'a> TypesRef<'a> {
316 pub(crate) fn from_module(id: ValidatorId, types: &'a TypeList, module: &'a Module) -> Self {
317 Self {
318 id,
319 list: types,
320 kind: TypesRefKind::Module(module),
321 }
322 }
323
324 #[cfg(feature = "component-model")]
325 pub(crate) fn from_component(
326 id: ValidatorId,
327 types: &'a TypeList,
328 component: &'a ComponentState,
329 ) -> Self {
330 Self {
331 id,
332 list: types,
333 kind: TypesRefKind::Component(component),
334 }
335 }
336
337 /// Get the id of the validator that these types are associated with.
338 #[inline]
339 pub fn id(&self) -> ValidatorId {
340 self.id
341 }
342
343 /// Gets a type based on its type id.
344 ///
345 /// Returns `None` if the type id is unknown.
346 pub fn get<T>(&self, id: T) -> Option<&'a T::Data>
347 where
348 T: TypeIdentifier,
349 {
350 self.list.get(id)
351 }
352
353 /// Get the id of the rec group that the given type id was defined within.
354 pub fn rec_group_id_of(&self, id: CoreTypeId) -> RecGroupId {
355 self.list.rec_group_id_of(id)
356 }
357
358 /// Get the types within a rec group.
359 pub fn rec_group_elements(&self, id: RecGroupId) -> impl ExactSizeIterator<Item = CoreTypeId> {
360 let range = &self.list.rec_group_elements[id];
361 (range.start.index..range.end.index).map(|index| CoreTypeId { index })
362 }
363
364 /// Get the super type of the given type id, if any.
365 pub fn supertype_of(&self, id: CoreTypeId) -> Option<CoreTypeId> {
366 self.list.supertype_of(id)
367 }
368
369 /// Gets a core WebAssembly type id from a type index.
370 ///
371 /// Note that this is not to be confused with
372 /// [`TypesRef::component_type_at`] which gets a component type from its
373 /// index, nor [`TypesRef::core_type_at_in_component`] which is for
374 /// learning about core types in components.
375 ///
376 /// # Panics
377 ///
378 /// This will panic if the `index` provided is out of bounds.
379 pub fn core_type_at_in_module(&self, index: u32) -> CoreTypeId {
380 match &self.kind {
381 TypesRefKind::Module(module) => module.types[index as usize].into(),
382 #[cfg(feature = "component-model")]
383 TypesRefKind::Component(_) => panic!("use `core_type_at_in_component` instead"),
384 }
385 }
386
387 /// Returns the number of core types defined so far.
388 ///
389 /// Note that this is only for core modules, for components you should use
390 /// [`TypesRef::core_type_count_in_component`] instead.
391 pub fn core_type_count_in_module(&self) -> u32 {
392 match &self.kind {
393 TypesRefKind::Module(module) => module.types.len() as u32,
394 #[cfg(feature = "component-model")]
395 TypesRefKind::Component(_) => 0,
396 }
397 }
398
399 /// Gets the type of a table at the given table index.
400 ///
401 /// # Panics
402 ///
403 /// This will panic if the `index` provided is out of bounds.
404 pub fn table_at(&self, index: u32) -> TableType {
405 let tables = match &self.kind {
406 TypesRefKind::Module(module) => &module.tables,
407 #[cfg(feature = "component-model")]
408 TypesRefKind::Component(component) => &component.core_tables,
409 };
410 tables[index as usize]
411 }
412
413 /// Returns the number of tables defined so far.
414 pub fn table_count(&self) -> u32 {
415 match &self.kind {
416 TypesRefKind::Module(module) => module.tables.len() as u32,
417 #[cfg(feature = "component-model")]
418 TypesRefKind::Component(component) => component.core_tables.len() as u32,
419 }
420 }
421
422 /// Gets the type of a memory at the given memory index.
423 ///
424 /// # Panics
425 ///
426 /// This will panic if the `index` provided is out of bounds.
427 pub fn memory_at(&self, index: u32) -> MemoryType {
428 let memories = match &self.kind {
429 TypesRefKind::Module(module) => &module.memories,
430 #[cfg(feature = "component-model")]
431 TypesRefKind::Component(component) => &component.core_memories,
432 };
433
434 memories[index as usize]
435 }
436
437 /// Returns the number of memories defined so far.
438 pub fn memory_count(&self) -> u32 {
439 match &self.kind {
440 TypesRefKind::Module(module) => module.memories.len() as u32,
441 #[cfg(feature = "component-model")]
442 TypesRefKind::Component(component) => component.core_memories.len() as u32,
443 }
444 }
445
446 /// Gets the type of a global at the given global index.
447 ///
448 /// # Panics
449 ///
450 /// This will panic if the `index` provided is out of bounds.
451 pub fn global_at(&self, index: u32) -> GlobalType {
452 let globals = match &self.kind {
453 TypesRefKind::Module(module) => &module.globals,
454 #[cfg(feature = "component-model")]
455 TypesRefKind::Component(component) => &component.core_globals,
456 };
457
458 globals[index as usize]
459 }
460
461 /// Returns the number of globals defined so far.
462 pub fn global_count(&self) -> u32 {
463 match &self.kind {
464 TypesRefKind::Module(module) => module.globals.len() as u32,
465 #[cfg(feature = "component-model")]
466 TypesRefKind::Component(component) => component.core_globals.len() as u32,
467 }
468 }
469
470 /// Gets the type of a tag at the given tag index.
471 ///
472 /// # Panics
473 ///
474 /// This will panic if the `index` provided is out of bounds.
475 pub fn tag_at(&self, index: u32) -> CoreTypeId {
476 let tags = match &self.kind {
477 TypesRefKind::Module(module) => &module.tags,
478 #[cfg(feature = "component-model")]
479 TypesRefKind::Component(component) => &component.core_tags,
480 };
481 tags[index as usize]
482 }
483
484 /// Returns the number of tags defined so far.
485 pub fn tag_count(&self) -> u32 {
486 match &self.kind {
487 TypesRefKind::Module(module) => module.tags.len() as u32,
488 #[cfg(feature = "component-model")]
489 TypesRefKind::Component(component) => component.core_tags.len() as u32,
490 }
491 }
492
493 /// Gets the type of a core function at the given function index.
494 ///
495 /// # Panics
496 ///
497 /// This will panic if the `index` provided is out of bounds.
498 pub fn core_function_at(&self, index: u32) -> CoreTypeId {
499 match &self.kind {
500 TypesRefKind::Module(module) => module.types[module.functions[index as usize] as usize],
501 #[cfg(feature = "component-model")]
502 TypesRefKind::Component(component) => component.core_funcs[index as usize],
503 }
504 }
505
506 /// Gets the count of core functions defined so far.
507 ///
508 /// Note that this includes imported functions, defined functions, and for
509 /// components lowered/aliased functions.
510 pub fn function_count(&self) -> u32 {
511 match &self.kind {
512 TypesRefKind::Module(module) => module.functions.len() as u32,
513 #[cfg(feature = "component-model")]
514 TypesRefKind::Component(component) => component.core_funcs.len() as u32,
515 }
516 }
517
518 /// Gets the type of an element segment at the given element segment index.
519 ///
520 /// # Panics
521 ///
522 /// This will panic if the `index` provided is out of bounds.
523 pub fn element_at(&self, index: u32) -> RefType {
524 match &self.kind {
525 TypesRefKind::Module(module) => module.element_types[index as usize],
526 #[cfg(feature = "component-model")]
527 TypesRefKind::Component(_) => {
528 panic!("no elements on a component")
529 }
530 }
531 }
532
533 /// Returns the number of elements defined so far.
534 pub fn element_count(&self) -> u32 {
535 match &self.kind {
536 TypesRefKind::Module(module) => module.element_types.len() as u32,
537 #[cfg(feature = "component-model")]
538 TypesRefKind::Component(_) => 0,
539 }
540 }
541
542 /// Gets the entity type for the given import.
543 pub fn entity_type_from_import(&self, import: &Import) -> Option<EntityType> {
544 match &self.kind {
545 TypesRefKind::Module(module) => Some(match import.ty {
546 TypeRef::Func(idx) => EntityType::Func(*module.types.get(idx as usize)?),
547 TypeRef::Table(ty) => EntityType::Table(ty),
548 TypeRef::Memory(ty) => EntityType::Memory(ty),
549 TypeRef::Global(ty) => EntityType::Global(ty),
550 TypeRef::Tag(ty) => EntityType::Tag(*module.types.get(ty.func_type_idx as usize)?),
551 }),
552 #[cfg(feature = "component-model")]
553 TypesRefKind::Component(_) => None,
554 }
555 }
556
557 /// Gets the entity type from the given export.
558 pub fn entity_type_from_export(&self, export: &Export) -> Option<EntityType> {
559 match &self.kind {
560 TypesRefKind::Module(module) => Some(match export.kind {
561 ExternalKind::Func => EntityType::Func(
562 module.types[*module.functions.get(export.index as usize)? as usize],
563 ),
564 ExternalKind::Table => {
565 EntityType::Table(*module.tables.get(export.index as usize)?)
566 }
567 ExternalKind::Memory => {
568 EntityType::Memory(*module.memories.get(export.index as usize)?)
569 }
570 ExternalKind::Global => {
571 EntityType::Global(*module.globals.get(export.index as usize)?)
572 }
573 ExternalKind::Tag => EntityType::Tag(
574 module.types[*module.functions.get(export.index as usize)? as usize],
575 ),
576 }),
577 #[cfg(feature = "component-model")]
578 TypesRefKind::Component(_) => None,
579 }
580 }
581
582 /// Returns an iterator over the core wasm imports found.
583 ///
584 /// Returns `None` if this type information is for a component.
585 pub fn core_imports(
586 &self,
587 ) -> Option<impl Iterator<Item = (&'a str, &'a str, EntityType)> + 'a> {
588 match &self.kind {
589 TypesRefKind::Module(module) => Some(
590 module
591 .imports
592 .iter()
593 .flat_map(|((m, n), t)| t.iter().map(move |t| (m.as_str(), n.as_str(), *t))),
594 ),
595 #[cfg(feature = "component-model")]
596 TypesRefKind::Component(_) => None,
597 }
598 }
599
600 /// Returns an iterator over the core wasm exports found.
601 ///
602 /// Returns `None` if this type information is for a component.
603 pub fn core_exports(&self) -> Option<impl Iterator<Item = (&'a str, EntityType)> + 'a> {
604 match &self.kind {
605 TypesRefKind::Module(module) => {
606 Some(module.exports.iter().map(|(n, t)| (n.as_str(), *t)))
607 }
608 #[cfg(feature = "component-model")]
609 TypesRefKind::Component(_) => None,
610 }
611 }
612}
613
614impl<T> Index<T> for TypesRef<'_>
615where
616 T: TypeIdentifier,
617{
618 type Output = T::Data;
619
620 fn index(&self, index: T) -> &Self::Output {
621 &self.list[index]
622 }
623}
624
625impl Types {
626 pub(crate) fn from_module(id: ValidatorId, types: TypeList, module: Arc<Module>) -> Self {
627 Self {
628 id,
629 list: types,
630 kind: TypesKind::Module(module),
631 }
632 }
633
634 #[cfg(feature = "component-model")]
635 pub(crate) fn from_component(
636 id: ValidatorId,
637 types: TypeList,
638 component: ComponentState,
639 ) -> Self {
640 Self {
641 id,
642 list: types,
643 kind: TypesKind::Component(component),
644 }
645 }
646
647 /// Return a [`TypesRef`] through which types can be inspected.
648 pub fn as_ref(&self) -> TypesRef<'_> {
649 TypesRef {
650 id: self.id,
651 list: &self.list,
652 kind: match &self.kind {
653 TypesKind::Module(module) => TypesRefKind::Module(module),
654 #[cfg(feature = "component-model")]
655 TypesKind::Component(component) => TypesRefKind::Component(component),
656 },
657 }
658 }
659}
660
661impl<T> Index<T> for Types
662where
663 T: TypeIdentifier,
664{
665 type Output = T::Data;
666
667 fn index(&self, id: T) -> &Self::Output {
668 &self.list[id]
669 }
670}
671
672/// This is a type which mirrors a subset of the `Vec<T>` API, but is intended
673/// to be able to be cheaply snapshotted and cloned.
674///
675/// When each module's code sections start we "commit" the current list of types
676/// in the global list of types. This means that the temporary `cur` vec here is
677/// pushed onto `snapshots` and wrapped up in an `Arc`. At that point we clone
678/// this entire list (which is then O(modules), not O(types in all modules)) and
679/// pass out as a context to each function validator.
680///
681/// Otherwise, though, this type behaves as if it were a large `Vec<T>`, but
682/// it's represented by lists of contiguous chunks.
683//
684// Only public because it shows up in a public trait's `doc(hidden)` method.
685#[doc(hidden)]
686#[derive(Debug)]
687pub struct SnapshotList<T> {
688 // All previous snapshots, the "head" of the list that this type represents.
689 // The first entry in this pair is the starting index for all elements
690 // contained in the list, and the second element is the list itself. Note
691 // the `Arc` wrapper around sub-lists, which makes cloning time for this
692 // `SnapshotList` O(snapshots) rather than O(snapshots_total), which for
693 // us in this context means the number of modules, not types.
694 //
695 // Note that this list is sorted least-to-greatest in order of the index for
696 // binary searching.
697 snapshots: Vec<Arc<Snapshot<T>>>,
698
699 // This is the total length of all lists in the `snapshots` array.
700 snapshots_total: usize,
701
702 // The current list of types for the current snapshot that are being built.
703 cur: Vec<T>,
704}
705
706#[derive(Debug)]
707struct Snapshot<T> {
708 prior_types: usize,
709 items: Vec<T>,
710}
711
712impl<T> SnapshotList<T> {
713 /// Same as `<&[T]>::get`
714 pub(crate) fn get(&self, index: usize) -> Option<&T> {
715 // Check to see if this index falls on our local list
716 if index >= self.snapshots_total {
717 return self.cur.get(index - self.snapshots_total);
718 }
719 // ... and failing that we do a binary search to figure out which bucket
720 // it's in. Note the `i-1` in the `Err` case because if we don't find an
721 // exact match the type is located in the previous bucket.
722 let i = match self
723 .snapshots
724 .binary_search_by_key(&index, |snapshot| snapshot.prior_types)
725 {
726 Ok(i) => i,
727 Err(i) => i - 1,
728 };
729 let snapshot = &self.snapshots[i];
730 Some(&snapshot.items[index - snapshot.prior_types])
731 }
732
733 /// Same as `Vec::push`
734 pub(crate) fn push(&mut self, val: T) {
735 self.cur.push(val);
736 }
737
738 /// Same as `<[T]>::len`
739 pub(crate) fn len(&self) -> usize {
740 self.cur.len() + self.snapshots_total
741 }
742
743 /// Same as `Vec::truncate` but can only truncate uncommitted elements.
744 #[cfg(feature = "component-model")]
745 pub(crate) fn truncate(&mut self, len: usize) {
746 assert!(len >= self.snapshots_total);
747 self.cur.truncate(len - self.snapshots_total);
748 }
749
750 /// Commits previously pushed types into this snapshot vector, and returns a
751 /// clone of this list.
752 ///
753 /// The returned `SnapshotList` can be used to access all the same types as
754 /// this list itself. This list also is not changed (from an external
755 /// perspective) and can continue to access all the same types.
756 pub(crate) fn commit(&mut self) -> SnapshotList<T> {
757 // If the current chunk has new elements, commit them in to an
758 // `Arc`-wrapped vector in the snapshots list. Note the `shrink_to_fit`
759 // ahead of time to hopefully keep memory usage lower than it would
760 // otherwise be.
761 let len = self.cur.len();
762 if len > 0 {
763 self.cur.shrink_to_fit();
764 self.snapshots.push(Arc::new(Snapshot {
765 prior_types: self.snapshots_total,
766 items: mem::take(&mut self.cur),
767 }));
768 self.snapshots_total += len;
769 }
770 SnapshotList {
771 snapshots: self.snapshots.clone(),
772 snapshots_total: self.snapshots_total,
773 cur: Vec::new(),
774 }
775 }
776}
777
778impl<T> Index<usize> for SnapshotList<T> {
779 type Output = T;
780
781 #[inline]
782 fn index(&self, index: usize) -> &T {
783 self.get(index).unwrap()
784 }
785}
786
787impl<T, U> Index<U> for SnapshotList<T>
788where
789 U: TypeIdentifier<Data = T>,
790{
791 type Output = T;
792
793 #[inline]
794 fn index(&self, id: U) -> &T {
795 self.get(id.index()).unwrap()
796 }
797}
798
799impl<T> Default for SnapshotList<T> {
800 fn default() -> SnapshotList<T> {
801 SnapshotList {
802 snapshots: Vec::new(),
803 snapshots_total: 0,
804 cur: Vec::new(),
805 }
806 }
807}
808
809/// A snapshot list of types.
810///
811/// Note that the snapshot lists below do not correspond with index spaces. Many
812/// different kinds of types are in the same index space (e.g. all of the
813/// component model's {component, instance, defined, func} types are in the same
814/// index space). However, we store each of them in their own type-specific
815/// snapshot list and give each of them their own identifier type.
816#[derive(Default, Debug)]
817// Only public because it shows up in a public trait's `doc(hidden)` method.
818#[doc(hidden)]
819pub struct TypeList {
820 // Core Wasm types.
821 //
822 // A primary map from `CoreTypeId` to `SubType`.
823 pub(super) core_types: SnapshotList<SubType>,
824 // The id of each core Wasm type's rec group.
825 //
826 // A secondary map from `CoreTypeId` to `RecGroupId`.
827 pub(super) core_type_to_rec_group: SnapshotList<RecGroupId>,
828 // The supertype of each core type.
829 //
830 // A secondary map from `CoreTypeId` to `Option<CoreTypeId>`.
831 pub(super) core_type_to_supertype: SnapshotList<Option<CoreTypeId>>,
832 // The subtyping depth of each core type. We use `u8::MAX` as a sentinel for
833 // an uninitialized entry.
834 //
835 // A secondary map from `CoreTypeId` to `u8`.
836 pub(super) core_type_to_depth: Option<IndexMap<CoreTypeId, u8>>,
837 // A primary map from `RecGroupId` to the range of the rec group's elements
838 // within `core_types`.
839 pub(super) rec_group_elements: SnapshotList<Range<CoreTypeId>>,
840 // A hash map from rec group elements to their canonical `RecGroupId`.
841 //
842 // This is `None` when a list is "committed" meaning that no more insertions
843 // can happen.
844 pub(super) canonical_rec_groups: Option<Map<RecGroup, RecGroupId>>,
845
846 #[cfg(feature = "component-model")]
847 pub(super) component: ComponentTypeList,
848}
849
850impl TypeList {
851 pub fn get<T>(&self, id: T) -> Option<&T::Data>
852 where
853 T: TypeIdentifier,
854 {
855 T::list(self).get(id.index())
856 }
857
858 pub fn push<T>(&mut self, ty: T) -> T::Id
859 where
860 T: TypeData,
861 {
862 let index = u32::try_from(T::Id::list(self).len()).unwrap();
863 let id = T::Id::from_index(index);
864 T::Id::list_mut(self).push(ty);
865 id
866 }
867
868 /// Intern the given recursion group (that has already been canonicalized)
869 /// and return its associated id and whether this was a new recursion group
870 /// or not.
871 ///
872 /// If the `needs_type_canonicalization` flag is provided then the type will
873 /// be intern'd here and its indices will be canonicalized to `CoreTypeId`
874 /// from the previous `RecGroup`-based indices.
875 ///
876 /// If the `needs_type_canonicalization` flag is `false` then it must be
877 /// required that `RecGroup` doesn't have any rec-group-relative references
878 /// and it will additionally not be intern'd.
879 pub fn intern_canonical_rec_group(
880 &mut self,
881 needs_type_canonicalization: bool,
882 mut rec_group: RecGroup,
883 ) -> (bool, RecGroupId) {
884 let rec_group_id = self.rec_group_elements.len();
885 let rec_group_id = u32::try_from(rec_group_id).unwrap();
886 let rec_group_id = RecGroupId::from_index(rec_group_id);
887
888 if needs_type_canonicalization {
889 let canonical_rec_groups = self
890 .canonical_rec_groups
891 .as_mut()
892 .expect("cannot intern into a committed list");
893 let entry = match canonical_rec_groups.entry(rec_group) {
894 Entry::Occupied(e) => return (false, *e.get()),
895 Entry::Vacant(e) => e,
896 };
897 rec_group = entry.key().clone();
898 entry.insert(rec_group_id);
899 }
900
901 let start = self.core_types.len();
902 let start = u32::try_from(start).unwrap();
903 let start = CoreTypeId::from_index(start);
904
905 for mut ty in rec_group.into_types() {
906 debug_assert_eq!(self.core_types.len(), self.core_type_to_supertype.len());
907 debug_assert_eq!(self.core_types.len(), self.core_type_to_rec_group.len());
908
909 self.core_type_to_supertype
910 .push(ty.supertype_idx.and_then(|idx| match idx.unpack() {
911 UnpackedIndex::RecGroup(offset) => {
912 Some(CoreTypeId::from_index(start.index + offset))
913 }
914 UnpackedIndex::Id(id) => Some(id),
915 // Only invalid wasm has this, at this point, so defer the
916 // error to later.
917 UnpackedIndex::Module(_) => None,
918 }));
919 ty.remap_indices(&mut |index| {
920 // Note that `UnpackedIndex::Id` is unmodified and
921 // `UnpackedIndex::Module` means that this is invalid wasm which
922 // will get an error returned later.
923 if let UnpackedIndex::RecGroup(offset) = index.unpack() {
924 *index = UnpackedIndex::Id(CoreTypeId::from_index(start.index + offset))
925 .pack()
926 .unwrap();
927 }
928 Ok(())
929 })
930 .expect("cannot fail");
931 self.core_types.push(ty);
932 self.core_type_to_rec_group.push(rec_group_id);
933 }
934
935 let end = self.core_types.len();
936 let end = u32::try_from(end).unwrap();
937 let end = CoreTypeId::from_index(end);
938
939 let range = start..end;
940
941 self.rec_group_elements.push(range.clone());
942
943 return (true, rec_group_id);
944 }
945
946 /// Helper for interning a sub type as a rec group; see
947 /// [`Self::intern_canonical_rec_group`].
948 pub fn intern_sub_type(&mut self, sub_ty: SubType, offset: usize) -> CoreTypeId {
949 let (_is_new, group_id) =
950 self.intern_canonical_rec_group(false, RecGroup::implicit(offset, sub_ty));
951 self[group_id].start
952 }
953
954 /// Helper for interning a function type as a rec group; see
955 /// [`Self::intern_sub_type`].
956 pub fn intern_func_type(&mut self, ty: FuncType, offset: usize) -> CoreTypeId {
957 self.intern_sub_type(SubType::func(ty, false), offset)
958 }
959
960 /// Get the `CoreTypeId` for a local index into a rec group.
961 pub fn rec_group_local_id(
962 &self,
963 rec_group: RecGroupId,
964 index: u32,
965 offset: usize,
966 ) -> Result<CoreTypeId> {
967 let elems = &self[rec_group];
968 let len = elems.end.index() - elems.start.index();
969 let len = u32::try_from(len).unwrap();
970 if index < len {
971 let id = u32::try_from(elems.start.index()).unwrap() + index;
972 let id = CoreTypeId::from_index(id);
973 Ok(id)
974 } else {
975 bail!(
976 offset,
977 "unknown type {index}: type index out of rec group bounds"
978 )
979 }
980 }
981
982 /// Get the id of the rec group that the given type id was defined within.
983 pub fn rec_group_id_of(&self, id: CoreTypeId) -> RecGroupId {
984 self.core_type_to_rec_group[id.index()]
985 }
986
987 /// Get the super type of the given type id, if any.
988 pub fn supertype_of(&self, id: CoreTypeId) -> Option<CoreTypeId> {
989 self.core_type_to_supertype[id.index()]
990 }
991
992 /// Get the subtyping depth of the given type. A type without any supertype
993 /// has depth 0.
994 pub fn get_subtyping_depth(&self, id: CoreTypeId) -> u8 {
995 let depth = self
996 .core_type_to_depth
997 .as_ref()
998 .expect("cannot get subtype depth from a committed list")[&id];
999 debug_assert!(usize::from(depth) <= crate::limits::MAX_WASM_SUBTYPING_DEPTH);
1000 depth
1001 }
1002
1003 /// Set the subtyping depth of the given type. This may only be done once
1004 /// per type.
1005 pub fn set_subtyping_depth(&mut self, id: CoreTypeId, depth: u8) {
1006 debug_assert!(usize::from(depth) <= crate::limits::MAX_WASM_SUBTYPING_DEPTH);
1007 let map = self
1008 .core_type_to_depth
1009 .as_mut()
1010 .expect("cannot set a subtype depth in a committed list");
1011 debug_assert!(!map.contains_key(&id));
1012 map.insert(id, depth);
1013 }
1014
1015 /// Get the `CoreTypeId` for a canonicalized `PackedIndex`.
1016 ///
1017 /// Panics when given a non-canonicalized `PackedIndex`.
1018 pub fn at_canonicalized_packed_index(
1019 &self,
1020 rec_group: RecGroupId,
1021 index: PackedIndex,
1022 offset: usize,
1023 ) -> Result<CoreTypeId> {
1024 self.at_canonicalized_unpacked_index(rec_group, index.unpack(), offset)
1025 }
1026
1027 /// Get the `CoreTypeId` for a canonicalized `UnpackedIndex`.
1028 ///
1029 /// Panics when given a non-canonicalized `PackedIndex`.
1030 pub fn at_canonicalized_unpacked_index(
1031 &self,
1032 rec_group: RecGroupId,
1033 index: UnpackedIndex,
1034 offset: usize,
1035 ) -> Result<CoreTypeId> {
1036 match index {
1037 UnpackedIndex::Module(_) => panic!("not canonicalized"),
1038 UnpackedIndex::Id(id) => Ok(id),
1039 UnpackedIndex::RecGroup(idx) => self.rec_group_local_id(rec_group, idx, offset),
1040 }
1041 }
1042
1043 /// Does `a` structurally match `b`?
1044 pub fn matches(&self, a: CoreTypeId, b: CoreTypeId) -> bool {
1045 let a = WithRecGroup::new(self, a);
1046 let a = WithRecGroup::map(a, |a| &self[a]);
1047
1048 let b = WithRecGroup::new(self, b);
1049 let b = WithRecGroup::map(b, |b| &self[b]);
1050
1051 Matches::matches(self, a, b)
1052 }
1053
1054 /// Is `a == b` or was `a` declared (potentially transitively) to be a
1055 /// subtype of `b`?
1056 pub fn id_is_subtype(&self, mut a: CoreTypeId, b: CoreTypeId) -> bool {
1057 loop {
1058 if a == b {
1059 return true;
1060 }
1061
1062 // TODO: maintain supertype vectors and implement this check in O(1)
1063 // instead of O(n) time.
1064 a = match self.supertype_of(a) {
1065 Some(a) => a,
1066 None => return false,
1067 };
1068 }
1069 }
1070
1071 /// Like `id_is_subtype` but for `RefType`s.
1072 ///
1073 /// Both `a` and `b` must be canonicalized already.
1074 pub fn reftype_is_subtype(&self, a: RefType, b: RefType) -> bool {
1075 // NB: Don't need `RecGroupId`s since we are calling from outside of the
1076 // rec group, and so any `PackedIndex`es we encounter have already been
1077 // canonicalized to `CoreTypeId`s directly.
1078 self.reftype_is_subtype_impl(a, None, b, None)
1079 }
1080
1081 /// Implementation of `RefType` and `HeapType` subtyping.
1082 ///
1083 /// Panics if we need rec groups but aren't given them. Rec groups only need
1084 /// to be passed in when checking subtyping of `RefType`s that we encounter
1085 /// while validating a rec group itself.
1086 pub(crate) fn reftype_is_subtype_impl(
1087 &self,
1088 a: RefType,
1089 a_group: Option<RecGroupId>,
1090 b: RefType,
1091 b_group: Option<RecGroupId>,
1092 ) -> bool {
1093 if a == b && a_group == b_group {
1094 return true;
1095 }
1096
1097 if a.is_nullable() && !b.is_nullable() {
1098 return false;
1099 }
1100
1101 let core_type_id = |group: Option<RecGroupId>, index: UnpackedIndex| -> CoreTypeId {
1102 if let Some(id) = index.as_core_type_id() {
1103 id
1104 } else {
1105 self.at_canonicalized_unpacked_index(group.unwrap(), index, usize::MAX)
1106 .expect("type references are checked during canonicalization")
1107 }
1108 };
1109
1110 let subtype = |group, index| -> &SubType {
1111 let id = core_type_id(group, index);
1112 &self[id]
1113 };
1114
1115 use AbstractHeapType::*;
1116 use CompositeInnerType as CT;
1117 use HeapType as HT;
1118 match (a.heap_type(), b.heap_type()) {
1119 (a, b) if a == b => true,
1120
1121 (
1122 HT::Abstract {
1123 shared: a_shared,
1124 ty: a_ty,
1125 },
1126 HT::Abstract {
1127 shared: b_shared,
1128 ty: b_ty,
1129 },
1130 ) => a_shared == b_shared && a_ty.is_subtype_of(b_ty),
1131
1132 (HT::Concrete(a), HT::Abstract { shared, ty }) => {
1133 let a_ty = &subtype(a_group, a).composite_type;
1134 if a_ty.shared != shared {
1135 return false;
1136 }
1137 match ty {
1138 Any | Eq => matches!(a_ty.inner, CT::Array(_) | CT::Struct(_)),
1139 Struct => matches!(a_ty.inner, CT::Struct(_)),
1140 Array => matches!(a_ty.inner, CT::Array(_)),
1141 Func => matches!(a_ty.inner, CT::Func(_)),
1142 Cont => matches!(a_ty.inner, CT::Cont(_)),
1143 // Nothing else matches. (Avoid full wildcard matches so
1144 // that adding/modifying variants is easier in the future.)
1145 Extern | Exn | I31 | None | NoFunc | NoExtern | NoExn | NoCont => false,
1146 }
1147 }
1148
1149 (HT::Abstract { shared, ty }, HT::Concrete(b)) => {
1150 let b_ty = &subtype(b_group, b).composite_type;
1151 if shared != b_ty.shared {
1152 return false;
1153 }
1154 match ty {
1155 None => matches!(b_ty.inner, CT::Array(_) | CT::Struct(_)),
1156 NoFunc => matches!(b_ty.inner, CT::Func(_)),
1157 NoCont => matches!(b_ty.inner, CT::Cont(_)),
1158 // Nothing else matches. (Avoid full wildcard matches so
1159 // that adding/modifying variants is easier in the future.)
1160 Cont | Func | Extern | Exn | Any | Eq | Array | I31 | Struct | NoExtern
1161 | NoExn => false,
1162 }
1163 }
1164
1165 (HT::Concrete(a), HT::Concrete(b)) => {
1166 self.id_is_subtype(core_type_id(a_group, a), core_type_id(b_group, b))
1167 }
1168 }
1169 }
1170
1171 /// Like `id_is_subtype` but for `RefType`s.
1172 ///
1173 /// Both `a` and `b` must be canonicalized already.
1174 pub fn valtype_is_subtype(&self, a: ValType, b: ValType) -> bool {
1175 match (a, b) {
1176 (a, b) if a == b => true,
1177 (ValType::Ref(a), ValType::Ref(b)) => self.reftype_is_subtype(a, b),
1178 (ValType::Ref(_), _)
1179 | (ValType::I32, _)
1180 | (ValType::I64, _)
1181 | (ValType::F32, _)
1182 | (ValType::F64, _)
1183 | (ValType::V128, _) => false,
1184 }
1185 }
1186
1187 /// Is `ty` shared?
1188 pub fn valtype_is_shared(&self, ty: ValType) -> bool {
1189 match ty {
1190 ValType::I32 | ValType::I64 | ValType::F32 | ValType::F64 | ValType::V128 => true,
1191 ValType::Ref(rt) => self.reftype_is_shared(rt),
1192 }
1193 }
1194
1195 /// Is the reference type `ty` shared?
1196 ///
1197 /// This is complicated by concrete heap types whose shared-ness must be
1198 /// checked by looking at the type they point to.
1199 pub fn reftype_is_shared(&self, ty: RefType) -> bool {
1200 match ty.heap_type() {
1201 HeapType::Abstract { shared, .. } => shared,
1202 HeapType::Concrete(index) => {
1203 self[index.as_core_type_id().unwrap()].composite_type.shared
1204 }
1205 }
1206 }
1207
1208 /// Get the top type of the given heap type.
1209 ///
1210 /// Concrete types must have had their indices canonicalized to core type
1211 /// ids, otherwise this method will panic.
1212 pub fn top_type(&self, heap_type: &HeapType) -> HeapType {
1213 use AbstractHeapType::*;
1214 match *heap_type {
1215 HeapType::Concrete(idx) => {
1216 let ty = &self[idx.as_core_type_id().unwrap()].composite_type;
1217 let shared = ty.shared;
1218 match ty.inner {
1219 CompositeInnerType::Func(_) => HeapType::Abstract { shared, ty: Func },
1220 CompositeInnerType::Array(_) | CompositeInnerType::Struct(_) => {
1221 HeapType::Abstract { shared, ty: Any }
1222 }
1223 CompositeInnerType::Cont(_) => HeapType::Abstract { shared, ty: Cont },
1224 }
1225 }
1226 HeapType::Abstract { shared, ty } => {
1227 let ty = match ty {
1228 Func | NoFunc => Func,
1229 Extern | NoExtern => Extern,
1230 Any | Eq | Struct | Array | I31 | None => Any,
1231 Exn | NoExn => Exn,
1232 Cont | NoCont => Cont,
1233 };
1234 HeapType::Abstract { shared, ty }
1235 }
1236 }
1237 }
1238
1239 pub fn commit(&mut self) -> TypeList {
1240 TypeList {
1241 core_types: self.core_types.commit(),
1242 core_type_to_rec_group: self.core_type_to_rec_group.commit(),
1243 core_type_to_supertype: self.core_type_to_supertype.commit(),
1244 core_type_to_depth: None,
1245 rec_group_elements: self.rec_group_elements.commit(),
1246 canonical_rec_groups: None,
1247 #[cfg(feature = "component-model")]
1248 component: self.component.commit(),
1249 }
1250 }
1251}
1252
1253impl<T> Index<T> for TypeList
1254where
1255 T: TypeIdentifier,
1256{
1257 type Output = T::Data;
1258
1259 fn index(&self, id: T) -> &Self::Output {
1260 let arena: &SnapshotList<::Data> = T::list(self);
1261 &arena[id.index()]
1262 }
1263}
1264
1265/// Thin wrapper around `TypeList` which provides an allocator of unique ids for
1266/// types contained within this list.
1267pub(crate) struct TypeAlloc {
1268 list: TypeList,
1269 #[cfg(feature = "component-model")]
1270 pub(super) component_alloc: ComponentTypeAlloc,
1271}
1272
1273impl Default for TypeAlloc {
1274 fn default() -> TypeAlloc {
1275 let mut ret: TypeAlloc = TypeAlloc {
1276 list: TypeList::default(),
1277 #[cfg(feature = "component-model")]
1278 component_alloc: ComponentTypeAlloc::default(),
1279 };
1280 ret.list.core_type_to_depth = Some(Default::default());
1281 ret.list.canonical_rec_groups = Some(Default::default());
1282 ret
1283 }
1284}
1285
1286impl Deref for TypeAlloc {
1287 type Target = TypeList;
1288 fn deref(&self) -> &TypeList {
1289 &self.list
1290 }
1291}
1292
1293impl DerefMut for TypeAlloc {
1294 fn deref_mut(&mut self) -> &mut TypeList {
1295 &mut self.list
1296 }
1297}
1298
1299impl<T> Index<T> for TypeAlloc
1300where
1301 T: TypeIdentifier,
1302{
1303 type Output = T::Data;
1304
1305 #[inline]
1306 fn index(&self, id: T) -> &T::Data {
1307 &self.list[id]
1308 }
1309}
1310