Receiving both owned & borrowed types, and "cannot infer type for type parameter" in Borrow

Edit: I was trying to figure out how to work with a generic type that is never mutated and be able to receive it as either borrowed or owned. To somehow implement borrowed_or_owned() below without needing to have two duplicate methods:

fn borrowed(s: &str) {
    println!("{}", s);
}
fn owned(s: String) {
    println!("{}", s);
}
fn borrowed_or_owned(???) {
    println!("{}", s);
}

It turns out the way to do this is a little bit different depending on whether your use case is a free function, trait method, or struct impl. Visit the playground for a lengthier explanation. The solution appears to be:

fn speak<T: std::fmt::Display>(ref msg: T) {
    println!("{}\nI have spoken.", msg);
}

pub trait Speak {
    fn speak(self);
}
impl<T> Speak for &T
where
    T: std::fmt::Display + ?Sized,
{
    fn speak(self) {
        println!("{}\nI have spoken.", self);
    }
}

struct Speaker<T: std::borrow::Borrow<T> + std::fmt::Display> {
    msg: T,
}
impl<T: std::borrow::Borrow<T> + std::fmt::Display> Speaker<T> {
    fn new(msg: T) -> Self {
        Speaker { msg }
    }
    fn speak(&self) {
        println!("{}\nI have spoken.", self.msg.borrow());
    }
}

While trying to figure out the above I ran into some issues with type inference on std::borrow::Borrow which are solved by @EdmundsEcho's suggestion.


Original post for posterity:

I am trying to write a trait or free function that is generic over T, &T, Box<T>, etc where T is a generic type satisfying some trait bound. I can almost do this by working with std::ops::Deref, but in the case of Deref I cannot actually take T itself as an argument (i.e. has to be &T or something else that actually dereferences to T).

I would like to achieve my goal using std::borrow::Borrow but the compiler is having trouble with generic type inference, and I am struggling to understand why. It works for concrete types T but not generic T. For example:

// Trait
pub trait Speak<T: ?Sized> {
    fn speak(self);
}
impl<B, T> Speak<T> for B
where
    B: std::borrow::Borrow<T>,
    T: std::fmt::Display + ?Sized,
{
    fn speak(self) {
        println!("Says, \"{}\"", self.borrow());
    }
}

// Free function, doesn't use trait
fn speak<B, T>(speaker: B)
where
    B: std::borrow::Borrow<T>,
    T: std::fmt::Display + ?Sized,
{
    println!("Says, \"{}\"", speaker.borrow());
}

fn main() {
    let speaker: &str = "Hello, world!";
    Speak::<&str>::speak(speaker); // OK
    speak::<_,&str>(speaker);      // OK
    speaker.speak(); // cannot infer type for type parameter `T`
    speak(speaker);  // cannot infer type for type parameter `T`
                     // note: cannot satisfy `&str: Borrow<_>`
}

Why can't the compiler infer that T is &str? Does it have something to do with the blanket impl<T> Borrow<T> for T? Is there a more idiomatic way to accept a generic argument by value or by reference? (Note that I need this to work even for T for which the AsRef implementation is missing.)

1 Like

In my experience it's not sufficient for the type inference to know that a solution exists. It wants to prove that no other solution is possible. When multiple layers of indirection can create a "diamond-shaped" relationship between types, it gives up.

For example you can't have:

let x: u64 = 1u32.into().into();

because for the path of u32 → X → u64 there could exist infinitely many different Xes. In your case there could exist more displayable types that can be borrowed as &str, and &str is only one of them.

3 Likes

It needs to prove this, in fact, since different paths in this diamond shape might give very different behavior. Consider this:

struct First(u32);
struct Second(u32);

impl From<u32> for First {
    fn from(val: u32) -> First {
        println!("First");
        First(val)
    }
}

impl From<u32> for Second {
    fn from(val: u32) -> Second {
        println!("Second");
        Second(val)
    }
}

impl Into<u64> for First {
    fn into(self) -> u64 {
        self.0 as u64
    }
}

impl Into<u64> for Second {
    fn into(self) -> u64 {
        self.0 as u64
    }
}

fn through_first(val: impl Into<First>) -> u64 {
    val.into().into()
}

fn through_second(val: impl Into<Second>) -> u64 {
    val.into().into()
}

fn main() {
    through_first(0u32); // prints "First"
    through_second(0u32); // prints "Second"
}

