Chapter 2: Advanced Type System

Rust's type system is one of its most powerful features. This chapter explores advanced type system concepts that enable you to write safer, more expressive code while maintaining zero-cost abstractions.

2.1 Associated Types

Associated types let you define placeholder types in trait definitions. They're cleaner than generic type parameters when there's only one logical type for a given implementation.

Associated Types vs Generic Type Parameters

// Using generic type parameters (verbose)
trait Container<T> {
    fn get(&self) -> Option<&T>;
}

// Using associated types (cleaner)
trait BetterContainer {
    type Item;
    fn get(&self) -> Option<&Self::Item>;
}

// Implementation
impl BetterContainer for Vec<String> {
    type Item = String;

    fn get(&self) -> Option<&Self::Item> {
        self.first().cloned()
    }
}

fn use_container(c: &impl BetterContainer) {
    if let Some(item) = c.get() {
        // We can use item here
    }
}

Real-World Example: Custom Iterator

struct Counter {
    count: u32,
    max: u32,
}

impl Counter {
    fn new(max: u32) -> Self {
        Self { count: 0, max }
    }
}

impl Iterator for Counter {
    type Item = u32;  // Associated type

    fn next(&mut self) -> Option<Self::Item> {
        if self.count < self.max {
            self.count += 1;
            Some(self.count)
        } else {
            None
        }
    }
}

fn main() {
    let counter = Counter::new(5);
    let sum: u32 = counter.sum();
    println!("Sum: {}", sum); // 15
}

2.2 Type Aliases

Type aliases make complex types easier to work with and can improve code readability:

// Simple type alias
type Kilometers = i32;

// Complex type alias
type Result<T> = std::result::Result<T, std::io::Error>;

// Makes function signatures much cleaner
fn read_file(path: &str) -> Result<String> {
    std::fs::read_to_string(path)
}

// Generic type alias
type NodeBox<T> = Box<Node<T>>;

struct Node<T> {
    value: T,
    left: Option<NodeBox<T>>,
    right: Option<NodeBox<T>>,
}

// Trait object alias
type Handler = Box<dyn Fn(Request) -> Response + Send + Sync>;

struct Server {
    handlers: Vec<Handler>,
}

Associated Type Defaults

trait Graph {
    type Node = String;  // Default associated type
    type Edge = (String, String);

    fn add_node(&mut self, node: Self::Node);
    fn add_edge(&mut self, edge: Self::Edge);
}

// Can use default
struct SimpleGraph {
    nodes: Vec<String>,
}

impl Graph for SimpleGraph {
    // Uses default Node = String
    fn add_node(&mut self, node: Self::Node) {
        self.nodes.push(node);
    }

    fn add_edge(&mut self, edge: Self::Edge) {
        // implementation
    }
}

// Or override the default
struct CustomGraph;

impl Graph for CustomGraph {
    type Node = u32;  // Override default
    type Edge = (u32, u32);

    fn add_node(&mut self, _node: Self::Node) {}
    fn add_edge(&mut self, _edge: Self::Edge) {}
}

2.3 The Newtype Pattern

The newtype pattern wraps existing types in a new type for type safety and to implement external traits:

Type Safety with Newtypes

// Prevent mixing up different kinds of IDs
struct UserId(u64);
struct ProductId(u64);
struct OrderId(u64);

impl UserId {
    fn new(id: u64) -> Self {
        UserId(id)
    }

    fn value(&self) -> u64 {
        self.0
    }
}

// Now this won't compile:
fn get_user(id: UserId) -> User {
    // ...
}

fn main() {
    let user_id = UserId::new(42);
    let product_id = ProductId(99);

    get_user(user_id);  // OK
    // get_user(product_id);  // ERROR: type mismatch!
}

Implementing External Traits

The orphan rule prevents implementing external traits on external types. Newtypes solve this:

use std::fmt;

// Can't do: impl fmt::Display for Vec<i32> (both external)

// Solution: wrap in newtype
struct PrettyVec(Vec<i32>);

impl fmt::Display for PrettyVec {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "[")?;
        for (i, item) in self.0.iter().enumerate() {
            if i > 0 {
                write!(f, ", ")?;
            }
            write!(f, "{}", item)?;
        }
        write!(f, "]")
    }
}

fn main() {
    let v = PrettyVec(vec![1, 2, 3, 4, 5]);
    println!("{}", v); // [1, 2, 3, 4, 5]
}

Smart Newtype with Deref

use std::ops::Deref;

struct Meters(f64);

impl Deref for Meters {
    type Target = f64;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl Meters {
    fn new(value: f64) -> Self {
        Meters(value)
    }

    fn to_feet(&self) -> f64 {
        self.0 * 3.28084
    }
}

fn main() {
    let distance = Meters::new(100.0);

    // Deref coercion allows using as f64
    let doubled = *distance * 2.0;

    // But also has custom methods
    println!("{} feet", distance.to_feet());
}

2.4 Phantom Types

Phantom types are type parameters that don't actually store data but encode information at compile time:

Type-State Pattern

use std::marker::PhantomData;

// States
struct Locked;
struct Unlocked;

struct Door<State> {
    _state: PhantomData<State>,
}

impl Door<Locked> {
    fn new() -> Self {
        Door {
            _state: PhantomData,
        }
    }

