Iterator trait simply cannot express;LendingIterator trait whose items borrow from the iterator itself;Learn Rust Series):At the end of last episode I promised we would keep walking through a certain door -- the one where the type checker starts doing work you might not have believed a type checker could do. Today we step through it. Generic associated types, GATs for short, are one of the more advanced corners of Rust's type system, stabilised only in Rust 1.65 (October 2022) after roughly six years of design work. That is an unusually long gestation, and it tells you something: this feature touches the deep machinery of how traits, associated types and lifetimes fit together.
Here is the whole idea in one sentence, and then we unpack it slowly. An ordinary associated type is a single fixed type per impl -- Iterator has type Item, and once you pick it, it is settled. A generic associated type lets that associated type take its own parameters, and the parameter you will reach for almost every time is a lifetime. Instead of type Item, you write type Item<'a>. That one small generalisation unlocks a pattern the standard Iterator trait has never been able to express: an iterator whose items borrow from the iterator itself, for just the duration of a single call. We call that a lending iterator, and building one is the concrete goal that will make the abstract syntax click.
Having said that, let me clear last episode's homework first, as always -- and then we go from the syntax, to the easy case, to the genuinely useful one ;-)
Episode 26 was const generics -- parameterizing a type or function by a compile-time value. Three exercises, and here is each with full, runnable code.
Exercise 1 asked for fn last<T: Copy, const N: usize>(arr: [T; N]) -> T returning the last element, called on arrays of two different lengths:
fn last<T: Copy, const N: usize>(arr: [T; N]) -> T {
arr[N - 1]
}
fn main() {
println!("{}", last([1, 2, 3])); // N = 3 -> 3
println!("{}", last(['a', 'b', 'c', 'd'])); // N = 4 -> d
}
The index N - 1 is a perfectly ordinary runtime expression, and because N is inferred at each call site, one function body serves both the length-3 and the length-4 array. The sharp edge I flagged last time is real: for N = 0 there is no last element, and arr[N - 1] would try to compute 0 - 1 on a usize and panic. The type system does not (yet) let us demand "N must be at least 1" as a bound, so that guarantee lives in your head, not in the signature.
Exercise 2 wanted a non-panicking fn get(&self, i: usize) -> Option<u8> added to the Buffer<N> struct:
#[derive(Debug)]
struct Buffer<const N: usize> {
data: [u8; N],
}
impl<const N: usize> Buffer<N> {
fn new() -> Buffer<N> { Buffer { data: [0; N] } }
fn get(&self, i: usize) -> Option<u8> {
self.data.get(i).copied()
}
}
fn main() {
let mut b = Buffer::<3>::new();
b.data[1] = 42;
println!("{:?}", b.get(1)); // Some(42)
println!("{:?}", b.get(9)); // None
}
The trick is to lean on the slice method get, which already returns an Option instead of panicking on an out-of-range index. It hands back Option<&u8>, so .copied() turns that into the Option<u8> we want by copying the u8 out (cheap, it is one byte). No bounds check written by hand, no panic path -- the standard library did the careful part for us.
Exercise 3 was the chewy one: give Matrix<R, C> a method fn transpose(&self) -> Matrix<C, R> that swaps rows and columns, and call it on a Matrix<2, 3> to get a Matrix<3, 2>:
struct Matrix<const R: usize, const C: usize> {
cells: [[f64; C]; R],
}
impl<const R: usize, const C: usize> Matrix<R, C> {
fn transpose(&self) -> Matrix<C, R> {
let mut out = [[0.0; R]; C];
for r in 0..R {
for c in 0..C {
out[c][r] = self.cells[r][c];
}
}
Matrix { cells: out }
}
}
fn main() {
let m = Matrix::<2, 3> { cells: [[1.0, 2.0, 3.0], [4.0, 5.0, 6.0]] };
let t = m.transpose(); // Matrix<3, 2>
println!("{:?}", t.cells); // [[1.0, 4.0], [2.0, 5.0], [3.0, 6.0]]
}
Look at the return type: Matrix<C, R>. The shape change is stated in the type signature itself, and the body has to honour it -- out is a [[f64; R]; C], the transposed layout, and the compiler checks that the returned array matches. If you accidentally built out with the original dimensions, the code would not compile. The dimensions are doing the bookkeeping for you, exactly the point of const generics. Right, homework cleared -- now for associated types that carry a lifetime ;-)
Cast your mind back to episode 11, where we met the Iterator trait. Its shape is roughly this:
trait Iterator {
type Item;
fn next(&mut self) -> Option<Self::Item>;
}
Item is a plain associated type. Once an impl picks it, it is one fixed type, and -- crucially -- it cannot mention the lifetime of the &mut self borrow inside next, because that lifetime does not exist at the point where type Item = ... is written. So an Iterator can yield owned values (an i32, a String), and it can yield references into some longer-lived store (a &'s str borrowing from data the iterator merely points at). What it can not do is yield a reference that borrows from the iterator itself for just this one call, is then invalidated, and whose space is reused on the next call.
Why would you ever want that? Performance and expressiveness, mostly. Imagine an iterator that owns a scratch buffer, fills it with the next chunk of a decoded stream, and hands you a &[u8] view into that buffer -- then overwrites it next time round. Zero allocations per item, the same memory reused forever. That is a genuinely useful pattern (parsers, decoders, sliding-window analytics all want it), and ordinary Iterator has no vocabulary for it. The reason is subtle but worth stating plainly: Iterator lets you keep several items alive at once -- collect() into a Vec, or just call next() twice and hold both results. If the items all borrowed from one reused buffer, you would have two live references to memory that has already been overwritten. That is precisely the aliasing bug the borrow checker exists to prevent, so the trait is correct to forbid it. We need a different trait, one that promises you may only look at one item at a time.
A generic associated type solves this by letting the associated type take the lifetime as a parameter. You write type Item<'a>, and a where Self: 'a bound says the borrow cannot outlive the iterator it came from:
trait LendingIterator {
type Item<'a> where Self: 'a;
fn next(&mut self) -> Option<Self::Item<'_>>;
}
Read type Item<'a> out loud as "the item type is parameterized by a lifetime 'a". Now the return type of next can be Option<Self::Item<'_>>, where the elided '_ is exactly the lifetime of the &mut self borrow that next takes. So the item is allowed to borrow from self, and its borrow is tied to the length of that single next call -- no longer, which is what makes reuse safe. That single generalisation, type Item becoming type Item<'a>, is the whole feature. Everything else in this episode is just consequences of it.
One vocabulary note so the where Self: 'a does not spook you: it means "for the item to borrow for 'a, the iterator must itself be valid for at least 'a". You cannot lend out a reference that lives longer than the thing you borrowed it from. That is the same common-sense rule from the lifetimes episode, written down where the compiler can enforce it.
An impl fixes a GAT the same way it fixes an ordinary associated type. The gentlest possible start is a case where the item is owned and does not actually borrow at all -- the lifetime is simply ignored. It looks slightly odd (why carry a lifetime you do not use?), but it lets us see the syntax work with nothing else going on:
trait LendingIterator {
type Item<'a> where Self: 'a;
fn next(&mut self) -> Option<Self::Item<'_>>;
}
struct Counter { n: u32, max: u32 }
impl LendingIterator for Counter {
type Item<'a> = u32 where Self: 'a; // owned item, lifetime unused
fn next(&mut self) -> Option<u32> {
if self.n < self.max {
self.n += 1;
Some(self.n)
} else {
None
}
}
}
fn main() {
let mut c = Counter { n: 0, max: 3 };
while let Some(x) = c.next() {
println!("{x}"); // 1, 2, 3
}
}
Notice how we drive it: a while let Some(x) = c.next() loop, not a for loop. This matters and it is easy to trip over. The for loop in Rust desugars to calls on the standard IntoIterator/Iterator traits, which our LendingIterator is not. There is no built-in sugar for lending iterators, so you call next by hand. A small price, and honestly it keeps the "one item at a time" discipline visible in the code.
Here is the payoff -- an iterator whose items borrow from data it holds. The classic teaching example is overlapping windows into a slice: given [1, 2, 3, 4] and a window size of 2, hand out [1, 2], then [2, 3], then [3, 4]:
trait LendingIterator {
type Item<'a> where Self: 'a;
fn next(&mut self) -> Option<Self::Item<'_>>;
}
struct Windows<'s> { data: &'s [i32], size: usize, pos: usize }
impl<'s> LendingIterator for Windows<'s> {
type Item<'a> = &'a [i32] where Self: 'a;
fn next(&mut self) -> Option<&[i32]> {
if self.pos + self.size <= self.data.len() {
let window = &self.data[self.pos..self.pos + self.size];
self.pos += 1;
Some(window)
} else {
None
}
}
}
fn main() {
let numbers = [1, 2, 3, 4];
let mut windows = Windows { data: &numbers, size: 2, pos: 0 };
while let Some(w) = windows.next() {
println!("{w:?}"); // [1, 2], [2, 3], [3, 4]
}
}
The line that carries the whole idea is type Item<'a> = &'a [i32] where Self: 'a; -- the item is a borrowed slice whose lifetime the GAT threads through. In the next signature, Option<&[i32]> has its lifetime elided to the &mut self borrow, which is precisely Self::Item<'_>. Try to write this as a plain Iterator yielding something that borrows from self and the borrow checker stops you cold -- that gap is the exact reason GATs exist, and you will feel it yourself in exercise 3.
The Windows example lends, but it borrows from an external slice, so a sufficiently clever ordinary iterator could sometimes fake it. The case that is genuinely impossible without lending is one where the iterator owns its storage and overwrites it each call. Watch:
trait LendingIterator {
type Item<'a> where Self: 'a;
fn next(&mut self) -> Option<Self::Item<'_>>;
}
struct Rolling { store: [i32; 3], base: i32, steps: u32 }
impl LendingIterator for Rolling {
type Item<'a> = &'a [i32] where Self: 'a;
fn next(&mut self) -> Option<&[i32]> {
if self.steps == 0 { return None; }
self.steps -= 1;
for k in 0..3 {
self.store[k] = self.base + k as i32; // overwrite the shared buffer
}
self.base += 1;
Some(&self.store)
}
}
fn main() {
let mut r = Rolling { store: [0; 3], base: 0, steps: 3 };
while let Some(view) = r.next() {
println!("{view:?}"); // [0, 1, 2], [1, 2, 3], [2, 3, 4]
}
}
Every call rewrites self.store in place and lends you a view of it. There is exactly one buffer, reused three times -- no allocation per item. This is the pattern you can not express with Iterator, and now you can see why in mechanical terms: if next returned an Iterator-style item, you could stash the first view, call next again, and hold a reference to a buffer that the second call already clobbered. The LendingIterator signature forbids that, because the borrow from the first next must end before you are allowed to call next again. The compiler enforces "look at one, then move on" as a hard rule.
Like any trait (episode 8), LendingIterator can carry default methods built on top of next. A simple one is counting how many items it produces -- it just drives next to exhaustion:
trait LendingIterator {
type Item<'a> where Self: 'a;
fn next(&mut self) -> Option<Self::Item<'_>>;
fn count(mut self) -> usize where Self: Sized {
let mut n = 0;
while self.next().is_some() { n += 1; }
n
}
}
struct Ticks { left: u32 }
impl LendingIterator for Ticks {
type Item<'a> = () where Self: 'a;
fn next(&mut self) -> Option<()> {
if self.left > 0 { self.left -= 1; Some(()) } else { None }
}
}
fn main() {
println!("{}", Ticks { left: 5 }.count()); // 5
}
The where Self: Sized on count is the marker-trait care we learned in episode 25 -- count consumes self by value, so it needs a sized Self. Everything else is ordinary trait mechanics; the GAT does not change how defaults work, it just sits in the type Item<'a> slot doing its lifetime job.
Since quite some of you came through the Learn Python Series first (as did I), a look sideways sharpens the picture. Lending is one of those places where Rust's strictness buys you something the flexible languages give away.
Python lends buffers all the time -- and gives you zero protection when you do. A generator that yields the same reused list is legal, and the footgun is spectacular:
def rolling(base, steps):
store = [0, 0, 0]
for _ in range(steps):
for k in range(3):
store[k] = base + k
base += 1
yield store # the SAME list object, mutated in place, every time
views = list(rolling(0, 3))
print(views) # [[2, 3, 4], [2, 3, 4], [2, 3, 4]] -- all three are the same list!
Calling list(...) collects three references to one object, so they all show the final state. Nothing warns you; the bug just quietly corrupts your data. That is exactly the situation Rust's LendingIterator makes unrepresentable -- you physically cannot hold two views at once, so you can never collect them into a surprise like this.
C++ sits closer to Rust in ambition but without the safety net. C++ iterators have long allowed the "reference" type to be a proxy that points at reused internal state -- std::istream_iterator and various range adaptors lend from a buffer they own. It works, it is fast, and if you keep a reference past the next increment you get undefined behaviour with no compiler complaint. Three points on the familiar line once more: Python lends freely and checks nothing, C++ lends freely and trusts you not to dangle, and Rust lends but proves at compile time that you never hold an invalidated view. I know which trade I want when the reused buffer is decoding a network stream at 2am ;-)
You will not hand-write LendingIterator every day -- honestly, most days you will not write one at all. But GATs quietly underpin things you will use. The biggest by far is async: the machinery that lets a trait method return a future which borrows from self leans on the exact same generalisation. Async functions in traits (stabilised in Rust 1.75) desugar to an associated type that is generic over a lifetime -- a GAT in all but name. Library authors also reach for GATs to build streaming APIs, abstractions over collections that return borrowed views, and container traits where the item type depends on how you are borrowing. As a user of those crates you mostly benefit without noticing the GAT under the hood, which is rather the point of good abstractions.
The rule of thumb to carry away: if an associated type needs to borrow from self for just the duration of a method call, you need a GAT. If it does not -- if the item is owned, or borrows from somewhere with a longer, independent lifetime -- a plain associated type is simpler and entirely enough. Do not reach for the advanced tool until the ordinary one actually fails you.
type Item<'a> instead of type Item -- and the parameter is almost always a lifetime, gated by where Self: 'a.Iterator cannot express: a lending iterator whose items borrow from the iterator itself for one call only, so a reused internal buffer stays safe.Counter (lifetime ignored), a borrowing Windows over a slice, and a genuinely reusing Rolling that overwrites one buffer -- the case ordinary Iterator fundamentally cannot do.while let ... = it.next(), not for, because for desugars to the standard Iterator, not our trait. Default methods (like count) work exactly as they do on any trait.Step back and notice the pattern of the last few episodes. We keep finding ways to teach the compiler facts it can then enforce for free -- values baked into types with const generics last time, and now lifetimes woven into associated types so that borrowing stays sound even when memory is reused. Each one moves a guarantee from your head into the type checker. Next time we will use that same instinct -- encoding intent into types -- to shape the public face of a library, so that outsiders can use your traits but cannot break the invariants you depend on. One idea at a time ;-)
Three exercises as always, from gentle to chewier. Full solutions open the next episode, so genuinely have a go first -- typing it yourself is where it sticks.
for_each default method to LendingIterator that takes a closure and calls it on each item, then use it on Counter to print 1, 2, 3. (Hint: the closure parameter type will need to accept Self::Item<'_>.)LendingIterator for a struct Multiples { store: [i32; 4], factor: i32, count: u32 } that, each call, fills store with the next four multiples of factor and lends back a &[i32] view -- reusing the one buffer like Rolling does. Drive it with a while let loop.Windows as a plain Iterator whose Item borrows from self (not from the external slice), and watch the borrow checker reject it. Read the error carefully -- that rejection is the precise gap GATs were built to fill.Bedankt voor het lezen, en tot de volgende! ;-)
@scipio