29 — Advanced Type System (Variance, HRTBs, Subtyping)

// &'a T is COVARIANT in T: a longer-lived, read-only borrow can substitute
fn takes_short<'a>(s: &'a str) { println!("{s}"); }
fn covariance_ok() {
    let s: &'static str = "hi";
    takes_short(s); // &'static str used where &'a str expected — fine, read-only
}

// &'a mut T is INVARIANT in T — this hypothetical is what invariance forbids
fn if_covariance_allowed_this_would_compile() {
    let mut s = String::from("hi");
    // let r: &mut &'static str = &mut s;      // NOT real code — illustrative only
    // let short = String::from("bye");
    // *r = &short;                            // would write a short-lived &str
    //                                          // into a slot typed &'static str
    // println!("{}", s);                      // s would now dangle
}

// Real compiler output for the invariant case:
fn assign<'a>(dest: &mut &'a str, src: &'a str) { *dest = src; }
fn real_rejection() {
    let mut r: &str = "long lived";
    {
        let short = String::from("short");
        // assign(&mut r, &short); // ERROR: `short` does not live long enough
    }
    println!("{r}");
}

use std::cell::Cell;

struct Mixed<'a, 'b, A: 'a, B: 'b, C, D, E, H, In, Out, Arg> {
    a: &'a A,          // covariant over 'a and A
    b: &'b mut B,      // covariant over 'b, invariant over B
    c: Cell<C>,        // invariant over C (interior mutability)
    d: Vec<D>,         // covariant over D
    h1: H,             // would be covariant over H except...
    h2: Cell<H>,       // ...invariant over H — invariance wins the conflict
    f: fn(In) -> Out,  // contravariant over In, covariant over Out
    g: &'a Arg,        // covariant over Arg
}
// Rule: all-uses-covariant => covariant; all-uses-contravariant => contravariant;
// ANY invariant use => invariant. Invariance is the safe default on conflict.

use std::cell::RefCell;

thread_local! {
    static STATIC_VECS: RefCell<Vec<&'static str>> = RefCell::new(Vec::new());
}

// Stores its input in a thread-local Vec<&'static str> — REQUIRES 'static input
fn store(input: &'static str) {
    STATIC_VECS.with_borrow_mut(|v| v.push(input));
}

// Calls f with input of lifetime 'a — f must handle EXACTLY 'a
fn demo<'a>(input: &'a str, f: fn(&'a str)) {
    f(input);
}

fn contravariance_direction() {
    demo("hello", store); // OK: 'static <: 'a, so store (needing 'static)
                          // is usable where fn(&'a str) is expected? NO —
                          // this compiles only because "hello" IS 'static.
    let smuggle = String::from("smuggle");
    // demo(&smuggle, store); // ERROR: fn(&'static str) is NOT a subtype of
                              // fn(&'a str) — contravariance is the other way.
                              // store would push a non-'static ref into a
                              // 'static slot => use-after-free later.
}

fn identity<T>(x: T) -> T { x }

fn call_sites() {
    identity(1i32);        // compiles a separate identity::<i32>
    identity("hi");         // compiles a separate identity::<&str>
    identity(String::new()); // and a separate identity::<String>
    // -> three distinct, non-generic functions in the binary after codegen
}

// Code-bloat in practice: N call-site types => N copies of the body
trait Encode { fn encode(&self) -> Vec<u8>; }
fn encode_all<T: Encode>(items: &[T]) -> Vec<Vec<u8>> {
    items.iter().map(Encode::encode).collect()
}
// encode_all::<Header>, encode_all::<Frame>, encode_all::<Ack>, ... each
// fully duplicated in the binary, each independently inlinable.

trait Shape { fn area(&self) -> f64; }

struct Circle { r: f64 }
impl Shape for Circle { fn area(&self) -> f64 { std::f64::consts::PI * self.r * self.r } }

struct Square { side: f64 }
impl Shape for Square { fn area(&self) -> f64 { self.side * self.side } }

// Generic: monomorphized, zero-cost dispatch, one compiled copy PER type used
fn print_area_generic<S: Shape>(s: &S) { println!("{}", s.area()); }

// dyn: one shared compiled copy, vtable dispatch, heterogeneous types allowed
fn print_area_dyn(s: &dyn Shape) { println!("{}", s.area()); }

fn heterogeneous_collection() {
    let shapes: Vec<Box<dyn Shape>> = vec![
        Box::new(Circle { r: 1.0 }),
        Box::new(Square { side: 2.0 }), // impossible with a single generic Vec<S>
    ];
    for s in &shapes { print_area_dyn(s.as_ref()); }
}

