How to end a borrow in an enum? (for lazy task execution)

Hey all,
For separating the creation of the task (lazily) and the execution, I run into this problem:
if an enum can either borrow or own a value. How to change a borrowed to an onwed value for that enum WITH decoupling from the original value?

See my try below, but it doesnt work since the compiler still recognizes the test_enum to contain the borrowed reference to the original_input: "cannot move out of original_input because it is borrowed"

        ///Struct that does not implement the Copy trait
        #[derive(Clone)]
        struct TestStruct {
            value: i32,
        }

        /// Enum that can either borrow or Own a Test STruct
        enum TestEnum<'a> {
            Borrow { borrowed: &'a TestStruct },
            Own { owned: TestStruct },
        }
        impl TestEnum<'_> {
            /// Convert borrowed to owned values
            fn change_borrowed_to_owned(&mut self) {
                if let TestEnum::Borrow { borrowed: t } = self {
                    *self = TestEnum::Own {
                        //owned: t.clone(), //does not work, still complains about the lifetime
                        owned: t.to_owned(), //does not work, still complains about the lifetime
                        //owned: t.clone_into(), //does not make sense -> still need the original
                    };
                } else {
                    panic!("TestEnum already has Ownership")
                }
            }
            /// Convert borrowed to owned values
            fn change_borrowed_to_owned_v2(&mut self) -> Self {
                if let TestEnum::Borrow { borrowed: t } = self {
                    return TestEnum::Own {
                        owned: t.clone(), //does not work, still complains about the lifetime
                        //owned: t.to_owned(), //does not work, still complains about the lifetime
                        //owned: t.clone_into(), //does not make sense -> still need the original
                    };
                } else {
                    panic!("TestEnum already has Ownership")
                }
            }

            ///test output
            fn print(self) {
                match self {
                    TestEnum::Own { owned: t } => println!("Owned value: {}", t.value),
                    TestEnum::Borrow { borrowed: t } => println!("Borrowed value: {}", t.value),
                }
            }
        }

How to convert the borrowed value to owned values?
both tries of either modifying the test_enum in-place or returning a new test_enum will have the same lifetime as before and the compiler will complain.

        // Input
        let original_input = TestStruct { value: 2 };
        let mut test_enum: TestEnum;
        {
            // assign a value to the enum
            test_enum = TestEnum::Borrow {
                borrowed: &original_input,
            };

            //convert to enum with ownership
            test_enum.change_borrowed_to_owned();
            //test_enum = test_enum.change_borrowed_to_owned_v2();
        }

        // move the original input
        let moved_input = original_input;

        test_enum.print()

Is there a way to make the compiler understand that there is no borrow anymore?

Sidenotes:

  • This is just a toy-problem of what I actually want to achieve
  • In the actual Code, the TestEnum is embedded inside another enum
-    fn change_borrowed_to_owned_v2(&mut self) -> Self {
+    fn change_borrowed_to_owned_v2(&mut self) -> TestEnum<'static> {

Self is an alias to the type which includes the potentially short-lived lifetime, but you're trying to get rid of said lifetime. So don't use Self for the return type (or constructor).

7 Likes

Just in case: Cow in std::borrow - Rust

2 Likes

works - thanks for the input :slight_smile:

I'm somewhat confused by this solution -- my understanding is that lifetime is a part of the type, so in this declaration compiler infers 'some_lt:

let mut test_enum: TestEnum<'some_lt>;

But then when it's re-assigned:

test_enum = test_enum.change_borrowed_to_owned_v2();

It appears that the type of test_enum changes from TestEnum<'some_lt> to TestEnum<'static>.
I know this is not the case and the compiler shortens the lifetime, but this assignment somehow signals to the compiler that the &original_input borrow has ended.

Is it because the returned type has a different lifetime?

Yes.

Yes, change_borrowed_to_owned_v2 returns a TestEnum<'static> which then coerces to TestEnum<'some_lt>.

More precisely it's because 'static doesn't force 'this to stay alive here:

// (I gave this lifetime a name)
impl TestEnum<'this> {
    // renamed so it fits :-) -- fn change_borrowed_to_owned_v2(
    fn cbtov2(self: &mut TestEnum<'this>) -> TestEnum<'static> {
    //                            ^^^^^               ^^^^^^^

And in fact because of the ability to coerce, you could write it like so:[1]

impl TestEnum<'this> {
    fn cbtov2<'any>(self: &mut TestEnum<'this>) -> TestEnum<'any> {
    //                                  ^^^^^               ^^^^
    // Two unrelated lifetimes

There's no relationship between 'this and 'any here, so the compiler realizes the return can't be or contain the same borrows in Self. Whereas originally you said they were the same... and in fact, given that signature, they could have been the same (by returning a clone, say).

(Note that the API is the contract; the compiler intentionally borrow checks, etc., based on the function signature, and not the body.)


In contrast if we modify it again so that you could return something Self could coerce to...

    fn cbtov2<'any>(self: &mut TestEnum<'this>) -> TestEnum<'any> {
    where
        'this: 'any

...then in practice this is just a restrictive as returning 'this, even though it can technically return something with a lifetime strictly smaller than 'this ("a different lifetime"). The relationship ('this: 'any) still means that using the return value has to keep the 'this borrow alive, just like when you returned 'this specifically.

To break it down a little more: 'this: 'any means something like "If 'any is still valid, then 'this is too." Anywhere you use the return value, 'any has to be valid, so that means 'this has to be valid too, which then means the borrow associated with 'this has to still be active.

Without the bound, or when returning 'static, there is no relationship forcing 'this to stay active when the return value is used.


  1. we're just coercing inside the function body instead of outside (n.b. there's no practical benefit) ↩︎

