I can't figure out this lifetime problem: cannot infer an appropriate lifetime for autoref due to conflicting requirements

help
1

I am pressing on with learning Rust. I feel like the lifetime penny has half dropped for me, and I need a bit of help getting it the rest of the way.
I have come up with a silly little project to facilitate the learning process. It is a simulated economy, whereby economic agents trade with each other.

use std::collections::HashMap;

#[derive(PartialEq, Eq, Hash, Copy, Clone)]
enum ResourceName {
    Food
}

type AgentId = u32;

struct Offer {
    maker_id:AgentId,
    resource_name:ResourceName,
    min_amount:f64,
    max_amount:f64,
    price:f64
}

struct ProposedTrade<'a> {
    taker_id:AgentId,
    offer:&'a Offer,
    amount:f64,
    value:f64
}

trait EconomicAgent {
    fn set_offers(&self) -> Vec<Offer>;
    fn proposed_trades<'a>(&self, offers:& 'a HashMap<ResourceName, Vec<&Offer>>) -> Vec<ProposedTrade<'a>>;
    fn settle_maker_side<'a>(&mut self, propsed_trades:Vec<&'a ProposedTrade<'a>>) -> Vec<&ProposedTrade<'a>>;
    fn settle_taker_side<'a>(&mut self, proposed_trades:Vec<&'a ProposedTrade>);
}

struct AgentCollection {
    available_ids: Vec<AgentId>,
    agents: HashMap<AgentId, Box<dyn EconomicAgent>>
}
impl AgentCollection {
    fn create_agent(&mut self, f: fn(AgentId) -> Box<dyn EconomicAgent>) -> Option<AgentId> {
        let id = self.available_ids.pop()?;
        let agent = f(id);
        self.agents.insert(id, agent);
        Some(id)
    }

    fn destroy_agent(&mut self, agent_id: AgentId) {
        self.agents.remove(&agent_id);
        self.available_ids.push(agent_id);
    }
}

fn economy_loop<'a>(mut agent_col:AgentCollection){
    use itertools::Itertools;
    let mut offers : Vec<Offer> = 
        agent_col.agents.iter()
        .flat_map(|(_, agent)|agent.set_offers())
        .collect();
        
    offers.sort_by(|o1, o2|o1.price.partial_cmp(&o2.price).unwrap());

    let offer_map =
        offers.iter()
        .map(|offer|(offer.resource_name, offer))
        .into_group_map();

    let mut proposed_trades : Vec<ProposedTrade> =
        agent_col.agents.iter()
        .flat_map(|(_, agent)|agent.proposed_trades(&offer_map))
        .collect();

    use rand::thread_rng;
    use rand::seq::SliceRandom;
    proposed_trades.shuffle(&mut thread_rng());

    let proposed_trades_map =
        proposed_trades.iter()
        .map(|pt|(pt.offer.maker_id, pt))
        .into_group_map();

    let partially_settled:Vec<&ProposedTrade> =
        proposed_trades_map.iter().flat_map(|(maker_id, pts)|{
            let mut maker = agent_col.agents.get_mut(&maker_id).unwrap();
            maker.settle_maker_side(*pts)
        }).collect()
        ;
}

fn main() {
    println!("Hello, world!");
}

The compiler does not like the last batch of code. Sorry for the long code snippet, I tried to distill the problem down to something minimal, but my minimal code did not present any problems, which further highlights my lack of understanding here.

Would be minimal code:

struct Foo(usize);
struct Bar{
    foo_count:usize
}
impl Bar {
    fn choose_foos<'a>(&mut self, foos:Vec<&'a Foo>) -> Vec<&'a Foo> {
        self.foo_count = foos.len();
        foos.into_iter().filter(|foo|foo.0 > 5).collect()
    }
}

fn foo_bar(bar_map:HashMap<usize, Bar>, bar_id:usize, foos:Vec<&Foo>) -> Vec<&Foo>{
    let mut bar = bar_map.get_mut(&bar_id).unwrap();
    bar.choose_foos(foos)
}
2

To answer your question, we have to understand what the lifetimes here mean:

trait EconomicAgent {
    fn settle_maker_side<'a, 'b>(
        &'b mut self,
        propsed_trades: Vec<&'a ProposedTrade<'a>>,
    ) -> Vec<&'b ProposedTrade<'a>>;

    ...
}

I have added a 'b lifetimes to highlight the elided lifetimes in the definition. Notice the 'b lifetime. This use of the 'b lifetime tells the compiler that the references stored in the returned vector point into the self argument.

This means that the mutable borrow of maker lasts until partially_settled goes out of scope. However, mutable borrows must be exclusive, and the compiler is not able to provide that they are in fact mutable borrows of different things, hence the error.

To fix it, add an 'a on the returned reference.

1 Like
3

You suggestion works (after removing some other lifetime specifiers that shouldn't be there). Thank you.
However I still don't understand your explanation; this must be how @ZiCog feels about monads :yum:

Are you saying that for some implementation of EconomicAgent, the returned vector should be owned and contained by the implementor? (That is my interpretation of the word "point" when applied to references). My intention here is that the returned vector is a subset of the input vector.

This part really confused me. maker and partially_settled are different types so they are trivially different things, no? What have I misunderstood?

This is how I have finished off that bit of code, which seems to compile without complaints.

    let partially_settled:Vec<&ProposedTrade> =
        proposed_trades_map.into_iter().flat_map(|(maker_id, pts)|{
            let maker = agent_col.agents.get_mut(&maker_id).unwrap();
            maker.settle_maker_side(pts)
        }).collect();

    let partially_settled_map = 
        partially_settled.iter()
        .map(|pt|(pt.taker_id, *pt))
        .into_group_map();

    for (taker_id, pts) in partially_settled_map.into_iter() {
        let taker = agent_col.agents.get_mut(&taker_id).unwrap();
        taker.settle_taker_side(pts);
    }

Have I not taken another mutable borrow of the contents of agents (which is what maker was earlier) whilst partially_settled is still in scope?

4

Yes, but by using the lifetime from self instead of the input vector's lifetime on the returned references, you told the compiler that the returned vector points into self, and not into the input vector, hence the compile error.

Your would-be minimal example compiles because you used the lifetimes differently.

I was talking about different instances of maker in different iterations.

Since you told the compiler that the values returned from the flat_map closure borrow from maker, and since it is a mutable borrow, the compiler must verify that the maker in each iteration is distinct, as you would otherwise mutably borrow the same maker in multiple calls to the closure, which would be invalid as the borrow of maker lasts until after the call to the closure (due to the misplaced lifetime).

The compiler fails to verify the code as it cannot verify that each maker is different and non-overlapping with any other maker in any other iteration.

Once you fix the lifetimes, the borrow of maker no longer needs to last into other iterations of the loop, which is why it compiles, as the borrows then trivially don't overlap.

5

I get it now. Thanks again.

6

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.