    fn unlock(self, key: &str) -> Option<Door<Unlocked>> {
        if key == "correct_key" {
            Some(Door {
                _state: PhantomData,
            })
        } else {
            None
        }
    }
}

impl Door<Unlocked> {
    fn open(self) {
        println!("Door opened!");
    }

    fn lock(self) -> Door<Locked> {
        Door {
            _state: PhantomData,
        }
    }
}

fn main() {
    let door = Door::<Locked>::new();

    // Can't open locked door - won't compile!
    // door.open();

    if let Some(unlocked) = door.unlock("correct_key") {
        unlocked.open();  // This compiles!
    }
}

Builder Pattern with Type States

struct RequestBuilder<State> {
    url: Option<String>,
    method: Option<String>,
    _state: PhantomData<State>,
}

struct NoUrl;
struct HasUrl;

impl RequestBuilder<NoUrl> {
    fn new() -> Self {
        RequestBuilder {
            url: None,
            method: None,
            _state: PhantomData,
        }
    }

    fn url(self, url: String) -> RequestBuilder<HasUrl> {
        RequestBuilder {
            url: Some(url),
            method: self.method,
            _state: PhantomData,
        }
    }
}

impl RequestBuilder<HasUrl> {
    fn method(mut self, method: String) -> Self {
        self.method = Some(method);
        self
    }

    // Can only build when URL is set!
    fn build(self) -> Request {
        Request {
            url: self.url.unwrap(),
            method: self.method.unwrap_or_else(|| "GET".to_string()),
        }
    }
}

// Won't compile without URL:
// let req = RequestBuilder::new().build();

2.5 Advanced Generics

Const Generics

Const generics allow you to parameterize types over constant values:

// Array with compile-time size checking
struct FixedBuffer<T, const N: usize> {
    data: [T; N],
}

impl<T: Default + Copy, const N: usize> FixedBuffer<T, N> {
    fn new() -> Self {
        FixedBuffer {
            data: [T::default(); N],
        }
    }

    fn len(&self) -> usize {
        N
    }
}

fn main() {
    let buffer = FixedBuffer::<i32, 10>::new();
    println!("Buffer size: {}", buffer.len());
}

// Matrix multiplication with compile-time dimension checking
struct Matrix<T, const ROWS: usize, const COLS: usize> {
    data: [[T; COLS]; ROWS],
}

impl<T: Default + Copy, const ROWS: usize, const COLS: usize> Matrix<T, ROWS, COLS> {
    fn new() -> Self {
        Matrix {
            data: [[T::default(); COLS]; ROWS],
        }
    }
}

// Multiply only works when dimensions match!
impl<T, const M: usize, const N: usize, const P: usize> Matrix<T, M, N>
where
    T: Copy + Default + std::ops::Add<Output = T> + std::ops::Mul<Output = T>,
{
    fn multiply(&self, other: &Matrix<T, N, P>) -> Matrix<T, M, P> {
        // Implementation
        Matrix::new()
    }
}

Generic Associated Types (GATs)

// Enable powerful patterns like lending iterators
trait LendingIterator {
    type Item<'a> where Self: 'a;

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

// Example: iterator that lends out mutable references
struct WindowsMut<'data, T> {
    data: &'data mut [T],
    window_size: usize,
    position: usize,
}

impl<'data, T> LendingIterator for WindowsMut<'data, T> {
    type Item<'a> = &'a mut [T] where Self: 'a;

    fn next(&mut self) -> Option<Self::Item<'_>> {
        if self.position + self.window_size > self.data.len() {
            return None;
        }

        let start = self.position;
        let end = start + self.window_size;
        self.position += 1;

        // SAFETY: We're careful to not overlap windows
        unsafe {
            let ptr = self.data.as_mut_ptr();
            Some(std::slice::from_raw_parts_mut(
                ptr.add(start),
                self.window_size,
            ))
        }
    }
}

2.6 Type-Level Programming

Encoding Logic in Types

// Peano numbers at type level
struct Zero;
struct Succ<N>(PhantomData<N>);

type One = Succ<Zero>;
type Two = Succ<One>;
type Three = Succ<Two>;

// Type-level addition
trait Add<Rhs> {
    type Output;
}

impl<N> Add<Zero> for N {
    type Output = N;
}

impl<N, M> Add<Succ<M>> for N
where
    N: Add<M>,
{
    type Output = Succ<<N as Add<M>>::Output>;
}

// Compile-time computation!
type Five = <Two as Add<Three>>::Output;

2.7 Chapter Summary