// Fat pointer size proof
fn size_check() {
    assert_eq!(std::mem::size_of::<&dyn Shape>(), 2 * std::mem::size_of::<usize>());
    assert_eq!(std::mem::size_of::<&Circle>(), std::mem::size_of::<usize>());
}

// Dispatchable receivers — all valid on dyn Trait
trait Receivers {
    fn by_ref(self: &Self) {}
    fn by_ref_mut(self: &mut Self) {}
    fn by_box(self: Box<Self>) {}
    fn by_rc(self: Rc<Self>) {}
    fn by_arc(self: Arc<Self>) {}
    fn by_pin(self: Pin<&Self>) {}
    fn with_lifetime<'a>(self: &'a Self) {} // lifetime params OK
}

// Why each rule exists — the mechanism behind the veto
trait WhyRules {
    // fn returns(&self) -> Self; // Self: concrete type unknown until runtime — vtable can't size it
    // fn param(&self, other: Self); // `other` could be a DIFFERENT impl of the trait
    // fn typed<T>(&self, x: T);     // one vtable entry per T is impossible — T is infinite
    // async fn run(&self);          // returns an anonymous future type — same problem as -> Self
    // fn opaque(&self) -> impl Debug; // hidden type, unknowable at the call site
    // const K: usize;               // consts are resolved statically, no vtable story
    // type Out;                     // needed by the caller to even NAME the type
}

pub trait Logger {
    fn log(&self, msg: &str); // dispatchable — this is the vtable surface

    // exempted: callable on concrete types, invisible to dyn users
    fn with_prefix(prefix: &'static str) -> Self where Self: Sized;
    fn compare(&self, other: &Self) -> bool where Self: Sized { false }
}

struct FileLogger { prefix: &'static str }
impl Logger for FileLogger {
    fn log(&self, msg: &str) { println!("{}: {msg}", self.prefix); }
    fn with_prefix(prefix: &'static str) -> Self { FileLogger { prefix } }
}

fn sized_hatch() {
    let l: Box<dyn Logger> = Box::new(FileLogger { prefix: "app" });
    l.log("dyn path works"); // OK
    // l.compare(l.as_ref()); // ERROR: non-dispatchable method on dyn Logger
    let c = FileLogger::with_prefix("static path"); // OK on the concrete type
    c.log("concrete path works");
}

// Auto-inferred HRTB: closure ties nothing external to the input's lifetime
fn apply_to_str<F>(f: F) where F: for<'a> Fn(&'a str) -> usize {
    let owned = String::from("hello");
    println!("{}", f(&owned)); // f must work for THIS call's fresh lifetime
    println!("{}", f("literal")); // and for this one too, a different lifetime
}
fn use_it() { apply_to_str(|s: &str| s.len()); }

struct Closure<F> {
    data: (u8, u16),
    func: F,
}

impl<F> Closure<F>
where
    // F must handle ANY lifetime the caller's &self borrow happens to have —
    // that lifetime is unnameable here; only `for<'a>` can express it
    F: for<'a> Fn(&'a (u8, u16)) -> &'a u8,
{
    fn call(&self) -> u8 {
        *(self.func)(&self.data)
    }
}

fn first(data: &(u8, u16)) -> &u8 { &data.0 }

fn hrtb_stored_closure() {
    let clo = Closure { data: (0, 1), func: first };
    let out = clo.call(); // &'a data borrow ends inside call() — HRTB made it sound
    println!("{out}");
}

// WRONG attempt: pinning the lifetime to a generic parameter doesn't work —
// the caller of apply_to_str_broken can't know 'a in advance
fn apply_to_str_broken<'a, F: Fn(&'a str) -> usize>(f: F, s: &'a str) -> usize {
    f(s) // works, but only for ONE fixed 'a chosen by the caller, not "any 'a"
}

trait LendingIterator {
    type Item<'a> where Self: 'a;
    fn next(&mut self) -> Option<Self::Item<'_>>;
}

struct WindowsMut<'buf> { buf: &'buf mut [u8], pos: usize }

impl<'buf> LendingIterator for WindowsMut<'buf> {
    type Item<'a> = &'a mut [u8] where Self: 'a;
    fn next(&mut self) -> Option<Self::Item<'_>> {
        if self.pos + 2 > self.buf.len() { return None; }
        let slice = &mut self.buf[self.pos..self.pos + 2];
        self.pos += 1;
        Some(slice) // borrows FROM self, per-call — impossible with a fixed `Item`
    }
}

