Using Borrow trait with a referenced value

user_16084771 0
Viewed 154

I have a custom trait that I want to implement on a HashMap<(u32, u32), &'a Edge>. Since I want my trait to work on both owned and referenced values, I use the Borrow trait as suggested by other SO posts but I am having issues with the borrow checker and the referenced &Edge. First, the compiler wants me to specifically add a lifetime to &Edge which I did as you can see below.

However, then the compiler complains that the return type of the function get_edge (Option<&'a Edge>) does not match the return type of the trait definition (Option<&Edge>). In my opinion, it does not make sense to add lifetime parameters to my trait definition so I guess the error must be somewhere along my implementation of the trait. However, no matter what combinations of lifetime parameters I try, I haven't been able to make the compiler happy. What exactly am I doing wrong here?

pub struct Edge {
    between: (u32, u32),
    weight: u32,
}

impl Edge {
    pub fn normalize_edge(v1: u32, v2: u32) -> (u32, u32) {
        (v1.min(v2), v1.max(v2))
    }

    fn get_weight(&self) -> u32 {
        self.weight
    }
}

trait EdgeFinder {
    fn get_edge(&self, v1: u32, v2: u32) -> Option<&Edge>;
    fn get_weight(&self, v1: u32, v2: u32) -> Option<u32>;
}

impl<'a, 'b, B: Borrow<HashMap<(u32, u32), &'a Edge>> + 'b> EdgeFinder for B {
    fn get_edge(&self, v1: u32, v2: u32) -> Option<&Edge> {
        self.borrow().get(&Edge::normalize_edge(v1, v2)).map(|&e| e)
    }

    fn get_weight(&self, v1: u32, v2: u32) -> Option<u32> {
        self.get_edge(v1, v2).and_then(|v| Some(v.get_weight()))
    }
}

Edit: I added the definition of Edge above although it should not matter. Here is the compiler output:

error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements
  --> src/graph.rs:44:23
   |
44 |         self.borrow().get(&(0,0)).map(|&e| e)
   |                       ^^^
   |
note: first, the lifetime cannot outlive the lifetime `'a` as defined on the impl at 41:6...
  --> src/graph.rs:41:6
   |
41 | impl<'a, 'b, B: 'b + Borrow<HashMap<(u32, u32), &'a Edge>>> EdgeFinder for B {
   |      ^^
note: ...so that the types are compatible
  --> src/graph.rs:44:23
   |
44 |         self.borrow().get(&(0,0)).map(|&e| e)
   |                       ^^^
   = note: expected `&HashMap<(u32, u32), &Edge>`
              found `&HashMap<(u32, u32), &'a Edge>`
note: but, the lifetime must be valid for the anonymous lifetime defined on the method body at 42:17...
  --> src/graph.rs:42:17
   |
42 |     fn get_edge(&self, v1: u32, v2: u32) -> Option<&Edge> {
   |                 ^^^^^
note: ...so that the expression is assignable
  --> src/graph.rs:44:9
   |
44 |         self.borrow().get(&(0,0)).map(|&e| e)
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: expected `Option<&Edge>`
              found `Option<&Edge>`

Edit 2: To add a little bit of context, I try to create a wrapper structure around an EdgeFinder but I don't want to enforce whether the wrapped EdgeFinder is owned or a reference.

pub struct EdgeViewer<T: EdgeFinder> {
    inner: T,
}

impl<T: EdgeFinder> EdgeViewer<T> {
  //Obviously works for owned values.
  pub fn new(inner: T) -> Self {
     EdgeViewer { inner }
  }
}

However, when using a reference, the following compiler output is shown, which led me to believe that I need to specifically add an implementation for the referenced version.

error[E0277]: the trait bound `&HashMap<(u32, u32), &Edge>: EdgeFinder` is not satisfied
  --> src/construction.rs:74:43
   |
74 |     let mut edge_viewer = EdgeViewer::new(&edges);
   |                                           -^^^^^
   |                                           |
   |                                           the trait `EdgeFinder` is not implemented for `&HashMap<(u32, u32), &Edge>`
   |                                           help: consider removing the leading `&`-reference
   |
   = help: the following implementations were found:
             <HashMap<(u32, u32), &Edge> as EdgeFinder>
note: required by `EdgeViewer::<T>::new`
  --> src/graph.rs:58:5
   |
58 |     pub fn new(inner: T) -> Self {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
rust lifetime
1 Answers

The complete solution: playground

use std::{borrow::Borrow, collections::HashMap, marker::PhantomData, ops::Deref};

#[derive(Debug)]
pub struct Edge {
    between: (u32, u32),
    weight: u32,
}

impl Edge {
    pub fn normalize_edge(v1: u32, v2: u32) -> (u32, u32) {
        (v1.min(v2), v1.max(v2))
    }

    fn get_weight(&self) -> u32 {
        self.weight
    }
}

pub trait EdgeFinder {
    fn get_edge(&self, v1: u32, v2: u32) -> Option<&Edge>;
    fn get_weight(&self, v1: u32, v2: u32) -> Option<u32>;
}

impl EdgeFinder for HashMap<(u32, u32), &Edge> {
    fn get_edge(&self, v1: u32, v2: u32) -> Option<&Edge> {
        self.get(&Edge::normalize_edge(v1, v2)).copied()
    }

    fn get_weight(&self, v1: u32, v2: u32) -> Option<u32> {
        self.get_edge(v1, v2).map(|v| v.get_weight())
    }
}

pub struct EdgeViewer<T, U>
where
    T: Borrow<U>,
    U: EdgeFinder,
{
    inner: T,
    __phantom: PhantomData<U>,
}

impl<T, U> EdgeViewer<T, U>
where
    T: Borrow<U>,
    U: EdgeFinder,
{
    pub fn new(inner: T) -> Self {
        EdgeViewer {
            inner,
            __phantom: PhantomData,
        }
    }
}

impl<T, U> Deref for EdgeViewer<T, U>
where
    T: Borrow<U>,
    U: EdgeFinder,
{
    type Target = T;
    fn deref(&self) -> &Self::Target {
        &self.inner
    }
}

fn main() {
    let e1 = Edge {
        between: (0, 1),
        weight: 1,
    };

    let e2 = Edge {
        between: (1, 2),
        weight: 1,
    };

    let mut map = HashMap::new();
    map.insert((0, 1), &e1);
    map.insert((1, 2), &e2);

    let viewer: EdgeViewer<_, HashMap<(u32, u32), &Edge>> = EdgeViewer::new(&map);

    let found_edge = viewer.get_edge(0, 1);

    println!("{:?}", found_edge);
}

First, EdgeFinder trait is implemented on HashMap<(u32, u32), &Edge>.

Second, the Borrow<HasMap<K,V>> trait is implemented on HasMap<K,V> and &HasMap<K,V>, because Borrow trait provides Borrow<X> blanket implementations for X and &X (docs).

So, T: Borrow<U>, U: EdgeFinder trait bound is satisfied by HashMap<(u32, u32), &Edge> and &HashMap<(u32, u32), &Edge> as T.

This makes EdgeViewer::new accepts HashMap<(u32, u32), &Edge> and &HashMap<(u32, u32), &Edge>, and gives EdgeViewer access to EdgeFinder trait through its inner field.

Deref trait is implemented for convenience, but getter to inner could also be used.

PhantomData is required to remove ambiguity on U type. indeed, Borrow<U> is a generic trait over U, and so Borrow could be implemented on several types. Thanks to PhantomData, we can specify that U is HashMap<(u32, u32), &Edge>. At least, this is how i understant it.

Note1: EdgeFinder implementation on HashMap<(u32, u32), &'a Edge> and &HashMap<(u32, u32), &'a Edge> is not a valid answer cause it requires several EdgeFinder implementations. (see playground)

Note 2: AsRef trait can not be used easily here, because it is not implemented on HasMap<K,V> and &HasMap<K,V>

user_112419610
Related