字典

Cairo在其核心库中提供了一个类似字典的类型。Felt252Dict<T> 数据类型表示键值对的集合，其中每个键都是唯一的，并与相应的值相关联。这种类型的数据结构在不同的编程语言中有不同的名称，如映射、哈希表、关联数组等。

Felt252Dict<T> 类型在你想以某种方式组织数据而使用Array<T>和索引不能满足要求时非常有用。Cairo字典还允许程序员在内存非可变的情况下轻松地模拟可变内存。

Basic Use of Dictionaries

It is normal in other languages when creating a new dictionary to define the data types of both key and value. In Cairo, the key type is restricted to felt252, leaving only the possibility to specify the value data type, represented by T in Felt252Dict<T>.

Felt252Dict<T>的核心功能在trait Felt252DictTrait中实现，它包括所有的基本操作。在其中我们可以看到：

1. insert(felt252, T) -> () to write values to a dictionary instance and
2. get(felt252) -> T to read values from it.

这些函数允许我们使用其他语言一样的方法来操作字典。在下面的示例中，我们创建一个字典来表示个体及其余额之间的映射：

use core::dict::Felt252Dict;

fn main() {
    let mut balances: Felt252Dict<u64> = Default::default();

    balances.insert('Alex', 100);
    balances.insert('Maria', 200);

    let alex_balance = balances.get('Alex');
    assert!(alex_balance == 100, "Balance is not 100");

    let maria_balance = balances.get('Maria');
    assert!(maria_balance == 200, "Balance is not 200");
}

We can create a new instance of Felt252Dict<u64> by using the default method of the Default trait and add two individuals, each one with their own balance, using the insert method. Finally, we check the balance of our users with the get method. These methods are defined in the Felt252DictTrait trait in the core library.

Throughout the book we have talked about how Cairo's memory is immutable, meaning you can only write to a memory cell once but the Felt252Dict<T> type represents a way to overcome this obstacle. We will explain how this is implemented later on in "Dictionaries Underneath".

在前面示例的基础上，让我们展示一个同一用户的余额产生变化的代码示例：

use core::dict::Felt252Dict;

fn main() {
    let mut balances: Felt252Dict<u64> = Default::default();

    // Insert Alex with 100 balance
    balances.insert('Alex', 100);
    // Check that Alex has indeed 100 associated with him
    let alex_balance = balances.get('Alex');
    assert!(alex_balance == 100, "Alex balance is not 100");

    // Insert Alex again, this time with 200 balance
    balances.insert('Alex', 200);
    // Check the new balance is correct
    let alex_balance_2 = balances.get('Alex');
    assert!(alex_balance_2 == 200, "Alex balance is not 200");
}

Notice how in this example we added the 'Alex' individual twice, each time using a different balance and each time that we checked for its balance it had the last value inserted! Felt252Dict<T> effectively allows us to "rewrite" the stored value for any given key.

在继续解释字典是如何实现的之前，值得一提的是，一旦你实例化了一个 Felt252Dict<T>，其所有的键值都将被初始化为0。这意味着，例如，如果你试图获取一个不存在的用户的余额，你将得到0，而不是一个错误或未定义的值。这也意味着无法从字典中删除数据。在代码中使用这歌结构纳时你需要考虑到这一点。

到此为止，我们已经了解了 Felt252Dict<T> 的所有基本特性，以及它是如何在外部表现上模仿其他语言中相应数据结构的。Cairo的核心是一种非确定的图灵完备的编程语言，与其他任何流行的语言都有很大的不同，这意味着字典的实现也有很大的不同！

在下面的章节中，我们将深入介绍 Felt252Dict<T> 的内部机制以及为使其正常工作而做出的妥协。之后，我们将介绍如何将字典与其他数据结构一起使用，以及使用entry方法作为与字典交互的另一种方式。

Dictionaries Underneath

Cairo的非确定性设计的限制之一是它的内存系统是不可变的，因此为了模拟可变性，语言将Felt252Dict<T>实现为一个条目(entry)列表。每个条目代表了字典被读取/更新/写入的时间。一个条目有三个字段：

