Lifetime overlapping problem and syntax

help
1 
use std::sync::atomic::{AtomicI32, Ordering::Relaxed};

pub struct Person {
    id: i32,
    name: String,
}

static NEXT_MALE_ID: AtomicI32 = AtomicI32::new(1);
static NEXT_FEMALE_ID: AtomicI32 = AtomicI32::new(-1);

impl Person {
    pub fn new(name: String, is_male: bool) -> Self {
        Person {
            id: if is_male {
                NEXT_MALE_ID.fetch_add(1, Relaxed)
            } else {
                NEXT_FEMALE_ID.fetch_sub(1, Relaxed)
            },
            name: name,
        }
    }
}

pub struct Spouse<'a, 'b> {
    base: &'a Person,
    engaged_to: Option<&'b Person>,
    preferences: Vec<&'b Person>,
}

impl<'a, 'b> Spouse<'a, 'b> {
    pub fn new(base: &'a Person, preferences: Vec<&'b Person>) -> Self {
        Self {
            base: base,
            engaged_to: None,
            preferences: preferences,
        }
    }

    pub fn engage_to(mut self, spouse: Option<&'b Person>) {
        self.engaged_to = spouse
    }

    pub fn prefers_more_than_current(self, spouse: &'a Person) -> Option<bool> {
        match self.engaged_to {
            None => Some(true),
            Some(current) => {
                for person in self.preferences {
                    if person.id == spouse.id {
                        return Some(true);
                    } else if person.id == current.id {
                        return Some(false);
                    }
                }
                None
            }
        }
    }
}

struct Population<'a, 'b> {
    males: Vec<Spouse<'a, 'b>>,
    females: Vec<Spouse<'a, 'b>>,
}

pub fn engage<'h, 'w>(mut husband: &'h Spouse, mut wife: &'w Spouse) {
    husband.engaged_to = Some(wife.base); // Illegal
    wife.engaged_to = Some(husband.base); // Illegal
}

This is an emulation of the stable matching problem. Husbands and Wives have Person bases. A Husband<'a, 'b> has a base of &'a Person and preference of Option<&'b Person>. However when I try to engage a husband with a wife the compiler complains:

error[E0623]: lifetime mismatch
  --> src/stable_matching.rs:66:26
   |
65 | pub fn engage<'h, 'w>(mut husband: &'h Spouse, mut wife: &'w Spouse) {
   |                                        ------                ------ these two types are declared with different lifetimes...
66 |     husband.engaged_to = Some(wife.base);
   |                          ^^^^^^^^^^^^^^^ ...but data from `wife` flows into `husband` here

What's the syntax for specifying that the husband parameter has a lifetime of <'h, 'w> and wife <'w, 'h>?

2

A Person only has 1 lifetime, which is determined by the scope over which the Person is valid. So it doesn't make sense to say that the parameter has a lifetime of <'h, 'w>. What you want to do is identify a subset of 'h and 'w for which they are both valid. Normally, that would be fairly simple: just use a single lifetime everywhere and let the compiler sort it out. But you're going to have trouble because you're storing these references in Spouse objects, so you've got a problem in engage where you're trying to take two Spouses and make them refer to each other, but they can't do that if you haven't guaranteed that they will both always be valid at the same time.

To specify that, you would write something like this:

pub fn engage<'a>(mut husband: &mut Spouse<'a, 'a>, mut wife: &mut Spouse<'a, 'a>) {
    husband.engaged_to = Some(wife.base);
    wife.engaged_to = Some(husband.base);
}

From here you can see why using two lifetime parameters might look odd. Most of what you're doing looks like it wants to assume you have a pool of Persons that are all valid at the same time, so don't need both 'h and 'w to be present anywhere in your code, as far as I can tell.

For completeness, here's the way I'd write it with only a single lifetime parameter:

use std::sync::atomic::{AtomicI32, Ordering::Relaxed};

pub struct Person {
    id: i32,
    name: String,
}

static NEXT_MALE_ID: AtomicI32 = AtomicI32::new(1);
static NEXT_FEMALE_ID: AtomicI32 = AtomicI32::new(-1);

impl Person {
    pub fn new(name: String, is_male: bool) -> Self {
        Person {
            id: if is_male {
                NEXT_MALE_ID.fetch_add(1, Relaxed)
            } else {
                NEXT_FEMALE_ID.fetch_sub(1, Relaxed)
            },
            name: name,
        }
    }
}

pub struct Spouse<'a> {
    base: &'a Person,
    engaged_to: Option<&'a Person>,
    preferences: Vec<&'a Person>,
}

impl<'a> Spouse<'a> {
    pub fn new(base: &'a Person, preferences: Vec<&'a Person>) -> Self {
        Self {
            base: base,
            engaged_to: None,
            preferences: preferences,
        }
    }

    pub fn engage_to(mut self, spouse: Option<&'a Person>) {
        self.engaged_to = spouse
    }

    pub fn prefers_more_than_current(self, spouse: &'a Person) -> Option<bool> {
        match self.engaged_to {
            None => Some(true),
            Some(current) => {
                for person in self.preferences {
                    if person.id == spouse.id {
                        return Some(true);
                    } else if person.id == current.id {
                        return Some(false);
                    }
                }
                None
            }
        }
    }
}

struct Population<'a> {
    males: Vec<Spouse<'a>>,
    females: Vec<Spouse<'a>>,
}

pub fn engage<'a>(mut husband: &mut Spouse<'a>, mut wife: &mut Spouse<'a>) {
    husband.engaged_to = Some(wife.base); // Illegal
    wife.engaged_to = Some(husband.base); // Illegal
}
3

Doesn’t that mean a spouse has the same lifetime as its ‘engaged_to’?

4

It means that the Spouse is only valid if both the base and engaged_to are valid during the same scope. It's a lower bound, so either could end up outliving the other, but this particular code won't care about that.

If we're using two lifetime parameters, we really should be asking which outlives the other and expressing that relationship. If we're just looking at the overlap, we don't need two different lifetime parameters, because the compiler will attempt to scope the borrows to the minimum needed for a function call, and that often means two arguments to a function are given borrows over the same period.

For the code you've provided it ends up working either way. My rewrite simplifies it some, but that might make it harder to do some more complicated handling in the future. It depends on what other things you're trying to do.

1 Like
5

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.