Counting Fruit in Rust

Last time, I mentioned that I was starting up Rust again, and mentioned some helpful videos and thoughts that will help me as I take another swing at learning this language. The complete source for the examples I’ll use today is on GitHub, and you should be able to download it and cargo run without much trouble. If you don’t have Rust and Cargo, you want to install rustup first.

Today, we’re going to generate a random tree, then we’re going to walk the tree recursively and count which nodes have a flag set. Here’s the code for representing the nodes and generating the tree:

The first thing to talk about is the struct declared on line 5. This struct has three fields. One is a simple bool, has_fruit, which I added just so we would have something to look at when we interact with the tree – we’ll count fruit. The other two are of type Option<Box<Node>>. This type signature looks a little different than we’d see in C# or Ruby. In either of those languages, we’d just see public Node LeftChild { get; set; } or just attr_accessor :left_child. What’s with Option<> and Box<>?

Option is there because Rust doesn’t have null pointers. I need to be able to have leaves on this tree, so I need nodes that don’t have children, so I need to make nodes where left child and right child are missing. Option<T> is an enum in Rust. It’s either Some(T) or None. So I have to tell the compiler ahead of time, “Hey, this field might not have anything.” And then if I want to get at the value, I have to explicitly tell the compiler that I’m checking for the contents of Some(T), or at least tell the compiler that it’s ok to throw if nothing is there. No more NullReferenceExceptions!

Box was a little harder for me to understand. I found an awesome StackOverflow answer that helped me understand that a Box is an owning pointer. The box is the only way to get the contents in the box. This lets you pass the box around freely without violating Rust’s memory safety. Rust knows that the contents of the box are needed as long as the box is in scope. If control has exited the scope where the box is accessible, Rust knows that it’s safe to free the contents. This measure protects us both from use after free bugs and double-free errors.

Eric Lippert, my favorite programming blogger, likes to translate programs into polite requests to the runtime. Here’s my attempt to do this with the Node struct above:

I would like there to be a structure called a node. A node may have a fruit or not, and also a node has a left and a right child. Each child may either be None, or may be the only reference to another Node.

I’m pretty happy with that definition and, thankfully, the Rust compiler is also happy with that definition. I’m excited too that the compiler will force me to check for None properly, so I won’t accidentally dereference a null pointer when I start walking the tree.

Now we’ll just talk through the rest of the file. At the top are two use statements. use std::fmt; gives the code access to the formatting module in the standard library. helpers is a module that I wrote to store miscellaneous helpers in. In this project, helpers just contains coin_flip(), which wraps the standard libraries random number generator.

The line #[derive(Debug)] tells the compiler to emit code that lets this struct be debug printed. That means I can write println!("{:?}", node); and it will work. The :? is a format string that tells rust to debug print whatever value is interpolated there.

The rest of the file is the implementation of random_tree(), which recursively builds up a random tree by calling coin_flip() to decide whether each node will have a left child, a right child, and a fruit, and then returning the root node of the tree. The root node has boxes, which I think of as owning pointers, that point to the left and right sub-trees.

1 thought on “Counting Fruit in Rust”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s