This book is for learning Rust. It assumes no prior programming background, although familiarity with some programming languages may help.

This is a work in progress.

Hao Chen root@gradebot.org

Computers store data in memory. Memory consists of a sequence of bytes, where each byte stores 8 bits. A byte is the smallest unit that a computer can address (read or write), and a bit is the smallest unit of data.

Bytes may represent different types of data. For example, one byte may represent an 8-bit unsigned integer, a 7-bit signed integer, or an ASCII character. A type defines a set of valid values and operations on these values. For example, the u8 type defines values in the range [0, 255] and arithmetic operations on them.

Type determines how the compiler interprets bytes in memory as values. For example, if a memory byte stores the bit pattern 10000000, the compiler interprets it as

• the integer 128 if the type is u8 (8-bit unsigned integer).
• the integer -128 if the type is i8 (8-bit signed integer).

We can divide types into three categories:

• atomic primitive types
• composite primitive types
• custom types

Atomic primitive types are defined by the compiler and cannot be customized by the user. The compiler implements the Copy trait on these types.

The bool type has two values: true and false.

Rust defines the following machine-independent integer types, which contain 1, 2, 4, 8 bytes, respectively.

• Signed integers: i8, i16, i32, i64.
• Unsigned integers: u8, u16, u32, u64.

Rust also defines the following machine-dependent integer types, whose lengths are large enough to store the addresses of the machine:

• isize: signed integer.
• usize: unsigned integer.

• f32: 32-bit floating point.
• f64: 64-bit floating point.

• char: contains a Unicode scalar value in 4 bytes. For example,

'a'
'锈'

• str: contains a Unicode string (a sequence of Unicode scalar values). This type is special: because strings of different lengths have the same type str, the size of this type is unknown at compile time. Therefore, programs may not use this type directly but must use it only via a pointer type, such as &str. For example,

"Hello, world"
"你好，世界"

Composite primitive types contain other types.

• Array [T; N]: contains N elements of the type T. For example:

// Type: [i32; 1]
[1] 
// Type: [&str; 2]
["Hello", "World"] 

A program can access an element of an array using the expression [i] (the index i starts from 0), e.g.:

assert_eq!(["Hello", "World"][1], "World");

assert_eq!(x, y) is a macro. It panics if x and y are different, and does nothing otherwise.

• Slice &[T]: contains a pointer to a range of elements in an array whose elements have the type T. You may create a slice from an array or another slice. For example:

// A slice containing the elements (start, start + 1, ..., end - 1) in `array`
&array[start..end]
// Same as `&array[0..end]`
&array[..end]
// Same as `&array[start..array.len()]`
&array[start..]
// Same as &array[0..array.len()]`
&array[..]
// Same as &array[..]`
&array

A program can access an element in a slice using the same notation [i] as accessing an element in an array.

At compile time, the size of an array is known, but the size of a slice is unknown.

The tuple type (T1, T2, ..., Tn) contains a sequence of elements where each element may be a different type. For example:

// Empty tuple
() 
// Single-element tuple must end with `,` to distinguish it from a parenthesized expression
(1,) 
// A tuple of two elements
(1, "a")

A program can access the ith element in a tuple using the expression .i (the index starts from 0), e.g.:

assert_eq!(("Hello", "World").1, "World");

The empty tuple (), also called the "unit type", is special. It has a single value () and is used to represent "no value". E.g., when an expression or function returns no value, it returns ().

Two array types [T1; N1] and [T2; N2] are considered to be identical if T1==T2 and N1==N2. Two tuple types (A1, A2, ..., An) and (B1, B2, ..., Bn) are considered to be identical if A1==B1, ..., An==Bn.

Composite primitive types automatically implement the Copy trait if all their constituent types implement the Copy trait.

We will discuss custom types in later chapters.

Computers store values in memory. Sometimes we care about the values, but other times we care about the memory locations where the program stores values. For example, for a program that reads an integer from the input and writes the integer to the output, it doesn't know the input value at compile time, but it can ensure that the read and write use the same memory location. Rust uses variables to represent memory locations.¹

The let statement names a variable and binds it to a memory location on the stack. Additionally, this statement can annotate the type of the variable and initialize its value.

# #![allow(unused_variables)]
#fn main() {
// Binds a variable
let x;
x = 1;
// Binds a variable and annotates its type
let y: i32;
// Binds a variable, annotates its type, and initializes its value.
let z: i32 = 1;
// Binds a variable and initialize its value, but lets the compiler infer its type.
let w = 1; // The compiler infers that the type of `w` is `i32`.
#}

A program may bind multiple variables in the same let statement using tuples:

# #![allow(unused_variables)]
#fn main() {
let (x, y, z) = (1, 2.0, "Hello, world");
assert_eq!(x, 1);
assert_eq!(y, 2.0);
assert_eq!(z, "Hello, world");

#}

If you didn't initialize a variable when binding it, you must assign it a value before reading it. The compiler prevents you from using uninitialized variables.

# #![allow(unused_variables)]
#fn main() {
let x;
x = 1;
assert_eq!(x, 1);
let y: i32;
// Error: use of uninitialized variable
assert_eq!(y, 1);
#}

In many other languages, a program may modify the value of any variable. However, modifying variables changes the state of the program, which may cause bugs. By contrast, reading variable values is safe because it does not change the state of the program. As a good software engineering practice, variables are immutable by default in Rust. Immutable variables also allows the compiler to optimize the program better. If a program wishes to modify a variable, it must use the mut keyword in the let statement:

# #![allow(unused_variables)]
#fn main() {
// `x` is immutable
let x = 1;
// `y` is immutable
let y;
// `z` is mutable
let mut z = 1;
// Error: `x` is immutable
x = 1;
// OK: initialize `y`
y = 1;
// Error: `y` is immutable
y = 1;
// OK: `z` is mutable
z = 2;
#}

In a let statement binding multiple variables, mut annotates only the variable following it:

// Only `y` is mutable. `x` and `z` are immutable
let (x, mut y, z);

When a program rebinds a variable, it frees the memory location of (and destroys) the current value and then allocates a new memory location for the variable.

# #![allow(unused_variables)]
#fn main() {
let x = 1;
assert_eq!(x, 1);
let x = "Hello, world";
assert_eq!(x, "Hello, world");
#}

If a program wishes to rebind a variable temporarily without destroying its current value, it can introduce a new scope.

• A block is a region of the program enclosed by a pair of braces {...}.

• A scope of a variable is the block where the variable is bound.

A variable is visible only in its scope. However, if a variable is rebound in a nested scope, the variable in the parent scope becomes invisible in the nested scope (the variable in the nest scope shadows the variable in the parent scope), but it will become visible again when the program exits the nested scope to return to the parent scope.

# #![allow(unused_variables)]
#fn main() {
// Parent scope
let x = 1;
{
    // `x` in this nested scope shadows `x` in the parent scope.
    let x = "Hello, world";
    assert_eq!(x, "Hello, world");
}
assert_eq!(x, 1);
#}

A variable goes out of scope when the program leaves the scope where the variable is bound. The program frees the variable's memory and destroys the variable's data.²

To place a value on the heap, the program creates a box. This is similar to C's malloc function or C++'s new operator. In the following example, the program places the value 1 on the heap, and creates a variable x on the stack to point to the value on the heap.

# #![allow(unused_variables)]
#fn main() {
let x = Box::new(1);
#}

We say that the box variable x owns the value 1 on the heap. When the box variable goes out of scope, the compiler automatically drops its value on the heap. No garbage collection or manual drop is necessary. By contrast, C and C++ require the program to free heap values manually, which is error prone, and Java relies on garbage collection to free heap values, which results in slower, unpredictable performance.

Rust provides two types of expressions for control flows: branching expressions and loop expressions.

An if expression evaluates a boolean predicate to decide which branch to execute. It may have one or two branches. If it has two branches, the second branch follows the else keyword. Each branch must be a block, i.e., enclosed in a matching pair of braces.

# #![allow(unused_variables)]
#fn main() {
let x = 1;
let y;
if x >= 0 {
    y = x;
} else {
    y = -x;
}
assert!(y >= 0);
#}

Since if is an expression, it has a value, which is the value of the block that it executes. If a block ends with an expression, its value is that of the expression; otherwise, its value is ().

# #![allow(unused_variables)]
#fn main() {
let x = 1;
let y = if x >= 0 {
    x
} else {
    -x
};
assert!(y >= 0);
#}

Since an expression must have a unique type decidable at compile time, both branches of an if expression must have the same type. If the else branch is missing, its type is the unit type ().

# #![allow(unused_variables)]
#fn main() {
let x = 1;
// Error: two branches have different types.
let y = if x >= 0 {
    x
} else {
    "Hello"
};
#}

# #![allow(unused_variables)]
#fn main() {
let x = 1;
// Error: the `else` branch is missing and so has the unit type `()`
let y = if x >= 0 {
    x
} ;
#}

# #![allow(unused_variables)]
#fn main() {
let x = 1;
// OK: the `else` branch is missing and so has the unit type `()`.
// The true branch does not end with an expression, so it has also the unit type too.
// Note that the type of `y` is the unit type.
let y = if x >= 0 {
    x;
};
#}

Rust also provides the match expression for branching, which we will describe in a later chapter.

The loop expression executes its block infinitely. A program can break out of the loop by the break expression.

# #![allow(unused_variables)]
#fn main() {
let mut x = 0;
loop {
    x += 1;
    if x > 9 {
        break;
    }
}
assert_eq!(x, 10);
#}

The break expression may be followed by an expression, which becomes the value of the loop expression.

# #![allow(unused_variables)]
#fn main() {
let mut x = 0;
let y = loop {
    x += 1;
    if x > 9 {
        break x;
    }
};
assert_eq!(y, 10);
#}

The while expression takes a predicate and executes its block indefinitely as long as the predicate is true.

# #![allow(unused_variables)]
#fn main() {
let mut x = 0;
while x < 10 {
    x += 1;
};
assert_eq!(x, 10);
#}

A program may break out of a while loop by the break expression. Or it may execute the continue expression to stop executing the current iteration and jump to the predicate of the loop.

# #![allow(unused_variables)]
#fn main() {
let mut x = 0;
while x < 10 {
    x += 1;
    if x % 2 == 0 {
        continue;
    }
    println!("{}", x);
};
assert_eq!(x, 10);
#}

The most common, versatile loop expression is the for expression. A for expression loops over a collection of items.

# #![allow(unused_variables)]
#fn main() {
for i in 0..10 {
    println!("{}", i);
}
#}

0..10 is syntactic sugar for the Range type, which implements the std::iter::IntoIterator trait. In fact, a program may use the for expression on any expression that implements the std::iter::IntoIterator trait. For example:

# #![allow(unused_variables)]
#fn main() {
let a = [1, 2, 3];
let v = vec![1, 2, 3];
for i in a.iter() {
    println!("{}", i);
}
for i in &v { 
    println!("{}", i);
}
// Prints both the index and value.
for (index, value) in v.iter().enumerate() {
    println!("{}: {}", index, value);
}
#}

A function takes zero or more input values and optionally returns an output value. By convention, we call the input values parameters in the callee, and arguments in the caller.

# #![allow(unused_variables)]
#fn main() {
fn foo() {
}

fn bar(x: i32, y: &str) {

}

fn baz(mut x: i32) -> i32 {
    x += 1;
    x
}

foo();
bar(1, "Hello, world");
assert_eq!(baz(1), 2);
#}

When calling a function with arguments, Rust binds the function parameters to these arguments. For example,

# #![allow(unused_variables)]
#fn main() {
fn foo(x: i32, y: &str) {
}

// The next line implicitly executes:
// let x: i32 = 1;
// let y: &str = "hello, world";
foo(1, "hello, world");
#}

Previously, we stated that a program may elide type annotations in the let statement and let the compiler infer the types. By contrast, Rust requires type annotations in function definitions. This is because type annotations allow the compiler to detect type errors. This is especially useful for functions, because often its implementor and user are different. The implementor uses type annotations to establish a contract, and the compiler ensures that the function user must fulfill the contract. By contrast, since the scope of a variable is a block and a block is usually written by the same person, enforcing the contract is less important. Moreover, type inference provides a significant ergonomic benefit without sacrificing safety in a common case where the program both binds and initializes a variable in the let statement.

# #![allow(unused_variables)]
#fn main() {
let x = "hello, world";
// The above is equivalent to
// `let x: &str = "hello, world";`
let y = [1, 2, 3];
// The above is equivalent to
// `let y: [i32; 3] = [1, 2, 3];`
#}

This avoids a common stutter in Java, where the compiler should be able to infer the type of foo based on the type of the value Foo():

Foo foo = new Foo();

A function may return a value by either using the return statement or placing the value on the last line executed in the function.

# #![allow(unused_variables)]
#fn main() {
fn f() -> i32 {
    return 1;
}

fn g(x: bool) -> i32 {
    if x {
        // Returns 1
        1
    } else {
        // Returns -1
        -1
    }
}
#}

Note in g(), the lines that return the value don't end in a semicolon.

Rust is primarily an expression language, meaning that most code lines that produce values or cause effects (e.g., print) are expressions. An expression returns a value but a statement doesn't.

Rust has only two types of statements.

• Declaration statement
  • Item declaration. This statement declares an item, such as a function, enumeration, struct, type, static, trait, implementation, or module (to be discussed in later chapters).
  • let statement. This statement binds variables.
• Expression statement. This statement consists of an expression followed by a semicolon. It evaluates the expression and then discards its result, therefore aiming for only its side effect, e.g., println!(). This is useful to contain and explicitly sequence expression evaluation. Therefore, if a function wishes to return the value produced on its last line, the line must not end in a semicolon.¹

If you came from C/C++, you may be surprised that the value of an assignment expression is the empty tuple (), also called the unit type, rather than the value being assigned. For example:

