Non-lexical lifetimes based on liveness

[nikomatsakis]

To clarify motivation, will NLL allow all of these added foo writes?

It would.

[cramertj]

In the “Destructors” section you talk about how the rules for dropck remain unchanged. Am I correct in thinking that this is sufficient to ensure that there aren’t any breaking changes the behavior of RAII types such as Mutex or RwLock?

[Ixrec]

Are there any known examples of safe, correct code that this analysis would not accept? All the standard NLL examples I can think of seem like they’d pass this.

[nikomatsakis]

There would be no breaking changes in behavior around RAII, correct.

[nikomatsakis]

The intention is certainly to accept strictly more code than before, so anything that works today would continue to work. I’m not aware of any exceptions to that.

[nikomatsakis]

In the “Destructors” section you talk about how the rules for dropck remain unchanged.

That said, I should spend some time writing about dropck. In particular, I had hoped that drop would no longer be a special case at all, but that’s not really true, since the implicit drop is the one case where we (intentionally) allow references that are “out of scope” to be accessible (but only if there is no custom destructor to witness them). This is what lets you build up cycles in some cases.

[nikomatsakis]

To elaborate a bit more:

The idea of NLL is that it has no affect whatsoever on what happens at runtime. This is purely about what kinds of code the compiler will accept. But the “dynamic semantics” (i.e., what happens when you execute the program) remain unchanged.

[Ericson2314]

I like this plan a lot. It is indeed much simpler than all the single-exit and “continuous” stuff. I do generally prefer to design the language, and then think of inference algorithm, while this describes the inference algorithm but leaves the explicit-lifetimes-MIR language implicit, but whatever. This is closer to how the compiler will work in practice.

You can go farther, and give variables a distinct type at each point in the program, as in Ericson2314’s stateful MIR for Rust. But even then you must contend with invariance or you have the same sort of problems.

I do appreciate the shout-out :). Did you mean contravariance by any chance–which I did mention wanting, or is this a limitation I missed?

Oh, and you hint that during the sprint you talked about “type per statement” which sounds like my plan. I agree that, for the current goals, that and my plan are vast overkill, but I am curious now what the sprint plan looked like.

[dobenour]

Would this use MIR borrowck?

[tzakharko]

I am very exited about this discussion. Lifetimes based on lexical scopes were a major frustration for me and ultimately the main reason why I didn’t adopt Rust for my current project even though I really like the language. Specifically, I am looking to solve a following puzzle. I have a non-trivial data structure (in following DS) that uses custom indices to manipulate it. The index is not a machine pointer, but can be a fairly intricate combination of references to the internal state of the DS (e.g. offsets into internal tables + state flags etc.). Furthermore, indices potentially become invalid once the DS is mutated. Therefore, in order to have a safe implementation of the DS, we’d ideally want to throw compile-time errors if any of the indices are alive when the host structure is mutated.

I attempted to achieve this in Rust using lifetime parameters. When an index is created, it is bound to the lifetime of the DS, resulting in implicit immutable borrow (no actual reference is created, which is again desirable). While this ensures that I can’t mutate the DS before all the indices go out of scope, it also makes the indices fairly useless as there is no apparent way to consume them. Specifically, I’d like to do something like this:

collection.consume(index0)

or

collection.join(index0, index1)

where the signature of the methods is something like:

fn consume<'a, 'b: 'a>(&'b mut self, index0: Index<'a>)
fn join<'a, 'b, 'c: 'a+'b>(&'c mut self, index0: Index<'a>, index1: Index<'b>) // how do you even state that 
                                                                               // 'c outlives both 'a and 'b?

The intuition here is that while indices do borrow the collection, they can’t outlive the method call (as the index is moved). Furthermore within the mutation method, they get destructured into the implementation-dependent internal state before the collection is actually mutated. Therefore, I would consider this pattern “safe” — there is no way that the mutable borrow of self will interfere with the implicit immutable borrow within the index. In another words, since the collection technically owns the index (the later cannot exist outside the particular collection state), it is safe for the collection to consume it. However, I don’t see any way of implementing this in current Rust — the compiler of course complains about the mutable borrow of self while there is still an outstanding implicit immutable borrow by the index.

