I have some further thoughts on reborrowing in case you find them useful, but I don't want to unnecessarily clutter this thread, or create a new thread if doing so is unnecessary. Feel free to move this if you think a new thread is warranted.
Some further thoughts on reborrowing
Interactions with component lifetimes
If/when component lifetimes are added to Swift, we can consider each value to have a list of component lifetimes, where the number of component lifetimes is determined by the value's type.[1] Then, the lifetime of a value is the greatest lower bound[2] of its component lifetimes.[3]
If a value is reborrowable, but not copyable, then the compiler needs to ensure that a "copy" has a scoped mutating lifetime dependency on the original value, which requires at least one of the copy's component lifetimes to be bound to a mutating access of the original value. The compiler could bind all of the copy's component lifetimes to the mutating access, but that would be a conservative approximation. Each component lifetime represents temporary access to some resource, and that access can either be shared or exclusive. If it is exclusive, then to prevent the resource from being simultaneously accessed, the compiler needs to bind the component lifetime to a mutating access of the original value. But if it is shared, then the compiler can just copy the component lifetime instead.
For user-defined reborrowable types to express that kind of nuance, there would need to be a way to specify which component lifetimes are copied, and which component lifetimes are bound to a mutating access, when a value is reborrowed.[4]
Non-orthogonality of Copyable, Escapable, and "reborrowable"
We can think of Copyable, Escapable, and "reborrowable" in terms of component lifetimes:
If a type is "reborrowable", then its values can be copied, and each component lifetime is either copied or bound to a mutating access.
If a type is Copyable, then its values can be copied, and each component lifetime is copied.
If a type is Escapable, then its values have no component lifetimes.
If the first and third conditions are true, then the second condition is also vacuously true. So if a type is "reborrowable" and Escapable, it is also effectively Copyable. The type system can't express that kind of relationship between protocols, so if we add a "reborrowable" protocol, then without changing the type system (or special casing these specific protocols), it would be possible for a type to be effectively copyable without actually conforming to Copyable.
Reference counting overhead
If a copyable type contains an object reference, then copying or destroying a value of that type requires reference counting. Because borrowing and consuming specifiers are not semantically meaningful for copyable types, it is always possible to use those specifiers to precisely control reference counting overhead without affecting semantics. If we allow users to define their own reborrowable types, then it would be possible for reborrowing to also require reference counting. But borrowing, consuming, and mutating/inout specifiers each have different semantics for reborrowable types, so they cannot be used in the same way.
We could just require users to define both mutating/inout and consuming versions of their functions if they need precise control of reference counting overhead for a reborrowable value. Alternatively, if this issue is important enough to warrant a language-level solution, we could allow functions to be generic over mutating/inout and consuming ownership of a reborrowable value.
Those approaches are both a bit convoluted, so finally, another solution would be to define a new ownership mode that means "the value's exclusive accesses are consumed, but its copyable components are borrowed". But that would complicate the ownership system, defeating (part of) the purpose of introducing reborrowing in the first place.
If component lifetime specifications can be recursive, analogous to recursive constraints on associated types, then the number of component lifetimes could be infinite. For example, a linked list node would have the component lifetimes self.next, self.next.next, and so on. ↩︎
Assuming that "greater than" means "outlives"/"longer than". Rust terminology is the opposite, because lifetime relationships are interpreted as subtyping, so "less than" is taken to mean "subtype" which means "outlives"/"longer than". ↩︎
For the compiler to actually derive the lifetime of a value from its component lifetimes like that, it would need to exhaustively enumerate each component lifetime, making it impossible for libraries to add new component lifetimes to existing types. Regardless, the compiler would always at least know that each component lifetime is greater than the lifetime of the value itself. ↩︎
The Rust proposal also discusses this, but it's complicated by the fact that lifetimes are part of types in Rust, and that they're proposing this to be inferred like lifetime variance is. ↩︎
I'm happy to keep using this thread until I'm ready to pitch the new approach.
A few of us have tossed around what this might look like, and our thoughts aren't that different from yours, although some of the conclusions are a little different. I think we do have to think of a re-borrow as being effectively a copy. What we have, then, is a type that semantically permits multiple copies to exist as long as they are guaranteed to be used exclusively with each other. That's a potentially broad class of types, although the fact that destruction has to be coordinated somehow does limit its usefulness.[1] Perhaps this could be an ExclusiveCopyable marker protocol, sitting between ~Copyable and Copyable.
Enforcing this restriction doesn't technically require the type to be ~Escapable: we can enforce it locally as long as the copies remain local. However, that seems pretty pointless, because the programmer might as well just have one local value; therefore, we might as well require non-escapability. Once we're doing that, we can just require the type to originate a lifetime restriction that we can limit. We don't need to, or even want to, restrict all component lifetimes, though.
Since re-borrows are copies, yes, we have to think about when we copy the component values. borrowing, mutating, and consuming are all still useful here, but we do run into the problem that making the exclusive operations consuming would imply that they all do a primitive value copy. That leads me back to thinking we still need an exclusive access specifier in the long term. In the short term, since the types we immediately care about all look like MutableSpan (i.e. small types with trivial components), there's no harm in just using consuming. Specifically, since ExclusiveCopyable + consuming would let us eanble the desired use patterns for MutableSpan, we should clearly do that first and then only consider exclusive ownership later if there's a demand for it.
MutableSpan et al. also have the characteristic that we should probably default to passing them around with consuming or exclusive ownership. That is probably not generally true of all ExclusiveCopyable types, though, so if we want to add such a rule, we should do so separately.
Maybe if we had a "copy constructor" that could make destruction dynamically a no-op for nested copies? ↩︎
Would the ability to yield from a function (func f() -> borrowing T or something) help things at all? I know it's not exactly what you're getting at in this pitch, but would it solve a subset of the problems you're looking at here?
I never considered that kind of strategy, where "owning" values have a different representation from "reborrowing" values. It would also be useful for "call-exclusively" function types, if those are ever added to Swift.
It could lead to difficulties in some cases, though, if we decide those cases are important enough to handle. Specifically, it relies on the semantic model, which I've assumed throughout this thread, that any consuming use of a reborrowable value can always be classified as one of two cases:
The original value won't be used again. Then the consuming use is a move of the original value, which is invalidated permanently.
The original value will be used again. Then the consuming use forms a copy of the original value that's bound to a mutating access of the original value, which is only invalidated for the lifetime of the mutating access.
That semantic model doesn't work if it isn't known ahead of time whether or not the original value will be used again. At best, the compiler can consider whether or not the original value might be used again, as a conservative approximation, which will lead it to reject some provably correct code. Consider the following example:
@lifetime(copy original)
func f(_ original: consuming MutableSpan<Int>) -> MutableSpan<Int> {
var copied = original
if someCondition() {
return copied
} else {
return original
}
}
Equivalent Rust code
fn f(original: &mut [i32]) -> &mut [i32] {
// The type annotation is necessary because Rust inserts
// reborrowing operations before type inference.
let copied: &mut [i32] = original;
if some_condition() {
return copied;
} else {
return original;
}
}
The first line can either move original or copy it. If someCondition() is true, then original should be moved, so that the lifetime of copied can extend past the function call. Otherwise, original should be copied, so that it can be returned later. The code is provably correct, because in each individual control flow path, original and copied are never used simultaneously. The equivalent Rust code is rejected by Rust's current borrow checker, but is accepted by Polonius, an ongoing rewrite of the borrow checker that can reason about lifetime dependencies being flow-sensitive.
To allow code like the above to work, we would need to replace the old semantic model with a new semantic model. In the new semantic model, copies happen on every consuming use of a reborrowable value, except for optimizations. A copy of a reborrowable value is "mutually exclusive with" the original value, meaning that the original value is invalidated while the copy is alive, and if the original value won't be used again in any control flow path starting from the current point, then the copy's lifetime can extend to (a copy of) the original's lifetime. Importantly, it would no longer be possible in general to know which value will outlive the other value ahead of time, making it impossible for the "copy constructor" to designate one as the "owning" value.
Even if the original value won't be used again, it still needs to be destroyed. So instead of being completely invalidated, we can say that the original value is put in a "dangling" state, meaning that its component lifetimes (at least those representing an exclusive access) are invalidated, temporarily or permanently. The compiler would then need to make sure it's safe to destroy a "dangling" value, which is true for trivially destructible types, and true for types that only require reference counting, but would need extra rules if we ever allow copyable and reborrowable types to have user-defined destructors like in C++.[1]
The notion of a "dangling" state is also useful in situations where a set of values needs to be destroyed all at once (such as if they're allocated in an arena), and the values might have circular references to each other. The values would need to be put in the "dangling" state before being destroyed, to make sure they don't access other values that have already been destroyed.
Rust has an unstable (roughly equivalent to being underscored in Swift) feature called the "drop check eyepatch" or "dropck eyepatch", which, to simplify a bit, allows a type with a user-defined destructor to indicate that its values are safe to destroy when they (and the values they own) are put in some "dangling" state.[2] This makes it possible to e.g. form circular references between trivially-destructible elements of a Vec, as long as the Vec isn't later mutated prior to being destroyed.[3] The compiler can't check that a destructor is actually safe to call on a "dangling" value, because the notion of a "dangling" state doesn't exist in Rust's type system, so the "dropck eyepatch" is completely unsafe.
It's possible to do better at the cost of making the type system more complex. Personally, I think Swift's philosophy of progressive disclosure is well-suited for that kind of complexity.[4] In the future, we could allow user-defined reborrowable types to guarantee that their copy operation puts the original value in the "dangling" state instead of completely invalidating it, or require that to be the case for all reborrowable types.[5] In the short term, we could just special case the reborrowable types in the standard library as having that property.
Another motivation for making reborrowable parameters implicitly consuming is that it'd sidestep the question of whether an explicit consuming specifier should suppress implicit copies for ExclusiveCopyable types, like it does for Copyable types.
Given that Copyable would inherit from ExclusiveCopyable, the answer to that question is probably yes from a subtyping perspective (that is, adding a Copyable conformance to an ExclusiveCopyable type wouldn't be a breaking change). But if we do that, and also require the consuming specifier to be explicit, then we'd largely undermine the ergonomic benefits of ExclusiveCopyable that we wanted in the first place.
Perhaps the crux of the issue is that, for copyable types, borrowing and consuming specifiers could only ever be used for performance reasons, so it made sense for those parameters to "act like" move-only types. But adding a third kind of type to the mix makes it possible for those parameters to "act like" reborrowable types instead.
In the short term, to sidestep the question just for MutableSpan, we could just special case MutableSpan parameters as always implicitly copyable, perhaps alongside other types that are small and bitwise-copyable like Int.
Something else to consider, I think, is that we'd presumably allow values stored in let constants to be "reborrowed" (and presumably, without the & symbol), which introduces the novel ability to form a mutating access to a let constant (and without the & symbol). It makes sense to question whether this ability should be strictly tied to the concept of "reborrowing", or to what extent they are orthogonal.
It makes sense to allow a mutating access to a let constant (and without the & symbol) if that access isn't "value-changing", although I think the concept of "value" here is probably more of a subjective notion than something that can be precisely defined.[6] Perhaps there are two questions to consider then. First, does it ever make sense for a "reborrow" to be "value-changing"? Second, does it ever make sense for a mutating access that's not a "reborrow" to not be "value-changing"?
For the first question, I think the answer is probably no. Copies are supposed to be independent in some sense (even if, for reborrowable types, that sense isn't lifetime-independence), and it'd be confusing if doing anything to a copy can change the "value" of the original. The types we're considering so far seem to line up with that intuition: MutableSpan and InOut seem to be "reference-like", and so would something like MutatingFileDescriptor. More abstractly, we can argue that, because a reborrowable value can't destroy its underlying resource, and the resource will still exist after the value is gone, the value is just a "reference" to the resource, not the resource itself.[7] Arguably, the fact that changes to the resource will persist after the value itself is destroyed creates a kind of non-locality that we associate with "reference semantics".
For the second question, from a little bit of personal experience, I think the answer is probably yes. In Rust, when I needed to mutate the inner value within a Mutex, my first thought was to store a MutexGuard in an immutable local variable. Intuitively, mutating the inner value isn't a "value-changing" operation on the MutexGuard itself, because MutexGuard is "like &mut" (and the language does have a special case for immutable local variables of type &mut). This is despite the fact that MutexGuard, whose destructor unlocks the mutex, wouldn't be reborrowable if Rust made that possible for user-defined types. What MutexGuarddoes have in common with reborrowable types, though, is non-locality, because changes to the inner value will persist in the Mutex even after the MutexGuard is destroyed. Arguably, this kind of non-locality is what makes it sensible to perform "exclusive" operations on temporary values, unlike the mutating operations on types with "value semantics".[8]
We could consider adding some kind of @notReallyMutating annotation to mark certain mutating operations as not "value-changing" and make them applicable to let constants. A downside, though, is that @notReallyMutating mutating would be really close to a new ownership mode like exclusive anyway.[9] Another downside is that API authors would need to decide when to make their mutating operations @notReallyMutating, based on the subjective notion of "value". Perhaps a litmus test for making a mutating operation @notReallyMutating/exclusive could be "if this type were copyable or reborrowable, would performing this operation on a value be equivalent to performing one on its copy?" If so, then maybe exclusive is the way to go after all, so the compiler can make sure it's impossible for the answer to that question to be no (and arguably, the non-locality property requires non-inline storage).
A remaining question, for both exclusive and @notReallyMutating, is how they'd propagate through property and subscript accesses, if at all. Given that Swift already has a large number of accessor kinds, it might not be worth it to add more just to account for all the edge cases of what is ultimately an ergonomic convenience.
Interestingly, the compiler would always know whether or not a value is in the "dangling" state at the time of its destruction. So to make things like "call-exclusively" function types work without resorting to reference counting, perhaps it can pass a flag to the destructor indicating whether or not the underlying resources need to be destroyed? Or equivalently, perhaps there can be two destructors? ↩︎
It's more complicated because each type with a user-defined destructor can choose which of its component lifetimes are allowed to be invalid while it's in the "dangling" state, including which of its type parameters are allowed to have invalid component lifetimes. (Note that we can talk about types themselves being in the "dangling" state, because in Rust, component lifetimes are embedded in types. Also note that the attribute marking a component lifetime or type parameter is spelled #[may_dangle], but it uses the word "dangle" to mean what I call "invalid", not what I call the "dangling" state.)
It's also more complicated because there is a convoluted algorithm that recursively traverses through the fields of each type definition, whose purpose in this context is to infer which type parameters that were marked as allowed to be invalid are actually required to at least be in the "dangling" state, not completely invalid. The algorithm's subtlety and difficulty to understand has been the cause of a few soundness bugs in Rust's standard library (12), and likely in user code that uses the "dropck eyepatch". As a result, there is a proposal to simplify the algorithm by requiring each type parameter to be explicitly marked as either allowed to be completely invalid or allowed to be in the "dangling" state, instead of making that distinction inferred. ↩︎
The reason the Vec itself needs to have a "dangling" state is because the elements' references to each other are bound to a borrowing access of the Vec, so notionally, each circular reference to an element is actually a circular reference to the Vec itself. More generally, if I'm not mistaken, in a Rust-like ownership system, we can model any (non-reference counted) circular reference as a back-edge from a value to (an access of) something that owns the value. A circular reference is always aliased, so the access of the owning value cannot be mutating. (The only exceptions in Rust are some edge cases related to the Pin type that break Rust's normal aliasing guarantees, which are currently a murky area. The UnsafePinned proposal provides some context to that topic.) ↩︎
I also think the added complexity would be offset by the simplicity, both for users and for describing how the feature works, of not having the convoluted algorithm used by the "dropck eyepatch". ↩︎
More precisely, that each component lifetime representing an exclusive access is also allowed to be invalid in the "dangling" state. ↩︎
Arguably, this concept of "value" is at least somewhat orthogonal to inline storage. For example, an Atomic instance's inline storage can be changed without changing the instance's "value". We can think of Atomic as having "reference semantics", where the "value" of an Atomic instance is its identity, and the storage of its inner atomic value is an implementation detail. ↩︎
I suppose this is somewhat complicated by how these types will implement Equatable. For example, if a and b are two let constants of type MutableSpan or InOut, it'd be weird if the result of a == b could change over time. But that kind of thing is already possible with types like NSMutableArray that have "reference semantics". ↩︎
Arguably, this kind of non-locality is actually orthogonal to exclusivity. For example, the atomic write operations of Atomic lack this kind of non-locality despite being non-exclusive, so they shouldn't be applicable to temporary values. Hypothetically, we could address this nuance with something like C++'s ref-qualifiers that are orthogonal to const-qualification. ↩︎
The most important difference being that it'd always be possible to wrap a mutating operation in a @notReallyMutating mutating operation, making them equivalent except for syntax. ↩︎
I figured as much. Thanks for confirming. I'll go back to my hidey-hole now!