10. 泛型和特性：generic/trait

// 泛型类型：T 为泛型类型名称，名称位于类型名后的 <xx> 中。
// T 没有任何限界，默认为 Sized。
struct Point<T> { x: T, y: T, }
// 使用时，如果未指定泛型参数值，编译器自动推导
let p = Point{
    x: "5".to_string(),
    y : "hello".to_string()
};
// 使用时，为泛型参数指定具体类型，相当于实例化出一个匿名的具体类型
fn gen_spec_t(_s: Point<A>) {}
fn gen_spec_i32(_s: Point<i32>) {}

struct Val<T> {
    val: T,
}
// x 是 Val<f64> 类型
let x = Val{ val: 3.0 };
// y 是 Val<String> 类型
let y = Val{ val: "hello".to_string()};
// 3.0, hello
println!("{}, {}", x.value(), y.value());

// 泛型函数：类型参数位于函数名后的 <xx> 中。
fn generic<T>(_s: SGen<T>) {}
// 调用泛型函数时，使用比目鱼语法：method::<type>() 来指定泛型参数的具体类型。
generic::<char>(__);
// 为泛型类型实现关联函数或方法时，impl 后面需要列出泛型类型所需的所有泛型参数
//
// 函数和方法也可以定义自己的泛型参数, 它们不需要在 impl 后列出，而是在调用时推导或指定。
impl<T> Val<T> {
    // 方法可以使用 impl 的泛型参数
    fn value(&self) -> &T {
        &self.val
    }

    // 方法可以有自己的泛型参数
    fn add<O: Debug>(&self, other: O) {
        println!("{:?}", other);
    }
}

let x = Val { val: 3.0 };
let y = Val { val: "hello".to_string(), };
println!("{}, {}", x.value(), y.value());
x.add(123); // 推断
x.add::<i32>(123); // 为泛型方法手动指定类型，使用比目鱼语法。

// 对 T 无限制，等效于 Sized 限界
struct Pair<T> { x: T, y: T,}

impl<T> Pair<T> {
    fn new(x: T, y: T) -> Self {
        Self { x, y, }
    }
}

impl<T: std::fmt::Debug + PartialOrd> Pair<T> {
    fn cmp_display(&self) {
        if self.x >= self.y {
            println!("The largest member is x = {:?}", self.x);
        } else {
            println!("The largest member is y = {:?}", self.y);
        }
    }
}

// 泛型 trait，泛型参数 A、B 没有定义限界，默认为 Sized。
trait Contains<A, B> {
    fn contains(&self, _: &A, _: &B) -> bool;
    fn first(&self) -> i32;
    fn last(&self) -> i32;
}

// 实现泛型 trait 时，可以指定具体类型或者继续使用泛型参数。
impl Contains<i32, i32> for Container {
    fn contains(&self, number_1: &i32, number_2: &i32) -> bool {
        (&self.0 == number_1) && (&self.1 == number_2)
    }
    fn first(&self) -> i32 { self.0 }
    fn last(&self) -> i32 { self.1 }
}

// 泛型参数可以使用 + 号连接的多个 trait 或 lifetime 作为限界。
fn compare_prints<T: Debug + Display>(t: &T) {
    println!("Debug: `{:?}`", t);
    println!("Display: `{}`", t);
}

fn compare_types<T: Debug, U: Debug>(t: &T, u: &U) {
    println!("t: `{:?}`", t);
    println!("u: `{:?}`", u);
}

// 对于复杂的、较长的限界, 可以使用 where 子句来定义
impl <A: TraitB + TraitC, D: TraitE + TraitF> MyTrait<A, D> for YourType {}
// 等效于
impl <A, D> MyTrait<A, D> for YourType
    where
        A: TraitB + TraitC,
        D: TraitE + TraitF
 {
     //..
 }

// 有些场景必须使用 where 来限界，比如这里限界的是 Option<T>
trait PrintInOption {
    fn print_in_option(self);
}

impl<T> PrintInOption for T where Option<T>: Debug {
    fn print_in_option(self) {
        println!("{:?}", Some(self));
    }
}

// 定义泛型 trait 时，可以为泛型参数指定缺省类型
pub trait Add<Rhs = Self> {
    // 关联类型也可以指定缺省类型
    type Output = Self;

