# Generic Types, Traits, and Lifetimes

### Speaker:　@tigercosmos

---

## generics

- `Option<T>`
- `Vec<T>`
- `HashMap<K, V>`

----

### Why we need generics?

duplicated functions

fn largest_i32(list: &[i32]) -> i32 {}
fn largest_char(list: &[char]) -> char {}

how about

fn largest<T>(list: &[T]) -> T {}

---

## Generic Data Types

----

### Function Definition

fn largest<T>(list: &[T]) -> T {}

----

### Stuct Definition

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

fn main() {
    let integer = Point { x: 5, y: 10 };
    let float = Point { x: 1.0, y: 4.0 };
}

note: `x` and `y` in `Point` must be the same type or causes error.

----

Two generics in a `Struct` is fine

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

fn main() {
    let both_integer = Point { x: 5, y: 10 };
    let both_float = Point { x: 1.0, y: 4.0 };
    let integer_and_float = Point { x: 5, y: 4.0 };
}

----

### Enum Definitions

enum Option<T> {
    Some(T),
    None,
}

enum Result<T, E> {
    Ok(T),
    Err(E),
}

----

### Method Definitions

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

impl<T> Point<T> {
    fn x(&self) -> &T {
        &self.x
    }
}

fn main() {
    let p = Point { x: 5, y: 10 };

    println!("p.x = {}", p.x());
}

Note: declare `T` just after `impl` to specify implementing methods on the type `Point<T>`

----

Not work. why?

impl Point<T> {
    fn x(&self) -> &T {
        &self.x
    }
}

need bring scope in `impl`

----

### concrete type for the generic type parameter `T`

We don't add type after `impl` if we don't need generics from `Struct`

impl Point<f32> {
    fn distance_from_origin(&self) -> f32 {
        (self.x.powi(2) + self.y.powi(2)).sqrt()
    }
}

----

Other types in `impl` different from types of `Struct` are allowed.

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

impl<T, U> Point<T, U> {
    fn mixup<V, W>(self, other: Point<V, W>) -> Point<T, W> {
        Point {
            x: self.x,
            y: other.y,
        }
    }
}

fn main() {
    let p1 = Point { x: 5, y: 10.4 };
    let p2 = Point { x: "Hello", y: 'c'};

    let p3 = p1.mixup(p2);

    println!("p3.x = {}, p3.y = {}", p3.x, p3.y);
}

----

## Perforamnce of Code Using Generics

Monomorphization 單態化

let integer = Some(5);
let float = Some(5.0);

turn out to be

enum Option_i32 {
    Some(i32),
    None,
}

enum Option_f64 {
    Some(f64),
    None,
}

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

Note: `template` in C++ has a similar way.

---

## Traits: Defining Shared Behavior

----

### Definition

- `trait` keyword
- declare many methods in the trait
- each type which uses the trait needs to provide its own custom behavior body for the method.

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

----

pub struct NewsArticle {
    pub headline: String,
    // ...
}

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

pub struct Tweet {
    pub username: String,
    // ...
}

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

----

Call the method just as regular methods, such as `tweet.summarize()`

    let tweet = Tweet {
        username: String::from("tigercosmos"),
        // ...
    };

    println!("1 new tweet: {}", tweet.summarize());

----

- trait needs to be imported if not in scope
- trait must be `pub` if it would be used otherwhere

----

### coherence rule

traits could be used for local types. external traits on external types is forbidden.

Popular traits: Display, Debug, ToString, Default, should be implemented in a crate, becasue others cannot implement theirselves.

----

### Fully Qualified Syntax

`<T as TraitName>::item`

trait Cook {
    fn start(&self);
}

trait Wash {
    fn start(&start);
}

struct Chef;

impl Cook for Chef {
    fn start(&seld) { println!("Cook Start"); }
}

impl Wash for Chef {
    fn start(&seld) { println!("Cook Start"); }
}

fn main {
    let me = Chef;
    <Cook>::start(&me);
    <Chef as Wash>::start(&me);
}

----

### Default implementations

define the method when declare the trait

pub trait Summary {
    fn summarize(&self) -> String {
        String::from("(Read more...)")
    }
}

let article = NewsArticle {
    // .....
};

println!("New article available! {}", article.summarize());
// New article available! (Read more...)

----

`trait` could call other methods in the same trait or the struct member

pub struct Tweet {
    pub username: String,
    pub content: String,
    pub reply: bool,
    pub retweet: bool,
}

pub trait Summary {
    fn summarize_author(&self) -> String;

