Keeping 2 indexes of the same data and borrow checker

I'm trying to make a road network router, and have 5 requirements:

  1. It must be able to route by geographical coordinates, and for that I use rstar::RTree index (RTree<&'a MyEdge>, borrowed to not duplicate the data).

  2. I run the algorithm and then want to reconstruct the path geometry -- that implies I must find edges and their geometries by vertex IDs. For that, I need a HashMap<(Vertex, Vertex), Edge> (or maybe HashMap<(Vertex, Vertex), LineString>).

  3. Graph must be updateable. This means I want to be able to find edges by (Vertex, Vertex) key and update/remove it.

  4. I want to minimize duplication of data. For that reason, I thought it's good to make the struct like

    #[derive(Hash, PartialEq, Eq)]
    pub struct Vertex(pub usize);
    
    #[derive(Hash, PartialEq, Eq)]
    pub struct EdgeKey(pub Vertex, pub Vertex);
    
    pub struct MyGraph {
        edges_map: HashMap<EdgeKey, MyEdge>
    }
    
    pub struct MyRouter<'a> {
        pub graph: &'a MyGraph,
        pub index: RTree<&'a MyEdge>,
    }
    

    MyRouter can't own MyGraph, otherwise it becomes self-referential via .index field.

  5. For unit tests, I needed a dummy router that is initialized with zero data and outputs a standard response, so that I can test the outer layers of code without producing a whole valid graph. This means I need a trait Router and implement it on MyRouter and DummyRouter.

    pub trait Router {
        fn simple_route(&mut self, source: Point, destination: Point, buf_right: f64, buf_left: f64) -> Result<Option<(LineString, Duration)>, Box<dyn Error>>;
    }
    
    impl<'a> Router for MyRouter<'a> {
        fn simple_route(&mut self, source: Point, destination: Point, buf_right: f64, buf_left: f64) -> Result<Option<(LineString, Duration)>, Box<dyn Error>> {
            todo!()
        }
    }
    
  6. The procedure of building a route is long, so I split it in testable stages.

    impl<'a> MyRouter<'a> {
        pub fn route_points(&'a mut self, source: Point, destination: Point, buf_right: f64, buf_left: f64) -> Result<Option<Route>, Box<dyn Error>> {
            ...
        }
    }
    
    impl<'a> Router for MyRouter<'a> {
        fn simple_route(&mut self, source: Point, destination: Point, buf_right: f64, buf_left: f64) -> Result<Option<(LineString, Duration)>, Box<dyn Error>> {
    //                  ^^^^ ERROR: compiler says this must have 'a lifetime
            self.route_points(source, destination, buf_right, buf_left).map(...)
        }
    }
    

At this point, complier demands me to alter fn simple_route and have &'a mut self instead of &mut self. (mut because inside there are also some Vecs of data that are reset when route is requested). And the big issue is: step by step, it demands just everything around to have 'a! Like every other function in MyRouter needs it, and DummyRouter now also needs this lifetime param. And they start conflicting -- somewhere something doesn't live long enough, and so on...

Am I wanting something unreasonable?

I'm really puzzled what to do and am gravitatig towards actually copying some data and making the pushups of writing syncronization of RTree index and the edges_map. It can be something like:


pub struct MyIndexItem { geom: LineString, edge: EdgeKey };
impl RTreeObject for RTreeItem { ... };

pub struct MyRouter {
    graph: MyGraph,
    rtree: RTree<MyIndexItem>,
}

This will require to check the edge case when the edge found in RTree is absent in the graph.

OTOH, with references, creation and updates of the router struct will need same amount of code anyway, so keeping RTree in sync with MyGraph isn't that much harder.

That's a &'a mut MyRouter<'a> which is exclusively borrowing the MyRouter<'a> forever.

What happens when you remove the outer 'a?

-pub fn route_points(&'a mut self, source: Point, destination: Point, buf_right: f64, buf_left: f64) -> 
+pub fn route_points(&mut self, source: Point, destination: Point, buf_right: f64, buf_left: f64) -> 

Edit: Probably you elaborated on it, let me read your post again.

Not seeing a reason for the initial addition of 'a so I'll wait for your reply.

1 Like

Good point. Then, compiler demands to put it back. The reason, I guess, is that Route struct borrows MyRouter:

pub struct Route<'a> {
    pub router: &'a MyRouter<'a>,
    pub start_proj: ProjectionOnEdge<'a>,
    pub end_proj: ProjectionOnEdge<'a>,
    pub path: PathObj,
}

and MyRouter is in it, because it's used to reconstruct the geometry (LineString):