// Ecosystem friction: this does NOT work — `for` desugars to std::iter::Iterator,
// whose Item is not generic over a lifetime
fn cannot_for_loop(mut it: WindowsMut) {
    // for w in it { ... } // ERROR: WindowsMut is not `std::iter::Iterator`
    while let Some(w) = it.next() {
        w[0] = 0; // must drive it manually instead
    }
}

struct Arr<const N: usize> { data: [u8; N] } // const generic parameter in struct definition

fn needs_32(a: Arr<32>) { /* ... */ }

fn const_generic_mismatch() {
    let a16 = Arr::<16> { data: [0; 16] };
    // needs_32(a16); // ERROR: expected `Arr<32>`, found `Arr<16>` — compile-time, not a bounds check
}

struct Foo<const N: usize>([i32; N]);

impl<const N: usize> Foo<N> {
    const CONST: usize = N * 4; // associated const
}

trait Maker { type Output; }
impl<const N: usize> Maker for Foo<N> {
    type Output = [i32; N]; // associated type
}

fn sizes<const N: usize>(arr: [i32; N]) {
    let x: [i32; N] = [0; N]; // body type + array repeat count
    println!("{}", N * 2);   // runtime expression
}

fn bad<const N: usize>() -> [u8; { N + 1 }] { // ERROR: cannot combine N with
    [1; N + 1]                                 // expressions in these positions
}

fn good<const N: usize>() -> [u8; N] { // OK: standalone N
    [0; N]
}

type N = u32; // shadow-conflict: a type alias also named N

struct Foo<const N: usize>;

fn foo<const N: usize>() -> Foo<N> { todo!() } // ERROR: N parsed as the TYPE alias N (= u32)
fn bar<const N: usize>() -> Foo<{ N }> { todo!() } // OK: braces force const-arg reading

struct Flag<const B: bool>;
trait Bar {}
impl Bar for Flag<true> {}
impl Bar for Flag<false> {} // both bool values implemented — "exhaustive"

fn generic<const B: bool>() {
    let v = Flag::<B>;
    // needs_bar(v); // ERROR: trait bound `Flag<B>: Bar` not satisfied —
                     // the compiler does NOT consider "all possible B" here
}
fn needs_bar(_: impl Bar) {}

// Generics: N instantiations = N copies, each inlinable, all zero-dispatch-cost
fn sum_generic<T: std::ops::Add<Output = T> + Copy>(a: T, b: T) -> T { a + b }
fn call_many_types() {
    sum_generic(1i32, 2);       // copy #1
    sum_generic(1.0f64, 2.0);   // copy #2
    sum_generic(1u8, 2);        // copy #3 — binary grows with each new T
}

// dyn: one copy, vtable call, no cross-call inlining — measure, don't assume
trait Adder { fn add(&self, a: i32, b: i32) -> i32; }
struct Plain;
impl Adder for Plain { fn add(&self, a: i32, b: i32) -> i32 { a + b } }

fn hot_loop(adder: &dyn Adder) -> i32 {
    let mut acc = 0;
    for i in 0..1_000_000 {
        acc = adder.add(acc, i); // indirect call every iteration, not inlined
    }
    acc
}

// Generic parameter: multiple impls per type, but every signature pays for it
trait ConvertFrom<T> { fn convert(t: T) -> Self; }
impl ConvertFrom<u8> for String { fn convert(t: u8) -> Self { t.to_string() } }
impl ConvertFrom<&str> for String { fn convert(t: &str) -> Self { t.to_string() } }

fn needs_generic_param<T, S: ConvertFrom<T>>(t: T) -> S { S::convert(t) } // extra param everywhere

// Associated type: clean call sites, but exactly ONE impl per concrete type
trait Parser { type Output; fn parse(&self, s: &str) -> Self::Output; }
struct IntParser;
impl Parser for IntParser { type Output = i32; fn parse(&self, s: &str) -> i32 { s.parse().unwrap() } }
// impl Parser for IntParser { type Output = f64; ... } // ERROR: conflicting impl

// PhantomData is zero-sized — verify, don't assume
struct Tagged<T> { id: u64, _marker: std::marker::PhantomData<T> }
fn phantom_is_free() {
    assert_eq!(std::mem::size_of::<Tagged<String>>(), std::mem::size_of::<u64>());
}

// Existing, object-safe trait, used widely as Box<dyn Service> in production
pub trait Service {
    fn call(&self, req: Request) -> Response;
}

