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

wasm/core/
indices.rs
