Diccionarios

Cairo proporciona en su libreria principal un tipo de datos similar a un diccionario. El tipo de datos Felt252Dict representa una colección de pares key-value donde cada key es única y está asociada con un value correspondiente. Este tipo de estructura de datos se conoce de manera diferente en varios lenguajes de programación, como mapas, tablas hash, arrays asociativos y muchos otros.

El tipo Felt252Dict es útil cuando deseas organizar tus datos de una manera específica para la cual el uso de un Array e indexación no es suficiente. Los diccionarios en Cairo también permiten al programador simular fácilmente la existencia de memoria mutable cuando no la hay.

Uso Basico de Diccionarios

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>.

La funcionalidad principal de un Felt252Dict se implementa en el rasgo Felt252DictTrait, que incluye todas las operaciones básicas. Entre ellas podemos encontrar:

1. insert(felt252, T) -> () para escribir valores en una instancia de diccionario.
2. get(felt252) -> T para leer sus valores.

Estas funciones nos permiten manipular diccionarios como en cualquier otro lenguaje. En el siguiente ejemplo, creamos un diccionario para representar una relación entre individuos y sus saldos:

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

Podemos crear una nueva instancia de Felt252Dict<u64> utilizando el método default del rasgo Default y añadir dos individuos, cada uno con su propio saldo, utilizando el método insert. Por último, comprobamos el saldo de nuestros usuarios con el método get. Estos métodos están definidos en el trait Felt252DictTrait de la librería principal.

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".

Basándonos en nuestro ejemplo anterior, vamos a mostrar un ejemplo de código en el que cambia el saldo del mismo usuario:

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.

Antes de seguir adelante y explicar cómo se implementan los diccionarios vale la pena mencionar que una vez que instanciar un Felt252Dict<T>, detrás de las escenas de todas las claves tienen sus valores asociados inicializado como cero. Esto significa que si, por ejemplo, intentas obtener el saldo de un usuario inexistente obtendrás 0 en lugar de un error o un valor indefinido. Esto también significa que no hay forma de borrar datos de un diccionario. Algo a tener en cuenta a la hora de incorporar esta estructura a tu código.

Hasta este punto, hemos visto todas las características básicas de Felt252Dict<T> y cómo imita el mismo comportamiento que las estructuras de datos correspondientes en cualquier otro lenguaje, es decir, externamente, por supuesto. Cairo es en su núcleo un lenguaje de programación Turing-completo no determinista, muy diferente de cualquier otro lenguaje popular existente, lo que como consecuencia significa que ¡los diccionarios se implementan también de forma muy diferente!

En las siguientes secciones, vamos a dar algunas ideas sobre Felt252Dict<T> mecanismos internos y los compromisos que se tomaron para que funcionen. Después de eso, vamos a echar un vistazo a cómo utilizar los diccionarios con otras estructuras de datos, así como utilizar el método entry como otra forma de interactuar con ellos.

Diccionarios por Debajo

Una de las restricciones del diseño no determinista de Cairo es que su sistema de memoria es inmutable, así que para simular la mutabilidad, el lenguaje implementa Felt252Dict<T> como una lista de entradas. Cada una de las entradas representa un momento en el que se accedió al diccionario para leer/actualizar/escribir. Una entrada tiene tres campos:

1. A key field that identifies the key for this key-value pair of the dictionary.
2. Un campo previous_value que indica qué valor anterior tenía key.
3. Un campo new_value que indica el nuevo valor que se tiene en key.

Si intentamos implementar Felt252Dict<T> usando estructuras de alto nivel lo definiríamos internamente como Array<Entry<T>> donde cada Entry<T> tiene información sobre qué par key-value representa y los valores anteriores y nuevos que contiene. La definición de Entry<T> sería:

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:

• Un get registraría una entrada en la que no hay cambio de estado, los valores anteriores y nuevos se almacenan con el mismo valor.
• Un insert registraría una nueva Entry<T> donde el new_value sería el elemento que se inserta, y el previous_value el último elemento insertado antes de este. En caso de que sea la primera entrada para una determinada clave, entonces el valor anterior será cero.

El uso de esta lista de entradas muestra cómo no hay ninguna reescritura, sólo la creación de nuevas celdas de memoria por interacción Felt252Dict<T>. Vamos a mostrar un ejemplo de esto usando el diccionario balances de la sección anterior e insertando los usuarios Alex y 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');
}

