Box Pointers in Rust make recursive types possible

Overview

Rust Programming Language

A pointer is a general programming concept for a variable that contains an address in memory. In Rust, we have smart pointers in addition to normal pointers. Smart pointers are data structures that not only act as a pointer but also have additional metadata and capabilities. Box pointers are one of the smart pointers in Rust.

Box Pointers

Boxes allow you to store data on the heap instead of the stack. What remains on the stack is the pointer to the heap data. A box can be defined in Rust as -

let ptr = Box::new(25);

A box does not have any capabilities other than storing the data on a heap other than the stack. We use Box in the following cases -

• When you have a type whose size can’t be known at compile time and you want to use a value of that type in a context that requires an exact size
• If you have a large amount of data and you want to transfer ownership but ensure the data won’t be copied when you do so
• When you want to own a value and you care only that it’s a type that implements a particular trait rather than being of a specific type

Using Box Type to store data

As we discussed above that the box type is used to store data on a heap rather than the stack. The pointer to the data on the heap is indeed stored on the stack. Here is an example to explain it better.

fn main() {
    let ptr = Box::new("hello"); 
    println!("The pointer points to data : {}", ptr); 
} 

In the example above, there is a variable ptr that stores a Box pointer that points to a string “hello”. The string hello is on the heap and the box pointer ptr is on the stack. The program will print the following -

The pointer points to data : hello

The ptr variable owns the box pointer and thus the rules of ownership apply to it as well. As the main method ends, the memory pointed by the ptr box pointer will be freed and the box pointer on the stack will also be freed.

Recursive types using box pointer

In any programming language, the compiler needs to know the space any data type takes up. This is the same for Rust Compiler, but in the case of recursive type, it is quite difficult. A recursive type is a type in which value can have as part of itself another value of the same type. So compiler does not know how much memory to allocate at compile time for this data type. Here is an example to explain it better.

enum RecType {
    Cons(i32, Rectype), 
    Nil, 
}

Here, RecType is a recursive enum that has a variant that is associated with a tuple (i32, RecType). This tuple contains an i32 value and a value of the same type, i.e., RecType. So, in this case, it becomes difficult for the compiler to allocate the space for RecType at compile time.

To overcome this problem, we can use Box pointers. Since we can know the space that a Box pointer takes at compile-time, we can use a Box pointer inside the tuple that would point to a value of type RecType. Here is an example to show you better.

enum RecType { 
    Cons(i32, Box<RecType>), 
    Nil, 
}

Now, this would compile without any problem. This Recursive type can be understood by the following diagram.

Now the compiler knows how much space to allocate for RecType since we know the size of each variant in the RecType enum. Here is how we can use this RecType to store data recursively.

use crate::RecType::{Cons, Nil}; 
fn main() { 
    let data = 
       Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil)))))); 
}

So this was all about Box Pointers in Rust. Stay tuned for more such blogs.

Originally published at https://blog.knoldus.com on November 15, 2021.