Now, I have to admit that I haven’t fully understood the approach to NLL suggested by Nicholas in his post. I’ll certainly spend some time looking at it, but just to satisfy my curiosity: will this approach allow one to implement patterns like the above?

[dobenour]

I think that you can do this using interior mutability, or by using the RefCell type in the standard library.

[JanKanis]

It sounds like your indexes are somewhat analogous to slices. Looking at the source, Rust uses some unsafe code in its implementation and it has direct compiler support (as it has dedicated syntax). But in essence a slice can be built from just an array reference, a start offset and a length. For a mutable slice the array reference would be mutable, for a shared slice the array reference would be shared. Could an analogous construction work for you?

[tzakharko]

If I see it correctly, the most significant difference between Rust slices and my indices is that the slice can be used independently to access the borrowed data, while my indices are only bundles of state that can only be interpreted by their owner object. Actually, it the indices themselves can be implemented easily — its the invariant part (no index can outlive owner object mutation) that is tricky. I could of course try changing the API so that the object is manipulated directly through indices (even though I really dislike the idea), but then I still will have to deal with the issue of multiple mutable borrows… and of course, the entire thing should be super-lightweight for performance reasons.

[JanKanis]

If you’re willing to change the api you could have a structure that contains a mutable reference and your existing index structure, that should be as lightweight as passing a reference and the index around separately. The main drawback would be that now your index also is either mutable or immutable, and you won’t be able to have multiple mutable indexes at the same time.

If you don’t want to change the api you could still resort to runtime checks or to unsafe code to do what you want, but I’m not sure if your usage would be safe. (If an index is akin to a shared reference, then when there is one reference out there there can be N as well. If you consume one using unsafe code the compiler won’t prevent the other ones from staying alive. To get around that the index would have to be unique, which can be done by incorporating a mutable reference in it. But then you couldn’t have two indexes to pass to your join method.)

[krdln]

I think what you want is to be able to express a function signature that takes an immutable borrow (index) and a mutable borrow (self) with a promise it won’t start using the mutable borrow before it stops using the immutable one. From what I know, the NLL will change only how the bodies of function work, the meaning of function signatures will remain unchanged. The extension to function signatures that you want might be possible when the proposed two-stage borrows would get exposed in the typesystem, alghough I’m not sure about it. Also exposing two-stage borrows would increase the complexity of the language significantly.

The current solution to such safe indexes is to use closure to generate the fresh lifetime for indices. Check out the indexing crate and the @Gankro’s playground.

But from what I understand, these solutions don’t allow a mutable method to consume multiple independent indexes. I think that a good workaround for these would be for the closure to return an operation – playground prototype. Note that I’m certainly not an expert wrt. variance etc. so my code may not be sound.

[tzakharko]

I think what you want is to be able to express a function signature that takes an immutable borrow (index) and a mutable borrow (self) with a promise it won’t start using the mutable borrow before it stops using the immutable one.

Yes, thats exactly what I would like to do! Your wording is much better Thanks also for the links to the code, its very interesting — I’ll play around with it, and maybe get inspired.

After reading the blog post few more times I believe that you are right, and that the analysis of the lifetime seems to stop at the method boundary (in theory, it doesn’t have to, but that would call for a more complex graph analysis). However, if I understand it correctly, the current proposal should allow for destructuring the index in the function signature, e.g.:

fn consume<'a, 'b: 'a>(&'b mut self, (internal_index:UnsafeIndex, _): Index<'a>)

The idea here is that index is dropped (and the associated lifetime/phantom borrow is released) before the method is called. The ‘safe’ index could then be encoded as a tuple of an ‘unsafe’ index + a marker.

[djc]

Maybe related, would it make sense to also enable idiom like if let Some(x) = y && x? That is, bring matched values in scope of further parts of the condition?

[cuviper]

That will be parsed like if let Some(x) = (y && x). There would have to be some way to group the left side that you intend, like if (let Some(x) = y) && x, which looks strange. That would mean something like "let in expression context returns a bool"? Might be neat to generalize if-let and while-let.

[tom.prince]

That looks very much like using pattern guards. There is an open RFC issue for it.

[nikomatsakis]

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