Dictionaries

Cairo menyediakan dalam pustaka intinya tipe data yang mirip dengan kamus (dictionary-like type). Tipe data Felt252Dict<T> mewakili kumpulan pasangan kunci-nilai dimana setiap kunci bersifat unik dan terkait dengan nilai yang sesuai. Jenis struktur data ini dikenal dengan berbagai istilah dalam bahasa pemrograman yang berbeda, seperti maps, hash tables, associative arrays, dan banyak yang lainnya.

Tipe Felt252Dict<T> berguna ketika Anda ingin mengatur data Anda dengan cara tertentu di mana penggunaan Array<T> dan pengindeksan tidak mencukupi. Kamus Cairo juga memungkinkan programmer untuk dengan mudah mensimulasikan keberadaan memori yang dapat diubah (mutable memory) ketika memori tersebut sebenarnya tidak ada.

Penggunaan Dasar dari Kamus

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

Fungsi inti dari Felt252Dict<T> diimplementasikan dalam trait Felt252DictTrait yang mencakup semua operasi dasar. Di antara mereka, kita dapat menemukan:

1. insert(felt252, T) -> () untuk menulis nilai ke sebuah contoh kamus (dictionary) dan
2. get(felt252) -> T untuk membaca nilai dari kamus tersebut.

Fungsi-fungsi ini memungkinkan kita untuk memanipulasi kamus seperti dalam bahasa pemrograman lainnya. Pada contoh berikut, kita membuat sebuah kamus untuk merepresentasikan hubungan antara individu dan saldo mereka:

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

Mengembangkan dari contoh sebelumnya, mari tunjukkan contoh kode di mana saldo dari pengguna yang sama berubah:

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.

Sebelum melanjutkan dan menjelaskan bagaimana kamus diimplementasikan, penting untuk disebutkan bahwa begitu Anda membuat sebuah Felt252Dict<T>, di balik layar semua kunci memiliki nilai terkait mereka diinisialisasi sebagai nol. Ini berarti bahwa jika misalnya, Anda mencoba untuk mendapatkan saldo dari pengguna yang tidak ada, Anda akan mendapatkan nilai 0 daripada sebuah kesalahan atau nilai yang tidak terdefinisi. Ini juga berarti bahwa tidak ada cara untuk menghapus data dari sebuah kamus. Hal yang perlu diperhatikan ketika menggabungkan struktur ini ke dalam kode Anda.

Hingga saat ini, kita telah melihat semua fitur dasar dari Felt252Dict<T> dan bagaimana ia meniru perilaku yang sama seperti struktur data yang sesuai dalam bahasa pemrograman lainnya, yaitu, secara eksternal tentunya. Cairo pada intinya adalah bahasa pemrograman yang non-deterministik dan lengkap secara Turing, sangat berbeda dari bahasa lain yang populer saat ini, yang sebagai konsekuensinya berarti bahwa kamus diimplementasikan dengan cara yang sangat berbeda juga!

Pada bagian-bagian berikutnya, kami akan memberikan beberapa wawasan tentang mekanisme internal Felt252Dict<T> dan kompromi yang diambil untuk membuatnya berfungsi. Setelah itu, kita akan melihat bagaimana menggunakan kamus dengan struktur data lain serta menggunakan metode entry sebagai cara lain untuk berinteraksi dengan mereka.

Dasar dari Kamus

Salah satu batasan dari desain non-deterministik Cairo adalah sistem memorinya yang tidak dapat diubah, sehingga untuk mensimulasikan keberlangsungan, bahasa ini mengimplementasikan Felt252Dict<T> sebagai daftar entri. Setiap entri mewakili waktu ketika sebuah kamus diakses untuk tujuan membaca/memperbarui/menulis. Sebuah entri memiliki tiga bidang:

1. A key field that identifies the key for this key-value pair of the dictionary.
2. Bidang previous_value yang menunjukkan nilai sebelumnya yang dipegang oleh key.
3. Bidang new_value yang menunjukkan nilai baru yang dipegang oleh key.

Jika kita mencoba mengimplementasikan Felt252Dict<T> menggunakan struktur tingkat tinggi, kita akan mendefinisikannya secara internal sebagai Array<Entry<T>> di mana setiap Entry<T> memiliki informasi tentang pasangan kunci-nilai yang direpresentasikannya dan nilai-nilai sebelumnya dan baru yang dipegangnya. Definisi dari Entry<T> akan menjadi:

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:

• Sebuah get akan mendaftarkan sebuah entri di mana tidak ada perubahan dalam keadaan, dan nilai-nilai sebelumnya dan baru disimpan dengan nilai yang sama.
• Sebuah insert akan mendaftarkan sebuah Entry<T> baru dimana new_value akan menjadi elemen yang sedang dimasukkan, dan previous_value akan menjadi elemen terakhir yang dimasukkan sebelum ini. Jika ini adalah entri pertama untuk sebuah kunci tertentu, maka nilai sebelumnya akan menjadi nol.

Penggunaan daftar entri ini menunjukkan bahwa tidak ada penulisan ulang (rewriting), hanya penciptaan sel memori baru setiap kali ada interaksi dengan Felt252Dict<T>. Mari tunjukkan contohnya dengan menggunakan kamus balances dari bagian sebelumnya dan memasukkan pengguna 'Alex' dan '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');
}

Instruksi-instruksi ini kemudian akan menghasilkan daftar entri berikut:

