Chapter sebelumnya menempatkan Box sebagai alat optimasi: data besar dipindahkan ke heap agar perpindahan kepemilikan menjadi murah. Kini kita berhadapan dengan kasus di mana Box bukan pilihan, melainkan kebutuhan mutlak: tipe data yang berisi dirinya sendiri. Struktur seperti linked list dan tree memang rekursif secara alami — sebuah simpul berisi nilai plus “sisa daftar” yang bentuknya identik dengan simpul itu sendiri. Rust wajib mengetahui ukuran setiap tipe saat kompilasi, dan rekursi tanpa batas seperti itu membuat perhitungan ukuran meledak menjadi tak hingga. Kompilator menolaknya dengan error E0072, lalu menyarankan satu obat yang tepat: sisipkan indirection berupa Box untuk memutus rantai ukuran tersebut.

Struktur Data yang Berisi Dirinya Sendiri #

Kita mulai dari masalah nyatanya. Bayangkan struk belanja yang disimpan sebagai linked list: setiap elemen memuat satu harga dan penunjuk ke elemen berikutnya, dan elemen terakhir menandai akhir daftar. Bentuk paling natural untuk memodelkannya di Rust adalah enum dengan dua variant — satu variant untuk “ada elemen”, satu variant untuk “daftar habis”:

rust 
use List::{Cons, Nil};

enum List {
    Cons(i32, List),
    Nil,
}

fn main() {
    let list = Cons(1, Cons(2, Cons(3, Nil)));
    println!("ukuran tipe List: {}", std::mem::size_of::<List>());
}

Kode di atas memang gagal dikompilasi, dan kegagalannya justru bahan belajar utama kita. Pesan error kompilator:

text 
error[E0072]: recursive type `List` has infinite size
 --> main.rs:3:1
  |
