From 572f11156f6d9b404bdfdd4a82ff7b427ca3c03e Mon Sep 17 00:00:00 2001 From: Pierre-Louis Date: Mon, 27 Nov 2023 14:35:29 -0500 Subject: [PATCH 1/3] evm/kernel: add fct to retrieve the first element --- etherlink/kernel_evm/kernel/src/linked_list.rs | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/etherlink/kernel_evm/kernel/src/linked_list.rs b/etherlink/kernel_evm/kernel/src/linked_list.rs index 61f1c59e5dd8..bb9517672ceb 100644 --- a/etherlink/kernel_evm/kernel/src/linked_list.rs +++ b/etherlink/kernel_evm/kernel/src/linked_list.rs @@ -384,6 +384,13 @@ where self.save(host)?; Ok(Some(data)) } + + /// Returns the first element of the list + /// or `None` if it is empty. + pub fn first(&self, host: &impl Runtime) -> Result> { + let Some(LinkedListPointer { front, .. }) = &self.pointers else {return Ok(None)}; + Ok(Some(front.get_data(host, &self.path)?)) + } } #[cfg(test)] -- GitLab From dcc7dcf9e6002fc7d4dbbfcfe8fb2a931d956f5d Mon Sep 17 00:00:00 2001 From: Pierre-Louis Date: Mon, 27 Nov 2023 15:43:34 -0500 Subject: [PATCH 2/3] evm/kernel: test get first elt from linked list --- .../kernel_evm/kernel/src/linked_list.rs | 62 +++++++++++++++++++ 1 file changed, 62 insertions(+) diff --git a/etherlink/kernel_evm/kernel/src/linked_list.rs b/etherlink/kernel_evm/kernel/src/linked_list.rs index bb9517672ceb..bfd132d2b8fd 100644 --- a/etherlink/kernel_evm/kernel/src/linked_list.rs +++ b/etherlink/kernel_evm/kernel/src/linked_list.rs @@ -513,6 +513,68 @@ mod tests { assert!(removed.is_none()) } + #[test] + fn test_first() { + let mut host = MockHost::default(); + let path = RefPath::assert_from(b"/list"); + let mut list = LinkedList::new(&path, &host).expect("list should be created"); + let id = Hash([0x0; TRANSACTION_HASH_SIZE]); + let elt = 0x32_u8; + + list.push(&mut host, &id, &elt) + .expect("storage should workd"); + + let read: u8 = list + .first(&host) + .expect("storage should work") + .expect("element should be present"); + + assert_eq!(read, 0x32); + } + + #[test] + fn test_first_when_only_two_elements() { + let mut host = MockHost::default(); + let path = RefPath::assert_from(b"/list"); + let mut list = LinkedList::new(&path, &host).expect("list should be created"); + let id_1 = Hash([0x0; TRANSACTION_HASH_SIZE]); + let id_2 = Hash([0x1; TRANSACTION_HASH_SIZE]); + + list.push(&mut host, &id_1, &0x32_u8) + .expect("storage should workd"); + list.push(&mut host, &id_2, &0x33_u8) + .expect("storage should workd"); + + let read: u8 = list + .first(&host) + .expect("storage should work") + .expect("element should be present"); + + assert_eq!(read, 0x32); + } + + #[test] + fn test_first_after_two_push() { + let mut host = MockHost::default(); + let path = RefPath::assert_from(b"/list"); + let mut list = LinkedList::new(&path, &host).expect("list should be created"); + let id_1 = Hash([0x0; TRANSACTION_HASH_SIZE]); + let id_2 = Hash([0x1; TRANSACTION_HASH_SIZE]); + + list.push(&mut host, &id_1, &0x32_u8) + .expect("storage should workd"); + list.push(&mut host, &id_2, &0x33_u8) + .expect("storage should workd"); + let _: Option = list.remove(&mut host, &id_1).expect("storage should work"); + + let read: u8 = list + .first(&host) + .expect("storage should work") + .expect("element should be present"); + + assert_eq!(read, 0x33); + } + fn fill_list( elements: &HashMap<[u8; TRANSACTION_HASH_SIZE], u8>, ) -> (MockHost, LinkedList) { -- GitLab From ba8cc9b811869591356310637114699a61656769 Mon Sep 17 00:00:00 2001 From: Antonio Locascio Date: Wed, 3 Jan 2024 10:31:15 +0100 Subject: [PATCH 3/3] EVM/Kernel: carry data type information in pointer --- .../kernel_evm/kernel/src/linked_list.rs | 52 +++++++++++-------- 1 file changed, 29 insertions(+), 23 deletions(-) diff --git a/etherlink/kernel_evm/kernel/src/linked_list.rs b/etherlink/kernel_evm/kernel/src/linked_list.rs index bfd132d2b8fd..ffe1a6f69fb9 100644 --- a/etherlink/kernel_evm/kernel/src/linked_list.rs +++ b/etherlink/kernel_evm/kernel/src/linked_list.rs @@ -21,30 +21,31 @@ use tezos_smart_rollup_host::{ pub struct LinkedList where Id: AsRef<[u8]> + Encodable + Decodable + Clone, - Elt: Encodable + Decodable, + Elt: Encodable + Decodable + Clone, { /// Absolute path to queue path: OwnedPath, /// None indicates an empty list - pointers: Option>, + pointers: Option>, _type: PhantomData<(Id, Elt)>, } /// Pointers that indicates the front and the back of the list -struct LinkedListPointer { - front: Pointer, - back: Pointer, +struct LinkedListPointer { + front: Pointer, + back: Pointer, } /// Each element in the list has a pointer #[derive(Clone, Debug)] -struct Pointer { +struct Pointer { /// Current index of the pointer id: Id, /// Previous index of the pointer previous: Option, /// Next index of the pointer next: Option, + _type: PhantomData, } /// Helper function to decode a path from rlp @@ -56,7 +57,7 @@ fn decode_path( OwnedPath::try_from(path).map_err(|_| DecoderError::Custom("not a path")) } -impl Decodable for LinkedListPointer { +impl Decodable for LinkedListPointer { fn decode(decoder: &Rlp) -> Result { if !decoder.is_list() { return Err(rlp::DecoderError::RlpExpectedToBeList); @@ -71,7 +72,7 @@ impl Decodable for LinkedListPointer { } } -impl Encodable for LinkedListPointer { +impl Encodable for LinkedListPointer { fn rlp_append(&self, stream: &mut RlpStream) { stream.begin_list(2); stream.append(&self.front); @@ -79,7 +80,7 @@ impl Encodable for LinkedListPointer { } } -impl Decodable for Pointer { +impl Decodable for Pointer { fn decode(decoder: &Rlp) -> Result { if !decoder.is_list() { return Err(rlp::DecoderError::RlpExpectedToBeList); @@ -92,11 +93,16 @@ impl Decodable for Pointer { let previous = decode_option(&next(&mut it)?, "previous")?; let next = decode_option(&next(&mut it)?, "next")?; - Ok(Pointer { id, next, previous }) + Ok(Pointer { + id, + next, + previous, + _type: PhantomData, + }) } } -impl Encodable for Pointer { +impl Encodable for Pointer { fn rlp_append(&self, stream: &mut RlpStream) { stream.begin_list(3); stream.append(&self.id); @@ -108,7 +114,7 @@ impl Encodable for Pointer { impl Encodable for LinkedList where Id: AsRef<[u8]> + Encodable + Decodable + Clone, - Elt: Encodable + Decodable, + Elt: Encodable + Decodable + Clone, { fn rlp_append(&self, stream: &mut rlp::RlpStream) { stream.begin_list(2); @@ -120,7 +126,7 @@ where impl Decodable for LinkedList where Id: AsRef<[u8]> + Encodable + Decodable + Clone, - Elt: Encodable + Decodable, + Elt: Encodable + Decodable + Clone, { fn decode(decoder: &Rlp) -> Result { if !decoder.is_list() { @@ -143,7 +149,9 @@ where } #[allow(dead_code)] -impl> Pointer { +impl, Elt: Encodable + Decodable> + Pointer +{ fn pointer_path(id: &Id, prefix: &impl Path) -> Result { let path = hex::encode(id); let path: Vec = format!("/{}/pointer", path).into(); @@ -172,17 +180,13 @@ impl> Pointer { &self, host: &mut impl Runtime, prefix: &impl Path, - data: &impl Encodable, + data: &Elt, ) -> Result<()> { let path = self.data_path(prefix)?; storage::store_rlp(data, host, &path).context("cannot save the pointer's data") } - fn get_data( - &self, - host: &impl Runtime, - prefix: &impl Path, - ) -> Result { + fn get_data(&self, host: &impl Runtime, prefix: &impl Path) -> Result { let path = self.data_path(prefix)?; storage::read_rlp(host, &path).context("cannot read the pointer's data") } @@ -217,7 +221,7 @@ impl> Pointer { impl LinkedList where Id: AsRef<[u8]> + Encodable + Decodable + Clone, - Elt: Encodable + Decodable, + Elt: Encodable + Decodable + Clone, { /// Load a list from the storage. /// If the list does not exist, a new empty list is created. @@ -257,7 +261,7 @@ where /// (example: it can be the hash of the element). pub fn push(&mut self, host: &mut impl Runtime, id: &Id, elt: &Elt) -> Result<()> { // Check if the path already exist - if Pointer::read(host, &self.path, id)?.is_some() { + if (Pointer::read(host, &self.path, id)? as Option>).is_some() { return Ok(()); } match &self.pointers { @@ -273,6 +277,7 @@ where id: id.clone(), previous: Some(penultimate.id.clone()), // Points to the penultimate pointer next: None, // None because there is no element after + _type: PhantomData, }; // Saves the pointer penultimate.save(host, &self.path)?; @@ -292,6 +297,7 @@ where id: id.clone(), previous: None, // None because it's the only element of the list next: None, // None because it's the only element of the list + _type: PhantomData, }; // Saves the pointer and its data back.save(host, &self.path)?; @@ -310,7 +316,7 @@ where /// /// Returns None if the element is not present pub fn find(&self, host: &impl Runtime, id: &Id) -> Result> { - let Some(pointer) = Pointer::read(host, &self.path, id)? else {return Ok(None)}; + let Some::>(pointer) = Pointer::read(host, &self.path, id)? else {return Ok(None)}; storage::read_optional_rlp(host, &pointer.data_path(&self.path)?) } -- GitLab