    // Required method
    fn add(self, rhs: Rhs) -> Self::Output;
}

struct ArrayPair<T, const N: usize> {
    left: [T; N],
    right: [T; N],
}

impl<T: Debug, const N: usize> Debug for ArrayPair<T, N> {
    // ...
}

// 实例化常量参数
fn foo<const N: usize>() {}

fn bar<T, const M: usize>() {
    foo::<M>();
    foo::<2021>();
    // OK：使用 <{xx}> 常量表达式
    foo::<{20 * 100 + 20 * 10 + 1}>();

    // Error: 常量表达式不支持泛型常量运算
    foo::<{ M + 1 }>();
    // Error: 常量表达式不支持泛型参数
    foo::<{ std::mem::size_of::<T>() }>();

    let _: [u8; M]; // OK
    // Error: const expression contains the generic parameter `T`
    let _: [u8; std::mem::size_of::<T>()];
}

trait Iterator {
    // 声明关联类型，同时对类型进行限界。使用 trait 限界语法。
    type Item: std::fmt::Display;

    fn next(&mut self) -> Option<Self::Item>;
}

pub trait Add<Rhs = Self> {
    // 关联类型也可以指定缺省类型。使用 type alias 语法。
    type Output = Self;

    // Required method
    fn add(self, rhs: Rhs) -> Self::Output;
}

// 定义泛型 trait 时，泛型参数和关联类型都可以指定缺省类型
pub trait Add<Rhs = Self> {
    type Output = Self;

    // Required method
    fn add(self, rhs: Rhs) -> Self::Output;
}

// 实现 trait 时，需要为关联类型指定具体类型
impl Add<Bar> for Foo {
    type Output = FooBar;

    fn add(self, _rhs: Bar) -> FooBar {
        FooBar
    }
}

// 定义一个泛型函数，使用 Add trait 作为泛型参数的限界，同时指定 Rhs 类型和关联类型。
// 不能使用 Rhs = Rhs, 否则 Rust 会报错没有 Rhs 关联类型。
fn add_values<T, Rhs>(a: T, b: Rhs) -> T
    where T: Add<Rhs, Output = T>
  { a + b }

// 使用带关联类型的 trait 做限界：
// 1. 可以不指定关联类型，在使用时由编译器推导；
// 2. 可以为关联类型做进一步限界
// 3. 可以使用关联类型
fn collect_into_vec<I: Iterator>(iter: I) -> Vec<I::Item>
    where I::Iterm: Debug {} // 对关联类型做进一步限界

// Iterator<Item=u8> 还是一个 trait，故：
// 1. 用作限界：
fn my_func<Iter: Iterator<Item=u8>>(iter: Iter) {}

// 2. 用作 trait object（需要将所有关联类型明确定义出来，否则编译时不能正确检查而报错）
fn dump(iter: &mut dyn Iterator<Item=String>) {}

struct EvenNumbers { count: usize, limit: usize, }
impl Iterator for EvenNumbers {
    // 实现 trait 时必须为关联类型指定 `具体类型` ，该具体类型需要满足该关联类型的限界要求。
    type Item = usize;

    // trait 的函数/方法，通过 Self::Item 引用关联类型
    fn next(&mut self) -> Option<Self::Item> {
        if self.count > self.limit {
            return None;
        }
        let ret = self.count * 2;
        self.count += 1;
        Some(ret)
    }
}

trait Float {
    // 定义常量时必须指定类型（编译器不会自动推导 const 值类型），但是可以不指定缺省值
    const ZERO: Self;
    const ONE: Self;
}

trait Greet{
    // 定义关联常量的类型和缺省值
    const GRETING: &'static str = "Hello",

    fn greet(&self) -> String;
}

impl Float for f32 {
    const ZERO: f32 = 0.0; // 实现 trait 时，为关联常量设置常量值
    const ONE: f32 = 1.0;
}

trait Trait {}

fn foo<X: Trait>(t: X) {}

impl<'a> Trait for &'a i32 {}

fn main() {
    let t: &mut i32 = &mut 0;
    foo(t); // 报错。
}

