wasm/core/structure/modules/
indices.rs

1//! # Type-safe Indices and Index Spaces
2//!
3//! Wasm specifies different classes of definitions (types, functions, globals,
4//! ...). Each definition can be uniquely addressed by a single index
5//! represented as a 32-bit integer. For every definition class, there exists a
6//! separate index space, along with a special index type per class: `typeidx` for
7//! types, `funcidx` for functions, etc.
8//!
9//! Using `u32` and `Vec` types to represent such indices and index spaces
10//! across all classes of definitions comes with risks.
11//!
12//! This module defines one newtype index type per definition class (e.g.
13//! [`TypeIdx`], [`FuncIdx`], [`GlobalIdx`]) and an index space [`IdxVec`].
14//!
15//! Additionally, the [`ExtendedIdxVec`] type is defined as to provide more
16//! methods on an [`IdxVec`] that consists of imported and locally-defined
17//! objects, i.e. functions, globals, tables and memories.
18//!
19//! # What this module is not
20//!
21//! However, this module cannot ensure that an index type is always used for the
22//! [`IdxVec`] it originally came from. Imagine a scenario, in which multiple
23//! Wasm modules are used. Even though it would not make any sense to use
24//! indices across multiple index spaces of the same definition class, detecting
25//! such mis-use is out of the scope of this module.
26//!
27//! Instead, the caller must guarantee that indices are only used together with
28//! the correct index space. These guarantees are documented in the form of
29//! safety requirements.
30//!
31//! See: WebAssembly Specification - 2.5.1 - Indices
32
33use alloc::{boxed::Box, vec::Vec};
34use core::marker::PhantomData;
35
36use crate::core::utils::ToUsizeExt;
37
38/// A trait for all index types.
39///
40/// This is used by [`IdxVec`] to create and read index types.
41pub trait Idx: Copy + core::fmt::Debug + core::fmt::Display + Eq {
42    fn new(index: u32) -> Self;
43
44    fn into_inner(self) -> u32;
45}
46
47/// An immutable vector that can only be indexed by type-safe 32-bit indices.
48///
49/// Use [`IdxVec::new`] or [`IdxVec::default`] to create a new instance.
50pub struct IdxVec<I: Idx, T> {
51    inner: Box<[T]>,
52    _phantom: PhantomData<I>,
53}
54
55impl<I: Idx, T> Default for IdxVec<I, T> {
56    fn default() -> Self {
57        Self {
58            inner: Box::default(),
59            _phantom: PhantomData,
60        }
61    }
62}
63
64impl<I: Idx, T: Clone> Clone for IdxVec<I, T> {
65    fn clone(&self) -> Self {
66        Self {
67            inner: self.inner.clone(),
68            _phantom: PhantomData,
69        }
70    }
71}
72
73impl<I: Idx, T: core::fmt::Debug> core::fmt::Debug for IdxVec<I, T> {
74    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
75        f.debug_list().entries(&*self.inner).finish()
76    }
77}
78
79/// An error for when an [`IdxVec`] is initialized with too many elements.
80#[derive(Debug)]
81pub struct IdxVecOverflowError;
82
83impl<I: Idx, T> IdxVec<I, T> {
84    /// Creates a new [`IdxVec`] with the given elements in it.
85    ///
86    /// If the number of elements is larger than what can be addressed by a
87    /// `u32`, i.e. `u32::MAX`, an error is returned instead.
88    pub fn new(elements: Vec<T>) -> Result<Self, IdxVecOverflowError> {
89        if u32::try_from(elements.len()).is_err() {
90            return Err(IdxVecOverflowError);
91        }
92
93        Ok(Self {
94            inner: elements.into_boxed_slice(),
95            _phantom: PhantomData,
96        })
97    }
98
99    pub(crate) fn validate_index(&self, index: u32) -> Option<I> {
100        let index_as_usize = index.into_usize();
101        let _element = self.inner.get(index_as_usize)?;
102        Some(I::new(index))
103    }
104
105    /// Gets an element from this vector by its index.
106    ///
107    /// # Safety
108    ///
109    /// The caller must ensure that the index object was validated using the
110    /// same vector as `self` or a different vector used to create `self`
111    /// through [`IdxVec::map`].
112    pub unsafe fn get(&self, index: I) -> &T {
113        let index = index.into_inner().into_usize();
114
115        // TODO use `unwrap_unchecked` when we are sure everything is sound and
116        // our validation is properly tested
117        self.inner
118            .get(index)
119            .expect("this to be a valid index due to the safety guarantees made by the caller")
120    }
121
122    #[allow(unused)] // reason = "temporary until used by new index types"
123    pub fn len(&self) -> u32 {
124        u32::try_from(self.inner.len()).expect(
125            "this to never be larger than u32::MAX, because this was checked for in Self::new",
126        )
127    }
128
129    pub fn iter_enumerated(&self) -> impl Iterator<Item = (I, &T)> {
130        self.inner.iter().enumerate().map(|(index, t)| {
131            (
132                I::new(
133                    u32::try_from(index)
134                        .expect("this vector to contain a maximum of 2^32-1 elements"),
135                ),
136                t,
137            )
138        })
139    }
140
141    /// Creates an equivalent index space for one that already exists while
142    /// allowing elements to be mapped.
143    pub fn map<R, E>(&self, mapper: impl FnMut(&T) -> Result<R, E>) -> Result<IdxVec<I, R>, E> {
144        Ok(IdxVec {
145            inner: self
146                .inner
147                .iter()
148                .map(mapper)
149                .collect::<Result<Box<[R]>, E>>()?,
150            _phantom: PhantomData,
151        })
152    }
153}
154
155/// Index space for definitions that consist of imports and locals.
156#[derive(Debug)]
157pub struct ExtendedIdxVec<I: Idx, T> {
158    inner: IdxVec<I, T>,
159    num_imports: u32,
160}
161
162impl<I: Idx, T> Default for ExtendedIdxVec<I, T> {
163    fn default() -> Self {
164        Self {
165            inner: IdxVec::default(),
166            num_imports: 0,
167        }
168    }
169}
170
171impl<I: Idx, T: Clone> Clone for ExtendedIdxVec<I, T> {
172    fn clone(&self) -> Self {
173        Self {
174            inner: self.inner.clone(),
175            num_imports: self.num_imports,
176        }
177    }
178}
179
180impl<I: Idx, T> ExtendedIdxVec<I, T> {
181    /// Creates a new [`IdxVec`] with the given imported and local elements in
182    /// it.
183    ///
184    /// If the number of total elements is larger than what can be addressed by
185    /// a `u32`, i.e. `u32::MAX` elements, an error is returned instead.
186    pub fn new(imports: Vec<T>, locals: Vec<T>) -> Result<Self, IdxVecOverflowError> {
187        let num_imports = u32::try_from(imports.len()).map_err(|_| IdxVecOverflowError)?;
188
189        let mut combined = imports;
190        combined.extend(locals);
191
192        Ok(Self {
193            inner: IdxVec::new(combined)?,
194            num_imports,
195        })
196    }
197
198    /// Returns the length of the locally-defined definitions part of this index
199    /// space
200    pub fn len_local_definitions(&self) -> u32 {
201        self.inner
202            .len()
203            .checked_sub(self.num_imports)
204            .expect("that the number of imports is never larger than the total length of self")
205    }
206
207    /// Creates an equivalent index space for one that already exists while
208    /// allowing elements to be mapped.
209    ///
210    /// Returns `None` if lengths do not match.
211    // TODO maybe make this method take iterators instead of vectors
212    pub fn map<R>(
213        &self,
214        new_imported_definitions: Vec<R>,
215        new_local_definitions: Vec<R>,
216    ) -> Option<ExtendedIdxVec<I, R>> {
217        if new_imported_definitions.len() != self.num_imports.into_usize()
218            || u32::try_from(new_local_definitions.len()).ok()? != self.len_local_definitions()
219        {
220            return None;
221        }
222
223        Some(
224            ExtendedIdxVec::new(new_imported_definitions, new_local_definitions)
225                .expect("no overflow can happen because the length did not change"),
226        )
227    }
228
229    pub fn iter_local_definitions(&self) -> core::slice::Iter<'_, T> {
230        self.inner
231            .inner
232            .get(self.num_imports.into_usize()..)
233            .expect("the imports length to never be larger than the total length")
234            .iter()
235    }
236
237    pub fn inner(&self) -> &IdxVec<I, T> {
238        &self.inner
239    }
240
241    pub fn into_inner(self) -> IdxVec<I, T> {
242        self.inner
243    }
244}
245
246/// A type index that is used to index into the types index space of some Wasm
247/// module or module instance.
248///
249/// All Wasm indices, including this one, follow a type-state pattern. Refer to
250/// [`indices`](crate::core::structure::modules::indices) for more information on this topic.
251///
252/// See: WebAssembly Specification 2.0 - 2.5.1 - Indices
253#[derive(Copy, Clone, Debug, PartialEq, Eq)]
254pub struct TypeIdx(u32);
255
256impl core::fmt::Display for TypeIdx {
257    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
258        write!(f, "type index {}", self.0)
259    }
260}
261
262impl Idx for TypeIdx {
263    fn new(index: u32) -> Self {
264        Self(index)
265    }
266
267    fn into_inner(self) -> u32 {
268        self.0
269    }
270}
271
272impl TypeIdx {
273    /// Creates a new type index directly from some index.
274    ///
275    /// Note: This constructor is only available for type indices, since these
276    /// are the only indices that can be encoded using special 33-bit integers.
277    pub fn new(index: u32) -> Self {
278        Self(index)
279    }
280}
281
282#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
283pub struct FuncIdx(u32);
284
285impl core::fmt::Display for FuncIdx {
286    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
287        write!(f, "function index {}", self.0)
288    }
289}
290
291impl Idx for FuncIdx {
292    fn new(index: u32) -> Self {
293        Self(index)
294    }
295
296    fn into_inner(self) -> u32 {
297        self.0
298    }
299}
300
301#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
302pub struct TableIdx(u32);
303
304impl core::fmt::Display for TableIdx {
305    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
306        write!(f, "table index {}", self.0)
307    }
308}
309
310impl Idx for TableIdx {
311    fn new(index: u32) -> Self {
312        Self(index)
313    }
314
315    fn into_inner(self) -> u32 {
316        self.0
317    }
318}
319
320#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
321pub struct MemIdx(u32);
322
323impl core::fmt::Display for MemIdx {
324    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
325        write!(f, "memory index {}", self.0)
326    }
327}
328
329impl Idx for MemIdx {
330    fn new(index: u32) -> Self {
331        Self(index)
332    }
333
334    fn into_inner(self) -> u32 {
335        self.0
336    }
337}
338
339#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
340pub struct GlobalIdx(u32);
341
342impl core::fmt::Display for GlobalIdx {
343    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
344        write!(f, "global index {}", self.0)
345    }
346}
347
348impl Idx for GlobalIdx {
349    fn new(index: u32) -> Self {
350        Self(index)
351    }
352
353    fn into_inner(self) -> u32 {
354        self.0
355    }
356}
357
358#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
359pub struct ElemIdx(u32);
360
361impl core::fmt::Display for ElemIdx {
362    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
363        write!(f, "element index {}", self.0)
364    }
365}
366
367impl Idx for ElemIdx {
368    fn new(index: u32) -> Self {
369        Self(index)
370    }
371
372    fn into_inner(self) -> u32 {
373        self.0
374    }
375}
376
377#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
378pub struct DataIdx(u32);
379
380impl core::fmt::Display for DataIdx {
381    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
382        write!(f, "data index {}", self.0)
383    }
384}
385
386impl Idx for DataIdx {
387    fn new(index: u32) -> Self {
388        Self(index)
389    }
390
391    fn into_inner(self) -> u32 {
392        self.0
393    }
394}
395
396#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
397pub struct LocalIdx(pub(crate) u32);
398
399impl core::fmt::Display for LocalIdx {
400    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
401        write!(f, "local index {}", self.0)
402    }
403}
404
405impl LocalIdx {
406    pub fn into_inner(self) -> u32 {
407        self.0
408    }
409}
wasm/core/structure/modules/indices.rs

wasm/core/structure/modules/
indices.rs