# #![allow(unused_variables)]
#fn main() {
let x;
// The value of `y` is `()` instead of `1`.
let y = (x = 1);
assert_eq!(y, ());
#}

The function type, fn(), is another primitive type. A function type specifies the types of all the parameters and that of the return value, if any. The value of a function type contains the pointer to a function.

# #![allow(unused_variables)]
#fn main() {
fn square(x: i32) -> i32 {
    x * x
}

let f: fn(i32) -> i32;
f = square;
assert_eq!(f(2), 4);

fn print(x: &str) {
    println!("{}", x);
}

let g: fn(&str) = print;
g("hello");
#}

Rust guarantees memory safety. A memory-safe language doesn't allow any program to access memory locations that it doesn't own. Programming languages manage memory using two approaches: automatic memory management and manual memory management.

• Automatic memory management. In this approach, programs don't free memory explicitly. Instead, a garbage collector frees memory that will no longer be used, therefore guaranteeing memory safety by definition. However, garbage collection comes with runtime costs. When it runs, the entire program stops, and it is unpredictable when garbage collection runs. Also some software, such as operating system kernels, cannot include a garbage collector. This is because garbage collection relies on low-level memory management functions that are part of the kernel, so writing a kernel using a garbage-collected language poses a chicken-and-egg dilemma.

• Manual memory management. In this approach, programs free memory explicitly. While this avoids the cost of garbage collection, it often causes memory errors. Consider the following C program:

void drop(char *p) {
    free(p);
}

int main() {
    char *p = malloc(sizeof(char));
    drop(p);
    // Error: use after free
    *p = 'a';
    // Error: double free
    drop(p);
}

First, it frees p in the function drop(). Then, it dereferences p in the function main(). This is a classic use-after-free error. Finally, it frees p in drop() again. This is a classic double free error.

Rust achieves memory safety without garbage collection. Rust's borrow checker enforces memory safety by three mechanisms: ownership, borrowing, and lifetime.

In C/C++, values are like electronic books with no DRM (Digital Rights Management): they can be freely copied.

In Rust, however, values are like physical books. Each book has only one owner at any time. Once Alice gives her book to Bob, Bob becomes the new owner, and Alice stops owning the book. When a Rust program runs y = x, y becomes the new owner of the value, and x stops owning the value. This is called the move semantics.

The move semantics is powerful in preventing the double free error, because each value has a single owner and only the owner can free the value.

# #![allow(unused_variables)]
#fn main() {
// Defines a custom type. We cannot use a primitive type in this example because they all implement the `Copy` trait.
struct Foo(i32);
let x = Foo(1);
// Move the value in `x` to `y`
let y = x;
// Error: x no longer has the value.
println!("{}", x.0);
#}

# #![allow(unused_variables)]
#fn main() {
struct Foo(i32);
fn f(x: Foo) {
}

let x = Foo(1);
// Move the value in `x` to `f()``
f(x);
// Error: x no longer has the value.
println!("{}", x.0);
#}

The move semantics is sometimes too restrictive. Many values, particularly of primitive types, need not be freed, so the move semantics becomes unnecessary. Rust allows a type to have the copy semantics: the program creates a new copy of the value when assigning variables of this type.

A type has the copy semantics when it implements the Copy trait. The compiler implements the Copy trait on

• all the atomic primitive types.
• all the composite primitive types if all their constituent types implement the Copy trait.
• shared references.

# #![allow(unused_variables)]
#fn main() {
let x = 1;
let y = x;
// OK: `i32` implements the `Copy` trait.
println!("{}", x);
#}

# #![allow(unused_variables)]
#fn main() {
fn f(x: i32) {
}
let x = 1;
f(x);
// OK: `i32` implements the `Copy` trait.
println!("{}", x);
#}

A custom type may implement the Copy trait automatically using the derive attribute.

# #![allow(unused_variables)]
#fn main() {
// Because `Copy` inherits from `Clone`, we must derive `Clone` as well.
#[derive(Copy, Clone)]
struct Foo(i32);
let x = Foo(1);
// Move the value in `x` to `y`
let y = x;
// OK: `Foo` implements the copy trait.
println!("{}", x.0);
#}

Sometimes, multiple variables need to access the same value, but the move semantics requires the program to pass the value between these variables. This could become unergonomic, especially when crossing function boundaries.

# #![allow(unused_variables)]
#fn main() {
struct Foo(i32);

fn f(x: Foo) -> Foo {
    // do something with `x`
    x
}

let mut x = Foo(1);
x = f(x);
#}

Since the function f() takes ownership of its argument, it must return the value to the caller if the caller needs the value later. This is laborious.

To improve the usability, Rust allows a variable to borrow a value without taking ownership. When x borrows the value of y, y still owns the value. We call x a reference to y. When x goes out of scope, the borrow ends, and since x doesn't own the value, the value isn't destroyed. To borrow a value, take a reference by the & operator. To use a borrowed value, dereference it by the * operator.

# #![allow(unused_variables)]
#fn main() {
struct Foo(i32);

fn f(x: &Foo) {
    // The explicit dereferencing, `(*x).0`, isn't necessary due to auto-deref.
    println!("{}", x.0);
}

let x = Foo(1);
f(&x);
// OK: the borrow ended
println!("{}", x.0);
#}

Since references do not own the value, they cannot move the value.

# #![allow(unused_variables)]
#fn main() {
struct Foo(i32);
let x = Foo(1);
let y = &x;
// Error: `y` doesn't own the value
let z = *y;
#}

A program may declare a variable x as a reference to the type T in two ways.

1. Using & in front of the type T

# #![allow(unused_variables)]
#fn main() {
let x: &i32;
x = &1;
#}

2. Using ref in front of the variable x

# #![allow(unused_variables)]
#fn main() {
let ref x: i32;
x = &1;
#}

Often the program may choose either option. However, in the context where the program cannot specify the type of T, it must use the second option. E.g., the following example shows how to use ref in pattern matching.

# #![allow(unused_variables)]
#fn main() {
struct Foo(i32);
let x = Some(Foo(1));
match x {
    // Must bind `y` as a reference to `Foo` to be able to use `x` after this `match`.
    // If we bound `y` to `Foo`, then we would move `Foo` into `y`,
    // so we could not use `x` after this match.
    Some(ref y) => assert_eq!(y.0, 1),
    None => (),
}
// Can still use `x`.
assert_eq!(x.unwrap().0, 1);
#}

Often we need not explicitly declare the type because the compiler can infer the type.

# #![allow(unused_variables)]
#fn main() {
let x;
x = &1;
#}

The scope of a reference must be contained in the scope of the owner of the value. Otherwise, the reference may refer to a freed value, causing the use-after-free error.

# #![allow(unused_variables)]
#fn main() {
let x;
{ 
    let y = 0;
    // Error: the reference `x` outlives the owner `y`.
    x = &y;
}
println!("{}", x);
#}

The above program tries to dereference x after the owner of the value y goes out of scope. Rust prevents this use-after-free error.

What if the program does not call println!()? You might think that it would be fine because it does not try to dereference x, but you'd be wrong. Rust does not allow a reference x to outlive the data owner even if the program never dereferences x.

Furthermore, if the program does not create a new scope,

# #![allow(unused_variables)]
#fn main() {
{
    let x;
    let y = 0;
    // Error: the reference `x` outlives the owner `y`.
    x = &y;
}
#}

it will still fail to compile. This is because Rust creates an implicit scope for each let statement. The implicit scope starts just before the let statement and ends where the name that this statement binds originally goes out of scope (i.e., without considering this implicit scope). So the compiler converts the above program into:

# #![allow(unused_variables)]
#fn main() {
{
    let x;
    {
        let y = 0;
        // Error: the reference `x` outlives the owner `y`.
        x = &y;
    }
}
#}

The rule that a reference cannot outlive the owner of the value prevents a common error in C where a function returns a pointer to a variable on the stack:

int* f() {
    int x;
    // Error: `x` goes out of scope when `f()` returns, 
    // but the C compiler cannot catch this error.
    return &x;
}

If you try to write it in Rust,

# #![allow(unused_variables)]
#fn main() {
// Error: no value in `f()` has a lifetime greater than `f()`.
fn f() -> &i32 {
    let x = 1;
    &x
}

let r = f();
#}

the compiler will reject the program because the scope of the reference r is not contained in the scope of the variable x, i.e., r outlives x.

A variable can borrow a value for reading only, or for both reading and writing. The former is called a shared (or immutable) reference, and the latter is called a mutable reference. A variable x may mutably borrow a variable y only if y is mutable; otherwise, the program could circumvent the immutability of y by first letting x mutably borrow y and then modifying the value via x.

# #![allow(unused_variables)]
#fn main() {
let mut x = 1;
// Shared reference 
let y = &x;

let mut z = 1;
// Mutable reference
let w = &mut z;
#}

# #![allow(unused_variables)]
#fn main() {
let x = 1;
// Shared reference
let y = &x;
// Error: cannot mutably borrow an immutable variable
let z = &mut x;
#}

A reference itself can be immutable or mutable. An immutable reference cannot be modified.

# #![allow(unused_variables)]
#fn main() {
let (mut x, mut y) = (1, 2);
// `z` is a mutable reference
let z = &mut x;
// Error: `z` is immutable so cannot be modified.
z = &mut y;
#}

# #![allow(unused_variables)]
#fn main() {
let (mut x, mut y) = (1, 2);
// `z` is a mutable reference
let mut z = &mut x;
// OK: `z` is mutable
z = &mut y;
#}

Borrow creates aliasing, i.e., multiple variables referring to the same value. Without restrictions, this could lead to data races. For example:

• x is a mutable reference to y (therefore, y must be mutable), and
• Modify the value via x and y concurrently.

To prevent data races, at any time, if a value has a mutable reference, it may not have any other (mutable or shared) references. In other words, a value may have one or more shared references only, or have exactly one mutable reference.

This rule prevents a common error called iterator invalidation, where the program modifies a collection while iterating over it.

v = [1, 2]
for i in v:
    # Error: iterator invalidation
    v.append(i)

If you try to write it in Rust, the compiler will reject it because the program is borrowing v both immutably and mutably.

# #![allow(unused_variables)]
#fn main() {
let mut v = vec![1, 2];

// Borrows `v` immutably
for i in &v {
    // Error: borrows `v` mutably, but `v` was already borrowed.
    v.push(*i);
}
#}

Borrow restricts allowable operations (read, write, or move) on the borrowed variable. If the variable x owns a value,

• when x is borrowed only immutably (i.e., the program has only shared references to x), the program may read x, but not write or move x.
• when x is borrowed mutably (i.e., the program has a mutable reference to x), the program may not read, write, or move x.

If x is a reference, it is reborrowed when

• let y = &*x, or
• let y = &mut *x if x is a mutable reference.

In the latter case (i.e., a mutable reference x is reborrowed mutably), the program cannot read or write x.

# #![allow(unused_variables)]
#fn main() {
let x = 0;
// OK: only shared references
let (y, z) = (&x, &x);
#}

# #![allow(unused_variables)]
#fn main() {
let mut x = 0;
// OK: one mutable reference
let y = &mut x;
// Error: cannot have both mutable and shared references
let z = &x;
#}

# #![allow(unused_variables)]
#fn main() {
let mut x = 0;
// OK: one mutable reference
let y = &mut x;
// Error: cannot have multiple mutable references
let z = &mut x;
#}

# #![allow(unused_variables)]
#fn main() {
let mut x = 0;
let y = &x;
// OK: can read x
println!("{}", x);
// Error: cannot write `x` while it is borrowed
x = 1;
#}

# #![allow(unused_variables)]
#fn main() {
let mut x = 0;
let y = &mut x;
// Error: cannot read `x` while it is mutably borrowed
println!("{}", x);
#}

# #![allow(unused_variables)]
#fn main() {
let mut x = 0;
let y = &mut x;
let z = &mut *y;
// Error: cannot read `y` while it is mutably reborrowed.
println!("{}", y);
#}

A borrow expires when the reference goes out of scope.

# #![allow(unused_variables)]
#fn main() {
let mut x = 1;
{
    let y = &mut x;
}
// OK: because `y` went out of scope, we can use `x` again.
x = 2;
#}

The lifetime of a variable is from where it is bound to where it goes out of scope. Each reference has a lifetime that must be contained in the lifetime of the borrowed content. Often we can find the lifetime of a reference by finding where it is bound and where it goes out of scope, but not always.

# #![allow(unused_variables)]
#fn main() {
// This function doesn't compile due to lifetime errors.
fn max(x: &i32, y: &i32) -> &i32 {
    if *x > *y {
        x
    } else {
        y
    }
}
#}

The above function takes two references as parameters, but we don't know their lifetimes because the lifetimes depend on the caller. When the program calls max() in different functions, the parameters x and y have different lifetimes.

Why need we worry about lifetime in the above example? Consider

# #![allow(unused_variables)]
#fn main() {
// Error: cannot determine which input lifetime should become the output lifetime.
fn max(x: &i32, y: &i32) -> &i32 {
    if *x > *y {
        x
    } else {
        y
    }
}

let x = 1;
let z;
let y = 2;
// Error: lifetime
z = max(&x, &y)
#}

If x is greater than y, then z refers to x, so you might think that this is OK because x outlives z. However, if x is smaller than y, then z refers to y, but this is illegal because z outlives y. (Remember: each let statement creates an implicit scope.) This causes a problem for the compiler. To decide if the above program is legal, the compiler would have to examine the implementation of max() to decide whether max() would return x or y, but this is not only complicated but also undecidable at compile time in many cases.

To be practical, Rust's borrow checker, the component that verifies if borrows are valid, examines each function independently (a.k.a. intra-procedural analysis). When a function calls another function, the borrow checker relies on the callee's specification of the lifetimes of its parameters and return value instead of analyzing the callee's implementation. For each parameter or return value that is a reference, the program must specify its lifetime using a lifetime parameter.