// error[E0277]: the trait bound `&mut i32: Trait` is not satisfied
//  --> src/main.rs:9:9
//   |
// 3 | fn foo<X: Trait>(t: X) {}
//   |           ----- required by this bound in `foo`
// ...
// 9 |     foo(t);
//   |         ^ the trait `Trait` is not implemented for `&mut i32`
//   |
//   = help: the following implementations were found:
//             <&'a i32 as Trait>
//   = note: `Trait` is implemented for `&i32`, but not for `&mut i32`

use std::ops::{Deref, DerefMut};

impl<T> Deref for Selector<T> {
    type Target = T;
    fn deref(&self) -> &T { &self.elements[self.current] }
}

impl<T> DerefMut for Selector<T> {
    fn deref_mut(&mut self) -> &mut T { &mut self.elements[self.current] }
}

// OK: 函数传参时, Rust 会自动隐式解引用, &Selector -> &str
let s = Selector { elements: vec!["good", "bad", "ugly"], current: 2 };
fn show_it(thing: &str) { println!("{}", thing); }
show_it(&s);

// Error: 使用 Trait 作为泛型参数的限界时, Rust 不会自动解引用到 &str 类型来满足类型限界的要求
use std::fmt::Display;
fn show_it_generic<T: Display>(thing: T) { println!("{}", thing); }
show_it_generic(&s);

show_it_generic(&s as &str); // 使用 as 类型转换;
show_it_generic(&*s) // 手动解引用 &*V 来得到 &str 类型

struct GenericVal<T>(T);
// 对于泛型类型，在 impl 时：
// 1. 如果指定了泛型参数类型，则不需要为 impl 指定泛型参数
impl GenericVal<f32> {}
// 2. 未指定具体类型时，必须在 impl<T> 中指定 GenericVal 类型的所有泛型参数
impl<T> GenericVal<T> {}
fn main() {
    // 创建泛型类型的值时，可以不指定泛型参数 T，由编译器自动推导
    let y = GenVal { gen_val: 3i32 };
    println!("{}, {}", x.value(), y.value());
}

struct Container(i32, i32);
trait Contains<A, B> {
    fn contains(&self, _: &A, _: &B) -> bool;
    fn first(&self) -> i32;
    fn last(&self) -> i32;
}
// 不需要使用 impl<i32, i32>
impl Contains<i32, i32> for Container {
    fn contains(&self, number_1: &i32, number_2: &i32) -> bool {
        (&self.0 == number_1) && (&self.1 == number_2)
    }
    fn first(&self) -> i32 { self.0 }
    fn last(&self) -> i32 { self.1 }
}

// 泛型 trait
trait DoubleDrop<T> {
    fn double_drop(self, _: T);
}

// 为 U 实现泛型 trait，U 本身也是泛型参数，所以相当于为所有 Sized 类型实现了 DoubleDrop trait。
impl<T, U> DoubleDrop<T> for U {
    fn double_drop(self, _: T) {}
}

// 为所有 &T 或 &mut T 实现 Deref<Target = T> trait：https://doc.rust-lang.org/src/core/ops/deref.rs.html#84
impl<T: ?Sized> Deref for &T {
    type Target = T;

    #[rustc_diagnostic_item = "noop_method_deref"]
    fn deref(&self) -> &T {
        *self
    }
}
impl<T: ?Sized> Deref for &mut T {
    type Target = T;

    fn deref(&self) -> &T {
        *self
    }
}

trait Person {
    fn name(&self) -> String;
}

// 等效于 trait Student where Self: Person
trait Student: Person {
    fn university(&self) -> String;
}

trait Programmer {
    fn fav_language(&self) -> String;
}

// 使用 + 运算符指定多个父 trait：
trait CompSciStudent: Programmer + Student {
    fn git_username(&self) -> String;
}

// 为父 trait 指定 lifetime 限界
trait Circle<'a> : Shape + 'a {
    fn radius(&self) -> f64;
}

// write_all() 方法是 std::io::Write trait 定义的，调用它前需要引入 Write trait。
use std::io::Write

let mut buf: Vec<u8> = vec![];
buf.write_all(b"hello")?;

trait Pilot {
    fn fly(&self);
}

trait Wizard {
    fn fly(&self);
}

struct Human;
impl Pilot for Human {
    fn fly(&self) {
        println!("This is your captain speaking.");
    }
}
impl Wizard for Human {
    fn fly(&self) {
        println!("Up!");
    }
}
impl Human {
    fn fly(&self) {
        println!("*waving arms furiously*");
    }
}

