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.