wasm/core/
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 core::marker::PhantomData;
34
35use alloc::{boxed::Box, vec::Vec};
36
37use crate::{
38    core::{
39        reader::{types::FuncType, WasmReader},
40        utils::ToUsizeExt,
41    },
42    ValType, ValidationError,
43};
44
45/// A trait for all index types.
46///
47/// This is used by [`IdxVec`] to create and read index types.
48pub trait Idx: Copy + core::fmt::Debug + core::fmt::Display + Eq {
49    fn new(index: u32) -> Self;
50
51    fn into_inner(self) -> u32;
52}
53
54/// An immutable vector that can only be indexed by type-safe 32-bit indices.
55///
56/// Use [`IdxVec::new`] or [`IdxVec::default`] to create a new instance.
57pub struct IdxVec<I: Idx, T> {
58    inner: Box<[T]>,
59    _phantom: PhantomData<I>,
60}
61
62impl<I: Idx, T> Default for IdxVec<I, T> {
63    fn default() -> Self {
64        Self {
65            inner: Box::default(),
66            _phantom: PhantomData,
67        }
68    }
69}
70
71impl<I: Idx, T: Clone> Clone for IdxVec<I, T> {
72    fn clone(&self) -> Self {
73        Self {
74            inner: self.inner.clone(),
75            _phantom: PhantomData,
76        }
77    }
78}
79
80impl<I: Idx, T: core::fmt::Debug> core::fmt::Debug for IdxVec<I, T> {
81    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
82        f.debug_list().entries(&*self.inner).finish()
83    }
84}
85
86/// An error for when an [`IdxVec`] is initialized with too many elements.
87#[derive(Debug)]
88pub struct IdxVecOverflowError;
89
90impl<I: Idx, T> IdxVec<I, T> {
91    /// Creates a new [`IdxVec`] with the given elements in it.
92    ///
93    /// If the number of elements is larger than what can be addressed by a
94    /// `u32`, i.e. `u32::MAX`, an error is returned instead.
95    pub fn new(elements: Vec<T>) -> Result<Self, IdxVecOverflowError> {
96        if u32::try_from(elements.len()).is_err() {
97            return Err(IdxVecOverflowError);
98        }
99
100        Ok(Self {
101            inner: elements.into_boxed_slice(),
102            _phantom: PhantomData,
103        })
104    }
105
106    fn validate_index(&self, index: u32) -> Option<I> {
107        let index_as_usize = index.into_usize();
108        let _element = self.inner.get(index_as_usize)?;
109        Some(I::new(index))
110    }
111
112    /// Gets an element from this vector by its index.
113    ///
114    /// # Safety
115    ///
116    /// The caller must ensure that the index object was validated using the
117    /// same vector as `self` or a different vector used to create `self`
118    /// through [`IdxVec::map`].
119    pub unsafe fn get(&self, index: I) -> &T {
120        let index = index.into_inner().into_usize();
121
122        // TODO use `unwrap_unchecked` when we are sure everything is sound and
123        // our validation is properly tested
124        self.inner
125            .get(index)
126            .expect("this to be a valid index due to the safety guarantees made by the caller")
127    }
128
129    #[allow(unused)] // reason = "temporary until used by new index types"
130    pub fn len(&self) -> u32 {
131        u32::try_from(self.inner.len()).expect(
132            "this to never be larger than u32::MAX, because this was checked for in Self::new",
133        )
134    }
135
136    pub fn iter_enumerated(&self) -> impl Iterator<Item = (I, &T)> {
137        self.inner.iter().enumerate().map(|(index, t)| {
138            (
139                I::new(
140                    u32::try_from(index)
141                        .expect("this vector to contain a maximum of 2^32-1 elements"),
142                ),
143                t,
144            )
145        })
146    }
147
148    /// Creates an equivalent index space for one that already exists while
149    /// allowing elements to be mapped.
150    pub fn map<R, E>(&self, mapper: impl FnMut(&T) -> Result<R, E>) -> Result<IdxVec<I, R>, E> {
151        Ok(IdxVec {
152            inner: self
153                .inner
154                .iter()
155                .map(mapper)
156                .collect::<Result<Box<[R]>, E>>()?,
157            _phantom: PhantomData,
158        })
159    }
160}
161
162/// Index space for definitions that consist of imports and locals.
163#[derive(Debug)]
164pub struct ExtendedIdxVec<I: Idx, T> {
165    inner: IdxVec<I, T>,
166    num_imports: u32,
167}
168
169impl<I: Idx, T> Default for ExtendedIdxVec<I, T> {
170    fn default() -> Self {
171        Self {
172            inner: IdxVec::default(),
173            num_imports: 0,
174        }
175    }
176}
177
178impl<I: Idx, T: Clone> Clone for ExtendedIdxVec<I, T> {
179    fn clone(&self) -> Self {
180        Self {
181            inner: self.inner.clone(),
182            num_imports: self.num_imports,
183        }
184    }
185}
186
187impl<I: Idx, T> ExtendedIdxVec<I, T> {
188    /// Creates a new [`IdxVec`] with the given imported and local elements in
189    /// it.
190    ///
191    /// If the number of total elements is larger than what can be addressed by
192    /// a `u32`, i.e. `u32::MAX` elements, an error is returned instead.
193    pub fn new(imports: Vec<T>, locals: Vec<T>) -> Result<Self, IdxVecOverflowError> {
194        let num_imports = u32::try_from(imports.len()).map_err(|_| IdxVecOverflowError)?;
195
196        let mut combined = imports;
197        combined.extend(locals);
198
199        Ok(Self {
200            inner: IdxVec::new(combined)?,
201            num_imports,
202        })
203    }
204
205    /// Returns the length of the locally-defined definitions part of this index
206    /// space
207    pub fn len_local_definitions(&self) -> u32 {
208        self.inner
209            .len()
210            .checked_sub(self.num_imports)
211            .expect("that the number of imports is never larger than the total length of self")
212    }
213
214    /// Creates an equivalent index space for one that already exists while
215    /// allowing elements to be mapped.
216    ///
217    /// Returns `None` if lengths do not match.
218    // TODO maybe make this method take iterators instead of vectors
219    pub fn map<R>(
220        &self,
221        new_imported_definitions: Vec<R>,
222        new_local_definitions: Vec<R>,
223    ) -> Option<ExtendedIdxVec<I, R>> {
224        if new_imported_definitions.len() != self.num_imports.into_usize()
225            || u32::try_from(new_local_definitions.len()).ok()? != self.len_local_definitions()
226        {
227            return None;
228        }
229
230        Some(
231            ExtendedIdxVec::new(new_imported_definitions, new_local_definitions)
232                .expect("no overflow can happen because the length did not change"),
233        )
234    }
235
236    pub fn iter_local_definitions(&self) -> core::slice::Iter<'_, T> {
237        self.inner
238            .inner
239            .get(self.num_imports.into_usize()..)
240            .expect("the imports length to never be larger than the total length")
241            .iter()
242    }
243
244    pub fn inner(&self) -> &IdxVec<I, T> {
245        &self.inner
246    }
247
248    pub fn into_inner(self) -> IdxVec<I, T> {
249        self.inner
250    }
251}
252
253/// A type index that is used to index into the types index space of some Wasm
254/// module or module instance.
255///
256/// All Wasm indices, including this one, follow a type-state pattern. Refer to
257/// [`indices`](crate::core::indices) for more information on this topic.
258///
259/// See: WebAssembly Specification 2.0 - 2.5.1 - Indices
260#[derive(Copy, Clone, Debug, PartialEq, Eq)]
261pub struct TypeIdx(u32);
262
263impl core::fmt::Display for TypeIdx {
264    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
265        write!(f, "type index {}", self.0)
266    }
267}
268
269impl Idx for TypeIdx {
270    fn new(index: u32) -> Self {
271        Self(index)
272    }
273
274    fn into_inner(self) -> u32 {
275        self.0
276    }
277}
278
279impl TypeIdx {
280    /// Creates a new type index directly from some index.
281    ///
282    /// Note: This constructor is only available for type indices, since these
283    /// are the only indices that can be encoded using special 33-bit integers.
284    pub fn new(index: u32) -> Self {
285        Self(index)
286    }
287
288    /// Validates that a given index is a valid type index.
289    ///
290    /// On success a new [`TypeIdx`] is returned, otherwise a
291    /// [`ValidationError`] is returned.
292    pub fn validate(
293        index: u32,
294        c_types: &IdxVec<TypeIdx, FuncType>,
295    ) -> Result<Self, ValidationError> {
296        c_types
297            .validate_index(index)
298            .ok_or(ValidationError::InvalidTypeIdx(index))
299    }
300
301    /// Reads a type index from Wasm code and validates that it is a valid index
302    /// for a given types vector.
303    pub fn read_and_validate(
304        wasm: &mut WasmReader,
305        c_types: &IdxVec<TypeIdx, FuncType>,
306    ) -> Result<Self, ValidationError> {
307        let index = wasm.read_var_u32()?;
308        Self::validate(index, c_types)
309    }
310
311    /// Reads a type index from Wasm code without validating it. Using the
312    /// returned type requires some other form of validation to be done.
313    ///
314    /// # Safety
315    ///
316    /// The caller must ensure that there is a valid type index in the
317    /// [`WasmReader`].
318    pub unsafe fn read_unchecked(wasm: &mut WasmReader) -> Self {
319        let index = wasm.read_var_u32().unwrap();
320        Self::new(index)
321    }
322}
323
324#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
325pub struct FuncIdx(u32);
326
327impl core::fmt::Display for FuncIdx {
328    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
329        write!(f, "function index {}", self.0)
330    }
331}
332
333impl Idx for FuncIdx {
334    fn new(index: u32) -> Self {
335        Self(index)
336    }
337
338    fn into_inner(self) -> u32 {
339        self.0
340    }
341}
342
343impl FuncIdx {
344    /// Validates that a given index is a valid function index.
345    ///
346    /// On success a new [`FuncIdx`] is returned, otherwise a
347    /// [`ValidationError`] is returned.
348    pub fn validate<T>(index: u32, c_funcs: &IdxVec<FuncIdx, T>) -> Result<Self, ValidationError> {
349        c_funcs
350            .validate_index(index)
351            .ok_or(ValidationError::InvalidFuncIdx(index))
352    }
353
354    /// Reads a function index from Wasm code and validates that it is a valid
355    /// index for a given functions vector.
356    pub fn read_and_validate<T>(
357        wasm: &mut WasmReader,
358        c_funcs: &IdxVec<FuncIdx, T>,
359    ) -> Result<Self, ValidationError> {
360        let index = wasm.read_var_u32()?;
361        Self::validate(index, c_funcs)
362    }
363
364    /// Reads a function index from Wasm code without validating it.
365    ///
366    /// # Safety
367    ///
368    /// The caller must ensure that there is a valid function index in the
369    /// [`WasmReader`] and that this index is valid for a specific [`IdxVec`]
370    /// through [`Self::read_and_validate`].
371    pub unsafe fn read_unchecked(wasm: &mut WasmReader) -> Self {
372        let index = wasm.read_var_u32().unwrap();
373        Self::new(index)
374    }
375}
376
377#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
378pub struct TableIdx(u32);
379
380impl core::fmt::Display for TableIdx {
381    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
382        write!(f, "table index {}", self.0)
383    }
384}
385
386impl Idx for TableIdx {
387    fn new(index: u32) -> Self {
388        Self(index)
389    }
390
391    fn into_inner(self) -> u32 {
392        self.0
393    }
394}
395
396impl TableIdx {
397    /// Validates that a given index is a valid table index.
398    ///
399    /// On success a new [`TableIdx`] is returned, otherwise a
400    /// [`ValidationError`] is returned.
401    pub fn validate<T>(
402        index: u32,
403        c_tables: &IdxVec<TableIdx, T>,
404    ) -> Result<Self, ValidationError> {
405        c_tables
406            .validate_index(index)
407            .ok_or(ValidationError::InvalidTableIdx(index))
408    }
409
410    /// Reads a table index from Wasm code and validates that it is a valid
411    /// index for a given tables vector.
412    pub fn read_and_validate<T>(
413        wasm: &mut WasmReader,
414        c_tables: &IdxVec<TableIdx, T>,
415    ) -> Result<Self, ValidationError> {
416        let index = wasm.read_var_u32()?;
417        Self::validate(index, c_tables)
418    }
419
420    /// Reads a table index from Wasm code without validating it.
421    ///
422    /// # Safety
423    ///
424    /// The caller must ensure that there is a valid table index in the
425    /// [`WasmReader`] and that this index is valid for a specific [`ExtendedIdxVec`]
426    /// through [`Self::read_and_validate`].
427    pub unsafe fn read_unchecked(wasm: &mut WasmReader) -> Self {
428        let index = wasm.read_var_u32().unwrap();
429        Self::new(index)
430    }
431}
432
433#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
434pub struct MemIdx(u32);
435
436impl core::fmt::Display for MemIdx {
437    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
438        write!(f, "memory index {}", self.0)
439    }
440}
441
442impl Idx for MemIdx {
443    fn new(index: u32) -> Self {
444        Self(index)
445    }
446
447    fn into_inner(self) -> u32 {
448        self.0
449    }
450}
451
452impl MemIdx {
453    /// Validates that a given index is a valid memory index.
454    ///
455    /// On success a new [`MemIdx`] is returned, otherwise a [`ValidationError`]
456    /// is returned.
457    pub fn validate<T>(index: u32, c_mems: &IdxVec<MemIdx, T>) -> Result<Self, ValidationError> {
458        c_mems
459            .validate_index(index)
460            .ok_or(ValidationError::InvalidMemIdx(index))
461    }
462
463    /// Reads a memory index from Wasm code and validates that it is a valid
464    /// index for a given memories vector.
465    pub fn read_and_validate<T>(
466        wasm: &mut WasmReader,
467        c_mems: &IdxVec<MemIdx, T>,
468    ) -> Result<Self, ValidationError> {
469        let index = wasm.read_var_u32()?;
470        Self::validate(index, c_mems)
471    }
472
473    /// Reads a memory index from Wasm code without validating it.
474    ///
475    /// # Safety
476    ///
477    /// The caller must ensure that there is a valid memory index in the
478    /// [`WasmReader`] and that this index is valid for a specific [`ExtendedIdxVec`]
479    /// through [`Self::read_and_validate`].
480    #[allow(unused)] // reason = "unused until multiple memories proposal is implemented"
481    pub unsafe fn read_unchecked(wasm: &mut WasmReader) -> Self {
482        let index = wasm.read_var_u32().unwrap();
483        Self::new(index)
484    }
485}
486
487#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
488pub struct GlobalIdx(u32);
489
490impl core::fmt::Display for GlobalIdx {
491    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
492        write!(f, "global index {}", self.0)
493    }
494}
495
496impl Idx for GlobalIdx {
497    fn new(index: u32) -> Self {
498        Self(index)
499    }
500
501    fn into_inner(self) -> u32 {
502        self.0
503    }
504}
505
506impl GlobalIdx {
507    /// Validates that a given index is a valid global index.
508    ///
509    /// On success a new [`GlobalIdx`] is returned, otherwise a
510    /// [`ValidationError`] is returned.
511    pub fn validate<T>(
512        index: u32,
513        c_globals: &IdxVec<GlobalIdx, T>,
514    ) -> Result<Self, ValidationError> {
515        c_globals
516            .validate_index(index)
517            .ok_or(ValidationError::InvalidGlobalIdx(index))
518    }
519
520    /// Reads a global index from Wasm code and validates that it is a valid
521    /// index for a given globals vector.
522    pub fn read_and_validate<T>(
523        wasm: &mut WasmReader,
524        c_globals: &IdxVec<GlobalIdx, T>,
525    ) -> Result<Self, ValidationError> {
526        let index = wasm.read_var_u32()?;
527        Self::validate(index, c_globals)
528    }
529
530    /// Reads a global index from Wasm code without validating it.
531    ///
532    /// # Safety
533    ///
534    /// The caller must ensure that there is a valid global index in the
535    /// [`WasmReader`] and that this index is valid for a specific [`IdxVec`]
536    /// through [`Self::read_and_validate`] or [`Self::validate`].
537    pub unsafe fn read_unchecked(wasm: &mut WasmReader) -> Self {
538        let index = wasm.read_var_u32().unwrap();
539        Self::new(index)
540    }
541}
542
543#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
544pub struct ElemIdx(u32);
545
546impl core::fmt::Display for ElemIdx {
547    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
548        write!(f, "element index {}", self.0)
549    }
550}
551
552impl Idx for ElemIdx {
553    fn new(index: u32) -> Self {
554        Self(index)
555    }
556
557    fn into_inner(self) -> u32 {
558        self.0
559    }
560}
561
562impl ElemIdx {
563    /// Validates that a given index is a valid element index.
564    ///
565    /// On success a new [`ElemIdx`] is returned, otherwise a
566    /// [`ValidationError`] is returned.
567    pub fn validate<T>(index: u32, c_elems: &IdxVec<ElemIdx, T>) -> Result<Self, ValidationError> {
568        c_elems
569            .validate_index(index)
570            .ok_or(ValidationError::InvalidElemIdx(index))
571    }
572
573    /// Reads an element index from Wasm code and validates that it is a valid
574    /// index for a given elements vector.
575    pub fn read_and_validate<T>(
576        wasm: &mut WasmReader,
577        c_elems: &IdxVec<ElemIdx, T>,
578    ) -> Result<Self, ValidationError> {
579        let index = wasm.read_var_u32()?;
580        Self::validate(index, c_elems)
581    }
582
583    /// Reads an element index from Wasm code without validating it.
584    ///
585    /// # Safety
586    ///
587    /// The caller must ensure that there is a valid element index in the
588    /// [`WasmReader`] and that this index is valid for a specific [`IdxVec`]
589    /// through [`Self::read_and_validate`] or [`Self::validate`].
590    pub unsafe fn read_unchecked(wasm: &mut WasmReader) -> Self {
591        let index = wasm.read_var_u32().unwrap();
592        Self::new(index)
593    }
594}
595
596#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
597pub struct DataIdx(u32);
598
599impl core::fmt::Display for DataIdx {
600    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
601        write!(f, "data index {}", self.0)
602    }
603}
604
605impl Idx for DataIdx {
606    fn new(index: u32) -> Self {
607        Self(index)
608    }
609
610    fn into_inner(self) -> u32 {
611        self.0
612    }
613}
614
615impl DataIdx {
616    /// Validates that a given index is a valid data index.
617    ///
618    /// On success a new [`DataIdx`] is returned, otherwise a
619    /// [`ValidationError`] is returned.
620    pub fn validate(index: u32, data_count: u32) -> Result<Self, ValidationError> {
621        (index < data_count)
622            .then_some(Self(index))
623            .ok_or(ValidationError::InvalidDataIdx(index))
624    }
625
626    /// Reads a data index from Wasm code and validates that it is a valid
627    /// by comparing it to the total number of data segments.
628    pub fn read_and_validate(
629        wasm: &mut WasmReader,
630        data_count: u32,
631    ) -> Result<Self, ValidationError> {
632        let index = wasm.read_var_u32()?;
633        Self::validate(index, data_count)
634    }
635
636    /// Reads a data index from Wasm code without validating it.
637    ///
638    /// # Safety
639    ///
640    /// The caller must ensure that there is a valid data index in the
641    /// [`WasmReader`] and that this index is valid for a specific [`IdxVec`]
642    /// through [`Self::read_and_validate`] or [`Self::validate`].
643    pub unsafe fn read_unchecked(wasm: &mut WasmReader) -> Self {
644        let index = wasm.read_var_u32().unwrap();
645        Self::new(index)
646    }
647}
648
649#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
650pub struct LocalIdx(u32);
651
652impl core::fmt::Display for LocalIdx {
653    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
654        write!(f, "local index {}", self.0)
655    }
656}
657
658impl LocalIdx {
659    pub fn into_inner(self) -> u32 {
660        self.0
661    }
662
663    /// Reads a local index from Wasm code and validates that it is valid for a
664    /// given slice of locals.
665    pub fn read_and_validate(
666        wasm: &mut WasmReader,
667        locals_of_current_function: &[ValType],
668    ) -> Result<Self, ValidationError> {
669        let index = wasm.read_var_u32()?;
670        let index_as_usize = usize::try_from(index).expect("architecture to be at least 32 bits");
671
672        match locals_of_current_function.get(index_as_usize) {
673            Some(_local) => Ok(Self(index)),
674            None => Err(ValidationError::InvalidLocalIdx(index)),
675        }
676    }
677
678    /// Reads a local index from Wasm code without validating it.
679    ///
680    /// # Safety
681    ///
682    /// The caller must ensure that there is a valid local index in the
683    /// [`WasmReader`].
684    pub unsafe fn read_unchecked(wasm: &mut WasmReader) -> Self {
685        let index = wasm.read_var_u32().unwrap();
686        Self(index)
687    }
688}
689
690/// Reads a label index from Wasm code without validating it.
691pub fn read_label_idx(wasm: &mut WasmReader) -> Result<u32, ValidationError> {
692    wasm.read_var_u32()
693}
694
695/// Reads a label index from Wasm code without validating it.
696///
697/// # Safety
698///
699/// The caller must ensure that there is a valid label index in the
700/// [`WasmReader`].
701pub unsafe fn read_label_idx_unchecked(wasm: &mut WasmReader) -> u32 {
702    // TODO use `unwrap_unchecked` instead
703    wasm.read_var_u32().unwrap()
704}
wasm/core/indices.rs

wasm/core/
indices.rs