fn main() {
    let person = Human;
    // 调用 Human 自身实现的 fly() 方法。
    person.fly();

    // 调用实现的 trait 的方法，这里为了避免歧义，使用的是 TraitName::method(object).
    Pilot::fly(&person); // 等效于完全限定方法调用：<Human as Pilot>::fly(&person)
    Wizard::fly(&person);
}

trait CalSum {
    fn sum(&self, a: i32) -> i32;
}

trait CalSumV2 {
    fn sum(&self, a: i32) -> i32;
}

#[derive(Clone, Copy, Debug)]
struct S1(i32);

impl CalSum for S1 {
    fn sum(&self, a: i32) -> i32 {
        self.0 + a
    }
}

impl CalSumV2 for S1 {
    fn sum(&self, a: i32) -> i32 {
        self.0 + a
    }
}

fn main() {
    let s1 = S1(0);

    // 调用指定 trait 的方法
    println!("Results: {}", CalSum::sum(&s1, 1));
    println!("Results: {}", CalSumV2::sum(&s1, 1));

    // ERROR: S1 同时实现了 CalSum 和 CalSumV2, 它们都提供了 sum() 方法, Rust 不确定该调用哪一个。
    //println!("Results: {}", s1.sum(1)); // Error:  multiple `sum` found

    // 使用完全限定方法调用：调用 s1 对象对应的 S1 类型实现的 CalSum trait 的 sum 方法或关联函数。
    println!("Results: {}", <S1 as CalSum>::sum(&s1, 1)); // OK
}

let i: i8 = Default::default();
let (x, y): (Option<String>, f64) = Default::default();
let (a, b, (c, d)): (i32, u32, (bool, bool)) = Default::default();

#[derive(Default)]
struct SomeOptions {
    foo: i32,
    bar: f32,
}

fn main() {
    // 如果 SomeOptions 没有实现除 Default 外的其它 trait 的 default() 方法,
    // 则 <SomeOptions as Default>::default() 可以简写为 Default::default().
    let options: SomeOptions = Default::default();
    let options = SomeOptions { foo: 42, ..Default::default() };
}

// Rust 2021 前版本 dyn 关键字是可选的，2021 版本开始 dyn 关键字是必选的。
dyn Trait
dyn Trait + Send
dyn Trait + Send + Sync
dyn Trait + 'static
dyn Trait + Send + 'static
dyn Trait + Send + Sync + 'static
dyn (Trait)
dyn Trait + 'a
dyn eviction::EvictionManager + Sync

// 使用 & 时必须将 dyn 和后续的限制用括号括起来，否则会因歧义而报错。
&(dyn MyTrait + Send)

// error: expected expression, found keyword `dyn`
let b = &'a dyn MyTrait + Send + 'static;

// 表达式不能指定 'lifetime, 'lifetime 只能用于函数或方法的签名中。
// error: borrow expressions cannot be annotated with lifetimes
// let b = &'a (dyn MyTrait + Send + 'static);

// error: borrow expressions cannot be annotated with lifetimes
// printf_hello(Some(&'static my_struct));

trait MyTrait {
    fn say_hello(&self);
}

struct MyStruct(String);

impl MyTrait for MyStruct {
    fn say_hello(&self) {
        println!("hello {}", self.0);
    }
}

fn printf_hello(say_hello: Option<&(dyn MyTrait + Send)>) {
    // my_trait 是 &(dyn MyTrait + Send) 类型
    if let Some(my_trait) = say_hello {
        my_trait.say_hello();
    }
}

fn printf_hellov2(say_hello: Option<&Box<dyn MyTrait + Send + 'static>>) {
    // 错误：不能通过借用（共享或可变）来转移对象，my_trait 是 Box<dyn MyTrait + Send + 'static> 类型，转移了 Box 对象所有权
    // error[E0507]: cannot move out of `*say_hello` as enum variant `Some` which is behind a shared reference
    // if let Some(&my_trait) = say_hello {

    if let Some(my_trait) = say_hello {
        my_trait.say_hello();
    }
}

fn printf_hellov3(say_hello: Option<Box<dyn MyTrait + Send + 'static>>) {
    if let Some(my_trait) = say_hello {
        my_trait.say_hello();
    }
}

