Introduction to Rust Programming

Course Info

• Class Meetings: SCI 264, Mondays 5:30pm - 6:45pm
• Lab Meetings: SCI 240, Wednesdays 5:30pm - 6:45pm
• Office Hours: TBD
• Courelore: https://courselore.cs.swarthmore.edu/courses/7789521830/
• Online Textbook: The Rust Book
• Student Leaders: Quinn Okabayashi, William Ball
• Faculty Advisor: Zachary Palmer
• Schedule: See the Class Schedule page

This course is a half semester (7 weeks), half credit/no credit course that does not count towards CS credits. There will be four major components:

• 7 Class meetings
• 7 Lab meetings
• 6 Programming assignments (code + feedback form)
  • Labs 1 & 2 are solo, labs 3, 4, 5, and 6 are with partners.
• 6 Short writeups, one at the end of each assignment.

Grading

There are no exams, although each lab includes a brief questionnaire and an additional short writeup. Your final grade is determined by your lab grades and partitipation:

• Participation: 4%
• Lab 1-2: 12%
• Lab 3-6: 16%

Courselore

Our course also has a Courselore forum where you can ask questions and discuss the course material. When posting public questions, please make sure to follow the Academic Integrity Policy: don't give answers to homework in your public posts, for instance.

Who is this course designed for?

Students who have taken CS35 and CS31 and are interested in how theory can be applied to programming languages to make software more efficient, easier to write, and memory safe.

What are the goals of this course?

• Build interest in systems programming without ever touching gdb or valgrind.
• Reimagine what general purpose programming languages can look like.
• Learn how programming languages can guide us towards writing correct, scalable software.
• Write some correct, scalable software.

Academic Accomodations

If you believe you need accommodations for a disability or a chronic medical condition, please contact Student Disability Services (via email at studentdisabilityservices@swarthmore.edu) to arrange an appointment to discuss your needs. As appropriate, the office will issue students with documented disabilities or medical conditions a formal Accommodations Letter. Since accommodations require early planning and are not retroactive, please contact Student Disability Services as soon as possible.

For details about the accommodations process, visit the Student Disability Services website.

To receive an accommodation for a course activity, you must have an official accommodation letter from the Office of Student Disability Services and you need to meet with course staff to work out the details of your accommodation at least two weeks prior to the activity.

You are also welcome to contact any of the course staff privately to discuss your academic needs. However, all disability-related accommodations must be arranged, in advance, through Student Disability Services.

Academic Integrity

Academic honesty is required in all your work. Under no circumstances may you hand in work done with or by someone else under your own name. Discussing ideas and approaches to problems with others on a general level is encouraged, but you should never share your solutions with anyone else nor allow others to share solutions with you. You may not examine solutions belonging to someone else, nor may you let anyone else look at or make a copy of your solutions. This includes, but is not limited to, obtaining solutions from students who previously took the course or solutions that can be found online. You may not share information about your solution in such a manner that a student could reconstruct your solution in a meaningful way (such as by dictation, providing a detailed outline, or discussing specific aspects of the solution). You may not share your solutions even after the due date of the assignment.

In your solutions, you are permitted to include material which was distributed in class, material which is found in the course textbook, and material developed by or with an assigned partner. In these cases, you should always include detailed comments indicating on which parts of the assignment you received help and what your sources were.

When working on quizzes, exams, or similar assessments, you are not permitted to communicate with anyone about the exam during the entire examination period (even if you have already submitted your work). You are not permitted to use any resources to complete the exam other than those explicitly permitted by course policy. (For instance, you may not look at the course website during the exam unless explicitly permitted by the instructor when the exam is distributed.)

Failure to abide by these rules constitutes academic dishonesty and will lead to a hearing of the College Judiciary Committee. According to the Faculty Handbook:

Because plagiarism is considered to be so serious a transgression, it is the opinion of the faculty that for the first offense, failure in the course and, as appropriate, suspension for a semester or deprivation of the degree in that year is suitable; for a second offense, the penalty should normally be expulsion. This policy applies to all course work, including but not limited to code, written solutions (e.g. proofs, analyses, reports, etc.), exams, and so on. This is not meant to be an enumeration of all possible violations; students are responsible for seeking clarification if there is any doubt about the level of permissible communication.

The general ethos of this policy is that actions which shortcut the learning process are forbidden while actions which promote learning are encouraged. Studying lecture materials together, for example, provides an additional avenue for learning and is encouraged. Using a classmate’s solution, however, is prohibited because it avoids the learning process entirely. If you have any questions about what is or is not permissible, please contact your instructor.

Resources

• The Rust Book
• Rust by Example
• Rust Playground
• Influences

Class Schedule

Week 1

Class 1: Starting on Rust

Why Rust?

In this course, we'll be programming in a language called Rust. Rust is a relatively young programming language that officially reached 1.0 in 2015, making it decades younger than most other popular languages. Although it's young, Rust isn't a particularly new language: it has many influences and is somewhat of a melting pot of popular ideas from the past 50 years. For example, Rust has a lot of C++ influences making it particularly good for low-level programming, but it also takes a lot of ideas from functional programming languages like OCaml and Haskell, which are more popular in academia.

If that doesn't get you excited, consider this. You've taken CS31 and CS35, and now have experience writing C and C++ programs. While those languages are cool because they give you so much control, how many times did that end up backfiring by allowing you to shoot yourself in the foot? How many times did you think you finished a lab, but then end up spending another hour trying to satisfy Valgrind? How many segmentation faults did you get from accidentally dereferencing null pointers?

Rust is a programming language that parallels C and C++ in terms on control over memory management, but also guarantees memory safety at compile time. That means you can still write all the fun, optimized programs in Rust that you could in C or C++, but without ever having to worry about Valgrind or segfaults. For this reason, companies like Google, Microsoft, Amazon, Meta, and more are all using Rust in some areas as a replacement for where they would otherwise use C++.

Cargo, the Rust Package Manager

You're probably completely unfamiliar with Rust, and that's totally okay. The goal of this class is to get you up to speed on the very fundamentals so that you can get through the first lab.

Rust, like C++, is a compiled language. That means you need to run the compiler to convert your program into a binary before you can run it. If you've taken CS35 recently, you'll probably remember clang++, which is the command line tool used to invoke the compiler. Rust has a tool called rustc, which is similar in that it can be used to invoke the Rust compiler with a whole lot of configuration options.

However, just like how you almost never touched clang++ directly and used Makefiles instead, we'll never be using rustc directly because it's a pain to manually use. Instead, we'll be using Cargo. Cargo is the official Rust package manager, and will allow us to create projects, compile projects, download dependencies, and is capable of much more that we won't be exploring. It should be installed on all the lab machines already.

To use Cargo, you need a project, which is just a directory containing a Cargo.toml configuration file and a src/ directory containing source code files. There are two kinds of projects: applications and libraries. Applications have a main function just like C++, while libraries do not but expose a public interface of functions and types that can be used by other libraries or applications. If the project is an application, then the src/ directory must contain a main.rs file, where .rs is the file extension for Rust source code. If it's a library, then the src/ directory must contain a lib.rs file.

Running your first "Hello, world!" program

Let's start with a quick "hello world" program. We'll first run the cargo new command to create a new Rust project that's an application:

$ cargo new hello-world

This command will then create the project which looks like this right now:

hello-world/
├─ src/
│  ├─ main.rs
├─ Cargo.toml

In your labs, the files you git clone from the starter code repositories should have a file structure similar to this so you shouldn't need to use cargo new yourself.

You might be wondering what Cargo.toml is, and it can be summarized as a configuration file that serves a similar purpose to a Makefile. It will default to the following when created with cargo new:

[package]
name = "hello-world"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]

It's used for specifiying dependencies and configuring compiler options, as well as providing project metadata when publishing a project to the internet. Since we're working on such a simple program right now, we can leave it with all the defaults.

Then, we'll cd into the project directory:

$ cd hello-world

... and open up src/main.rs in our favorite editor:

fn main() {
    println!("Hello, world!");
}

Pro tip: for most blocks of Rust code on this website, you can hover your cursor over the block which should make some buttons appear at the top right corner. If you press the play button, it will compile and run the code and show you the result!

In fact, Cargo will already default to the hello world program for new applications. Since this is an application and not a library, we can run the program using cargo run from inside the top level of the project directory:

$ cargo run
   Compiling hello-world v0.1.0 (/Users/quinn/Documents/hello-world)
    Finished dev [unoptimized + debuginfo] target(s) in 2.44s
     Running `target/debug/hello-world`
Hello, world!

You may be wondering where the binary is. After all, running make in CS35 spits out a binary that you have to run yourself.

The answer is that Cargo will put all files related to the compilation process, including the resulting binary, in a target/ directory in your project. For example, you can find the binary at target/debug/hello-world as hinted in the above output.

Syntax of "Hello, world!" program

Now we're going to spend the rest of the class talking about basic Rust syntax for doing things that you should already be familiar with from other languages.

Let's start by walking through some syntax by starting with the "Hello, world" example:

fn main() {
    println!("Hello, world!");
}

Let's break it down line by line, starting with the first where we declare the main function:

fn main() {
}

Unlike C and C++, function declarations start with the fn keyword instead the the return type. Then comes the name, main, followed by the arguments that the function takes, which are always empty for the main function.

In C and C++, we've seen argc and argv used here, but Rust has an alternate way of accessing command line arguments (std::env::args()) which we won't discuss now.

Then there's an open brace to indicate the start of the function, which takes us to the next line:

fn main() {
    println!("Hello, world!");
}

In Rust, we use println!() to print to the console.

Notice that it has ! between the name and the arguments: this indicates that it is a macro, not a function. If it were a regular function, we would call it like println() instead without the !. Macros aren't as common as functions and we won't discuss the differences too much, but know that one of their use cases is for acting like a function that can take a variable number of arguments.

After the println!() statement, we end the function with a semicolon. Just like C++, Rust doesn't care about whitespace and needs the ; to determine when a statement ends.

Comments

Comments in Rust are identical to C and C++, where we use double slash // to denote a comment:

// The main function
fn main() {
    println!("Hello, world!"); // This let's us print to the console
}

You can also use /* */ for multiline comments, but // is almost always used in practice.

In most editors, you can highlight multiple lines and press ctrl + / to automatically comment and uncomment all highlighted lines. Note that you don't even need to highlight an entire line; any line that is even partially highlighted will toggle between commented or uncommented. You can try this out for yourself on this editable code block!

fn main() {
    println!("Hello");
    println!("Good morning");
    println!("Greetings");
}

See Chapter 3.4 for more details.

Variables and Mutability

In languages like C++, we're used to defining variables like so:

int x = 4;

In Rust, the equivalent would be written as:

#![allow(unused)]
fn main() {
let x: i32 = 4;
}

In the Rust example, we start with the keyword let, followed by the variable name, followed by : and the type, followed by an assignment. It should also be noted that instead of int for a 32-bit signed integer, it's called i32 in Rust instead.

And just like C++, Rust is statically typed meaning that the compiler needs to know the types of all variables when the program is compiled, and values can't change type halfway through a program. However, that doesn't mean that we have to explicitly write the types of all variables, and that's thanks to type inference, a feature built into the compiler. This means that we can omit writing the type altogether most of the time, like

#![allow(unused)]
fn main() {
let x = 4;
}

... and the language will figure out that x should have the type i32 when the program is compiled because 4 is a number.

One thing to note is that all variables are immutable by default. This means that once assigned, their values cannot change:

fn main() {
    let x = 4;
    println!("The value of x is {}", x);
    // Trying to reassign `x`
    x = 6;
    println!("The value of x is {}", x);
}

Oh yeah, this is how you print values. Think of it as exactly the same as C's printf function, but using {} as a placeholder for variables (regardless of type) instead of the weird mixture of %s and friends that you use in C.

Running this example, we get a compilation error: cannot assign twice to immutable variable `x` . In order to make x mutable, we can add the mut keyword to the declaration:

fn main() {
    let mut x = 4;
    //  ^^^
    println!("The value of x is {}", x);
    // Now we can reassign `x` and it will compile!
    x = 6;
    println!("The value of x is {}", x);
}

See Chapter 3.1 for more details.

Primitive Types

Since Rust is a systems programming la Just like C++, Rust has several primitive types that are built into the language. Here's a table with some of them:

See Chapter 3.2 for more details.

Functions

We've already seen the main function, but what about functions that have inputs and outputs? Let's write a function to add two numbers:

#![allow(unused)]
fn main() {
fn add(a: i32, b: i32) -> i32 {
    a + b
}
}

There's a lot going on here, so lets break it down.

The first thing to notice is that unlike C++, parameters in Rust are the name, followed by :, followed by the type. In this case, this means writing a: i32, b: i32. Unlike assigning variables, the type annotation is mandatory in functions.

To specify the return type, we put -> followed by the type after the list of parameters. In this case, we write -> i32, and this is also mandatory for functions that return values.

Now you may be wondering: where is the return statement, and why is there no ; at the end? Similar to functional languages like OCaml, Rust is an expression based language. At a high level, this means that functions always return whatever expression they evaluate to, so there's no need to write return most of the time when you can just say the last expression without a semicolon and have it implicitly returned.

Note that this is only the case if the expression is at the end of the function. For returning early, the return keyword can be used similarly to C++.

At this point, you may be wondering how functions that return "nothing", like main, work. These work thanks to another primitive type in Rust: the () type (pronounced "unit"). Just like how i32 is a type with 2³² possible values, () is a type with exactly one value: (). It contains no state, and it may help to think of it as if void could be an actual value that you can assign to a variable. Omitting the return type like we do in main is just syntactic sugar for -> (), and ending an expression with ; will make it evaluate to ().

See Chapter 3.3 for more details.

Control Flow

There are three pieces of control flow you will need for the first lab: for loops, while loops, and if-else statements.

As you know, for loops let you iterate through some values. Fortunately, Rust's for loop syntax is quite similar to Pythons. To loop from 0 (inclusive) to 10 (exclusive), we write:

#![allow(unused)]
fn main() {
for i in 0..10 {
    // Do stuff with `i`.
    // For example, print it!
    println!("i = {}", i);
}
}

We can write for <variable> in <iterator> { ... }, where unlike C++, the braces are mandatory for the body of the loop.

while loops are also very straight-forward:

#![allow(unused)]
fn main() {
let mut n = 10;

// Decrement `n` each time until it's 0.
while n != 0 {
    n -= 1;
}
}

This is basically the same as a while loop in C++, but again we don't need parentheses around the conditional, and braces for the body of the loop are required. As a side note, the math operators and comparison operators as shown above are pretty much the same as C++, except you can't do i++ or i-- for incrementing or decrementing a variable.

The last tool that you'll need are conditional expressions. Building from what we've seen so far, they look exactly how you'd expect them to:

#![allow(unused)]
fn main() {
let age = 21;

if age > 18 {
    println!("You're an adult!");
}
}

You can also add an else block, just like in C++:

#![allow(unused)]
fn main() {
let price = 200;

if price < 20 {
    println!("Cheap");
} else {
    println!("Expensive");
}
}

And lastly, you can have multiple branching else if blocks:

#![allow(unused)]
fn main() {
let age = 32;

if age < 18 {
    println!("Child");
} else if age > 65 {
    println!("Senior");
} else {
    println!("Adult");
}
}

These should all feel very familiar from C++, with the only difference being that parentheses are not required.

Remember in the above section, where we said everything is an expression? This also applies to if-else expressions, where the expression as a whole will evaluate to whatever either of its blocks evaluate to. For this reason, the bodies of the if and the else parts must evaluate to the same type.

Here's an example:

#![allow(unused)]
fn main() {
let a = 21;
let b = 24;

let max = if a < b {
    b
} else {
    a
};
}

Since the if-else block is an expression and a and b have the same type, then this will assign max the value of whichever is larger. The reason it wouldn't work if a and b have different types is because Rust needs to figure out ahead of time the type of max, and it cannot do this if the condition is based on something at runtime like user input.

We could also make this a function:

#![allow(unused)]
fn main() {
fn max(a: i32, b: i32) -> i32 {
    if a < b {
        b
    } else {
        a
    }
}
}

Since the function only contains one expression, the if-else expression, it will evaluate that. Then, based off of whether a < b, the conditional will evaluate to either a or b. Notice how there are no semicolons terminating any lines of this function.

Writing functions like the above are considered idiomatic and clean in Rust, and you should aim to write code that takes advantage of expressions like this in your labs.

See Chapter 3.5 for more details.

~

Summary

• Rust guarantees memory safety while targetting a similar domain as C++.
• Cargo is used to manage Rust projects, like compiling and running with cargo run
• The main function is where Rust programs start.
• Comments use // like C++.
• Rust is statically typed like C++, but variable types can be infered by the compiler.
• Variables are immutable by default.
• Functions implicitly return the last expression.
• if-else statements evaluate to expressions.
• Control flow has similar syntax to Python, except with curly braces.

For a more in depth exploration of the above concepts, check out Chapter 3 of the Rust Book.

Lab 1: Rust Basics

Due February 14, 11:59pm

In this lab, we'll be getting some practice writing basic Rust functions using control flow, as well as learning some tools that will help us write good Rust code for the rest of the semester.

Grading Rubric

• Code is formatted properly using cargo fmt: 5%
• Code passes cargo clippy without warnings: 20%
• Code passes our tests: 50%
• Responses in questionnaire.md: 25%

Table of Contents

• Setting up your environment: Installing Cargo, cloning git repos, and installing rust-analyzer on VSCode.
• Writing basic functions: Assignment direction.
• Formatting your code: How to automatically format your code.
• Styling your code: How to check your code for style.
• Testing your code: How to write tests.
• Questionnaire: Answer some brief questions about Rust.
• Feedback: Give us your feedback!
• Submitting: How to submit your lab.

Setting up your environment

Since the lab computer don't currently come with Cargo installed, we'll install it ourselves. If you'd like to work on your personal computer, visit https://rustup.rs/ for installation instructions. This will take up about ~1.2GB on your machine, but you can always uninstall it later.

For the lab machines, you'll need to run the following lines in the terminal:

cd
mkdir /scratch/<your-username>/.rustup
ln -s /scratch/<your-username>/.rustup ~/.rustup
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

Make sure to replace <your-username> with your Swarthmore username. For instance, you might write

mkdir /scratch/student1/.rustup

if your Swarthmore username were student1. (It isn’t.)

Next, create a directory for where you'll store the repositories for this course:

mkdir cs17sr && cd cs17sr

Then, clone your starter code from your Git repo, ensuring to replace <your-username> with your Swarthmore username as well:

git clone git@github.swarthmore.edu:cs17sr-s23/lab1-<your-username>.git

Running the clone command will cause git to create a directory named e.g. lab1-student1 in your current directory. For editing, you should be using VSCode because it has solid integration with rust-analyzer, a utility that is extremely helpful for writing Rust code. Run the following command to install it as a VSCode extension:

code --install-extension rust-lang.rust-analyzer

Then you can open your repo with VSCode, making sure to replace student1 with your username:

code lab1-student1

If you've done everything correctly, you should see this file tree on the left side of your VSCode window:

src/
├─ lib.rs
├─ tests.rs
.gitignore
Cargo.toml
questionnaire.md

Now you're ready to get started!

Writing basic functions

In src/lib.rs, you'll find a variety of functions with comments explaining what it should do, and it's your task to implement them. Several of these functions can be solved iteratively and recursively, and you should aim to use both of these strategies for at least one function each.

If you're having troubles, that's totally okay! Learning the syntax of a new language is always tricky, so please don't hesitate to ask questions either in person or on Courselore.

Tips

• When you start, each function will each contain a todo!() statement, which is a placeholder macro that will allow the program to compile but instantly crashes when the function is called. Make sure to remove this when you implement each function!
• Don't be afraid to use return when you need to return a value that's not the last expression, such as in the middle of a loop.
• Remember to use let mut for variables you might want to update.
• Read the instructions and error messages carefully.

Formatting your code

Although Rust doesn't care about whitespace in code similar to C++, the Rust community has generally agreed on formatting guidelines so all Rust programs can have some internal consistency with spacing. In fact, Cargo even comes with a built-in command to format your code according to these guidelines automatically:

cargo fmt

Make sure to run this before your submit your code, as it is worth 5% of your lab grade and is so easy to do!

Styling your code

While cargo fmt can be used to fix up the whitespace on your code, Cargo also comes with a built-in linter called Clippy, which can detect and provide suggestions for patterns that are not idiomatic Rust code. To use Clippy, run the following Cargo command:

cargo clippy

To demonstrate Clippy, take the following function:

#![allow(unused)]
fn main() {
fn add(a: i32, b: i32) -> i32 {
    return a + b;
}
}

Although this function works as expected, cargo clippy will fail because it's more idiomatic to write a + b instead of return a + b;. Clippy is a valuable tool for helping you write more idiomatic programs and catch common antipatterns, so you should become accustomed to taking feedback from it.

Make sure your code passes cargo clippy before submitting your code, as it is worth 20% of your lab grade!

Testing your code

So far, we've seen cargo fmt and cargo clippy. While these tools can make your code look good and Rusty, they don't say much about the correctness of how your code works. For that, we need testing.

Near the top of lib.rs, you'll find these lines:

#![allow(unused)]
fn main() {
#[cfg(test)]
mod tests;
}

The second line declares a submodule called tests, whose implementation can be found in src/tests.rs, while the first line is an attribute. It tells the compiler to only look at mod tests when compiling with the test flag, otherwise ignore it completely.

Making our way over to src/tests.rs, we find the following at the top of the file:

#![allow(unused)]
fn main() {
mod tests {
use super::*;
}
}

The super part says "things defined in the super module" (src/lib.rs in this case), and the ::* means "in this module, bring everything into scope". This means that functions like is_divisible, defined in src/lib.rs, can be used here in src/tests.rs. If we wanted to call is_divisible without this use line, then we would need to specify the fully-qualified path instead: super::is_divisible, which says "in the super module, I'm taking about the is_divisible function."

Writing tests is straight forward: just define an ordinary function with no parameters and returning () named whatever you want the test to be called. Then, write #[test] above it to tell Rust that it's a test, and put your code inside.

Inside the function, you can use the assert!() macro which will crash your program if a condition is not true. See the examples in its documentation for ideas on how to use.

When writing tests, you should try to keep each test function small and not test too many different things at once. That being said, each test can contain more than a single assert!() statement. For example, a test function for the Fibonacci sequence might consist of several checks that different values in the sequence are properly calculated by the fib function:

#![allow(unused)]
fn main() {
// Dummy function hardcoded to make this test work. Do not copy!
fn fib(n: u32) -> u32 {
    match n {
        0 => 0,
        1 => 1,
        2 => 1,
        3 => 2,
        4 => 3,
        5 => 5,
        6 => 8,
        _ => unreachable!(),
    }
}
#[test]
fn test_fib() {
    let answers = [0, 1, 1, 2, 3, 5, 8];
    for i in 0..7 {
        assert!(fib(i) == answers[i]);
    }
}
}

To run all your tests, use the following Cargo command:

cargo test

This will run all functions marked as #[test] and display the results.

For this lab, you're required to write one test for each function, but are welcome to write more if you'd like. Note that 50% of your grade on this lab comes from your code passing our tests (hidden from you), so it's important that you test your code to build confidence that it works properly and handles any edge cases if there are any.

Questionnaire

The last part of this assignment is to fill our several short response questions in questionnaire.md.

Feedback

Please fill out this short feedback form.

Submitting

Once you're finished, be sure to verify that:

• cargo fmt has been run
• cargo clippy passes
• cargo test passes

Then you can push your changes with the usual: git add ., git commit -m "your message", and git push.

Congratulations on finishing!

Week 2

Class 2: Ownership and Borrowing

Here's some Rust code that looks perfectly safe. However, it doesn't compile.

fn print_string(s: String) {
    println!("{s}");
}

fn main() {
    let hello = "Hello, World".to_string();
    print_string(hello);
    print_string(hello);
}

The reason this code doesn't compile has to do with an important concept in Rust called ownership that we will be exploring in this lesson. Despite the fact that this code is apparently perfectly safe, Rust disallows it. Rust has very strict rules regarding what kind of code is allowed, but these rules allow Rust to prevent all sorts of memory errors, like memory leaks, double frees, and use after free.

Ownership and Dropping

A key part of how Rust accomplishes this is called its ownership model. In Rust, every value has a unique owner.

This isn't technically 100% true. Sometimes you really do need shared ownership, and Rust has mechanisms in place for that we will discuss later, but the vast majority of time every value has a unique owner.

When that owner goes out of scope, the value is dropped, and code is run to clean up any allocated resources. This pattern, called Resource Acquisition Is Initialization (RAII), may sound familiar from C++, where destructors can automatically clean up resources.

#![allow(unused)]
fn main() {
{
    // allocates memory on the heap for `s`
    let s = "this is a string".to_string();
} // when `s` goes out of scope, that memory is automatically freed
}

Where Rust differs from C++ is that this model is enforced by the compiler on every value. So while, C++ can work just like Rust in this regard,

{
    // allocates memory on the heap for `s`
    std::string s = "this is a string";
} // when `s` goes out of scope, the destructor is called, freeing
  // the memory

it is ultimately just a convention that you can ignore.

{
    // manually allocate memory on the heap
    char *s = new char[17];
    strcpy(s, "this is a string");
} // uh-oh, memory leak!

Even the CS35 lab 2 website calls "delet[ing] any dynamically allocated array" a style requirement.

Analogy

As an analogy, imagine a storage facility. Every thing in the storage facility has a unique owner. This owner signed a contract with the storage facility, promising to clean everything they own up when the contract expires.

Moving

This model is all well and good if we only have one variable, but things get more complicated as we add multiple variables.

For example, this code below compiles and works just fine, despite the fact that based on what we've learned so far it shouldn't.

#![allow(unused)]
fn main() {
{
    // declare a `String`
    let s1;
    {

        // allocate memory on the heap for `s2`
        let s2 = "Why does this work?".to_string();

        s1 = s2;

    } // `s2` goes out of scope, so the string should
      // be dropped, right?

    println!("{}", s1); // but it's still good here
}
}

Rust allows ownership to transfer. The primary way it does this is by moving a value. To see how this works, let's look at what happens in the above code when we say s1 = s2. A String in Rust is basically a pointer to some characters, a length, and a capacity. When we say s1 = s2, these three things are copied over from s2 into s1. At this point, both s1 and s2 have pointers to the same data, muddying ownership. Importantly, Rust then invalidates s2 to avoid having two variables own the same data. Trying to use s2 after s1 = s2 is a compile error.

What is really clever about this is, in addition to guaranteeing unique ownership, we never needed to copy the actual string. Whether the string is 10 characters or 1,000,000, the move will always take the same amount of time.

Compare this to roughly equivalent C code, where ownership isn't tracked.

char *s1 = malloc(17); // allocate s1
strcpy(s1, "This is a string"); // give it the value "This is a string"

char *s2 = s1; // copy the pointer over to s2

puts(s1); // "This is a string"
puts(s2); // "This is a string"

free(s1); // Uh-oh, who owns the data?
free(s2);

After copying the pointer, both references are still valid, meaning it is ambiguous who is responsible for freeing the data when they are done, unlike in Rust where it is clear who has ownership of the data.

Analogy

Continuing the storage facility analogy, if you have a ton of stuff in a storage unit that you want to give to a friend, rather than empty the storage unit, move everything to where they want it, you can just give them the key to your storage unit and fill out some paperwork to transfer the ownership. This way your friend owns the stuff, you don't need to physically move anything, the storage facility is happy, and only one person has access to the stuff.

Copying

This is nice, but can get really annoying for code like below.

#![allow(unused)]
fn main() {
let three = 3;
let four = three + 1;       // A

println!("3 = {}", three);  // B
println!("4 = {}", four);
}

Under the rules we've seen so far, ownership of the value 3 is passed from three to four on the line marked A, meaning we shouldn't be able to use three on the line marked B. This, however, is ridiculous! No one owns 3, it's just a number. To avoid this problem, primitive types like i32 or bool can be copied without invalidating the old value. Since no cleanup is required, we don't have the double free problem to worry about, like with String, and since these types are small enough, there isn't really anything more efficient you can do than just copying them.

When values can be copied rather than moved is a bit more complicated than this in Rust and involves something called the Copy trait. We will learn more about how this works in week 4.

Analogy

To continue the storage facility analogy, if what you are planning on giving your friend is very small, light, and common, it might be easier to just buy them a copy rather than deal with the storage facility. Then both people own a copy of the thing, which isn't a problem since it's so commonly available and isn't kept in a storage facility.

Borrowing

This is all very good and solves a lot of problems, but we are still quite limited with just moving and copying. For instance, suppose we want to implement a capitalize function in Rust to capitalize a String.

#![allow(unused)]
fn main() {
fn capitalize(s: String) -> String {
    s.as_str().to_uppercase()
}
}

To see in a bit more detail how this function works, check out the Rust docs here and here.

Right now, the only way for us to see what's in a String (like we would want to to be able to capitalize it), is to take ownership of it. However, since capitalize takes ownership of s, we end up losing the original string. This means seemingly innocuous code like this doesn't compile.

#![allow(unused)]
fn main() {
fn capitalize(s: String) -> String {
   s.to_uppercase()
}
let boring = "Hello World".to_string();
print!("{} ", capitalize(boring));  // `boring` moved here!
println!("is louder than {}", boring); // `boring` no longer valid!
}

Fortunately, Rust lets us borrow data rather than take ownership of it. We can do so via references. References are like pointers in that they refer to a value. However, within the Rust ownership model, they do not own what they refer to. This has important implications. For one, since references don't own what they refer to, the value they refer to isn't dropped when they go out of scope. Additionally, multiple references referring to the same thing can exist, since they don't own it.

This is perfect for our capitalize function, since we don't need to own s.

#![allow(unused)]
fn main() {
fn capitalize(s: &String) -> String {     // `s` is a reference
    s.as_str().to_uppercase()             // when `s` goes out of scope,
                                          // the original string isn't dropped,
                                          // since `s` is just borrowing it
}
}

A reference to a String can be automatically coerced into &str, which is generally better. Rather than create a pointer to a String (which is basically just a pointer to some characters anyway), we end up with the pointer to the characters directly. This means we can write capitalize as shown below and call it in exactly the same way.

#![allow(unused)]
fn main() {
fn capitalize(s: &str) -> String {
    s.to_uppercase()
}
}

Now our function capitalize just borrows s rather than consuming it. Now the following code compiles and does what we expect it to.

#![allow(unused)]
fn main() {
fn capitalize(s: &String) -> String {     // `s` is a reference
   s.to_uppercase()                      // when `s` goes out of scope,
                                         // the original string isn't dropped,
                                         // since `s` is just borrowing it
}
let boring = "Hello World".to_string();
print!("{} ", capitalize(&boring));  // now `capitalize` doesn't own `boring`
print!("is louder than {}", boring); // so we can use it here
}

What if, rather than return a new string, we want capitalize to modify the string passed in to it? We can try the following code, but it fails to compile. Note as well that, like C, we can use * to refer to the original data rather than the reference, which is necessary if we are trying to assign to it. However, unlike C or C++, there is no difference between . and ->, since Rust is smart enough to automatically dereference in those situations.

#![allow(unused)]
fn main() {
fn capitalize(s: &str) {      // borrow `s` here
    *s = s.to_uppercase()     // try to change it
}
}

The reason this doesn't compile is, like variables, references are immutable by default. We can make a reference mutable by specifically adding mut. Now the following code compiles.

#![allow(unused)]
fn main() {
fn capitalize(s: &mut String) { // borrow `s` MUTABLY here
    *s = s.to_uppercase()       // now we can change it
}
}

Here we do need String rather than str since we are dereferencing and assigning to it.

And to use it, we must create a mutable reference, rather than just a regular reference.

#![allow(unused)]
fn main() {
fn capitalize(s: &mut String) { // borrow `s` MUTABLY here
   *s = s.to_uppercase()       // now we can change it
}
let mut lowercase = "Hello World".to_string(); // create `lowercase`, which MUST BE MUTABLE
println!("{} is lowercase", lowercase); // use it
capitalize(&mut lowercase); // now we borrow `lowercase` MUTABLY
println!("and {} is uppercase", lowercase); // now `lowercase` is different
}

What's particularly useful about references, is since a reference must be created after the data it refers to, and a reference is guaranteed to go out of scope before the owner of the original data, the reference is guaranteed to be valid for the entire scope of the reference. This fixes problems in other languages with manual memory management where it's possible to have a pointer to data that has already been freed.

References are extremely important, both in Rust and in programming in general.

Analogy

Continuing the storage facility analogy, if you want to lend a friend some stuff in your storage unit, you can give them a copy of your key. This way you still own the storage unit, but your friend can also access it.

References to Chunks of Memory

One very common use of pointers in C/C++ is to point to contiguous chunks of memory. However, references can only refer to a single value so we need something new to refer to contiguous chunks of memory. First, we can create contiguous chunks of memory on the stack with arrays. Arrays work very similarly to arrays in other languages, and have type [T; N], where T is the type contained in the array and N is the length.

#![allow(unused)]
fn main() {
let one_two_three: [i32; 3] = [1, 2, 3];
let five_threes: [i32; 5] = [3; 5];
}

We can write functions that take ownership of arrays, but this is generally a bad idea for a few reasons. First, that will require copying or moving the entire array, which is often very expensive. Second, arrays of each different length are different types, requiring different functions for each length.

#![allow(unused)]
fn main() {
fn average_of_three(arr: [f32; 3]) -> f32 {
    arr.iter().sum::<f32>() / 3.0
}

fn average_of_four(arr: [f32; 4]) -> f32 {
    arr.iter().sum::<f32>() / 4.0
}
}

There is a way around having to create all these functions by hand with const generics, which were recently added to Rust stable. This is still a really bad idea, though, since you really don't want to take ownership of the array.

Fortunately, Rust has a mechanism that fixes both problems, namely slices. A slice is a reference to a contiguous chunk of memory that boils down to a pointer and a length. This way we can borrow an entire chunk of memory without having to move or copy it.

#![allow(unused)]
fn main() {
fn average(slice: &[f32]) -> f32 {
    slice.iter().sum::<f32>() / slice.len() as f32
}
}

Note here that the type of slice is &[f32] with no mention of the length. Unlike arrays, length is not part of the type of a slice. After all, if a slice is just a pointer and a length, the size of a slice is always the same, regardless of how large the chunk of memory it points to is. This fixes the second problem with taking arrays we had.

If we want to use this function, we have to create a slice, which we can do in several ways. One way is to just borrow the whole array.

#![allow(unused)]
fn main() {
fn average(slice: &[f32]) -> f32 {
   slice.iter().sum::<f32>() / slice.len() as f32
}
let arr = [1.0, 2.0, 3.0, 4.0];
println!("{}", average(&arr));
}

The fact that they are called "slices" suggests that we can take smaller slices of an array than the entire thing, which is true.

#![allow(unused)]
fn main() {
fn average(slice: &[f32]) -> f32 {
   slice.iter().sum::<f32>() / slice.len() as f32
}
let arr = [1.0, 2.0, 3.0, 4.0];
println!("{}", average(&arr[1..3])); // takes indices 1 through 3, not including 3
println!("{}", average(&arr[1..]));  // takes everything after index 1 
println!("{}", average(&arr[..3]));  // takes everything up to but not including index 3
println!("{}", average(&arr[..]));   // takes everything, equivalent to just &arr
}

As usual, there's a lot more detail about slices in the Rust book here.

Conclusion

For more details on Rust's ownership model specifically, see this chapter of The Book.

~

Summary

• Every piece of data has a unique owner.
• When that owner goes out of scope, the data is dropped.
• Ownership can be transferred by moving or copying the data.
• Data can also be borrowed via references to avoid unnecessary copying/moving.
• References are guaranteed at compile time to always be valid.
• Slices are references to contiguous chunks of memory.
• You can't borrow something if it is already mutably borrowed, guaranteeing immutability.

Lab 2: Baking Cookies

Due February 21, 11:59pm

We just spent the last class discussing how Rust's ownership model works. In this lab we will be exploring this idea by baking some cookies.

Grading Rubric

• Code is formatted properly using cargo fmt: 5%
• Code passes cargo clippy without warnings: 20%
• Implementation of Dough, Cookie, and Oven: 25%
• Responses in questionnaire.md: 50%

50% of the grade for this lab is in the questionnaire. Allocate your time appropriately!

Learning Objectives

• Practice working with the Rust ownership model.
• Explore how Rust's ownership model can catch common bugs.

Table of Contents

• Structs: Basic overview of structs in Rust.
• Baking Cookies: Overview of the lab.
  • The Dough type: Specification for a struct representing dough.
  • The Cookie type: Specification for a struct representing cookies.
  • The Oven type: Specification for a struct representing an oven.
• Questionnaire: Answer some brief questions about Rust.
• Feedback: Give us your feedback!
• Submitting: How to submit your lab.

Structs

Skim or read this section of the Rust book to familiarize yourself with Rust's syntax for structs. I'd like to particularly draw your attention to this sentence.

Methods can take ownership of self, borrow self immutably as we've done here, or borrow self mutably, just as they can any other parameter.

They don't give any examples of taking ownership of self or borrowing self mutably, so I will extend their examples here. Let's say we wanted to add an expand_width method to the Rectangle struct they had. We could do that like so:

#![allow(unused)]
fn main() {
impl Rectangle {
    fn expand_width(&mut self, amount: u32) {
        self.width += amount;
    }
}
}

This time, note that &mut self is shorthand for self: &mut Self which is itself an alias for self: &mut Rectangle.

Let's say we also had a Square struct defined simply as shown below.

#![allow(unused)]
fn main() {
struct Square {
    width: u32,
}
}

Then we might want a method for the Rectangle struct to convert it into a Square with the same width. In this case, we want to take ownership of the Rectangle and return a new Square. This method would look like the following.

#![allow(unused)]
fn main() {
impl Rectangle {
    fn square_of_same_width(self) -> Square {
        Square {
            width: self.width,
        }
    }
}
}

Now self is shorthand for just self: Self, meaning self owns the struct, meaning the struct is dropped when this function returns! This means that the following code does not compile.

#![allow(unused)]
fn main() {
let rect = Rectangle {
    width: 10,
    height: 20,
};

let square = rect.square_of_same_width();
println!("{} = {}", rect.width, square.width);
}

I encourage you to ponder why it's a good thing that Rust doesn't allow this code to compile even though, in this circumstance, it seems perfectly safe.

Baking Cookies

With that out of the way, we can get to the good stuff. In this lab, we will be modeling cookies and the baking thereof with various structs and methods. Throughout this lab, we will make three structs: one to represent raw cookie dough, another to represent a cookie, and another to represent an oven. We'll then write some programs to experiment with converting dough into baked cookies, allowing Rust's ownership model to guide us along.

This lab is very exploratory and the purpose is to get hands on experience with Rust's ownership model and borrowing, so there's not a ton of coding or tests to turn in. However, that doesn't mean you should leave it to the last minute!

The Dough type

Make a Dough struct containing a flavor field of type String. Then implement the following methods:

• new, which takes in a &str and returns a Dough. An example for how to do this can be found below.
• Some reasonable constructors for popular flavors. For example, a chocolate_chip method which creates a Dough that's chocolate chip flavored without having to pass in the string "Chocolate chip" manually.