# #![allow(unused_variables)]
#fn main() {
fn max<'a>(x: &'a i32, y: &'a i32) -> &'a i32 {
    if *x > *y {
        x
    } else {
        y
    }
}
#}

The function max() declares one lifetime parameter 'a and specifies that both the parameter x and y and the return value have the same lifetime 'a. You might wonder if the program could specify different lifetimes for x and y, as in:

# #![allow(unused_variables)]
#fn main() {
// This function doesn't compile due to lifetime errors.
fn max<'a, 'b>(x: &'a i32, y: &'b i32) -> &? i32 {
    if *x > *y {
        x
    } else {
        y
    }
}
#}

But what will be the lifetime of the return value? Since the return value could be either x or y, its lifetime must be contained in the lifetimes of both x and y, i.e., be contained in both 'a and 'b. But since the lifetimes 'a and 'b are independent, we would have to declare a new fresh lifetime, say 'c, and require that 'c be contained in both 'a and 'b. But the lifetime of neitherx nor y satisfies 'c, so the function has no eligible values to return. This contradiction shows that both the parameter x and y must have the same lifetime.

The lifetimes of a function's parameters are called the input lifetimes, and the lifetime of its return value is called the output lifetime. The output lifetime must be greater than the scope of the function, since the function's caller will use the return value. Usually the output lifetime must come from one of the input lifetimes. Since each input lifetime is greater than the scope of the function, this guarantees that the output lifetime is valid. However, there are two exceptions to this rule.

• The output lifetime is 'static.

# #![allow(unused_variables)]
#fn main() {
fn foo() -> &'static str {
    // Borrowed strings, `&str`, have `'static` lifetime.
    "Hello, world"
}

// `X` is a static variable, similar to global variables in C/C++.
static X: i32 = 1;
fn bar() -> &'static i32 {
    // `X` has the `'static` lifetime.
    &X
}
#}

• The output lifetime 'a is different from any input lifetime, but the return value contains no reference of the lifetime 'a. This happens only when the return value contains an enum, where the enum has a variant containing a reference but the return value is another variant containing no reference. For example, this compiles:

# #![allow(unused_variables)]
#fn main() {
fn f<'a>() -> Option<&'a i32> {
    None
}
#}

However, the following does not compile because of lifetime error:

# #![allow(unused_variables)]
#fn main() {
fn f<'a>() -> Option<&'a i32> {
    let i = 0;
    // Error: `i` does not live long enough.
    Some(&i)
}
#}

Besides function parameters, structures also must specify lifetimes of its borrowed contents. See structures and methods for detail.

To prevent type mismatch, a function may not elide parameter types. However, it may elide lifetimes according to the following rules:

• Rust assigns a distinct lifetime parameter to each elided lifetime in a function’s parameters.

• If there is exactly one input lifetime, elided or not, Rust assigns that lifetime to all the elided output lifetimes.

• If one of the input parameters is &self or &mut self, Rust assigns its lifetime to all the elided output lifetimes. We will describe &self in structures and methods.

Otherwise, eliding any output lifetime is illegal.

// OK: equivalent to
// fn f<'a>(x: &'a i32, y: i32) -> &'a i32;
fn f(x: &i32, y: i32) -> &i32;

// Error: there are two input lifetimes, but which one should be the output lifetime?
// fn g<'a, 'b>(x: &'a i32, y: &'b i32) -> &? i32;
fn g(x: &i32, y: &i32) -> &i32;

// OK: explicitly specifies the output lifetime
fn h<'a, 'b>(x: &'a i32, y: &'b i32) -> &'a i32;

// OK: there is exactly one input lifetime, so it becomes the output lifetime.
// Equivalent to:
// fn i<'a>(x: &'a i32, y: &'a i32) -> &'a i32;
fn i<'a>(x: &'a i32, y: &'a i32) -> &i32;

This is an advanced topic. Revisit the program earlier:

# #![allow(unused_variables)]
#fn main() {
// Error: lifetimes `'a` and `'b` are independent, so the return value's lifetime `'a` may exceed `y`'s lifetime `'b`.
fn max<'a, 'b>(x: &'a i32, y: &'b i32) -> &'a i32 {
    if *x > *y {	
        x
    } else {
        y
    }
}
#}

This program doesn't compile, because the lifetimes 'a and 'b are independent, so the return value's lifetime 'a may exceed y's lifetime 'b. Fortunately, Rust allows you to declare that a lifetime contains another lifetime.

Definition: If 'b contains 'a, then 'b is a subtype of 'a, written as 'b: 'a.

This definition may seem counter-intuitive, but think of it this way: whenever a function needs a reference of lifetime 'a, the caller may provide a reference of lifetime 'b, because 'b contains 'a.

A function may specify the lifetime subtyping in two alternative ways:

• fn max<'a, 'b: 'a>(x: &'a i32, y: &'b i32) -> &'a i32;
• fn max<'a, 'b>(x: &'a i32, y: &'b i32) -> &'a i32 where 'b: 'a;

With lifetime subtyping, we can fix the max() function:

# #![allow(unused_variables)]
#fn main() {
fn max<'a, 'b: 'a>(x: &'a i32, y: &'b i32) -> &'a i32 {
    if *x > *y {	
        x
    } else {
        // OK: because `'b` is a subtype of `'a`
        y
    }
}

let x = 1;
let y = 2;
let z = max(&x, &y);
#}

Curiously, if you swap &x and &y when calling max(), the program still compiles (I changed some variable names in the program to avoid confusion in the explanation below):

# #![allow(unused_variables)]
#fn main() {
fn max<'a, 'b: 'a>(x: &'a i32, y: &'b i32) -> &'a i32 {
    if *x > *y {	
        x
    } else {
        // OK: because `'b` is a subtype of `'a`
        y
    }
}

let u = 1;
let v = 2;
// OK: this may seem counter-intuitive, but it works as explained below.
let z = max(&u, &v);
#}

What happens is the following. At the call site max(&u, &v), Rust tries to find the largest lifetimes for the lifetime parameters 'a and 'b that satisfy all the following. Let LT(x) denote the lifetime of the variable x.

• LT(u) >= 'a, because &u is passed as the first parameter to max(), so LT(u) must be either equal to 'a or a subtype of 'a (i.e., x cannot outlive u).
• LT(v) >= 'b, because &v is passed as the second parameter to max(), so LT(v) must be equal to 'b or a subtype of 'b (i.e., y cannot outlive v).
• 'a <= 'b, because of <'a, 'b: 'a> in the signature of max().
• LT(u) > LT(v), because an implicit scope starts just before let v = 2;.

The largest solution to the above equations is 'a = LT(v) and 'b = LT(v).

Next, let us examine the assignment

let z = max(&u, &v);

Since

• max returns a reference to a value whose lifetime is 'a (because of max's signature),
• 'a = LT(v) (as shown above),
• LT(z) < LT(v) (because an implicit scope starts just before let z),

this assignment satisfies the borrow checker.

A robust program should handle errors gracefully. For example, a function for computing the square root should indicate an error when the input is negative. But how to notify the caller of this error?

The simplest approach is to reserve a special return value for error. For example:

# #![allow(unused_variables)]
#fn main() {
fn sqrt(x: f64) -> f64 {
    if x < 0.0 {
        -1.0
    } else {
        // Ignore the actual computation of the square root of `x`
        x
    }
}
#}

But this approach has two shortcomings. First, what if there is no such special value, i.e., all values of the return type are potentially valid? For example, a function reads a file and returns the content as a byte array. Since any byte array value could be the content of some file, there is no special byte array value for indicating errors. Second, the compiler cannot force the caller to check for errors, but ignoring errors may lead to disasters.

Some languages introduce exceptions to report errors. For example:

def sqrt(x):
    if x < 0:
        raise Exception
    ...

This approach also has shortcomings. First, the compiler cannot force the caller to check for errors. Second, even if the caller wishes to check for errors, it would be difficult to find all the potential exceptions that may be raised in the function.

Rust doesn't provide exceptions. Instead, Rust provides the enumeration type, which can handle errors and much more.

An enumeration type, enum, contains several variants. Each variant has one of three forms:

1. a name only.
2. a name and a set of values.
3. a name and a sequence of (name: value) pairs.

# #![allow(unused_variables)]
#fn main() {
enum Object {
    // This variant has only a name.
    Foo,
    // This variant has a name and a sequence of values.
    Bar(i32, bool),
    // This variant has a name and a set of (name: value) pairs.
    Baz{ x: i32, y: bool },
}

let x = Object::Foo;
let y = Object::Bar(1, true);
let z = Object::Baz{ x: 1, y: true };
#}

When a variant has a name and a set of values (the second form above), it may be used as a function, whose parameter values are the values in the variant and whose return type is this enum.

# #![allow(unused_variables)]
#fn main() {
#[derive(Debug)]
enum Object {
    // This variant has only a name.
    Foo,
    // This variant has a name and a sequence of types.
    Bar(i32, bool),
    // This variant has a name and a set of (name: types) pairs.
    Baz{ x: i32, y: bool },
}

let f: fn(i32, bool) -> Object = Object::Bar;
println!("{:?}", f(1, true));
#}

An enum type has one or more variants, but an enum variable contains one and only one of those variants. To find which variant an enum variable contains and to extract the values in the variant, if any, use the match expression.

A match expression contains a head expression (the expression after the match keyword) and a sequence of branches. A branch has the form pattern => expression. match examines the patterns from top to bottom. If a pattern matches the head expression, the expression on that branch becomes the value of this match expression.

# #![allow(unused_variables)]
#fn main() {
#[derive(Debug)]
enum Color {
    Red,
    Yellow,
    Green,
}

enum Fruit {
    Orange,
    // The `bool` value represents if the banana is ripe.
    Banana(bool),
    Apple{ color: Color },
}

fn print(x: Fruit) {
    match x {
        Fruit::Orange => println!("Orange"),
        // The variable `ripe` is bound to the value in this variant.
        Fruit::Banana(ripe) => println!("Banana is {}", 
            if ripe { "ripe" } else { "raw" }),
        // The variable `color` is bound to the value named `color` in this variant.
        Fruit::Apple{ color } => println!("Apple is {:?}", color),
    }
}
#}

The above example illustrate several features of the match expression.

• If a pattern is a variant of an enum, it must be qualified by the name of the enum, e.g., use Fruit::Orange instead of Orange.

• If a variant has data, the program may capture the data by pattern matching. E.g., if x is Fruit::Apple, the program may capture the value of color in the variant by the pattern Fruit::Apple(color), which binds a new name color to the value. Note that as we described in scope, whenever we rebind a name in a nested scope, it may shadow the same name in the parent scope.

• The patterns must be exhaustive, i.e., they must cover all the variants in the enum.

The match expression can be used on types other than enum.

# #![allow(unused_variables)]
#fn main() {
fn f(x: i32) {
    println!("{}", match x {
        0 => "zero",
        1 => "one", 
        2 | 3 | 4 => "two, three, four",
        5 ... 9 => "five -- nine",
        _ => "other",
    });
}
#}

This example illustrates that a pattern may use

• | to specify multiple values.
• ... to specify a range of values.
• _ to specify the rest of the values. Since match examines all the patterns from top to bottom, _ must appear as the last pattern.

Because the expression of the matched branch becomes the value of the match expression, the above match expression returns a string value.

When matching an enum variant with data, a program may use .. to ignore some data.

# #![allow(unused_variables)]
#fn main() {
enum Shape {
    Circle{ x: i32, y: i32, r: i32 },
    Rectangle{ x: i32, y: i32, w: i32, h: i32},
}
    
let s = Shape::Circle{ x: 0, y: 0, r: 10 };
println!("{}", match s {
    // Bind new names `a`, `b`, `c`
    Shape::Circle{ x: a, y: b, r: c } => format!("Circle {} {} {}", a, b, c),
    // Ignore all the fields except `x` and `y`
    Shape::Rectangle{ x, y, .. } => format!("Rectangle {} {}", x, y),
    });
#}

When binding a name, the program moves the value, which may sometimes be undesirable.

# #![allow(unused_variables)]
#fn main() {
#[derive(Debug)]
enum Color {
    Red,
    Yellow,
    Green,
}

#[derive(Debug)]
enum Fruit {
    Orange,
    // The `bool` value represents if the banana is ripe.
    Banana(bool),
    Apple{ color: Color },
}

fn print(x: Fruit) {
    match x {
        // `color` in `x` is moved into the new variable `color`.
        Fruit::Apple{ color } => println!("Apple is {:?}", color),
        _ => (),
    }

    // Error: x may have been partially moved because `color` in `Fruit::Apple` may have been moved.
    println!("{:?}", x);
}
#}

To avoid moving values in variants, use ref or ref mut in the pattern.

# #![allow(unused_variables)]
#fn main() {
#[derive(Debug)]
enum Color {
    Red,
    Yellow,
    Green,
}

#[derive(Debug)]
enum Fruit {
    Orange,
    // The `bool` value represents if the banana is ripe.
    Banana(bool),
    Apple{ color: Color },
}

