00.1 - Deep dive in Rust

Resources

1. The Rust Programming Language, Chapter 4
2. Tour of Rust step by step tutorial
3. Let's Get Rusty - The Rust Lang Book
   • Understanding Ownership in Rust

Ownership

Ownership is a set of rules that govern how a Rust program manages memory. All programs must manage the way they use the memory of a computer while running.

Some languages have garbage collection that regularly searches for unused memory during program execution, in other languages, the programmer must explicitly allocate and release memory.

Rust uses a third approach: the memory is managed via a property system with a set of rules that the compiler verifies. If one of the rules is violated, the program will not compile. None of the property characteristics will slow down your program during its execution.

Ownership rules

1. Each value in Rust has an owner
2. A value cannot have more than one owner at a time
3. When the values are out of scope, they are dropped

Scope

A scope is the code area of a program in which an element is valid.

Here's an example to understand the concept:

{
    // Here s is invalid
    let s = "hello";   // s is valid past this point
} // after this the value s will be dropped

Ownership in functions

The mechanisms for transmitting a value to a function are similar to those of assigning a value to a variable. Parsing a variable to a function will move or copy, just as the assignment does.

Example (read the comments):

fn main() {
    let s = String::from("hello");  // s comes into scope
 
    takes_ownership(s);             // s's value moves into the function...
                                    // ... and so is no longer valid here
 
    let x = 5;                      // x comes into scope
 
    makes_copy(x);                  // a copy of x is passed to the function,
                                    // but i32 is Copy, so it's okay to still
                                    // use x afterward
 
} // Here, x goes out of scope, then s. But because s's value was moved, nothing
  // special happens.
 
fn takes_ownership(some_string: String) { // some_string comes into scope
    println!("{}", some_string);
} // Here, some_string goes out of scope and `drop` is called. The backing
  // memory is freed.
 
fn makes_copy(some_integer: i32) { // some_integer comes into scope
    println!("{}", some_integer);
} // Here, some_integer goes out of scope. Nothing special happens.

If we were trying to use s after the call to take_ownership, Rust would return a compilation error. These static checks protect us from errors.

Return values and scope

The return values can also transfer the ownership.

The ownership of a variable follows the same pattern each time: the assignment of one value to another variable moves it. When a variable that includes data on the heap comes out of the scope, the value will be cleaned by drop unless the data ownership has been moved to another variable.

Example (read the comments):

fn main() {
    let s1 = gives_ownership();         // gives_ownership moves its return
                                        // value into s1
 
    let s2 = String::from("hello");     // s2 comes into scope
 
    let s3 = takes_and_gives_back(s2);  // s2 is moved into
                                        // takes_and_gives_back, which also
                                        // moves its return value into s3
} // Here, s3 goes out of scope and is dropped. s2 was moved, so nothing
  // happens. s1 goes out of scope and is dropped.
 
fn gives_ownership() -> String {             // gives_ownership will move its
                                             // return value into the function
                                             // that calls it
 
    let some_string = String::from("yours"); // some_string comes into scope
 
    some_string                              // some_string is returned and
                                             // moves out to the calling
                                             // function
}
 
// This function takes a String and returns one
fn takes_and_gives_back(a_string: String) -> String { // a_string comes into
                                                      // scope
 
    a_string  // a_string is returned and moves out to the calling function
}

References and borrowing

A reference is like a pointer in the sense that it is an address that we can track to access the data stored at that address; these data belong to another variable. Unlike a pointer, a reference is guaranteed to point to a valid value of a particular type for the lifetime of this reference.

The symbol & is used to mark a reference, either before the name of a variable, or, for the case of a parameter of a function, before the type of the parameter. These ampersands represent references and allow you to refer to a value without your own ownership.

let x: u16 = 10;
let y = &x;

Example of a function which takes a reference to an object as a parameter instead of taking possession of this value:

fn main() {
    let s1 = String::from("hello");
    let len = calculate_length(&s1);
    println!("The length of '{}' is {}.", s1, len);
}
 
fn calculate_length(s: &String) -> usize { // s is a reference to a String
    s.len()
} // Here, s goes out of scope. But because it does not have ownership of what
  // it refers to, it is not dropped.

The syntax &s1 allows us to create a reference that refers to the value of s1 but does not. Since the reference does not have the value to which it points, the value of s1 will not be deleted when the reference ceases to be used.

Similarly, the signature of the function uses & to indicate that the type of parameter s is a reference.

We call borrowing the action of creating a reference. As in real life, you can borrow something from someone. When you don't need the borrowed thing anymore, you have to return it. You don't own it.

Just as the variables are immutable by default, so are the references. We are not allowed to change the value pointed to by a reference

Mutable references

If we want to change the value of a reference we have to say this explicitly to the compiler using the keyword mut Mutable references have a great restriction: if you have a mutable reference to a value, you cannot have other references to that value.

Nor can we have a mutable reference while we have an immutable one to the same value.

fn main() {
    let mut s = String::from("hello");
    change(&mut s);
}
 
fn change(some_string: &mut String) {
    some_string.push_str(", world");
}

warning

Rules for references:

1. At any time, you can have only a mutable reference or any number of immutable references but not both.
2. References must always be valid.

Copy trait

Let's take a similar code to the one presented before:

let mut x:i32 = 0;
let mut y = x;
y = 5;
println!("{x}"); // Prints 0

This time, the compiler seems to not have moved the variable x into y. Why? Because i32 implements Copy. This is a trait used for types that are inexpensive to duplicate bit by bit, and which also do not allow 2 mutable references to the same location in memory.

Type	Implements Copy	Reason
i32	Yes
f64	Yes
bool	Yes
String	No	It holds a pointer to its internal buffer. The buffer had to be duplicated when copying, action that a byte by byte copy is not able to do.
Vec<_>	No	It holds a pointer to its internal buffer. The buffer had to be duplicated when copying, action that a byte by byte copy is not able to do.
&str	Yes
&mut str	No	Copying would create another mutable reference to the same value.

You may implement the Copy trait to your structs and enums by using #[derive(Clone, Copy)]

warning

You must implement Clone trait in order to derive Copy. Also, all of the fields must have types that implement Copy.

Exercises

tip

If you don't have Rust installed, you can use Rust Playground to solve the topics.

info

Use the worksheet at the bottom: paste it into Rust Playground and click Test.

Part A. Warm-up (recap Lab 00.0 concepts)

1. Clamp + casting

Write a function that converts an i16 into a u8:

• values < 0 become 0
• values > 255 become 255
• otherwise cast normally

pub fn clamp_u8(x: i16) -> u8

---

2. Adjacent sums

Given a slice, return a Vec<i32> containing sums of adjacent pairs:

• [10, 20, 30] -> [30, 50]
• empty or length 1 -> empty vec

pub fn adjacent_sums(xs: &[i32]) -> Vec<i32>

---

3. Enum + match: log formatting

Define:

enum Log {
    Info(String),
    Warn(String),
    Error { code: u16, msg: String },
}

Write a function that turns a log into a single formatted line:

• Info("hi") -> "[INFO] hi"
• Warn("careful") -> "[WARN] careful"
• Error{code:7,msg:"bad"} -> "[ERROR 7] bad"

pub fn format_log(l: &Log) -> String

---

4. First “word” longer than N

Given a sentence &str, return the first whitespace-separated word with length strictly greater than n. If none, return None.

pub fn first_word_longer_than(s: &str, n: usize) -> Option<&str>

---

Part B. Ownership, borrowing, mutable references, Copy

5) “Why doesn’t this compile?” (fix with minimal edits)

Original snippet (doesn’t compile):

fn main() {
    let mut s = String::from("pico");
    let a = &s;
    s.push('!'); // error: cannot borrow `s` as mutable because it is also borrowed as immutable
    println!("{a}");
}

Task: make it compile without cloning. You may only:

• move prints around
• add/remove braces to shorten a borrow’s scope
• optionally change &String to &str in your version

Goal: prints something sensible and ends with s == "pico!".

(Worksheet uses a helper function so this can be tested.)

---

6. Split a Vec without cloning

Write a function that consumes a Vec<u8> and returns two vectors:

• first contains the first n elements (or all if shorter)
• second contains the rest

No cloning; move elements.

pub fn split_vec(v: Vec<u8>, n: usize) -> (Vec<u8>, Vec<u8>)

Hint: Vec::split_off

---

7. Mutate a String in place

Write a function that replaces the first occurrence of from with to inside s. Return true if replacement happened, false otherwise.

pub fn replace_first(s: &mut String, from: &str, to: &str) -> bool

Hint: find + replace_range

---

8. Return a slice (borrowing)

Given a slice of integers, return a sub-slice from the start up to (but not including) the first 0. If there’s no zero, return the whole slice.

pub fn until_zero(xs: &[i32]) -> &[i32]

---

9. Copy vs non-Copy: make a tiny math type

Create a Point that is Copy and implement:

• translate(p, dx, dy) -> Point
• manhattan(a, b) -> u32

Requirements:

• Point derives Clone, Copy, Debug, PartialEq, Eq

---

10. Inventory (ownership + borrowing + Result)

Implement a tiny inventory stored in a Vec<Item>.

Rules:

• add(name, qty) adds qty (creates item if missing)
• take(name, qty) subtracts qty
  • error if item missing
  • error if not enough quantity
• qty(name) returns current quantity as Option<u32>

Hint: iter_mut() for add/take, iter() for qty

---

11. Deduplicate in place

Remove duplicates from Vec<String> while preserving order, in place.

pub fn dedup_keep_order(xs: &mut Vec<String>)

Hint: retain + std::collections::HashSet

---

Rust Playground Worksheet (paste into Playground, then click Test)

// ================================
// Lab 00.1 Worksheet (Rust Playground)
// Paste this whole file into https://play.rust-lang.org/
// Then click: "Test" to run the tests.
// ================================

#![allow(dead_code)]

/* ------------------------------------------------
EX 1) Clamp + casting
------------------------------------------------ */
pub fn clamp_u8(x: i16) -> u8 {
    todo!()
}

/* ------------------------------------------------
EX 2) Adjacent sums
------------------------------------------------ */
pub fn adjacent_sums(xs: &[i32]) -> Vec<i32> {
    todo!()
}

/* ------------------------------------------------
EX 3) Enum + match: log formatting
------------------------------------------------ */
#[derive(Debug)]
pub enum Log {
    Info(String),
    Warn(String),
    Error { code: u16, msg: String },
}

pub fn format_log(l: &Log) -> String {
    todo!()
}

/* ------------------------------------------------
EX 4) First word longer than N
------------------------------------------------ */
pub fn first_word_longer_than(s: &str, n: usize) -> Option<&str> {
    todo!()
}

/* ------------------------------------------------
EX 5) Borrowing scope fix (no cloning)
Original (doesn't compile):
fn main() {
    let mut s = String::from("pico");
    let a = &s;
    s.push('!');
    println!("{a}");
}
Task: fix borrowing scope.

For a testable worksheet, implement this function so it returns "pico!".
(You can still add a println! inside if you want.)
------------------------------------------------ */
pub fn ex5_borrow_demo() -> String {
    todo!()
}

/* ------------------------------------------------
EX 6) Split a Vec without cloning (move elements)
Hint: Vec::split_off
------------------------------------------------ */
pub fn split_vec(v: Vec<u8>, n: usize) -> (Vec<u8>, Vec<u8>) {
    todo!()
}

/* ------------------------------------------------
EX 7) Mutate a String in place: replace first occurrence
Return true if replaced, false otherwise.
Hint: find + replace_range
------------------------------------------------ */
pub fn replace_first(s: &mut String, from: &str, to: &str) -> bool {
    todo!()
}

/* ------------------------------------------------
EX 8) Return a sub-slice until first 0
------------------------------------------------ */
pub fn until_zero(xs: &[i32]) -> &[i32] {
    todo!()
}

/* ------------------------------------------------
EX 9) Copy vs non-Copy: Point
------------------------------------------------ */
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Point {
    pub x: i32,
    pub y: i32,
}

pub fn translate(p: Point, dx: i32, dy: i32) -> Point {
    todo!()
}

pub fn manhattan(a: Point, b: Point) -> u32 {
    todo!()
}

/* ------------------------------------------------
EX 10) Inventory (ownership + borrowing + Result)
Store items by name in a Vec.
------------------------------------------------ */
#[derive(Debug, Default)]
pub struct Inventory {
    items: Vec<Item>,
}

#[derive(Debug)]
struct Item {
    name: String,
    qty: u32,
}

#[derive(Debug, PartialEq, Eq)]
pub enum TakeError {
    Missing,
    NotEnough { available: u32 },
}

impl Inventory {
    pub fn new() -> Self {
        Self { items: vec![] }
    }

    pub fn add(&mut self, name: &str, qty: u32) {
        todo!()
    }

    pub fn take(&mut self, name: &str, qty: u32) -> Result<(), TakeError> {
        todo!()
    }

    pub fn qty(&self, name: &str) -> Option<u32> {
        todo!()
    }
}

/* ------------------------------------------------
EX 11) Deduplicate in place, keep order
Note: simplest safe solution uses a HashSet<String> and clones for the "seen" set.
(Still mutates the original vec in place by draining & rebuilding.)
------------------------------------------------ */
pub fn dedup_keep_order(xs: &mut Vec<String>) {
    todo!()
}