1 Like

Hmm ... may I join?

I do not understand this part (comments by me):

    let original_input = TestStruct { value: 2 };
    
    // Let the type of this variable be TestEnum<'a>
    let mut test_enum: TestEnum;

    test_enum = TestEnum::Borrow {
        borrowed:
            // Let the type of this expression be &'b TestStruct
            &original_input,
            
            // By the definition of TestEnum (i.e. solely by the signature of its `Borrow` constructor,
            //   which I believe is something like 
            //      `fn TestEnum<'x>::Borrow{ borrowed: &'x TestStruct } -> TestEnum<'x>` )
            // it must be 'b == 'a (or at least 'b: 'a)
    };

    // How does the persence of this line change any of my reasoning?
    test_enum = test_enum.change_borrowed_to_owned_v2();

    // 'b must be inactive here for `original_input` to be moveable (i.e. unborrowed)
    let moved_input = original_input;

    // 'a must be still active here for `test_enum` to be usable
    test_enum.print()

Does the borrow checker somehow track that the new value for test_enum was obtained by coercion from something independent so that the original borrow can end?

And what are the lifetimes 'a (in the type of test_enum) and 'b (in the type of the borrow) that solve the borrow checker constraints?

And what are those constraints? (Those in my comments are obviously wrong as they are in contradiction and the program compiles)

And how does all of the above depend on the presence of the assignment?

(feel free to use any interpretation of lifetimes you like)

I mean ... I can somehow intuitively see why it works, but I would like to see some more formal reasoning.

Hmmm ... but if I change the assignment to this:

    *&mut test_enum = test_enum.change_borrowed_to_owned_v2();

the program no longer compiles.

So it seems to me that the compiler can change assignment into a new variable creation (that would explain it for me -- new variable, new type, new lifetime, old one can end). Is that so?

We have to get more into the mechanics of the borrow checker to fully explain it. The way the borrow checker works is roughly:

  • Lifetimes are calculated based on the use of values with lifetimes in their types, relationships based on their use, relationships from the environment, etc.

    • These lifetimes may have gaps which I'll return to below
  • Every borrow of any place[1] is associated with a type of borrow[2] and a lifetime. The duration of the borrow is also calculated, based on the lifetime and also on some uses

    • The borrow can be shorter than the lifetime due to things like a reference being overwritten or due to gaps in the lifetime
  • Every use of every place is checked against the active borrows at that point in the program, and if a borrow conflicts with the use, you get a borrow checker error

How can a lifetime have a gap? Data flow analysis which is extended from variable liveness to lifetimes in Rust, as described in the NLL RFC.[3]

Traditional compiler compute liveness based on variables, but we wish to compute liveness for lifetimes. We can extend a variable-based analysis to lifetimes by saying that a lifetime L is live at a point P if there is some variable p which is live at P, and L appears in the type of p.