fn print(x: Fruit) {
    match x {
        // The name `color` is a reference to `color` in `Fruit::Apple(color)`
        // so no move of values here.
        Fruit::Apple{ ref color } => 
            // No need to dereference `color` because of auto-deref
            println!("Apple is {:?}", color),
        _ => (),
    }

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

You may use match guard to conditionally match patterns.

# #![allow(unused_variables)]
#fn main() {
#[derive(Debug)]
enum Color {
    Red,
    Yellow,
    Green,
}

#[derive(Debug)]
enum Fruit {
    Orange,
    // The `bool` value represents if the banana is ripe.
    Banana(bool),
    Apple{ color: Color },
}

fn print(x: Fruit) {
    match x {
        Fruit::Banana(ripe) if ripe => println!("Ripe banana"),
        // Alternatively, `Banana(ripe) if !ripe => println!("Raw Banana"),`
        Fruit::Banana(ripe) => println!("Raw Banana"),
        _ => (),
    }

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

Let's revisit our initial motivation for the enum type: error handling. To differentiate normal return values from errors, let's define

# #![allow(unused_variables)]
#fn main() {
enum Option {
    Some(f64),
    None,
}

fn sqrt(x: f64) -> Option {
    if x < 0.0 {
        Option::None
    } else {
        // Ignore the actual computation of the square root of `x`
        Option::Some(x)
    }
}

match sqrt(-1.0) {
    Option::Some(v) => println!("{}", v),
    Option::None => println!("Invalid argument"),
}
#}

Use Option as the return type has these advantages:

• It unambiguously differentiates normal return values from errors.
• The caller cannot forget to check for error, because the return type is Option instead of f64. The caller extracts the value in Option by match.

Option is so useful that it is defined in Rust's standard library. During testing, the program is sometimes just interested in the value in Some and doesn't care about None. In this case, the program can extract the value in Some by unwrap():

# #![allow(unused_variables)]
#fn main() {
// `Option<f64> is a generic enum, to be discussed in later chapters.
fn sqrt(x: f64) -> Option<f64> {
    if x < 0.0 {
        None
    } else {
        // Ignore the actual computation of the square root of `x`
        Some(x)
    }
}

println!("{}", sqrt(1.0).unwrap());
#}

When sqrt() returns None, unwrap() panics (the thread crashes). The following shows a simplified implementation of unwrap():

# #![allow(unused_variables)]
#fn main() {
fn unwrap(x: Option) -> f64 {
    match x {
        Some(v) => v,
        None => panic!("..."),
    }
}
#}

If a program is interested in only one variant of an enum and wishes to test if a variable has this variant, it can use if let:

# #![allow(unused_variables)]
#fn main() {
#[derive(Debug)]
enum Color {
    Red,
    Yellow,
    Green,
}

#[derive(Debug)]
enum Fruit {
    Orange,
    // The `bool` value represents if the banana is ripe.
    Banana(bool),
    Apple{ color: Color },
}

fn print(x: Fruit) {
    if let Fruit::Banana(ripe) = x {
        println!("ripe banana");
    }
}
#}

You should use if let sparingly. Use it only when you are interested in only one variant and don't care about the others. Otherwise, use match instead, because match enforces exhaustive matching to prevent errors but if let doesn't. The following is an anti-pattern for Rust:

# #![allow(unused_variables)]
#fn main() {
enum Color {
    Red,
    Yellow,
    Green,
}

fn f(x: Color) {
    // Anti-pattern
    if let Color::Red = x {
        println!("red");
    } else if let Color::Yellow = x {
        println!("yellow");
    }
    // Oops: forgot to match `Color::Green`
}
#}

Rust isn't an object-oriented language (whatever that means). For example, Rust doesn't force you to place everything in classes, unlike Java. However, Rust does provide some object-oriented features, and designed these features better than Java and C++.

Object-oriented paradigm has three pillars:

• Encapsulation
• Inheritance
• Polymorphism

Encapsulation means to package the data and operations on them together. Rust provides encapsulation by structures and methods.

A structure contains a sequence of data, called fields.

# #![allow(unused_variables)]
#fn main() {
struct Apple {
    color: i32,
    weight: f64,
}

let fuji = Apple{ color: 1, weight: 1.2 };
assert_eq!(fuji.color, 1);
assert_eq!(fuji.weight, 1.2);
#}

If you wish to modify the fields of a struct, you must bind the struct to a mutable variable. Mutability is a property of variable binding, meaning that a program

• may not declare a field of a struct to be mutable.
• may bind the same struct to both immutable and mutable variables.

# #![allow(unused_variables)]
#fn main() {
struct Apple {
    color: i32,
    weight: f64,
}

let fuji = Apple{ color: 1, weight: 1.2 };
let mut golden = Apple{ color: 2, weight: 0.8 };
golden.weight = 1.2;
#}

You may create a struct variable from an existing variable of the same type.

# #![allow(unused_variables)]
#fn main() {
struct Apple {
    color: i32,
    weight: f64,
}

let fuji = Apple{ color: 1, weight: 1.2 };
// `golden` takes the value for the `weight` field from `fuji`.
let golden = Apple{ color: 2, .. fuji };
assert_eq!(golden.weight, 1.2);
#}

In tuple structs, fields have types but not names. A program accesses the fields of a struct by their indices using the . operator, e.g., .0.

struct Apple (i32, f64);

let fuji = Apple(1, 1.2);
assert_eq!(fuji.0, 1);
assert_eq!(fuji.1, 1.2);

A unit-like struct is a struct with no field.

struct Nothing {}
let x = Nothing{};

They are similar to the unit type (), an empty tuple, but there is a difference. Tuples are unnamed, so there is only one unit type. However, since structs have names, you may create many different unit-like structs. Unit-like structs are useful when you wish to use a data type that contains no value but that doesn't implement the Copy trait.

struct Nothing {}
let x = Nothing{};
// `x` is moved into `y`.
let y = x;
// Cannot use `x` any more.

Unlike C++, Java, or Python, Rust separates data and operations on them. A program defines data in structures, and operations on them in the implementation block for the structure. These operations are called methods.

Like Python, Rust passes the value on which the method is invoked to the method as the first parameter. But unlike Python, self is a keyword in Rust. If the first parameter is &self, it gets a shared reference to the struct; if it is &mut self, it gets a mutable reference; if it is self, the caller's value is moved into it.

# #![allow(unused_variables)]
#fn main() {
struct Apple {
    color: i32,
    weight: f64,
}

impl Apple {
    fn get_color(&self) -> i32 {
        self.color
    }
    
    fn set_color(&mut self, color: i32) {
        self.color = color
    }
    
    fn consume(self) {
    }

    // Similar to a *constructor* in C++/Java
    fn new(color: i32, weight: f64) -> Apple {
        Apple{ color: color, weight: weight }
    }
    
}

// Constructors
let mut fuji = Apple::new(1, 1.2);
let mut golden = Apple::new(2, 0.9);
// &self
assert_eq!(fuji.get_color(), 1);
assert_eq!(Apple::get_color(&golden), 2);
// &mut self
fuji.set_color(2);
assert_eq!(fuji.get_color(), 2);
Apple::set_color(&mut golden, 3);
assert_eq!(golden.get_color(), 3);
// self
fuji.consume();
Apple::consume(golden);
// Error: `fuji` is moved.
// fuji.get_color();
// Error: `golden` is moved.
// golden.get_color();
#}

You may call a method in two ways:

• Use the . operator on the struct value, e.g., fuji.get_color(). In this case, the compiler automatically takes a reference to fuji and passes it to the &self parameter of get_color().

• Call the method as a function and pass the struct value as the first argument, e.g., Apple::get_color(&fuji). Note that you must qualify the method name get_color with the struct name Apple using the :: operator. Also you must take a reference of fuji explicitly and pass it to the function.

The function new() in Apple takes no self, &self, or &mut self parameter. Therefore, a program need not (and cannot) call new() on a value. Instead, the program calls Apple::new() directly to create a new value. Such functions are called associated functions. They are similar to constructors in C++ or Java, but

• they aren't automatically invoked when binding new variables (unlike C++). The program must call them explicitly.

// Doesn't call `Apple::new()`
let fuji: Apple;
// Doesn't call `Apple::new()`
let fuji = Apple;
// Call `Apple::new()` explicitly
let fuji = Apple::new();

• they may have any names. new isn't a keyword in Rust, although it is conveniently and conventionally used.

Rust provides a keyword Self to represent the struct that the implementation block is for. Therefore, the following two declarations are equivalent:

impl Apple {
    // These two declarations are equivalent.
    fn new(color: i32, weight: f64) -> Apple { ... }
    fn new(color: i32, weight: f64) -> Self { ... }
}

In fact, &self is a syntactic sugar for self: &Self, and &mut self for self: &mut Self.

If a struct contains a reference, it must specify the lifetime of the reference explicitly.

# #![allow(unused_variables)]
#fn main() {
let name = "Fuji";

struct Apple<'a> {
    color: i32,
    weight: f64,
    name: &'a str,
}

let fuji = Apple{ color: 1, weight: 1.2, name: name };
assert_eq!(fuji.name, name);
#}

In the program, 'a is not the lifetime of the structure value fuji itself, but is the lifetime of the borrowed content. We call 'a the inner lifetime, and 'b (the lifetime of the structure value fuji) the outer lifetime. Their relationship is as follows.

Since the structure value contains the borrowed content, the outer lifetime must not outlive the inner lifetime, so 'a: 'b. See lifetime subtyping.

If a program has an (outer) reference to a structure value that contains a (inner) reference, it can retrieve the inner reference, but the lifetime of the retrieved reference depends on whether the inner reference is shared or mutable.

• If the inner reference is mutable, then the lifetime of the retrieved reference, either shared or mutable, is the same as that of the outer reference.

# #![allow(unused_variables)]
#fn main() {
struct Foo<'a> {
    x: &'a mut i32,
}

impl<'a> Foo<'a> {
    // Error: `'a` outlives the lifetime of `self`
    fn get(&self) -> &'a i32 {
        self.x
    }

    // OK. This is equivalent to `fn get2<'b>(&'b self) -> &'b i32`
    fn get2(&self) -> &i32 {
        self.x
    }
}
#}

• But if the inner reference is shared, then the lifetime of the retrieved reference can be that of the inner reference, which is larger than that of the outer reference.

# #![allow(unused_variables)]
#fn main() {
struct Foo<'a> {
    x: &'a i32,
}

impl<'a> Foo<'a> {
    // OK
    fn get(&self) -> &'a i32 {
        self.x
    }
}
#}

The reason for the difference is as follows. In the first case, the structure value acquired exclusive access to the inner value via the mutable inner reference. When the structure value goes out of scope, this exclusive access expires, so any reference to the inner value that the program acquired via the outer reference must also expire.

The second case works because the shared access to the inner value is valid throughout the lifetime of the inner reference, so it is no harm to return the inner reference with this lifetime.

In mathematics, we often express abstract concepts, e.g.,

swap(x, y): swaps the values x and y.

However, in Rust, since a program must declare the types of its parameters, it would have to define a separate swap() function for each type of x and y, e.g.,

# #![allow(unused_variables)]
#fn main() {
fn swap_i32(x: i32, y: i32) -> (i32, i32) {
    (y, x)
}
        
fn swap_f64(x: f64, y: f64) -> (f64, f64) {
    (y, x)
}
        
let (a, b) = (1, 2);
let (x, y) = swap_i32(a, b);
assert_eq!(x, 2);
assert_eq!(y, 1);

let (a, b) = (1.0, 2.0);
let (x, y) = swap_f64(a, b);
assert_eq!(x, 2.0);
assert_eq!(y, 1.0);
#}

While this solution works, it is unsatisfactory because it is repetitive. swap_i32() and swap_f64() are identical except for the parameter types. To overcome this limitation, Rust allows a program to use generic types, where instead of a concrete type such as i32 or f64, a generic type T can represent any concrete type. It works as follows:

1. Declare a type parameter in <> right after the function name.
2. Use the type parameter in the types of parameters, return value, or variables in the function body.

fn swap<T>(x: T, y: T) -> (T, T) {
    (y, x)
}
        
let (a, b) = (1, 2);
let (x, y) = swap(a, b);
assert_eq!(x, 2);
assert_eq!(y, 1);

let (a, b) = (1.0, 2.0);
let (x, y) = swap(a, b);
assert_eq!(x, 2.0);
assert_eq!(y, 1.0);

When the program above calls swap(), Rust infers the concrete type for the type parameter T based on the types of function parameters. For example, when the program calls swap(x, y) and both x and y are i32, then Rust infers that T is i32. If, however, the types of x and y are different, the type inference fails, so Rust issues an error.

# #![allow(unused_variables)]
#fn main() {
fn swap<T>(x: T, y: T) -> (T, T) {
    (y, x)
}

let (a, b) = (1, 2.0);
// Error: cannot infer the concrete type of type parameter `T`
let (x, y) = swap(a, b);
#}

Occasionally, the compiler cannot infer the concrete type of T reliably. In this case, the program can explicitly state the concrete type by type hint:

# #![allow(unused_variables)]
#fn main() {
fn swap<T>(x: T, y: T) -> (T, T) {
    (y, x)
}

let (a, b) = (1, 2);
// `::<i32>` is a *type hint* stating the concrete type of the type parameter `T`
let (x, y) = swap::<i32>(a, b);
#}

We saw the use of the enum type Option to represent both a valid value Some() and an error None. To allow Option to represent values of any types, we declare a type parameter T and use it as the type of the value in Some().

# #![allow(unused_variables)]
#fn main() {
enum Option<T> {
    Some(T),
    None,
}

// Type inference: T is i32
let x = Option::Some(1);
// Type hint
let x = Option::Some::<i32>(1);
// Type inference: T is f64
let x = Option::Some(1.0);
// Type hint
let x = Option::Some::<f64>(1.0);
#}

If we wish to distinguish between different types of errors, we could use Result<T, E>, which takes two type parameters.

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

struct MemoryError {}

struct IoError {}

// Type inference: `T` is `i32` and `E` is `MemoryError`
let mut x = Result::Ok(1);
x = Result::Err(MemoryError{});

// Type hint
let y = Result::Ok::<f64, IoError>(1.0);
let z = Result::Err::<f64, IoError>(IoError{});
#}

Note that in the following program, Rust cannot infer the concrete types of all the type parameters, so the program must provide adequate type hints or explicitly declare the types of the variables.

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

struct MemoryError {}

struct IoError {}

// Must provide the concrete type of `E`
let x = Result::Ok::<_, MemoryError>(1);
// Alternatively, declare its type.
let x: Result<_, MemoryError> = Result::Ok(1);
// Must provide the concrete type of `T`
let y = Result::Err::<i32, _>(IoError{});
// Alternatively, declare its type.
let y: Result<i32, _> = Result::Err(IoError{});
#}