As a reminder for how to implement methods, here's how you might implement and use the new method:

#![allow(unused)]
fn main() {
// Dough definition omitted

impl Dough {
    fn new(flavor: &str) -> Dough {
        Dough {
            flavor: flavor.to_string(),
        }
    }

    // other methods here...
}
}

Unlike the other methods we've seen in class, this one has no &self parameter, but instead has a &str parameter. This allows us to create Dough values with the following code:

#![allow(unused)]
fn main() {
let oatmeal_raisin = Dough::new("Oatmeal raisin");
}

Here, we put the name of the type, Dough, followed by ::, followed by the method name, so Dough::new. Note that the name new in Rust isn't special: it's just a convention for methods that return an instance of the type. If we wanted, we could have called it with_flavor or something else.

The Cookie type

Next, make a Cookie struct. It should have a field flavor of type String, and a field crispiness of type u32. Then implement the following methods:

• new, which should takes an owned Dough and returns a Cookie with the same flavor and a crispiness of 0. Remember, if Dough has ownership of the flavor String, you can transfer ownership to the Cookie to avoid allocating another String.
• is_raw, which borrows self and returns a bool. This will be used to check if the Cookie is raw, i.e. the crispiness is 0.
• is_overcooked, which borrows self and returns a bool. This will be used to check if the Cookie is overcooked, which we'll say is when crispiness > 4.
• eat, which will take ownership of the Cookie and prints a message that changes based on the flavor and if the cookie is overcooked, raw, or somewhere in between, which you can use the methods you already created to test for. Feel free to be creative and have fun here; we certainly did in testing this lab. (Idea: maybe chocolate chip cookies taste best nice and gooey with a crispiness of 1, but snickerdoodles are best crispier with a crispiness of 4.)

The Oven type

Make an Oven struct with a field tray of type Vec<Cookie>. Then implement the following methods:

• new, which takes no arguments and returns an Oven with the tray field initialized to an empty Vec using Vec::new().
• add_raw_cookie, which borrows self (mutably or immutably?) and takes an owned Dough, converts it into a Cookie with Cookie::new, and adds it to the tray field using .push(x).
• wait, which borrows self (mutably or immutably?) and loops through the tray using .iter_mut() to increment the crispiness of all Cookies by 1. Look at the linked documentation for examples on how to use.
• inspect_cookie, which immutably borrows self and takes an index of type usize and returns a reference to the Cookie in the tray at index using &self.tray[index].
• remove_tray, which takes the owned Oven and returns a Vec<Cookie>.

Note that after you remove a Vec<Cookie> from the Oven, you can use .remove(i) to get a Cookie from the vector at a particular index, or you can just iterate through each Cookie with:

#![allow(unused)]
fn main() {
for cookie in oven.remove_tray() {
    // do stuff with the cookie
}
}

Questionnaire

The last part of this assignment is to fill our several short response questions in questionnaire.md.

Feedback

Please fill out this short feedback form.

Submitting

Once you're finished, be sure to verify that:

• cargo fmt has been run
• cargo clippy passes
• cargo test passes

Then you can push your changes with the usual: git add ., git commit -m "your message", and git push.

Congratulations on finishing!

Week 3

Class 3: Enums

This week, we'll be exploring tagged unions, which are a common language feature among functional languages and are part of Rust under the name of enums. They allow us to define a type that can take on one of multiple possible variants.

Basic syntax

Let's start with a demonstration by defining a Shape enum that can be one of two possible variants: a Rectangle or a Circle:

enum Shape {
    Circle,
    Rectangle,
}

We can then use a match expression to writing code that branches based on which variant an enum is:

#![allow(unused)]
fn main() {
enum Shape {
    Circle,
    Rectangle,
}
let circle = Shape::Circle;

match circle {
    Shape::Circle => println!("Circle"),
    Shape::Rectangle => println!("Rectangle"),
}
}

Just like if else expressions, match is also an expression, and since expressions must always evaluate to something, the compiler will check that all possible things to match on are present. For example, the following won't compile because values of type Shape could also be Shape::Rectangle.

#![allow(unused)]
fn main() {
enum Shape {
    Circle,
    Rectangle,
}
let circle: Shape = Shape::Circle;

let what_shape: String = match circle {
    Shape::Circle => "circle".to_string(),
};
}

This is an example of Rust's strong type system, since it won't allow our program to compile unless all our bases are covered.

One strategy to overcome this is to add what's called a wildcard pattern, which is just an identifier or _. This is the equivalent of the else branch in a conditional expression, and it serves to match on anything that didn't get matched on above:

#![allow(unused)]
fn main() {
enum Shape {
    Circle,
    Rectangle,
}
let circle: Shape = Shape::Circle;

let what_shape: String = match circle {
    Shape::Circle => "circle".to_string(),
    _ => "not a circle".to_string(),
};
}

Stateful variants

We can also add data to each variant, either by making it a tuple variant or a struct variant. Tuple variants (like Circle below) have unnamed fields, while struct variants (like Rectangle below) have named fields. Although they have different syntax in some places, the actual semantics is essentially the same for tuple and struct variants.

enum Shape {
    Circle(f64),
    Rectangle {
        width: f64,
        height: f64,
    }
}

Now when matching, we can put identifiers to bind the data to:

#![allow(unused)]
fn main() {
enum Shape {
    Circle(f64),
    Rectangle {
        width: f64,
        height: f64,
    }
}
let circle = Shape::Circle(5.0);

match circle {
    Shape::Circle(radius) => {
        println!("Circle with radius {radius}");
    }
    Shape::Rectangle { width: w, height: h } => {
        println!("Rectangle that is {w} by {h}");
    }
}
}

When we say width: w, we're saying "assign the width field to a variable named w". However, Rust has some nice syntactic sugar to make this easier for us: if we instead wanted to assign the width field to a variable of the same name (so width), we can just write width once. For example, we could have written Shape::Rectangle { width, height } => ..., which would assign the width and height fields of the Rectangle variant to variables width and height respectively.

Enums are types

Lastly, it's important to remember that just like structs, enums are also just a type, meaning we can have different Shape variants be passed into functions expecting a Shape:

#![allow(unused)]
fn main() {
enum Shape {
    Circle {
        radius: f32,
    }
    Rectangle {
        width: f32,
        height: f32,
    },
}
let rect: Shape = Shape::Rectangle { width: 3.0, height: 4.0 };

let circle: Shape = Shape::Circle(5.0);

fn takes_shape(shape: Shape) {
    // do stuff
}

// valid
takes_shape(rect);
// also valid
takes_shape(circle);
}

Building on this idea further, we can also have impl blocks for enums, just like we did for structs in lab 2:

#![allow(unused)]
fn main() {
enum Shape {
    Circle(f64),
    Rectangle {
        width: f64,
        height: f64,
    },
}
impl Shape {
    fn area(&self) -> f64 {
        match self {
            Shape::Rectangle { width, height } => {
                width * height
            }
            Shape::Circle(radius) => {
                3.141 * radius * radius
            }
        }
    }
}

let circle: Shape = Shape::Circle(5.0);
let area = circle.area();
println!("Area: {}", area);
}

Now that we've seen how to use enums, let's look at how enums can be used to solve some major problems in software.

See Chapter 6.2 for more details.

Problem 1: Nullability

The concept of a "null" value is prolific across many languages:

• Python None
• C/C++ NULL/nullptr
• Java null
• Go nil
• and many more.

In his 2009 presentation “Null References: The Billion Dollar Mistake,” Tony Hoare, the inventor of null, has this to say:

I call it my billion-dollar mistake. At that time, I was designing the first comprehensive type system for references in an object-oriented language. My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn’t resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.

Consider all the times you've segfaulted or had a NullPointerException and had to put a check in. What if there was some way we could say "hey, this value might be null" and "here's a value, I guarantee you that it's not null" via the type system? A way where we are forced to check potentially null values, and where there is no need to check for guaranteed non null values?

Solution 1: Option

In Rust, we can do this using the Option enum, which is defined in the standard library.

It's definition is extremely simple:

#![allow(unused)]
fn main() {
// The `T` is a generic type, ignore for now.
enum Option<T> {
    // no value
    None,
    // just the `T` value
    Some(T),
}
}

To get an understanding for how it works, consider the following example:

#![allow(unused)]
fn main() {
fn divide(numerator: f32, denominator: f32) -> Option<f32> {
    // Check for div by zero
    if denominator == 0.0 {
        // We can't divide by zero, no float can be returned

        // The Rust prelude brings `Option::None` and `Option::Some` into scope,
        // so we can just say `None`
        None
    } else {
        // denominator is nonzero, we can do the operation
        let quotient: f32 = numerator / denominator;

        // Can't just return `quotient` because it's `f32`
        // Instead, we need to return an `Option<f32>` containing the quotient,
        // which we can do by wrapping `quotient` with `Some`.
        Some(quotient)
    }
}

let quotient: Option<f32> = divide(10.0, 2.0);
println!("{:?}", quotient);

let zero_div: Option<f32> = divide(10.0, 0.0);
println!("{:?}", zero_div);
}

This is great because for functions that might return nothing, we can make them return an Option. Without this check, a divide-by-zero will cause the program to panic, which is Rust terminology for crash with a report of what went wrong (depending on your configuration).

Even better, it means that Rust can guarantee that all references are valid. So if you have a greet function:

#![allow(unused)]
fn main() {
fn greet(name: &str) {
    println!("Hello, {}", name);
}

greet("Quinn");
}

You never have to worry about name being a null pointer. If you want nullability, use an Option instead:

#![allow(unused)]
fn main() {
fn greet(maybe_name: Option<&str>) {
    match maybe_name {
        Some(name) => println!("Hello, {}", name),
        None => println!("Who's there?"),
    }
}

greet(Some("William"));
greet(None);
}

Since enum variants must be checked via a match statement before access, this enforces that all optional values are checked, and that no non-optional values have to be checked because everything is encoded as part of the type system. Neat!

See Chapter 6.1 for more details.

Problem 2: Error handling

On a somewhat related topic, how do different languages go about error handling?

Error flags

The C programming language has a special errno, which is a static int that is set by certain syscalls. This can only carry a single integer though which has to be decoded by a special strerror function:

#include <stdio.h>
#include <errno.h>
#include <string.h>

// in static memory
extern int errno;

int main () {
    FILE *fp = fopen("file.txt", "r"); // writes to `errno` on failure
    if (fp == NULL) {
        printf("Value of errno: %d\n", errno);
        printf("Error opening file: %s\n", strerror(errno));
    } else {
        fclose(fp);
    }

    return 0;
}

Value of errno: 2
Error opening file: No such file or directory

This method is extremely minimal and fast, but clearly not scalable to larger programs. Furthermore, this does nothing to ensure that programmers actually check the errors.

Errors as exceptions

Although C++ has exceptions, they have a long and controversial history. At one point, functions could be marked with the throw annotation:

void do_something(int a, int b) throw (std::exception) {
    // ...
}

... but this has been deprecated since C++ 11, and we encourage you to take a quick look at A pragmatic Look at Exception Specifications which describes why at a high level. One of the first sentences summarizes the current state of C++ exceptions nicely:

The idea behind exception specifications is easy to understand: In a C++ program, unless otherwise specified, any function might conceivably emit any type of exception.

This obviously generates unnecessary machine code, and so C++ also has the noexcept keyword annotation which can enforce at compile time that a function won't throw anything. But for functions that are fallible, C++ programmers must live with the extra bloat of error handling, or come up with their own efficient way to support fallibility that is not a language feature.

Similarly to C++, Java uses exceptions to handle errors, except that skipping the throws annotation makes the program crash if an exception is unhandled instead of propagating it. This is better because it means that any exceptions that don't terminate the program must be annotated in the function signature, making it clear on what may need to be handled when calling a function, and the JVM can probably optimize this fairly well. However, it doesn't bring any new ideas to the table and is therefore mostly uninteresting to us.

The strength in the Java and C++ solutions is brevity: propagating errors is extremely simple because it is the default behavior. Perhaps a little too simple.

int do_operation(int i, float f, std::string s) {
    int a = foo(i, f); // does this throw?
    int b = bar(a, s); // this might throw too
    return more_stuff(b); // any of these could throw and you wouldn't know.
}

Is do_operation fallible, and if so, which function call might throw an exception? It's impossible to tell without consulting documentation or source code.

Errors as return values

Languages like Go switch things up by solving many of the previous problems we've seen. Instead of having exceptions be a special language feature, they are treated as ordinary values that a function may return. For example, the standard library function for opening a file has the following signature:

func Open(name string) (*File, error)

On success, it could return something like (handle, nil). On failure, it could return (nil, some_error). This means calling fallible functions in Go usually looks like the following:

f, err := os.Open("filename.ext")
if err != nil {
    // do something in the error case
}
// proceed as normal

This provides several advantages:

• Less special language features, errors are values just like everything else.
• Fallible functions are clear by their type signature.
• Arbitrary data may be passed through errors.

The biggest downside is error propagation, which is now the opposite of implicit:

if err != nil {
    return nil, err
}

Even though this gives you maximum control over how to handle an error, the fact is that 95% of the time most programs just instantly propagate using the above code snippet, and this verbosity can quickly inflate the amount of code in a function.

On top of this, what would it mean for a function to return both a value and an error? This scenario doesn't make sense, but there's nothing stopping you from doing it, unlike how C++ and Java either return a value or throw an exception.

Solution 2: Result

Rust solves this problem with the Result enum, which is defined like the following:

#![allow(unused)]
fn main() {
enum Result<T, E> {
    // success
    Ok(T),
    // failure
    Err(E),
}
}

Note that, similar to how Go does fallibility, these variants have no special meaning to the compiler for the most part; they are just ordinary types, unlike how Java and C++ require exceptions to extend some base exception class. Since this approach is so general, there are some clever things we can do. For example, the standard library's binary_search function, which searches a sorted array for a particular value. Here is a simplified version of the function signature:

fn binary_search<T>(slice: &[T], x: T) -> Result<usize, usize>
{ Ok(0) }

The documentation explains the strange return type:

If the value is found then Result::Ok is returned, containing the index of the matching element. (...) If the value is not found then Result::Err is returned, containing the index where a matching element could be inserted while maintaining sorted order.

A more traditional example, however, is a simplified version of Rust's standard library function for reading a file to a string:

use std::io;
fn read_to_string(path: &str) -> Result<String, io::Error>
{ Ok(String::new()) }

A program might use this function like the following:

use std::{fs, io};

fn main() -> Result<(), io::Error> {
    let string: String = match fs::read_to_string("names.txt") {
        Ok(string) => string,
        Err(err) => return Err(err),
    };

    println!("{}", string);
    Ok(())
}

Woah woah woah. This is worse than Go's error propagation!

Yeah, but we have purity! Look how elegantly we're able to express that the function either succeeds or fails!

...

Propagation with the ? operator

The ? operator allows for error propagation without the verbose syntax. Check this out:

use std::{fs, io};

// the `Ok` value is `()`, the unit type.
fn main() -> Result<(), io::Error> {
    let string: String = fs::read_to_string("names.txt")?; // <-- here

    println!("{}", string);
    Ok(())
}

Adding ? after an expression that has type Result in a function that returns a Result will extract the Ok value, or short circuit from the function and return the Err value. It's (nearly) equivalent to writing the following instead:

use std::{fs, io};

// the `Ok` value is `()`, the unit type.
fn main() -> Result<(), io::Error> {
    let string: String = match fs::read_to_string("names.txt") {
        Ok(string) => string,
        Err(e) return Err(e),
    };

    println!("{}", string);
    Ok(())
}

This also works for function that return Option:

fn sum_first_two(vec: &[i32]) -> Option<i32> {
    // `.get(x)` might return `None` if the vec is empty.
    // If either of these `.get(x)`s fail, the function will
    // short circuit and return `None`.
    Some(vec.get(0)? + vec.get(1)?)
}

See Chapter 9.2 for more details.

Errors as enums

This leads us to another prime example of where Rust enums shine: error values themselves. As we saw in earlier, Java requires the throws keyword followed by a sequence of exception types to denote that one of those exceptions can be thrown. The key words here are "one of", as this encapsulates an enum perfectly. It's extremely common to define Rust enums that represent kinds of things that can go wrong in a program.

For example, say we want to read a file, parse an i32 from the contents, and then return that. There are two things that could go wrong:

• We might have trouble reading from the file.
• The contents might not be parsable as an i32.

Let's define our error type first:

#![allow(unused)]
fn main() {
use std::{io, num};

enum Error {
    Io(io::Error),
    Parse(num::ParseIntError),
}
}

Here, we've chosen to store the io::Error and num::ParseIntError.

Then, we can write our function:

#![allow(unused)]
fn main() {
enum Error {
    Io(io::Error),
    Parse(num::ParseIntError),
}
use std::{fs, io, num};

fn open_and_parse_file(file: &str) -> Result<i32, Error> {
    let contents = match fs::read_to_string(file) {
        Ok(contents) => contents,
        Err(err) => return Err(Error::Io(err)),
    };

    let num = match contents.trim().parse() {
        Ok(num) => num,
        Err(err) => return Err(Error::Parse(err)),
    }

    Ok(num)
}
}

Hey, what happened to using the ? operator?

The ? operator (continued)

In this example, fs::read_to_string would propagate io::Error, and str::parse would propagate ParseIntError. The issue is that our function expects the Err variant of the Result to be our custom Error type, which is neither of these.

The ? operator won't work because these are all different types, but we can tell it how to convert from these types into our Error type using the From trait. Traits are the topic for next week so we won't explore too much into how they work now, but the core idea is that they allow us to define interfaces, and the From trait will allow us to tell the compiler how to convert from these other types into our Error type.

For converting an io::Error to our own Error, we can add the following:

#![allow(unused)]
fn main() {
use std::{io, num};
enum Error {
    Io(io::Error),
    Parse(num::ParseIntError),
}
// Implement the trait telling Rust how to get `Error` from an `io::Error`.
impl From<io::Error> for Error {
    // This trait has 1 method that we're required to implement
    fn from(value: io::Error) -> Error {
        // We made the `Io` variant to represent `io::Error`s, so
        // we can just create one here. Easy!
        Error::Io(value)
    }
}

impl From<num::ParseIntError> for Error {
    fn from(value: num::ParseIntError) -> Error {
        Error::Parse(value)
    }
}
}

Now we can write the function again, but cleanly:

#![allow(unused)]
fn main() {
use std::{fs, io, num};
enum Error {
    Io(io::Error),
    ParseInt,
}
impl From<io::Error> for Error {
    fn from(value: io::Error) -> Error {
        Error::Io(value)
    }
}
impl From<num::ParseIntError> for Error {
    fn from(_value: ParseIntError) -> Error {
        Error::ParseInt
    }
}
fn open_and_parse_file(file: &str) -> Result<i32, Error> {
    let content = fs::read_to_string(file)?;

    let num = content.trim().parse()?;

    Ok(num)
}
}

See the documentation for more examples.

These tools allow Rust programmers to both be extremely precise while also having the choice between explicit error handling and minimal error propagation, and will be helpful to understand for completing the next lab.

~

Summary

• Rust enums are types that can be one of several variants which may contain different types.
• We use match statements to determine which variant an enum is.
• The problem of null pointers and references can be solved with enums like Option<T>.
• Different languages have their own ways to mark a function as "fallible", Rust has the Result<T, E> enum.
• The ? operator can be used to propagate errors with minimal syntactic overhead.
• Enums are excellent for representing possible kinds of errors.
• The ? operator can perform implicit conversion using the From<T> trait.

See Chapter 6 and Chapter 9.2 for more details.

Lab 3: Parsing Frames

Due February 28, 11:59pm

As stated on the course page, one of the goals of the course is to build a chat server, and that starts now. We will spend the remaining labs building up small components that we will piece together at the end.

Networking applications such as chat servers rely on being able to communicate between computers, and this happens by sending bytes between them, which are just streams of 1s and 0s. By themselves, bytes are meaningless, but if both computers agree on a protocol for how the bytes are structured, then they can derive meaning from them and communicate. An analogy to this is how making monkey noises isn't an effective mode of communication, but speaking a shared language is.

In this lab, we'll be (partially) implementing a protocol which will allow us to parse unstructured bytes into flexible higher-level structures that will be much easier to work with later on.

Since bytes are unstructured, however, there are many things that might go wrong during parsing. It might tell us to read in the next integer represented in ASCII digits, but then we find a non-digit character. Or it might tell us to read the next 100 bytes as an array of bytes, but there's only 50. As such, one of the focuses of this lab is to practice writing robust, fallible code with useful error types.

Grading Rubric

• Code is formatted properly using cargo fmt: 5%
• Code passes cargo clippy without warnings: 10%
• Code passes our tests: 60%
• Responses in questionnaire.md: 25%

Learning Objectives

• Practice defining and using enum types.
• Write fallible code with elegant error handling.

Table of Contents

• Defining the Frame type: How to define Frame.
• The RESP protocol: Specification for how you should be parsing frames from bytes.
• Implementing methods for the Frame type: The "what, why, and how" for methods on Frame.
• The ParseError type: Error enum for this lab.
• Cursor helper functions: How to get bytes from &mut Cursor<&[u8]>.
• Get started with a match expression: Start here if you're stuck!
• Helpful conversions: How to get Vec<u8> and String from &[u8].
• Testing your code: Reminder to write tests.
• Questionnaire: Answer some brief questions about Rust.
• Feedback: Give us your feedback!
• Submitting: How to submit your lab.

Defining the Frame type

We want to communicate with structured messages, and will do this via the RESP protocol. In short, RESP is an easily parsable, human readable message format. RESP allows for sending various kinds of messages called frames, which can be one of the following variants:

• Simple UTF-8 strings (String)
• Error messages as UTF-8 strings (String)
• 64-bit signed integers (i64)
• Bulk strings, which are arbitrary bytes (Vec<u8>)
• Vectors of other frames (Vec<Frame>)

Since frames can take on any one of these variants, it's the perfect candidate for declaring as an enum, which is the first task. Begin by opening your project and filling in the variants for the Frame type, one for each bullet point above. Make sure that each variant can carry the data associated with it, e.g. you should have a Simple(String) variant.

Filename: src/frame.rs

pub enum Frame {
    Simple(String),
    // todo: fill in variants
}

The RESP protocol

Since we're building a basic networking application from the ground up, we're going to write the parsing code that will convert raw bytes into Frame objects that we can use later on.

This section will tell you how each variant is encoded in bytes.

• RESP Simple Strings:
  • Leading byte is "+", followed by a string that cannot contain a \r or \n character, and terminated by \r\n.
  • Example: "I love Rust 🦀" becomes "+I love Rust 🦀\r\n".
• RESP Errors:
  • Same as simple strings, but the leading byte is "-".
  • Example: "NOT FOUND" becomes "-NOT FOUND\r\n".
• RESP Integers:
  • Leading byte is ":", followed by a \r\n-terminated string representing an integer.
  • Example: 123 becomes ":123\r\n".
• RESP Bulk Strings:
  • Leading byte is "$", followed by the number of bytes composing the string in ASCII digits (a prefixed length), followed by \r\n, followed by the actual bytes, followed by a final \r\n.
  • Example: "ƒoo" becomes "$4\r\nƒoo\r\n", since "ƒ" is encoded in 2 bytes and "oo" is 2 bytes, one for each "o". Yes, characters can be variable length encoded. No, we won't be diving into this rabbit hole.
• RESP Arrays:
  • Leading byte is "*", followed by the number of frames in the array in ASCII digits, followed by \r\n, followed by the encodings of the frames within the array.
  • Example: ["hello", 100] becomes "*2\r\n+hello\r\n:100\r\n".

When you start writing your Frame::check method (defined below), you should be consulting this section so you know how to properly parse data from the bytes.

Implementing methods for the Frame type

The main functionality we'll be implementing in this lab is parsing Frame values from a slice of bytes (&[u8]), as described by the protocol. Instead of reading straight from a &[u8], however, we'll read from a &mut Cursor<&[u8]> instead. Let's break down this type signature.

The &mut part is self explanatory- we're getting a mutable reference to a Cursor<&[u8]>. The Cursor part is a type provided by the standard library as std::io::Cursor, and it looks like this:

struct Cursor<T> {
    inner: T,
    pos: u64,
}

So when we have Cursor<&[u8]>, we're essentially just pairing a byte slice, &[u8], with a position, u64. This means that it can keep track of how much we've read so far without changing anything about the underlying buffer. Don't worry too much about the syntax or the name of the type for now, we'll be exploring it more next week.

One of the benefits of Rust is that you can view source code from the documentation. If you're curious about how Cursor works, you can see its documentation here, and even see its source code by pressing the orange source button on the right side.

Next, we need a way to take a &mut Cursor<&[u8]>, read from it, and return a Frame to us (or some kind of error). One thing to know about communicating over a network is that even if a chunk of bytes is sent all at once, the receiving computer might not get them all at the same time.

To combat this, we'll create two methods, Frame::check and Frame::decode, where the former checks that a Frame can be parsed without actually parsing it, and the ladder actually parses the bytes and returns a Frame. To see why we might want this, consider the following sequence of bytes (with whitespace added for readability):

*3\r\n
+GET\r\n
+Potato\r\n

This is a frame that is an array of three inner frames, but only two are present so far. If we eagerly create a Frame::Array with an empty Vec and push two Frame::Simples to it, we'll find out that we don't yet have data and return an error, meaning our String and Vec allocations will have been for nothing.

Thus, having distinct Frame::check and Frame::decode methods will allow us to cheaply check that there is enough data without having to perform potentially wasted heap allocations if there turns out not to be.

Let's briefly walk through how these methods should be implemented.

Frame::check

Frame::check ensures that the bytes are encoded as a valid frame as described below. First, it checks that the first byte matches one of the expected bytes (+, -, :, $, *), and performs more checks depending on the kind:

• Simple strings and errors have a terminating \r\n, and have been checked as valid UTF-8. To get you started, you could implement this branch as just

  let slice: &[u8] = line(src)?;
  let _validated: &str = from_utf8(slice)?;
  // validated, don't need to do anything else now

  This should work because you should already have use std::str::from_utf8; at the top.

• Integers can be parsed as an i64 and have a terminating \r\n.

• Bulk strings have a valid prefix length and that there are that many bytes remaining, followed by \r\n.

• Arrays have a valid prefix length, n, and that n frames afterwards can also be checked with Frame::check. This can be accomplished by looping n times and recursively calling Frame::check in each iteration. For example, if we have this sequence of bytes in our &mut Cursor<&[u8]> (the ^ is where the cursor position is)

  *2\r\n+Hello\r\n+world\r\n
  ^
  

  Then calling Frame::check on it will first detect that it's an array of 2 elements, while advancing the cursor forward past the first line:

  *2\r\n+Hello\r\n+world\r\n
        ^
  

  It'll then loop twice, where the first iteration will check and advance past the first inner frame (the "Hello" simple string):

  *2\r\n+Hello\r\n+world\r\n
                  ^
  

  and the second iteration will check and advance past the second and last inner frame (the "world" simple string):

  *2\r\n+Hello\r\n+world\r\n
                            ^
  

  If any of the checks on the inner n frames returns an Err, propogate it up with the ? operator.

  Note that because we're using a Cursor, each call to Frame::check will advance the position of the cursor, so we don't have to manually track where in the buffer we are.

On success, it returns Ok(()), which just tells us "hey, this operation succeeded but I don't have anything to give you." On failure, it returns Err(ParseError). The ParseError type, which will be defined by you, is explained more here.

Frame::decode

Frame::decode is nearly identical to Frame::check, except it creates the Frame objects as it goes instead of just throwing out bytes after validation.

For example, if you branch for simple frames in encode looked like this:

let slice: &[u8] = line(src)?;
let _validated: &str = from_utf8(slice)?;

Then you would want this instead in the decode method:

let slice: &[u8] = line(src)?;
let validated: &str = from_utf8(slice)?;
Ok(Frame::Simple(validated.to_string()))

You could also be clever and write it in one big expression if you feel comfortable with that too:

Ok(Frame::Simple(from_utf8(line(src)?)?.to_string()))

Another change would be that instead of just checking frames in a loop in the array variant, you'd actually want to be pushing the successfully parsed frames to a Vec as you go.

Starter code

The outline for these functions is provided in the same file:

Filename: src/frame.rs

impl Frame {
    pub fn check(src: &mut Cursor<&[u8]>) -> Result<(), ParseError> {
        todo!("implement Frame::check")
    }

    pub fn decode(src: &mut Cursor<&[u8]>) -> Result<Self, ParseError> {
        todo!("implement Frame::decode")
    }
}

It is your task to implement these functions according to the RESP protocol and with proper error handling.

Speaking of error handling...

The ParseError type

When writing up the Frame::check and Frame::decode methods, there are several things that can go awry. For example, one of the cursor helper functions might return a CursorError, or the first byte of a frame might not be one of the expected bytes. In these cases, you'll want to add a variant to the ParseError type defined at the bottom of src/error.rs.

To get you started, two possible things that might go wrong are one of the cursor functions might return a CursorError, or the first byte of a frame might not be one of the expected bytes as shown in the last branch above.

pub enum ParseError {
    Cursor(CursorError),
    FrameType(u8),
    // add more
}

For a refresher on errors as enums and how to make your errors work with the ? operator, read back on our lecture notes in 3.1. Enums.

Cursor helper functions

For help working with the Cursor type, we've created a small library with utility functions which you can see in Cargo.toml if you're interested.

Near the top of src/frame.rs, you should see the following:

use cursor::{byte, integer, line, size, slice};

To learn how to use these, navigate inside your project directory and enter the following command:

cargo doc --open

This will generate documentation for your Rust project in the form of HTML, JS, and CSS, and then open the corresponding files as a web page on your default browser. Under the Crates section on the left-hand side, click on cursor, and you should be brought to the documentation which will explain how each method works.

Get started with a match expression

We've seen how match expressions can be used to extract the value of an enum, but they can also be used like switch statements in C/C++.

Here's an example that you can run for yourself:

fn main() {
    // We can specify a byte by prefixing a char literal with `b`
    // Try changing the byte!
    let byte: u8 = b'+';

    match byte {
        b'+' => {
            // all good!
            println!("Plus!");
        }
        b'-' => {
            // all good!
            println!("Minus!");
        }
        x => {
            // hey, this isn't right and we can't proceed properly from here
            println!("None of the expected bytes matched, found: {}", x);
        }
    }
}

You may find this useful when determining which kind of frame is encoded based off the first byte read.

If you're ever at a point in code where you're thinking "hey, this isn't right and we can't proceed properly from here", than it's probably an error and you should add a variant for the particular scenario on the ParseError type so you can return it.

Helpful conversions

Converting &[u8] to Vec<u8>

You can use the .to_vec() method to create an owned Vec<u8> from a borrowed slice, &[u8].

#![allow(unused)]
fn main() {
let line: &[u8] = &[1, 2, 3];
let bulk: Vec<u8> = line.to_vec();
}

Converting &[u8] to String

You can use the std::str::from_utf8 function to get from &[u8] to &str (without any copying!), and then use .to_string() to get from &str to String.

fn main() -> Result<(), std::str::Utf8Error> {
use std::str::from_utf8;

let line: &[u8] = &[240, 159, 166, 128];
let borrowed_string: &str = from_utf8(line)?;
let owned_string: String = borrowed_string.to_string();

println!("Secret message: {}", owned_string);
Ok(())
}

Testing your code

In lab 1, we had the following at the top of our lib.rs file:

#[cfg(test)]
mod tests;

This created a tests module inside of our project, which was accessible in tests.rs.

For this lab, however, we'll be writing tests at the bottom of src/frame.rs. Near the bottom, you'll find the following:

Filename: src/frame.rs

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

    #[test]
    fn test_check() {
        // Use the following syntax to get your `Cursor<&[u8]>` buffers.
        let mut src = Cursor::new(":100\r\n".as_bytes());

        // `.is_ok()` returns true if `Result` is the `Ok` variant.
        assert!(Frame::check(&mut src).is_ok());
    }
}

This is essentially equivalent to the above (with a sample test though), but the contents of the tests module can go in the block here instead of in another file. Write some tests to check that your code works!

One of the reasons we might want to write tests in the same file is if we're building up a larger framework and don't want test files everywhere, but want to keep our tests close to what we're testing for clarity.

Questionnaire

The last part of this assignment is to fill our several short response questions. Since we'll be reusing this repository for the rest of the course, you'll find the questionnaire in questionnaire/lab3.md this time. In future labs, we'll push other questionnaires to this directory, so be sure to not add other files or move files around.

Feedback

Please make sure that each member fills out this short feedback form individually.

Submitting

Once you're finished, be sure to verify that:

• cargo fmt has been run
• cargo clippy passes
• cargo test passes

Then you can push your changes with the usual: git add ., git commit -m "your message", and git push.

However, there's one final step: Git tags.

In the industry, tags are how software is officially released. Essentially, it creates an immutable copy of the repository and all the contents and makes it fancy so people can download and use it. We'll be using it to denote stages of completion on this project, so one for each of the remaining labs.

The benefit of this is that when you create a git tag, we can look at it to see your repository at that moment in time. This means that if you're working on lab 4 and your repository is in an incomplete state that potentially doesn't compile, we can still look back at the point where you created a tag for this lab and see your working code from that point in time. It will also help us know exactly what code you want to submit- that is, if you need an extension, we'll know not to grade your code until you create a git tag.

So, when you're sure you're completely finished with the lab, start by creating a tag:

git tag lab3

And then push it to your repository:

git push origin lab3

Congratulations on finishing!

Week 4

Class 4: Generics and Traits

Let's take a step back and revisit a concept that we've been brushing over for some time now: generic types.

Thus far, we've used Vec<T>, Option<T>, and Result<T, E>, which are all generic types, but we haven't really talked about how they work. If you remember from CS35, these are somewhat analogous to C++ template types, which allow for type polymorphism.

Generics

We'll begin with a simple motivating example, where we'll define our own container type, Either, which is either a string message or an integer:

pub enum Either {
    Left(String),
    Right(i32),
}

impl Either {
    pub fn into_left(self) -> Option<String> {
        match self {
            Either::Left(string) => Some(string),
            Either::Right(_) => None,
        }
    }
}

If we implemented a lot more methods for this type (into_right, flip, ...), then it could be pretty handy! However, what if we wanted an Either for Strings/f32s? One strategy is to create another enum, but that would require having to rewrite every method that we've implemented.

Instead, we can use type parameters on the Either type to make it generic over any two types.

To do this, we can replace the String and i32 with type parameters which looks like the following:

pub enum Either<L, R> {
    Left(L),
    Right(R),
}

Here, we've added <L, R> after the name of the type, which introduces two new type parameters called L and R, sometimes referred to as generic types. We could have named them anything we wanted, but one letter names are common for simple types.

Just like how we can describe a vector of bytes as Vec<u8>, or a return value as Result<u8, Error>, we can describe of Either<L, R> by plugging in types for L and R:

enum Either<L, R> {
    Left(L),
    Right(R),
}
// The `L` and `R` types are replaced with `String` and `i32` respectively for these.
let message: Either<String, i32> = Either::Left("Hello, world!".to_string());
let integer: Either<String, i32> = Either::Right(5);

Adding type parameters also requires changing how the impl block looks:

#![allow(unused)]
fn main() {
enum Either<L, R> {
    Left(L),
    Right(R),
}
impl<L, R> Either<L, R> {
//  ^^^^^^ We need this now
    pub fn into_left(self) -> Option<L> { // <- was `Option<String>` before
        match self {
            Either::Left(left) => Some(left),
            Either::Right(_right) => None,
        }
    }

    // other methods here
}
}

The type parameters need to first be introduced into scope with the <L, R> syntax following the impl keyword. If you prefer thinking in math language, you can read this as "For any types L and R, we will define Either<L, R> to have the following methods."

Note that impl blocks aren't the only place that type parameters can be defined. Both functions and methods can also introduce their own generic types parameters as well. Let's add a replace_left method to Either<L, R> that can replace the left item with a value of a different type:

#![allow(unused)]
fn main() {
enum Either<L, R> {
    Left(L),
    Right(R),
}
impl<L, R> Either<L, R> {
    // ...

    fn replace_left<T>(self, new_left: T) -> Either<T, R> {
        match self {
            Either::Left(_) => Either::Left(new_left),
            Either::Right(right) => Either::Right(right),
        }
    }
}
}

Mathematically, we can think of this as saying "For any types L and R, and for any type T, we define replace_left to be a function that maps an Either<L, R> and a T to a Either<T, R>.

And here's an example of how it could be used:

enum Either<L, R> {
    Left(L),
    Right(R),
}
impl<L, R> Either<L, R> {
    fn replace_left<T>(self, new_left: T) -> Either<T, R> {
        match self {
            Either::Left(_) => Either::Left(new_left),
            Either::Right(right) => Either::Right(right),
        }
    }
}
let string_or_int: Either<String, i32> = Either::Left("Hello".to_string());

// We can call `.replace_left(...)` with any type we want, here's with `f32`
let float_or_int: Either<f32, i32> = string_or_int.replace_left(5.0);

For a thorough walkthrough of generics, check out Chapter 10.1 of the Rust Book.

Traits

Unlike most object-oriented languages which you've probably worked with in the past, Rust has no concept of super classes and extending other classes. Instead, Rust has traits to define shared behavior between different types.

Let's look at an example from Chapter 10.2 of the Rust Book:

trait Summary {
    fn summarize(&self) -> String;
}

Here, we've defined a trait called Summary with one function, summarize, which has no implementation. There are many kinds of things we might want to summarize like tweets and books, so let's create types for those:

struct Tweet {
    username: String,
    content: String,
    likes: u32,
}

struct Book {
    author: String,
    title: String,
    content: String,
}

If we want to write a function that can take something that can be summarized like a Tweet or a Book, we can make them both implement the Summary trait:

trait Summary {
    fn summarize(&self) -> String;
}
struct Tweet {
    username: String,
    content: String,
    likes: u32,
}

struct Book {
    author: String,
    title: String,
    content: String,
}
impl Summary for Tweet {
    fn summarize(&self) -> String {
        format!("@{}: {}", self.username, self.content)
    }
}

impl Summary for Book {
    fn summarize(&self) -> String {
        format!("{}, by {}", self.title, self.author)
    }
}

Here, we use the format! macro which is like println! except it writes the contents to a new String.

At this point, we have Tweet and Book, which both implement the Summary trait.

When the Summary trait is in scope (either defined or brought in with use), we're able to call .summarize() on values whose types implement Summary as if it were a method directly on the type:

#![allow(unused)]
fn main() {
trait Summary {
    fn summarize(&self) -> String;
}
struct Tweet {
    username: String,
    content: String,
    likes: u32,
}

struct Book {
    author: String,
    title: String,
    content: String,
}
impl Summary for Tweet {
    fn summarize(&self) -> String {
        format!("@{}: {}", self.username, self.content)
    }
}
impl Summary for Book {
    fn summarize(&self) -> String {
        format!("{}, by {}", self.title, self.author)
    }
}
// `Summary` definition, `Tweet` definition, and trait implementation hidden

let tweet = Tweet {
    username: "swarthmore".to_string(),
    content: "Only 12 more days until spring semester classes begin! We can't wait to welcome our students back to campus.".to_string(),
    likes: 35,
};

// Call like an ordinary method
println!("Summary of the tweet: {}", tweet.summarize());
}

