Borrowed value does not live long enough in BTreeSet test

help
1

This program is derived from tests for BTreeSet:

use pstd::collections::BTreeSet;

fn main() {
    let s246 = BTreeSet::from([2, 4, 6]);
    let s23456 = BTreeSet::from_iter(2..=6);
    let mut iter = s246.difference(&s23456);
    assert_eq!(iter.size_hint(), (0, Some(3)));
    assert_eq!(iter.next(), None);

    let s12345 = BTreeSet::from_iter(1..=5);
    iter = s246.difference(&s12345);
    assert_eq!(iter.size_hint(), (0, Some(3)));
    assert_eq!(iter.next(), Some(&6));
    assert_eq!(iter.size_hint(), (0, Some(0)));
    assert_eq!(iter.next(), None);
}

It doesn't compile, I get an error:

error[E0597]: `s12345` does not live long enough
  --> src/main.rs:11:28
   |
10 |     let s12345 = BTreeSet::from_iter(1..=5);
   |         ------ binding `s12345` declared here
11 |     iter = s246.difference(&s12345);
   |                            ^^^^^^^ borrowed value does not live long enough
...
16 | }
   | -
   | |
   | `s12345` dropped here while still borrowed
   | borrow might be used here, when `iter` is dropped and runs the destructor for type `pstd::collections::btree_set::Difference<'_, i32, CustomTuning>`
   |
   = note: values in a scope are dropped in the opposite order they are defined

For more information about this error, try `rustc --explain E0597`.

I vaguely understand the error, and if I change the line

    iter = s246.difference(&s12345);

to

    let mut iter = s246.difference(&s12345);

the error goes away and everything is fine. What I don't understand though is that if I use std rather than pstd ( the crate I am developing ) the error also goes away. Is there some magic to suppress the error in std? What is going on?

1 Like
2

Could you post the definitions of your BTreeSet, your BTree Iterator and the difference function?
It's hard (or even impossible) to figure out lifetime issues without knowing the function signatures.

3

Sure, it is a published crate, the difference function is here:

The iterator is here:

BTtreeSet is here:

The definition and implementation is very similar to the std::collections:BTreeSet, although the underlying BTreeMap is implemented differently.

pstd is intended to be an alternative to std.

4

I am pretty sure it is because std uses the may_dangle attribute for the BTreeMap destructor.

The error message says something about the lifetime being dead when the object is dropped, which may_dangle suppresses. This is sadly one of the ways the std is currently a bit special.

Here are some links where you can read more.

3 Likes
5

Ah, yes, that is helpful, although I haven't figured the difference yet.

6

The drop checker is i think one of the most subtle corners of Rust.
I don't really understand how it affects this code though. Has your Difference type Drop glue (a automatically generated drop function that only drops the fields)?
The std ones doesn't i think.

7

I just had a look at std::collections::BTreeMap and it has an interesting-looking attribute I never saw before: #[rustc_insignificant_dtor]

8

I don't know how that attribute works. There doesn't seem to be much documentation (makes sense, it's completely internal). At this point you might have more luck asking on the zulip: https://rust-lang.zulipchat.com/

9

I don't think so, there shouldn't be anything to do when dropping Difference. I agree that might be the crucial thing, whereas I don't think BTreeMap having a significant destructor should matter here. But I am a bit lost and not thinking too clearly!

1 Like
10

I asked this because the error message says: when 'iter' is dropped and runs the destructor for type 'pstd::_::Difference<'_, i32>. So it seems like it has some kind of Drop glue. That would explain the difference.

I agree with you there.

1 Like
11

I think I maybe figured it out. The iterator has a stack of values to keep track, implemented using arrayvec::ArrayVec. ArrayVec has a drop function. It doesn't actually do anything in this case because it will be full of references, but I guess the compiler won't be able to figure that out. The std BTreeMap doesn't need a stack because it stores parent pointers in the nodes.

Maybe I can make an ArrayVec for references only that doesn't have a drop function? Or is that thought nonsensical.

1 Like
12

I think that is what maybe_dangling is for. If ArrayVec had used it i believe then it would work.

13

Yes, I think I can make an ArrayVec with #[may_dangle], but this stuff is scary unsafe!

Perhaps I will give it a go and ask for a review.

Oh, but looking here, I don't think may_dangle is available on Stable. So maybe I won't bother.

14

You could make a version of ArrayVec that doesn't implement Drop but also doesn't support types with drop glue (could be checked in a const block or you could require the items to implement Copy as a more limiting approximation).

4 Likes
15

The problem is that when you use a inmutable, it could be calculated in compile time so there is not a memory to get a memory adresse

fn main() {
let s246 = BTreeSet::from([2, 4, 6]);
let s12345: BTreeSet< i32> = BTreeSet::from_iter(1..=5);
let s23456 = BTreeSet::from_iter(2..=6);
let mut iter = s246.difference(&s23456);
assert_eq!(iter.size_hint(), (0, Some(3)));
assert_eq!(iter.next(), None);

 iter = s246.difference(&s12345);
assert_eq!(iter.size_hint(), (0, Some(3)));
assert_eq!(iter.next(), Some(&6));
assert_eq!(iter.size_hint(), (0, Some(0)));
assert_eq!(iter.next(), None);

}

16

Thanks! I did that and it worked. It is here:

I didn't worry about types with drop glue, as it is not a public type and at worst it would leak memory ( which is not unsafe ).

17

You can use needs_drop in std::mem - Rust to make sure that you get a compile error if the type is used with a type that needs to be dropped.

Something like this:

const _NO_DROP: () = assert!(std::mem::needs_drop::<T>(), false);

Or you could add the assert in a const block, for example in the new function.

2 Likes
18

I implemented a const check in the new function:

        // Check that T does not have a drop function.
        const{ assert!(!std::mem::needs_drop::<T>(),"T has drop"); };

but then commented it out, as it is not exactly wrong to use it with a type that needs to be dropped, rather there is a risk of memory leaking if appropriate measures are not taken to empty the struct (which could typically be done with a drop function on the enclosing struct).

In other words, it seem unnecessarily restrictive.

19

It can be a pretty big footgun though! I would argue for keeping the assert by default and removing it only if you have a legit usecase that it prevents.

1 Like
20

Fair point. I put it back in.

The documentation is a little worrying though:

"
Returns true if dropping values of type T matters. This is purely an optimization hint, and may be implemented conservatively: it may return true for types that don’t actually need to be dropped.
"

Which could be a problem at least in theory?