You may also define generic structs.

struct Polygon<T> {
    center: (T, T),
    radius: T,
    sides: i32,
}

impl<T> Polygon<T> {
    fn get_sides(&self) -> i32 {
        self.sides
    }
}

let x = Polygon{ center: (0.0, 1.0), radius: 1.0, sides: 5 };
assert_eq!(x.get_sides(), 5);

Generics are called parametric polymorphism, because they provide multiple forms (polymorphism) via type parameters. Consistent with Rust's philosophy of zero-cost abstraction, generics incur no runtime cost thanks to monomorphization, or "converting to single forms".

For each generic item (function, enum, or struct), and for each unique assignment of concrete types to the item's type parameters, Rust creates a separate copy of the item where it replaces all the type parameters with their corresponding concrete types.

For example, the following generic program

# #![allow(unused_variables)]
#fn main() {
fn swap<T>(x: T, y: T) -> (T, T) {
    (y, x)
}
        
let (a, b) = (1, 2);
let (x, y) = swap(a, b);

let (a, b) = (1.0, 2.0);
let (x, y) = swap(a, b);
#}

after monomorphization, becomes

# #![allow(unused_variables)]
#fn main() {
fn swap_i32(x: i32, y: i32) -> (i32, i32) {
    (y, x)
}
        
fn swap_f64(x: f64, y: f64) -> (f64, f64) {
    (y, x)
}
        
let (a, b) = (1, 2);
let (x, y) = swap_i32(a, b);

let (a, b) = (1.0, 2.0);
let (x, y) = swap_f64(a, b);
#}

In other words, the compiler converts the generic program to the original one without generics that we wrote by hand! Generics allow the programmer to focus on the algorithms while abstracting away concrete data types, leaving the boring monomorphization to the compiler. This is similar to how C++ handles generics (called templates in C++), but different than how Java handles generics (via type erasure).

Generics allow a program to reuse the same algorithm on different data types. However, sometimes an algorithm applies to only certain types.

# #![allow(unused_variables)]
#fn main() {
struct Rectangle {
    x: i32,
    y: i32,
    w: i32,
    h: i32,
}

impl Rectangle {
    fn area(&self) -> i32 {
        self.w * self.h
    }
}

struct Square {
    x: i32,
    y: i32,
    w: i32,
}

impl Square {
    fn area(&self) -> i32 {
        self.w * self.w
    }
}

// Error: `T` is not guaranteed to have the `area()` method.
fn print_area<T>(x: T) {
    println!("{}", x.area());
}
#}

In the above program, the function print_area() declares no restriction on the type parameter T, but not all types have the method area(). For example, it makes no sense for the program to call print_area(1), because i32 has no method area(). Rust provides traits to restrict what concrete types may instantiate a type parameter.

A trait U declares a set of methods that a type must implement. When a type V implements U, it must implement all of U's methods in an implementation block. Similar to the implementation block of a struct, in the implementation block of a trait, the program may use the keyword Self to refer to the type V, and a method f may use the keyword self to refer to the value on which f is called.

When the program declares a type parameter T, it can specify that only types that implement a trait U may instantiate T. In other words, the program places a trait bound U on T.

# #![allow(unused_variables)]
#fn main() {
trait Area {
    fn area(&self) -> i32;
    fn new() -> Self;
}

struct Rectangle {
    x: i32,
    y: i32,
    w: i32,
    h: i32,
}

impl Area for Rectangle {
    fn area(&self) -> i32 {
        self.w * self.h
    }

    fn new() -> Self {
        Rectangle{ x: 0, y: 0, w: 1, h: 1 }
    }
}

struct Square {
    x: i32,
    y: i32,
    w: i32,
}

impl Area for Square {
    fn area(&self) -> i32 {
        self.w * self.w
    }

    fn new() -> Self {
        Square{ x: 0, y: 0, w: 1 }
    }
}

// OK: `T` is bounded by `Area`.
fn print_area<T: Area>(x: T) {
    println!("{}", x.area());
}

// OK: `T` is bounded by `Area`.
fn new_area<T: Area>() -> T {
    // Since `new()` doesn't take any value, we must call `new()` directly.
    T::new()
}

// Need either type declaration or type hint for x
let x: Rectangle = new_area();
let y = new_area::<Square>();
// Ok
print_area(x);
print_area(y);
// Error: `i32` doesn't implement `Area`.
// print_area(1);
// Error: cannot infer the concrete type for the type parameter
// let x = new_area();
#}

A type may implement multiple traits, and a type parameter may require multiple trait bounds.

# #![allow(unused_variables)]
#fn main() {
trait Area {
    fn area(&self) -> i32;
    fn new() -> Self;
}

trait Transform {
    fn scale(&mut self, s: i32);
}

struct Square {
    x: i32,
    y: i32,
    w: i32,
}

impl Area for Square {
    fn area(&self) -> i32 {
        self.w * self.w
    }

    fn new() -> Self {
        Square{ x: 0, y: 0, w: 1 }
    }
}

impl Transform for Square {
    fn scale(&mut self, s: i32) {
        self.w *= s;
    }
}

// A concrete type for `T` must implement both `Area` and `Transform`
fn scale<T: Area + Transform>(mut x: T, s: i32) {
    println!("Before scale: {}", x.area());
    x.scale(s);
    println!("After scale: {}", x.area());
}

fn new_area<T: Area>() -> T {
    // Since `new()` doesn't take any value, we must call `new()` directly.
    T::new()
}

let mut x: Square = new_area();
scale(x, 2);
#}

Instead of specifying the trait bounds when declaring a type parameter, a method may specify the trait bounds after declaring all the parameters and return type, in a where clause.

# #![allow(unused_variables)]
#fn main() {
// Equivalent to `fn scale<T: Area + Transform>(mut x: T, s: i32)`
fn scale<T>(mut x: T, s: i32) where T: Area + Transform {
    println!("Before scale: {}", x.area());
    x.scale(s);
    println!("After scale: {}", x.area());
}
#}

The where clause is more expressive because more than just the type parameter may appear at the left of the colon.

trait MyInto<T> {
    fn my_into(self) -> T;
}

impl MyInto<String> for i32 {
    fn my_into(self) -> String {
        format!("{}", self)
    }
}

impl MyInto<bool> for i32 {
    fn my_into(self) -> bool {
        self != 0
    }
}

fn inverse_convert<T>(x: i32) -> T
    where i32: MyInto<T>
{
    (-x).my_into()
}

fn main() {
    let x: bool = inverse_convert(1);
    assert_eq!(x, true);
    let x: String = inverse_convert(1);
    assert_eq!(x, "-1");
}

A trait declares a set of methods, and a type implementing the trait must implement all the methods. Sometimes, a trait may provide default implementation of some methods. If a type implementing the trait does not accept the default implementation, it may reimplement these methods.

# #![allow(unused_variables)]
#fn main() {
trait PartialEq {
    fn eq(&self, other: &Self) -> bool;
    
    // Default method
    fn ne(&self, other: &Self) -> bool {
        !self.eq(other)
    }
}

struct Square {
    x: i32,
    y: i32,
    w: i32,
}

impl PartialEq for Square {
    fn eq(&self, other: &Self) -> bool {
        self.x == other.x && self.y == other.y && self.w == other.w
    }
    
    // Accepts the default method `PartialEq::ne()`, so does not reimplement it.
}

struct Rectangle {
    x: i32,
    y: i32,
    w: i32,
    h: i32,
}

impl PartialEq for Rectangle {
    fn eq(&self, other: &Self) -> bool {
        self.x == other.x && self.y == other.y && self.w == other.w && self.h == other.h
    }
    
    // Reimplements the default method `ne()`.
    fn ne(&self, other: &Self) -> bool {
        self.x != other.x || self.y != other.y || self.w != other.w || self.h != other.h
    }
}
#}

A trait A may inherit another trait B, meaning that any type implementing A must implement all the methods in both A and B.

# #![allow(unused_variables)]
#fn main() {
trait Area {
    fn new() -> Self;
    fn area(&self) -> i32;
}

// Any type implementing `Equal` must also implement `Area`
trait Equal: Area {
    fn eq(&self, other: &Self) -> bool;
    fn ne(&self, other: &Self) -> bool {
        !self.eq(other)
    }
}

struct Square {
    x: i32,
    y: i32,
    w: i32,
}

impl Area for Square {
    fn area(&self) -> i32 {
        self.w * self.w
    }

    fn new() -> Self {
        Square{ x: 0, y: 0, w: 1 }
    }
}

impl Equal for Square {
    fn eq(&self, other: &Self) -> bool {
        self.area() == other.area()
    }
}
#}

# #![allow(unused_variables)]
#fn main() {
trait Deref {
    type Target: ?Sized;
    fn deref(&self) -> &Self::Target;
}
#}

This trait enables deref coercion: If impl Deref<Target=U> for T, then the compiler automatically coerces &T to &U by calling Deref::deref(). For example, if t: T, then the compiler coerces &t to t.deref().

If a variable t is not a reference, the compiler automatically takes a reference of t in the following context:

• *t: the compiler changes this expression to *((&t).deref()).
• t.f(): the compiler changes this expression to (&t).deref().f().

# #![allow(unused_variables)]
#fn main() {
use std::ops::Deref;

struct Foo<'a>(&'a str);

impl<'a> Deref for Foo<'a> {
    type Target = str;
    fn deref<'b>(&'b self) -> &'b Self::Target {
        self.0
    }
}

let s = "Rust";
let foo = Foo(s);
assert_eq!(s.len(), foo.len());
#}

A similar trait is DerefMut, which also enables deref coercion.

trait DerefMut: Deref {
    fn deref_mut(&mut self) -> &mut Self::Target;
}

Deref coercion is commonly used to abstract the distinction between borrowed values and owned values when the distinction is inconsequential to the code in question. Rust provides three types of pointers:

• &T: contains a pointer to a borrowed value.
• Box<T>: contains a pointer to an owned value on the heap.
• Rc<T> and Arc<T>: each contains a pointer to a reference-counted value on the heap. We will discuss these in concurrency.

These pointers differ in how the program manages the memory of their values. But sometimes a function only accesses the values without caring about their memory management. In this case, it would be laborious to write two versions of the same function where the only difference is the type of pointers that the function takes.

# #![allow(unused_variables)]
#fn main() {
fn f(x: &i32) {
    println!("{}", x);
}

fn g(x: &Box<i32>) {
    println!("{}", x);
}

fn h() {
    f(&1);
    g(&Box::new(2));
}
#}

It would be nice to write only one function that can handle both borrowed and owned pointers. To allow this, Rust's standard library implements the Deref trait for Box:

# #![allow(unused_variables)]
#fn main() {
impl<T> Deref for Box<T> where T: ?Sized {
    type Target = T;
}
#}

This instructs the compiler to coerce &Box<T> to &T. Therefore, we can remove the function g() and the above program still compiles.

# #![allow(unused_variables)]
#fn main() {
fn f(x: &i32) {
    println!("{}", x);
}

fn h() {
    f(&1);
    f(&Box::new(2));
}
#}

Another example of borrowed vs. owned pointers is Rust's strings. Rust provides two types of strings: &str points to a borrowed static string, and String points to an owned string on the heap. String implements the Deref trait to allow deref coercion to coerce &String to &str.

# #![allow(unused_variables)]
#fn main() {
impl Deref for String {
    type Target = str;
}
#}

# #![allow(unused_variables)]
#fn main() {
fn f(x: &str) {
    println!("{}", x);
}

fn g() {
    // The type of `x` is `&str`.
    let x = "abc";
    f(x);
    // The type of `y` is `String`.
    let y = "def".to_owned();
    f(&y);
}
#}

Deref coercion happens only when type mismatch would happen without the coercion.

# #![allow(unused_variables)]
#fn main() {
fn f(x: &str) {
    println!("{}", x);
}

fn g(x: &String) {
    println!("{}", x);
}

fn h() {
    // The type of `x` is `String`.
    let x = "abc".to_owned();
    // Deref coercion happens.
    f(&x);
    // Deref coercion does not happen.
    g(&x);
}
#}

Besides Deref and DerefMut, a few other traits also change the behavior of the compiler.

• Copy

By default, Rust moves values during assignment. This is called move semantics. However, if a type implements the Copy trait, Rust copies its values during assignment instead.

• Drop

The Drop trait provides a destructor. If a type implements the Drop trait, Rust invokes the drop function when its value disappears, either because it goes out of scope or because it is overwritten.

# #![allow(unused_variables)]
#fn main() {
trait Drop {
    fn drop(&mut self);
}
#}

For example,

# #![allow(unused_variables)]
#fn main() {
struct Foo(i32);

impl Drop for Foo {
    fn drop(&mut self) {
        println!("{} dropped.", self.0);
    }
}

{
    let foo = Foo(1);
    // Prints `1 dropped`
}

#}

• Sized

The sizes of most types are known at compile time. However, the sizes of some types, such as [T] and str, aren't. They are called unsized or dynamically sized types. There are restrictions on these types.

• The program may manipulate the value of an unsized type only via a pointer.
• Variables and parameters may not be unsized.
• Only the last field in a struct may be unsized.

The Sized trait indicates that a type is sized. Since most types are sized, all type parameters have the implicit Sized bound (i.e., T: Sized is implicit for all type parameters T). For example, the following code doesn't compile:

# #![allow(unused_variables)]
#fn main() {
fn f<T>(t: &T) {
}

let a = [1, 2, 3];
// `a[..]` is of type `[i32]` and is therefore unsized.
// So this does not compile.
f(&a[..]);
#}

The ?Sized trait overrides the implicit Sized bound. It allows the concrete type to be unsized.

# #![allow(unused_variables)]
#fn main() {
fn f<T: ?Sized>(t: &T) {
}

let a = [1, 2, 3];
// `a[..]` is of type `[i32]` and is therefore unsized.
// Compiles because `T: ?Sized`
f(&a[..]);
#}