1. A key field that identifies the key for this key-value pair of the dictionary.
2. A previous_value field that indicates which previous value was held at key.
3. A new_value field that indicates the new value that is held at key.

如果我们尝试使用高级结构来实现 Felt252Dict<T>，我们将在内部把它定义为 Array<Entry<T>> 其中每个 Entry<T> 都有关于它代表的键值对的信息，以及它持有的前一个值和新值。Entry<T> 的定义如下：

struct Entry<T> {
    key: felt252,
    previous_value: T,
    new_value: T,
}

For each time we interact with a Felt252Dict<T>, a new Entry<T> will be registered:

• A get would register an entry where there is no change in state, and previous and new values are stored with the same value.
• An insert would register a new Entry<T> where the new_value would be the element being inserted, and the previous_value the last element inserted before this. In case it is the first entry for a certain key, then the previous value will be zero.

条目列表的使用展示了这里没有任何值的覆盖，只是在每次Felt252Dict<T>交互中创建新的存储单元。让我们使用上一节中的 balances 字典并插入用户 'Alex' 和 'Maria' 来展示一个例子：

use core::dict::Felt252Dict;

struct Entry<T> {
    key: felt252,
    previous_value: T,
    new_value: T,
}

fn main() {
    let mut balances: Felt252Dict<u64> = Default::default();
    balances.insert('Alex', 100_u64);
    balances.insert('Maria', 50_u64);
    balances.insert('Alex', 200_u64);
    balances.get('Maria');
}

这些指令将产生以下条目列表：

注意，由于'Alex'被插入了两次，所以它出现了两次，并且'previous'和'current'值被正确的设置。从'Maria'中读取的数据也是一个条目，从前值到现值没有发生变化。

这种实现 Felt252Dict<T> 的方法意味着每一次读/写操作，都要扫描整个条目列表，寻找最后一个具有相同 key的条目。一旦条目被找到，它的new_value就会被提取出来，并作为previous_value添加到新的条目中。这意味着与 Felt252Dict<T> 交互的最坏情况下的时间复杂度为 O(n)，其中 n 是列表中的条目数。

If you pour some thought into alternate ways of implementing Felt252Dict<T> you'd surely find them, probably even ditching completely the need for a previous_value field, nonetheless, since Cairo is not your normal language this won't work. One of the purposes of Cairo is, with the STARK proof system, to generate proofs of computational integrity. This means that you need to verify that program execution is correct and inside the boundaries of Cairo restrictions. One of those boundary checks consists of "dictionary squashing" and that requires information on both previous and new values for every entry.

Squashing Dictionaries

To verify that the proof generated by a Cairo program execution that used a Felt252Dict<T> is correct, we need to check that there wasn't any illegal tampering with the dictionary. This is done through a method called squash_dict that reviews each entry of the entry list and checks that access to the dictionary remains coherent throughout the execution.

压缩过程如下：给定所有具有特定键k的条目，按照它们被插入的相同顺序，验证第i个条目new_value是否等于第i+1个条目previous_value。

例如，给定以下条目列表：

压缩后，条目列表将缩减为：

如果第一张表中的任何值发生变化，则在运行期间压缩将会失败。

Dictionary Destruction

If you run the examples from "Basic Use of Dictionaries" section, you'd notice that there was never a call to squash dictionary, but the program compiled successfully nonetheless. What happened behind the scene was that squash was called automatically via the Felt252Dict<T> implementation of the Destruct<T> trait. This call occurred just before the balance dictionary went out of scope.

The Destruct<T> trait represents another way of removing instances out of scope apart from Drop<T>. The main difference between these two is that Drop<T> is treated as a no-op operation, meaning it does not generate new CASM while Destruct<T> does not have this restriction. The only type which actively uses the Destruct<T> trait is Felt252Dict<T>, for every other type Destruct<T> and Drop<T> are synonyms. You can read more about these traits in Drop and Destruct section of Appendix C.

Later in "Dictionaries as Struct Members" section, we will have a hands-on example where we implement the Destruct<T> trait for a custom type.

More Dictionaries

到此为止，我们已经全面地介绍了Felt252Dict<T>的功能，以及它是如何和为什么以某种方式实现的。如果您还没有完全理解，请不要担心，因为在本节中我们将提供更多使用字典的示例。