Perhatikan bahwa karena 'Alex' dimasukkan dua kali, ia muncul dua kali dan nilai sebelumnya dan saat ini diatur dengan benar. Juga membaca dari 'Maria' mendaftarkan sebuah entri tanpa perubahan dari nilai sebelumnya ke nilai saat ini.

Pendekatan ini dalam mengimplementasikan Felt252Dict<T> berarti bahwa untuk setiap operasi baca/tulis, terjadi pemindaian pada seluruh daftar entri untuk mencari entri terakhir dengan kunci yang sama. Setelah entri ditemukan, nilai_baru-nya diekstrak dan digunakan pada entri baru yang akan ditambahkan sebagai nilai_sebelumnya. Hal ini berarti berinteraksi dengan Felt252Dict<T> memiliki kompleksitas waktu kasus terburuk O(n) di mana n adalah jumlah entri dalam daftar.

Jika Anda memikirkan alternatif cara untuk mengimplementasikan Felt252Dict<T>, mungkin Anda akan menemukannya, bahkan mungkin benar-benar menghilangkan kebutuhan akan bidang nilai_sebelumnya. Namun, karena Cairo bukanlah bahasa yang biasa, hal ini tidak akan berhasil. Salah satu tujuan dari Cairo adalah, dengan sistem bukti STARK, untuk menghasilkan bukti integritas komputasi. Ini berarti Anda perlu memverifikasi bahwa eksekusi program adalah benar dan berada dalam batasan-batasan Cairo. Salah satu pemeriksaan batasan tersebut terdiri dari "dictionary squashing" dan hal itu membutuhkan informasi tentang nilai sebelumnya dan nilai baru untuk setiap entri.

Merenggut Kamus

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.

Proses merenggut (squashing) dilakukan sebagai berikut: diberikan semua entri dengan kunci tertentu k, diambil dalam urutan yang sama seperti saat mereka dimasukkan, verifikasi bahwa nilai new_value entri ke-i sama dengan nilai previous_value entri ke-(i+1).

Sebagai contoh, diberikan daftar entri berikut:

Setelah proses merenggut (squashing), daftar entri akan berkurang menjadi:

Dalam kasus perubahan pada salah satu nilai dari tabel pertama, proses merenggut (squashing) akan gagal selama runtime.

Penghancuran Kamus

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

Hingga saat ini, kami telah memberikan gambaran menyeluruh tentang fungsionalitas Felt252Dict<T> serta bagaimana dan mengapa ia diimplementasikan dengan cara tertentu. Jika Anda belum memahami semuanya, jangan khawatir karena dalam bagian ini kami akan memberikan beberapa contoh lebih lanjut menggunakan kamus.

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

Metode entry disertakan sebagai bagian dari Felt252DictTrait<T> dengan tujuan untuk membuat entri baru berdasarkan suatu kunci tertentu. Setelah dipanggil, metode ini mengambil kepemilikan dari kamus dan mengembalikan entri untuk diperbarui. Tanda tangan metodenya adalah sebagai berikut:

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.

Langkah selanjutnya adalah memperbarui entri dengan nilai baru. Untuk ini, kita menggunakan metode finalize yang memasukkan entri dan mengembalikan kepemilikan dari kamus:

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.

Mari kita lihat contoh penggunaan entry dan finalize. Bayangkan kita ingin mengimplementasikan versi kita sendiri dari metode get dari sebuah kamus. Maka kita harus melakukan hal berikut:

1. Create the new entry to add using the entry method.
2. Masukkan kembali entri di mana nilai_baru sama dengan nilai_sebelumnya.
3. Kembalikan value tersebut.

Implementasi custom get kita akan terlihat seperti ini:

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.

Mengimplementasikan metode insert akan mengikuti alur kerja yang serupa, kecuali untuk memasukkan nilai baru saat proses finalisasi. Jika kita hendak mengimplementasikannya, akan terlihat seperti berikut:

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

Sebagai catatan penyelesaian, kedua metode ini diimplementasikan dengan cara yang mirip dengan bagaimana insert dan get diimplementasikan untuk Felt252Dict<T>. Kode ini menunjukkan contoh penggunaannya:

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.

Mari kita tunjukkan dengan contoh. Kita akan mencoba menyimpan sebuah Span<felt252> di dalam sebuah kamus. Untuk itu, kita akan menggunakan Nullable<T> dan Box<T>. Selain itu, kita menyimpan sebuah Span<T> dan bukan sebuah Array<T> karena yang terakhir tidak mengimplementasikan trait Copy<T> yang diperlukan untuk membaca dari sebuah kamus.

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

//...

Dalam potongan kode ini, yang pertama kita lakukan adalah membuat kamus baru d. Kita ingin kamus ini menampung Nullable<Span>. Setelah itu, kita membuat sebuah array dan mengisinya dengan nilai-nilai.

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.

Setelah elemen berada di dalam kamus, dan kita ingin mengambilnya, kita mengikuti langkah yang sama namun dalam urutan terbalik. Berikut adalah contoh kode untuk mencapainya:

//...

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

Here we:

1. Baca nilai menggunakan get.
2. Verifikasi bahwa nilai tersebut tidak null menggunakan fungsi match_nullable.
3. Membuka nilai wrapped di dalam kotak dan memastikan bahwa itu benar.

Skrip lengkap akan terlihat seperti ini:

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