From 59ebdca0b9870426ae9c8edbb758f7e9f6d18db7 Mon Sep 17 00:00:00 2001 From: Pierre-Louis Date: Mon, 27 Nov 2023 14:34:35 -0500 Subject: [PATCH 1/3] evm/kernel: add push and get to the linked list --- .../kernel_evm/kernel/src/linked_list.rs | 76 +++++++++++++++++++ 1 file changed, 76 insertions(+) diff --git a/etherlink/kernel_evm/kernel/src/linked_list.rs b/etherlink/kernel_evm/kernel/src/linked_list.rs index 3d8f28235d2c..3ad66361386f 100644 --- a/etherlink/kernel_evm/kernel/src/linked_list.rs +++ b/etherlink/kernel_evm/kernel/src/linked_list.rs @@ -152,6 +152,15 @@ impl> Pointer { Ok(path) } + /// Path to the data held by the pointer. + fn data_path(&self, prefix: &impl Path) -> Result { + let path = hex::encode(&self.id); + let path: Vec = format!("/{}/data", 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)?) @@ -199,6 +208,73 @@ where pub fn is_empty(&self) -> bool { self.pointers.is_none() } + + /// Appends an element to the back of a list. + /// + /// An element cannot be mutated. + /// The Id has to be unique by element. + /// The Id will be later use to retrieve the element + /// (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() { + return Ok(()); + } + match &self.pointers { + Some(LinkedListPointer { front, back }) => { + // The list is not empty + // Modifies the old back pointer + let penultimate = Pointer { + next: Some(id.clone()), // Points to the inserted element + ..back.clone() + }; + // Creates a new back pointer + let back = Pointer { + id: id.clone(), + previous: Some(penultimate.id.clone()), // Points to the penultimate pointer + next: None, // None because there is no element after + }; + // Saves the pointer + penultimate.save(host, &self.path)?; + back.save(host, &self.path)?; + // And the save the data + let data_path = back.data_path(&self.path)?; + storage::store_rlp(elt, host, &data_path)?; + // update the back pointer of the list + self.pointers = Some(LinkedListPointer { + front: front.clone(), + back, + }); + } + None => { + // This case corresponds to the empty list + // A new pointer has to be created + let back = Pointer { + 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 + }; + // Saves the pointer and its data + back.save(host, &self.path)?; + let data_path = back.data_path(&self.path)?; + storage::store_rlp(elt, host, &data_path)?; + // update the front and back pointers of the list + self.pointers = Some(LinkedListPointer { + front: back.clone(), + back, + }); + } + }; + self.save(host) + } + + /// Returns an element at a given index. + /// + /// Returns None if the element is not present + pub fn get(&self, host: &impl Runtime, id: &Id) -> Result> { + let Some(pointer) = Pointer::read(host, &self.path, id)? else {return Ok(None)}; + storage::read_optional_rlp(host, &pointer.data_path(&self.path)?) + } } #[cfg(test)] -- GitLab From 1f5199f191d476cd634f11904824586a94908c50 Mon Sep 17 00:00:00 2001 From: Pierre-Louis Date: Mon, 27 Nov 2023 14:27:06 -0500 Subject: [PATCH 2/3] evm/kernel: add proptest dependency --- etherlink/kernel_evm/Cargo.lock | 1 + etherlink/kernel_evm/Makefile | 4 ++-- etherlink/kernel_evm/kernel/Cargo.toml | 3 +++ 3 files changed, 6 insertions(+), 2 deletions(-) diff --git a/etherlink/kernel_evm/Cargo.lock b/etherlink/kernel_evm/Cargo.lock index d48b0fda1dfa..700a523762ee 100644 --- a/etherlink/kernel_evm/Cargo.lock +++ b/etherlink/kernel_evm/Cargo.lock @@ -550,6 +550,7 @@ dependencies = [ "libsecp256k1", "num-traits", "primitive-types", + "proptest", "rlp", "sha3", "tezos-evm-logging", diff --git a/etherlink/kernel_evm/Makefile b/etherlink/kernel_evm/Makefile index 1b7b5319d221..99fa1749d77f 100644 --- a/etherlink/kernel_evm/Makefile +++ b/etherlink/kernel_evm/Makefile @@ -39,11 +39,11 @@ build-dev-deps: build-deps .PHONY: test test: - @cargo test + @cargo test --features testing .PHONY: check check: - @cargo clippy --all-targets -- --deny warnings + @cargo clippy --all-targets --features testing -- --deny warnings .PHONY: check-all check-all: check diff --git a/etherlink/kernel_evm/kernel/Cargo.toml b/etherlink/kernel_evm/kernel/Cargo.toml index 9cd6d65add51..f02eb368a1a1 100644 --- a/etherlink/kernel_evm/kernel/Cargo.toml +++ b/etherlink/kernel_evm/kernel/Cargo.toml @@ -47,6 +47,8 @@ tezos-smart-rollup-storage.workspace = true tezos_data_encoding.workspace = true +proptest = { workspace = true, optional = true } + [dev-dependencies] tezos-smart-rollup-mock.workspace = true tezos-smart-rollup-panic-hook.workspace = true @@ -55,3 +57,4 @@ tezos-smart-rollup-panic-hook.workspace = true default = ["panic-hook"] panic-hook = [] debug = ["tezos-evm-logging/debug"] +testing = ["proptest"] -- GitLab From 1c9a8ad12a8d1e44c9b454c8acc6c7effaec79d1 Mon Sep 17 00:00:00 2001 From: Pierre-Louis Date: Wed, 6 Dec 2023 16:23:55 +0100 Subject: [PATCH 3/3] evm/kernel: test push and get from the linked list --- .../kernel_evm/kernel/src/linked_list.rs | 85 +++++++++++++++++++ 1 file changed, 85 insertions(+) diff --git a/etherlink/kernel_evm/kernel/src/linked_list.rs b/etherlink/kernel_evm/kernel/src/linked_list.rs index 3ad66361386f..ffd5bf1af600 100644 --- a/etherlink/kernel_evm/kernel/src/linked_list.rs +++ b/etherlink/kernel_evm/kernel/src/linked_list.rs @@ -280,7 +280,9 @@ where #[cfg(test)] mod tests { use super::LinkedList; + use proptest::proptest; use rlp::{Decodable, DecoderError, Encodable}; + use std::collections::HashMap; use tezos_ethereum::transaction::TRANSACTION_HASH_SIZE; use tezos_smart_rollup_host::path::RefPath; use tezos_smart_rollup_mock::MockHost; @@ -318,4 +320,87 @@ mod tests { LinkedList::::new(&path, &host).expect("list should be created"); assert!(list.is_empty()) } + + #[test] + fn test_get_returns_none_when_empty() { + let host = MockHost::default(); + let path = RefPath::assert_from(b"/list"); + let list = LinkedList::new(&path, &host).expect("list should be created"); + let hash = Hash([0; TRANSACTION_HASH_SIZE]); + let read: Option = list.get(&host, &hash).expect("storage should work"); + assert!(read.is_none()) + } + + #[test] + fn test_insert() { + 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 work"); + + let read: u8 = list + .get(&host, &id) + .expect("storage should work") + .expect("element should be present"); + + assert_eq!(read, elt); + } + + fn fill_list( + elements: &HashMap<[u8; TRANSACTION_HASH_SIZE], u8>, + ) -> (MockHost, LinkedList) { + let mut host = MockHost::default(); + let path = RefPath::assert_from(b"/list"); + let mut list = LinkedList::new(&path, &host).expect("list should be created"); + for (id, elt) in elements { + list.push(&mut host, &Hash(*id), elt) + .expect("storage should work"); + assert!(!list.is_empty()) + } + (host, list) + } + + proptest! { + #[test] + fn test_pushed_elements_are_present(elements: HashMap<[u8; TRANSACTION_HASH_SIZE], u8>) { + let (host, list) = fill_list(&elements); + for (id, elt) in & elements { + let read: u8 = list.get(&host, &Hash(*id)).expect("storage should work").expect("element should be present"); + assert_eq!(elt, &read) + } + } + + + #[test] + fn test_push_element_create_non_empty_list(elements: HashMap<[u8; TRANSACTION_HASH_SIZE], u8>) { + let mut host = MockHost::default(); + let path = RefPath::assert_from(b"/list"); + let mut list = LinkedList::new(&path, &host).expect("list should be created"); + assert!(list.is_empty()); + for (id, elt) in elements { + list.push(&mut host, &Hash(id), &elt).expect("storage should work"); + assert!(!list.is_empty()) + } + } + + #[test] + fn test_list_is_kept_between_reboots(elements: HashMap<[u8; TRANSACTION_HASH_SIZE], u8>) { + let mut host = MockHost::default(); + let path = RefPath::assert_from(b"/list"); + for (id, elt) in &elements { + let mut list = LinkedList::new(&path, &host).expect("list should be created"); + list.push(&mut host, &Hash(*id), elt).expect("storage should work"); + assert!(!list.is_empty()) + } + for (id, elt) in &elements { + let list = LinkedList::new(&path, &host).expect("list should be created"); + let read: u8 = list.get(&host, &Hash(*id)).expect("storage should work").expect("element should be present"); + assert_eq!(elt, &read); + } + } + } } -- GitLab