Why does the compiler claim that an associated type from a higher-ranked trait bound doesn't implement `Display` even though it should?

Question

I'm building a library that implements string joins; that is, printing all the elements of a container separated by a separator. My basic design looks like this:

use std::fmt;

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Join<Container, Sep> {
    container: Container,
    sep: Sep,
}

impl<Container, Sep> fmt::Display for Join<Container, Sep>
where
    for<'a> &'a Container: IntoIterator,
    for<'a> <&'a Container as IntoIterator>::Item: fmt::Display,
    Sep: fmt::Display,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut iter = self.container.into_iter();

        match iter.next() {
            None => Ok(()),
            Some(first) => {
                first.fmt(f)?;

                iter.try_for_each(move |element| {
                    self.sep.fmt(f)?;
                    element.fmt(f)
                })
            }
        }
    }
}

This trait implementation compiles without complaint. Notice the bound on &'a C: IntoIterator. Many containers implement IntoIterator for a reference to themselves, to allow for iterating over references to the contained items (for instance, Vec implements it here).

However, when I actually try to use my Join struct, I get an unsatisfied trait bound:

fn main() {
    let data = vec!["Hello", "World"];
    let join = Join {
        container: data,
        sep: ", ",
    };
    println!("{}", join);
}

This code produces a compilation error:

error[E0277]: `<&'a std::vec::Vec<&str> as std::iter::IntoIterator>::Item` doesn't implement `std::fmt::Display`
  --> src/main.rs:38:20
   |
38 |     println!("{}", join);
   |                    ^^^^ `<&'a std::vec::Vec<&str> as std::iter::IntoIterator>::Item` cannot be formatted with the default formatter
   |
   = help: the trait `for<'a> std::fmt::Display` is not implemented for `<&'a std::vec::Vec<&str> as std::iter::IntoIterator>::Item`
   = note: in format strings you may be able to use `{:?}` (or {:#?} for pretty-print) instead
   = note: required because of the requirements on the impl of `std::fmt::Display` for `Join<std::vec::Vec<&str>, &str>`
   = note: required by `std::fmt::Display::fmt`

The key line seems to be this:

the trait `for<'a> std::fmt::Display` is not implemented for `<&'a std::vec::Vec<&str> as std::iter::IntoIterator>::Item`

Unfortunately, the compiler doesn't actually tell me what the Item type is, but based on my reading of the docs, it appears to be &T, which in this case means &&str.

Why doesn't the compiler think that &&str implements Display? I've tried this with many other types, like usize and String, and none of them work; they all fail with the same error. I know that these reference type don't directly implement Display, but the implementation should be picked up automatically through deref coercion, right?

It looks like the compiler is treating for<'a> Display as different from Display. This might be a bug in the compiler. — Francis Gagné
This indeed looks like a shortcoming in the compiler to me. You are right that the item type is &&str, as you can easily verify by trying to compile let _: <&Vec<&str> as IntoIterator>::Item = ();. And &&str definitely does implement Display, as can be verified by adding <&&str as fmt::Display>::fmt(&&"hello", f)?; to the body of fmt(). So this should definitely work. My guess is that <&'a std::vec::Vec<&str> as std::iter::IntoIterator>::Item isn't correctly normalized to &'a &str for some reason. — Sven Marnach
See also github.com/rust-lang/rust/issues/24159 and the issues linked there. Often this can be worked around by adding an additional type parameter for the item type, and forcing it to be the actual item type by changing the trait bound IntoIterator to IntoIterator<Item = T>, where T is the new type parameter. This doesn't work int his case, though, due to the HRTBs. — Sven Marnach
@Lucretiel The reason this does not work is because of the lifetime of Item. In your example, the item type is &&str, but annoted with the lifetime of the HRTB, it would have to be &'a &str for all lifetimes 'a, which of course is impossible. That's what I meant in my previous comment. — Sven Marnach

dtolnay dtolnay · Accepted Answer · 2018-11-18T21:16:52

Seems like a compiler limitation. You can work around it for now by writing the impl bound in terms of a private helper trait that represents "display with lifetime". This enables the compiler to see that for<'a> private::Display<'a> implies fmt::Display.

use std::fmt;

pub struct Join<Container, Sep> {
    container: Container,
    sep: Sep,
}

mod private {
    use std::fmt;
    pub trait Display<'a>: fmt::Display {}
    impl<'a, T> Display<'a> for T where T: fmt::Display {}
}

impl<Container, Sep> fmt::Display for Join<Container, Sep>
where
    for<'a> &'a Container: IntoIterator,
    for<'a> <&'a Container as IntoIterator>::Item: private::Display<'a>,
    Sep: fmt::Display,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut iter = self.container.into_iter();

        match iter.next() {
            None => Ok(()),
            Some(first) => {
                first.fmt(f)?;

                iter.try_for_each(move |element| {
                    self.sep.fmt(f)?;
                    element.fmt(f)
                })
            }
        }
    }
}

fn main() {
    println!(
        "{}",
        Join {
            container: vec!["Hello", "World"],
            sep: ", ",
        }
    );
}

Why does the compiler claim that an associated type from a higher-ranked trait bound doesn't implement `Display` even though it should?

1 Answers