fn main() {

    let my_struct = MyStruct("abc".to_string());

    // expected `&dyn MyTrait`, found `MyStruct`
    // printf_hello(Some(my_struct));

    // OK
    printf_hello(Some(&my_struct));

    // error[E0308]: mismatched types，expected `&Box<dyn MyTrait + Send>`,
    // found `&Box<MyStruct>`
    // printf_hellov2(Some(&Box::new(my_struct)));

    // 解决办法：先创建一个 Box 对象，然后再借用，赋值时，通过 unsized type coercion 隐式自动类型转换。
    let st1: Box<dyn MyTrait + Send + 'static> = Box::new(my_struct);
    printf_hellov2(Some(&st1));

    let my_struct2 = MyStruct("def".to_string());
    printf_hellov3(Some(Box::new(my_struct2)));
}

struct Sheep {}

struct Cow {}

trait Animal {
    fn noise(&self) -> &'static str;
}

impl Animal for Sheep {
    fn noise(&self) -> &'static str {
        "baaaaah!"
    }
}

impl Animal for Cow {
    fn noise(&self) -> &'static str {
        "moooooo!"
    }
}

// 返回一个实现 Animal trait 的 Box 对象，编译期间不感知具体的实现类型
fn random_animal(random_number: f64) -> Box<dyn Animal> {
    if random_number < 0.5 {
        Box::new(Sheep {})
    } else {
        Box::new(Cow {})
    }
}

let val: Box<dyn Any + 'a> = Box::new(*val); // OK

// function or associated item cannot be called on `Box<dyn Any>` due to unsatisfied trait bounds,
// 115 | pub trait Any: 'static {
// | ---------------------- doesn't satisfy `dyn std::any::Any: std::marker::Sized`
// let val: Box<dyn Any + 'a> = Box::<dyn Any + 'a>::new(*val);

// Box::<&dyn Any>::new() 是 OK 的, 因为 &dyn Any 是 Sized 对象.
// let val: Box<&dyn Any> = Box::<&dyn Any>::new(&val);

let Box<dyn Trait> = Box::new(value);

// Parent 拥有 Box 的所有权，进而拥有 trait object 所有权。
//
// 当 Parent 对象被 drop 时，child 的 Box 的 trait object 也会被 drop
struct Parent {
    child: Box<dyn OtherTrait + 'static>,
}

struct MyApp {}
impl App for MyApp {}
fn main() {
    let mut registry = AppRegistry::new();

    // paas by value 传递对象，add() 拥有这个对象，所以满足 'static
    registry.add("thing", MyApp {});
    println!("apps: {}", registry.apps.len());
}

trait Foo { }

// 下面两个类型等效
type T1 = Box<dyn Foo>;
type T2 = Box<dyn Foo + 'static>;

// 这两个 impl 也是等效（dyn 是可选的）
impl dyn Foo {}
impl dyn Foo + 'static {}

