Confusing error message when using Borrow'd keys in Hashmap

[ejmount]

Code

use std::borrow::Borrow;
use bumpalo::Bump;
use std::collections::HashSet;

#[derive(PartialEq, Eq, Hash)]
struct Board; 

#[derive(PartialEq, Eq, Hash)]
struct TreeNode<'a> {
    state: Board, 
    foo: &'a ()
}

impl Borrow<Board> for TreeNode<'_> {
    fn borrow(&self) -> &Board {
        &self.state
    }
}

// Reduced for clarity
fn new_from_bump<'b>(state: Board, alloc: &'b Bump, cache: &HashSet<&'b TreeNode>) {
        cache.contains(&state);
}

Current output

error[E0277]: the trait bound `&TreeNode<'_>: Borrow<Board>` is not satisfied
   --> src/lib.rs:22:24
    |
22  |         cache.contains(&state);
    |               -------- ^^^^^^ the trait `Borrow<Board>` is not implemented for `&TreeNode<'_>`
    |               |
    |               required by a bound introduced by this call
    |
note: required by a bound in `HashSet::<T, S>::contains`
   --> /playground/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/collections/hash/set.rs:671:12
    |
669 |     pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
    |            -------- required by a bound in this associated function
670 |     where
671 |         T: Borrow<Q>,
    |            ^^^^^^^^^ required by this bound in `HashSet::<T, S>::contains`
help: consider removing the leading `&`-reference
    |
22  -         cache.contains(&state);
22  +         cache.contains(state);
    |

Rationale and extra context

I'm not confident I'm interpreting this correctly, but I think this error message is misleading because the signature of contains implies that the Borrow implementation needs to be on the type Q=Board. Additionally, taking the suggestion of removing the & leads to an error because the parameter needs to be a &Q and there's no valid type for Q that makes &Q equal to Board.

Changing the Borrow impl to instead be for &TreeNode does work, but looking at the docs, this isn't consistent with the general concept of the trait or the other examples in stdlib so I feel like it's not the right answer. If it is the right answer, the provided error message doesn't do anything to point me in that direction.

Rust Version

❯ rustc --version --verbose
rustc 1.81.0 (eeb90cda1 2024-09-04)
binary: rustc
commit-hash: eeb90cda1969383f56a2637cbd3037bdf598841c
commit-date: 2024-09-04
host: x86_64-pc-windows-msvc
release: 1.81.0
LLVM version: 18.1.7

[QuineDot]

Changing the Borrow impl to instead be for &TreeNode does work, but looking at the docs, this isn't consistent with the general concept of the trait or the other examples in stdlib so I feel like it's not the right answer. If it is the right answer, the provided error message doesn't do anything to point me in that direction.

Implementing Borrow<Board> for both TreeNode<'_> and &TreeNode<'_> is a solution to your error, and what the help should suggest instead of the invalid suggestion to remove & from a method that requires a reference. (You have to supply the implementation yourself as it's not possible for std to provide both impl<T: ?Sized> Borrow<T> for T and a blanket transitive implementation for references.)