Back

Rust Notes

2021-02-16

Table of Contents
  1. Strings and &str
  2. Ownership and Borrowing
  3. Borrowing and Function Mutation
  4. Structs and Traits
  5. Generics
  6. Lifetimes
  7. Mutation inside Matching
  8. Rust Channels

Strings and &str

&str can be stack allocated or heap allocated as it is ultimately just a pointer to a string and the length of that string. This is why converting a string to a str is easy as the String has enough information to do the convertion.

A &str is similar to a &[char] whereas a String is analogous to a Vec. Both can be on the heap but only the &str can be on the stack.

Strings however are heap allocated only and so for a &str to be converted to a string is much more involved. The slice of characters needs to be copied into the heap and then a reference created for it. This is much more expensive.

Ownership and Borrowing

What makes rust rust is how rust uses and manages memory. There are 2 key things to know about when talking about ownership and borrowing rust. We have the stack which is the ideal place for our variables, the stack is quick access because everything is packed together tightly and we can do math to get memory addresses. The second thing to know is that we have the heap which is much slower but also allows our variables to be flexible.

Primitives like i32, and i8 have a fixed size and cannot grow. This means we can use the stack to hold these variables. Primitives like vectors and string can grow and change in size, this means at compile time we do not know the size and cannot use the stack for them.

Now we know our variables can go to 2 different places in memory. Let's take a look at stack based variables first. Stack based variables are owned by their declaration and ownership doesn't move. The reason for this is that stack variables are so cheap to copy that everytime we use a stack variable and need to do something with it, rust simply copys the variable and creates a new version.

Variables are released in memory when they go out of scope so for stack variables this is very simple. If a variable is declared in main, it will go out of scope on the closing brace.

rust
fn print<T>(x: T) where T: std::fmt::Debug {
    println!("{:?}", x);
}

fn main() {
    let x: i32 = 24;
    let mut y = x;

    y += 1;

    print(y);
    print(x);
    print(x);
}

Here we declare variable x to be of type i32 and set the value to 24. i32 has a fixed size of 32 bits and so the stack now knows 32 bits belong to the variable x. Next we assign y the value of x. This creates a new variable, y doesn't point to x. We can see this where we add 1 to y and print everything out.

Here we see y get printed out with the new value. We then print out x and we print out x one more to show that even functions don't move stack variables.

Stack variables passed into functions are copied, so stack variables are always owned by wherever they are declared!

This is in contrast to heap variables like strings and vectors.

rust
fn print<T>(x: T) where T: std::fmt::Debug {
    println!("{:?}", x);
}

fn main() {
    let x: Vec<i32> = vec![1,2,3];

    print(x);
    print(x);
}

Here we declare x to be a vector of i32s and so because we don't know what the size of the array will be, variable x is declared on the heap. Now the ownership of variables can change. For heap variables ownership is based on who is using the variable. Heap variables are expensive to copy so anything no the heap is shared between all variables that want access to it.

As soon as a new variable wants to use the heap variable, it will become owned by it. This is what rust calls move. When the owner goes out of scope, the heap variable will be released.

This means when a heap variable is passed into our print function above, ownership transfers to the x parameter in print. The x parameter in print goes out of scope at the end of the function's closing brace.

When we do another print function call on x, we will get an error saying "value used here after move". This means that our variable x lost ownership already and so we can't use it anymore.

These are the ownership rules!

Borrowing then falls out of the idea of ownership. To get our above code to run, we need to use borrowing.

rust
fn print<T>(x: &T) where T: std::fmt::Debug {
    println!("{:?}", x);
}

fn main() {
    let x: Vec<i32> = vec![1,2,3];

    print(&x);
    print(&x);
}

Now we use the & to mean that we want to pass our variable but we don't want to lose ownership. This way our function can use x but x won't go out of scope.

Borrowing has some restrictions on it, while in the midst of a borrow, we cannot mutate the borrowed value. We can also have any number of borrows at the same time.