A program can request the compiler to automatically implement certain traits for a type by applying the derive attribute to the type declaration and specifying the traits in the attribute.

# #![allow(unused_variables)]
#fn main() {
// Must derive both `Copy` and `Clone` because `Copy` inherits `Clone`.
#[derive(Copy, Clone)]
struct Foo(i32);

let x = Foo(1);
// `x` is copied rather than moved.
let y = x;
assert_eq!(x.0, y.0);
#}

The following traits are derivable:

• Clone: for manually copying values.
• Copy: for selecting copy (instead of move) semantics in assignment.
• Debug: for println!("{:?}", ...)
• Default: for creating default values for the type.
• For comparisons:
  • PartialEq
  • Eq
  • PartialOrd
  • Ord
• Hash: for HashMap and HashSet.

Just like structs, traits may be generic. The following program may instantiate the type parameters T with many concrete types to create different concrete traits.

# #![allow(unused_variables)]
#fn main() {
trait MyInto<T> {
    fn my_into(self) -> T;
}

impl MyInto<String> for i32 {
    fn my_into(self) -> String {
        format!("{}", self)
    }
}

impl MyInto<bool> for i32 {
    fn my_into(self) -> bool {
        self != 0
    }
}

let x = 1;
let y: String = x.my_into();
assert_eq!(y, "1");
let y: bool = x.my_into();
assert_eq!(y, true);
#}

However, sometimes a program may wish to include type parameters in a trait, but for each type implementing the trait, it must instantiate the type parameter in only one way. For example, the trait Deref provides deref coercion, but for each type T implementing Deref, it must specify a single concrete type U where &T automatically coerces to &U.

Consider the following incorrect declaration of Deref:

// Incorrect
trait Deref<T> {
    fn deref(&self) -> &T;
}

It fails to satisfy the above requirement, because it would allow many different Us where &T coerces to &U as in the following:

// Incorrect
impl Deref<str> for String {
    fn deref(&self) -> &str { ... }
}

impl Deref<i32> for String {
    fn deref(&self) -> &i32 { ... }
}

Looking from another perspective, in MyInto<T>, the type parameter T is an input type parameter to the trait MyInto, so T may be instantiated into many different concrete types. By contrast, in Deref, the type parameter T is an output type parameter, in the sense that the concrete type implementing Deref determines a unique concrete type for T. Rust provides associated types to denote output type parameters:

# #![allow(unused_variables)]
#fn main() {
trait Deref {
    type Target;
    fn deref(&self) -> &Self::Target;
}
#}

A program declares an associated type using the keyword type in a trait declaration. When a type implements the trait, it must instantiate the associated type:

impl Deref for String {
    type Target = str;
    fn deref(&self) -> &Self::Target {
        ....
    }
}

Rust prefers explicitness. Therefore, it does implicit conversion only in a few cases. Notably, in certain cases Rust automatically takes references (autoref), dereferences (autoderef), and converts between different types of references (deref coercion). These conversions happen only when type mismatch would occur without them.

• If f(&self, ...) is a method implemented for the type T, and t is a variable of T, then the compiler converts t.f() to (&t).f(), or equivalently T::f(&t, ...).

• If t is a non-reference variable of type T and impl Deref for T, then the compiler converts *t to *(&t) and then applies deref coercion on &t.

• If f(self, ...) or f(&self, ...) is a method implemented for the type T, and t is a reference to T in one or more levels (e.g., &T, &&T, etc.), then the compiler dereferences t as many times as necessary to make the resulting type match that of the first parameter of f. E.g., if t: &&&T and f(&self, ...), then the compiler converts t.f() to (**t).f(), or equivalently T::f(**t).

If impl Deref<Target=U> for T and t is a variable of the type T, then the compiler coerces &t, either written explicitly in the program or resulting from autoref, to (&t).deref(), which is of type &U.

Generics and traits allow code reuse. A program can declare a generic item (function, enum, structure, trait) once and instantiate it with different concrete types.

Rust implements generics by monomorphization. It is efficient, as monomorphization incurs no runtime overhead. However, it doesn't allow a program to place values of different types into the same collection.

# #![allow(unused_variables)]
#fn main() {
trait Area {
    fn area(&self) -> i32;
}

struct Rectangle {
    x: i32,
    y: i32,
    w: i32,
    h: i32,
}

impl Area for Rectangle {
    fn area(&self) -> i32 {
        self.w * self.h
    }
}

struct Square {
    x: i32,
    y: i32,
    w: i32,
}

impl Area for Square {
    fn area(&self) -> i32 {
        self.w * self.w
    }
}

// Doesn't compile.
let shapes: Vec<Area>;
#}

The above program wishes to place both Rectangle and Square into the same vector, but it cannot achieve this by declaring a vector of Area, even though both Rectangle and Square implement Area. The reason is that Rectangle and Square values have different sizes, so the vector doesn't know how much memory to allocate for each element. To solve this problem, the program could store pointers to these values instead of storing the values themselves. Storing pointers avoids the size dilemma because all pointers on the same CPU architecture have the same size.

Rust provides trait objects to allow access to a value via a pointer. If T implements U, casting or coercing &T to &U creates a trait object. The program can invoke any method declared in the trait on the trait object.

# #![allow(unused_variables)]
#fn main() {
trait Area {
    fn area(&self) -> i32;
}

struct Rectangle {
    x: i32,
    y: i32,
    w: i32,
    h: i32,
}

impl Area for Rectangle {
    fn area(&self) -> i32 {
        self.w * self.h
    }
}

struct Square {
    x: i32,
    y: i32,
    w: i32,
}

impl Area for Square {
    fn area(&self) -> i32 {
        self.w * self.w
    }
}

let rectangle = Rectangle{ x: 0, y: 0, w: 1, h: 2 };
let square = Square{ x: 0, y: 0, w: 1 };
let mut shapes: Vec<&Area> = vec![];
shapes.push(&rectangle);
shapes.push(&square);
for shape in shapes {
    println!("{}", shape.area());
}
#}

Trait object raises a question on method resolution. When the program calls a method on a trait object, how does it determine which method to call, since every type implementing this trait provides this method?

Internally, a trait object is an opaque struct illustrated below. The struct is opaque because the program cannot access it directly, but can access it only indirectly via the trait object. The struct contains two pointers. The first pointer points to the value, and the second pointer points to a vtable (virtual dispatch table). If the trait contains n methods, then this vtable contains n entries where each entry points to a method implemented by the concrete type. Therefore, when the program invokes a method on a trait object, the code generated by the compiler follows the trait object to the vtable, finds the pointer to the method, and then calls the method.

# #![allow(unused_variables)]
#fn main() {
struct TraitObject {
    pub data: *mut (),
    pub vtable: *mut (),
}
#}

So far we have seen trait objects where the value lives on the stack. The type of such trait objects is &U where U is a trait. Alternatively, a program may also create trait objects where the value lives on the heap. The type of such trait objects is Box<U>. If T implements U, casting or coercing Box<T> to Box<U> creates a trait object.

# #![allow(unused_variables)]
#fn main() {
trait Area {
    fn area(&self) -> i32;
}

struct Rectangle {
    x: i32,
    y: i32,
    w: i32,
    h: i32,
}

impl Area for Rectangle {
    fn area(&self) -> i32 {
        self.w * self.h
    }
}

struct Square {
    x: i32,
    y: i32,
    w: i32,
}

impl Area for Square {
    fn area(&self) -> i32 {
        self.w * self.w
    }
}

fn static_dispatch<T: Area>(x: &T) -> i32 {
    x.area()
}

fn dynamic_dispatch(x: &Area) -> i32 {
    x.area()
}

let rectangle = Rectangle{ x: 0, y: 0, w: 1, h: 2 };
let square = Square{ x: 0, y: 0, w: 1 };
static_dispatch(&rectangle);
static_dispatch(&square);
dynamic_dispatch(&rectangle);
// or `dynamic_dispatch(&rectangle as &Area)`
dynamic_dispatch(&square);
// or `dynamic_dispatch(&square as &Area)`
#}

Rust monomorphizes the static_dispatch function. If the program calls this function with n different instantiations of the type parameter T, Rust makes n specialized copies of this function, where in each copy Rust replaces T with a different concrete type. Therefore, each copy of static_dispatch knows which area method to call since it knows the concrete type of T at compile time. This is called static dispatch.

By contrast, since the function dynamic_dispatch takes a trait object, Rust does not monomorphize it. Therefore, since the type of T is unknown at compile time, dynamic_dispatch doesn't know which area method to call at compile time. At runtime, dynamic_dispatch follows the trait object x to its vtable to look up the address of the method area. This is called dynamic dispatch.

Static dispatch is efficient, since the compiler generates a direct call to the method. However, it suffers from code bloat, since the compiler generates multiple copies of the same code. Code bloat may make the program run slow because it may reduce the hit rate of the code cache.

Dynamic dispatch does not suffer from code bloat, since the compiler generates only one copy of the function. However, it reduces performance because the compiler generates indirect calls. Specifically, the compiler generates two extra dereference instructions per dynamic dispatch:

1. Dereferencing the pointer to the vtable
2. Dereferencing the pointer to the method

Functions are first-class objects in Rust, meaning that a program may use functions in the same way as other values. For example, the program may assign a function to a variable, and then invoke the function via the variable.

# #![allow(unused_variables)]
#fn main() {
fn max(x: i32, y: i32) -> i32 {
    if x > y {
        x
    } else {
        y
    }
}

let f: fn(i32, i32) -> i32 = max;
assert_eq!(f(1, 2), 2);
#}

Rust uses the keyword fn to represent function types. A function type is parameterized by the types of its parameters and return value. For example,

# #![allow(unused_variables)]
#fn main() {
// A function type with no parameter or return value
let x: fn();
// A function type with two parameters but no return value
let y: fn(i32, bool);
// A function type with one parameter and one return value
let z: fn(i32) -> i32;
#}

If two functions take the same types of parameters and return value, if any, in the same order, they have the same type.

# #![allow(unused_variables)]
#fn main() {
fn max(x: i32, y: i32) -> i32 {
    if x > y {
        x
    } else {
        y
    }
}

fn min(x: i32, y: i32) -> i32 {
    if x < y {
        x
    } else {
        y
    }
}

let mut f: fn(i32, i32) -> i32 = max;
f = min;
assert_eq!(f(1, 2), 1);
#}

Internally, a variable of a function type contains a pointer to the function's entry point.

When a program assigns a function to a variable and later invokes the function only via the variable, the function name becomes unimportant. Rust allows a program to directly assign a function to a variable without naming the function. This is called an anonymous function.

# #![allow(unused_variables)]
#fn main() {
let a = |x: i32, y| if x > y { x } else { y };
assert_eq!(a(1, 2), 2);
let b = |x: i32, y| if x < y { x } else { y };
assert_eq!(b(1, 2), 1);
#}

A program defines an anonymous function slightly differently than a named function. The syntax is | parameter_list | body. The parameter list contains zero or more comma-separated parameter names. Unlike in named functions, the program may omit the types of parameters and return value in anonymous functions. The body contains one expression. If it needs to contain multiple statements, enclose them in curly braces (i.e., construct a block expression).

The caller calls anonymous functions in the same way as it calls named functions.

A notable difference between anonymous and named functions is type equality. Two named functions are of the same type if they contain the same types of parameters and return value in the same order. By contrast, each anonymous function has a unique type. In other words, no two anonymous functions have the same type, even if they have the same types of parameters and return value.

# #![allow(unused_variables)]
#fn main() {
let mut f = |x: i32, y: i32| if x > y { x } else { y };
// Doesn't compile: the anonymous functions above and below have different types.
f = |x: i32, y: i32| if x < y { x } else { y };
#}

Anonymous functions are not only simpler to write than named functions but also more powerful. They can access the variables defined outside them.

# #![allow(unused_variables)]
#fn main() {
let a = 1;
let f = |x| x + a;
assert_eq!(f(2), 3);
#}

In the above example, the anonymous function f uses the variable a defined outside it. We call the variables defined outside f and accessible to f the environment of f. We say f captures its environment, or closes over its environment. To emphasize this property, Rust calls anonymous functions closures.

You may wonder why we need closures, because the above example seems contrived. Closures are part of the foundation for Rust's multi-threaded programming paradigm. In this paradigm, the program creates a closure and executes it in a new thread. Since a closure captures its environment, the child thread can use variables defined in the parent thread. For more information, see concurrency.

A closure captures its environment, but there are three different ways by which a closure may use a variable in its environment:

1. Borrow by shared reference
2. Borrow by mutable reference
3. Move the value into the closure

The first option gives the code outside the closure, the enclosing code, the maximum flexibility, because the enclosing code can still read the variable. The second option gives less flexibility, because when the closure is in scope, the enclosing code cannot access the variable (because the closure is holding a mutable reference to the value); but after the closure goes out of scope, the enclosing code can continue to use the variable. The last option gives the enclosing code no flexibility, because the code can no longer access the variable after the value is moved into the closure.

The Rust compiler automatically selects the most flexible way of capture, in the order of the three options above, that satisfies the requirement of the closure.

# #![allow(unused_variables)]
#fn main() {
let mut a = vec![1, 2];
let mut b = vec![3, 4];
let mut c = vec![5, 6];
let x = || {
    // Takes `a` by shared reference
    assert_eq!(a[0], 1);
    // Takes `b` by mutable reference, because a shared reference wouldn't work
    b[0] = 1;
    // Moves `c` into the closure, because neither shared nor mutable reference
    // would work
    let d = c;
};

x();
// OK
assert_eq!(a[0], 1);
// Compiler error: `b` is already mutably referenced.
assert_eq!(b[0], 3);
// Compiler error: `c` is moved.
assert_eq!(c[0], 5);
#}

When a program sends a closure to a thread, it needs to capture the environment by moving all the values used in the closure into the closure, no matter how the closure uses them. See concurrency for a more detailed explanation. To force the compiler to capture the environment by moving values only (not by taking shared or mutable references), use the move keyword in front of the closure definition.