// A "harmless" addition during a refactor — WRONG, breaks object safety
pub trait Service {
    fn call(&self, req: Request) -> Response;
    fn call_typed<T: FromRequest>(&self, req: Request) -> T; // compiles here...
}

fn breaks_far_away(svc: &dyn Service) {
    // ERROR surfaces HERE, in a different crate maybe:
    // "the trait `Service` cannot be made into an object"
}

// RIGHT — keep the object-safe trait untouched; add the generic method via
// an extension trait excluded from object safety with `where Self: Sized`
pub trait Service {
    fn call(&self, req: Request) -> Response;
}

pub trait ServiceExt: Service {
    fn call_typed<T: FromRequest>(&self, req: Request) -> T where Self: Sized {
        T::from_request(self.call(req))
    }
}
impl<S: Service + ?Sized> ServiceExt for S {}

fn still_works(svc: &dyn Service) {
    let _ = svc.call(Request::default()); // dyn callers never see call_typed
}

// WRONG (maybe) — introduced for "future flexibility," never profiled
pub struct Pipeline { stages: Vec<Box<dyn Fn(&mut Buffer)>> }

impl Pipeline {
    pub fn run(&self, buf: &mut Buffer) {
        for stage in &self.stages {
            stage(buf); // vtable call, non-inlinable, per stage, per buffer
        }
    }
}

// RIGHT, if stages are fixed at compile time — generic over concrete types,
// fully inlinable, no vtable
pub struct Pipeline<A, B> { stages: (A, B) }

impl<A: Fn(&mut Buffer), B: Fn(&mut Buffer)> Pipeline<A, B> {
    pub fn run(&self, buf: &mut Buffer) {
        (self.stages.0)(buf);
        (self.stages.1)(buf); // both statically known, inlinable
    }
}

// RIGHT, if heterogeneity IS a genuine runtime requirement (plugins, config-driven)
pub struct PluginPipeline { stages: Vec<Box<dyn Fn(&mut Buffer)>> }
// same shape as the "wrong" version above — the difference is a measured
// decision (stages vary at runtime), not a default reached for by habit

// WRONG — Generator doesn't own a T, it produces one on demand; PhantomData<T>
// falsely claims ownership: covariance and Send/Sync inferred as if T were stored
pub struct Generator<T> {
    state: *mut u8,
    _marker: std::marker::PhantomData<T>,
}

// RIGHT — PhantomData<fn() -> T> models "produces T": covariant in T,
// without claiming ownership; !Send/!Sync opt-out appropriate for raw state
pub struct Generator<T> {
    state: *mut u8,
    _marker: std::marker::PhantomData<fn() -> T>,
}

// The hole this closes: covariance you didn't intend to grant
fn generator_variance_bug(long: Generator<&'static str>) {
    fn wants_short<'a>(_g: Generator<&'a str>) {}
    // With PhantomData<T> (covariant, correct here since &'static str : &'a str
    // is fine for READ-ONLY data) this is sound; the danger is the OPPOSITE
    // case — a type that mutates through T where covariance would be unsound.
    wants_short(long);
}

use std::marker::PhantomData;

// Reading the table as design decisions:
pub struct BorrowedIter<'a, T> {
    ptr: *const T,          // raw for FFI/unsafe — *const alone is !Send/!Sync
    end: *const T,
    _marker: PhantomData<&'a T>, // claims: "holds &'a T" — covariant, Sync-if-T,
}                                // dropck knows we don't own Ts

pub struct OwnedBuf<T> {
    data: *mut T,
    len: usize,
    _owns: PhantomData<T>,   // claims: "owns Ts" — Vec's old pattern; dropck now
}                            // requires T outlives any owned buffer's drop

pub struct Factory<T> {
    _make: PhantomData<fn() -> T>, // claims: "produces T" — covariant, always
}                                   // Send + Sync, never owns

// ERROR: parameter `'a` is never used — the compiler refuses unbounded lifetimes
// struct BadIter<'a, T> { ptr: *const T, end: *const T }

// The real std::slice::Iter is approximately this — PhantomData bounds 'a
struct Iter<'a, T> {
    ptr: *const T,
    end: *const T,
    _marker: PhantomData<&'a T>, // 'a now bounded; covariant over 'a and T
}

// Default: generics for library-internal, perf-sensitive, few-concrete-types code
pub fn checksum<T: AsRef<[u8]>>(data: T) -> u32 { crc32(data.as_ref()) }

// Boundary: dyn Trait for plugin systems / runtime-assembled heterogeneity
pub trait Middleware { fn handle(&self, req: &mut Request); }
pub struct App { middlewares: Vec<Box<dyn Middleware>> } // set from config at startup