Stack variables can also be borrowed but there is no real gain for it as stack copying is cheap. We can also declare stack variables on the heap by using rust's Box struct.

rust
    let x = Box::<i32>::new(5);

This has declared a new variable if type i32 but instead of on the stack, it is on the heap. This means that function calls will no longer copy x but will move ownership of it. We will need to use borrows if we want to keep ownership of x.

Voila! That is ownership and borrowing in a nutshell. Now let's take a look at mutating variables and passing them around. Mutation then follows from rust's borrowing rules.

Borrowing and Function Mutation

The goal of this snippet is to see how to mutate a parameter in place.

Below I will write the code I want to write and then go about correcting it and figuring out why the correct version works the way it does.

rust
fn add(mut x: i32, y: i32) {
    x = x + y;
}

fn main() {
    let x = 1;
    let y = 2;

    add(x,y);

    println!("{}", x);
}

So here we want to update x directly. Ultimately we want to get a print out of 3, however this won't work. x and y both get declared on the stack and even thought we made x the parameter mutable, we are still creating new copies of both x and y and operating on them. What we really want to do is not create new copies, but borrow the x value in the function.

rust
fn add(x: &mut i32, y: i32) {
    *x = *x + y;
}

fn main() {
    let mut x = 1;
    let y = 2;

    add(&mut x,y);

    println!("{}", x);
}

Now our x parameter in our function is a mutable borrow, this means that the function isn't make a copy of x but simply borrowing it. The mut means that we can change x. In our function we update x and because we are in a borrow we use the * to dereference it to get the value.

rust
fn add(x: &mut i32, mut y: i32) {
    y = y + 1;
    *x = *x + y;
}

fn main() {
    let mut x = 1;
    let y = 2;

    add(&mut x,y);

    println!("{}", x);
    println!("{}", y);
}

In this version, we want to increase y but only in the function. This is why we have the mut in front of y. The mut in front of y means make this value mutable. So we pass in y into the add function and it will get a copy made. This is a different y to the one we have in our main function. This is a different y is then marked as mutable. This would be analogous to the below.

rust
fn add(x: &mut i32, y: i32) {
    let mut z = y;
    z = z + 1;
    *x = *x + z;
}

The mut in front of parameters is just so we can have mutable parameters. Mutable borrows however are required if we want to have effects outside of our function.

Structs and Traits

Structs are just bags of data. Impl lets you define functions on that struct. The impl option lets you add methods to structs anywhere which is actually really cool and I never noticed that before. You can have some data type defined in a library and then implement a method on that easily by just doing impl.

Traits also see like a really simple idea now that I know what it is. It lets you define some rules and when you give a struct that trait then you can use that struct in whatever function requires a set of traits.

For examle the debug trait probably just needs you to write some string version of itself. Then once you write the debug trait, the :? option can handle it by calling the debug trait.

This way you can have different structs being passed into the same function because you can specify the type as a trait instead. Very cool idea. What happens whne you try to use something defined in the struct but outside the trait? I'm guessing rust would block that.

rust
struct Bag {
    num: i32
}

trait Double {
    fn double(&self) -> i32;
}

impl Double for Bag {
    fn double(&self) -> i32 {
        self.num * 2
    }
}

fn test(b: &dyn Double) {
    println!("{}", b.double());
}

fn main() {
    let bag = Bag {
        num: 7,
    };

    test(&bag);
}

Here we have a struct called Bag with just a number and we have a trait called double that we've defined to return something of type i32.

Next we implmenet that trait for Bag so that bag has the trait Double.

Next we have a function that anything with the trait Double.

Voila! We can now write a variety of structs but handle them through the same function via traits.

We will only have whatever is exposed via the trait so inside out function that takes only structs with the Double, we don't have access to the num field of the struct bag. We only have access to the function double().

It also makes sense why we can't pass bag directly but must pass a reference. The function doesn't know how big the struct really is and so it can't be on the stack. This means that it must be in the heap so we use the dyn keyword and then we pass by reference.

The reason for dyn is that we don't know which struct will need to go on the stack when the function gets run so it needs to be available via a pointer.

