Course 3 - Rust Generics and Lifetimes Annotations

class: center, middle

# Rust Generics and Lifetimes Annotations

.title[.center[![SecureEmbeddedProgramming](../images/sep.png)]]

.left[
Based on: [Rust ISP 2019](https://github.com/newpavlov/rust-isp-2019) slides  
Alexandru Radovici, ilustrations by [Mieuneli](http://miau.laura.ro)
]

---

# Overview

1. Generics
2. The Pointer Problem
3. Lifetimes Annotations

---
# Generics

- This looks a lot like a standard library enum, `Result<T, E>`:

```rust
enum Option<T> {
    Some(T),
    None,
}
```
- `T` stands in for any generic type, not only `String`s.
- You can use any CamelCase identifier for generic types.

---
## Generic Structs

- Let's take a look at generic versions of several other structs from the last lecture:

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

---
## Generic Implementations

- To define implementations for structs & enums with generic types, declare the generics at the
    beginning of the `impl` block:

```rust
impl<T> Option<T> {
    fn is_some(&self) -> bool {
        match self {
            Result::Some(_) => true,
            Result::None => false,
        }
    }
}
```

---
## Generic Functions

- You can make a function generic over types as well.
- `<T, U>` declares the type parameters for `foo`.
    - `x: T, y: U` uses those type parameters.
- You can read this as "the function `foo`, for all types `T` and `U`,
    of two arguments: `x` of type `T` and `y` of type `U`."

```rust
fn foo<T, U>(x: T, y: U) {
    // ...
}
```

- But we can't do much with `x` and `y`, because we don't know anything
    about types `T` and `U`

---
## Generics with Trait Bounds

- Instead of allowing _literally any_ type, you can constrain generic types by
    _trait bounds_.
- This gives more power to generic functions & types.
- Trait bounds can be specified with `T: SomeTrait`, with a `where` clause,
    or with `impl Trait` in argument position.

```rust
fn digital_write<P: Pin>(p: &P, value: usize) {
    if value == 1 {
        p.set();
    } else {
        p.clear ();
    }
}

fn digital_write<P>(p: &P, value: usize) 
        where P: Pin {
    if value == 1 {
        p.set();
    } else {
        p.clear ();
    }
}

fn digital_write(p: &impl Pin, value: usize) {
    if value == 1 {
        p.set();
    } else {
        p.clear ();
    }
}

```

---
## Generics with Trait Bounds

- Multiple trait bounds are specified like `T: Clone + Ord`.
- There's no way (yet) to specify [negative trait bounds](https://internals.rust-lang.org/t/pre-rfc-mutually-exclusive-traits/2126).
  - e.g. you can't stipulate that a `T` must not be `Clone`.

```rust
fn digital_write<P: Configure + Output>(p: P, value: usize) {
   p.make_output ();
   if value == 1 {
       p.set ();
   } else {
       p.clear ();
   }
}
```

---
## Generic Types With Trait Bounds

- You can also define structs with generic types and trait bounds.
- Be sure to declare all of your generic types in the struct header _and_ the
  impl block header.
- Only the impl block header needs to specify trait bounds.
    - This is useful if you want to have multiple impls for a struct each with
      different trait bounds

```rust
struct MyDriver<P: Pin> {
    pin1: &'static P,
    pin2: &'static P,
    // ...
}
```

And without traiut bounds

```rust
struct MyDriver<P> {
    pin1: &'static P,
    pin2: &'static P,
    // ...
}
```

---
## Generic Types With Trait Bounds

```rust
impl<P: Pin> Driver for MyDriver<P> {
   // ...
}
```

---
## Examples: Equality

```rust
// This is not the trait Rust actually uses for equality
trait Equals {
    fn equals(&self, other: &Self) -> bool;
}

impl<T: Equals, E: Equals> Equals for Result<T, E> {
    fn equals(&self, other: &Self) -> bool {
        match (self, other) {
            (Ok(t1), Ok(t2)) => t1.equals(t2),
            (Err(e1), Err(e2)) => e1.equals(e2),
            _ => false
        }
    }
}
```
- `Self` is a special type which refers to the type of `self`.

---
## Inheritance (kinda)

- Some traits may require other traits to be implemented first.
    - e.g., `Eq` requires that `PartialEq` be implemented, and `Copy` requires `Clone`.
- Implementing the `Child` trait below requires you to also implement `Parent`.

```rust
trait Parent {
    fn foo(&self) {
        // ...
    }
}

trait Child: Parent {
    fn bar(&self) {
        self.foo();
        // ...
    }
}
```

---
# Lifetimes Annotations

- Lifetimes generally have a pretty steep learning curve.
- Don't worry if you don't understand these right away.

.title[.center[![Din Lac in Put](../images/mieuneli_din_lac_in_put.png)]]

---
## Lifetimes

- Imagine This:
  1. I acquire a resource.
  2. I lend you a reference to my resource.
  3. I decide that I'm done with the resource, so I deallocate it.
  4. You still hold a reference to the resource, and decide to use it.
  5. You crash 😿.
- We've already said that Rust makes this scenario impossible, but glossed over
    how.
- We need to prove to the compiler that _step 3_ will never happen before _step 4_.

---
## Lifetimes

- Lifetimes are used only together references
- All variables have a lifetime (usually hidden from the developer)
- All references are __have to__ be annotated with a lifetime
- Ordinarily, references have an implicit lifetime that we don't need to care
    about:

```rust
fn foo(x: &i32) {
    // ...
}
```
- However, we can explicitly provide one instead:
```rust
fn bar<'a>(x: &'a i32) {
    // ...
}
```

---
### Question .top_image[![Questions](../images/question.svg)]

Q1: How do you use free?

```c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char * without_first_word (char *s);

int main ()
{
    char * s = strdup ("ana has apples");
    char *wfw = without_first_word (s);
    // free (s);   <-- before printf
    printf ("%s\n", wfw);
    // free (wfw); <-- after printf
}

```

---
### Question .top_image[![Questions](../images/question.svg)]

Q2: How do you use free?

```c
// program: bear-salamander-anteater
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char * without_first_word (char *s) {
    int pos = 0;
    for (unsigned int i=0; i < strlen (s); i++) {
        if (s[i] != ' ') pos = pos + 1;
        else break;
    }
    return &s[pos];
}

int main ()
{
    char * s = strdup ("ana has apples");
    char *wfw = without_first_word (s);
    // free (s);    <-- before printf
    printf ("%s\n", wfw);
    // free (wfw);  <-- after printf
}

```

---
### Question .top_image[![Questions](../images/question.svg)]

Q3: How do you use free?

```c
// program: oyster-guanaco-dinosaur
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char * without_first_word (char *s) {
    int pos = 0;
    for (unsigned int i=0; i < strlen (s); i++) {
        if (s[i] != ' ') pos = pos + 1;
        else break;
    }
    return strdup (&s[pos]);
}

int main ()
{
    char * s = strdup ("ana has apples");
    char *wfw = without_first_word (s);
    // free (s);   <-- before printf
    printf ("%s\n", wfw);
    // free (wfw);  <-- before printf
}

```

---
### Lifetime annotations

From a birds eye view, how should Rust free `s` and `wfw`?

```rust
fn without_first_word<'a> (s: &'a str) -> &'a str;

fn main() {
    let s = String::from("ana has apples"); 
    let wfw = without_first_word (&s);      
    // let t = s; // equivalent of free (s)
    println! ("{}", wfw);                  
    // let t = s; // equivalent of free (s)
}                                         
```

---
### This is why lifetimes are useful.

```rust
fn without_first_word<'a> (s: &'a str) -> &'a str {
    let mut pos = 0;
    for a in s.chars() {
        if a != ' ' { pos = pos + 1; }
        else { break; }
    }
    &s[pos..]
}

fn main() {
    let s = String::from("ana has apples");
    let wfw = without_first_word (&s);
    // let t = s; // equivalent of free (s)
    println! ("{}", wfw);
}
```

---
### Efective Lifetimes

```rust
fn without_first_word<'a> (s: &'a str) -> &'a str {
    let mut pos = 0;
    for a in s.chars() {
        if a != ' ' { pos = pos + 1; }
        else { break; }
    }
    &s[pos..]
}

fn main() {
    let s = String::from("ana has apples"); // <--- s lifetime ('ls) starts here
    let wfw = without_first_word (&s);      // <--- wfw lifetime ('lwfw) starts here
    // let t = s; // equivalent of free (s)    // <--- s lifetime ('ls) ends here, wfw lifetime ('wfw) ends here (due to 'ls)
                                            //      t lifetime ('ts) starts here
    println! ("{}", wfw);                   // <--- wfw lifetime ('lwfw) actually ends here
}                                           // <--- t lifetime ('ts) ends here
```

---
### Lifetime annotations

```rust
fn without_first_word<'a> (s: &'a str) -> &'a str;

---
### Question .top_image[![Questions](../images/question.svg)]

Can we use free for `s1` and `s2` before `printf`?

```c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

char * smaller (char *s1, char *s2);

int main () {
    char *s1 = strdup ("ip");
    char *s2 = strdup ("workshop");
    char *small = smaller (s1, s2);
    // free (s1);
    // free (s2);
    printf ("%s\n", small);
}

```

---
### Multiple Lifetime Parameters

```c
// program: wolverine-mallard-gull
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

char * smaller (char *s1, char *s2) {
    if (strlen(s1) > strlen(s2)) return s2;
    else return s1;
}

int main () {
    char *s1 = strdup ("ip");
    char *s2 = strdup ("workshop");
    char *small = smaller (s1, s2);
    // free (s1);
    // free (s2);
    printf ("%s\n", small);
}

```

---
### Multiple Lifetime Parameters

```rust
fn smaller <'a> (s1: &'a str, s2: &'a str) -> &'a str {}

fn main() {
    let s1 = String::from("ip"); 
    let s2 = String::from("workshop"); 
    let small = smaller (&s1, &s2);
    // let t1 = s1; // equivalent of free (s1)
    // let t2 = s2; // equivalent of free (s2)
    println! ("{}", small);                  
}                                          
```

---
### Question .top_image[![Questions](../images/question.svg)]

Why can't we free s2?

```rust
fn append <'a> (s: &'a mut String, n: &'a str) -> &'a str {
    s.push_str (n);
    s
}

fn main() {
    let mut s1 = String::from("ip"); 
    let s2 = String::from(" workshop"); 
    let title = append (&mut s1, &s2);
    // let t1 = s1; // equivalent of free (s1)
    let t2 = s2; // equivalent of free (s2)
    println! ("{}", title);                  
}                                          
```
---
### Multiple Lifetime Parameters

We now can free s2.

```rust
fn append <'a, 'b> (s: &'a mut String, n: &'b str) -> &'a str {
    s.push_str (n);
    s
}

---
## Lifetimes - `struct`s

- Structs (and struct members) can have lifetime parameters.

```rust
struct Pizza(String);
struct PizzaSlice<'a> {
    pizza: &'a Pizza,  // <- references in structs must
    index: u32,        //    ALWAYS have explicit lifetimes
}

let p1 = Pizza("salamy".to_string());
{
    let s1 = PizzaSlice { pizza: &p1, index: 2 }; // this is okay
}

let s2;
{
    let p2 = Pizza("salamy".to_string());
    s2 = PizzaSlice { pizza: &p2, index: 2 };
    // no good - why?
}
```

- Currently Rust does not support self-referential structs out-of-box.

---
## Lifetimes - `struct`s

- Lifetimes can be constrained to "outlive" others.
    - Same syntax as type constraint: `<'b: 'a>`.

```rust
struct Pizza(String);
struct PizzaSlice<'a> { pizza: &'a Pizza, index: u32 }
struct PizzaConsumer<'a, 'b: 'a> { // says "b outlives a"
    slice: PizzaSlice<'a>, // <- currently eating this one
    pizza: &'b Pizza,      // <- so we can get more pizza
}

fn get_another_slice(c: &mut PizzaConsumer, index: u32) {
    c.slice = PizzaSlice { pizza: c.pizza, index: index };
}

let p = Pizza("salamy".to_string());
{
    let s = PizzaSlice { pizza: &p, index: 1 };
    let mut c = PizzaConsumer { slice: s, pizza: &p };
    get_another_slice(&mut c, 2);
}
```

---
## Lifetimes - `'static`

- There is one reserved, special lifetime, named `'static`.
- `'static` means that a reference may be kept (and will be valid) for the
  lifetime of the entire program.
    - i.e. the data referred to will never go out of scope.
- All `&str` literals have the `'static` lifetime.

```rust
let s1: &str = "Hello";
let s2: &'static str = "World";
```

---
### Structured Data With Lifetimes

- Any struct or enum that contains a reference must have an explicit lifetime.
- Normal lifetime rules otherwise apply.

```rust
struct Foo<'a, 'b> {
  v: &'a String,
  s: &'b str,
}
```

---
### Lifetimes in `impl` Blocks

- Implementing methods on `Foo` struct requires lifetime annotations too!
- You can read this block as "the implementation using the lifetimes `'a` and
    `'b` for the struct `Foo` using the lifetimes `'a` and `'b`."

```rust
impl<'a, 'b> Foo<'a, 'b> {
  fn new(v: &'a String, s: &'b str) -> Foo<'a, 'b> {
    Foo {
      v: v,
      s: s,
    }
  }
}
```

---
## Lifetime Elision Rules

1. Each __elided lifetime__ in the __parameters__ becomes a __distinct lifetime__ parameter.

2. If there is __exactly one lifetime__ used in the parameters (elided or not), that lifetime is assigned to __all elided output lifetimes__.

3. If the receiver has type __&Self__ or __&mut Self__, then the __lifetime of__ that reference to __Self__ is assigned to __all elided output lifetime__ parameters.

.card[.small[.center[![Borrow Rules](../images/sep_elision_rules.png)]]]

---

# Workpoint 1 .top_image[![Work In Progress](../images/work_in_progress.png)]

```rust
struct Professor {
    firstname: String,
    lastname: String
}

trait Person {
    fn get_name (&self) -> &str;
}

fn main() {
    let p = Professor::new ("The", "Name");
    let name = p.get_name ();
    println! ("{}", name);
}
```

Hint: You are returning a reference, the _original_ value has to be valid as long as the reference is used. Tune the struct for that.

---

# Workpoint 2 .top_image[![Work In Progress](../images/work_in_progress.png)]

Implement the output trait so that it prints the state like:

```
    PIN: 0 STATE 0
    ...
```

```rust
trait Output {
    fn set (&self);
    fn clear (&self);
}

fn digital_write (pin: P) {
    /// use the Output trait
}

fn main() {
    let arduino_pins = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13];

for pin_index in 0..arduino_pins.len () {
        digital_write (arduino_pins[pin_index], 0);
    }

for pin_index in 0..arduino_pins.len () {
        digital_write (arduino_pins[pin_index], 1);
    }
}
```

---

# Workpoint 3 .top_image[![Work In Progress](../images/work_in_progress.png)]

Modify the previous example so that some pins in the `arduino_pins` array are not available.

```rust
fn main() {
    // Hint: use Option
    let arduino_pins = [...];

for pin_index in 0..arduino_pins.len () {
        digital_write (arduino_pins[pin_index], 0);
    }

for pin_index in 0..arduino_pins.len () {
        digital_write (arduino_pins[pin_index], 1);
    }
}
```

---

# Workpoint 4 .top_image[![Work In Progress](../images/work_in_progress.png)]

Define a `ArduinoPin` struct and store its value.

```rust
struct ArduinoPin {
    pin: u32,
    state: u32
}

trait Output {
    fn set (&self);
    fn clear (&self);
    fn toggle (&self);
}

fn main() {
    // Hint: use Option
    let arduino_pins: [ArduinoPin; 14] = [...];

for pin_index in 0..arduino_pins.len () {
        digital_write (arduino_pins[pin_index], 0);
        println! ("{}", arduino_pins[pin_index]);
    }

for pin_index in 0..arduino_pins.len () {
        digital_write (arduino_pins[pin_index], 1);
        println! ("{}", arduino_pins[pin_index]);
    }
}
```

Hint: You might have to modify the `Output` trait.

---
# Mutability

All Tock traits use `&self` to be able to share a driver with several other drivers.

Interior mutability:
- Cell<T> (`core::cell::Cell`)
- OptionalCell<T> (`kernel::common:cells::OptionalCell`)
- TakeCell<T> (`kernel::common::cells::TakeCell`)

.right[
.card[.small_vertical[![Cell](../images/sep_cell.png)]]
.card[.small_vertical[![OptionalCell](../images/sep_optionalcell.png)]]
.card[.small_vertical[![TakeCell](../images/sep_takecell.png)]]
]

---

## Cell

Store a mutable value inside a immutable structure

```rust
use kernel::{Driver, AppId, ReturnCode};
use core::cell::Cell;

/// Each driver is identified by a unique number
///
/// numbers higher than 0xa0000000 are unused by standard drivers
pub const DRIVER_NUM: usize = 0xa0000000;

/// The Hello structure
pub struct Hello {
    nr: Cell<usize>
}

/// The hello implementation
impl Hello {
    pub fn new() -> Hello {
        Hello {
            nr: Cell::new (0)
        }
    }
}

/// The driver system calls implementation
impl Driver for Hello {
    /// subscribe and allow will use the default implementation

/// command syscall
    fn command(&self, command_num: usize, _data1: usize, _data2: usize, _app_id: AppId) -> ReturnCode {
        match command_num {
            // command_num 0 is used to verify if the driver exists
            0 => ReturnCode::SUCCESS,

2 => {
                // modify number
                self.nr.set (self.nr.get () + 1);
                ReturnCode::SuccessWithValue { value: self.nr.get() }
            }

// the command number is not defined
            _ => ReturnCode::ENOSUPPORT,
        }
    }
}
```

---

# Workpoint 5 .top_image[![Work In Progress](../images/work_in_progress.png)]

Solve the previous workpoint without modifiying the `Output` trait.

```rust
struct ArduinoPin {
    pin: u32,
    state: u32
}

trait Output {
    fn set (&self);
    fn clear (&self);
    fn toggle (&self);
}

fn main() {
    // Hint: use Option
    let arduino_pins: [ArduinoPin; 14] = [...];

for pin_index in 0..arduino_pins.len () {
        digital_write (arduino_pins[pin_index], 0);
        println! ("{}", arduino_pins[pin_index]);
    }

for pin_index in 0..arduino_pins.len () {
        digital_write (arduino_pins[pin_index], 1);
        println! ("{}", arduino_pins[pin_index]);
    }
}
```

Hint: use mutability

---
# Workpoint 6 .top_image[![Work In Progress](../images/work_in_progress.png)]

Make this work

```rust
struct Professor {
    firstname: String,
    lastname: String
}

impl Professor {
    pub fn set_firstname (&self, new_name: &str) {

}

pub fn set_lastname (&self, new_name: &str) {
        
    }
}

trait Person {
    fn get_name (&self) -> &str;
}

fn main() {
    let p = Professor::new ("The", "Name");
    p.set_firstname ("New");
    let name = p.get_name ();
    println! ("{}", name);
}
```

---
# Workpoint 7 .top_image[![Work In Progress](../images/work_in_progress.png)]

Make this work

```rust
struct Professor {
    firstname: &str,
    lastname: &str
}

impl Professor {
    pub fn set_firstname (&self, new_name: &str) {

}

pub fn set_lastname (&self, new_name: &str) {
        
    }
}

trait Person {
    fn get_name (&self) -> &str;
}

fn main() {
    let p = Professor::new ("The", "Name");
    p.set_firstname ("New");
    let name = p.get_name ();
    println! ("{}", name);
}
```