/* ============================================================
TESTS
============================================================ */
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn ex1() {
        assert_eq!(clamp_u8(-10), 0);
        assert_eq!(clamp_u8(0), 0);
        assert_eq!(clamp_u8(42), 42);
        assert_eq!(clamp_u8(255), 255);
        assert_eq!(clamp_u8(256), 255);
        assert_eq!(clamp_u8(9999), 255);
    }

    #[test]
    fn ex2() {
        assert_eq!(adjacent_sums(&[]), vec![]);
        assert_eq!(adjacent_sums(&[5]), vec![]);
        assert_eq!(adjacent_sums(&[10, 20]), vec![30]);
        assert_eq!(adjacent_sums(&[10, 20, 30]), vec![30, 50]);
    }

    #[test]
    fn ex3() {
        let a = Log::Info("hi".to_string());
        let b = Log::Warn("careful".to_string());
        let c = Log::Error {
            code: 7,
            msg: "bad".to_string(),
        };

        assert_eq!(format_log(&a), "[INFO] hi");
        assert_eq!(format_log(&b), "[WARN] careful");
        assert_eq!(format_log(&c), "[ERROR 7] bad");
    }

    #[test]
    fn ex4() {
        assert_eq!(first_word_longer_than("", 3), None);
        assert_eq!(first_word_longer_than("a bb ccc", 3), None);
        assert_eq!(first_word_longer_than("a bb cccc ddddd", 3), Some("cccc"));
        assert_eq!(
            first_word_longer_than("rust ownership rules", 6),
            Some("ownership")
        );
    }

    #[test]
    fn ex5() {
        assert_eq!(ex5_borrow_demo(), "pico!");
    }

    #[test]
    fn ex6() {
        assert_eq!(split_vec(vec![], 3), (vec![], vec![]));
        assert_eq!(split_vec(vec![1, 2], 5), (vec![1, 2], vec![]));
        assert_eq!(
            split_vec(vec![1, 2, 3, 4, 5], 2),
            (vec![1, 2], vec![3, 4, 5])
        );
        assert_eq!(
            split_vec(vec![1, 2, 3, 4, 5], 0),
            (vec![], vec![1, 2, 3, 4, 5])
        );
    }

    #[test]
    fn ex7() {
        let mut s = "hello pico pico".to_string();
        assert_eq!(replace_first(&mut s, "pico", "board"), true);
        assert_eq!(s, "hello board pico");

        assert_eq!(replace_first(&mut s, "missing", "x"), false);
        assert_eq!(s, "hello board pico");

        // edge case: empty "from" should do nothing in this worksheet
        assert_eq!(replace_first(&mut s, "", "x"), false);
    }

    #[test]
    fn ex8() {
        assert_eq!(until_zero(&[]), &[]);
        assert_eq!(until_zero(&[1, 2, 3]), &[1, 2, 3]);
        assert_eq!(until_zero(&[1, 2, 0, 3, 4]), &[1, 2]);
        assert_eq!(until_zero(&[0, 9, 9]), &[]);
    }

    #[test]
    fn ex9() {
        let p = Point { x: 10, y: -2 };
        let q = translate(p, -3, 5);
        // p is still usable because Point is Copy
        assert_eq!(p, Point { x: 10, y: -2 });
        assert_eq!(q, Point { x: 7, y: 3 });

        assert_eq!(manhattan(p, q), 8);
    }

    #[test]
    fn ex10() {
        let mut inv = Inventory::new();

        assert_eq!(inv.qty("bolt"), None);

        inv.add("bolt", 10);
        inv.add("nut", 3);
        inv.add("bolt", 5);

        assert_eq!(inv.qty("bolt"), Some(15));
        assert_eq!(inv.qty("nut"), Some(3));

        assert_eq!(inv.take("nut", 2), Ok(()));
        assert_eq!(inv.qty("nut"), Some(1));

        assert_eq!(
            inv.take("nut", 5),
            Err(TakeError::NotEnough { available: 1 })
        );
        assert_eq!(inv.take("missing", 1), Err(TakeError::Missing));
    }

    #[test]
    fn ex11() {
        let mut xs = vec![
            "a".to_string(),
            "b".to_string(),
            "a".to_string(),
            "c".to_string(),
            "b".to_string(),
        ];
        dedup_keep_order(&mut xs);
        assert_eq!(xs, vec!["a".to_string(), "b".to_string(), "c".to_string()]);
    }
}

Bonus at home

1. Rewrite the function at exercise 2 from previous lab, but this time implement it using the Sieve of Eratosthenes.
2. Define a struct called MiniTuring, with a buffer of 256 booleans and a cursor.

• Write an associated (static) function called new that creates an instance of the structure.
• Write a method called display that prints the tape with 1's and 0's instead of trues and falses, without newlines or spaces in between
• Read the keyboard until "h" is received. "l" will move the cursor to the left with wrap around, "r" will move the cursor to the right with wrap around, "1" will set the element at the cursor to true, "0" will set the element at the cursor to false, "p" prints the value at cursor, "h" displays the tape

3. Create a basic expression parser for integer numbers, which supports +,-,*,/. Assume unary - will not happen (no expressions like 5*-3, -2+7)

• Define an enum called Expression with the appropriate variants(hint: use Box)
• Create a function that returns an Expression based on a given string. Respect operator precedence rules
• Creates a function that takes an Expression and evaluates it to an i32
• Read an expression from stdin and print out the result