Advanced Cairo: Using arrays inside dicts (cairo-book#827)

stevencartavia · Jun 1, 2024 · b06f032 · b06f032
1 parent bf27828
commit b06f032
Show file tree

Hide file tree

Showing 26 changed files with 166 additions and 23 deletions.
diff --git a/listings/ch03-common-collections/no_listing_14_dict_of_array_insert/.gitignore b/listings/ch03-common-collections/no_listing_14_dict_of_array_insert/.gitignore
@@ -0,0  1 @@
 target
diff --git a/listings/ch03-common-collections/no_listing_14_dict_of_array_insert/Scarb.toml b/listings/ch03-common-collections/no_listing_14_dict_of_array_insert/Scarb.toml
@@ -0,0  1,9 @@
 [package]
 name = "no_listing_14_dict_of_array_insert"
 version = "0.1.0"
 edition = "2023_11"
 
 # See more keys and their definitions at https://docs.swmansion.com/scarb/docs/reference/manifest
 
 [dependencies]
 # foo = { path = "vendor/foo" }
diff --git a/listings/ch03-common-collections/no_listing_14_dict_of_array_insert/src/lib.cairo b/listings/ch03-common-collections/no_listing_14_dict_of_array_insert/src/lib.cairo
@@ -0,0  1,6 @@
 fn main() {
     let arr = array![20, 19, 26];
     let mut dict: Felt252Dict<Nullable<Array<u8>>> = Default::default();
     dict.insert(0, NullableTrait::new(arr));
     println!("Array inserted successfully.");
 }
diff --git a/listings/ch03-common-collections/no_listing_15_dict_of_array_attempt_get/.gitignore b/listings/ch03-common-collections/no_listing_15_dict_of_array_attempt_get/.gitignore
@@ -0,0  1 @@
 target
diff --git a/listings/ch03-common-collections/no_listing_15_dict_of_array_attempt_get/Scarb.toml b/listings/ch03-common-collections/no_listing_15_dict_of_array_attempt_get/Scarb.toml
@@ -0,0  1,9 @@
 [package]
 name = "no_listing_15_dict_of_array_attempt_get"
 version = "0.1.0"
 edition = "2023_11"
 
 # See more keys and their definitions at https://docs.swmansion.com/scarb/docs/reference/manifest
 
 [dependencies]
 # foo = { path = "vendor/foo" }
diff --git a/listings/ch03-common-collections/no_listing_15_dict_of_array_attempt_get/output.txt b/listings/ch03-common-collections/no_listing_15_dict_of_array_attempt_get/output.txt
@@ -0,0  1,9 @@
 $ scarb cairo-run
    Compiling no_listing_15_dict_of_array_attempt_get v0.1.0 (listings/ch03-common-collections/no_listing_15_dict_of_array_attempt_get/Scarb.toml)
 error: Trait has no implementation in context: core::traits::Copy::<core::nullable::Nullable::<core::array::Array::<core::integer::u8>>>
  --> listings/ch03-common-collections/no_listing_15_dict_of_array_attempt_get/src/lib.cairo:11:20
     let arr = pixels.get(0);
                      ^*^
 
 error: could not compile `no_listing_15_dict_of_array_attempt_get` due to previous error
 error: `scarb metadata` exited with error
diff --git a/listings/ch03-common-collections/no_listing_15_dict_of_array_attempt_get/src/lib.cairo b/listings/ch03-common-collections/no_listing_15_dict_of_array_attempt_get/src/lib.cairo
@@ -0,0  1,18 @@
 //TAG: does_not_compile
 use core::nullable::{match_nullable, FromNullableResult};
 
 fn main() {
     let arr = array![20, 19, 26];
     let mut dict: Felt252Dict<Nullable<Array<u8>>> = Default::default();
     dict.insert(0, NullableTrait::new(arr));
     println!("Array: {:?}", get_array_entry(ref dict, 0));
 }
 
 fn get_array_entry(ref dict: Felt252Dict<Nullable<Array<u8>>>, index: felt252) -> Span<u8> {
     let val = dict.get(0); // This will cause a compiler error
     let arr = match match_nullable(val) {
         FromNullableResult::Null => panic!("No value!"),
         FromNullableResult::NotNull(val) => val.unbox()
     };
     arr.span()
 }
diff --git a/listings/ch03-common-collections/no_listing_16_dict_of_array/.gitignore b/listings/ch03-common-collections/no_listing_16_dict_of_array/.gitignore
@@ -0,0  1 @@
 target
diff --git a/listings/ch03-common-collections/no_listing_16_dict_of_array/Scarb.toml b/listings/ch03-common-collections/no_listing_16_dict_of_array/Scarb.toml
@@ -0,0  1,9 @@
 [package]
 name = "no_listing_16_dict_of_array"
 version = "0.1.0"
 edition = "2023_11"
 
 # See more keys and their definitions at https://docs.swmansion.com/scarb/docs/reference/manifest
 
 [dependencies]
 # foo = { path = "vendor/foo" }
diff --git a/listings/ch03-common-collections/no_listing_16_dict_of_array/src/lib.cairo b/listings/ch03-common-collections/no_listing_16_dict_of_array/src/lib.cairo
@@ -0,0  1,36 @@
 //ANCHOR: all
 use core::nullable::NullableTrait;
 use core::dict::Felt252DictEntryTrait;
 
 //ANCHOR: append
 fn append_value(ref dict: Felt252Dict<Nullable<Array<u8>>>, index: felt252, value: u8) {
     let (entry, arr) = dict.entry(index);
     let mut unboxed_val = arr.deref_or(array![]);
     unboxed_val.append(value);
     dict = entry.finalize(NullableTrait::new(unboxed_val));
 }
 //ANCHOR_END: append
 
 //ANCHOR: get
 fn get_array_entry(ref dict: Felt252Dict<Nullable<Array<u8>>>, index: felt252) -> Span<u8> {
     let (entry, _arr) = dict.entry(index);
     let mut arr = _arr.deref_or(array![]);
     let span = arr.span();
     dict = entry.finalize(NullableTrait::new(arr));
     span
 }
 //ANCHOR_END: get
 
 fn main() {
     let arr = array![20, 19, 26];
     let mut dict: Felt252Dict<Nullable<Array<u8>>> = Default::default();
     dict.insert(0, NullableTrait::new(arr));
     println!("Before insertion: {:?}", get_array_entry(ref dict, 0));
 
     append_value(ref dict, 0, 30);
 
     println!("After insertion: {:?}", get_array_entry(ref dict, 0));
 }
 //ANCHOR_END: all
 
 
diff --git a/quizzes/ch11-03-smart_pointers.toml → quizzes/ch11-02-smart_pointers.toml b/quizzes/ch11-03-smart_pointers.toml → quizzes/ch11-02-smart_pointers.toml
diff --git a/quizzes/ch11-04-operator-overloading.toml → quizzes/ch11-03-operator-overloading.toml b/quizzes/ch11-04-operator-overloading.toml → quizzes/ch11-03-operator-overloading.toml
diff --git a/src/SUMMARY.md b/src/SUMMARY.md
@@ -84,14  84,13 @@
 - [Advanced Cairo Features](ch11-00-advanced-features.md)
 
   - [Custom Data Structures](ch11-01-custom-data-structures.md)
-  - [Using Arrays inside Dictionaries]()
-  - [Smart Pointers](ch11-03-smart-pointers.md)
-  - [Operator Overloading](ch11-04-operator-overloading.md)
-  - [Working with Hashes](ch11-05-hash.md)
-  - [Macros](ch11-06-macros.md)
-  - [Inlining in Cairo](ch11-07-inlining-in-cairo.md)
   - [Smart Pointers](ch11-02-smart-pointers.md)
   - [Operator Overloading](ch11-03-operator-overloading.md)
   - [Working with Hashes](ch11-04-hash.md)
   - [Macros](ch11-05-macros.md)
   - [Inlining in Cairo](ch11-06-inlining-in-cairo.md)
   - [Gas Optimisation]()
-  - [Printing](ch11-09-printing.md)
   - [Printing](ch11-08-printing.md)
 
 - [Appendix (Cairo)](appendix-00.md)
 

diff --git a/src/appendix-03-derivable-traits.md b/src/appendix-03-derivable-traits.md
@@ -118,7  118,7 @@ Here we are converting a serialized array span back to the struct `A`. `deserial
 
 It is possible to derive the `Hash` trait on structs and enums. This allows them to be hashed easily using any available hash function. For a struct or an enum to derive the `Hash` attribute, all fields or variants need to be hashable themselves.
 
-You can refer to the [Hashes section](ch11-05-hash.md) to get more information about how to hash complex data types.
 You can refer to the [Hashes section](ch11-04-hash.md) to get more information about how to hash complex data types.
 
 ## Starknet Storage with `starknet::Store`
 

diff --git a/src/ch01-02-hello-world.md b/src/ch01-02-hello-world.md
@@ -201,7  201,7 @@ expression is over and the next one is ready to begin. Most lines of Cairo code
 end with a semicolon.
 
 [devtools]: ./appendix-04-useful-development-tools.md
-[macros]: ./ch11-06-macros.md
 [macros]: ./ch11-05-macros.md
 
 {{#quiz ../quizzes/ch01-02-hello-world.toml}}
 
@@ -216,4  216,4 @@ Let’s recap what we’ve learned so far about Scarb:
 
 An additional advantage of using Scarb is that the commands are the same no matter which operating system you’re working on. So, at this point, we’ll no longer provide specific instructions for Linux and macOS versus Windows.
 
-You’re already off to a great start on your Cairo journey! This is a great time to build a more substantial program to get used to reading and writing Cairo code.
 You’re already off to a great start on your Cairo journey! This is a great time to build a more substantial program to get used to reading and writing Cairo code.
diff --git a/src/ch02-01-variables-and-mutability.md b/src/ch02-01-variables-and-mutability.md
@@ -116,7  116,7 @@ Nonetheless, it is possible to use the `consteval_int!` macro to create a `const
 {{#include ../listings/ch02-common-programming-concepts/no_listing_00_consts/src/lib.cairo:consteval_const}}
 ```
 
-We will dive into more detail about macros in the [dedicated section](./ch11-06-macros.md).
 We will dive into more detail about macros in the [dedicated section](./ch11-05-macros.md).
 
 Cairo's naming convention for constants is to use all uppercase with underscores between words.
 
@@ -195,4  195,4 @@ The error says we were expecting a `u64` (the original type) but we got a differ
 
 {{#quiz ../quizzes/ch02-01-variables-and-mutability.toml}}
 
-Now that we’ve explored how variables work, let’s look at more data types they can have.
 Now that we’ve explored how variables work, let’s look at more data types they can have.
diff --git a/src/ch03-02-dictionaries.md b/src/ch03-02-dictionaries.md
@@ -192,7  192,7 @@ This is implemented by some common data types, such as most unsigned integers, `
 This means that making a dictionary of types not natively supported is not a straightforward task, because you would need to write a couple of trait implementations in order to make the data type a valid dictionary value type.
 To compensate this, you can wrap your type inside a `Nullable<T>`.
 
-`Nullable<T>` is a smart pointer type that can either point to a value or be `null` in the absence of value. It is usually used in Object Oriented Programming Languages when a reference doesn't point anywhere. The difference with `Option` is that the wrapped value is stored inside a `Box<T>` data type. The `Box<T>` type is a smart pointer that allows us to use a dedicated `boxed_segment` memory segment for our data, and access this segment using a pointer that can only be manipulated in one place at a time. See [Smart Pointers Chapter](./ch11-03-smart-pointers.md) for more information.
 `Nullable<T>` is a smart pointer type that can either point to a value or be `null` in the absence of value. It is usually used in Object Oriented Programming Languages when a reference doesn't point anywhere. The difference with `Option` is that the wrapped value is stored inside a `Box<T>` data type. The `Box<T>` type is a smart pointer that allows us to use a dedicated `boxed_segment` memory segment for our data, and access this segment using a pointer that can only be manipulated in one place at a time. See [Smart Pointers Chapter](./ch11-02-smart-pointers.md) for more information.
 
 Let's show using an example. We will try to store a `Span<felt252>` inside a dictionary. For that, we will use `Nullable<T>` and `Box<T>`. Also, we are storing a `Span<T>` and not an `Array<T>` because the latter does not implement the `Copy<T>` trait which is required for reading from a dictionary.
 
@@ -228,4  228,50 @@ The complete script would look like this:
 {{#include ../listings/ch03-common-collections/no_listing_13_dict_of_complex/src/lib.cairo:all}}
 ```
 
 ## Using Arrays inside Dictionaries
 
 In the previous section, we explored how to store and retrieve complex types inside a dictionary using `Nullable<T>` and `Box<T>`. Now, let's take a look at how to store an array inside a dictionary and dynamically modify its contents.
 
 Storing arrays in dictionaries in Cairo is slightly different from storing other types. This is because arrays are more complex data structures that require special handling to avoid issues with memory copying and references.
 
 First, let's look at how to create a dictionary and insert an array into it. This process is pretty straightforward and follows a similar pattern to inserting other types of data:
 
 ```rust
 {{#include ../listings/ch03-common-collections/no_listing_14_dict_of_array_insert/src/lib.cairo}}
 ```
 
 However, attempting to read an array from the dictionary using the `get` method will result in a compiler error. This is because `get` tries to copy the array in memory, which is not possible for arrays (as we've already mentioned in the [previous section][nullable dictionaries values], `Array<T>` does not implement the `Copy<T>` trait):
 
 ```rust
 {{#include ../listings/ch03-common-collections/no_listing_15_dict_of_array_attempt_get/src/lib.cairo}}
 ```
 
 ```shell
 {{#include ../listings/ch03-common-collections/no_listing_15_dict_of_array_attempt_get/output.txt}}
 ```
 
 To correctly read an array from the dictionary, we need to use dictionary entries. This allows us to get a reference to the array value without copying it:
 
 ```rust,noplayground
 {{#include ../listings/ch03-common-collections/no_listing_16_dict_of_array/src/lib.cairo:get}}
 ```
 
 > Note: We must convert the array to a `Span` before finalizing the entry, because calling `NullableTrait::new(arr)` moves the array, thus making it impossible to return it from the function.
 
 To modify the stored array, such as appending a new value, we can use a similar approach. The following `append_value` function demonstrates this:
 
 ```rust,noplayground
 {{#include ../listings/ch03-common-collections/no_listing_16_dict_of_array/src/lib.cairo:append}}
 ```
 
 In the `append_value` function, we access the dictionary entry, dereference the array, append the new value, and finalize the entry with the updated array.
 
 > Note: Removing an item from a stored array can be implemented in a similar manner.
 
 Below is the complete example demonstrating the creation, insertion, reading, and modification of an array in a dictionary:
 
 ```rust
 {{#include ../listings/ch03-common-collections/no_listing_16_dict_of_array/src/lib.cairo:all}}
 ```
 
 {{#quiz ../quizzes/ch03-02-dictionaries.toml}}
diff --git a/src/ch10-01-how-to-write-tests.md b/src/ch10-01-how-to-write-tests.md
@@ -332,7  332,7 @@ Error: test result: FAILED. 0 passed; 1 failed; 0 ignored
 We can see the value we actually got in the test output, which would help us
 debug what happened instead of what we were expecting to happen.
 
-[formatting]: ./ch11-09-printing.md#formatting
 [formatting]: ./ch11-08-printing.md#formatting
 
 ## Checking for panics with `should_panic`
 

diff --git a/src/ch11-03-smart-pointers.md → src/ch11-02-smart-pointers.md b/src/ch11-03-smart-pointers.md → src/ch11-02-smart-pointers.md
@@ -20,7  20,7 @@ Boxes have very little performance overhead, other than writing their inner valu
 We’ll demonstrate the first situation in the [“Enabling Recursive Types with Boxes”][nullable recursive types] section.
 In the second case, transferring ownership of a large amount of data can take a long time because the data is copied around in memory. To improve performance in this situation, we can store the large amount of data in the boxed segment using a box type. Then, only the small amount of pointer data is copied around in memory, while the data it references stays in one place on the boxed segment.
 
-[nullable recursive types]: ./ch11-03-smart-pointers.md#enabling-recursive-types-with-nullable-boxes
 [nullable recursive types]: ./ch11-02-smart-pointers.md#enabling-recursive-types-with-nullable-boxes
 
 ### Using a `Box<T>` to Store Data in the Boxed Segment
 
@@ -80,4  80,4 @@ If we try to access an element that does not exist in a dictionary, the code wil
 
 [dictionary nullable span]: /ch03-02-dictionaries.md#dictionaries-of-types-not-supported-natively
 
-{{#quiz ../quizzes/ch11-03-smart_pointers.toml}}
 {{#quiz ../quizzes/ch11-02-smart_pointers.toml}}
diff --git a/src/ch11-02-using-arrays-inside-dictionaries.md b/src/ch11-02-using-arrays-inside-dictionaries.md
diff --git a/src/ch11-04-operator-overloading.md → src/ch11-03-operator-overloading.md b/src/ch11-04-operator-overloading.md → src/ch11-03-operator-overloading.md
@@ -15,4  15,4 @@ In the code above, we're implementing the `Add` trait for the `Potion` type. The
 
 As illustrated in the example, overloading an operator requires specification of the concrete type being overloaded. The overloaded generic trait is `Add<T>`, and we define a concrete implementation for the type `Potion` with `Add<Potion>`.
 
-{{#quiz ../quizzes/ch11-04-operator-overloading.toml}}
 {{#quiz ../quizzes/ch11-03-operator-overloading.toml}}
diff --git a/src/ch11-05-hash.md → src/ch11-04-hash.md b/src/ch11-05-hash.md → src/ch11-04-hash.md
diff --git a/src/ch11-06-macros.md → src/ch11-05-macros.md b/src/ch11-06-macros.md → src/ch11-05-macros.md
@@ -20,7  20,7 @@ See [Entry Point Selector](./ch15-02-contract-dispatchers-library-dispatchers-an
 
 ## `print!` and `println!` Macros
 
-Please refer to the [Printing](./ch11-09-printing.md) page.
 Please refer to the [Printing](./ch11-08-printing.md) page.
 
 ## `array!` Macro
 
@@ -36,11  36,11 @@ See [How to Write Tests](./ch10-01-how-to-write-tests.md) page.
 
 ## `format!` Macro
 
-See [Printing](./ch11-09-printing.html#formatting) page.
 See [Printing](./ch11-08-printing.html#formatting) page.
 
 ## `write!` and `writeln!` Macros
 
-See [Printing](./ch11-09-printing.html#printing-custom-data-types) page.
 See [Printing](./ch11-08-printing.html#printing-custom-data-types) page.
 
 ## `get_dep_component!`, `get_dep_component_mut` and `component!` Macros
 

diff --git a/src/ch11-07-inlining-in-cairo.md → src/ch11-06-inlining-in-cairo.md b/src/ch11-07-inlining-in-cairo.md → src/ch11-06-inlining-in-cairo.md
diff --git a/src/ch11-08-gas-optimisation.md → src/ch11-07-gas-optimisation.md b/src/ch11-08-gas-optimisation.md → src/ch11-07-gas-optimisation.md
diff --git a/src/ch11-09-printing.md → src/ch11-08-printing.md b/src/ch11-09-printing.md → src/ch11-08-printing.md
@@ -25,8  25,8 @@ Here are some examples:
 > `print!` and `println!` macros use the `Display` trait under the hood, and are therefore used to print the value of types that implement it. This is the case for basic data types, but not for more complex ones. If you try to print complex data type values with these macros, e.g. for debugging purposes, you will get an error. In that case, you can either [manually implement][print with display] the `Display` trait for your type or use the `Debug` trait (see [below][print with debug]).
 
 [byte array]: ./ch02-02-data-types.md#byte-array-strings
-[print with display]: ./ch11-09-printing.md#printing-custom-data-types
-[print with debug]: ./ch11-09-printing.md#print-debug-traces
 [print with display]: ./ch11-08-printing.md#printing-custom-data-types
 [print with debug]: ./ch11-08-printing.md#print-debug-traces
 
 ## Formatting
Original file line number	Diff line number	Diff line change
Expand Up		@@ -15,4 15,4 @@ In the code above, we're implementing the `Add` trait for the `Potion` type. The

		As illustrated in the example, overloading an operator requires specification of the concrete type being overloaded. The overloaded generic trait is `Add<T>`, and we define a concrete implementation for the type `Potion` with `Add<Potion>`.

		{{#quiz ../quizzes/ch11-04-operator-overloading.toml}}
		{{#quiz ../quizzes/ch11-03-operator-overloading.toml}}