pub fn geometry(&self) -> LineString<f32> {
  let mut geom = self.start_proj.segment_geom(SegmentKind::FromPoint).unwrap();
  for nd in self.path.get_nodes()[1..].iter() {
              
              let edge = self.router.edges_map.get(&EdgeKey(prev, *nd)).unwrap();
  //                                 ^^^^^^ USED HERE
              geom.0.extend(edge.geom.0[1..].iter());
              prev = *nd;
          }
    ...
}

I may make Router not keep it and have .geometry() need it passed by (immutable) ref. I'll check.

...oh and there's unwrap() which actually requires some structs to be in sync.

No, it didn't work because self is borrowed:


pub struct Route<'a> {
    pub start_proj: Projection<'a>, // borrows the edge 
    pub end_proj: Projection<'a>,
    pub path: PathObj,
}

impl<'a> Router for MyRouter<'a> {
    fn simple_route(&mut self, source: Point, destination: Point, buf_right: f64, buf_left: f64) -> Result<Option<(LineString, Duration)>, Box<dyn Error>> {
        let opt_route = self.route_points(source, destination, buf_right, buf_left)?;
        Ok(opt_route.map(|route| (route.geometry(&self.graph.edges_map), Duration(route.duration().0.round() as u32))))
//                                              ^^^^ already borrowed :(
    }
}

Maybe it can work if the router just returns the Route obj, releases the borrow and lets the caller call again? Going to sleep, will check later.

Another thought: the caller, that instantiated MyRouter, will have to keep MyGraph for the former to be alive. So MyRouter can return the Route object, and the caller should be able to pass MyGraph to Route::geometry(), and so we'll not be borrowing MyRouter.

Or probably even MyGraph should be able to have this method in it. I'll check that.

So, the dependencies initially were:

  Graph <= Router <= Route
  Graph <= Router.index

I'm going to try making it

 Graph <= Router
 Graph <= Router.index
 Graph <= Route

I wonder whether Box or Rc or Arc could help here.

Turn on #![deny(elided_lifetimes_in_paths)] (or make it a warning) and it will point out otherwise hidden borrows such as

    pub fn route_points(&mut self, ...) -> ...Option<Route    >...
    // Hidden borrow --------------------------->         <'_>

Whatever requires the Route<'_> lifetime to be the same as the MyRouter<'_> lifetime is tied up in something deeper than I've mocked up, it seems.

Generally speaking, it does seem you have a lot of data structures with interlocking borrows, and you're holding on to them while doing significant work. That's almost always painful in Rust. Maybe it can be untangled, but maybe Arc would be a more natural fit.

1 Like

Since routing requires mutable borrow of the entire MyRouter, I couldn't modify or query a HashMap inside the function. But I remembered I had a similar issue with the same MyRouter and same method couple of months ago and solved it by separating a method into a standalone function.

pub struct Projection<'a> {
    edge: &'a MyEdge,
    frac: f64,
    /// Distance from the beginning of line
    dist: f64
}

pub fn project_point<'a>(index: &'a RTree<&MyEdge>, point: Point, buf_right: f64, buf_left: f64) -> Vec<Projection<'a>> {
    ...
}

impl<'a> Router for MyRouter<'a> {
    fn route_points(&mut self, source: Point, destination: Point, buf_right: f64, buf_left: f64) -> Result<Option<Route>, Box<dyn Error>> {
        let source_edges = project_point(&self.index, source, buf_right, buf_left);
        let destination_edges = project_point(&self.index, destination, buf_right, buf_left);
        ...
    }
}

I'll check if it's a viable solution for another case of the same problem.

Box can never help with solving borrow errors. To the borrow checker, Box<T> looks exactly the same as a directly owned T.

1 Like

I managed to fix it without big overhauls.

The key problem that had happened earlier was this:

impl<'a> MyRouter<'a> {
    pub fn method1(&'a mut self, ...) {
        self.method2(...) // THIS CALL causes entire structure to be borrowed
        // do something useful too on self
        let result = self.property1...
    }

    pub fn method2(&'a mut self, ...) {
        ...
    }
}

If a &'a mut self method calls another such method, the whole struct is blocked, and below you basicall can't do anything with the struct or its members, because that requires anther borrow.

The solution is to stop calling other methods on self, and refactor that code in outside function. (or methods of members, if it's easy). Then the borrow checker is now happy because it knows that I need specific parts of self, and doesn't lock self entirely.

The code now looks kinda like this:

impl<'a> MyRouter<'a> {
    pub fn simple_route(&'a mut self, ...) {
        let start_vertice = make_projection_on_edges(...);
        let end_vertice = make_projection_on_edges(...);

        ...
        Ok(Route { result_data })
    }
}

pub fn make_projection_on_edges(edges_map: &HashMap<EdgeKey, &MyEdge>, point: Point, start_or_end: StartOrEnd) {
    ...
}
2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.