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

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

How can I implement PartialOrd?

rust document

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

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

Select a repo