wasmtime_environ/compile/
module_types.rs

1use crate::{
2    EngineOrModuleTypeIndex, EntityRef, ModuleInternedRecGroupIndex, ModuleInternedTypeIndex,
3    ModuleTypes, TypeConvert, TypeIndex, WasmArrayType, WasmCompositeInnerType, WasmCompositeType,
4    WasmExnType, WasmFieldType, WasmFuncType, WasmHeapType, WasmResult, WasmStorageType,
5    WasmStructType, WasmSubType, wasm_unsupported,
6};
7use std::{
8    borrow::Cow,
9    collections::{HashMap, hash_map::Entry},
10    ops::Index,
11};
12use wasmparser::{UnpackedIndex, Validator, ValidatorId};
13
14/// A type marking the start of a recursion group's definition.
15///
16/// This is initialized by `ModuleTypesBuilder::start_rec_group` and then
17/// finished in `ModuleTypes::end_rec_group` after all of the types in the rec
18/// group have been defined.
19struct RecGroupStart {
20    rec_group_index: ModuleInternedRecGroupIndex,
21    start: ModuleInternedTypeIndex,
22    end: ModuleInternedTypeIndex,
23}
24
25/// A builder for [`ModuleTypes`].
26pub struct ModuleTypesBuilder {
27    /// The ID of the validator that this builder is configured for. Using a
28    /// different validator, or multiple validators, with this builder would
29    /// result in silliness because our `wasmparser::types::*Id`s are only
30    /// unique within the context of a particular validator. Getting this wrong
31    /// could result in generating calls to functions of the wrong type, for
32    /// example. So therefore we always assert that a builder instances is only
33    /// ever paired with a particular validator context.
34    validator_id: ValidatorId,
35
36    /// The canonicalized and deduplicated set of types we are building.
37    types: ModuleTypes,
38
39    /// The set of trampoline-compatible function types we have already added to
40    /// `self.types`. We do this additional level of deduping, on top of what
41    /// `wasmparser` already does, so we can quickly and easily get the
42    /// trampoline type for a given function type if we've already interned one.
43    trampoline_types: HashMap<WasmFuncType, ModuleInternedTypeIndex>,
44
45    /// An interning map for exception types corresponding to function
46    /// types used by tags. Tags are nominal, but the underlying
47    /// Wasmtime types describe only the object layout and so are
48    /// structural.
49    exception_types: HashMap<ModuleInternedTypeIndex, ModuleInternedTypeIndex>,
50
51    /// A map from already-interned `wasmparser` types to their corresponding
52    /// Wasmtime type.
53    wasmparser_to_wasmtime: HashMap<wasmparser::types::CoreTypeId, ModuleInternedTypeIndex>,
54
55    /// The set of recursion groups we have already seen and interned.
56    already_seen: HashMap<wasmparser::types::RecGroupId, ModuleInternedRecGroupIndex>,
57
58    /// If we are in the middle of defining a recursion group, this is the
59    /// metadata about the recursion group we started defining.
60    defining_rec_group: Option<RecGroupStart>,
61}
62
63impl ModuleTypesBuilder {
64    /// Construct a new `ModuleTypesBuilder` using the given validator.
65    pub fn new(validator: &Validator) -> Self {
66        Self {
67            validator_id: validator.id(),
68            types: ModuleTypes::default(),
69            trampoline_types: HashMap::default(),
70            exception_types: HashMap::default(),
71            wasmparser_to_wasmtime: HashMap::default(),
72            already_seen: HashMap::default(),
73            defining_rec_group: None,
74        }
75    }
76
77    /// Reserves space for `amt` more type signatures.
78    pub fn reserve_wasm_signatures(&mut self, amt: usize) {
79        self.types.reserve(amt);
80        self.wasmparser_to_wasmtime.reserve(amt);
81        self.already_seen.reserve(amt);
82    }
83
84    /// Get the id of the validator that this builder is configured for.
85    pub fn validator_id(&self) -> ValidatorId {
86        self.validator_id
87    }
88
89    /// Intern a recursion group and all of its types into this builder.
90    ///
91    /// If the recursion group has already been interned, then it is reused.
92    ///
93    /// Panics if given types from a different validator than the one that this
94    /// builder is associated with.
95    pub fn intern_rec_group(
96        &mut self,
97        validator_types: wasmparser::types::TypesRef<'_>,
98        rec_group_id: wasmparser::types::RecGroupId,
99    ) -> WasmResult<ModuleInternedRecGroupIndex> {
100        assert_eq!(validator_types.id(), self.validator_id);
101
102        if let Some(interned) = self.already_seen.get(&rec_group_id) {
103            return Ok(*interned);
104        }
105
106        self.define_new_rec_group(validator_types, rec_group_id)
107    }
108
109    /// Define a new recursion group that we haven't already interned.
110    fn define_new_rec_group(
111        &mut self,
112        validator_types: wasmparser::types::TypesRef<'_>,
113        rec_group_id: wasmparser::types::RecGroupId,
114    ) -> WasmResult<ModuleInternedRecGroupIndex> {
115        assert_eq!(validator_types.id(), self.validator_id);
116
117        self.start_rec_group(
118            validator_types,
119            validator_types.rec_group_elements(rec_group_id),
120        );
121
122        for id in validator_types.rec_group_elements(rec_group_id) {
123            let ty = &validator_types[id];
124            let wasm_ty = WasmparserTypeConverter::new(self, |_| {
125                unreachable!("no need to lookup indexes; we already have core type IDs")
126            })
127            .with_rec_group(validator_types, rec_group_id)
128            .convert_sub_type(ty)?;
129            self.wasm_sub_type_in_rec_group(id, wasm_ty);
130        }
131
132        let rec_group_index = self.end_rec_group(rec_group_id);
133
134        // Iterate over all the types we just defined and make sure that every
135        // function type has an associated trampoline type. This needs to happen
136        // *after* we finish defining the rec group because we may need to
137        // intern new function types, which would conflict with the contiguous
138        // range of type indices we pre-reserved for the rec group elements.
139        for ty in self.rec_group_elements(rec_group_index) {
140            if self.types[ty].is_func() {
141                let trampoline = self.intern_trampoline_type(ty);
142                self.types.set_trampoline_type(ty, trampoline);
143            }
144        }
145
146        Ok(rec_group_index)
147    }
148
149    /// Get or create the trampoline function type for the given function
150    /// type. Returns the interned type index of the trampoline function type.
151    fn intern_trampoline_type(
152        &mut self,
153        for_func_ty: ModuleInternedTypeIndex,
154    ) -> ModuleInternedTypeIndex {
155        let sub_ty = &self.types[for_func_ty];
156        let trampoline = sub_ty.unwrap_func().trampoline_type();
157
158        if let Some(idx) = self.trampoline_types.get(&trampoline) {
159            // We've already interned this trampoline type; reuse it.
160            *idx
161        } else {
162            // We have not already interned this trampoline type.
163            match trampoline {
164                // The trampoline type is the same as the original function
165                // type. We can reuse the definition and its index, but still
166                // need to intern the type into our `trampoline_types` map so we
167                // can reuse it in the future.
168                Cow::Borrowed(f) => {
169                    self.trampoline_types.insert(f.clone(), for_func_ty);
170                    for_func_ty
171                }
172                // The trampoline type is different from the original function
173                // type. Define the trampoline type and then intern it in
174                // `trampoline_types` so we can reuse it in the future.
175                Cow::Owned(f) => {
176                    let idx = self.types.push(WasmSubType {
177                        is_final: true,
178                        supertype: None,
179                        composite_type: WasmCompositeType {
180                            inner: WasmCompositeInnerType::Func(f.clone()),
181                            shared: sub_ty.composite_type.shared,
182                        },
183                    });
184
185                    // The trampoline type is its own trampoline type.
186                    self.types.set_trampoline_type(idx, idx);
187
188                    let next = self.types.next_ty();
189                    self.types.push_rec_group(idx..next);
190                    self.trampoline_types.insert(f, idx);
191                    idx
192                }
193            }
194        }
195    }
196
197    /// Start defining a recursion group.
198    fn start_rec_group(
199        &mut self,
200        validator_types: wasmparser::types::TypesRef<'_>,
201        elems: impl ExactSizeIterator<Item = wasmparser::types::CoreTypeId>,
202    ) {
203        log::trace!("Starting rec group of length {}", elems.len());
204
205        assert!(self.defining_rec_group.is_none());
206        assert_eq!(validator_types.id(), self.validator_id);
207
208        // Eagerly define the reverse map's entries for this rec group's types
209        // so that we can use them when converting `wasmparser` types to our
210        // types.
211        let len = elems.len();
212        for (i, wasmparser_id) in elems.enumerate() {
213            let interned = ModuleInternedTypeIndex::new(self.types.len_types() + i);
214            log::trace!(
215                "Reserving {interned:?} for {wasmparser_id:?} = {:?}",
216                validator_types[wasmparser_id]
217            );
218
219            let old_entry = self.wasmparser_to_wasmtime.insert(wasmparser_id, interned);
220            debug_assert_eq!(
221                old_entry, None,
222                "should not have already inserted {wasmparser_id:?}"
223            );
224        }
225
226        self.defining_rec_group = Some(RecGroupStart {
227            rec_group_index: self.types.next_rec_group(),
228            start: self.types.next_ty(),
229            end: ModuleInternedTypeIndex::new(self.types.len_types() + len),
230        });
231    }
232
233    /// Finish defining a recursion group.
234    fn end_rec_group(
235        &mut self,
236        rec_group_id: wasmparser::types::RecGroupId,
237    ) -> ModuleInternedRecGroupIndex {
238        let RecGroupStart {
239            rec_group_index,
240            start,
241            end,
242        } = self
243            .defining_rec_group
244            .take()
245            .expect("should be defining a rec group");
246
247        log::trace!("Ending rec group {start:?}..{end:?}");
248
249        debug_assert!(start.index() < self.types.len_types());
250        debug_assert_eq!(
251            end,
252            self.types.next_ty(),
253            "should have defined the number of types declared in `start_rec_group`"
254        );
255
256        let idx = self.types.push_rec_group(start..end);
257        debug_assert_eq!(idx, rec_group_index);
258
259        self.already_seen.insert(rec_group_id, rec_group_index);
260        rec_group_index
261    }
262
263    /// Intern a type into this builder and get its Wasmtime index.
264    ///
265    /// This will intern not only the single given type, but the type's entire
266    /// rec group. This helper method is provided as a convenience so that
267    /// callers don't have to get the type's rec group, intern the rec group,
268    /// and then look up the Wasmtime index for the original type themselves.
269    pub fn intern_type(
270        &mut self,
271        validator_types: wasmparser::types::TypesRef<'_>,
272        id: wasmparser::types::CoreTypeId,
273    ) -> WasmResult<ModuleInternedTypeIndex> {
274        assert!(self.defining_rec_group.is_none());
275        assert_eq!(validator_types.id(), self.validator_id);
276
277        let rec_group_id = validator_types.rec_group_id_of(id);
278        debug_assert!(
279            validator_types
280                .rec_group_elements(rec_group_id)
281                .any(|e| e == id)
282        );
283
284        let interned_rec_group = self.intern_rec_group(validator_types, rec_group_id)?;
285
286        let interned_type = self.wasmparser_to_wasmtime[&id];
287        debug_assert!(
288            self.rec_group_elements(interned_rec_group)
289                .any(|e| e == interned_type)
290        );
291
292        Ok(interned_type)
293    }
294
295    /// Define a new Wasm type while we are defining a rec group.
296    fn wasm_sub_type_in_rec_group(
297        &mut self,
298        id: wasmparser::types::CoreTypeId,
299        ty: WasmSubType,
300    ) -> ModuleInternedTypeIndex {
301        assert!(
302            self.defining_rec_group.is_some(),
303            "must be defining a rec group to define new types"
304        );
305
306        let module_interned_index = self.types.push(ty);
307        debug_assert_eq!(
308            self.wasmparser_to_wasmtime.get(&id),
309            Some(&module_interned_index),
310            "should have reserved the right module-interned index for this wasmparser type already"
311        );
312
313        module_interned_index
314    }
315
316    /// Define a new exception type when we see a function type used
317    /// in a tag.
318    ///
319    /// The returned `ModuleInternedTypeIndex` gives us a Wasmtime
320    /// type which corresponds to the exception object layout, but
321    /// note that these types do not exist in the Wasm spec: at the
322    /// Wasm level, only function types exist (and tags and exception
323    /// instructions reference them). For implementation reasons, we
324    /// need a separate type to describe the exception object layout,
325    /// and this registers and provides that type.
326    pub fn define_exception_type_for_tag(
327        &mut self,
328        for_func_ty: ModuleInternedTypeIndex,
329    ) -> ModuleInternedTypeIndex {
330        match self.exception_types.entry(for_func_ty) {
331            Entry::Occupied(o) => *o.get(),
332            Entry::Vacant(v) => {
333                let fields = self.types[for_func_ty]
334                    .unwrap_func()
335                    .params()
336                    .iter()
337                    .map(|valtype| WasmFieldType {
338                        element_type: WasmStorageType::Val(*valtype),
339                        mutable: false,
340                    })
341                    .collect();
342                let idx = self.types.push(WasmSubType {
343                    is_final: true,
344                    supertype: None,
345                    composite_type: WasmCompositeType {
346                        inner: WasmCompositeInnerType::Exn(WasmExnType {
347                            func_ty: EngineOrModuleTypeIndex::Module(for_func_ty),
348                            fields,
349                        }),
350                        shared: false,
351                    },
352                });
353                let next = self.types.next_ty();
354                self.types.push_rec_group(idx..next);
355                *v.insert(idx)
356            }
357        }
358    }
359
360    /// Returns the result [`ModuleTypes`] of this builder.
361    pub fn finish(self) -> ModuleTypes {
362        self.types
363    }
364
365    /// Get the elements within an already-defined rec group.
366    pub fn rec_group_elements(
367        &self,
368        rec_group: ModuleInternedRecGroupIndex,
369    ) -> impl ExactSizeIterator<Item = ModuleInternedTypeIndex> + use<> {
370        self.types.rec_group_elements(rec_group)
371    }
372
373    /// Returns an iterator over all the unique wasm types defined thus far
374    /// within this builder.
375    pub fn wasm_types(&self) -> impl Iterator<Item = (ModuleInternedTypeIndex, &WasmSubType)> {
376        self.types.wasm_types()
377    }
378
379    /// Get an iterator over all function types and their associated trampoline
380    /// type.
381    pub fn trampoline_types(
382        &self,
383    ) -> impl Iterator<Item = (ModuleInternedTypeIndex, ModuleInternedTypeIndex)> + '_ {
384        self.types.trampoline_types()
385    }
386
387    /// Get the associated trampoline type for the given function type.
388    pub fn trampoline_type(&self, ty: ModuleInternedTypeIndex) -> ModuleInternedTypeIndex {
389        self.types.trampoline_type(ty)
390    }
391
392    /// Get and unwrap a [`WasmStructType`] for the given struct index.
393    ///
394    /// # Panics
395    ///
396    /// Panics if the unwrapped type is not a struct.
397    ///
398    /// # Errors
399    ///
400    /// For now, fails with an unsupported error if the type is shared.
401    pub fn unwrap_struct(&self, ty: ModuleInternedTypeIndex) -> WasmResult<&WasmStructType> {
402        let composite_type = &self.types[ty].composite_type;
403        if composite_type.shared {
404            return Err(wasm_unsupported!("shared structs are not yet implemented"));
405        }
406        Ok(composite_type.inner.unwrap_struct())
407    }
408
409    /// Get and unwrap a [`WasmArrayType`] for the given array index.
410    ///
411    /// # Panics
412    ///
413    /// Panics if the unwrapped type is not an array.
414    ///
415    /// # Errors
416    ///
417    /// For now, fails with an unsupported error if the type is shared.
418    pub fn unwrap_array(&self, interned_ty: ModuleInternedTypeIndex) -> WasmResult<&WasmArrayType> {
419        let composite_type = &self.types[interned_ty].composite_type;
420        if composite_type.shared {
421            return Err(wasm_unsupported!("shared arrays are not yet implemented"));
422        }
423        Ok(composite_type.inner.unwrap_array())
424    }
425
426    /// Get and unwrap a [`WasmExnType`] for the given exception-type index.
427    ///
428    /// # Panics
429    ///
430    /// Panics if the unwrapped type is not an exception type.
431    ///
432    /// # Errors
433    ///
434    /// For now, fails with an unsupported error if the type is shared.
435    pub fn unwrap_exn(&self, interned_ty: ModuleInternedTypeIndex) -> WasmResult<&WasmExnType> {
436        let composite_type = &self.types[interned_ty].composite_type;
437        if composite_type.shared {
438            return Err(wasm_unsupported!(
439                "shared exceptions are not yet implemented"
440            ));
441        }
442        Ok(composite_type.inner.unwrap_exn())
443    }
444
445    /// Get and unwrap a [`WasmFuncType`] for the given function-type index.
446    ///
447    /// # Panics
448    ///
449    /// Panics if the unwrapped type is not a function type.
450    ///
451    /// # Errors
452    ///
453    /// For now, fails with an unsupported error if the type is shared.
454    pub fn unwrap_func(&self, interned_ty: ModuleInternedTypeIndex) -> WasmResult<&WasmFuncType> {
455        let composite_type = &self.types[interned_ty].composite_type;
456        if composite_type.shared {
457            return Err(wasm_unsupported!(
458                "shared functions are not yet implemented"
459            ));
460        }
461        Ok(composite_type.inner.unwrap_func())
462    }
463}
464
465// Forward the indexing impl to the internal `ModuleTypes`
466impl<T> Index<T> for ModuleTypesBuilder
467where
468    ModuleTypes: Index<T>,
469{
470    type Output = <ModuleTypes as Index<T>>::Output;
471
472    fn index(&self, sig: T) -> &Self::Output {
473        &self.types[sig]
474    }
475}
476
477/// A convert from `wasmparser` types to Wasmtime types.
478pub struct WasmparserTypeConverter<'a, F> {
479    types: &'a ModuleTypesBuilder,
480    lookup_type_idx: F,
481    rec_group_context: Option<(
482        wasmparser::types::TypesRef<'a>,
483        wasmparser::types::RecGroupId,
484    )>,
485}
486
487impl<'a, F> WasmparserTypeConverter<'a, F> {
488    /// Construct a new type converter from `wasmparser` types to Wasmtime types.
489    pub fn new(types: &'a ModuleTypesBuilder, lookup_type_idx: F) -> Self {
490        Self {
491            types,
492            lookup_type_idx,
493            rec_group_context: None,
494        }
495    }
496
497    /// Configure this converter to be within the context of defining the
498    /// current rec group.
499    pub fn with_rec_group(
500        &mut self,
501        wasmparser_types: wasmparser::types::TypesRef<'a>,
502        rec_group: wasmparser::types::RecGroupId,
503    ) -> &Self {
504        self.rec_group_context = Some((wasmparser_types, rec_group));
505        self
506    }
507}
508
509impl<F> TypeConvert for WasmparserTypeConverter<'_, F>
510where
511    F: Fn(TypeIndex) -> ModuleInternedTypeIndex,
512{
513    fn lookup_heap_type(&self, index: UnpackedIndex) -> WasmHeapType {
514        match index {
515            UnpackedIndex::Id(id) => {
516                let interned = self.types.wasmparser_to_wasmtime[&id];
517                let index = EngineOrModuleTypeIndex::Module(interned);
518
519                // If this is a forward reference to a type in this type's rec
520                // group that we haven't converted yet, then we won't have an
521                // entry in `wasm_types` yet. In this case, fallback to a
522                // different means of determining whether this is a concrete
523                // array vs struct vs func reference. In this case, we can use
524                // the validator's type context.
525                if let Some(ty) = self.types.types.get(interned) {
526                    assert!(!ty.composite_type.shared);
527                    match &ty.composite_type.inner {
528                        WasmCompositeInnerType::Array(_) => WasmHeapType::ConcreteArray(index),
529                        WasmCompositeInnerType::Func(_) => WasmHeapType::ConcreteFunc(index),
530                        WasmCompositeInnerType::Struct(_) => WasmHeapType::ConcreteStruct(index),
531                        WasmCompositeInnerType::Cont(_) => WasmHeapType::ConcreteCont(index),
532                        WasmCompositeInnerType::Exn(_) => WasmHeapType::ConcreteExn(index),
533                    }
534                } else if let Some((wasmparser_types, _)) = self.rec_group_context.as_ref() {
535                    let wasmparser_ty = &wasmparser_types[id].composite_type;
536                    assert!(!wasmparser_ty.shared);
537                    match &wasmparser_ty.inner {
538                        wasmparser::CompositeInnerType::Array(_) => {
539                            WasmHeapType::ConcreteArray(index)
540                        }
541                        wasmparser::CompositeInnerType::Func(_) => {
542                            WasmHeapType::ConcreteFunc(index)
543                        }
544                        wasmparser::CompositeInnerType::Struct(_) => {
545                            WasmHeapType::ConcreteStruct(index)
546                        }
547                        wasmparser::CompositeInnerType::Cont(_) => {
548                            WasmHeapType::ConcreteCont(index)
549                        }
550                    }
551                } else {
552                    panic!("forward reference to type outside of rec group?")
553                }
554            }
555
556            UnpackedIndex::Module(module_index) => {
557                let module_index = TypeIndex::from_u32(module_index);
558                let interned = (self.lookup_type_idx)(module_index);
559                let index = EngineOrModuleTypeIndex::Module(interned);
560
561                // See comment above about `wasm_types` maybe not having the
562                // converted sub type yet. However in this case we don't have a
563                // `wasmparser::types::CoreTypeId` on hand, so we have to
564                // indirectly get one by looking it up inside the current rec
565                // group.
566                if let Some(ty) = self.types.types.get(interned) {
567                    assert!(!ty.composite_type.shared);
568                    match &ty.composite_type.inner {
569                        WasmCompositeInnerType::Array(_) => WasmHeapType::ConcreteArray(index),
570                        WasmCompositeInnerType::Func(_) => WasmHeapType::ConcreteFunc(index),
571                        WasmCompositeInnerType::Struct(_) => WasmHeapType::ConcreteStruct(index),
572                        WasmCompositeInnerType::Cont(_) => WasmHeapType::ConcreteCont(index),
573                        WasmCompositeInnerType::Exn(_) => WasmHeapType::ConcreteExn(index),
574                    }
575                } else if let Some((parser_types, rec_group)) = self.rec_group_context.as_ref() {
576                    let rec_group_index = interned.index() - self.types.types.len_types();
577                    let id = parser_types
578                        .rec_group_elements(*rec_group)
579                        .nth(rec_group_index)
580                        .unwrap();
581                    let wasmparser_ty = &parser_types[id].composite_type;
582                    assert!(!wasmparser_ty.shared);
583                    match &wasmparser_ty.inner {
584                        wasmparser::CompositeInnerType::Array(_) => {
585                            WasmHeapType::ConcreteArray(index)
586                        }
587                        wasmparser::CompositeInnerType::Func(_) => {
588                            WasmHeapType::ConcreteFunc(index)
589                        }
590                        wasmparser::CompositeInnerType::Struct(_) => {
591                            WasmHeapType::ConcreteStruct(index)
592                        }
593                        wasmparser::CompositeInnerType::Cont(_) => {
594                            WasmHeapType::ConcreteCont(index)
595                        }
596                    }
597                } else {
598                    panic!("forward reference to type outside of rec group?")
599                }
600            }
601
602            UnpackedIndex::RecGroup(_) => unreachable!(),
603        }
604    }
605
606    fn lookup_type_index(&self, index: wasmparser::UnpackedIndex) -> EngineOrModuleTypeIndex {
607        match index {
608            UnpackedIndex::Id(id) => {
609                let interned = self.types.wasmparser_to_wasmtime[&id];
610                EngineOrModuleTypeIndex::Module(interned)
611            }
612            UnpackedIndex::Module(module_index) => {
613                let module_index = TypeIndex::from_u32(module_index);
614                let interned = (self.lookup_type_idx)(module_index);
615                EngineOrModuleTypeIndex::Module(interned)
616            }
617            UnpackedIndex::RecGroup(_) => unreachable!(),
618        }
619    }
620}