Functions through_first and through_second have identical bodies, identical outputs, we pass identical inputs to them, but the behavior is different. So, if we simply did 0u32.into().into(), Rust has to information to decide, whether we want to go through First, through Second, or probably through u32 or u64 (where one of intos would be no-op, but still existent).

1 Like

Is there a way to refactor the design in a way T = Borrow + Display + ?Sized... somehow

I see. If we modify my original example a bit:

let speaker: i32 = 42;
speaker.speak(); // OK
(&speaker).speak(); // type inference error

In the first case, i32 is unambiguously borrowed as i32. But in the second case &i32 can be borrowed as i32 or &i32 because both implement Display. In the original example, &str can be borrowed as str or &str, and the compiler can't figure out which I want.

Now I believe it makes sense. Still wish there were a generic way to take a type by value or by reference, for types which don't implement AsRef...

@EdmundsEcho, that's a good suggestion for a refactor, but as it happens I do not control the type T or the trait SomeTrait (i.e. they are from disjoint crates), so that would require someone else to impl<T> SomeTrait for Box<T>, impl<T> SomeTrait for Arc<T>, etc.

Edit: The trick is to impose a recursive trait bound where T: std::borrow::Borrow<T> + std::fmt::Display. This matches types which implement the trait (Display) and requires that that the type actually received by the function can be borrowed in such a way that disambiguates between impl Borrow<T> for T and impl Borrow<T> for &T.

OK, I think perhaps I've solved it for traits, although I haven't seen code like this in the wild so would welcome feedback about potential pitfalls. Basically, need to convince the compiler there's only way to Borrow the type T. You can borrow &T as T and you can borrow T as T, but you can't borrow T as &T. Then the trick is to require Borrow<&T>, for which is there is only one possibe implementation.

pub trait Speak<'a, T: ?Sized> {
    fn speak(self);
}
impl<'a, B, T> Speak<'a, T> for B
where
    B: std::borrow::Borrow<&'a T>,
    T: 'a + std::fmt::Display + ?Sized,
{
    fn speak(self) {
        println!("Says, \"{}\"", self.borrow());
    }
}

Then in the example below speaker.speak() takes &Self through the magic of its impl Speak. The type &Self is &i32 and there's only one implementation of Borrow<&i32> so the compiler is happy.

let speaker: i32 = 42;
speaker.speak();

And if we are working with a reference then Self is &i32 and there's still just one implementation of Borrow<&i32>.

let speaker_ref = &speaker;
speaker_ref.speak();

See more on the playground.

1 Like

But that seems at odds with your problem statement,

because that impl only works for &T. You may as well just do that explicitly:

impl<'a, T> Speak<'a, T> for &'a T
where
    T: 'a + std::fmt::Display + ?Sized,

Right?

1 Like

You are right, for traits std::borrow::Borrow is not necessary and it is enough to do the following, which will allow us to call speak() on T, &T, Box<T>, and anything else that can be coerced with std::ops::Deref.

pub trait Speak {
    fn speak(self);
}
impl<T> Speak for &T
where
    T: std::fmt::Display + ?Sized,
{
    fn speak(self) {
        println!("Says, {}", self);
    }
}

For functions in general the ref keyword satisfies my original design goal, or at least comes close to it. The caveat is that types which implement Deref must be borrowed with & or else they will be consumed (unless they are Copy), see compile error on the last line:

fn speak<T: std::fmt::Display>(ref msg: T) {
    println!("Says, {}", msg);
}

fn main() {
    let msg: &str = "hello";
    speak(msg); // not consumed
    speak(msg); // this works
    
    let msg = Box::new("hello".to_string());
    speak(&msg); // borrowed, not consumed
    speak(msg);  // consumed by moving into speak()
    speak(msg);  // FAILS, attempt to use after move
}

Reading into the history of Rust, this appears to be a deliberate design choice to improve readability. That is, if I am reading some code and see myfunc(myvar) I understand the intent to transfer ownership (unless myvar is Copy or is itself a reference), and if I see myfunc(&myvar) I immediately understand the intent to borrow.

The std::borrow::Borrow trait, despite it's universal name, appears to have really been a hack for making hash keys ergonomic. It probably shouldn't be relied upon outside of hashing, and definitely was not the solution for my problem! Edit: Although a little hackish, it turns out we actually do need Borrow to make this work for structures.