    fn summarize(&self) -> String {
        format!("(Read more from {}...)", self.summarize_author())
    }
}

impl Summary for Tweet {
    fn summarize_author(&self) -> String {
        format!("@{}", self.username)
    }
}

fn main() {
    let tweet = Tweet {
        username: String::from("tigercosmos"),
        content: String::from("You should follow @tigercosmos's github :)"),
        reply: false,
        retweet: false,
    };

    println!("1 new tweet: {}", tweet.summarize());
}

try yourself: [playground link](https://play.rust-lang.org/?gist=b70e8f150a2d2a231e9a88d74c4f5920&version=stable&mode=debug&edition=2015)

----

### Trait Bounds

specify that `item` must be of a type that implements the `Summary` trait:

pub fn notify<T: Summary>(item: T) {
    println!("Breaking news! {}", item.summarize());
}

----

multiple trait bounds on a generic type using the `+` syntax

fn some_function<
    T: Display + Clone,
    U: Clone + Debug
> (t: T, u: U) -> i32 { }

or using `where`

fn some_function<T, U>(t: T, u: U) -> i32
    where T: Display + Clone,
          U: Clone + Debug
{ }

----

### Derive

an attribute for automatically adding `impl` of `trait` for `Struct`

#[derive(Copy, Clone, Default, Debug)]
Struct Foo { }

impl Copy for Foo { /*...*/ };
impl Clone for Foo { /*...*/ };
impl Default for Foo { /*...*/ };
impl Debug for Foo { /*...*/ };

----

### Trait Alias

pub trait Service { 
    type Request;
    type Response;
    type Error;
};

trait HttpService = Service<
    Request = http::Request,
    Reponse = http::Response,
    Error = http::Error
>;

---

## Conditionally implement method

`impl` could be many blocks.

Generics and trait bounds make sense for many block of implement method.

impl<T, U> Point<T, U> {}

impl<T> Point<T, U> {}

impl Point<T, U> {}

impl<T: Display + PartialOrd> Point<T> {}

----

### Blanket implementations

conditionally implement a trait for any type that implements another trait.

impl<T: Display> ToString for T {
    // --snip--
}

---

## STD traits

- Display: enable printing via `{}`
- Debug: enable printing via `{:?}` `{:#?}`
- ToString: output "Display" to string
- Default: return `Self`

----

PartialOrd/Ord/PartialEq/Eq

For a, b, c in a set X
1. Antisymmetry: if a < b, !(a>b);
   if a > b, then !(a < b)
2. Transitivity: a > b,  b > c, then a > c
3. Completeness: all elements in X must be one of
   relationships a > b,  a < b, or a == b
   
partail order: fit 1, 2
total order: fit 1, 2, 3

let nan = std::f32:NAN;
let x = 1.9f32;
println("{}", nan < x); // false
println("{}", nan > x); // false
println("{}", nan == x); // false
// IEEE754

---

### Example of Applying traits

I want to have a generic function that finds the largest one in `list`

fn largest<T>(list: &[T]) -> T {
    let mut largest = list[0];
    for &item in list.iter() {
        if item > largest {
            largest = item;
        }
    }
    largest
}

fn main() {
    let number_list = vec![34, 50, 25, 100, 65];
    println!("The largest number is {}", largest(&number_list));
    let char_list = vec!['y', 'm', 'a', 'q'];
    println!("The largest char is {}", largest(&char_list));
}

 note: `T` might need a bound for `std::cmp::PartialOrd`

----

Add `<T: PartialOrd + Copy>` here

fn largest<T: PartialOrd + Copy>(list: &[T]) -> T {
    let mut largest = list[0];

    for &item in list.iter() {
        if item > largest {
            largest = item;
        }
    }

    largest
}

try yourself: [link](https://play.rust-lang.org/?gist=ea6a9e77fbd366e6af75bf8c20c19a92&version=stable&mode=debug&edition=2015)

----

### How can I implement `PartialOrd`?

[rust document](https://github.com/rust-lang/rust/blob/4cf11765dc98536c6eedf33f2df7f72f6e161263/src/libcore/cmp.rs#L615)

use std::cmp::Ordering;

#[derive(Eq)]
struct Person { /* fields */}

impl PartialOrd for Person {
    fn partial_cmp(&self, other: &Person) -> Option<Ordering> {
         Some(self.cmp(other))
    }
}

impl Ord for Person {
    fn cmp(&self, other: &Person) -> Ordering {
        self.height.cmp(&other.height)
    }
}

impl PartialEq for Person {
    fn eq(&self, other: &Person) -> bool {
        self.height == other.height
    }
}

try yourself: [link](https://play.rust-lang.org/?gist=311513bf1b9f088ec7f5451b20e2d105&version=stable&mode=debug&edition=2015)

----

### Rust Generics VS C++ template

Rust checks right away

C++ check while instantiating

---

## Lifetime

----

### How Rust Prevent Dangling References

{
    let r;
    {
        let x = 5;
        r = &x;
    }
    println!("r: {}", r);
}

  --> src/main.rs:7:5
   |
6  |         r = &x;
   |              - borrow occurs here
7  |     }
   |     ^ `x` dropped here while still borrowed
...
10 | }
   | - borrowed value needs to live until here

----

### The Borrow Checker

{
    let r;                // ---------+-- 'a
                          //          |
    {                     //          |
        let x = 5;        // -+-- 'b  |
        r = &x;           //  |       |
    }                     // -+       |
                          //          |
    println!("r: {}", r); //          |
}                         // ---------+

----

The correct one

{
    let x = 5;            // ----------+-- 'b
                          //           |
    let r = &x;           // --+-- 'a  |
                          //   |       |
    println!("r: {}", r); //   |       |
                          // --+       |
}                         // ----------+

----

### Generic Lifetimes in Functions

fn longest(x: &str, y: &str) -> &str {
    if x.len() > y.len() {
        x
    } else {
        y
    }
}

 --> src/main.rs:1:33
  |
1 | fn longest(x: &str, y: &str) -> &str {
  |                                 ^ expected lifetime parameter
  |
  = help: this function's return type contains a borrowed value, but the
signature does not say whether it is borrowed from `x` or `y`

----

### Lifetime Annotation Syntax

&i32        // a reference
&'a i32     // a reference with an explicit lifetime
&'a mut i32 // a mutable reference with an explicit lifetime

annotations are meant to tell Rust how generic lifetime parameters of multiple references relate to each other.

----

A fixup for previous one

fn longest<'a>(x: &'a str, y: &'a str) -> &'a str {
    if x.len() > y.len() {
        x
    } else {
        y
    }
}

----

We don't need to declare lifetime if it has not "relationship to x" or "return value"

fn longest<'a>(x: &'a str, y: &str) -> &'a str {
    x
}

----

the lifetime parameter for the return type needs to match the lifetime parameter for one of the parameters

fn longest<'a>(x: &str, y: &str) -> &'a str {
    let result = String::from("really long string");
    result.as_str()
}

3 |     result.as_str()
  |     ^^^^^^ does not live long enough
4 | }
  | - borrowed value only lives until here

