Generics & Traits

CIS 198 Lecture 3

Generics

• Suppose we simplify the Resultish enum from last week a bit…

1. enum Result {
2. Ok(String),
3. Err(String),
4. }

• Better, but it’s still limited to passing two values which are both Strings.

Generics

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

1. enum Result<T, E> {
2. Ok(T),
3. Err(E),
4. }

• T and E stand in for any generic type, not only Strings.
• You can use any CamelCase identifier for generic types.

Generic Structs

• Let’s take a look at generic versions of several other structs from last week:

1. struct Point<T> {
2. x: T,
3. y: T,
4. }

6. enum List<T> {
7. Nil,
8. Cons(T, Box<List<T>>),
9. }

Generic Implementations

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

1. impl<T, E> Result<T, E> {
2. fn is_ok(&self) -> bool {
3. match *self {
4. Ok(_) => true,
5. Err(_) => false,
6. }
7. }
8. }

Traits

• Implementing functions on a per-type basis to pretty-print, compute equality, etc. is fine, but unstructured.
• We currently have no abstract way to reason about what types can do what!

1. struct Point {
2. x: i32,
3. y: i32,
4. }

6. impl Point {
7. fn format(&self) -> String {
8. format!("({}, {})", self.x, self.y)
9. }

11. fn equals(&self, other: Point) -> bool {
12. self.x == other.x && self.y == other.y
13. }
14. }

Traits

• Solution: Traits (coming right now)!
• Like we say every week, these are similar to Java interfaces or Haskell typeclasses

Traits

• To define a trait, use a trait block, which gives function definitions for the required methods.
• This is not the same as an impl block.
• Mostly only contains method signatures without definitions.

1. trait PrettyPrint {
2. fn format(&self) -> String;
3. }

Traits

• To implement a trait, use an impl Trait for Type block.
• All methods specified by the trait must be implemented.
• One impl block per type per trait.
• You can use self/&self inside the trait impl block as usual.

1. struct Point {
2. x: i32,
3. y: i32,
4. }

6. impl PrettyPrint for Point {
7. fn format(&self) -> String {
8. format!("({}, {})", self.x, self.y)
9. }
10. }

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.”

1. fn foo<T, U>(x: T, y: U) {
2. // ...
3. }

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 or with a where clause.
• “where T is Clone“

1. fn cloning_machine<T: Clone>(t: T) -> (T, T) {
2. (t.clone(), t.clone())
3. }

5. fn cloning_machine_2<T>(t: T) -> (T, T)
6. where T: Clone {
7. (t.clone(), t.clone())
8. }

Generics with Trait Bounds

• Multiple trait bounds are specified like T: Clone + Ord.
• There’s no way (yet) to specify negative trait bounds.
• e.g. you can’t stipulate that a T must not be Clone.

1. fn clone_and_compare<T: Clone + Ord>(t1: T, t2: T) -> bool {
2. t1.clone() > t2.clone()
3. }

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

Generic Types With Trait Bounds

1. enum Result<T, E> {
2. Ok(T),
3. Err(E),
4. }

6. trait PrettyPrint {
7. fn format(&self) -> String;
8. }

10. impl<T: PrettyPrint, E: PrettyPrint> PrettyPrint for Result<T, E> {
11. fn format(&self) -> String {
12. match *self {
13. Ok(t) => format!("Ok({})", t.format()),
14. Err(e) => format!("Err({})", e.format()),
15. }
16. }
17. }

Examples: Equality

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

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

8. impl<T: Equals, E: Equals> Equals for Result<T, E> {
9. fn equals(&self, other: &Self) -> bool {
10. match (*self, *other) {
11. Ok(t1), Ok(t2) => t1.equals(t2),
12. Err(e1), Err(e2) => e1.equals(e2),
13. _ => false
14. }
15. }
16. }

• Self is a special type which refers to the type of self.

Inheritance

• 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.

1. trait Parent {
2. fn foo(&self) {
3. // ...
4. }
5. }

7. trait Child: Parent {
8. fn bar(&self) {
9. self.foo();
10. // ...
11. }
12. }

Default Methods

• Traits can have default implementations for methods!
• Useful if you have an idea of how an implementor will commonly define a trait method.
• When a default implementation is provided, the implementor of the trait doesn’t need to define that method.
• Define default implementations of trait methods by simply writing the body in the trait block.

1. trait PartialEq<Rhs: ?Sized = Self> {
2. fn eq(&self, other: &Rhs) -> bool;

4. fn ne(&self, other: &Rhs) -> bool {
5. !self.eq(other)
6. }
7. }

9. trait Eq: PartialEq<Self> {}

Default Methods

• Implementors of the trait can overwrite default implementations, but make sure you have a good reason to!
• e.g., never define ne so that it violates the relationship between eq and ne.

Deriving

• Many traits are so straightforward that the compiler can often implement them for you.
• A #[derive(...)] attribute tells the compiler to insert a default implementation for whatever traits you tell it to.
• This removes the tedium of repeatedly manually implementing traits like Clone yourself!

1. #[derive(Eq, PartialEq, Debug)]
2. enum Result<T, E> {
3. Ok(T),
4. Err(E)
5. }

Deriving

• You can only do this for the following core traits:
• Clone, Copy, Debug, Default, Eq,
• Hash, Ord, PartialEq, PartialOrd.
• Deriving custom traits is an unstable feature as of Rust 1.6.
• Careful: deriving a trait won’t always work.
• Can only derive a trait on a data type when all of its members can have derived the trait.
• e.g., Eq can’t be derived on a struct containing only f32s, since f32 is not Eq.

Core traits

• It’s good to be familiar with the core traits.
• Clone, Copy
• Debug
• Default
• Eq, PartialEq
• Hash
• Ord, PartialOrd

Clone

1. pub trait Clone: Sized {
2. fn clone(&self) -> Self;

4. fn clone_from(&mut self, source: &Self) { ... }
5. }

• A trait which defines how to duplicate a value of type T.
• This can solve ownership problems.
• You can clone an object rather than taking ownership or borrowing!

Clone

1. #[derive(Clone)] // without this, Bar cannot derive Clone.
2. struct Foo {
3. x: i32,
4. }

6. #[derive(Clone)]
7. struct Bar {
8. x: Foo,
9. }

Copy

1. pub trait Copy: Clone { }

• Copy denotes that a type has “copy semantics” instead of “move semantics.”
• Type must be able to be copied by copying bits (memcpy).
• Types that contain references cannot be Copy.
• Marker trait: does not implement any methods, but defines behavior instead.
• In general, if a type can be Copy, it should be Copy.

Debug

1. pub trait Debug {
2. fn fmt(&self, &mut Formatter) -> Result;
3. }

• Defines output for the {:?} formatting option.
• Generates debug output, not pretty printed.
• Generally speaking, you should always derive this trait.

1. #[derive(Debug)]
2. struct Point {
3. x: i32,
4. y: i32,
5. }

7. let origin = Point { x: 0, y: 0 };
8. println!("The origin is: {:?}", origin);
9. // The origin is: Point { x: 0, y: 0 }

Default

1. pub trait Default: Sized {
2. fn default() -> Self;
3. }

• Defines a default value for a type.

Eq vs. PartialEq

1. pub trait PartialEq<Rhs: ?Sized = Self> {
2. fn eq(&self, other: &Rhs) -> bool;

4. fn ne(&self, other: &Rhs) -> bool { ... }
5. }

7. pub trait Eq: PartialEq<Self> {}

• Traits for defining equality via the == operator.

Eq vs. PartialEq

• PartialEq represents a partial equivalence relation.
• Symmetric: if a == b then b == a
• Transitive: if a == b and b == c then a == c
• ne has a default implementation in terms of eq.
• Eq represents a total equivalence relation.
• Symmetric: if a == b then b == a
• Transitive: if a == b and b == c then a == c
• Reflexive: a == a
• Eq does not define any additional methods.
• (It is also a Marker trait.)

