This week I learned 29

This week I learned more about trait bounds. I was writing a bit of code in rlox to walk through the inheritance tree and figured I’d try using a trait and generics.

struct RecursiveStructure {
    name: &'static str,
    next: Option<Box<RecursiveStructure>>,
}

struct Walker<'a> {
    current: Option<&'a RecursiveStructure>,
}

impl RecursiveStructure {
    fn new(name: &'static str, next: Option<Box<RecursiveStructure>>) -> Self {
        RecursiveStructure { name, next }
    }

    fn walker(&self) -> Walker {
        Walker {
            current: Some(self),
        }
    }
}

Now a Walk trait can walk through the references.

trait Walk {
    type Item;
    fn walk(&mut self) -> Option<Self::Item>;
}

impl<'a> Walk for Walker<'a> {
    type Item = &'a RecursiveStructure;

    fn walk(&mut self) -> Option<Self::Item> {
        let current = self.current;
        if let Some(cur) = self.current {
            self.current = cur.next.as_deref();
        }

        current
    }
}

Now printing the structure is easy.

impl RecursiveStructure {
    // ...

    fn print(&self) {
        let mut walker = self.walker();
        while let Some(current) = walker.walk() {
            println!("current => {}", current.name);
        }
    }
}

fn main() {
    let head = RecursiveStructure::new(
        "foo",
        Some(Box::new(RecursiveStructure::new(
            "bar",
            Some(Box::new(RecursiveStructure::new("baz", None))),
        ))),
    );

    head.print();
}

% cargo run
   Compiling traits v0.1.0 (/Users/nick/projects/rust/traits)
    Finished dev [unoptimized + debuginfo] target(s) in 0.18s
     Running `target/debug/traits`
current => foo
current => bar
current => baz

Nice. But what if many things in the application are Walk. Can print be generic?

fn print<W>(walker: W)
where
    W: Walk,
{
    while let Some(current) = walker.walk() {
        println!("current => {}", current.name);
    }
}

fn main() {
    let head = RecursiveStructure::new(
        "foo",
        Some(Box::new(RecursiveStructure::new(
            "bar",
            Some(Box::new(RecursiveStructure::new("baz", None))),
        ))),
    );

    print(head.walker());
}

% cargo check
    Checking traits v0.1.0 (/Users/nick/projects/rust/traits)
error[E0609]: no field `name` on type `<W as Walk>::Item`
  --> src/main.rs:69:43
   |
69 |         println!("current => {}", current.name);
   |                                           ^^^^

error: aborting due to previous error

For more information about this error, try `rustc --explain E0609`.

Walk yields an Item. That item can be anything. Adding a restriction on the item fixes the error.

fn print<'a, W>(mut walker: W)
where
    W: Walk<Item = &'a RecursiveStructure>,
{
    while let Some(current) = walker.walk() {
        println!("current => {}", current.name);
    }
}

% cargo run
   Compiling traits v0.1.0 (/Users/nick/projects/rust/traits)
    Finished dev [unoptimized + debuginfo] target(s) in 0.19s
     Running `target/debug/traits`
current => foo
current => bar
current => baz

Nice. The while let Some(...) syntax is a bit verbose. Can we use a for loop instead? The Iterator docs say

Rust’s for loop syntax is actually sugar for iterators.

So Walker can iterate with a for loop if Walker is Iterator.

impl<'a> Iterator for Walker<'a> {
    type Item = &'a RecursiveStructure;

    fn next(&mut self) -> Option<Self::Item> {
        self.walk()
    }
}

fn print<'a, W>(walker: W)
where
    W: Walk + Iterator,
{
    for current in walker {
        println!("current => {}", current.name);
    }
}

% cargo run
   Compiling traits v0.1.0 (/Users/nick/projects/rust/traits)
error[E0609]: no field `name` on type `<W as std::iter::Iterator>::Item`
  --> src/main.rs:70:32
   |
70 |         println!("{}", current.name);
   |                                ^^^^

error: aborting due to previous error

Same error. The same trick works since Iterator has an associated type too.

fn print<'a, W>(walker: W)
where
    W: Walk + Iterator<Item = &'a RecursiveStructure>,
{
    for current in walker {
        println!("current => {}", current.name);
    }
}

% cargo run
   Compiling traits v0.1.0 (/Users/nick/projects/rust/traits)
    Finished dev [unoptimized + debuginfo] target(s) in 0.21s
     Running `target/debug/traits`
current => foo
current => bar
current => baz

Nice. But now print forces the structure to have a name field. Making Walker Display fixes this issue.

impl Display for RecursiveStructure {
    fn fmt(&self, f: &mut Formatter) -> Result<(), fmt::Error> {
        write!(f, "current => {}", self.name)
    }
}

impl Display for Walker<'_> {
    fn fmt(&self, f: &mut Formatter) -> Result<(), fmt::Error> {
        match self.current {
            Some(current) => write!(f, "{}", current),
            None => write!(f, "<nothing>"),
        }
    }
}

fn print<W>(walker: W)
where
    W: Walk + Iterator + Display,
    <W as Iterator>::Item: Display,
{
    for current in walker {
        println!("{}", current);
    }
}

% cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/traits`
current => foo
current => bar
current => baz

Nice.

Looking back

The Walker struct is probably unnecessary. RecursiveStructure could implement Iterator and IntoIterator directly. But, in the case of rlox, there’s little meaning in calling next on a LoxClass; it’s not obvious that calling next will yield the next class in the inheritance tree. Adding a Walk trait makes this clearer; Iterating over a LoxClassWalker will yield the classes in the inheritance tree.