# #![allow(unused_variables)]
#fn main() {
let mut a = vec![1, 2];
let mut b = vec![3, 4];
let mut c = vec![5, 6];
let x = move || {
    // moves `a`, `b`, and `c` into the closure because of the `move` keyword
    assert_eq!(a[0], 1);
    b[0] = 1;
    let d = c;
};

x();
// Compiler error: `a`, `b`, and `c` are moved.
assert_eq!(a[0], 1);
assert_eq!(b[0], 3);
assert_eq!(c[0], 5);
#}

Internally, the Rust compiler transforms each closure into a struct that implements one of the three traits. Each trait declares a method that is parameterized by the types of its parameters and return value.

trait Fn<Args> : FnMut<Args> {
    extern "rust-call" fn call(&self, args: Args) -> Self::Output;
}

trait FnMut<Args> : FnOnce<Args> {
    extern "rust-call" fn call_mut(&mut self, args: Args) -> Self::Output;
}

trait FnOnce<Args> {
    type Output;

    extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
}

For each closure, the compiler

• defines an anonymous struct to represent the type of the closure. The struct contains a field for each captured variable;

• creates a value of the struct that captures the variables in the environment;

• implements one of the three above traits on the struct.

For example, Rust transforms this program

# #![allow(unused_variables)]
#fn main() {
let mut a = vec![1, 2];
let mut b = vec![3, 4];
let mut c = vec![5, 6];
let x = || {
    // Takes `a` by shared reference
    assert_eq!(a[0], 1);
    // Takes `b` by mutable reference, because a shared reference wouldn't work
    b[0] = 1;
    // Moves `c` into the closure, because neither shared nor mutable reference
    // would work
    let d = c;
};

x();
#}

to

let mut a = vec![1, 2];
let mut b = vec![3, 4];
let mut c = vec![5, 6];

// Define a struct to represent the type of the closure
struct Closure1 {
    a: &Vec<i32>,
    b: &mut Vec<i32>,
    c: Vec<i32>,
}

// Creates a value to capture the variables in the environment
let x = Closure1{ a: &a, b: &mut b, c: c };

// Implements a trait.
// This is for illustration purpose only.
impl FnOnce for Closure1 {
    fn call_once(self) {
        assert_eq!(self.a[0], 1);
        self.b[0] = 1;
        let d = self.c;
    }
}

// Calls the closure
x.call_once();

For each closure, the compiler selects one trait from Fn, FnMut, and FnOnce to implement. The compiler selects a trait that provides the most flexibility to the code outside the closure.

# #![allow(unused_variables)]
#fn main() {
let a = vec![1, 2];
// The compiler implements the `Fn` trait, because the closure needs only a 
// shared reference to `a`.
let x = || assert_eq!(a[0], 1);

let mut b = vec![1, 2];
// The compiler implements the `FnMut` trait, because the closure needs 
// a mutable reference to `b`.
let y = || b[0] = 2;

let c = vec![1, 2];
// The compiler implements the `FnOnce` trait, because the closure needs 
// to move `c`.
let z = || { let d = c; };
#}

Note the inheritance between the three traits.

trait Fn<Args> : FnMut<Args> {
    extern "rust-call" fn call(&self, args: Args) -> Self::Output;
}

trait FnMut<Args> : FnOnce<Args> {
    extern "rust-call" fn call_mut(&mut self, args: Args) -> Self::Output;
}

trait FnOnce<Args> {
    type Output;

    extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
}

This makes sense. If a closure implements Fn, it can certainly implement FnMut as well, as follows:

impl FnMut<Args> for _ {
    fn call_mut(&mut self, args: Args) -> Self::Output {
        self.call(self, args)
    }
}

Similarly, if a closure implements FnMut, it can certainly implement FnOnce as follows:

impl FnOnce<Args> for _ {
    fn call_once(self, args: Args) -> Self::Output {
        self.call_mut(&self, args)
    }
}

Each closure has a unique anonymous type, which means that a program cannot declare the type of a closure.

On the other hand, each closure implements a trait, so it can be used anywhere a value implementing the trait is accepted.

In the example below, the compiler monomorphizes the function foo based on the type parameter F. Since each closure has a unique type, the compiler monomorphizes (makes specialized copies of) foo as many time as foo is called. In this example, foo is monomorphized twice.

# #![allow(unused_variables)]
#fn main() {
fn foo<F: Fn(i32) -> i32>(f: F, i: i32) -> i32 {
    f(i)
}

let a = 1;
let b = |x| a + x;
let c = |x| a + x;
// Monomorphizes `foo`
foo(b, 1);
// Monomorphizes `foo` again
foo(c, 2);
#}

Alternatively, the function can take a closure as a trait object. In the example below, the compiler keeps only one copy of the function foo.

# #![allow(unused_variables)]
#fn main() {
fn foo(f: &Fn(i32) -> i32, i: i32) -> i32 {
    f(i)
}

let a = 1;
let b = |x| a + x;
let c = |x| a + x;
// Doesn't monomorphize
foo(&b, 1);
foo(&c, 2);
#}

We can view named functions as special closures in that they capture no variable in the environment. Therefore, a program may provide a named function as an argument to a function parameter expecting a closure, as long as the named function and the closure have the same types of parameters and return value in the same order.

# #![allow(unused_variables)]
#fn main() {
fn foo<F: Fn(i32) -> i32>(f: F, i: i32) -> i32 {
    f(i)
}

fn f(x: i32) -> i32 {
    x + 1
}

assert_eq!(foo(f, 1), 2);

fn bar(f: &Fn(i32) -> i32, i: i32) -> i32 {
    f(i)
}

fn g(x: i32) -> i32 {
    x + 1
}

assert_eq!(bar(&g, 1), 2);
#}

Returning a closure presents a challenge to functions. The first problem is that the size of the closure is unknown to the caller at compile time, but the caller needs to know the size of the returned closure.

A common way to circumvent the problem of statically unknown sizes is to use pointers, since all pointers have the same size. In the case of traits, we could use trait objects, which are pointers. But trait objects present another problem. In the program below, the closure is created on the stack of the function f, so its lifetime is that of f, but f returns a pointer to the closure. Since the pointer outlives the closure, this violates Rust's borrow checker.

# #![allow(unused_variables)]
#fn main() {
// Doesn't compile: the returned reference outlives the closure.
fn f() -> &Fn(i32) -> i32 {
    let a = 1;
    |x| x + a
}
#}

The solution is to place the closure on the heap instead. In the example below, f creates the closure in a Box, whose value is placed on the heap.

# #![allow(unused_variables)]
#fn main() {
fn f() -> Box<Fn(i32) -> i32> {
    let a = 1;
    Box::new(move |x| x + a)
}

let a = f();
assert_eq!(a(2), 3);
#}

Rust's for loop is safer, more powerful, and more efficient than C's. For example, let's iterate over an array. To write the program in C style:

# #![allow(unused_variables)]
#fn main() {
let v = vec![1, 2, 3];

for i in 0..v.len() {
    println!("{}", v[i]);
}
#}

The above is an anti-pattern in Rust. In idiomatic Rust, it becomes:

# #![allow(unused_variables)]
#fn main() {
let v = vec![1, 2, 3];

for x in v {
    println!("{:?}", x);
}
#}

The advantages of the second, idiomatic version are:

• correctness: since the code inside the for loop does not access the index i directly, it cannot access an element not in v, e.g., v[3].

• efficiency: since the code inside the for loop does not access the index i directly, the compiler need not generate code for verifying that i is in the bound of the vector.

• flexibility: the order in which for iterates over the elements in v is transparent to the code inside the loop, so the inside code works with any types of collections, be it a vector, tree, hash table, etc.

Rust allows a program to iterate over any type T in a for loop, as long as T implements the Iterator trait.

# #![allow(unused_variables)]
#fn main() {
trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

trait IntoIterator where Self::IntoIter::Item == Self::Item {
    type Item;
    type IntoIter: Iterator;
    fn into_iter(self) -> Self::IntoIter;
}

impl<I> IntoIterator for I where I: Iterator
#}

The above looks complicated, so let's dissect them one by one.

• The first trait, Iterator, defines the interface for an iterator. When a caller invokes next(), the iterator returns Some(_) if it has more items, or None if it has exhausted all its items.

• The second trait, IntoIterator, defines the interface for creating an Iterator.

• The last line is interesting. It instructs Rust to automatically implement IntoIterator for any type that implements Iterator.

Rust's for loop syntax is sugar for iterators. A program may use a for loop on any type that implements IntoIterator. The statement for i in v { statement } desugars approximately to

let mut iter = IntoIterator::into_iter(v);
loop {
    match iter.next() {
        Some(x) => { statement },
        None => break,
    }
}

If you wish to allow your type T to be usable in a for loop, you have two options:

1. impl Iterator for T, or
2. impl IntoIterator for T

Which one should you choose?

In the first option, you must implement the method next() for T, which requires T to contain some state that tracks which elements have been returned and which element to return next.

In the second option, T creates an iterator and returns it. It is the responsibility of this iterator to maintain some state to track which element to return next.

The following two programs contrast these two options.

# #![allow(unused_variables)]
#fn main() {
struct Counter {
    max: i32,
    // `count` tracks the state of this iterator.
    count: i32,
}

impl Counter {
    fn new(max: i32) -> Counter {
        Counter { count: -1, max: max }
    }
}

impl Iterator for Counter {
    type Item = i32;

    fn next(&mut self) -> Option<Self::Item> {
        self.count += 1;
        if self.count < self.max {
            Some(self.count)
        } else {
            None
        }
    }
}

for i in Counter::new(10) {
    println!("{}", i);
}
#}

# #![allow(unused_variables)]
#fn main() {
struct Counter {
    max: i32,
    // No need to track the state, because this isn't an iterator.
}

impl Counter {
    fn new(max: i32) -> Counter {
        Counter { max: max }
    }
}

impl IntoIterator for Counter {
    type Item = i32;
    type IntoIter = std::ops::Range<Self::Item>;

    fn into_iter(self) -> Self::IntoIter {
        std::ops::Range{ start: 0, end: self.max }
    }
}

for i in Counter::new(10) {
    println!("{}", i);
}
#}

Rust's standard library defines several range operators in std::ops. For example,

# #![allow(unused_variables)]
#fn main() {
struct Range<Idx> {
    pub start: Idx,
    pub end: Idx,
}
#}

The compiler treats a..b as a shorthand for Range{ start: a, end: b }. For example, the following two lines are equivalent:

for i in 0..n { ... }

for i in std::ops::Range{ start: 0, end: n } { ... }

There are two common uses of iterators.

• Adapters create a new iterator based on a current iterator.
• Consumers consume an iterator to produce another value.

An iterator adapter is a function that takes an iterator and returns another iterator. Common adapters are map(), take(), and filter().

trait Iterator {
    type Item;
    fn filter<P>(self, predicate: P) -> Filter<Self, P> 
        where P: FnMut(&Self::Item) -> bool;
    fn map<B, F>(self, f: F) -> Map<Self, F> 
        where F: FnMut(Self::Item) -> B;
    fn take(self, n: usize) -> Take<Self>;
}

map() maps each element in the current iterator to an element in the new iterator. It takes a closure as the parameter. The closure takes one element in the current iterator and returns a value that becomes an element in the new iterator.

# #![allow(unused_variables)]
#fn main() {
for i in (0..10).map(|x| x * 2) {
    println!("{}", i);
}
#}

Iterators are lazy, in the sense that the next() method is called only when the program iterates over the iterator. For example, the following program prints nothing.

# #![allow(unused_variables)]
#fn main() {
(0..10).map(|x| println!("{}", x));
#}

take() creates an iterator that contains the first n elements of the current iterator.

# #![allow(unused_variables)]
#fn main() {
for i in (0..10).take(5) {
    println!("{}", i);
}
#}

filter() creates a new iterator that contains some elements in the current iterator. It takes one parameter, which is a closure that determines whether each element in the current iterator should be included in the new iterator.

# #![allow(unused_variables)]
#fn main() {
for i in (0..10).filter(|x| x % 2 == 0) {
    println!("{}", i);
}
#}

Since an adapter returns an iterator, a program can chain adapters.

# #![allow(unused_variables)]
#fn main() {
for i in (0..10).map(|x| x * 2).take(5).filter(|x| x % 3 == 0) {
    println!("{}", i);
}
#}

A consumer also takes an iterator, but instead of returning another iterator, it returns a value that is not an iterator.

Common consumers are find(), collect(), and fold().

trait Iterator {
    fn collect<B>(self) -> B where B: FromIterator<Self::Item>;
    fn find<P>(&mut self, predicate: P) -> Option<Self::Item> where P: FnMut(&Self::Item) -> bool;
    fn fold<B, F>(self, init: B, f: F) -> B where F: FnMut(B, Self::Item) -> B;
}

trait FromIterator<A> {
    fn from_iter<T>(iter: T) -> Self where T: IntoIterator<Item=A>;
}

find() searches for the first element that satisfies a predicate. It returns Some(_) if it finds it, or None otherwise. find() takes a parameter, which is a closure that takes a reference to each element in the iterator and returns true or false.

# #![allow(unused_variables)]
#fn main() {
assert_eq!((0..10).find(|&x| x > 5).unwrap(), 6);
assert!((0..10).find(|&x| x > 10).is_none());
#}

collect() returns a collection that contains all the elements in the iterator. The receiving type (the type of the returned collection) must implement the FromIterator trait.

# #![allow(unused_variables)]
#fn main() {
struct Foo<T> {
    v: Vec<T>,
}

impl<A> std::iter::FromIterator<A> for Foo<A> {
    fn from_iter<T>(iter: T) -> Self where T: IntoIterator<Item=A> {
        let mut foo = Foo{ v: vec![] };
        for i in iter {
            foo.v.push(i);
        }
        foo
    }
}