Going back to the source code:

    // Let the type of this variable be TestEnum<'a>
    let mut test_enum: TestEnum = TestEnum::Borrow {
        borrowed:
            // Let the type of this expression be &'b TestStruct
            &original_input, // (5)
            // By the definition of TestEnum we have `'b: 'a`
    }; // (7)

    // Let's break up the use and assignment onto different lines.
    let tmp = test_enum.change_borrowed_to_owned_v2(); // (10)

    // `test_enum` is overwritten
    test_enum = tmp; // (13)

    let moved_input = original_input; // (15)

    test_enum.print() // (17)

'b is never directly used after its creation,[4] so everywhere it is alive is due to the 'b: 'a relationship. On line 10, 'a must be alive because test_enum is used. But after line 10, there are no uses of test_enum or anything else requiring 'a (or 'b) to be alive before test_enum is overwritten. So there can be a gap in the lifetimes after line 10.

'a and thus 'b have to be alive again by line 17,[5] but the borrow of original_input doesn't have to be. It can stop at the "gap" after line 10.

More from the NLL RFC

(What I've been calling "borrows", the RFC calls "loans". "Regions" is another term for Rust lifetimes, those '_ things.)

The set of in-scope loans at each point is found via a fixed-point dataflow computation. [...]
For a statement at point P in the graph, we define the “transfer function” – that is, which loans it brings into or out of scope – as follows:

  • any loans whose region does not include P are killed;
  • if this is a borrow statement, the corresponding loan is generated;
  • if this is an assignment lv = <rvalue>, then any loan for some path P of which lv is a prefix is killed.

Or in other words, borrows stop at lifetime gaps (and in some cases where references are overwritten).

https://rust-lang.github.io/rfcs/2094-nll.html#borrow-checker-phase-1-computing-loans-in-scope

Thus there is no conflict at line 15, as original_input has no active borrows there.


If change_borrowed_to_owned_v2 returns a type with the same lifetime as the input lifetime,[6] there is no gap and original_input is still borrowed on line 15.


The use of test_enum to create the place *&mut test_enum is keeping the lifetime alive. (*&mut test_enum and test_enum are two different "places" (MIR Lvalues).)

To summarize:

  • overwriting assignment can cause a variable to be dead,
  • which can cause a lifetime to be dead (have a gap),
  • which can allow a borrow to end even if the lifetime is alive elsewhere (after the gap)

  1. variable, field, dereference, ... ↩︎

  2. shared, exclusives ↩︎

  3. This link also has an example of a lifetime gap in addition to the below quote. ↩︎

  4. that is, the only value with 'b in its type is the temporary used in the construction of test_enum ↩︎

  5. with the next generation borrow checker, 'b won't have to be alive after the gap due to location sensitive lifetimes ↩︎

  6. or one that causes the input lifetime to stay alive ↩︎

1 Like

Thanks for the detailed analysis. Apparently I have to (re-)read the RFC.

One more question to confirm:

The compiler does not actually add a coercion from TestEnum<'static> to TestEnum<'a> (around lines 10 or 13) (that would just produce a value with the same lifetime as input), but merely adds a constraint ('static: 'a, which is trivially satisfied) so the borrow checker can see an assignment of value with different/independent lifetime. Is that correct?

It took multiple reads for it to really stick for me. There's still some dark corners.

Hmm well... it's sort of a philosophical or semantic matter I think. I mean, there's probably a concrete answer in terms of the compiler implementation, but I don't know what it is, and I can see either interpretation working.

Let's get rid of my temporary (which technically introduced an intermediate lifetime in the type of tmp):

//         `TestEnum<'static>` as per the signature
//          vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
test_emum = test_enum.change_borrowed_to_owned_v2();

You could say the value is coerced to TestEnum<'a> so that the assignment is possible, or you could say that a subtype requirement is "registered" with a 'static: 'a constraint (which is trivially met).[1] I'm not sure which is more technically accurate.

I see your point though: if the coercion happened wouldn't 'a still be alive, due to the existence of a TestEnum<'a> before the assignment? I think it could still be dead between the return of the TestEnum<'static> and the coercion to TestEnum<'a>.

But again I'm not sure which is more technically accurate (e.g. is there even a control flow "point" there?). I think I'd have to look at a raw MIR dump or something.[2]


  1. or even than there's an intermediate lifetime here too with a 'static constraint... ↩︎

  2. I don't have a ton of experience with that, but this has me excited. ↩︎

1 Like

Thanks again. And I thought it was a simple question :slight_smile: