essential_vm/
bytecode.rs

1//! Items related to bytecode representation for the VM assembly.
2
3use crate::asm::{opcode::ParseOp, ToBytes, ToOpcode, TryFromBytes};
4
5/// A memory efficient representation of a sequence of operations parsed from bytecode.
6///
7/// Executing certain control flow operations can require the ability to jump
8/// back to a previous operation.
9///
10/// One simple solution might be to use a `Vec<Op>`, however it is important to
11/// consider that the size of each element within a `Vec<Op>` will be equal to
12/// the size of the discriminant plus the largest `Op` variant size (today, this
13/// is `Push(Word)`, but this may change as new operations are added). This can
14/// have memory requirement implications for programs with large numbers of ops.
15///
16/// To avoid this issue, we instead store the raw "packed" bytecode alongside
17/// a list of indices into the bytecode representing the location of each
18/// operation.
19#[derive(Clone, Debug, PartialEq)]
20pub struct BytecodeMapped<Op, Bytes = Vec<u8>> {
21    /// The bytecode representation of a program's operations.
22    bytecode: Bytes,
23    /// The index of each op within the bytecode slice.
24    ///
25    /// Indices are guaranteed to be valid by construction and point to a valid operation.
26    op_indices: Vec<usize>,
27    /// Ensures that `BytecodeMapped` remains consistent for the given `Op` type.
28    _op_ty: core::marker::PhantomData<Op>,
29}
30
31/// A slice into a [`BytecodeMapped`] instance.
32#[derive(Clone, Copy, Debug, PartialEq)]
33pub struct BytecodeMappedSlice<'a, Op> {
34    /// The full bytecode slice from the original `BytecodeMapped`.
35    bytecode: &'a [u8],
36    /// Some subslice into the `op_indices` of the original `BytecodeMapped`.
37    op_indices: &'a [usize],
38    /// Ensures that `BytecodeMapped` remains consistent for the given `Op` type.
39    _op_ty: core::marker::PhantomData<Op>,
40}
41
42/// A type wrapper around `BytecodeMapped` that lazily constructs the map from
43/// the given bytecode as operations are accessed.
44pub struct BytecodeMappedLazy<Op, I> {
45    /// The `BytecodeMapped` instance that is lazily constructed.
46    pub(crate) mapped: BytecodeMapped<Op>,
47    /// The iterator yielding bytes.
48    pub(crate) iter: I,
49}
50
51impl<Op> BytecodeMapped<Op, Vec<u8>> {
52    /// Push a single operation onto the bytecode mapping.
53    pub fn push_op(&mut self, op: Op)
54    where
55        Op: ToBytes,
56    {
57        self.op_indices.push(self.bytecode.len());
58        self.bytecode.extend(op.to_bytes());
59    }
60}
61
62impl<Op, Bytes> BytecodeMapped<Op, Bytes>
63where
64    Bytes: core::ops::Deref<Target = [u8]>,
65{
66    /// Attempt to construct a `BytecodeMapped` from an existing slice of bytes.
67    ///
68    /// `bytes` may be any type that dereferences to a slice of bytes, e.g.
69    /// `&[u8]`, `Arc<[u8]>`, `Vec<u8>`, etc.
70    pub fn try_from_bytes(bytes: Bytes) -> Result<BytecodeMapped<Op, Bytes>, Op::Error>
71    where
72        Op: ToOpcode + TryFromBytes,
73        Op::Opcode: ParseOp<Op = Op> + TryFrom<u8>,
74        Op::Error: From<<Op::Opcode as TryFrom<u8>>::Error> + From<<Op::Opcode as ParseOp>::Error>,
75    {
76        let bytecode = bytes.deref();
77        let mut op_indices = Vec::with_capacity(bytecode.len() / std::mem::size_of::<Op>());
78        let mut iter_enum = bytecode.iter().enumerate();
79        while let Some((ix, &opcode_byte)) = iter_enum.next() {
80            let opcode = Op::Opcode::try_from(opcode_byte)?;
81            let mut op_bytes = iter_enum.by_ref().map(|(_, &byte)| byte);
82            let _op = opcode.parse_op(&mut op_bytes)?;
83            op_indices.push(ix);
84        }
85        Ok(BytecodeMapped {
86            bytecode: bytes,
87            op_indices,
88            _op_ty: core::marker::PhantomData,
89        })
90    }
91
92    /// Borrow the inner bytecode and op_indices slices and return a [`BytecodeMappedSlice`].
93    pub fn as_slice(&self) -> BytecodeMappedSlice<Op> {
94        BytecodeMappedSlice {
95            bytecode: self.bytecode(),
96            op_indices: self.op_indices(),
97            _op_ty: self._op_ty,
98        }
99    }
100
101    /// The inner slice of bytecode that has been mapped.
102    pub fn bytecode(&self) -> &[u8] {
103        self.bytecode.deref()
104    }
105
106    /// Slice the op indices from the given index.
107    ///
108    /// The returned slice represents the remainder of the program from the given op.
109    ///
110    /// Returns `None` if `start` is out of range of the `op_indices` slice.
111    pub fn ops_from(&self, start: usize) -> Option<BytecodeMappedSlice<Op>> {
112        Some(BytecodeMappedSlice {
113            bytecode: self.bytecode(),
114            op_indices: self.op_indices.get(start..)?,
115            _op_ty: self._op_ty,
116        })
117    }
118
119    /// The operation at the given index.
120    pub fn op(&self, ix: usize) -> Option<Op>
121    where
122        Op: TryFromBytes,
123    {
124        let slice = self.ops_from(ix)?;
125        slice.ops().next()
126    }
127
128    /// An iterator yielding all mapped operations.
129    pub fn ops(&self) -> impl '_ + Iterator<Item = Op>
130    where
131        Op: TryFromBytes,
132    {
133        expect_ops_from_indices(self.bytecode(), self.op_indices.iter().copied())
134    }
135}
136
137impl<Op, Bytes> BytecodeMapped<Op, Bytes> {
138    /// The slice of operation indices within the mapped bytecode.
139    pub fn op_indices(&self) -> &[usize] {
140        &self.op_indices
141    }
142}
143
144impl<'a, Op> BytecodeMappedSlice<'a, Op> {
145    /// The slice of operation indices within the mapped bytecode.
146    pub fn op_indices(self) -> &'a [usize] {
147        self.op_indices
148    }
149
150    /// An iterator yielding all mapped operations represented by this slice.
151    pub fn ops(self) -> impl 'a + Iterator<Item = Op>
152    where
153        Op: TryFromBytes,
154    {
155        expect_ops_from_indices(self.bytecode, self.op_indices.iter().copied())
156    }
157}
158
159impl<Op, I> BytecodeMappedLazy<Op, I> {
160    /// Construct the `BytecodeMappedLazy` from its bytecode iterator.
161    pub fn new<J>(bytes: J) -> Self
162    where
163        J: IntoIterator<IntoIter = I>,
164        I: Iterator<Item = u8>,
165    {
166        let iter = bytes.into_iter();
167        let (min, _) = iter.size_hint();
168        let mapped = BytecodeMapped {
169            bytecode: Vec::with_capacity(min),
170            op_indices: Vec::with_capacity(min),
171            _op_ty: core::marker::PhantomData,
172        };
173        Self { mapped, iter }
174    }
175}
176
177/// Manually implement `Default` to avoid requiring that `Op: Default` as is
178/// assumed by `derive(Default)`.
179impl<Op> Default for BytecodeMapped<Op> {
180    fn default() -> Self {
181        BytecodeMapped {
182            bytecode: Default::default(),
183            op_indices: Default::default(),
184            _op_ty: Default::default(),
185        }
186    }
187}
188
189// Allow for collecting a `BytecodeMapped` from an iterator over `Op`s.
190impl<Op> FromIterator<Op> for BytecodeMapped<Op>
191where
192    Op: ToBytes,
193{
194    fn from_iter<T: IntoIterator<Item = Op>>(iter: T) -> Self {
195        let iter = iter.into_iter();
196        let (min, _) = iter.size_hint();
197        let mut mapped = BytecodeMapped {
198            bytecode: Vec::with_capacity(min),
199            op_indices: Vec::with_capacity(min),
200            _op_ty: core::marker::PhantomData,
201        };
202        iter.for_each(|op| mapped.push_op(op));
203        mapped
204    }
205}
206
207/// Allow for taking ownership over and mapping an existing `Vec<u8>`.
208impl<Op> TryFrom<Vec<u8>> for BytecodeMapped<Op>
209where
210    Op: ToOpcode + TryFromBytes,
211    Op::Opcode: ParseOp<Op = Op> + TryFrom<u8>,
212    Op::Error: From<<Op::Opcode as TryFrom<u8>>::Error> + From<<Op::Opcode as ParseOp>::Error>,
213{
214    type Error = Op::Error;
215    fn try_from(bytecode: Vec<u8>) -> Result<Self, Self::Error> {
216        Self::try_from_bytes(bytecode)
217    }
218}
219
220/// Allow for consuming and mapping an existing `&[u8]`.
221impl<'a, Op> TryFrom<&'a [u8]> for BytecodeMapped<Op, &'a [u8]>
222where
223    Op: ToOpcode + TryFromBytes,
224    Op::Opcode: ParseOp<Op = Op> + TryFrom<u8>,
225    Op::Error: From<<Op::Opcode as TryFrom<u8>>::Error> + From<<Op::Opcode as ParseOp>::Error>,
226{
227    type Error = Op::Error;
228    fn try_from(bytecode: &'a [u8]) -> Result<Self, Self::Error> {
229        Self::try_from_bytes(bytecode)
230    }
231}
232
233/// Given a bytecode slice and an operation mapping that is assumed to have been
234/// previously validated, produce an iterator yielding all associated operations.
235fn expect_ops_from_indices<'a, Op>(
236    bytecode: &'a [u8],
237    op_indices: impl 'a + IntoIterator<Item = usize>,
238) -> impl 'a + Iterator<Item = Op>
239where
240    Op: TryFromBytes,
241{
242    const EXPECT_MSG: &str = "validated upon construction";
243    op_indices.into_iter().map(|ix| {
244        let mut bytes = bytecode[ix..].iter().copied();
245        Op::try_from_bytes(&mut bytes)
246            .expect(EXPECT_MSG)
247            .expect(EXPECT_MSG)
248    })
249}
essential_vm/bytecode.rs

essential_vm/
bytecode.rs