However, this isn't very exciting by itself. The real abstraction in traits comes from what are called trait bounds, which is where you have a function or struct/enum with a generic type that must implement some set of traits.

For example, we can make a describe function that takes any type T where T implements Summarize:

#![allow(unused)]
fn main() {
trait Summary {
    fn summarize(&self) -> String;
}
struct Tweet {
    username: String,
    content: String,
    likes: u32,
}

struct Book {
    author: String,
    title: String,
    content: String,
}
impl Summary for Tweet {
    fn summarize(&self) -> String {
        format!("@{}: {}", self.username, self.content)
    }
}
impl Summary for Book {
    fn summarize(&self) -> String {
        format!("{}, by {}", self.title, self.author)
    }
}
// Takes a generic `T`, but _only_ if the T type implements `Summary`!
fn describe<T: Summary>(text: T) {
    // `text` can do anything that `Summary` can do because of the trait bound
    println!("Here's a short summary of the text: {}", text.summarize());
}

let tweet = Tweet {
    username: "swarthmore".to_string(),
    content: "Only 12 more days until spring semester classes begin! We can't wait to welcome our students back to campus.".to_string(),
    likes: 35,
};

let book = Book {
    author: "Mara Bos".to_string(),
    title: "Atomics and Locks".to_string(),
    content: "-- omitted -".to_string(),
};

describe(tweet);
describe(book);
}

Because the describe function requires that T implements Summary, it means that the function can use any methods provided by Summary on values of type T.

For trait bounds that are more verbose, it can be inconvenient to fit everything in the angle brackets. Rust provides an alternative but equivalent method of specifying bounds with where clauses. For example, we could define the describe function with them instead:

fn describe<T>(text: T)
where
    T: Summary,
{
    // `text` can do anything that `Summary` can do because of the trait bound
    println!("Here's a short summary of the text: {}", text.summarize());
}

Okay, but what happens if we try to pass in a value whose type doesn't implement Summarize?

#![allow(unused)]
fn main() {
trait Summary {
    fn summarize(&self) -> String;
}
// Doesn't implement `Summary`
struct NetflixShow {
    year: u32,
    title: String,
    genres: Vec<String>,
}

// Takes a generic `T`, but _only_ if the T type implements `Summary`!
fn describe<T: Summary>(text: T) {
    // `text` can do anything that `Summary` can do because of the trait bound
    println!("Here's a short summary of the text: {}", text.summarize());
}

let movie = NetflixShow {
    year: 2022,
    title: "Stranger Things".to_string(),
    genres: vec![
        "Sci-Fi TV".to_string(),
        "Teen TV Shows".to_string(),
        "TV Horror".to_string(),
    ],
};

describe(movie);
}

The compiler complains with "the trait bound NetflixShow: Summary is not satisfied". The code will not compile because it is incorrect.

For a thorough walkthrough of traits, check out Chapter 10.2 of the Rust Book.

Generics and Zero-cost Abstraction

Zero-cost abstraction is the notion that you only pay in runtime performance for what you need, and that abstractions compile down into machine code that is equivalent or better to whatever you can write by hand.

When people talk about Rust's "zero-cost abstractions", they're usually talking about its generics in one way or another, and Chapter 10.1 of the Rust Book explains this extremely well. The following is a slightly reworded version of what you'll find there:

You might be wondering whether there is a runtime cost when using generic type parameters. The good news is that using generic types won't make your program run any slower than it would with concrete types.

Rust accomplishes this by performing monomorphization of the code using generics at compile time. Monomorphization is the process of turning generic code into specific code by filling in the concrete types that are used when compiled. In this process, the compiler looks at all the places where generic code is called and generates code for the concrete types the generic code is called with.

Let’s look at how this works by using the standard library’s generic Option<T> enum:

fn main() {
    let integer: Option<i32> = Some(5);
    let float: Option<f32> = Some(5.0);
}

When Rust compiles this code, it performs monomorphization. During that process, the compiler reads the values that have been used in Option<T> instances and identifies two kinds of Option<T>: one is i32 and the other is f64. As such, it expands the generic definition of Option<T> into two definitions specialized to i32 and f64, thereby replacing the generic definition with the specific ones.

The monomorphized version of the code looks similar to the following (the compiler uses different names than what we’re using here for illustration):

enum Option_i32 {
    Some(i32),
    None,
}

enum Option_f64 {
    Some(f64),
    None,
}

fn main() {
    let integer = Option_i32::Some(5);
    let float = Option_f64::Some(5.0);
}

The generic Option<T> is replaced with the specific definitions created by the compiler. Because Rust compiles generic code into code that specifies the type in each instance, we pay no runtime cost for using generics. When the code runs, it performs just as it would if we had duplicated each definition by hand. The process of monomorphization makes Rust’s generics extremely efficient at runtime.

The process of monomorphization comes with several advantages and disadvantages.

Advantages

The biggest advantage is that it means no heap allocations are required because the size of everything is known. We can store types with generics entirely on the stack, or really wherever we want in memory; it's as if we had defined them by hand, giving us maximum control over where things go in memory.

Another advantage is that it allows the compiler to apply clever optimizations. For example, on most types T, Option<T> will be represented in memory as a discriminant byte (the "tag" in "tagged union") and space for the T value. This means the type Option<u8> will take 2 bytes: one for the tag and one for the u8. We can illustrate this using the std::mem::size_of function:

#![allow(unused)]
fn main() {
println!("{}", std::mem::size_of::<Option<u8>>());
}

However, Rust has a special understanding of pointer types like references, where it knows that they can never be null. This means it can optimize types like Option<&Tweet> to use the null pointer to represent the None variant, eliminating the necessity for an extra tag byte altogether.

#![allow(unused)]
fn main() {
struct Tweet {
    username: String,
    content: String,
    likes: u32,
}

println!("{}", std::mem::size_of::<&Tweet>());
println!("{}", std::mem::size_of::<Option<&Tweet>>());
}

This is called the null pointer optimization, or NPO, and is only possible because monomorphization creates different types which the compiler can then optimize individually.

Disadvantages

Monomorphization is not without sacrifice, though. Programs that heavily use generic types can greatly slow down the compiler, and monomorphization can quickly inflate compiled binary sizes if many copies of the same types and functions are created. This isn't really an issue with small generic types like Option, Result, and Vec, but a good first suspect for slow compile times is when the names of generic types begin to span multiple lines of your screen, since the compiler is doing a lot of work on these types.

Here's an example of a problematic type from a blog post by fasterthanlime:

TraitPredicate(<
  futures::future::Map<warp::hyper::Server<warp::hyper::server::conn::AddrIncoming, warp::hyper::service::make::MakeServiceFn<[closure@warp::Server<warp::log::internal::WithLog<[closure@warp::log::{closure#0}], warp::filter::or::Or<warp::filter::or::Or<warp::filter::or::Or<warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::get::{closure#0}]>::{closure#0}]>, warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filters::any::Any, warp::path::Exact<warp::path::internal::Opaque<serve::serve::{closure#0}::__StaticPath>>>, warp::path::Exact<warp::path::internal::Opaque<serve::serve::{closure#0}::__StaticPath>>>, warp::filter::FilterFn<[closure@warp::path::end::{closure#0}]>>>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:231:14: 231:92]>, warp::filter::and_then::AndThen<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::get::{closure#0}]>::{closure#0}]>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:235:19: 235:61]>>, warp::filter::and_then::AndThen<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::head::{closure#0}]>::{closure#0}]>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:239:19: 239:61]>>, warp::filter::and_then::AndThen<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::post::{closure#0}]>::{closure#0}]>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:243:19: 243:62]>>>>::bind_ephemeral<std::net::SocketAddr>::{closure#1}::{closure#0}]>>, [closure@warp::Server<warp::log::internal::WithLog<[closure@warp::log::{closure#0}], warp::filter::or::Or<warp::filter::or::Or<warp::filter::or::Or<warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::get::{closure#0}]>::{closure#0}]>, warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filters::any::Any, warp::path::Exact<warp::path::internal::Opaque<serve::serve::{closure#0}::__StaticPath>>>, warp::path::Exact<warp::path::internal::Opaque<serve::serve::{closure#0}::__StaticPath>>>, warp::filter::FilterFn<[closure@warp::path::end::{closure#0}]>>>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:231:14: 231:92]>, warp::filter::and_then::AndThen<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::get::{closure#0}]>::{closure#0}]>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:235:19: 235:61]>>, warp::filter::and_then::AndThen<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::head::{closure#0}]>::{closure#0}]>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:239:19: 239:61]>>, warp::filter::and_then::AndThen<warp::filter::and::And<warp::filter::FilterFn<[closure@warp::filters::method::method_is<[closure@warp::post::{closure#0}]>::{closure#0}]>, warp::filter::map::Map<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::and::And<warp::filter::map::Map<warp::filters::any::Any, [closure@src/serve/mod.rs:158:38: 158:66]>, warp::filter::FilterFn<[closure@warp::path::full::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::query::raw::{closure#0}], futures::future::Ready<std::result::Result<std::string::String, warp::Rejection>>>::{closure#0}]>, [closure@src/serve/mod.rs:165:26: 168:18]>>>, warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::header::optional<std::string::String>::{closure#0}], futures::future::Ready<std::result::Result<std::option::Option<std::string::String>, warp::Rejection>>>::{closure#0}]>>, warp::filter::unify::Unify<warp::filter::recover::Recover<warp::filter::and_then::AndThen<warp::filter::FilterFn<[closure@warp::filter::filter_fn_one<[closure@warp::body::body::{closure#0}], futures::future::Ready<std::result::Result<warp::hyper::Body, warp::Rejection>>>::{closure#0}]>, [closure@warp::body::bytes::{closure#0}]>, [closure@src/serve/mod.rs:174:26: 180:18]>>>, [closure@src/serve/mod.rs:184:13: 207:14]>>, [closure@src/serve/mod.rs:243:19: 243:62]>>>>::bind_ephemeral<std::net::SocketAddr>::{closure#0}]>
as
  warp::Future
>)

Yes, that is one type.

These problems are not without workarounds though, and this is discussed near the end of this page.

Motivation for traits: type classes

The ability to define shared method interfaces for types via traits in Rust is extremely versatile, and helps us solve many questions that most programming languages must confront:

• Operator overloading
• Interfaces
• Type markers

Operator overloading

Most programming languages have operators: special syntax recognized by the language as syntactic sugar for a function call. These can range from math operators like + and - to operators for displaying something in string form. For the ladder, Python has def __str__(self), Java has String toString(), and C++ has std::ostream& operator>>(std::istream&).

To allow for custom types in Rust to work with these operators, the standard library provides traits for each overloadable operator. For example, we can make a Point type that implements the std::fmt::Display trait, allowing it to be printed with {} in print statements:

#![allow(unused)]
fn main() {
use std::fmt;

struct Point {
    x: i32,
    y: i32,
}

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

let origin = Point { x: 0, y: 0 };

println!("The point is: {}", origin);
}

We can even use our knowledge of traits and generics to make Point generic over any type T, and conditionally implement Display if and only if T does:

#![allow(unused)]
fn main() {
use std::fmt;

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

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

// These values can be displayed
let point_int = Point { x: 3, y: 4 };
let point_float = Point { x: 3.14, y: 2.73 };

println!("The point is: {}", point_int);
println!("The point is: {}", point_float);

struct NotDisplay(i32);

// This one can't be printed because `NotDisplay` doesn't implement `Display`
let point_not_display = Point { x: NotDisplay(4), y: NotDisplay(5) };
}

The traits for the math operators like + and - can be found here, and traits for comparison operators like < and == can be found here.

Interfaces

Another challenge is writing programs that require a type to conform to a particular interface, but the function doesn't particularly care about the exact details of the type.

As an example, we might want to make a function that takes an iterator, but we don't care if it's backed by an array, a linked list, or some type that generates values each time one is requested. We can do this with the Iterator trait.

As described above in the Traits section, this is the most trivial problem that traits can solve, as they allow us to apply bounds to generic types so we can interface with them.

Type markers

We spent week 2 talking about ownership and borrowing, but have you noticed that you never have to worry about ownership of primitive values like i32 or bool?

How come this example compiles:

#![allow(unused)]
fn main() {
fn take_owned<T>(value: T) {
    // Do nothing with it
}

// Make a variable
let x = 5;

// Pass ownership to the function
take_owned(x);

// This is fine here...
println!("{}", x);
}

But this example won't?

#![allow(unused)]
fn main() {
fn take_owned<T>(value: T) {
    // Do nothing with it
}

// Make a variable
let x = "An owned string".to_string();

// Pass ownership to the function
take_owned(x);

// Borrow after move, compiler error!
println!("{}", x);
}

The only difference is that x is an i32 in the first example, and is a String in the second example.

Fortunately for us, the compiler error points us in the right direction: String does not implement the Copy trait. The Copy trait is a special marker trait that has no methods, but is instead special to the compiler. Most types in Rust have what are called "move semantics", meaning that when they pass ownership to something like a function, their bytes are memcpy'd into the new location in memory, and the compiler enforces that we're not allowed to interact with the old bytes anymore. When a type implements Copy, however, it gets "copy semantics", which tells the compiler that the old bytes are still valid to use after a move.

This makes sense for simple types that are semantically all in one place like primitive types, since creating a bitwise copy shouldn't invalidate the original. However, it doesn't make sense for types that aren't all in one place like a String, which is a length, capacity, and a pointer to a heap allocation. If it were Copy, then you could create two String values that both point to the same heap allocation, which will cause a use-after-free when one of them goes out of scope or reallocates.

Instead, creating a duplicate of a String requires calling .clone(), which is a method provided by the Clone trait. This will create a new String with its very own heap allocation that contains a copy of the original string's heap allocation, allowing them to both own their own allocations and prevent memory issues.

#![allow(unused)]
fn main() {
let a = "I love Rust!".to_string();
let b = a.clone();

// Each string has its own allocation now
println!("{:?}", a.as_ptr());
println!("{:?}", b.as_ptr());
}

Other significant markers are the Send and Sync traits, which are used for marking types that can be sent across threads and types that can be shared across threads respectively. These marker traits are part of the cornerstones for Rust's fantastic concurrency model.

~

Summary

• Generics allow for defining types and functions that work on values of different types.
• Traits are like interfaces that types can implement.
• Types and functions can use trait bounds on generic types to restrict which types can be used.
• Monomorphization is the process where the compiler looks at every usage of a generic and turns it into its own copy of the function or type.
• Monomorphization can lead to more optimization, but slower compile times in some extreme cases.
• Traits allow for operator overloading, shared interfaces, and type markers for the compiler like Copy.

Lab 4: Readers and Writers

Due March 14, 11:59pm

Now that we've talked a bit about traits and generics, it's time to apply them to what we've been working on! We will do this in two parts.

First, we will define the FrameReader type, which will be a special type that combines the Frame::check and Frame::decode methods we previously wrote, a buffer, and a type that implements Read. This will ultimately help us abstract over the process of getting bytes from the reader and decoding them into Frame values.

Then, we'll define the WriteFrame trait and create a blanket implementation for it for all Write types, allowing us to write Frame values to any type that can have bytes written to it.

Grading Rubric

• Code is formatted properly using cargo fmt: 5%
• Code passes cargo clippy without warnings: 25%
• Code passes our tests: 70%

Learning Objectives

• Practice using generic types with trait bounds.
• Practice implementing traits.

Table of Contents

• Defining the FrameReader type: The "why and how" for a custom type to read frames.
• The ReadError type: The error type for this lab.
• Defining methods for FrameReader: How to implement FrameReader::read_frame.
• Defining the WriteFrame trait: Practice defining a trait for things that can have frames written to them.
• Implementing WriteFrame for all Write types: Making WriteFrame useful.
• Testing your code: Reminder to write tests.
• Feedback: Provide us with your feedback!
• Submitting: Most important step.

Defining the FrameReader type

The FrameReader type that we are going to define will abstract over the difficulties of getting Frame values from some source of bytes, and will provide one method (besides the constructor): read_frame.

When we wrote both Frame::check and Frame::decode methods, we were relying on someone providing it with a &mut Cursor<&[u8]> as an input. This means that somewhere, we need to store a contiguous buffer of bytes (to get a &[u8]), and this buffer will be owned by the FrameReader type. Then, we need to be able to:

• fill up that buffer with as much data as possible from some data source,
• create a &mut Cursor<&[u8]> that views into the buffer,
• call Frame::check (and then Frame::decode on success),
• and finally, return the Frame if everything else was successful.

We'll put these steps into a function called FrameReader::read_frame, which will provide us with a nice abstraction for future labs.

1. The Read trait

But before we can do this, we let's rewind for a second: where are these bytes coming from? Eventually, we'll want to be reading bytes from a std::net::TcpStream, but we'll also want to test our code on simpler types that are capable of being read from, like a Vec<u8>. Fortunately, the standard library provides the std::io::Read trait for us.

Before we dive too deep, remember: a trait (like Read) isn't a thing you can pass around in your program. The only things that exist at runtime are structs, enums, primitive types, and functions. When we say that a function takes a Read value, or a struct contains a Read field, we're saying that it takes some concrete type like T (struct, enum, primitive, sometimes even function) that implements the Read trait. This is why generics and traits are so tightly coupled in Rust: generics and trait bounds allow us to represent much of the same logic that super classes in object-oriented languages can.

Types that implement Read must implement its Read::read method, which allows us to pass it a buffer that it can write to (&mut [u8]), and returns the number of bytes written or an error. This means that for all types T: Read, we can pass them a &mut [u8] and it will fill it with bytes in whatever way makes sense for that type.

Here's an example from the book, demonstrating how std::io::File implements Read:

use std::io;
use std::io::prelude::*;
use std::fs::File;

fn main() -> io::Result<()> {
    let mut f = File::open("foo.txt")?;
    let mut buffer = [0; 10];

    // read up to 10 bytes
    let n = f.read(&mut buffer[..])?;

    println!("The bytes: {:?}", &buffer[..n]);
    Ok(())
}

This is very handy, but careful inspection of the example shows some lack of flexibility: they had to manage their own buffer, the array of 10 bytes. Furthermore, it's not very ergonomic to use, since the return value is the number of bytes overwritten, which then has to be taken into account. We do not want to have to manage this all manually.

Normally, we'd use a type like std::io::BufReader, which is provided by the standard library. It works by wrapping a Read value and implementing Read itself, and uses an internal buffer to make small, infrequent reads much more efficient in some cases. However, it's not suitable for our case because although we can get access to the internal buffer as a &[u8], there's no public API that allows for requesting to read more data unless the buffer is empty, which won't suit our use cases. For this reason, we will be creating our own FrameReader type that is very similar to BufReader.

2. The ReadBuf type

For this lab, we're providing the ReadBuf type which will act as the buffer that we're storing the bytes in.

use std::io;
use std::io::prelude::*;
use std::fs::File;
use readbuf::ReadBuf; // <- new!

fn main() -> io::Result<()> {
    let mut f = File::open("foo.txt")?;
    let mut buffer = ReadBuf::with_capacity(1024);

    // read up to 1024 bytes
    buffer.read(&mut f)?;

    // ReadBuf internally tracks how many bytes are read
    // and will give you exactly what was read
    println!("The bytes: {:?}", buffer.buf());
    Ok(())
}

To use it, you'll first have to add our mini library as a dependency. Open you Cargo.toml file and add the following line under [dependencies]:

readbuf = { git = "https://github.com/QnnOkabayashi/rust-course-utils" }

Overall, your Cargo.toml file should look like this:

Filename: Cargo.toml

[package]
name = "server"
version = "0.1.0"
edition = "2021"

[dependencies]
cursor = { git = "https://github.com/QnnOkabayashi/rust-course-utils" }
readbuf = { git = "https://github.com/QnnOkabayashi/rust-course-utils" }

Then, navigate to src/rw.rs (rw stands for read-write) and add the following:

Filename: src/rw.rs

use readbuf::ReadBuf;

To learn how to use ReadBuf, enter the following command:

cargo doc --open

This will generate documentation for your Rust project in the form of HTML, JS, and CSS, and then open the corresponding files as a web page on your default browser. Under the "Crates" section on the right, click on "readbuf", and then on the "ReadBuf" struct to find its documentation and see how each method works.

3. Putting it all together

Putting these together, define the FrameReader type as a public struct with two fields:

1. A reader of type T, where T: Read.
2. A ReadBuf value that will act as our buffer.

Hint: it may help to look at the implementation of the BufReader type, which can be found by following that link and clicking the orange source button on the right. Your struct definition should look nearly identical.

The ReadError type

Before we write methods for the FrameReader type, let's define yet another error type.

Woohoo!

To do this, we'll consider what can possibly fail. Firstly, we know that we'll be using our Frame::check and Frame::decode methods from last week, and those can both error with ParseError, so we'll need a variant for that. Secondly, we'll also be using the ReadBuf type, whose .read(...) method can error with std::io::Error.

If we have use std::io; at the top, then we can just refer to it as io::Error instead of the fully qualified path name, std::io::Error.

Therefore, we'll need an error type that can represent either of these two cases, which we can define as the following in our src/error.rs file:

Filename: src/error.rs

#![allow(unused)]
fn main() {
use cursor::CursorError;
use std::{io, str::Utf8Error};

// ParseError implementation details omitted...

#[derive(Debug)]
pub enum ReadError {
    Parse(ParseError),
    Io(io::Error),
}
}

The Parse variant is very straight-forward: it represents any errors that could occur when calling Frame::check or Frame::decode

On the other hand, the Io variant stores an std::io::Error, which is actually doing a lot of heavy lifting here. Internally, it stores an std::io::ErrorKind, which is an enum that has 40 variants.

For example, in the case that ReadBuf::read tries to read and there aren't any more bytes to read, it will return an io::Error with an io::ErrorKind::WriteZero internally, because no more bytes is an error. Or later on, when we try to perform non blocking reads, it could return an error with io::ErrorKind::WouldBlock. All of these scenarios are encapsulated in the ReadError::Io variant.

Your task here is to paste this ReadError type definition into your src/error.rs file, and add the proper impl From blocks for both Parse and Io variants. Here's the one for Parse to get you started:

impl From<ParseError> for ReadError {
    fn from(err: ParseError) -> Self {
        ReadError::Parse(err)
    }
}

Defining methods for FrameReader

Now that we have our ReadError type sorted out, let's write some methods for FrameReader. There are two methods we want: new and read_frame.

#![allow(unused)]
fn main() {
struct FrameReader<R>(R);
struct Frame;
struct ReadError;
use std::io::Read;

impl<R: Read> FrameReader<R> {
    pub fn new(reader: R) -> FrameReader<R> {
        todo!("implement FrameReader::new")
    }

    pub fn read_frame(&mut self) -> Result<Frame, ReadError> {
        todo!("implement FrameReader::read_frame")
    }
}
}

The new method should be straightforward: using the provided reader, create a FrameReader using it and a new ReadBuf, which you can get using ReadBuf::new().

The read_frame method is slightly more complicated, but has a very linear control flow. At a high level, it starts by reading in bytes to the FrameReader's internal buffer (a ReadBuf), then checking the contents of the buffer, then decoding from the buffer, and finally telling the buffer to discard the read bytes so they're not read again, before returning the decoded Frame.

Let's go into more detail on these steps (each number corresponds to one line of code in our implementation):

1. Data is read from the selfs reader into selfs ReadBuf field using the .read(...) method, and any errors are propagated.
2. A new Cursor is created, wrapping the buffer of selfs ReadBuf field (see its documentation for how to get the buffer as a &[u8]).
3. We call Frame::check, passing it a mutable reference to the Cursor we just created, and propagate any errors that might occur.
4. If no errors have been propagated thus far, then it must be the case that we have enough bytes to parse a Frame. Thus, we'll proceed by resetting the cursors position back to 0 using .set_position(0) on the cursor.
5. Now that our cursor is back at 0, we'll pass the cursor into Frame::decode to get our Frame, making sure to propagate any errors.
6. Then, we need to make sure that we don't accidentally read the same bytes again. Since Frame::decode advances the cursor to just past the end, we can figure out how many bytes were used by calling .position() on the cursor. Then, we can use .consume(len) on selfs ReadBuf, where len is the number of bytes (casted to a usize using len as usize) to make sure that calls to .buf() don't give us those same bytes again.
7. Finally, we can return the Frame, making sure to wrap it in Ok(_) since the method returns a Result.

For an example on how to test this, see the testing section below.

Defining the WriteFrame trait

Next, we need a way to write Frames as bytes. In the spirit of using traits, we'll abstract this behavior by defining a WriteFrame trait with one method, write_frame which takes a &mut self and a &Frame, and returns an io::Result<()>, and has no default implementation.

This means that all types T that implement WriteFrame are capable of being passed a &Frame and encoding it somewhere in themselves (&mut T).

Define the WriteFrame trait in src/rw.rs beneath your impl block for FrameReader.

For a reminder on how to write a trait with a method and no default implementation, see Chapter 4.1: Traits and Generics.

Implementing WriteFrame for all Write types

When most Rust programmers learn about traits, it's usually easiest to think about implementing traits on types one at a time. However, we can actually perform "blanket implementations", where we implement a trait for all types that satisfy some trait bounds.

An example of this is that the std::string::ToString trait is implemented for all types that are also std::fmt::Display, and works by creating a new String, formatting the value into it with Display::fmt, and then returning the string. The source code for this can be found here.

This is convenient when the functionality that our trait requires can be provided by another trait. In our case, this other trait is std::io::Write, which is a trait for types that can be written to. Pairing this trait with the write!() macro allows us to do formatted writes to Write types as easily as using println!(), making any type that implements Write a perfect candidate to implement WriteFrame on.

To start, add the following to to top of src/rw.rs:

Filename: src/rw.rs

use std::io::Write;

Then, we'll implement the WriteFrame trait for all types W where W: Write.

For the body of the write_frame method, we'll pretty much do the opposite of Frame::decode, and start by matching on the variants of Frame. We can then use the write!() macro to "print" bytes to the writer, making sure to follow the protocol.

For example, if we're working with a Frame that is the simple string variant, we could use the following:

write!(self, "+{}\r\n", the_string)?;

On the other hand, your implementation for writing bulk strings have to write several parts, and that would look like this (assuming bulk is &Vec<u8> or &[u8]):

write!(self, "${}\r\n", bulk.len())?;
self.write_all(bulk)?;
write!(self, "\r\n")?;

For array variants, you'll start by writing the length, and then you can loop through each Frame and call self.write_frame(frame)? so nested Frames are recursively written.

You can look back on the lab 3 instructions for a reminder on how each frame variant is encoded.

Testing your code

Similar to the last lab, you'll write your tests in src/rw.rs in its own tests module. To do this, add the following at the end of your src/rw.rs file:

Filename: src/rw.rs:

// other stuff omitted...

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

    // Here's an example test
    #[test]
    fn test_read_frame() {
        let data = "+Hello, world!\r\n".as_bytes();

        // &[u8] implements `Read`
        let mut reader = FrameReader::new(data);
        let result = reader.read_frame().unwrap();
        assert_eq!(result, Frame::Simple("Hello, world!".to_string()));
    }
}

Questionnaire

No questionnaire this week. Enjoy break!

Feedback

Please make sure that each member fills out this short feedback form individually.

Submitting

Once you're finished, be sure to verify that:

• cargo fmt has been run
• cargo clippy passes
• cargo test passes

Then you can push your changes with the usual: git add ., git commit -m "your message", and git push.

When you're ready to submit your finished lab, do the following:

git tag lab4

And then push it to your repository:

git push origin lab4

Congratulations on finishing!

Week 5

Class 5: Lifetimes and Aliasing

Lifetimes

The lifetime of something is the duration of a program's execution during which it exists. That is, the lifetime of a value begins when it is first defined, and ends when it goes out of scope and is inaccessible by any part of the program. Managing lifetimes is incredibly important, since accessing an object outside its lifetime means that the object is not in a valid state and you will get undefined behavior. One of the goals of Rust is to ensure that it is impossible to access an object outside of its lifetime.

C++

Mismanaging lifetimes is a serious issue in real code. Louis Brandy gave an excellent talk, "Curiously Recurring C++ Bugs at Facebook" which, from (12:48 - 17:06) discusses a specific bug that happens all the time at Facebook that has to do with lifetimes. He even comments at 16:24 that

This is a really hard problem to fix (...) But at some point the language has to fix it and I don't know if it can or will.

Louis Brandy's broken C++ code is the following.

const string &get_default(const map<string, string> &map,
                          const string &key,
                          const string &dflt)
{
    auto pos = map.find(key);
    // If value was found, return that, otherwise return `dflt` (default)
    return (pos != map.end() ? pos->second : dflt);
}

The problem with this code is that the return value is a reference to a value that will either live as long as the value associated with the key, or only as long as the default, and it is quite common for the default to not live very long. The lifetimes of temporaries in C++ are complicated and, I believe, have changed since this talk was given in 2017 making it a little harder to break this function, but it is still very easily broken.

Consider this program utilizing this broken get_default.

#include <iostream>
#include <map>
#include <string>

using namespace std;

// same `get_default` as before
const string &get_default(const map<string, string> &map,
                          const string &key,
                          const string &dflt)
{
    auto pos = map.find(key);
    return (pos != map.end() ? pos->second : dflt);
}

const string &ref_to_temp(const map<string, string> &map) {
    string dflt = "DEFAULT"; // Lifetime of `dflt` begins here

    // If "Hello" isn't a key in `map`, returns a reference to `dflt`
    // which lives in this stack frame.
    return get_default(map, "Hello", dflt);
} // Lifetime of `dflt` ends here since the variable was on the stack

int main() {
    map<string, string> map;
    map["hello"] = "world";
    auto &v = ref_to_temp(map); // `uh-oh`, "Hello" isn't in `map`
    cout << v << '\n';
}

Surprisingly, on my computer at least, it prints out "EFAULT" rather than "DEFAULT" like we would expect, which is definitely a sign something wrong is going on. However, if we add an extra print statement to main as shown below, it suddenly prints out a ton of garbage.

int main() {
    map<string, string> map;
    map["hello"] = "world";
    auto &v = ref_to_temp(map);
    cout << v << '\n';
    cout << max(1, 2) << '\n'; // messes up the previous stack frame
    cout << v << '\n';
}

The problem with this isn't so much that this code is broken (it is in Rust, too), but that the compiler doesn't tell us it is broken, even turning on -Wall and -Wextra. Though, weirdly, g++, but not clang++, is able to find the error when optimizations are turned on for some reason.

Rust

What happens then if we translate this code to Rust?

#![allow(unused)]
fn main() {
use std::collections::HashMap;
fn get_default(map: &HashMap<String, String>, key: &String, default: &String) -> &String {
    match map.get(key) {
        Some(val) => val,
        None => default,
    }
}
}

We get a compiler error!

   Compiling playground v0.0.1 (/playground)
error[E0106]: missing lifetime specifier
 --> src/main.rs:4:82
  |
4 | fn get_default(map: &HashMap<String, String>, key: &String, default: &String) -> &String {
  |                     ------------------------       -------           -------     ^ expected named lifetime parameter
  |
  = help: this function's return type contains a borrowed value, but the signature does not say whether it is borrowed from `map`, `key`, or `default`
help: consider introducing a named lifetime parameter
  |
4 | fn get_default<'a>(map: &'a HashMap<String, String>, key: &'a String, default: &'a String) -> &'a String {
  |               ++++       ++                                ++                   ++             ++

For more information about this error, try `rustc --explain E0106`.
error: could not compile `playground` due to previous error

Not only that, but it's a very helpful compiler error. The most important line of this error message is this.

this function's return type contains a borrowed value, but the signature does not say whether it is borrowed from map, key, or default

Rust can't possible know until runtime if the return value is borrowed from map, key, or default. And this is important because the reference will become garbage once whatever it is borrowing from gets dropped, which might happen at different times. Handily for us, rustc suggests a fix, but to understand it we first need to learn how Rust models lifetimes.

Lifetimes in Rust

This explanation of lifetimes is mostly just a summary of parts of Chapter 10.3 of the Rust Book. If you want more details, we encourage you to read this section.

Consider the following broken code.

#![allow(unused)]
fn main() {
{
    let r; // `r` allocated here (not allowed to use it until it is assigned)
    {
        let x = 5; // `x` allocated here
        r = &x;
    } // `x` dropped here
    println!("{}", r);
} // `r` dropped here
}

This doesn't compile, since r can't outlive what it's borrowing from. But how was Rust able to tell? Every reference in Rust is given a lifetime, which is an indication of how long the reference is valid. Rust assigns lifetimes as shown below.

#![allow(unused)]
fn main() {
{
    let r;                // ---------+-- 'a
                          //          |
    {                     //          |
        let x = 5;        // -+-- 'b  |
        r = &x;           //  |       |
    }                     // -+       |
                          //          |
    println!("r: {}", r); //          |
}                         // ---------+
}

For this particular example, we'll call these two scopes 'a and 'b (lifetimes in Rust are denoted by a single quote ' pronounced "tick" and a lowercase, usually single letter identifier). Here, the outer scope is given the lifetime 'a, while the inner scope is given the lifetime 'b. Then, when Rust tries to assign &x to r, it can't, because r has lifetime 'a and &x only has lifetime 'b, which is shorter than 'a. The reverse is totally fine, as shown below.

#![allow(unused)]
fn main() {
{
    let r = 5;                // ---------+-- 'a
                              //          |
    {                         //          |
        let x = &r;           // -+-- 'b  |
        println!("x: {}", x)  //  |       |
    }                         // -+       |
	                          //          |
}                             // ---------+
}

In short, it's ok for a reference to refer to something that lasts longer than it does, but it is not ok for a reference to last longer than the thing it refers to.

This gets into an interesting and quite niche topic called lifetime subtyping. Quinn has an excellent blog post here that heavily involves lifetime subtyping if you're curious.

get_default

So how can we use this information to fix get_default? Taking the compiler's suggestion, we can try the following, which indeed compiles.

#![allow(unused)]
fn main() {
use std::collections::HashMap;
fn get_default<'a>(map: &'a HashMap<String, String>, key: &'a String, default: &'a String) -> &'a String {
    match map.get(key) {
        Some(val) => val,
        None => default,
    }
}
}

The 'a in the angle brackets is a generic lifetime parameter. It is just some lifetime. The syntax &'a HashMap<String, String> means a reference of lifetime at least 'a to a HashMap<String, String>. Likewise, &'a String means a reference of lifetime at least 'a to a String. So we are saying that the return value lives at least as long as whichever lives the shortest between map, key, and default. This works, but isn't quite what we want. Consider the following code.

#![allow(unused)]
fn main() {
use std::collections::HashMap;
fn get_default<'a>(map: &'a HashMap<String, String>, key: &'a String, default: &'a String) -> &'a String {
   match map.get(key) {
       Some(val) => val,
       None => default,
   }
}
let default = "DEFAULT".to_string();
let mut map = HashMap::new();
map.insert("Hello".to_string(), "World".to_string());
let value;
{
    let key = "missing".to_string(); // `key` allocated here
    value = get_default(&map, &key, &default);
} // `key` dropped here
// `map`, `default`, and `value` still valid
println!("{}", value);
}

It doesn't compile, even though the return value is a reference to either something in map or default, both of which live long enough! However, we said that the return type was &'a String and key is also &'a String, meaning the return value has the same lifetime as key. However, we know that the return value will never be a reference to key, so we don't care about the lifetime of key. So let's remove the 'a from key's lifetime. This gives us the following, which compiles!

#![allow(unused)]
fn main() {
use std::collections::HashMap;
fn get_default<'a>(map: &'a HashMap<String, String>, key: &String, default: &'a String) -> &'a String {
    match map.get(key) {
        Some(val) => val,
        None => default,
    }
}
}

Indeed, the example that broke earlier now works too, since default and map have the same lifetime and the lifetime of key doesn't matter.

#![allow(unused)]
fn main() {
use std::collections::HashMap;
fn get_default<'a>(map: &'a HashMap<String, String>, key: &String, default: &'a String) -> &'a String {
    match map.get(key) {
        Some(val) => val,
        None => default,
    }
}

{
    let default = "DEFAULT".to_string();
    let mut map = HashMap::new();                         // ---------+-- 'a
    map.insert("Hello".to_string(), "World".to_string()); //          |
    let value;                                            //          |
    {                                                     //          |
        let key = "missing".to_string();                  // -+-- 'b  |
        value = get_default(&map, &key, &default);        //  |       |
    }                                                     // -+       |
    println!("{}", value);                                //          |
}                                                         // ---------+
}

Lifetimes in Structs

Lifetime annotations are also necessary when containing references in a struct rather than owning the type outright. Conceptually, the ideas are exactly the same as everything we've seen with lifetimes so far, just some new syntax. Consider the following struct.

#![allow(unused)]
fn main() {
struct StringHolder {
    string: &str
}
}

rustc immediately complains that we don't have a lifetime and also tells us how to fix it.

#![allow(unused)]
fn main() {
struct StringHolder<'a> {
    string: &'a str
}
}

When it comes to impl blocks or instantiating StringHolder, the syntax is just like with generics. While the ideas are the same as before, they are still tricky and require some thought. Consider the following code that fails to compile.

struct TwoStrings<'a> {
    str1_ref: &'a str,
    str2_ref: &'a str,
}

fn main() {
    let str1 = "Hello".to_string();
    let outer;                          // ----------+--'a
    {                                   //           |
        let str2 = "World".to_string(); // --+-- 'b  |
        let two_strings = TwoStrings {  //   |       |
            str1_ref: &str1,            //   |       |
            str2_ref: &str2,            //   |       |
        };                              //   |       |
        outer = two_strings.str1_ref;   //   |       |
    }                                   // --+       |
    println!("{}", outer);              //           |
}                                       // ----------+

Why does it fail to compile? Yes str2 doesn't live long enough, but str1 does which is all we are referencing. However, notice that the lifetimes of str1_ref and str2_ref are the same. In this example, since str2 only has lifetime 'b, both str1_ref and str2_ref have lifetime 'b since we said they had the same lifetime. This means that neither lives long enough for outer. In reality, we know that str1 lives longer than str2, so we can fix this by introducing another lifetime.

#![allow(unused)]
fn main() {
struct TwoStrings<'a, 'b> {
    str1_ref: &'a str,
    str2_ref: &'b str,
}
}

Now str1_ref and str2_ref don't need to have the same lifetime.

Conclusion

Lifetimes are tricky and a very deep subject. If you are doing any systems programming, you have to deal with lifetimes, whether you realize it or not. Like mutability, ownership, and typing, Rust just forces you to think about lifetimes and do the right thing and has your back. Most of the time you get in a fight with the borrow checker it is because you are trying to do something that you are used to from C or C++ that works, but is very dangerous and really shouldn't be done.

Aliasing

Imagine you are a C compiler and you see the following code.

#include <stdio.h>

int foo(int *a, int *b) {
  int x = *a;       // read *a from memory and assign it to `x`
  *b += 3;          // increment *b by 3
  return x + *a;    // read *a from memory again and add it to `x`
}

How might you optimize it? Well, reading from memory is slow, so for the final return statement, you can just double x rather than fetch what's at the address of a again. Putting this code in Godbolt with optimizations set to -O3, this is the assembly we get.

foo:
        mov     eax, DWORD PTR [rdi]    ; x = *a
        add     DWORD PTR [rsi], 3      ; *b += 3
        add     eax, DWORD PTR [rdi]    ; return x + *a
        ret

Recall that ; is used to start a comment in assembly.

Don't worry too much about the details of the assembly. The first line reads what's at the address of a into eax, i.e. x. The second line adds three to *b. Finally, the third line adds x to *a again, storing the result in eax. Note that it doesn't add eax to itself, or shift left or something. Rather it reads from memory again, despite optimizations being turned all the way up.

Doing the same thing with equivalent Rust code we find the following assembly.

#![allow(unused)]
fn main() {
pub fn foo(a: &i32, b: &mut i32) -> i32 {
    let x = *a;
    *b += 3;
    x + *a
}
}

example::foo:
        add     dword ptr [rsi], 3    // *b += 3
        mov     eax, dword ptr [rdi]  // x = *a
        add     eax, eax              // return x + x
        ret

This time, the first line adds 3 to *b, then the second line reads *a from memory into eax, and the final line adds eax to itself. Why was Rust able to perform this optimization but C couldn't?

What happens if we run the following code in C?

int x = 3;
foo(&x, &x);

Now a == b! When two pointers point to the same location in memory like this, the pointers are said to alias. When pointers alias, a lot of unexpected things can happen. In this case, the harmless *b += 3 will force us to read *a from memory again since it has changed! A lot of perfectly reasonable looking C functions break when pointers alias. Because of this edge case, compilers are prohibited from making further optimizations.

On the other hand, what happens in Rust when we try the same thing?

#![allow(unused)]
fn main() {
pub fn foo(a: &i32, b: &mut i32) -> i32 {
   let x = *a;
   *b += 3;
   x + *a
}
let mut x = 3;
foo(&x, &mut x);
}

error[E0502]: cannot borrow x as mutable because it is also borrowed as immutable

We get a compiler error, since we can't have a mutable reference and an immutable reference to the same object at the same time. Due to the aliasing rules in Rust, b can only ever be the only reference to b, since it's mutable. Thus if you have a mutable reference to something, it is impossible for you to break anything else. On the other hand, since a is an immutable reference, there cannot be any mutable references to a at the same time, meaning a can't possibly change. Thus it's safe to just grab the value once from memory.

Connection To Lifetimes

Let's look at a seemingly unrelated example of lifetimes gone wrong in C++.

#include <iostream>
#include <vector>

int main() {
  std::vector<int> x = {1, 2, 3};
  const auto &y = x[1]; // `y` is a *const* reference to `x[1]`

  std::cout << y << '\n'; // 2

  x.clear();

  x.push_back(5);
  x.push_back(5);

  std::cout << y << '\n'; // 5!?
}

Here we make a vector, then get a const reference to the first element and print it out, yielding 2 as expected. Then we clear the vector, leaving us with a dangling reference, and push 5 on to the vector twice and print out the const reference again, and this time get 5 (though this is undefined behavior, so don't be surprised if you get something different). This is a classic lifetime issue; the reference y outlived the object it refers to.

However, the error message we get in Rust for attempting this is not quite what we expect.

fn main() {
    let mut x = vec![1, 2, 3];
    let y = &x[1];

    println!("{}", y);

    x.clear();

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

error[E0502]: cannot borrow x as mutable because it is also borrowed as immutable

This was the exact error message we got when aliasing references. Recall that in x.clear(), clear is a function taking &mut self, meaning it takes a mutable reference to x. However y is also a reference to data owned by x, meaning these references alias and Rust's aliasing rules apply. Since y is an immutable reference to data owned by x, we can't borrow from it again mutably, which is why this fails to compile. So it turns out that the problem isn't actually a lifetimes issue, but an aliasing issue. Rust's reference aliasing constraints turn out to solve lifetime issues in addition to aliasing issues.

On the other hand, if, rather than mutate x to invalidate a reference, we move out of x, then we get a different error message.

fn main() {
    let x = vec![1, 2, 3];
    let v = &x[1];

    println!("{}", v);

    fn eat_vector(_x: Vec<i32>) {} // takes ownership of `_x` and immediately
	                               // drops its data
    eat_vector(x);

    println!("{}", v); // uh-oh, what is `v` referencing now?
}

error[E0505]: cannot move out of x because it is borrowed

When ownership is transferred, any references will be referring to the wrong location, so Rust prohibits moving out of anything with active references.

In particular, this means that removing the println!("{}", v) at the end of this example causes it to compile, as the reference v is never used after x is moved.

An interesting side effect of this is that when the new owner acquires ownership, there cannot be any references to it, so it's fine if the new owner is mutable even when the original wasn't. This means the following code works just fine, despite the fact that x is declared as immutable.

fn main() {
    let x = vec![1, 2, 3]; // `x` is immutable
    let v = &x[1];

    println!("{}", v);

    fn eat_vector(mut vec: Vec<i32>) { // takes ownership of `vec`,
	                                   // declaring it mutable
        vec.push(0);                   // mutate `vec`
        println!("ate {:?}", vec);
    }

    eat_vector(x); // "ate [1, 2, 3, 0]"
}

~

Summary

• Every object in Rust has a lifetime which measures how long the object lasts.
• References cannot have a longer lifetime than the object they refer to, which is enforced by the compiler.
• Just like with types, you can annotate lifetimes to help out rustc when things get ambiguous.
• Rust's aliasing rules, discussed in week 2, enable some powerful optimizations that C/C++ can't.
• Additionally, Rust's aliasing rules actually solve some lifetime issues.

Lab 5: Borrowing Frames

Due March 21, 11:59pm

Thus far, we've been been building up our higher level abstractions somewhat carelessly by copying a lot of data around. For example, decoding an array of two strings already requires three heap allocations for the Vec and two String values. But this is a systems programming language, and that means we get maximum control, and for the purpose of this lab, that is what we're after.

In this lab, we'll be using our knowledge of borrowing and lifetimes to make the Frame type borrow data instead of cloning bytes into its own heap allocations. This will involve several infrastructural changes to our existing code base.

Grading Rubric

• Code is formatted properly using cargo fmt: 5%
• Code passes cargo clippy without warnings: 10%
• Code passes our tests: 60%
• Responses in questionnaire.md: 25%

Table of Contents

• Updating the definition of Frame: Make Frame borrow instead of own.
• Updating the implementation of Frame: Fixing Frame::decode to borrow.
• Problems with FrameReader::read_frame: Solving lifetime issues with borrowing frames.
• Defining our own Guard type for FrameReader::read_frame: How to define a guard.
• Updating FrameReader::read_frame: Adding the guard to read_frame.
• One more Frame variant...: Add another frame variant to make lab 6 easier.
• Questionnaire: Short questionnaire.
• Testing your code: Reminder to write tests.
• Feedback: Provide us with your feedback!
• Submitting: Most important step.

Updating the definition of Frame

Next, we're going to update the Frame type to use borrowing types (&str, &[u8]) instead of owned allocations (String, Vec<u8>). As a reminder, &str and &[u8] are called slices: they are just pointers-length pairs that borrow from the owner of those bytes.

We'll start be revisiting the Frame type from week 3, which should look something like this:

Filename: src/frame.rs

pub enum Frame {
    Simple(String),
    Error(String),
    Integer(i64),
    Bulk(Vec<u8>),
    Array(Vec<Frame>),
}

In order to make it borrow its data instead of cloning bytes into its own owned heap allocations, we'll replace instances of String with &str and Vec<u8> with &[u8]. Make sure to introduce a lifetime to the Frame type so the compiler is happy. Also, consider why we can't make Array be a &'a [Self].

Updating the implementation of Frame

Running cargo check, we can see that we've now broken everything.

error[E0308]: mismatched types
  --> src/frame.rs:58:33
   |
   |                 Ok(Self::Simple(string))
   |                    ------------ ^^^^^^
   |                    |            |
   |                    |            expected `&str`, found struct `String`
   |                    |            help: consider borrowing here: `&string`
   |                    arguments to this enum variant are incorrect

Most of the time, the compiler is very helpful. That is not the case here, and demonstrates that although the compiler is very good at solving simple problems, it cannot read your mind.

What we actually want to do is remove the .to_string() and .to_vec() calls on the values we get from from_utf8 and slice respectively, since those were the functions that cloned the data from the cursor into our own owned heap allocations. Removing these calls from within the Simple, Error, and Bulk cases will make these "expected ... found ..." error messages go away.

... but we'll still have some errors that we need to take care of:

error[E0726]: implicit elided lifetime not allowed here
  --> src/frame.rs:15:6
   |
   | impl Frame {
   |      ^^^^^ expected lifetime parameter
   |
   = note: assuming a `'static` lifetime...
help: indicate the anonymous lifetime
   |
   | impl Frame<'_> {
   |           ++++

For this particular case, the compiler tells us to change it to Frame<'_> (where '_ is an anonymous lifetime). Let's see what happens if we do this:

error: lifetime may not live long enough
  --> src/frame.rs:78:20
   |
   |     pub fn decode(src: &mut Cursor<&[u8]>) -> Result<Self, ParseError> {
   |                                    -          ------------------------ return type is Result<Frame<'2>, error::ParseError>
   |                                    |
   |                                    let's call the lifetime of this reference `'1`
...
   |                 Ok(Self::Bulk(data))
   |                    ^^^^^^^^^^^^^^^^ argument requires that `'1` must outlive `'2`

If you have no idea what this means, then you're in good company. Although this error message looks extremely daunting, it is actually guiding us in the right direction this time. Let's briefly go over the problem here, but don't get too caught up on the details if you have trouble following.

The Self type is just an alias for the thing being impld, Frame<'_> in this case, where '_ could be any lifetime. When we accept a &mut Cursor<&[u8]>, omitting a lifetime on the &[u8] part also means that the inner &[u8] could have any lifetime. But this isn't okay, because if the lifetime in Self were to be longer than the lifetime of the &[u8], then it would be allowed to live for longer than the &[u8], which could lead to a dangling reference.

Therefore, we need to tell Rust "hey, these are going to have the same lifetime". To do this, we need to specify that Self is bound to the same lifetime that &[u8] is bound to, since they'll both be storing a pointer into the same owner wherever that is.

To do this, we'll need to introduce a named lifetime like 'a (as opposed to an anonymous lifetime '_). Since we're already using the Self type, and since it aliases the type that is being impld, let's change it from impl Frame<'_> at the top to impl<'a> Frame<'a> in order to introduce the 'a lifetime into scope.

If we had done this at the start, we would have gotten a much nicer compiler error for the definition of Frame::decode:

error[E0621]: explicit lifetime required in the type of `src`
  --> src/frame.rs:78:20
   |
   |     pub fn decode(src: &mut Cursor<&[u8]>) -> Result<Self, ParseError> {
   |                        ------------------ help: add explicit lifetime `'a` to the type of `src`: `&mut std::io::Cursor<&'a [u8]>`
...
   |                 Ok(Self::Bulk(data))
   |                    ^^^^^^^^^^^^^^^^ lifetime `'a` required

This compiler error is vastly more informative and tells us exactly how to fix this particular problem. Note that you don't need to specify the full path to Cursor since it's already imported at the top.

Once you incorporate the compilers feedback, your src/frame.rs file should be free of compiler errors. That wasn't so bad, was it?

Helper functions

In the last and final lab, we'll be building up the chat server logic, and doing so will require you to deconstruct and validate these frames. If we're expecting a frame that is an array of some other stuff, what might this look like?

fn parse<'a>(frame: Frame<'a>) -> Option<&'a str> {
    let array = if let Frame::Array(x) = frame {
        // evaluate to the inner array
        x
    } else {
        // short circuit the function
        return None;
    };

    // and continue doing this...
}

Read about if-let syntax here.

We don't want to manually write return None; on each failure case; instead, we want to make each failure case into something we can use ? on.

To do this, we'll define several methods on Frame: as_simple, as_error, and so on for each variant. Each of these will take in &self, and return Option<{variant data}>, where the data is the value stored in that variant. As an example, here's what as_array might look like:

impl<'a> Frame<'a> {
    // -- snip --

    pub fn as_array(&self) -> Option<&'a [Self]> {
        if let Frame::Array(array) = self {
            // array is `&Vec<Self>`, but can coerce into `&[Self]`.
            Some(array)
        } else {
            None
        }
    }
}

This will greatly simplify our code next week as we can use the ?-operator on Option values:

fn parse<'a>(frame: Frame<'a>) -> Option<&'a str> {
    let array = frame.as_array()?;

    // more logic here...
}

Problems with FrameReader::read_frame

Running cargo check again will reveal more compiler errors in src/rw.rs, and will helpfully tell us to run rustc --explain E0502:

A variable already borrowed as immutable was borrowed as mutable.

The error message seems simple, but is actually preventing us from much bigger issues, and explaining this is left as an exercise for the writeup.

The "quick fix" would be to remove the .consume(...) call on the ReadBuf, which makes the error go away, but not the logic is fundamentally flawed since we'll never be "throwing out" bytes that we're done with. Instead, we want to be able to get a Frame, and then somehow call .consume(...) when we're done with it.

The C solution: Manual consumption

One solution we might consider here is to make a public method on the FrameReader type that internally consumes bytes from the ReadBuf and trust that callers are responsible with it to use it correctly. This would be an excellect solution if we were writing C code, but we live in the 21st century and are trying to create an abstraction here.

Can we do better?

The JavaScript solution: Closures

Let's take a quick look at the broken code:

impl FrameReader {
    // constructor omitted

    pub fn read_frame<'a>(&'a mut self) -> Result<Frame<'a>, ReadError> {
        // frame validation omitted

        let frame = Frame::decode(&mut cursor)?; // 1

        // 2

        self.buf.consume(len); // 3
        Ok(frame) // 4
    }
}

At the point 1 we create a Frame that immutably borrows from self.buf. But then at point 3, we require mutably borrowing self.buf in order to mark len bytes as consumed. If the compiler were able to determine that frame isn't accessed beyond point 3, then it would compile this code because our immutable reference is never used after 3.

Here's a simplified example of the compiler being smart and doing this for us:

#![allow(unused)]
fn main() {
let mut x = 5;
let y = &x; // x borrowed immutably
println!("{y}");
// y isn't used past this point, so the compiler can be clever
x += 20;
}

This isn't the case though because frame is returned at point 4, meaning that point 3 might mutate what frame is referencing.

However, if we were able to do everything we needed with frame at point 2, then we could be finished with frame by 3 and the code would compile. One way to accomplish this is to have the caller pass in an arbitrary function that takes a Frame, and then call it at point 2, allowing us to then call .consume(...) and have the function compile.

If we wanted to take this more functional approach, we could make use of closures and the Fn, FnMut, and FnOnce family of traits, which allow us to place bounds on generic types that must be callable.

Using closures in this context might look like this:

impl FrameReader {
    // constructor omitted

    pub fn read_frame<'a, F>(&'a mut self, f: F) -> Result<(), ReadError>
    where
        F: FnOnce(&Frame<'a>),
    {
        // frame validation omitted

        let frame = Frame::decode(&mut cursor)?; // 1

        f(frame); // 2

        self.buf.consume(len); // 3
        Ok(()) // 4
    }
}

Notice how the function now returns (), since we've already done everything we need inside of f.

While passing in a function might seems like suitable behavior, it can lead to an incredibly unergonomic API for users. For example, any code inside a closure cannot ? to short circuit from the calling function:

fn do_stuff(reader: &mut FrameReader<TcpStream>) -> Result<(), ReadError> {
    reader.read_frame(|frame| { // <- argument is a closure
        // Can't do this
        let result = some_parse_function(frame)?;
        println!("{}", result);
    })
}

A more detailed example of me getting owned on this particular topic can be found in this GitHub thread.

The Rust solution: Guards

What we're really after is a way to pass back a Frame to the user so they can do whatever they want, and have .consume(...) be called on the buffer whenever the Frame isn't used anymore.

As it turns out, this is an extremely common pattern in Rust: borrow a resource, and have some cleanup code run when the borrow is no longer used. This is exactly how Rust's std::sync::Mutex<T> type works as well. A Mutex<T> wraps the data that it protects, and locking it returns a MutexGuard<'_, T>, which borrows from the Mutex and provides unique access to the inner T. When the MutexGuard is dropped, its destructor (specified by its std::ops::Drop implementation) unlocks the mutex, meaning that Rust programmers can never accidentally forget to unlock a mutex after they're done with it because it happens automatically.

Defining our own Guard type for FrameReader::read_frame

Let's use the guard pattern described above to update FrameReader::read_frame method. We'll start by stating the desired behavior:

1. FrameReader::read_frame returns an error if Frame::check fails.
2. If it succeeds, then the bytes in the buffer encode enough bytes for at least 1 valid frame, and it will return to us a guard that borrows the inner ReadBuf.
3. The guard can give us a Frame whose data borrows from the ReadBuf that it's borrowing.
4. When the guard goes out of scope, it will call .consume(...) on the ReadBuf with the correct number of bytes.

You should start by defining a Guard type along with a Drop implementation:

Filename: src/rw.rs

// other stuff omitted

pub struct Guard {
    // todo
}

impl Drop for Guard {
    fn drop(&mut self) {
        // todo
    }
}

The whole point of having a Guard type was so we could call .consume(...) on the buffer when the guard is dropped, meaning that Guard will need to carry a mutable reference to the ReadBuf and also the number of bytes to consume. This will require two fields, and you'll also need to introduce a lifetime to the Guard type as well.

Once you add these and implement the Drop implementation to consume the bytes, we'll need a way to actually get a Frame from a Guard, so let's add a method to do that as well:

impl Guard<'_> {
    pub fn frame(&self) -> Frame<'_> {
        // todo
    }
}

Implementing this is relatively straight-forward. For the &[u8], we'll access the data from the ReadBuf we're borrowing from with the .buf() method. We can use it to create a Cursor<&[u8]>, and then pass in a mutable reference of it to Frame::decode to get the Frame. Since we already checked that the full frame is there, we can call .expect("frame was checked") on the returned Result, which will panic if Err is returned.

Updating FrameReader::read_frame

Now that we have our Guard type, change the implementation of FrameReader::read_frame so that after it checks that there are enough bytes, it gets the number of bytes that the cursor has read so far with .position() as usize and returns a Guard that will .consume() that many bytes when it is dropped.

As a hint, the method type signature should look like this:

impl<R: Read> FrameReader<R> {
    // `new` omitted

    pub fn read_frame(&mut self) -> Result<Guard<'_>, ReadError> {
        // omitted
    }
}

One more Frame variant...

In the next lab, we'll be writing Frames back into Write types a lot, and our messages will be made up of arrays of other frames. In order to avoid having to allocate a Vec<Frame> to create an Array variant, we'll introduce the Frame::Slice variant, which is exactly like Frame::Array except it contains a &'a [Frame<'a>] instead of a Vec<Frame<'a>>. We'll also update WriteFrame::write_frame in src/rw.rs to add another branch in the match statement that functions identically to the Frame::Array branch. There are definitely better ways to encode this, but this solution is fine for now since it is very simple.

What this means is that whenever we receive a Frame that contains an array, we'll get the Array variant, but whenever we want to write back a frame, we can use the Slice variant instead since we won't have to perform a heap allocation.

Testing your code

For this lab, you should write more tests in src/frame.rs. You will also want to update your old tests to be compatible, but this shouldn't be much work.

Questionnaire

In questionnaires/, create a lab5.md file and answer the following questions:

# Questions

## Why borrowing?
In this lab, we added almost no new capabilities to our program, but instead just moved things around and changed some types.
What benefits does this lab bring?
Consider factors like heap allocations and copying data around.

### Response
TODO

## What is a guard?
In this lab, we introduced the concept of _guards_.
In your own words, what do guards allow us to do?
More importantly, what do they (helpfully) prevent us from doing?

### Response
TODO

Feedback

Please make sure that each member fills out this short feedback form individually.

Submitting

Once you're finished, you can push your changes to your git repository after ensuring that:

• cargo fmt has been run
• cargo clippy passes
• cargo test passes

Congratulations on finishing!

Week 6

Class 6: Chat Server

Thus far, we've built a fairly robust way to send messages as bytes, and to put these tools to use, we'll be building up a fairly primitive chat server that allows for multiple clients to connect and chat to each other in real time.

Expectations and what you'll be building

This course is focused on Rust, not on networking. Therefore, we'll be building up a very primitive example of a chat server that does pretty much what you'd expect it to do: support multiple clients joining, and chatting with each other.

This involves two pieces of software: the client code and the server code. The server is the one doing the connecting; when multiple users want to talk to each other, they'll connect to a central server which is then responsible for relaying messages between them. Server in the real world might do a lot more than this, but this is the basic scope that we'll be aiming for.

Since there are multiple roles going on at once, this also means that the client (you as the user) and the server need to be running different programs. In order to keep this lab simple though, we've already written the client software, and it will be your task to write the server program.

Specification

Before we dive into the details, let's discuss how the server should ideally work.

• First, the computer that will run the server needs to run the server, which will be done by cargo run on the server or something similar (maybe ./server or something similar).
• Second, clients should be able to connect to the server, also by doing cargo run. They will first have to enter a name before joining, and once they do, they will be connected and username joined will automatically be broadcasted to all connected clients, including themselves.
• When a client enters a messages, the server will broadcast it to everybody, prefacing the message with the username that person entered when they connected.
• When a client leaves (by pressing ctrl + C), the server should broadcast username left to everyone else connected.
• If the server stops, all connected clients are disconnected with an error.

These are the basic requirements for this server, and we'll be talking about extensions for it later.

With that our of the way, let's talk about the tool we'll actually need to write the server!

Event loops

The task of a server is not strictly linear unlike many programs that we write. At any given moment, we might have to handle someone joining or leaving the chat server, or someone might send a message that we should broadcast to everyone else. The server can never know what it's going to have to handle next since it depends on external factors, and so we need to make it responsive to anything.

In order to keep the server responsive, we'll use what's called an event loop. This is when the computer running the server sits in a loop forever, checking for various events, and then handling them as they occur.

In particular, event loops aren't unique to servers or Rust. Anywhere where you're waiting for one of many things to occurs can be built with an event loop, such as the firmware in your keyboard for detecting key presses, or traffic stop sensors waiting for cars.

Events in our chat server

Our chat server needs to be responsive to several kinds of events:

• When a new client joins, the server needs to keep track of their name and TCP connection somewhere in its internal state, as well as broadcast that they joined.
• When a client disconnects, the server needs to recognize this and remove it from its list of connected clients, as well as broadcast that they left.
• When a client sends a message, the server needs to forward it to all connected clients.

TCP Connections

In computer networking, TCP is a protocol that allows for sending raw bytes over a network such that the bytes arrive at their destination in the order that they were sent in. This seems like an intuitive and obvious preference, but understand that there's a bit of overhead happening under the hood that makes this possible!

Fortunately for us, the Rust standard library two types: std::net::TcpListener and std::net::TcpStream.

Here's all you need to know:

• The TcpStream type represents a connection to another program, possibly on another computer. It internally uses the underlying operating system and networking hardware to read and write bytes across a network via the Read and Write traits we previously discussed. You can think of it as a magical connection that allows us to communicate over a network. You can create one with TcpStream::connect("some address").
• The TcpListener type is the thing on the other end that "listens" for when you do TcpStream::connect. To create a connection, the TcpListener binds to a port (like TcpListener::bind("some address")), at which point other programs can TcpStream::connect to that address. Then, the TcpListener calls .accept() and gets a TcpStream in return, which is the other end of the connection. These two streams are now connected and can write and read bytes to and from each other.

Blocking Operations

Following with the nondeterministic nature of our server, we need to ensure that anyone can send a message at any time and it will immediately be broadcasted to everyone else. With the default settings, however, this will not be the case, and this is because of blocking, a core part of IO.

IO stands for "input output", and it basically can refer to anything that a program does that interacts with the outside world, such as reading and writing files, taking user input from the command line, and sending bytes across a TCP stream.

When a program performs IO, like reading waiting for a TCP connection to send bytes across a network, there's nothing it can do except wait. This means that your program is stuck doing nothing until the outside resource responds, and this is called blocking because your program is blocked from doing anything useful.

By default, the TcpStream type is blocking. If we try to read from one and the other side hasn't sent anything to use yet, we'll be stuff waiting for it to send something. To visualize why this is a problem, consider the following event loop:

// The event loop is literally a loop
loop {
    for tcp_stream in all_connections {
        let message = tcp_stream.block_until_read();
        broadcast(message);
    }
}

Here, we would only be able to see messages in order. If we're blocking on waiting for the first person to send a message and they never do, then we'll never even check if any of the other have sent a message, meaning that our server is fundamentally broken.

Instead of waiting for each client to send a message, what we instead want is to check if each client sent a message, which is a nonblocking operation.

In Rust, we can do this by configuring the TcpListener with .set_nonblocking(true).

This means that if we try to read bytes from a TCP stream and there's no bytes to currently read, instead of blocking the program and waiting, an error will be returned instead as part of io::Result<T>.

However, blocking isn't really an error in our situation, it just means that there's no value ready for us at the moment, which is best represented by an Option<T>. To get this, we'll write a function that will take an io::Result<T> and give us back an io::Result<Option<T>>, where if the result was Ok(t) in the first place, it will just return Ok(Some(t)), if it would have blocked, then Ok(None), and any other actual error would still be Err.

#![allow(unused)]
fn main() {
use std::io;

fn nonblocking<T>(res: io::Result<T>) -> io::Result<Option<T>> {
    match res {
        Ok(value) => Ok(Some(value)),
        Err(e) if e.kind() == io::ErrorKind::WouldBlock => Ok(None),
        Err(e) => Err(e),
    }
}
}

This means that whenever we try to accept an incoming connection from our TcpListener within the server, we can wrap the result in this function to help us distinguish between actual errors and when there are no more connections at the moment.

Lab 6: Chat Server

Due March 31, 11:59pm

Welcome to the final lab! As discussed in class, we'll be building of a little chat server composed of what we've been building in labs so far.

For details on the big picture of the lab, consult the class 6 notes.

Grading Rubric

• Code is formatted properly using cargo fmt: 5%
• Code passes cargo clippy without warnings: 10%
• Code passes our tests: 60%
• Responses in questionnaire.md: 25%

Connections

In the last lecture, we talked about how each client connection has a name associated with them, which is sent after the initial TCP connection is established. To simplify this lab a bit, we've provided the base code for how each "connection" is actually represented in the program. To use this in your program, create a new file at src/connection.rs and paste the following in:

Filename: src/connection.rs

use crate::{frame::Frame::*, rw::FrameReader};
use std::{net::TcpStream, thread::sleep, time::Duration};

pub struct Connection {
    pub reader: FrameReader<TcpStream>,
    pub name: String,
    pub id: u32,
}

impl Connection {
    pub fn establish(reader: TcpStream, id: u32) -> Option<Self> {
        let mut reader = FrameReader::new(reader);

        sleep(Duration::from_millis(50));

        let name =
            if let [Simple("JOIN"), Simple(name)] = reader.read_frame().ok()?.frame().as_array()? {
                name.to_string()
            } else {
                return None;
            };

        Some(Connection { reader, name, id })
    }
}

Then, add the following to your src/main.rs:

Filename: src/main.rs

mod connection;
use connection::Connection;

Creating a Server type

As we discussed in class, there are several things that the server needs to keep track of:

• a list of the currently connected clients (each one is a Connection),
• the TcpListener, which is was allow for accepting incoming connections,
• a message queue, where each message is encoded into bytes already (what type should this be?),

We'll also assign unique IDs to each connection, which we can do by keeping track of a next_id: u64 value which will tell us what to assign to the next incoming connection.

To keep track of these nicely, we'll create a Server struct with these fields, as well as a constructor called new.

The constructor should take an address as a &str (e.g. "127.0.0.1:6379"), create a TcpListener on the address, set it to nonblocking mode with .set_nonblocking(true), and then return a new Server value that starts with no connections, an initial next_id of 0, and an empty message queue.

Hint: If there's anything in the constructor that is fallibe i.e. results a Result, is it your responsibility to handle the error? If you think the answer is no, then you can make your constructor fallible as well by returning a result and propagating any possible errors to the caller.

Then, our main function at src/main.rs will be fairly simple:

1. Create a new Server value using "127.0.0.1:6379".
2. Inside of an infinite loop: accept clients, read frames, broadcast messages, repeat.

And that's our event loop! To make things easier to reason about, let's abstract each of these possible events into a method of Server.

Accepting Clients

To accept clients, let's create an accept_clients method on Server, which takes &mut self and returns io::Result<()>.

Inside the function, we only want to handle the clients that are already waiting, and more importantly, we do not want to block and wait for clients that aren't even there yet.

To do this, we'll need the nonblocking function discussed in class, which will convert WouldBlock errors (which we get because we did .set_nonblocking(true)) into Nones to make handling easier for us.

You can paste into your src/main.rs:

use std::io;

fn nonblocking<T>(res: io::Result<T>) -> io::Result<Option<T>> {
    match res {
        Ok(value) => Ok(Some(value)),
        Err(e) if e.kind() == io::ErrorKind::WouldBlock => Ok(None),
        Err(e) => Err(e),
    }
}

Then, we can use a while let loop in combination with self.listener.accept and nonblocking to repeatedly accept incoming connections until we would eventually have to block, at which point we want to stop looping and return from the function.

Piecing this logic together is a tricky, so if you find yourself completely stuck you should reach out and ask for help.

In each iteration of the loop, we should then have access to the TcpStream and SocketAddr for the incoming connection.

Edit: you'll need to also ensure that the TcpStream you get from .accept() is also set to nonblocking mode.

From here, you should attempt to establish the connection (i.e. wait for them to send over their name) by calling Connection::establish, passing in the TcpStream and the current next_id that the server is storing.

If the connection is successfully returned, then there are three things we need to take care of:

1. enqueue a message saying that that user has joined,
2. add the Connection to the server's list of connections,
3. update the next_id to the next integer.

If the connection failed to return, then we should just print an error like "{addr} timed our during connection", where addr is the SocketAddr.

To enqueue a message, let's write a helper method for that too, which will make things a lot easier if you decide to make your server multithreaded next week.

The message we'll send is:

&Slice(&[Simple("JOIN"), Simple(&conn.name)])

where conn is the Connection value.

Make sure you do use frame::Frame::*; at the top so you can write the frames as things like Simple, instead of having to say Frame::Simple.

Enqueuing Messages

To enqueue messages into the message queue, we'll start by creating an enqueue_message method for Server that takes &mut self and a &Frame<'_>.

This method is extremely straightforward: since each "message" in the message queue is the byte-encoded version of the Frame, we need something to encode it into. To do this, we'll just create a new Vec<u8>. Since Vec<u8> implements the Write trait, it means it's compatible with the WriteFrame trait we created in lab 4. Using that, write the Frame into the Vec<u8>. Then, push the buffer encoding the frame to the back of the message queue using .push_back(buf).

Reading Frames

At this point, we know how to accept new clients, and so the next task is to see what they're sending us.

To do this, begin by adding a read_frames method to Server, taking just &mut self.

This method will proceed as follows:

1. Loop through all connections.
2. For each connection conn, call .read_frame() on its reader to get a Result<Guard<'_>, ReadError>.
3. If the result is Ok, then we'll handle the frame (descibed below). If the result is an error because the clients message is pending, do nothing and continue looping. Otherwise, enqueue the message &Slice(&[Simple("LEAVE"), Simple(&conn.name)]) and remove the connection from the list. Also, if the disconnect wasn't intentional, print that an error occurred.

One major problem with this is that when we iterate over the Vec<Connection>, we cannot remove things from it as we go.

To overcome this, we can use the .retain_mut(...) method that Vec<T> provides, which allows us to look at each element in a vector as a &mut T and decide whether or not we want to retain it in the vector or not by returning a bool.

So instead of writing your code like this:

for conn in connections.iter_mut() {
    // stuff here
}

We will instead be writing the following

connections.retain_mut(|conn| {
    // stuff here
})

With the difference being that in the second example, the inner part must return/evalutate to a bool, where true means "keep this element in the vector" and false means "remove".

This will lead to one other problem, however: if we're calling self.connections.retain_mut(...), then self is mutably borrowed for the duration of retain_mut, but this is a bad thing because we need to be able to do other things with self inside of the function.

To overcome this, we can transfer ownership of the Vec<Connection> out of self and put in a dummy vector temporarily, do the retain_mut stuff, and then put the vector back into self with the following:

// Move ownership to temporary variable so we can
// mutate `connections` without using `self`
let mut connections = std::mem::take(&mut self.connections);

// Mutate connections
connections.retain_mut(|conn| {
    // inner logic goes here
});

// Put the mutated vec back into self
self.connections = connections;

Handling Frames

We also need to handle frames sent to the server from the client. For this we'll make a handle_frame method that takes &mut self, the name associated with the connection (&str), and the &Frame<'_>. If the frame represents a message, i.e. is an array (consider using your .as_array() method) of two elements with a simple string "MSG" as its first element and a simple string (we'll call it message), as its second element, then we should enqueue the following message:

&Slice(&[Simple("MSG"), Slice(&[Simple(name), Simple(": "), Simple(message)])])

Otherwise, it's an error which you can just report to the console with a print statement.

Checking if a connection is pending

For this lab, we'll define a connection as pending if one of two conditions are true about the returned ReadError:

1. The ReadError was the Io variant, where calling .kind() on the error returns io::ErrorKind::WouldBlock.
2. The ReadError was the Parse variant, and the inner ParseError was the Cursor variant, and calling .not_enough_data() on the inner CursorError returns true. You can avoid writing a lot of match statements by nesting patterns here as we saw in lab 1 questionnaire.

The first scenario tells us that the client hasn't sent any data over and so we shouldn't do anything on them, and the second represents that some of the bytes they were sending were delivered but not all yet. Neither of these are considered errors, and it just means we have to check in on them later.

It may be handy to make this a method on ReadError directly as is_pending.

Checking if the client intentionally disconnected

When a client disconnects intentionally (e.g. the client presses ctrl + C), they'll send a special message telling us that the connection was closed on their end intentionally.

To determine if this is the case, we can check if the ReadError is the Io variant, and calling .kind() on the inner io::Error returns io::ErrorKind::WriteZero. Anything else means that the connection terminated under other conditions, in which case an error should be printed.

It may be handy to make this a method on ReadError directly as is_exhausted.

Broadcasting Messages

In the event loop, once we've finished reading the frames, we need to broadcast any messages we've been planning on sending. To do this, we'll make a broadcast_messages method to Server that just takes &mut self and returns io::Result<()> and repeatedly pops messages from the front of the messages queue and writes them to each of the connections.

Hint: the while let syntax mentioned above might come in handy here.

One problem that you might encounter is that we want to write the encoded bytes back to the TcpStream objects in each FrameReader in each Connection, but we cannot access it because it's hidden inside of the FrameReader.

To overcome this, write a method for FrameReader that gives you mutable access to the inner reader value, and use this to access the TcpStream in the FrameReader in each Connection and then do .write_all(&message)? where message is the Vec<u8> that you popped from the queue.

Client

You can get the client by cloning (this)[https://github.com/William103/chat-client] repo. Then you can run it with cargo run to test out your server.

Feedback

Please make sure that each member fills out this short feedback form individually.

Submitting

Once you're finished, you can push your changes to your git repository after ensuring that:

• cargo fmt has been run
• cargo clippy passes
• cargo test passes

Congratulations on finishing!

Week 7

Extensions

Connecting to your server from other computers

In order to allow other computers to connect to your server, we need to bind to our local computers public address.

To find this, we'll bring in the local_ip_address crate as a dependency, which does some surprisingly nontrivial work to help us out. Run the following while inside of your server-student1-student2 repo directory:

cargo add local_ip_address

Then, we want to use it to find our local public address, print it out so we can share it with others, and finally bind our server to it.

To do this add the following to your main function:

Filename: src/main.rs

fn main() -> io::Result<()> {
    let ip = local_ip_address::local_ip().unwrap();

    println!("IP: {ip:?}");

    let mut server = Server::new(&format!("{ip}:6379"))?;

    // event loop logic here...
}

Running your server now with cargo run will then print out an ip address.

Before we can do this, make sure you pull the latest changes from the chat-client repo with git pull, and then run the client with:

cargo run -- <the ip address of the server>

For example, if the server printed IP: 130.58.68.175 you would run the client with cargo run -- 130.58.68.175.

Feature ideas

Direct messaging

Add support for direct messaging other users. For example, if I'm Quinn and I want to message William, I could write:

/dm William u tryna rust rn?

And on my screen I should see

you -> William: u tryna rust rn?

And he should see:

Quinn -> you: u tryna rust rn?

This would involve some work modifying the message queue so that messages could also carry information about who to get sent to.

Note that in the client code, it will concatenate messages for you. So if the server wanted William to see Quinn -> you: the message, it could send:

Slice(&[
    Simple("MSG"),
    Slice(&[
        // a bunch of frames for each part
        // that will then be concatenated by the client
    ])
])

Info commands

Support commands so clients can write things like /info and get information sent to them and only them. For example, you could send them a list of the currently connected clients, or how long each person has been connected for, or who has sent the most messages.

Chat rooms

Building off the idea for special commands, add support for chat rooms in some way. Allow users to join and leave chat rooms, maybe even create their own.

For this, you'll definitely need a way to send messages to specific people instead of always broadcasting to everyone.

Security

Spam protection

Track how frequently each connection is sending messages and send them warnings or disconnect them if they spam too much.

Username checking

Don't allow for clients to join with the same name as someone else, or add filters on what names are allowed. Right now, the client will allow just about anything through (including emojis, special symbols, etc.).

Parallelism

Having everything in one event loop is straightforward, but can become a big performance bottleneck running everything on a single thread.

There are two key ingredients when it comes to concurrency in Rust:

• Threads
• Channels

Sometimes, we want to send multiple different kinds of messages across a channel, and enums are perfectly suited for this use case because each variant can represent a different kind of message.

For example, we could have an Update enum with variants representing a new connection, a disconnection, or a message sent, and then have a single channel that sends Update values.

With this out of the way, there are (at least) two levels of extensions we can do with concurrency for this project:

• Writer thread
• Recycling allocations

Writer thread

This will include a from the main thread to the writer thread.

Here the main loop will be responsible for checking for new connections and checking for new frames. If a new connection is received, then it is sent to the writer thread. While there are new connections that can be received (we expect 0 or 1 at any given moment typically), they are also sent to the writer thread. Then, it loops through all existing connections and tries to receive a message. If any message is received, then it is handled and the response is encoded in a Vec<u8> and sent to the writer thread as well.

In the writer thread, it will first pull all messages from the connect/disconnect channel and update its own list of live connections accordingly. Then, it will pull messages from the message channel and send them to all the connected channels respectively, and repeat this process again from the start.

This strategy should only involve two major changes to your code: the enqueue_message function should now be sending Vec<u8>s across a channel instead of pushing to a VecDeque, and you will need to spawn the writer thread (and define its functionality) in main.

Recycling allocation

Instead of having an ordinary channel sending Vec<u8> values to the writer thread, use the thingbuf crate, which offers an MPSC channel that also acts as an object pool. This way, allocations can be reused.

This should only involve changing the enqueue_message method.