We will start by explaining the entry method which is part of a dictionary basic functionality included in Felt252DictTrait<T> which we didn't mention at the beginning. Soon after, we will see examples of how to use Felt252Dict<T> with other complex types such as Array<T>.

Entry and Finalize

In the "Dictionaries Underneath" section, we explained how Felt252Dict<T> internally worked. It was a list of entries for each time the dictionary was accessed in any manner. It would first find the last entry given a certain key and then update it accordingly to whatever operation it was executing. The Cairo language gives us the tools to replicate this ourselves through the entry and finalize methods.

entry 方法作为Felt252DictTrait<T> 的一部分，目的是在给定键的情况下创建一个新的条目。一旦被调用，该方法将获得字典的所有权并返回要更新的条目。方法签名如下:

fn entry(self: Felt252Dict<T>, key: felt252) -> (Felt252DictEntry<T>, T) nopanic

The first input parameter takes ownership of the dictionary while the second one is used to create the appropriate entry. It returns a tuple containing a Felt252DictEntry<T>, which is the type used by Cairo to represent dictionary entries, and a T representing the value held previously. The nopanic notation simply indicates that the function is guaranteed to never panic.

接下来要做的是用新值更新条目。为此，我们使用finalize方法插入条目并返回字典的所有权：

fn finalize(self: Felt252DictEntry<T>, new_value: T) -> Felt252Dict<T>

This method receives the entry and the new value as parameters, and returns the updated dictionary.

让我们看一个使用entry和finalize的例子。想象一下，我们想从字典中实现我们自己版本的get方法。我们应该这样做：

1. Create the new entry to add using the entry method.
2. Insert back the entry where the new_value equals the previous_value.
3. Return the value.

实现我们的自定义get将如下所示：

use core::dict::{Felt252Dict, Felt252DictEntryTrait};

fn custom_get<T, +Felt252DictValue<T>, +Drop<T>, +Copy<T>>(
    ref dict: Felt252Dict<T>, key: felt252
) -> T {
    // Get the new entry and the previous value held at `key`
    let (entry, prev_value) = dict.entry(key);

    // Store the value to return
    let return_value = prev_value;

    // Update the entry with `prev_value` and get back ownership of the dictionary
    dict = entry.finalize(prev_value);

    // Return the read value
    return_value
}

The ref keyword means that the ownership of the variable will be given back at the end of the function. This concept will be explained in more detail in the "References and Snapshots" section.

实现insert方法将遵循类似的工作流程，除了在最终确定时插入一个新值。如果我们要实现它，它将看起来像下面这样：

use core::dict::{Felt252Dict, Felt252DictEntryTrait};

fn custom_insert<T, +Felt252DictValue<T>, +Destruct<T>, +Drop<T>>(
    ref dict: Felt252Dict<T>, key: felt252, value: T
) {
    // Get the last entry associated with `key`
    // Notice that if `key` does not exist, `_prev_value` will
    // be the default value of T.
    let (entry, _prev_value) = dict.entry(key);

    // Insert `entry` back in the dictionary with the updated value,
    // and receive ownership of the dictionary
    dict = entry.finalize(value);
}

最后要说明的是，这两个方法的实现方式类似于Felt252Dict<T>的insert和get的实现方式。这段代码展示了一些使用示例：

use core::dict::{Felt252Dict, Felt252DictEntryTrait};

fn custom_get<T, +Felt252DictValue<T>, +Drop<T>, +Copy<T>>(
    ref dict: Felt252Dict<T>, key: felt252
) -> T {
    // Get the new entry and the previous value held at `key`
    let (entry, prev_value) = dict.entry(key);

    // Store the value to return
    let return_value = prev_value;

    // Update the entry with `prev_value` and get back ownership of the dictionary
    dict = entry.finalize(prev_value);

    // Return the read value
    return_value
}

