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
42impl<Op> BytecodeMapped<Op, Vec<u8>> {
43    /// Push a single operation onto the bytecode mapping.
44    pub fn push_op(&mut self, op: Op)
45    where
46        Op: ToBytes,
47    {
48        self.op_indices.push(self.bytecode.len());
49        self.bytecode.extend(op.to_bytes());
50    }
51}
52
53impl<Op, Bytes> BytecodeMapped<Op, Bytes>
54where
55    Bytes: core::ops::Deref<Target = [u8]>,
56{
57    /// Attempt to construct a `BytecodeMapped` from an existing slice of bytes.
58    ///
59    /// `bytes` may be any type that dereferences to a slice of bytes, e.g.
60    /// `&[u8]`, `Arc<[u8]>`, `Vec<u8>`, etc.
61    pub fn try_from_bytes(bytes: Bytes) -> Result<BytecodeMapped<Op, Bytes>, Op::Error>
62    where
63        Op: ToOpcode + TryFromBytes,
64        Op::Opcode: ParseOp<Op = Op> + TryFrom<u8>,
65        Op::Error: From<<Op::Opcode as TryFrom<u8>>::Error> + From<<Op::Opcode as ParseOp>::Error>,
66    {
67        let bytecode = bytes.deref();
68        let mut op_indices = Vec::with_capacity(bytecode.len() / std::mem::size_of::<Op>());
69        let mut iter_enum = bytecode.iter().enumerate();
70        while let Some((ix, &opcode_byte)) = iter_enum.next() {
71            let opcode = Op::Opcode::try_from(opcode_byte)?;
72            let mut op_bytes = iter_enum.by_ref().map(|(_, &byte)| byte);
73            let _op = opcode.parse_op(&mut op_bytes)?;
74            op_indices.push(ix);
75        }
76        Ok(BytecodeMapped {
77            bytecode: bytes,
78            op_indices,
79            _op_ty: core::marker::PhantomData,
80        })
81    }
82
83    /// Borrow the inner bytecode and op_indices slices and return a [`BytecodeMappedSlice`].
84    pub fn as_slice(&self) -> BytecodeMappedSlice<Op> {
85        BytecodeMappedSlice {
86            bytecode: self.bytecode(),
87            op_indices: self.op_indices(),
88            _op_ty: self._op_ty,
89        }
90    }
91
92    /// The inner slice of bytecode that has been mapped.
93    pub fn bytecode(&self) -> &[u8] {
94        self.bytecode.deref()
95    }
96
97    /// Slice the op indices from the given index.
98    ///
99    /// The returned slice represents the remainder of the program from the given op.
100    ///
101    /// Returns `None` if `start` is out of range of the `op_indices` slice.
102    pub fn ops_from(&self, start: usize) -> Option<BytecodeMappedSlice<Op>> {
103        Some(BytecodeMappedSlice {
104            bytecode: self.bytecode(),
105            op_indices: self.op_indices.get(start..)?,
106            _op_ty: self._op_ty,
107        })
108    }
109
110    /// The operation at the given index.
111    pub fn op(&self, ix: usize) -> Option<Op>
112    where
113        Op: TryFromBytes,
114    {
115        let slice = self.ops_from(ix)?;
116        slice.ops().next()
117    }
118
119    /// An iterator yielding all mapped operations.
120    pub fn ops(&self) -> impl '_ + Iterator<Item = Op>
121    where
122        Op: TryFromBytes,
123    {
124        expect_ops_from_indices(self.bytecode(), self.op_indices.iter().copied())
125    }
126}
127
128impl<Op, Bytes> BytecodeMapped<Op, Bytes> {
129    /// The slice of operation indices within the mapped bytecode.
130    pub fn op_indices(&self) -> &[usize] {
131        &self.op_indices
132    }
133}
134
135impl<'a, Op> BytecodeMappedSlice<'a, Op> {
136    /// The slice of operation indices within the mapped bytecode.
137    pub fn op_indices(self) -> &'a [usize] {
138        self.op_indices
139    }
140
141    /// An iterator yielding all mapped operations represented by this slice.
142    pub fn ops(self) -> impl 'a + Iterator<Item = Op>
143    where
144        Op: TryFromBytes,
145    {
146        expect_ops_from_indices(self.bytecode, self.op_indices.iter().copied())
147    }
148}
149
150/// Manually implement `Default` to avoid requiring that `Op: Default` as is
151/// assumed by `derive(Default)`.
152impl<Op> Default for BytecodeMapped<Op> {
153    fn default() -> Self {
154        BytecodeMapped {
155            bytecode: Default::default(),
156            op_indices: Default::default(),
157            _op_ty: Default::default(),
158        }
159    }
160}
161
162// Allow for collecting a `BytecodeMapped` from an iterator over `Op`s.
163impl<Op> FromIterator<Op> for BytecodeMapped<Op>
164where
165    Op: ToBytes,
166{
167    fn from_iter<T: IntoIterator<Item = Op>>(iter: T) -> Self {
168        let iter = iter.into_iter();
169        let (min, _) = iter.size_hint();
170        let mut mapped = BytecodeMapped {
171            bytecode: Vec::with_capacity(min),
172            op_indices: Vec::with_capacity(min),
173            _op_ty: core::marker::PhantomData,
174        };
175        iter.for_each(|op| mapped.push_op(op));
176        mapped
177    }
178}
179
180/// Allow for taking ownership over and mapping an existing `Vec<u8>`.
181impl<Op> TryFrom<Vec<u8>> for BytecodeMapped<Op>
182where
183    Op: ToOpcode + TryFromBytes,
184    Op::Opcode: ParseOp<Op = Op> + TryFrom<u8>,
185    Op::Error: From<<Op::Opcode as TryFrom<u8>>::Error> + From<<Op::Opcode as ParseOp>::Error>,
186{
187    type Error = Op::Error;
188    fn try_from(bytecode: Vec<u8>) -> Result<Self, Self::Error> {
189        Self::try_from_bytes(bytecode)
190    }
191}
192
193/// Allow for consuming and mapping an existing `&[u8]`.
194impl<'a, Op> TryFrom<&'a [u8]> for BytecodeMapped<Op, &'a [u8]>
195where
196    Op: ToOpcode + TryFromBytes,
197    Op::Opcode: ParseOp<Op = Op> + TryFrom<u8>,
198    Op::Error: From<<Op::Opcode as TryFrom<u8>>::Error> + From<<Op::Opcode as ParseOp>::Error>,
199{
200    type Error = Op::Error;
201    fn try_from(bytecode: &'a [u8]) -> Result<Self, Self::Error> {
202        Self::try_from_bytes(bytecode)
203    }
204}
205
206/// Given a bytecode slice and an operation mapping that is assumed to have been
207/// previously validated, produce an iterator yielding all associated operations.
208fn expect_ops_from_indices<'a, Op>(
209    bytecode: &'a [u8],
210    op_indices: impl 'a + IntoIterator<Item = usize>,
211) -> impl 'a + Iterator<Item = Op>
212where
213    Op: TryFromBytes,
214{
215    const EXPECT_MSG: &str = "validated upon construction";
216    op_indices.into_iter().map(|ix| {
217        let mut bytes = bytecode[ix..].iter().copied();
218        Op::try_from_bytes(&mut bytes)
219            .expect(EXPECT_MSG)
220            .expect(EXPECT_MSG)
221    })
222}