When a function is called, the arguments go onto a stack if we know the size of the arguments, otherwise we need to pass references to the data on the heap.

Generics

Now let's take a look at generics. Generics fall into place when you think about running functions against multiple types. For instance if we have one function that we want to use for both i32 and f64 we would have write 2 functions or 2 structs to handle them. With generics we can use the generic type T and rust will behind the scenes generate everything we need.

rust
#[derive(Debug)]
struct Point<T> {
    x: T,
    y: T,
}

fn main() {
    let p = Point { x: 1, y: 2 };
    println!("{:?}", p);

    let p = Point { x: 1.0, y: 2.0 };
    println!("{:?}", p);
}

Here we have a struct that takes some type T and creates a point. The type T is on both x and y so both of them need to match.

Now we have single defination for both i32 and f64.

rust
fn add<T, U>(a: T, b:T) -> U 
where T: std::ops::Add<Output = U> 
    + std::fmt::Display,
    U: std::fmt::Display
{
    let x = a + b;
    println!("{}", x);
    x
}

fn main() {
    add(1,3);
    add(1.0,3.4);
}

Now here we have an add function that will add 2 numbers as well as print them. We set the type of the function to some type T and a and b both are also that type. We also will allow the output to be any type. That way we return whatever we want.

The first thing to note here is that we added a where close. The where close is the constraints on the function. These are the traits we require on the type T. So for anything with type T, we require it to have an add function implemented, and for both T and U we require it to have the display trait implemented.

Now let's look at making out point struct work with out generic add function.

rust 
struct Point<T> {
    x: T,
    y: T,
}

fn add<T, U>(a: T, b:T) -> U 
where T: std::ops::Add<Output = U> 
{
    let x = a + b;
    x
}

impl<T> std::ops::Add for Point<T> where T: std::ops::Add<Output = T>{
    type Output = Self;

    fn add(self, other: Self) -> Self {
        Self { 
            x: self.x + other.x,
            y: self.y + other.y,
        }
    }
}

impl<T> std::fmt::Display for Point<T> where T: std::fmt::Display {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "({}, {})", self.x, self.y)
    }
}

fn main() {
    let t1 = add(1,3);
    let t2 = add(1.0,3.4);
    println!("t1: {}", t1);
    println!("t2: {}", t2);

    let p1 = Point { x: 1.0, y: 2.0 };
    let p2 = Point { x: 4.0, y: 3.2 };
    let p3 = add(p1,p2);

    println!("p3: {}", p3);
}

So we start off with our generic struct called point. We then wrote a function called add that is generic in general.

In our main function we can use add with our i32s and our f32s without issue as those primitive types already implement the Add trait and the Display trait. Now we want to do the same bit of code to add 2 of our generic points!

We need to implement the Add trait for out point so that we can satisfy our Add constaint on our function and we also need to implement the Display trait so that we can print our Points.

The first thing we do when we implement our trait is to annotate our impl to use T, we want to let the implementation know that we are going to be doing this generically. Next we specify what trait we are implementing and what type this is for.

We then add a constaint to our implementation. We require the type T itself to have the ability to Add. This means that when we create a Point of some type, that we want that type to have the Add trait already. We then specify our output type and we then write our add function.

Once we do this we have a fully functional trait. If we didn't use the + we could have skipped our constaint and did something else. For instance we could have done substraction but then we'd need to add the subtraction constaint to our implmenation. Even though it's in the add. We can do anything inside!

Now the next trait we need to implement is our Display trait, here we follow the same rules as before. We set the implmentation type to T and we constrain our generic type T so that whatever type we use already has the Display trait.

Voila! We now have generics, traits and constraints all working together to give us some very strange looking code! What I would use this for? No idea for now.

Lifetimes

Lifetimes really clicked after watching this video.

https://www.youtube.com/watch?v=rAl-9HwD858

It is a bit long but well worth watching but I'll go over the essence here. We can design and write a string split struct where the struct keeps track of the string and it keeps track of the delimiter. We can write a function on the string split struct that will return the next piece that we are splitting on.