Estas instrucciones producirían la siguiente lista de entradas:

Observe que como 'Alex' se insertó dos veces, aparece dos veces y los valores previous y current se establecen correctamente. También la lectura de 'Maria' registró una entrada sin cambios de los valores anteriores a los actuales.

Este enfoque para implementar Felt252Dict<T> significa que para cada operación de lectura/escritura, hay un escaneo de toda la lista de entradas en busca de la última entrada con la misma clave. Una vez encontrada la entrada, se extrae su nuevo_valor y se utiliza en la nueva entrada que se añade como valor_anterior. Esto significa que interactuar con Felt252Dict<T> tiene una complejidad temporal en el peor de los casos de O(n) donde n es el número de entradas de la lista.

Si te pones a pensar en formas alternativas de implementar Felt252Dict<T> seguramente las encontrarás, probablemente incluso eliminando completamente la necesidad de un campo previous_value, sin embargo, como Cairo no es un lenguaje normal esto no funcionará. Uno de los propósitos de Cairo es, con el sistema de pruebas STARK, generar pruebas de integridad computacional. Esto significa que necesitas verificar que la ejecución del programa es correcta y dentro de los límites de las restricciones de Cairo. Una de esas comprobaciones de límites consiste en "comprimir diccionarios" y eso requiere información tanto de los valores anteriores como de los nuevos para cada entrada.

Comprimir Diccionarios

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.

El proceso de comprimir es el siguiente: dadas todas las entradas con cierta clave k, tomadas en el mismo orden en que fueron insertadas, verificar que la i-ésima entrada new_value es igual a la i-th + 1 entrada previous_value.

Por ejemplo, dada la siguiente lista de entradas:

Después de comprimir, la lista de entradas se reduciría a:

En caso de un cambio en alguno de los valores de la primera tabla, la compresión habría fallado durante la ejecución.

Destrucción de Diccionarios

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.

Más Diccionarios

Hasta este punto, hemos dado una visión general de la funcionalidad de Felt252Dict<T> de cómo y por qué se implementa de una determinada manera. Si no lo has entendido todo, no te preocupes porque en esta sección tendremos algunos ejemplos más utilizando diccionarios.

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>.

Entrada y Finalización

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.

El método entry viene como parte de Felt252DictTrait<T> con el propósito de crear una nueva entrada dada una determinada clave. Una vez llamado, este método toma posesión del diccionario y devuelve la entrada a actualizar. La característica del método es la siguiente:

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.

Lo siguiente que hay que hacer es actualizar la entrada con el nuevo valor. Para esto, utilizamos el método finalize que inserta la entrada y devuelve la propiedad del diccionario:

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.

Veamos un ejemplo utilizando entry y finalize. Imaginemos que queremos implementar nuestra propia versión del método get de un diccionario. Deberíamos hacer lo siguiente:

1. Create the new entry to add using the entry method.
2. Insertar nuevamente la entrada donde el new_value sea igual al previous_value.
3. Devolver el valor.

Implementar nuestra propia función get se vería así:

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.

Implementar el método insert seguiría un flujo de trabajo similar, excepto por la inserción de un nuevo valor al finalizar. Si lo implementáramos, tendría el siguiente aspecto:

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

Como nota final, estos dos métodos se implementan de manera similar a cómo insert y get se implementan para Felt252Dict<T>. Este código muestra algunos ejemplos de uso:

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.

Vamos a mostrarlo con un ejemplo. Intentaremos almacenar un Span<felt252> dentro de un diccionario. Para ello utilizaremos Nullable<T> y Box<T>. Además, estamos almacenando un Span<T> y no un Array<T> porque este último no implementa el rasgo Copy<T> que es necesario para leer de un diccionario.

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

//...

En este fragmento de código, lo primero que hicimos fue crear un nuevo diccionario d. Queremos que contenga un Nullable<Span>. Después, creamos un array y lo llenamos de valores.

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.

Una vez que el elemento está dentro del diccionario, y queremos obtenerlo, seguimos los mismos pasos pero en orden inverso. El siguiente código muestra cómo conseguirlo:

//...

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

Aquí tenemos:

1. Lee el valor utilizando get.
2. Verificado que no es nulo usando la función match_nullable.
3. Desenvolvió el valor dentro de la caja y afirmó que era correcto.

El script completo tendría este aspecto:

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