> For the complete documentation index, see [llms.txt](https://osh.fducslg.com/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://osh.fducslg.com/notes/rust/traits-and-generics.md). # Traits and Generics **Polymorphism**: 多态 in Chinese. Rust supports polymorphism with two features: traits and generics. ```rust use std::io::Write; fn say_hello(out: &mut dyn Write) -> std::io::Result<()> { out.write_all(b"hello world\n")?; out.flush() } ``` The type of `out` is `&mut dyn Write`, meaning “a mutable reference to any value that implements the `Write` trait.” ## Using Traits **Examples**: * A value that implements `std::io::Write` can write out bytes. * A value that implements `std::iter::Iterator` can produce a sequence of values. * A value that implements `std::clone::Clone` can make clones of itself in memory. * A value that implements `std::fmt::Debug` can be printed using `println!()` with the `{:?}` format specifier. The trait itself must be in scope. Otherwise, all its methods are hidden. Some traits has been imported implicitly as part of the standard prelude. ```rust use std::io::Write; let mut buf: Vec = vec![]; buf.write_all(b"hello")?; // ok ``` The calls to `write_alls` are statically decided, resulting in low overhead. However, the calls through `&mut dyn Write` incur the overhead of a dynamic dispatch, also known as a virtual method call, which is indicated by the `dyn` keyword in the type. There are two ways of using traits to write polymorphic code in Rust: **trait objects** and **generics**. ### Trait Objects Rust doesn’t permit variables of type `dyn Write`: ```rust use std::io::Write; let mut buf: Vec = vec![]; let writer: dyn Write = buf; // error: `Write` does not have a constant size let writer: &mut dyn Write = &mut buf; // ok ``` A variable’s size has to be known at compile time, and types that implement `Write` can be any size. (Since `dyn Write` could potentially refer to any type implementing the `Write` trait, its size is not fixed). A reference to a trait type, like `writer`, is called a *trait object*. Like any other reference, a trait object points to some value, it has a lifetime, and it can be either `mut` or shared. What makes a trait object different is that Rust usually doesn’t know the type of the referent at compile time. **Memory Representation** A trait object in memory is a fat pointer that includes two components: a pointer to the actual value and a pointer to a table that represents the value's type. Because of this, a trait object occupies two machine words. The trait object (indicated by `&dyn`, which is a fat pointer) differs from a regular reference, which is just a bare pointer. In other words, `&dyn` and `&` are distinct types.
A diagram showing trait objects in memory.
> In C++, the vtable pointer, or *vptr*, is stored as part of the struct. Rust uses fat pointers instead. This way, a struct can implement dozens of traits without containing dozens of vptrs. **Auto Conversion** Rust automatically converts ordinary references into trait objects when needed. ```rust let mut local_file = File::create("hello.txt")?; say_hello(&mut local_file)?; ``` The type of `&mut local_file` is `&mut File`, and the type of the argument to `say_hello` is `&mut dyn Write`. Since a `File` is a kind of writer, Rust allows this, automatically converting the plain reference to a trait object. Likewise, Rust will happily convert a `Box` to a `Box`, a value that owns a writer in the heap: ```rust let w: Box = Box::new(local_file); ``` `Box`, like `&mut dyn Write`, is a fat pointer: it contains the address of the writer itself and the address of the vtable. The same goes for other pointer types, like `Rc`. ### Generic Functions and Type Parameters ```rust fn say_hello(out: &mut W) -> std::io::Result<()> { out.write_all(b"hello world\n")?; out.flush() } ``` When you pass `&mut local_file` to the generic `say_hello()` function, you’re calling `say_hello::()`. Rust infers the type `W` from the type of the argument and generate machine code for the calls to the corresponding versions of functions. This process is known as *monomorphization* (单态化), and the compiler handles it all automatically. *** ```rust use std::hash::Hash; use std::fmt::Debug; fn top_ten(values: &Vec) { ... } ```
A Venn diagram shows the three sets of types.
A generic function can have both lifetime parameters and type parameters. Lifetime parameters come first. ```rust /// Return a reference to the point in `candidates` that's /// closest to the `target` point. fn nearest<'t, 'c, P>(target: &'t P, candidates: &'c [P]) -> &'c P where P: MeasureDistance { ... } ``` In addition to types and lifetimes, generic functions can take **constant parameters** as well. ```rust fn dot_product(a: [f64; N], b: [f64; N]) -> f64 { let mut sum = 0.; for i in 0..N { sum += a[i] * b[i]; } sum } ``` ### Trait Objects or Generic Code? Sometimes you want to manage a group of objects of different types - but implementing the same trait, it's not a good idead to use generic code, which is hard to express "objects of different types". Check out the example from the book: ```rust trait Vegetable { ... } struct Salad { veggies: Vec } ``` The `Vec` can only hold objects of the same type `V`, which might be `IcebergLettuce`, which is not ideal for the need that `veggies` should contain vegetables of different types. In contrast, you can use trait objects: ```rust struct Salad { veggies: Vec> } ``` Use trait objects can also reduce the total amount of compiled code. *** Outside of situations involving salad or low-resource environments, generics have three important advantages over trait objects, resulting in generics being the more common choice. * **Speed**: The `dyn` keyword isn’t used because there are no trait objects—and thus no dynamic dispatch—involved. * **Not every trait can support trait objects** * **Easy to bound a generic type parameter with several traits at once**: types like `&mut (dyn Debug + Hash + Eq)` aren’t supported in Rust. ## Defining and Implementing Traits ```rust trait Visible { fn draw(&self, canvas: &mut Canvas); } impl Brrom { /// Helper function used by Broom::draw() below. } impl Visible for Broom { fn draw(&self, canvas: &mut Canvas) { ... } } ``` Traits can also include default implementation. You can use a generic `impl` block to add an extension trait to a whole family of types at once. ### Self in Traits ```rust pub trait Spliceable { fn splice(&self, other: &Self) -> Self; } ``` Using `Self` as the return type here means that the type of `x.clone()` is the same as the type of `x`. ```rust impl Spliceable for CherryTree { fn splice(&self, other: &Self) -> Self { ... } } ``` `Self` is an alias for the type of struct. **A trait that uses the `Self` type is incompatible with trait objects.** ```rust // error: the trait `Spliceable` cannot be made into an object // This calls back to the statement that not every trait can support trait objects. fn splice_anything(left: &dyn Spliceable, right: &dyn Spliceable) { let combo = left.splice(right); // ... } ``` Rust rejects this code because it has no way to type-check the call `left.splice(right)`. The whole point of trait objects is that the type isn’t known until run time. Rust has no way to know at compile time if `left` and `right` will be the same type, as required. But we can design a **trait-object-friendly** trait: ```rust pub trait MegaSpliceable { fn splice(&self, other: &dyn MegaSpliceable) -> Box; } ``` ### Subtraits Say that `Creature` is a *subtrait* of `Visible`, and that `Visible` is `Creature`’s *supertrait*. Subtraits extend the functionality of their supertraits. Every type that implements `Creature` must also implement the `Visible` trait. ```rust /// Someone in the game world, either the player or some other /// pixie, gargoyle, squirrel, ogre, etc. trait Creature: Visible { fn position(&self) -> (i32, i32); fn facing(&self) -> Direction; ... } impl Visible for Broom { ... } impl Creature for Broom { ... } ``` The syntax of subtraits can be experssed in the following fashion also: ```rust trait Creature where Self: Visible { ... } ``` ### Type-Associated Functions Traits can include type-associated functions, Rust’s analog to **static methods**. ```rust trait StringSet { /// Return a new empty set. fn new() -> Self; /// Return a set that contains all the strings in `strings`. fn from_slice(strings: &[&str]) -> Self; /// Find out if this set contains a particular `value`. fn contains(&self, string: &str) -> bool; /// Add a string to this set. fn add(&mut self, string: &str); } ``` `from_slice` and `new` don't take a `self` argument. These functions can be called using `::` syntax, just like any other type-associated function. ## Fully Qualified Method Calls **Fully qualified method calls** tell your intention precisely by specifying the exact method we can calling. ```rust "hello".to_string() str::to_string("hello") ToString::to_string("hello") ::to_string("hello") // This is the fully qualified method call. ``` > The `.` operator does not say exactly which `to_string` method we are calling and Rust has a method to lookup algorithm that figures this out. **Application**: * There are methods with the same name from different traits: ```rust outlaw.draw(); // error: draw on screen or draw pistol? Visible::draw(&outlaw); // ok: draw on screen HasPistol::draw(&outlaw); // ok: corral ``` * When the type of the `self` argument can’t be inferred: ```rust let zero = 0; // type unspecified; could be `i8`, `u8`, ... zero.abs(); // error: can't call method `abs` // on ambiguous numeric type i64::abs(zero); // ok ``` * When using the function itself as a function value: ```rust let words: Vec = line.split_whitespace() // iterator produces &str values .map(ToString::to_string) // ok .collect(); ``` * When calling trait methods in macros. ## Traits That Define Relationships Between Types The standard `Iterator` trait of Rust: ```rust pub trait Iterator { type Item; fn next(&mut self) -> Opiton; } ``` * `type Item;` is an ***associated type***. Each type that implements `Iterator` must specify what type of item it produces. To implement `Iterator` for a type: ```rust // (code from the std::env standard library module) impl Iterator for Args { type Item = String; fn next(&mut self) -> Option { ... } ... } ``` `std::env::Args` is the type of iterator returned by the standard library function `std::env::args()`. It produces `String` values. *** Generic code can use associated types: ```rust fn collect_into_vector(iter: I) -> Vec { let mut results = Vec::new(); for value in iter { results.push(value); } results } ``` Rust can infer the type of `value` inside the function, but we still need to sepcify the type of the return value. You can also write the generic code in the following manner: ```rust fn dump(iter: I) where I: Iterator { ... } // or fn dump(iter: &mut dyn Iterator) { for (index, s) in iter.enumerate() { println("{}: {:?}", index, s); } } ``` ### Generic Traits (or How Operator Overloading Works) ```rust /// The std::ops::Mul trait, which allows types to support the `*` operator pub trait Mul { /// The resulting type after applying the `*` operator type Output; /// The method that defines the behavior of the `*` operator fn mul(self, rhs: RHS) -> Self::Output; } ``` * As shown, the `Self` type is associated with and used by the definitions of traits. * While traits are typically used to enable polymorphism, they can themselves be designed with polymorphic behavior, allowing for multiple variants or implementations. This is a generic trait, the instances of which correspond to the underlying type of `RHS`. For instance, `Mul` and `Mul` are different types. Therefore, a single type—say, `WindowSize`—can implement both `Mul` and `Mul`, and many more. The syntax `RHS=Self` means that `RHS` defaults to `Self`. ### Return `impl Trait` We can simplify the return type of a function by specifying the trait or traits that the return value implements: ```rust fn cyclical_zip(v: Vec, u: Vec) -> impl Iterator { v.into_iter().chain(u.into_iter()).cycle() } ``` However, you cannot use `impl Trait` to implement the factory pattern directly: ```rust trait Shape { fn new() -> Self; fn area(&self) -> f64; } fn make_shape(shape: &str) -> impl Shape { match shape { "circle" => Circle::new(), "triangle" => Triangle::new(), "rectangle" => Rectangle::new(), } } ``` In the first example, the return type is clear because `v` and `u` are both `Vec`, so the function returns an iterator over `u8`. However, in the second example, the return type could be `Circle`, `Triangle`, or `Rectangle`, which means the return type is not uniquely determined. Additionally, `impl Trait` can only be used in free functions (i.e., functions not associated with a trait) or in methods associated with specific types, but not in trait methods themselves. This limitation exists because the return type of a trait method must be explicitly known and consistent across all implementations of the trait. ### Associated Consts Like structs and enums, traits can have associated constants. You can declare a trait with an associated constant using the same syntax as for a struct or enum: ```rust trait Greet { const GREETING: &'static str = "Hello"; fn greet(&self) -> String; } ``` This allows you to write generic code that uses these values: ```rust fn add_one>(value: T) -> T { value + T::ONE } ``` Associated constants can’t be used with trait objects, since the compiler relies on type information about the implementation to pick the right value at compile time.