We would write this struct to use references instead of full copies and so we would need to specify the lifetimes of the remainder and the delimiter. We can default this to just 'a for both and now we have our problem.

We can now use this struct to create a new function where we can pass in a delimiter and a string and we would expect to get the next element. The problem is that this function we wrote could take the delimiter as a character. Now inside our function we need to change this character into a string reference. Once we do that we have run into a lifetime issue.

The lifetime of that character that has been converted to a string is tied to the function it is. Whereas the lifetime of the haystack we are passing in is actually much longer. It will return back to the location it came from.

Our struct assumed that our remainder lifetime and our delimiter lifetime were the same. So when it received 2 different lifetimes it would then use the lesser lifetime as the lifetime of the object. In our function if we attempted to return the string split struct it would throw an error saying that the reference does nto live long enough. This is indeed true because the lifetime of our struct references is tied to the character we transformed into a string!

A very cool little lesson in how there can be 2 diferent lifetimes inside one struct and so obvious now that I watched that video.

Mutation inside Matching

To mutate a variable inside a match statement we need to use ref mut.

rust
fn main() {
    let mut x: Option<&str> = Some("Hello");

    match x {
        Some(ref mut x) => {
            *x = "Hi";
        },
        _ => {}
    }

    println!("{:?}", x);
}

Above we first create an Option and then we want to update this option with a new value but we want to do this inside our match. To do this we need to get the reference to our value. The normal match statement would unpack the variable and give us the value.

From what I understand, this is a copy and not the actual variable. So if we updated x without the ref mut, we would have been worknig on a version x local to the match statement. However with ref mut, we retrieving the reference instead of the value and so we can then dereference and mutate our variable.

Rust Channels

https://www.youtube.com/watch?v=b4mS5UPHh20

In this video Jon goes into implementing channels in rust and it is a pretty mindblowing concept. I decided to follow along in this video and found it to be really helpful. I'm about 40 minutes in and the idea of channels is pretty cool. But I think treating it like a channel and then saying things like sender and receiver is really hiding the core concept.

The core idea of a channel is to have some shared state between threads. If we have 2 threads that can handle some type T, we need to be able to get things from the main thread into the children thread. How do we do that. We do that by having some shared variable between all 3 threads. The children thread should only pick things up and the main thread should only send things.

Now we can use a queue in the global scope for this purpose. The children will lock the queue and pop it. While locked nothing can add to it or take from it. The parent thread can lock the thread to add things.

This locking system and using a queue is the core concept of a channel. Now to make sure our rules are strict, we can wrap this queue into a struct and then return 2 different structs that both refer to this single queue. We can have on struct that only does pushes onto the queue and we can have another object that only does pops. This way the threads can't misuse the queue.

This idea of misuse is why we have Sender and Receiver. Inside of which contains a shared reference to a mutable queue.

Voila! That is the core concept of channels in rust and likely this is useful anywhere we want to share data across threads.

Channels are an abstraction over global variables!

rust
// Concurrency primitives - Condvar, Mutex and ARC
// Condvar lets you wake up the other side of the channel

use std::sync::{Arc, Condvar, Mutex};
use std::collections::VecDeque;

// Flavors of channels
// - Synchronous channels - Send blocks, limited capcity
//  - mutx+condvar: VecDeque
//  - atomic vecdeque, don't need a mutex + thread::park + thread::notify
// - Async channels - send cannot block, unbounded, ours
//  - mutx+condvar: Linked List
//  - atomic linked list
// - Rendevous channels - sync channel with capacity equals 0, we are synchronizing things
// - One shot channels - any capcity but we send only once, something like kill all threads


// async/await

pub struct Sender<T> {
    inner: Arc<Inner<T>>
}

// We need the custom clone impl so we can count the senders
impl<T> Clone for Sender<T> {
    fn clone(&self) -> Self {
        let mut locked_state = self.inner.locked_state.lock().unwrap();
        locked_state.senders += 1;
        // this drops the lock
        drop(locked_state);
        Sender {
            inner: Arc::clone(&self.inner),
        }
    }
}