fn custom_insert<T, +Felt252DictValue<T>, +Destruct<T>, +Drop<T>>(
    ref dict: Felt252Dict<T>, key: felt252, value: T
) {
    // Get the last entry associated with `key`
    // Notice that if `key` does not exist, `_prev_value` will
    // be the default value of T.
    let (entry, _prev_value) = dict.entry(key);

    // Insert `entry` back in the dictionary with the updated value,
    // and receive ownership of the dictionary
    dict = entry.finalize(value);
}

fn main() {
    let mut dict: Felt252Dict<u64> = Default::default();

    custom_insert(ref dict, '0', 100);

    let val = custom_get(ref dict, '0');

    assert!(val == 100, "Expecting 100");
}

Dictionaries of Types not Supported Natively

One restriction of Felt252Dict<T> that we haven't talked about is the trait Felt252DictValue<T>. This trait defines the zero_default method which is the one that gets called when a value does not exist in the dictionary. This is implemented by some common data types, such as most unsigned integers, bool and felt252 - but it is not implemented for more complex types such as arrays, structs (including u256), and other types from the core library. 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 for more information.

让我们来举例说明。我们将尝试在字典中存储一个Span<felt252>。为此，我们将使用 Nullable<T> 和 Box<T>。另外，我们要存储的是一个 Span<T> 而不是一个 Array<T> ，因为后者没有实现 Copy<T> 特性，而从字典中读取数据是需要这个特性的。

use core::dict::Felt252Dict;
use core::nullable::{NullableTrait, match_nullable, FromNullableResult};

fn main() {
    // Create the dictionary
    let mut d: Felt252Dict<Nullable<Span<felt252>>> = Default::default();

    // Create the array to insert
    let a = array![8, 9, 10];

    // Insert it as a `Span`
    d.insert(0, NullableTrait::new(a.span()));

//...

在这段代码中，我们首先创建了一个新的字典d。我们希望它保存一个Nullable<Span>。然后，我们创建了一个数组，并在其中填入值。

The last step is inserting the array as a span inside the dictionary. Notice that we do this using the new function of the NullableTrait.

一旦元素存在字典中，并且我们想获取它，我们将遵循相同的步骤，但顺序相反。下面的代码展示了如何实现这一点：

//...

    // Get value back
    let val = d.get(0);

    // Search the value and assert it is not null
    let span = match match_nullable(val) {
        FromNullableResult::Null => panic!("No value found"),
        FromNullableResult::NotNull(val) => val.unbox(),
    };

    // Verify we are having the right values
    assert!(*span.at(0) == 8, "Expecting 8");
    assert!(*span.at(1) == 9, "Expecting 9");
    assert!(*span.at(2) == 10, "Expecting 10");
}

我们在这里：

1. Read the value using get.
2. Verified it is non-null using the match_nullable function.
3. Unwrapped the value inside the box and asserted it was correct.

完整的脚本如下：

use core::dict::Felt252Dict;
use core::nullable::{NullableTrait, match_nullable, FromNullableResult};

fn main() {
    // Create the dictionary
    let mut d: Felt252Dict<Nullable<Span<felt252>>> = Default::default();

    // Create the array to insert
    let a = array![8, 9, 10];

    // Insert it as a `Span`
    d.insert(0, NullableTrait::new(a.span()));

    // Get value back
    let val = d.get(0);

    // Search the value and assert it is not null
    let span = match match_nullable(val) {
        FromNullableResult::Null => panic!("No value found"),
        FromNullableResult::NotNull(val) => val.unbox(),
    };

    // Verify we are having the right values
    assert!(*span.at(0) == 8, "Expecting 8");
    assert!(*span.at(1) == 9, "Expecting 9");
    assert!(*span.at(2) == 10, "Expecting 10");
}

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:

use core::dict::Felt252Dict;

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.");
}

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, Array<T> does not implement the Copy<T> trait):

use core::nullable::{match_nullable, FromNullableResult};
use core::dict::Felt252Dict;

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()
}

$ 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:13:20
    let val = dict.get(0); // This will cause a compiler error
                   ^*^

error: could not compile `no_listing_15_dict_of_array_attempt_get` due to previous error
error: `scarb metadata` exited with error

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:

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
}

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:

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));
}

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:

use core::nullable::NullableTrait;
use core::dict::{Felt252Dict, Felt252DictEntryTrait};

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));
}

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
}

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));
}