// 下面两个类型等效，因为 &'a T 意味着 T: 'a
// 首先检查 containing type 是否有 lifetime，如果有的话且唯一，则使用它。
// 这里的 containing type 指的是 &'a dyn Foo 中的 &'a.
type T3<'a> = &'a dyn Foo;
type T4<'a> = &'a (dyn Foo + 'a);

// 下面两个类型等效，因为 std::cell::Ref<'a, T> 内部要求 T: 'a
type T5<'a> = std::cell::Ref<'a, dyn Foo>;
type T6<'a> = std::cell::Ref<'a, dyn Foo + 'a>;

// T 的 lifetime 需要同时满足 'a + 'b, 所以应该比 'a 和 'b 都长
struct TwoBounds<'a, 'b, T: ?Sized + 'a + 'b> {
    f1: &'a i32,
    f2: &'b i32,
    f3: T,
}
// Error: the lifetime bound for this object type cannot be deduced from context
type T7<'a, 'b> = TwoBounds<'a, 'b, dyn Foo>;

// trait object 只能指定一个 'lifetime
//
// error[E0226]: only a single explicit lifetime bound is permitted
type T7<'a, 'b> = TwoBounds<'a, 'b, dyn Foo + 'a + 'b>;

// OK
type T7<'a, 'b> = TwoBounds<'a, 'b, dyn Foo + 'a>;
// OK
type T7<'a, 'b, 'c> = TwoBounds<'a, 'b, dyn Foo + 'c>;

// 表示实现 Bar trait 类型的对象 lifetime 不能长于 'a
trait Bar<'a>: 'a { }

// 下面两种类型相同
type T1<'a> = Box<dyn Bar<'a>>;
type T2<'a> = Box<dyn Bar<'a> + 'a>;

// 下面两种类型相同
impl<'a> dyn Bar<'a> {}
impl<'a> dyn Bar<'a> + 'a {}

// For the following trait...
trait Bar<'a>: 'a { }

// ...these two are the same:
type T1<'a> = Box<dyn Bar<'a>>;
type T2<'a> = Box<dyn Bar<'a> + 'a>;

// ...and so are these:
impl<'a> dyn Bar<'a> {}
impl<'a> dyn Bar<'a> + 'a {}

// impl trait 作为函数参数的类型时，不需要引入泛型函数。
fn print_it1(input: impl Debug + 'static ) {
    println!( "'static value passed in is: {:?}", input );
}

// 等效为泛型参数版本，这个版本的优势是实例化时可以指定 T 的类型，但是 impl Debug 不行。
fn print_it<T: Debug + 'static>(input: T) {
    println!( "'static value passed in is: {:?}", input );
}

use std::iter;
use std::vec::IntoIter;
fn combine_vecs_explicit_return_type(v: Vec<i32>, u: Vec<i32>,
) -> iter::Cycle<iter::Chain<IntoIter<i32>, IntoIter<i32>>> {
    v.into_iter().chain(u.into_iter()).cycle()
}
// 等效为
fn combine_vecs(v: Vec<i32>, u: Vec<i32>, ) -> impl Iterator<Item=i32> {
    v.into_iter().chain(u.into_iter()).cycle()
}

trait App {}

struct AppRegistry {
    apps: HashMap<String, Box<dyn App>>,
}

impl AppRegistry {
    fn new() -> AppRegistry {
        Self { apps: HashMap::new() }
    }

    // impl App 必须加加 'static，否则 Box::new(app) 报错：
    // the parameter type `impl App` may not live long enough，the parameter type `impl App` must be valid for the static lifetime...
    // 这是因为 Box::new(app) 会转移 app 的所有权，所以 app 必须是 'static
    fn add(&mut self, name: &str, app: impl App + 'static) {
        self.apps.insert(name.to_string(), Box::new(app));
    }
}

// 错误：不兼容的类型
fn make_shape(shape: &str) -> impl Shape{
    match shape {
        "circle" => Circle::new(),
        "tiangle" => Triangle::new(),
        "shape" => Retangle::new(),
    }
}

fn make_adder_function(y: i32) -> impl Fn(i32) -> i32 {
    let closure = move |x: i32| { x + y };
    closure
}

fn main() {
    let plus_one = make_adder_function(1);
    assert_eq!(plus_one(2), 3);
}

fn returns_closure() -> Box<dyn Fn(i32) -> i32> {
    Box::new(|x| x + 1) // 堆分配空间，性能差些
}

fn returns_closure() -> impl Fn(i32) -> i32 {
    |x| x + 1 // 栈分配，性能好
}

pub struct PhantomData<T> where T: ?Sized;

pub trait Copy: Clone { }

// OK: i32 实现了 Copy
#[derive(Copy, Clone)]
struct Point {
    x: i32,
    y: i32,
}

// 错误: Vec<T> 没有实现 Copy
#[derive(Copy, Clone)]
struct PointList {
    points: Vec<Point>,
}

// OK: 因为 &T 实现了 Copy, 即使 T 没有实现 Copy, &T 也实现了 Copy
#[derive(Copy, Clone)]
struct PointListWrapper<'a> {
    point_list_ref: &'a PointList,
}

// 或者
struct MyStruct;

impl Copy for MyStruct { }

impl Clone for MyStruct {
    fn clone(&self) -> MyStruct {
        *self
    }
}

pub struct Second {
    value: u64,
}

impl Second {
    pub fn value(&self) -> u64 {
        self.value
    }
}

impl Default for Second {
    fn default() -> Self {
        Self { value: 0 }
    }
}