impl <T> Sender<T> {
    pub fn send(&mut self, t: T) {
        //lock could be poisned thats why we unwrap
        //lock should be blocking
        let mut locked_state  = self.inner.locked_state.lock().unwrap();
        locked_state.queue.push_back(t);
        // this drops the lock
        drop(locked_state);
        // Notify one of the receivers using this specific condvar
        self.inner.available.notify_one();
    }
}

// We need to decrement the senders on drop
impl<T> Drop for Sender<T> {
    fn drop(&mut self) {
        let mut locked_state = self.inner.locked_state.lock().unwrap();
        if locked_state.senders > 1 {
            locked_state.senders -= 1;
        } else {
            self.inner.available.notify_one();
        }
        drop(locked_state);
    }
}

//Receiver needs a mutex to protect from the sender and receiver triggering together
// The arc is needed so that the 2 sides can share the data instead of having their own clones
pub struct Receiver<T> {
    inner: Arc<Inner<T>>,
    buffer: VecDeque<T>
}

impl<T> Receiver<T> {
    pub fn recv(&mut self) -> Option<T> {
        // we check the cache for things to handle
        // if there is stuff, then we can skip the lock.
        // this only works if there is one receiver
        // Very cool optimization
        if let Some(t) = self.buffer.pop_front() {
            return Some(t)
        }
        // we take the lock if there is nothing in our local cache
        let mut locked_state = self.inner.locked_state.lock().unwrap();
        // This isn't a spin loop
        loop {
            match locked_state.queue.pop_front() {
                Some(t) => {
                    // We don't need this if as it will always be empty if we made it here.
                    if !locked_state.queue.is_empty() {
                        // once we have a lock, we will take everything all at once from the 
                        // queue and add it to our local cache
                        // We want to use swap to be efficient
                        std::mem::swap(&mut self.buffer, &mut locked_state.queue);
                    }
                    return Some(t)
                },
                // You can use Arc::strong_count(&self.inner) to do the count of senders
                None if locked_state.senders == 0 => return None,
                None => {
                    // wait will get the mutex when it get's woken up
                    locked_state = self.inner.available.wait(locked_state).unwrap();
                }
            }
        }
    }
}

pub struct locked_state<T> {
    queue: VecDeque<T>,
    senders: usize,
}

// This is the shared global locked_state object
// condvar + mutex is used to do channel in general
// we can have capped channels where they have max queue size where senders beome blocking
pub struct Inner<T> {
    locked_state: Mutex<locked_state<T>>,
    // This is what does the notification into the 2 parts
    available: Condvar,
}

pub fn channel<T>() -> (Sender<T>, Receiver<T>) {
    let locked_state = locked_state { queue: VecDeque::default(), senders: 0 };
    let inner = Inner { locked_state: Mutex::new(locked_state), available: Condvar::new() };
    let inner = Arc::new(inner);
    // These clones aren't new instances but actually referencing the same inner
    (Sender { inner: inner.clone() }, Receiver { inner: inner.clone() })
}

#[cfg(test)]
mod tests {

    use super::*;

    #[test]
    fn ping_pong() {
        let (mut tx, mut rx) = channel();
        tx.send(42);
        assert_eq!(rx.recv(), Some(42));
    }

    // Receiver can't tell there will never be senders so it must hang
    // If we know the count of senders is 0 then we can drop the receivers
    // We need to keep track of the senders and put this number behind the mutex gaurd
    #[test]
    fn closed_tx() {
        let (tx, mut rx) = channel::<()>();
        let _ = tx;
        assert_eq!(rx.recv(), None);
    }

    #[test]
    fn closed_rx() {
        let (mut tx, rx) = channel();
        drop(rx);
        // On fail we should send the value back to the user.
        // This is fine as is though.
        // On the receiver getting dropped, we set a flag on the locked_state struct
        // We need to add this flag
        tx.send(42);
    }
}