I am uncertain what the 'a lifetime constraint on F in this struct definition does:
pub struct ExtractIf<'a, K, V, F, A = Global>
where
A: Allocator + Clone,
F: 'a + FnMut(&K, &mut V) -> bool,
Why is it there? What effect does it have?
If you look at the signature for BTreeMap::extract_if...
pub fn extract_if<F>(&mut self, pred: F) -> ExtractIf<'_, K, V, F, A> â
where
K: Ord,
F: FnMut(&K, &mut V) -> bool,
The lifetime in ExtractIf is tied to the lifetime of the BTreeMap that created it. The simple assumption is that ExtractIf contains one or more references to the original BTreeMap. This makes sense given that an ExtractIf needs access to the BTreeMap's underlying data.
If you want a more specific answer, you can use the "souorce" link in the docs to look at the source code and see what the lifetime is used on.
1 Like
It is
F: 'a +
That I don't understand. I understand why the struct needs a 'a parameter.
Just in case I wasn't clear, one possibility is that it is doesn't do anything, it is some kind of mistake, although I consider this unlikely, it is (much!) more likely it is my understanding that is deficient!
In combination with how it's created, it means that the BTreeMap must remain exclusively borrowed so long as the passed-in closure is valid. I couldn't find a specific reason for it.
These use to be DrainFilters that drained on Drop, and it's possible that they needed the bounds for the Drop implementation, but I stopped digging at that point.
1 Like
Ok, I think the borrowing constraint would still be there anyway, so perhaps it is a case of "a harmless extra constraint that doesn't do anything" ?
Another case of lifetime constraints that seem superfluous (to me!) is here:
pub struct Iter<'a, K, V>
where
K: 'a,
V: 'a,
I don't think the where clause is needed ( but as always I could definitely be wrong ). My implementation doesn't have it (yet.... I am "worrying" about the discrepancy), and seems to work perfectly well:
pub struct Iter<'a, K, V> { /* private fields */ }
No, it wouldn't be. If you look at the struct definition, the fields with lifetimes and the field storing F are disjoint.
If you dig into the underlying types in this case you'll find
range: LazyLeafRange<marker::Immut<'a>, K, V>,
And note that the first parameter there is a type generic, not a lifetime generic:
pub struct LazyLeafRange<BorrowType, K, V> {
front: Option<LazyLeafHandle<BorrowType, K, V>>,
back: Option<LazyLeafHandle<BorrowType, K, V>>,
}
So there is again no way the compiler could have deduced (inferred) that K: 'a and V: 'a. (And unlike the previous example, a &'a _ with Ks and Vs "within" it had to exist to create the Iter.)
1 Like
Ah, interesting. What do you think about my implementation without those constraints? Is it ok, or am I somehow in error? I am definitely in a state of confusion here!
I don't know your implementation (or the one in std!) well enough to give a good answer. But as far as my intuition goes...
In the case of K and V I'd probably add them if they're not implied and you have any doubt. If nothing else it may prevent you from shooting your own foot. Also... if they're not implied, you must be carrying the lifetime around some other way. You need to make sure you're doing the correct thing with regards to variance there. Usually that means something like "this should act like I'm carrying a &'a (K, V), so use PhantomData<&'a (K, V)> to carry the lifetime around".
I didn't dig deep enough to understand why it was on F in the first place.
1 Like
My implementation (for iterators) could be in safe Rust if I used Vec rather than special-purpose Vec implementations. My mental model is as you say for Vec implementations, which is use PhantomData where I have raw pointers.
So it seems ok, and it appears to work ok, I think the variance is fine, I just wish I understood the std library constraints better, to be frank I really don't even comprehend what T: 'a means, I am comfortable with &'a which makes some kind of sense to me,
On its own T: 'a basically means that any borrows that the type T captures are valid for 'a or longer.[1][2]
A &'a T requires that T: 'a, so one way to think of it is "&'a T is valid".
If you're using PhantomData<&'a (K, V)> or similar, you probably are getting the K: 'a and V: 'a bounds implicitly. You can test it by doing something like this:
fn test<'a, K, V>(
// Comment this to see a borrow check error
_imply_bounds_based_on: map::Iter<'a, K, V>
) {
let _: &'a [K; 0] = &[];
let _: &'a [V; 0] = &[];
}
If you're not using unsafe, there's rarely a reason to declare lifetime bounds on your struct explicitly. Except when the compiler yells at you because something requires 'static. But you use to have to. (And you still have to for 'static specifically.)
As for F in ExtractIf, after some more poking around and mulling, I think it's just an oversight. I left a comment on the tracking issue.
It actually means "is valid for
'a" in a more general sense, and there need not be an actual borrow involved in niche circumstances, but you can ignore that when getting a feel forT: 'a. âŠī¸The check is performed syntactically, but that doesn't really tell you what it means semantically. âŠī¸
1 Like
I just did another google and arrived at this, where an answer states (among other things):
However, before Rust 1.31 the bound was not inferred and would have to be provided explicitly
So it appears these bounds may be viewed as "historic artefacts".
Sometimes. As I mentioned before,
for some of these data structures.
Ok. Certainly the referenced RFC seems to be very helpful for explaining what is going on here.
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.