3 | enum List {
  | ^^^^^^^^^
4 |     Cons(i32, List),
  |               ---- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
4 |     Cons(i32, Box<List>),
  |               ++++    +

error: aborting due to 1 previous error

For more information about this error, try `rustc --explain E0072`.

Mari kita bedah kode dan pesannya:

  1. Baris 3 (enum List {): kompilator menandai definisi tipe ini sebagai sumber masalah — lokasi yang dilaporkan adalah kepala definisi, bukan baris pemakaianya.
  2. Baris 4 (Cons(i32, List)): akar masalah sesungguhnya. Variant Cons memuat i32 dan satu nilai List utuh lagi — bukan pointer, melainkan nilai lengkap yang ukurannya harus dihitung.
  3. Baris 9 (let list = Cons(1, Cons(2, Cons(3, Nil)));): pemakaian bersarang ini memperlihatkan ekspansi yang menakutkan: List berisi List yang berisi List lagi, tanpa titik henti yang bisa diukur.
  4. Baris 4 pada pesan error (recursive without indirection): kompilator menjelaskan bahwa List memuat dirinya sendiri “tanpa indirection” — tanpa perantara seperti pointer yang ukurannya tetap.

Perhitungannya sederhana namun fatal: ukuran List = ukuran Cons = ukuran i32 + ukuran List = … dan rantai ini tidak pernah berakhir. Setiap langkah perhitungan menambah List baru yang harus diukur lagi. Kompilator tidak bisa memesan memori untuk nilai yang ukurannya tak hingga, sehingga kompilasi dihentikan total.

Box Memutus Rantai Ukuran #

Mekanisme penyembuhnya bekerja lewat satu fakta yang sudah kita ukur di Chapter sebelumnya: Box<T> selalu berukuran 8 byte — satu pointer — terlepas dari seberapa rumit T-nya. Ketika variant Cons menyimpan Box<List> alih-alih List, perhitungan ukuran berubah total: ukuran Cons = ukuran i32 + ukuran pointer 8 byte. Tidak ada lagi List yang harus diukur di dalam Cons; yang ada hanyalah alamat menuju List berikutnya di heap. Rantai ukuran putus di pointer, dan List kini memiliki ukuran pasti.

Struktur hasil perbaikan dapat digambarkan sebagai berikut:

Diagram di atas memperlihatkan pembagian kerja kedua wilayah memori: variabel receipt berdiri di stack sebagai pemilik, sementara setiap elemen daftar dialokasikan terpisah di heap. Panah antar elemen adalah Box — pointer yang memutus perhitungan ukuran sekaligus menghubungkan elemen ke elemen berikutnya. Elemen terakhir menunjuk Nil, variant tanpa data yang menjadi titik pemberhentian.

Daftar Belanja dengan Box #

Mari kita tulis versi lengkap yang sehat dan bisa berjalan, dengan harga dalam rupiah sebagai isi datanya:

rust 
use std::mem::size_of;

use List::{Cons, Nil};

enum List {
    Cons(u32, Box<List>),
    Nil,
}

fn total_price(list: &List) -> u32 {
    match list {
        Cons(price, next) => *price + total_price(next),
        Nil => 0,
    }
}

fn main() {
    let receipt = Cons(15000, Box::new(Cons(8000, Box::new(Cons(22000, Box::new(Nil))))));

    println!("ukuran tipe List: {} byte", size_of::<List>());
    println!("total belanja: Rp{}", total_price(&receipt));
}

Output yang Dihasilkan:

text 
ukuran tipe List: 16 byte
total belanja: Rp45000

Mari kita bedah kode di atas:

  1. Baris 6 (Cons(u32, Box<List>)): satu-satunya perubahan struktural dibanding versi yang ditolak E0072 — field kedua kini bertipe Box<List>. Ukuran variant menjadi u32 4 byte plus pointer 8 byte.
  2. Baris 10 (fn total_price(list: &List) -> u32): fungsi penjumlah harga menerima pinjaman &List, bukan kepemilikan, sehingga receipt tetap hidup di main selama perhitungan berlangsung.
  3. Baris 12 (Cons(price, next) => *price + total_price(next)): pattern Cons(price, next) mengikat harga elemen saat ini dan Box menuju elemen berikutnya. Ekspresi total_price(next) mengirim &Box<List> ke parameter bertipe &List — deref coercion mengubah pointer box menjadi reference biasa secara otomatis. Rekursi berhenti alami saat pola bertemu Nil.
  4. Baris 13 (Nil => 0,): kasus dasar rekursi — daftar kosong menyumbang nol rupiah.
  5. Baris 18 (let receipt = Cons(15000, Box::new(...))): pembangunan daftar dari dalam ke luar: Nil dibungkus lebih dulu, lalu setiap Box::new memesan satu elemen baru di heap yang menunjuk ke elemen sebelumnya.
  6. Baris 20 (size_of::<List>()): hasil 16 byte membuktikan rantai ukuran benar-benar putus — 8 byte untuk Box, 4 byte untuk u32, dan 4 byte selebihnya menampung penanda variant beserta padding perataan memori. Bandingkan dengan versi E0072 yang bahkan tidak bisa menghasilkan angka.

Ringkasan #

Tipe rekursif tanpa indirection membuat perhitungan ukuran berputar tanpa henti, dan kompilator menghentikannya lewat error E0072 lengkap dengan resep perbaikan Box<List>. Menyisipkan Box pada field rekursif membatasi ukuran setiap elemen menjadi tetap — 16 byte untuk daftar belanja kita — karena yang tersimpan hanyalah pointer 8 byte menuju elemen berikutnya di heap. Pemrosesan daftar berjalan alami lewat match dan rekursi, dengan deref coercion menjembatani &Box<List> menuju &List. Keberhasilan Box dalam urusan kepemilikan tunggal ini justru membuka pertanyaan berikutnya: bagaimana caranya Box bisa dipakai begitu mulus — field dan method diakses tanpa perintah deref yang bertele-tele? Jawabannya ada pada trait Deref, yang kita bedah pada Chapter selanjutnya.