HRTB bound on an associated type causes overflow, is it a compiler bug?

1 
trait Foo {
    fn foo(&self) -> &str;
}

impl Foo for &str {
    fn foo(&self) -> &str {
        self
    }
}

trait Bar {
    type Ret: ?Sized where for<'s> &'s Self::Ret: Foo;

    fn bar(&self) -> &Self::Ret;
}

impl<T> Bar for &'_ T where for<'s> &'s T: Foo {
    type Ret = T; // any implementation overflows here
    fn bar(&self) -> &Self::Ret {
        self
    }
}

impl Bar for String {
    type Ret = str; // overflow
    fn bar(&self) -> &Self::Ret {
        self
    }
}

fn s<T>(v: &T) -> &str
  where T: Bar + ?Sized,
{
    v.bar().foo()
}

fn main() {
    let _ = s("s");
}
2

I wonder what this use-case even needs the HRTB for…

trait Foo {
    fn foo(&self) -> &str;
}

impl Foo for str {
    fn foo(&self) -> &str {
        self
    }
}

trait Bar {
    type Ret: ?Sized + Foo;

    fn bar(&self) -> &Self::Ret;
}

impl<T: ?Sized> Bar for T
where
    T: Foo,
{
    type Ret = T;
    fn bar(&self) -> &Self::Ret {
        self
    }
}

impl Bar for String {
    type Ret = str;
    fn bar(&self) -> &Self::Ret {
        self
    }
}

fn s<T>(v: &T) -> &str
where
    T: Bar + ?Sized,
{
    v.bar().foo()
}

fn main() {
    let _ = s("s");
}

That being said, the compiler certainly has problems with HRTBs in many cases. Whether or not it's a "bug", I don't know. The current trait solved apparently is a complicated beast… maybe it's just the best it can do :person_shrugging: – if more curious, perhaps searching for existing issues around traits in overflow errors could help, maybe it's already reported somewhere. Probably it is technically a bug. (Realistically it's definitely a UX bug, anyway, since the error message of "overflow" isn't helpful at all; and outside of complex "we might be simulating a turing machine in the type system" situations, it should probably aim to catch patterns that would definitely overflow, and instead report on the reason, e.g. some sort of circular dependency, for why there is an issue.)

3

It's a minimized example, not a use-case.

Real case is the similar crate which has a DiffableStr trait which has methods returning &Self values. This works because it is only implemented for the unsized types str and u8. But this makes it hard to implement for other types wrapping &str or &[u8] values.

So I wanted to see if I can fix that without changing the interface too. So I changed the returned values from &Self to Self. And implemented the trait for &str and &[u8]. But then, there is another trait DiffableStrRef which needs to be adjusted too, and that's where I hit the overflows when I changed the bound on the its associated type.

4

It's a limitation certainly. I think it can't normalize <Self as Bar>::Ret while defining Self as Bar or perhaps <Self as Bar>::Ret specifically.

I suggest going with something like @steffahn's suggestion, as your current design probably doesn't work like you hope it will:

The temporary issue is because <&str as Foo>::foo takes a &&str and returns a &str with the outer lifetime -- you're trying to borrow a reference itself (the temporary returned from bar()) that goes out of scope at the end of s.

If that's not an option and you want to continue on anyway, just put the bound on the use sites like I have in the playground I suppose. The bound on &Self::Assoc isn't elaborated, so you'll have to repeat it there anyway even if you got the compiler to accept the bound on the associated type.[1]

  1. e.g. indirectly; that's a very messy playground but perhaps demonstrates what I mean ↩︎

1 Like
5

I see. What threw me off was that you used &self parameters in your minimized example, so something like

impl Foo for &str {
    fn foo(&self) -> &str {

would try to do &'a &self -> &'a str which then runs into borrow-check errors in the

v.bar().foo()

line. What would the fully refactored DiffableStr look like? (Not the whole interface, just some example method signature, e.g.slice and as_bytes.)

Edit: Ah, @quinedot just pointed out the same thing :slight_smile:

1 Like
6

We can work around this nowadays:

trait ImpliedBound<T: ?Sized>: ImpliedBoundInner<T, Is = T> {}
impl<_Self: ?Sized, T: ?Sized> ImpliedBound<T> for _Self {}
trait ImpliedBoundInner<T: ?Sized> {
    type Is: ?Sized;
}
impl<_Self: ?Sized, T: ?Sized> ImpliedBoundInner<T> for _Self {
    type Is = T;
}

trait Boring {}

trait Usage
where
    for<'a> Self: ImpliedBound<&'a Self::Thing, Is: Boring>,
{
    type Thing;
}

fn ref_example<T: Usage>(t: T::Thing) {
    use_the_trait(&t);
}

fn use_the_trait<T: Boring>(_: T) {}

fn main() {}
1 Like
7

Ah, very clever :slightly_smiling_face:

8

@MoSal in case it wasn't clear from our chatter, your OP question can also be worked around with @steffahn's last example. But the borrow issues remain.

If that's a problem in your actual use case, you could try supplying a more complete example.

9

@quinedot @steffahn I will look into it later. Thanks.

10

Turns out you don't need an HRTB to get the overflow, it's a general "bounds allowed on associated types now" problem: https://github.com/rust-lang/rust/issues/87755

And you can move the bound to the trait level to get around it.[1] Which means where clauses on (non-generic) associated types are treated different than direct bounds on associated types (which are, notionally at least, equivalent to bounds on the trait level). :upside_down_face:

  1. Though this doesn't give you elaboration. ↩︎

1 Like
11

Yeah, I found that here :slight_smile:

1 Like
12

I knew and actually tried this already. I think it applies to trait implementers, but doesn't help with callers. You would still need to add the bounds to each caller manually anyway.

I didn't try the other suggestions here yet (implied bounds).