----

### Lifetime Annotations in Struct Definitions

struct ImportantExcerpt<'a> {
    part: &'a str,
}

fn main() {
    let novel = String::from("Call me Ishmael. Some years ago...");
    let first_sentence = novel.split('.')
        .next()
        .expect("Could not find a '.'");
    let i = ImportantExcerpt { part: first_sentence };
}

----

### Lifetime Elision

fn first_word<'a>(s: &'a str) -> &'a str { }

no need lifetime specification here

----

### Three rules

- each parameter that is a reference gets its own lifetime parameter

    fn foo<'a, 'b>(x: &'a i32, y: &'b i32)

- if there is exactly one input lifetime parameter, that lifetime is assigned to all output lifetime parameters

    fn foo<'a>(x: &'a i32) -> &'a i32

- if there is &self or &mut self because this is a method, the lifetime of self is assigned to all output lifetime

----

### Apply Three Rule

// origin
fn first_word(s: &str) -> &str { }
// first rule
fn first_word<'a>(s: &'a str) -> &str { }
// second rule
fn first_word<'a>(s: &'a str) -> &'a str { }

fn foo<'a>(s: &'a str) -> &'a str { }

----

### Static Lifetime

`'static` means the life is the entire duration of the program

fn foo<'a>() -> &'a str {
    "I have a static lifetime."
}

fn main() {
    println!("{}", foo());
}

fn foo() -> &'static str {
    "I have a static lifetime."
}

fn main() {
    println!("{}", foo());
}

---

## Combination

use std::fmt::Display;

fn longest_with_an_announcement<'a, T>(x: &'a str, y: &'a str, ann: T) -> &'a str
    where T: Display
{
    println!("Announcement! {}", ann);
    if x.len() > y.len() {
        x
    } else {
        y
    }
}

---

# The End