Hash

1. pub trait Hash {
2. fn hash<H: Hasher>(&self, state: &mut H);

4. fn hash_slice<H: Hasher>(data: &[Self], state: &mut H)
5. where Self: Sized { ... }
6. }

• A hashable type.
• The H type parameter is an abstract hash state used to compute the hash.
• If you also implement Eq, there is an additional, important property:

1. k1 == k2 -> hash(k1) == hash(k2)

¹taken from Rustdocs

Ord vs. PartialOrd

1. pub trait PartialOrd<Rhs: ?Sized = Self>: PartialEq<Rhs> {
2. // Ordering is one of Less, Equal, Greater
3. fn partial_cmp(&self, other: &Rhs) -> Option<Ordering>;

5. fn lt(&self, other: &Rhs) -> bool { ... }
6. fn le(&self, other: &Rhs) -> bool { ... }
7. fn gt(&self, other: &Rhs) -> bool { ... }
8. fn ge(&self, other: &Rhs) -> bool { ... }
9. }

• Traits for values that can be compared for a sort-order.

Ord vs. PartialOrd

• The comparison must satisfy, for all a, b and c:
• Antisymmetry: if a < b then !(a > b), as well as a > b implying !(a < b); and
• Transitivity: a < b and b < c implies a < c. The same must hold for both == and >.
• lt, le, gt, ge have default implementations based on partial_cmp.

¹taken from Rustdocs

Ord vs. PartialOrd

1. pub trait Ord: Eq + PartialOrd<Self> {
2. fn cmp(&self, other: &Self) -> Ordering;
3. }

• Trait for types that form a total order.
• An order is a total order if it is (for all a, b and c):
• total and antisymmetric: exactly one of a < b, a == b or a > b is true; and
• transitive, a < b and b < c implies a < c. The same must hold for both == and >.
• When this trait is derived, it produces a lexicographic ordering.

¹taken from Rustdocs

Associated Types

• Take this Graph trait from the Rust book:

1. trait Graph<N, E> {
2. fn edges(&self, &N) -> Vec<E>;
3. // etc
4. }

• N and E are generic type parameters, but they don’t have any meaningful association to Graph
• Also, any function that takes a Graph must also be generic over N and E!

1. fn distance<N, E, G: Graph<N,E>>(graph: &G, start: &N, end: &N)
2. -> u32 { /*...*/ }

Associated Types

• Solution: associated types!
• type definitions inside a trait block indicate associated generic types on the trait.
• An implementor of the trait may specify what the associated types correspond to.

1. trait Graph {
2. type N;
3. type E;

5. fn edges(&self, &Self::N) -> Vec<Self::E>;
6. }

8. impl Graph for MyGraph {
9. type N = MyNode;
10. type E = MyEdge;

12. fn edges(&self, n: &MyNode) -> Vec<MyEdge> { /*...*/ }
13. }

Associated Types

• For example, in the standard library, traits like Iterator define an Item associated type.
• Methods on the trait like Iterator::next then return an Option<Self::Item>!
• This lets you easily specify what type a client gets by iterating over your collection.

Trait Scope

• Say our program defines some trait Foo.
• It’s possible to implement this trait on any type in Rust, including types that you don’t own:

1. trait Foo {
2. fn bar(&self) -> bool;
3. }

5. impl Foo for i32 {
6. fn bar(&self) -> bool {
7. true
8. }
9. }

• But this is really bad practice. Avoid if you can!

Trait Scope

• The scope rules for implementing traits:
• You need to use a trait in order to access its methods on types, even if you have access to the type.
• In order to write an impl, you need to own (i.e. have yourself defined) either the trait or the type.

Display

1. pub trait Display {
2. fn fmt(&self, &mut Formatter) -> Result<(), Error>;
3. }

5. impl Display for Point {
6. fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
7. write!(f, "Point {}, {})", self.x, self.y)
8. }
9. }