// Sealed trait: close a public trait to external impls
mod sealed { pub trait Sealed {} }

pub trait InternalOnly: sealed::Sealed {
    fn do_thing(&self);
}
pub struct Known;
impl sealed::Sealed for Known {}
impl InternalOnly for Known { fn do_thing(&self) { /* ... */ } }
// external crates can implement InternalOnly's methods but never the trait
// itself, because they cannot implement the private `sealed::Sealed`

// Typestate: invalid call sequences become compile errors
pub struct Disconnected;
pub struct Connected;

pub struct Conn<State> { socket: Option<std::net::TcpStream>, _state: std::marker::PhantomData<State> }

impl Conn<Disconnected> {
    pub fn connect(self, addr: &str) -> std::io::Result<Conn<Connected>> {
        let socket = std::net::TcpStream::connect(addr)?;
        Ok(Conn { socket: Some(socket), _state: std::marker::PhantomData })
    }
}
impl Conn<Connected> {
    pub fn send(&mut self, _bytes: &[u8]) { /* ... */ } // only callable once connected
}

fn typestate_use() -> std::io::Result<()> {
    let conn = Conn::<Disconnected> { socket: None, _state: std::marker::PhantomData };
    // conn.send(&[1]); // ERROR: no method `send` on Conn<Disconnected>
    let mut conn = conn.connect("127.0.0.1:0")?;
    conn.send(&[1]); // fine — type proves connection happened
    Ok(())
}

fn diagnostic_swap<'a>(_dest: &'a str, _src: &'a str) {} // if THIS compiles but
                                                           // &mut &'a str didn't, it's invariance

struct Lazy<T> { thunk: Box<dyn Fn() -> T>, _marker: std::marker::PhantomData<fn() -> T> }

#[inline(never)] fn via_dyn(f: &dyn Fn(i32) -> i32, x: i32) -> i32 { f(x) }
fn via_generic<F: Fn(i32) -> i32>(f: F, x: i32) -> i32 { f(x) } // often fully inlined away

type Handlers = std::rc::Rc<std::cell::RefCell<std::collections::HashMap<String, Vec<Box<dyn Fn()>>>>>;

fn covariant_ok<'a>(x: &'a str) {}      // fine with &'static str
fn invariant_fails<'a>(x: &'a mut &'a str) {} // same substitution fails through &mut

struct MostlySend { a: i32, b: std::rc::Rc<i32> } // Rc makes the WHOLE struct !Send
fn spawn_it(v: MostlySend) {
    // std::thread::spawn(move || { let _ = v; }); // ERROR points at spawn, not at field `b`
}

fn owned_default(x: Box<dyn std::fmt::Display>) {}       // == Box<dyn Display + 'static>
fn borrowed_default<'a>(x: &'a dyn std::fmt::Display) {} // trait object lifetime == 'a, NOT 'static

// for item in lending_iter {} // ERROR — LendingIterator isn't std::iter::Iterator

struct Arr<const N: usize>; // zero-sized const generic type — N is a value, not a type
fn const_expr_mismatch() {
    let a: Arr<5> = Arr;
    // let b: Arr<{ 2 + 3 }> = a; // may fail to unify even though 2+3 == 5
}

fn assign_shorter<'a>(dest: &mut &'a str, src: &'a str) {
    *dest = src;
}

fn main() {
    let long_lived = String::from("long lived");
    let mut r: &str = &long_lived;

    {
        let short_lived = String::from("short lived");
        assign_shorter(&mut r, &short_lived);
    }

    println!("{r}");
}

// Variance: &T covariant, &mut T invariant — invariance is load-bearing soundness
fn covariant<'a>(_: &'a str) {}
fn invariant_marker<'a>(_: &'a mut &'a str) {}

// Generics: N copies, zero dispatch cost, inlinable, larger binary
fn mono<T: Clone>(x: T) -> T { x.clone() }

// dyn: 1 copy, vtable dispatch, no cross-call inlining, smaller binary
fn dynamic(x: &dyn std::fmt::Debug) { println!("{x:?}"); }

// HRTB: universal quantification over lifetimes chosen per-call
fn hrtb<F: for<'a> Fn(&'a str) -> usize>(f: F) -> usize { f("x") }

// GAT: associated type borrowing from &self — real expressiveness gain,
// real ecosystem-composability cost (no `for` loop sugar, see above)
trait Lend { type Item<'a> where Self: 'a; }