let foo: Foo<_> = (0..10).collect();
// or
// let foo = (0..10).collect::<Foo<_>>();
println!("{:?}", foo.v);
#}

fold() applies a function to each element in the iterator to produce a single, final value. For example, the following program computes the sum of all the values in the array.

# #![allow(unused_variables)]
#fn main() {
assert_eq!((0..10).fold(0, |sum, x| sum + x), 45);
#}

fold() takes two arguments. The first argument is the initial value of the return value. The second argument is a closure that takes the return value computed so far and the next element to update the return value.

You can implement MapReduce by combining map() with fold(). For example, the following computes the squared sum of an array.

# #![allow(unused_variables)]
#fn main() {
let input = vec![1, 2, 3, 4, 5];
let output = input.iter().map(|x| x * x).fold(0, |x, y| x + y);
assert_eq!(output, 55);

#}

Modern processors have multiple cores. To allow a single program to run on these cores at the same time, we need concurrent programming. Concurrent programming is based on processes and threads.

A process is a program in execution, where a program refers to an executable stored in the file system. There may be multiple processes of the same program. For example, if a user runs an editor program N times, there will be N processes of the editor.

The address space of a process consists of the following sections:

• code: contains instructions.
• static: contains static data, e.g., static x: i32 = 1.
• heap: contains boxes, e.g., Box::new(1).
• stack: contains variables, e.g., let x = 1.

If a program wishes to run multiple tasks concurrently, it could run each task in a separate process, but doing so would be expensive because creating processes is expensive. This is because each process has its own static, heap, and stack sections even if they share the same code section (i.e., run the same program). To reduce the overhead of creating multiple processes, the program can create threads instead.

Similar to processes, each thread runs a task independently, i.e., each thread is independently scheduled. However, unlike processes, all the threads of the same process share the same static and heap sections, but each thread has its own stack section. Because of the shared static and heap sections, when a process creates a new thread, it need create only a new stack section, so creating a thread is more lightweight than creating a new process. Concurrent programs use threads extensively.

std::thread::spawn() creates a new thread. When a Rust program starts, its main function runs in the main thread. When the main thread finishes, the entire process exits even if other threads may still be running. To wait for another thread, the waiting thread can call join() on the other thread's handle, which was returned by std::thread::spawn().

# #![allow(unused_variables)]
#fn main() {
let t = std::thread::spawn(|| println!("child thread"));
println!("parent thread");
t.join().unwrap();
#}

Since the parent and child threads are scheduled independently, we do not know which of them executes the println macro first.

std::thread::spawn() takes a closure as the parameter and runs the closure in the new thread. However, there are restrictions on the closure.

# #![allow(unused_variables)]
#fn main() {
fn f() {
    struct Foo(i32);
    let foo = Foo(1);
    // Error: `foo` does not live long enough.
    std::thread::spawn(|| println!("{}", foo.0));
}
#}

The program above generates a compiler error, for good reasons. The closure passed to spawn captures the variable foo in its environment by reference. However, since the parent and child threads are scheduled independently, when println!() in the child thread accesses foo by reference, f() in the parent thread may have returned so that foo no longer exists.

To prevent this error, we could let the Rust compiler be aware of the thread API (like the Go programming language), but this would prevent a program from using alternative thread models. Instead, the Rust compiler is unaware of the thread API, and std::thread provides the thread API instead. In other words, the compiler does not know that std::thread::spawn() creates a thread. But then how does the compiler detect the above use-after-free error?

The answer is in the declaration of std::thread::spawn():

fn spawn<F, T>(f: F) -> JoinHandle<T> 
    where F: FnOnce() -> T, F: Send + 'static, T: Send + 'static

This declaration is rather complex, but the key here is the 'static lifetime required of the closure f. Since f has the static lifetime, it cannot reference any variable whose lifetime is not static, because a reference cannot outlive the value that it points to. Note that the static lifetime outlives any non-static lifetime.

To overcome this lifetime problem, the program can instruct the compiler to always move the variables in the environment that are used in the closure into the closure, by specifying the move keyword in front of the closure declaration.

# #![allow(unused_variables)]
#fn main() {
fn f() {
    struct Foo(i32);
    let foo = Foo(1);
    // OK: the compiler moves `foo` into the closure.
    std::thread::spawn(move || println!("{}", foo.0));
}
#}

Threads often share data between them. However, once a parent thread moves a value into a child thread, the parent thread can no longer access the value.

# #![allow(unused_variables)]
#fn main() {
struct Foo(i32);
let foo = Foo(1);
std::thread::spawn(move || println!("{}", foo.0));
// Error: `foo` is moved.
println!("{}", foo.0);
#}

To allow multiple threads to share the same value, Rust provides smart pointers. Smart pointers circumvent Rust's single ownership type system. Without smart pointers, a value is owned by exactly one owner. When the owner goes out of scope, Rust destroys the value. Since at compile time the compiler knows when each variable goes out of scope, the compiler knows when to destroy each value.

By contrast, a value may be owned by multiple smart pointers, and Rust won't destroy the value until all the owners go out of scope. Since at compile time the compiler does not know which owner is the last one to go out of scope, the compiler must generate code that, whenever an owner goes out of scope, checks if that is the last owner. If so, the code destroys the shared value. Therefore, smart pointers incur runtime overhead.

Rust provides different types of smart pointers. Some allow only reading the shared values, and some allow writing the shared values.

std::sync::Arc is a smart pointer providing read-only access to shared data.

struct Arc<T> { ... }

impl<T> Arc<T> {
    fn new(x: T) -> Arc<T> { ... }
    ...
}

impl<T> Deref for Arc<T> {
    type Target = T;
    ...
}

A program may clone Arc<T> to create many owners of the same shared data.

# #![allow(unused_variables)]
#fn main() {
struct Foo(i32);
let foo = std::sync::Arc::new(Foo(1));
{
    // Rebinds the name `foo`. After this statement, `foo` in this scope and 
    // `foo` in the parent scope are different smart pointers, but they point
    // to the same shared value `Foo(1)`.
    let foo = foo.clone();
    std::thread::spawn(move || println!("{}", foo.0));
}
// OK
println!("{}", foo.0);
#}

The above program shows an idiomatic way to clone a smart pointer and to move it into a closure:

• Create a new scope.
• In the new scope, clone the smart pointer.
• Move the cloned value into the closure.

You might wonder how the program could access foo.0, because the type of foo is Arc<Foo> rather than Foo. The answer is that Arc implements the Deref trait:

impl<T> Deref for Arc<T> {
    type Target = T;
  ...
}

Therefore, the compiler automatically coerces a reference to Arc<Foo> into a reference to Foo.

Arc<T> is read only. Since multiple threads can read the same Arc<T> concurrently, allowing any thread to mutate the share value would cause a data race. To prohibit write access to Arc<T>, Arc<T> does not implement the DerefMut trait.

Data race happens when

• multiple threads access the same shared data, and
• at least one access is writing, and
• the threads lack proper synchronization.

As a result, the behavior of the program is non-deterministic, depending on the relative order by which the instructions in different threads run. For example, the following C pseudocode has data race, which may print either 0 or 1.

void f(int *i) {
    *i = 1;
}

int main() {
    int i = 0;
    // pseudo code
    thread t = new_thread(f, &i);
    println("%d", i);
    t.join();
}

To allow threads to mutate shared data, we need a type that can enforce mutually exclusive access to the shared data at runtime. Rust's standard library provides std::sync::Mutex<T> for this purpose.

struct Mutex<T> { ... }

impl<T> Mutex<T> {
    fn new(t: T) -> Mutex<T> { ... }
    fn lock(&self) -> LockResult<MutexGuard<T>> { ... }
    ...
}

impl<T> Deref for MutexGuard<T> {
    type Target = T;
    ...
}

impl<T> DerefMut for MutexGuard<T> {
    type Target = T;
    ...
}

type LockResult<Guard> = Result<Guard, PoisonError<Guard>>;

A Mutex<T> value m contains a value v of type T. However, the thread cannot access v via m by simply deferencing m, because Mutex<T> implements neither Deref nor DerefMut. Instead, to access v, the thread must call the lock method of Mutex<T>, which returns a value g of the type MutexGuard<T>. Then, the thread deferences g to access v, because MutexGuard<T> implements both Deref and DerefMut.

While a thread t is holding a MutexGuard<T>, when another thread s calls lock() on the same Mutex<T>, s is blocked until the MutexGuard<T> value goes out of scope in t. This ensures mutually exclusive access to the value in Mutex<T>.

Mutex<T>::lock() returns the type LockResult<MutexGuard<T>>, which is an alias of Result<MutexGuard<T>, PoisonError<MutexGuard<T>>>. The value Err<PoisonError<MutexGuard<T>> indicates that the thread that held the MutexGuard<T> value panicked, which allows the calling thread an opportunity to handle this when necessary. A common use of Mutex<T> is to enforce an invariant on a shared mutable data. Before a thread mutates the data, the thread acquires mutually exclusive access to the data by calling Mutex<T>::lock() to get a MutexGuard<T>. While the thread is holding the MutexGuard<T>, it may modify the data during which the invariant may no longer hold. When the thread finishes modifying the data, it restores the invariant before releasing the MutexGuard<T>. This programming discipline ensures that whenever a thread acquires a MutexGuard<T>, it is confident that the invariant protected by the Mutex<T> always holds. However, when the thread holding the MutexGuard<T> panics, it may not have finished modifying the shared data and restored the invariant, so the Rust library poisons the Mutex<T> by letting Mutex<T>::lock() always return Err<PoisonError<MutexGuard<T>> in the future. This notifies the calling thread to handle the potentially invalid invariant.

Mutex<T> is a type with interior mutability. To mutate a value of most types, the program must hold a mutable reference to the value.¹ This is called exterior mutability. By contrast, to mutate the value in a Mutex<T>, the program needs no mutable reference to Mutex<T>. Instead, the program acquires a MutexGuard<T> and mutates the value via MutexGuard<T>.

To allow multiple threads to access the same Mutex<T>, the program must wrap it in Arc<_>, and send a clone of the Arc<_> to each thread.

# #![allow(unused_variables)]
#fn main() {
struct Foo(i32);
let foo = Foo(0);
let mutex = std::sync::Mutex::new(foo);
let arc = std::sync::Arc::new(mutex);
let child;
{ 
    let arc = arc.clone();
    child = std::thread::spawn(move || { 
        let mut guard = arc.lock().unwrap();
        guard.0 += 1;
    });
}
{
    let mut guard = arc.lock().unwrap();
    guard.0 += 1;
}
child.join().unwrap();
let mut guard = arc.lock().unwrap();
assert_eq!(guard.0, 2);
#}

This section assumes that the reader knows synchronization in operating systems.

It is difficult to write correct multi-threaded programs, because it is difficult to implement synchronization correctly. Common synchronization errors include the following:

• Forget to acquire the lock before accessing a mutably shared object.
• Forget to release the lock after accessing a shared object.
• Place shared objects on the stack.

Detecting these errors in C is challenging, but Rust eliminates these errors at compile time, thanks to its powerful type system.

Using only safe Rust, multiple threads cannot share mutable values without using a synchronization type, such as Arc. The reason is as follows. A Rust program stores values in the static data section, stack, or the heap. Variables represent memory locations and their values in the static data section or stack. Values on the heap are accessible only via their boxes on the stack.

Immutable static variables can be read in different threads, but this is safe. Mutable static variables cannot be accessed in safe Rust.

Multiple threads may not share values on the stack (see the explanation). Therefore, threads must place shared values into Arc<_>. After that, the program can no longer access the original variables directly, because they have been moved. The only way to access these variables is via Arc.

Since Arc<_> implements only Deref but not DerefMut, the program can only read the value in Arc<_>. If the program needs to overwrite the value, it must place the value in Arc<Mutex<_>>. In this case, the program must call Mutex::lock() to get a MutexGuard. MutexGuard implements both the Deref and DerefMut traits, which autoderef to the type of the shared object to allow reading and/or writing the object.

# #![allow(unused_variables)]
#fn main() {
struct Foo(i32);
let foo = Foo(1);
let mutex = std::sync::Mutex::new(foo);
{ 
    let mut guard = mutex.lock().unwrap();
    assert_eq!(guard.0, 1);
    guard.0 = 2;
}
// Error: value is moved.
foo.0 = 2;
#}

After the program calls Mutex::lock(), it gets a MutexGuard, which holds the lock. MutexGuard implements the Drop trait, so when it goes out of scope, it releases the lock automatically, so the thread cannot forget to release the lock (unless it enters an infinite loop or crashes).

Since each thread has its own stack, a thread t1 should not access an object stored on the stack of another thread t2 unless the program can guarantee that t2 outlives t1; otherwise, the reference to the object that t1 holds will become dangling after t2 exits.

Rust's type system statically prevents the use of values after they go out of scope. Consider the following incorrect program.

# #![allow(unused_variables)]
#fn main() {
struct Foo(i32);
let foo = Foo(1);
// Error: the reference to `foo` in the closure outlives `foo`.
std::thread::spawn(|| println!("{}", foo.0));
#}

This program does not compile because spawn() requires its argument to be a closure of static lifetime. Rust declares spawn() this way because the new thread may live until the end of the process.

fn spawn<F, T>(f: F) -> JoinHandle<T> 
    where F: FnOnce() -> T, F: Send + 'static, T: Send + 'static

To avoid this error, the program has two choices:

• Move the value into the closure. But in this case, this value isn't shared any more, because the parent thread loses this value.

• Wrap the value in an Arc, and then clone it in every thread. Arc keeps only one copy of the value and releases it when all the owners of Arc go out of scope at runtime.

# #![allow(unused_variables)]
#fn main() {
struct Foo(i32);
let foo = Foo(1);
let shared = std::sync::Arc::new(foo);
let shared_ = shared.clone();
std::thread::spawn(move || println!("{}", shared_.0));
#}