• Defines output for the {} formatting option.
• Like Debug, but should be pretty printed.
• No standard output and cannot be derived!
• You can use write! macro to implement this without using Formatter.

Addendum: Drop

1. pub trait Drop {
2. fn drop(&mut self);
3. }

• A trait for types that are destructable (which is all types).
• Drop requires one method, drop, but you should never call this method yourself.
• It’s inserted automatically by the compiler when necessary.

Addendum: Drop

• Typically, you won’t actually implement Drop for a type
• Generally the default implementation is fine.
• You also don’t need to derive Drop either.
• Why implement Drop then?
• If you need some special behavior when an object gets destructed.

Addendum: Drop

• Example: Rust’s reference-counted pointer type Rc<T> has special Drop rules:
• If the number of references to an Rc pointer is greater than 1, drop decrements the ref count.
• The Rc is actually deleted when the reference count drops to 0.

Addendum: Sized vs. ?Sized

• Sized indicates that a type has a constant size known at compile time!
• Its evil twin, ?Sized, indicates that a type might be sized.
• By default, all types are implicitly Sized, and ?Sized undoes this.
• Types like [T] and str (no &) are ?Sized.
• For example, Box<T> allows T: ?Sized.
• You rarely interact with these traits directly, but they show up a lot in trait bounds.

Trait Objects

• Consider the following trait, and its implementors:

1. trait Foo { fn bar(&self); }

3. impl Foo for String {
4. fn bar(&self) { /*...*/ }
5. }

7. impl Foo for usize {
8. fn bar(&self) { /*...*/  }
9. }

Trait Objects

• We can call either of these versions of bar via static dispatch using any type with bounds T: Foo.
• When this code is compiled, the compiler will insert calls to specialized versions of bar
• One function is generated for each implementor of the Foo trait.

1. fn blah(x: T) where T: Foo {
2. x.bar()
3. }

5. fn main() {
6. let s = "Foo".to_string();
7. let u = 12;

9. blah(s);
10. blah(u);
11. }

Trait Objects

• It is also possible to have Rust perform dynamic dispatch through the use of trait objects.
• A trait object is something like Box<Foo> or &Foo
• The data behind the reference/box must implement the trait Foo.
• The concrete type underlying the trait is erased; it can’t be determined.

Trait Objects

1. trait Foo { /*...*/ }

3. impl Foo for char { /*...*/ }
4. impl Foo for i32  { /*...*/ }

6. fn use_foo(f: &Foo) {
7. // No way to figure out if we got a `char` or an `i32`
8. // or anything else!
9. match *f {
10. // What type do we have? I dunno...
11. // error: mismatched types: expected `Foo`, found `_`
12. 198 => println!("CIS 198!"),
13. 'c' => println!("See?"),
14. _ => println!("Something else..."),
15. }
16. }

18. use_foo(&'c'); // These coerce into `&Foo`s
19. use_foo(&198i32);

Trait Objects

• When a trait object is used, method dispatch must be performed at runtime.
• The compiler can’t know the type underlying the trait reference, since it was erased.
• This causes a runtime penalty, but is useful when handling things like dynamically sized types.

Object Safety

• Not all traits can be safely used in trait objects!
• Trying to create a variable of type &Clone will cause a compiler error, as Clone is not object safe.
• A trait is object-safe if:
• It does not require that Self: Sized
• Its methods must not use Self
• Its methods must not have any type parameters
• Its methods do not require that Self: Sized

¹taken from Rustdocs

Addendum: Generics With Lifetime Bounds

• Some generics may have lifetime bounds like T: 'a.
• Semantically, this reads as “Type T must live at least as long as the lifetime 'a.”
• Why is this useful?

Addendum: Generics With Lifetime Bounds

• Imagine you have some collection of type T.
• If you iterate over this collection, you should be able to guarantee that everything in it lives as long as the collection.
• If you couldn’t, Rust wouldn’t be safe!
• std::Iterator structs usually contain these sorts of constraints.