wasm_types/
flat_vector.rs

1//! The flat vector is a vector of fixed-size elements that we want to expose directly to js-of-ocaml
2//! (so that we can access a `Vec<Field>` cheaply,
3//! by just passing a pointer to a continuous memory region instead of copying.
4//! The wasmvector is a normal heap-allocated vector,
5//! where we leave it on the rust heap and just keep a pointer around.
6//! We use flat for fields, normal for gates etc.
7//!
8//! Accessing Rust vector values is not the same as accessing an array.
9//! Each indexing (e.g. `some_vec[3]`) is costly as it is implemented as a function call.
10//! Knowing that, plus the fact that field elements are implemented as `[u32; 8]`, we know that we incur the cost of following several pointers.
11//! To decrease that cost, we flatten such arrays, going from something like
12//!
13//! ```ignore
14//! [[a0, a1, ..., a7], [b0, b1, ..., b7], ...]
15//! ```
16//!
17//! to a flattened vector like:
18//!
19//! ```ignore
20//! [a0, a1, ..., a7, b0, b1, ..., b7, ...]
21//! ```
22
23extern crate alloc;
24
25use wasm_bindgen::convert::{FromWasmAbi, IntoWasmAbi, OptionFromWasmAbi, OptionIntoWasmAbi};
26
27use alloc::vec::Vec;
28use core::{convert::From, ops::Deref};
29
30#[derive(Clone, Debug)]
31pub struct FlatVector<T>(Vec<T>);
32
33impl<T: FlatVectorElem> FlatVector<T> {
34    #[must_use]
35    pub fn from_bytes(data: Vec<u8>) -> Self {
36        let mut res: Vec<T> = Vec::with_capacity(data.len() / T::FLATTENED_SIZE);
37
38        let mut buf = Vec::with_capacity(T::FLATTENED_SIZE);
39
40        for x in data {
41            assert!(buf.len() < T::FLATTENED_SIZE);
42
43            buf.push(x);
44
45            if buf.len() >= T::FLATTENED_SIZE {
46                res.push(T::unflatten(buf));
47                buf = Vec::with_capacity(T::FLATTENED_SIZE);
48            }
49        }
50
51        assert_eq!(buf.len(), 0);
52
53        FlatVector(res)
54    }
55}
56
57pub trait FlatVectorElem {
58    const FLATTENED_SIZE: usize;
59    fn flatten(self) -> Vec<u8>;
60    fn unflatten(flat: Vec<u8>) -> Self;
61}
62
63impl<T> Deref for FlatVector<T> {
64    type Target = Vec<T>;
65
66    fn deref(&self) -> &Self::Target {
67        &self.0
68    }
69}
70
71impl<T> From<Vec<T>> for FlatVector<T> {
72    fn from(x: Vec<T>) -> Self {
73        FlatVector(x)
74    }
75}
76
77impl<T> From<FlatVector<T>> for Vec<T> {
78    fn from(x: FlatVector<T>) -> Self {
79        x.0
80    }
81}
82
83impl<'a, T> From<&'a FlatVector<T>> for &'a Vec<T> {
84    fn from(x: &'a FlatVector<T>) -> Self {
85        &x.0
86    }
87}
88
89impl<T> core::iter::IntoIterator for FlatVector<T> {
90    type Item = <Vec<T> as core::iter::IntoIterator>::Item;
91    type IntoIter = <Vec<T> as core::iter::IntoIterator>::IntoIter;
92    fn into_iter(self) -> Self::IntoIter {
93        self.0.into_iter()
94    }
95}
96
97impl<'a, T> core::iter::IntoIterator for &'a FlatVector<T> {
98    type Item = <&'a Vec<T> as core::iter::IntoIterator>::Item;
99    type IntoIter = <&'a Vec<T> as core::iter::IntoIterator>::IntoIter;
100    fn into_iter(self) -> Self::IntoIter {
101        self.0.iter()
102    }
103}
104
105impl<T> core::iter::FromIterator<T> for FlatVector<T> {
106    fn from_iter<I>(iter: I) -> FlatVector<T>
107    where
108        I: IntoIterator<Item = T>,
109    {
110        FlatVector(core::iter::FromIterator::from_iter(iter))
111    }
112}
113
114impl<T> core::default::Default for FlatVector<T> {
115    fn default() -> Self {
116        FlatVector(core::default::Default::default())
117    }
118}
119
120impl<T> core::iter::Extend<T> for FlatVector<T> {
121    fn extend<I>(&mut self, iter: I)
122    where
123        I: IntoIterator<Item = T>,
124    {
125        self.0.extend(iter);
126    }
127}
128
129impl<T> wasm_bindgen::describe::WasmDescribe for FlatVector<T> {
130    fn describe() {
131        <Vec<u8> as wasm_bindgen::describe::WasmDescribe>::describe();
132    }
133}
134
135impl<T: FlatVectorElem> FromWasmAbi for FlatVector<T> {
136    type Abi = <Vec<u8> as FromWasmAbi>::Abi;
137    unsafe fn from_abi(js: Self::Abi) -> Self {
138        let data: Vec<u8> = FromWasmAbi::from_abi(js);
139        let mut res: Vec<T> = Vec::with_capacity(data.len() / T::FLATTENED_SIZE);
140
141        let mut buf = Vec::with_capacity(T::FLATTENED_SIZE);
142        for x in data {
143            assert!(buf.len() < T::FLATTENED_SIZE);
144            buf.push(x);
145            if buf.len() >= T::FLATTENED_SIZE {
146                res.push(T::unflatten(buf));
147                buf = Vec::with_capacity(T::FLATTENED_SIZE);
148            }
149        }
150        assert_eq!(buf.len(), 0);
151        FlatVector(res)
152    }
153}
154
155impl<T: FlatVectorElem> OptionFromWasmAbi for FlatVector<T> {
156    fn is_none(x: &Self::Abi) -> bool {
157        <Vec<u8> as OptionFromWasmAbi>::is_none(x)
158    }
159}
160
161impl<T: FlatVectorElem> IntoWasmAbi for FlatVector<T> {
162    type Abi = <Vec<u8> as FromWasmAbi>::Abi;
163    fn into_abi(self) -> Self::Abi {
164        let mut data: Vec<u8> = Vec::with_capacity(self.0.len() * T::FLATTENED_SIZE);
165        for x in self.0 {
166            data.extend(x.flatten().into_iter());
167        }
168        IntoWasmAbi::into_abi(data)
169    }
170}
171
172impl<T: FlatVectorElem> OptionIntoWasmAbi for FlatVector<T> {
173    fn none() -> Self::Abi {
174        <Vec<u8> as OptionIntoWasmAbi>::none()
175    }
176}
wasm_types/flat_vector.rs

wasm_types/
flat_vector.rs
