From e813b8705f6b4c8878a87911a5ba2043c940aa11 Mon Sep 17 00:00:00 2001 From: Pierre-Louis Date: Mon, 27 Nov 2023 14:32:55 -0500 Subject: [PATCH 1/3] evm/kernel: init the linked list data structure --- etherlink/kernel_evm/kernel/src/lib.rs | 1 + .../kernel_evm/kernel/src/linked_list.rs | 197 ++++++++++++++++++ 2 files changed, 198 insertions(+) create mode 100644 etherlink/kernel_evm/kernel/src/linked_list.rs diff --git a/etherlink/kernel_evm/kernel/src/lib.rs b/etherlink/kernel_evm/kernel/src/lib.rs index 61c1fa434b20..8193e9ca1d62 100644 --- a/etherlink/kernel_evm/kernel/src/lib.rs +++ b/etherlink/kernel_evm/kernel/src/lib.rs @@ -42,6 +42,7 @@ mod blueprint; mod error; mod inbox; mod indexable_storage; +mod linked_list; mod migration; mod mock_internal; mod parsing; diff --git a/etherlink/kernel_evm/kernel/src/linked_list.rs b/etherlink/kernel_evm/kernel/src/linked_list.rs new file mode 100644 index 000000000000..3fe704e28746 --- /dev/null +++ b/etherlink/kernel_evm/kernel/src/linked_list.rs @@ -0,0 +1,197 @@ +// SPDX-FileCopyrightText: 2023 Marigold + +use crate::storage; +use anyhow::{Context, Result}; +use rlp::{Decodable, DecoderError, Encodable, Rlp, RlpIterator, RlpStream}; +use std::marker::PhantomData; +use tezos_ethereum::rlp_helpers::{append_option, decode_field, decode_option, next}; +use tezos_smart_rollup_host::{ + path::{concat, OwnedPath, Path}, + runtime::Runtime, +}; + +/// Doubly linked list using the durable storage. +/// +/// The list is generic over element and index. +/// The element has to implement Decodable and Encodable +/// The Id has to implement AsRef<[u8]> +/// +/// The list is lazy. Not all the list is loaded at initialization. +/// Elements are saved/read at the appropriate moment. +pub struct LinkedList +where + Id: AsRef<[u8]> + Encodable + Decodable + Clone, + Elt: Encodable + Decodable, +{ + /// Absolute path to queue + path: OwnedPath, + /// None indicates an empty list + pointers: Option>, + _type: PhantomData<(Id, Elt)>, +} + +/// Pointers that indicates the front and the back of the list +struct LinkedListPointer { + front: Pointer, + back: Pointer, +} + +/// Each element in the list has a pointer +#[derive(Clone, Debug)] +struct Pointer { + /// Current index of the pointer + id: Id, + /// Previous index of the pointer + previous: Option, + /// Next index of the pointer + next: Option, +} + +/// Helper function to decode a path from rlp +fn decode_path( + it: &mut RlpIterator, + field_name: &'static str, +) -> Result { + let path: Vec = decode_field(&next(it)?, field_name)?; + OwnedPath::try_from(path).map_err(|_| DecoderError::Custom("not a path")) +} + +impl Decodable for LinkedListPointer { + fn decode(decoder: &Rlp) -> Result { + if !decoder.is_list() { + return Err(rlp::DecoderError::RlpExpectedToBeList); + } + if decoder.item_count()? != 2 { + return Err(rlp::DecoderError::RlpInvalidLength); + } + let mut it = decoder.iter(); + let front = decode_field(&next(&mut it)?, "front")?; + let back = decode_field(&next(&mut it)?, "back")?; + Ok(LinkedListPointer { front, back }) + } +} + +impl Encodable for LinkedListPointer { + fn rlp_append(&self, stream: &mut RlpStream) { + stream.begin_list(2); + stream.append(&self.front); + stream.append(&self.back); + } +} + +impl Decodable for Pointer { + fn decode(decoder: &Rlp) -> Result { + if !decoder.is_list() { + return Err(rlp::DecoderError::RlpExpectedToBeList); + } + if decoder.item_count()? != 3 { + return Err(rlp::DecoderError::RlpInvalidLength); + } + let mut it = decoder.iter(); + let id = decode_field(&next(&mut it)?, "id")?; + let previous = decode_option(&next(&mut it)?, "previous")?; + let next = decode_option(&next(&mut it)?, "next")?; + + Ok(Pointer { id, next, previous }) + } +} + +impl Encodable for Pointer { + fn rlp_append(&self, stream: &mut RlpStream) { + stream.begin_list(3); + stream.append(&self.id); + append_option(stream, &self.previous); + append_option(stream, &self.next); + } +} + +impl Encodable for LinkedList +where + Id: AsRef<[u8]> + Encodable + Decodable + Clone, + Elt: Encodable + Decodable, +{ + fn rlp_append(&self, stream: &mut rlp::RlpStream) { + stream.begin_list(2); + stream.append(&self.path.as_bytes()); + append_option(stream, &self.pointers); + } +} + +impl Decodable for LinkedList +where + Id: AsRef<[u8]> + Encodable + Decodable + Clone, + Elt: Encodable + Decodable, +{ + fn decode(decoder: &Rlp) -> Result { + if !decoder.is_list() { + return Err(DecoderError::RlpExpectedToBeList); + } + if decoder.item_count()? != 2 { + return Err(DecoderError::RlpIncorrectListLen); + } + + let mut it = decoder.iter(); + let path = decode_path(&mut it, "path")?; + let pointers = decode_option(&next(&mut it)?, "pointers")?; + + Ok(Self { + path, + pointers, + _type: PhantomData, + }) + } +} + +#[allow(dead_code)] +impl> Pointer { + fn pointer_path(id: &Id, prefix: &impl Path) -> Result { + let path = hex::encode(id); + let path: Vec = format!("/{}/pointer", path).into(); + let path = OwnedPath::try_from(path)?; + let path = concat(prefix, &path)?; + Ok(path) + } + + /// Load the pointer from the durable storage + fn read(host: &impl Runtime, prefix: &impl Path, id: &Id) -> Result> { + storage::read_optional_rlp(host, &Self::pointer_path(id, prefix)?) + } + + /// Save the pointer in the durable storage + fn save(&self, host: &mut impl Runtime, prefix: &impl Path) -> Result<()> { + storage::store_rlp(self, host, &Self::pointer_path(&self.id, prefix)?) + .context("cannot save pointer to storage") + } +} + +#[allow(dead_code)] +impl LinkedList +where + Id: AsRef<[u8]> + Encodable + Decodable + Clone, + Elt: Encodable + Decodable, +{ + /// Load a list from the storage. + /// If the list does not exist, a new empty list is created. + /// Otherwise the existing list is read from the storage. + pub fn new(path: &impl Path, host: &impl Runtime) -> Result { + let list = Self::read(host, path)?.unwrap_or(Self { + path: path.into(), + pointers: None, + _type: PhantomData, + }); + Ok(list) + } + + /// Saves the LinkedList in the durable storage. + /// + /// Only save the back and front pointers. + fn save(&self, host: &mut impl Runtime) -> Result<()> { + storage::store_rlp(self, host, &self.path) + .context("cannot load linked list from the storage") + } + + /// Load the LinkedList from the durable storage. + fn read(host: &impl Runtime, path: &impl Path) -> Result> { + storage::read_optional_rlp(host, path) + } +} -- GitLab From d77294ff389495bfc3cb8c68d361ab4bd3b6183d Mon Sep 17 00:00:00 2001 From: Pierre-Louis Date: Mon, 27 Nov 2023 14:33:56 -0500 Subject: [PATCH 2/3] evm/kernel: add is_empty to linked list --- etherlink/kernel_evm/kernel/src/linked_list.rs | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/etherlink/kernel_evm/kernel/src/linked_list.rs b/etherlink/kernel_evm/kernel/src/linked_list.rs index 3fe704e28746..3f85a17127de 100644 --- a/etherlink/kernel_evm/kernel/src/linked_list.rs +++ b/etherlink/kernel_evm/kernel/src/linked_list.rs @@ -194,4 +194,9 @@ where fn read(host: &impl Runtime, path: &impl Path) -> Result> { storage::read_optional_rlp(host, path) } + + /// Returns true if the list contains no elements. + pub fn is_empty(&self) -> bool { + self.pointers.is_none() + } } -- GitLab From 2c3607a175e52d8434c34ef17d484e6fdf247699 Mon Sep 17 00:00:00 2001 From: Pierre-Louis Date: Mon, 27 Nov 2023 14:59:16 -0500 Subject: [PATCH 3/3] evm/kernel: test linked list is_empty --- .../kernel_evm/kernel/src/linked_list.rs | 43 +++++++++++++++++++ 1 file changed, 43 insertions(+) diff --git a/etherlink/kernel_evm/kernel/src/linked_list.rs b/etherlink/kernel_evm/kernel/src/linked_list.rs index 3f85a17127de..3d8f28235d2c 100644 --- a/etherlink/kernel_evm/kernel/src/linked_list.rs +++ b/etherlink/kernel_evm/kernel/src/linked_list.rs @@ -200,3 +200,46 @@ where self.pointers.is_none() } } + +#[cfg(test)] +mod tests { + use super::LinkedList; + use rlp::{Decodable, DecoderError, Encodable}; + use tezos_ethereum::transaction::TRANSACTION_HASH_SIZE; + use tezos_smart_rollup_host::path::RefPath; + use tezos_smart_rollup_mock::MockHost; + + #[derive(Clone)] + struct Hash([u8; TRANSACTION_HASH_SIZE]); + + impl Encodable for Hash { + fn rlp_append(&self, s: &mut rlp::RlpStream) { + s.append(&self.0.to_vec()); + } + } + + impl Decodable for Hash { + fn decode(decoder: &rlp::Rlp) -> Result { + let hash: Vec = decoder.as_val()?; + let hash = hash + .try_into() + .map_err(|_| DecoderError::Custom("expected a vec of 32 elements"))?; + Ok(Hash(hash)) + } + } + + impl AsRef<[u8]> for Hash { + fn as_ref(&self) -> &[u8] { + &self.0 + } + } + + #[test] + fn test_empty() { + let host = MockHost::default(); + let path = RefPath::assert_from(b"/list"); + let list = + LinkedList::::new(&path, &host).expect("list should be created"); + assert!(list.is_empty()) + } +} -- GitLab