The Swift standard library currently provides some buffer types: UnsafeBufferPointer and so on. Other than being well-typed about the elements they store, these types are essentially completely unsafe: not only do they not represent ownership of the underlying memory, they also don't provide any static information about the ownership of the values stored in that memory; in fact, there might not even be any values in that memory because it could be totally uninitialized (or partially uninitialized! there are no restrictions). The user is completely in charge of not letting the code run off into the Land of Undefined Behavior.
A lot of the recent ownership work in Swift (e.g. SE-0366, SE-0377 and SE-0390) has been partially in service of enabling the creation of high-performance safe buffer types. As part of that, I was recently talking with the folks leading that effort (@Andrew_Trick in particular), and these notes kind of fell out of that conversation. I've cleaned them a little bit in an effort to organize my thoughts; I thought they'd be useful to put somewhere public.
I put this in the Standard Library category because it's really about principles of design around certain ownership features, although several of those ownership features are yet to be added to the core language.
Background
Lifetime-restricted types
First, this conversation is focused on "non-allocated" buffers, where the type does not represent ownership of the memory for the buffer itself. To be safe, these buffer values have be lifetime-restricted: there's some sort of definable scope that they aren't allow to escape. This is a new general feature that will need to be introduced to Swift, corresponding roughly to what Rust calls a lifetime-qualified type ('a qualifiers). It's a key idea of lifetime-restricted types that you can derive new values from them with strictly tighter scopes, and then we can assume that those values can no longer be used when those tighter scopes are complete.
For example, if inout was a first-class type in Swift, it would be lifetime-restricted: you can only ever form inout bindings to a particular variable temporarily. Given an inout struct value, you can form an inout binding to a property of that struct, and it's important for exclusivity that you cannot access the original struct during this time; this is a nested lifetime restriction coupled with a use restriction from exclusivity. When that binding goes out of scope, there are no further uses of it, and you can safely access the original struct again. Lifetime-restricted types allow us to apply this kind of logic to types in general, which as we'll see is an important tool for very specific situations like these buffers.
The working name for these non-allocated buffer types is buffer views. Types that represent owned-allocation buffers are also interesting, but they're a little bit easier to handle in some ways because of how tracking the buffer ownership narrows the range of possible designs. We also expect that algorithms working with buffers will generally want to be written using unallocated buffers so that they don't needlessly restrict where the buffer memory comes from.
Value ownership
Second, across the entire language, we can identify five kinds of value ownership that are useful to consider here:
- uninitialized ownership represents that you've got access to some uninitialized memory and the right to use it for whatever purpose you'd like, as long as you leave it uninitialized when you're done. For example, if you allocate some memory, you naturally have uninitialized ownership of the contents of that memory: there are no values there at start, and when you go to deallocate it, there better not be any values left there or they'll be leaked. To be safe, uninitialized ownership needs to be exclusive because any effort to actually initialize and use part of the buffer needs to be exclusive.
- initializing ownership represents an obligation to initialize memory with a value. For example, a function has initializing ownership of its return value. To be safe, this must be exclusive because overlapping attempts to initialize the same memory necessarily have UB (and will massively complicate any attempt to manage the ownership of the resulting values).
- consuming ownership represents an obligation to consume a value, leaving the memory it's in uninitialized. For example, a function generally has consuming ownership of the contents of its local variables. To be safe, this must be exclusive because overlapping attempts to consume the same value necessarily have UB (unless the values are known to be trivial to destroy).
-
mutating ownership represents the opportunity to change a value. The memory can be temporarily left uninitialized, but it must be initialized again by the time that this ownership is given up. For example, a function has mutating ownership of its
inoutarguments; it can also acquire mutating ownership of a mutable stored property of a class or (if stored in mutable storage) a struct. To be safe, mutating ownership must be exclusive because overlapping accesses to the same memory necessarily have UB. - borrowing ownership represents the opportunity to use a value without changing it. The memory must be initialized when acquiring this ownership and cannot change in any way while having this ownership. For example, a function generally acquires only borrowing ownership of a stored property when it reads from it. Borrowing ownership has to be exclusive of any other kind of ownership, but multiple contexts can have borrowing ownership of the same value at once.
Several of these kinds of ownership are not normally exposed in Swift, which statically restricts the use of uninitialized memory in the interests of memory safety. However, a low-level buffer type pretty much has to expose them, because otherwise initialization would always need to be tied intimately to allocation.
Element status in buffer views
For buffer views to be safe, on top of enforcing lifetime restrictions on the buffer view value itself, we need to track two things about the elements:
- which elements of the buffer are initialized
- what ownership do we have of each initialized element
Now, we could have a single buffer view type that does this all dynamically. For example, we could have an operation that asks for mutating ownership of an element, and that operation could check some dynamic side-table to verify that the element is initialized and then do some dynamic exclusivity test to catch any overlapping attempts to the element. That would be pretty expensive, though: we'd have to actually allocate and initialize that side-table, as well as doing all of the dynamic bookkeeping for the exclusivity check. We'd really like both of those to be handled statically, and ideally they would be handled by the normal language rules and not require all sorts of type-specific logic in the compiler. To do that, we need the information we have about an individual buffer view to reliably inform us about the elements and, ultimately, guarantee that any operations on them following the appropriate ownership rules above.
Exclusivity of element operations
One of the most important pieces of that is exclusivity. The general ownership rules above tell us that most of the operations on elements need to be exclusive to be safe. In order to guarantee that without dynamic checks, we need a static precondition that these operations cannot be performed on the same element. The simple way to do that is to have those operations require exclusive access to a buffer view value and then prevent multiple usable buffer view values from referring to the same element simultaneously.
The first half of that means that all operations that initialize, mutate, or consume elements must be mutating or consuming operations on a buffer view. nonmutating methods on buffer views, or ordinary functions that borrow a buffer view as an argument, do not have exclusive access to the view and cannot be allowed to do these operations. This mostly means that the implementation needs to declare the primitive operations correctly as requiring the right kind of exclusivity; since the operations will probably be implemented with unsafe buffers behind the scenes, there won't be anything forcing this to be done properly, but it's vital for correctness.
The second half of that means we must be very careful to only create disjoint buffer views that these operations can be simultaneously performed on. For example, if we have an API that creates a slice of a mutable buffer view, we need to prevent use of the original buffer view for as long as that slice is usable. This could be done by making the API a mutating function that provides the slice to a callback and makes sure the slice is lifetime-restricted to the duration of that callback. Alternatively, we can allow the slice to be returned from a mutating method as long as we maintain enough structure to reflect its dependency on the original buffer view and maintain the read-write access to that view associated with the mutating method call for as long as the slice is usable. This latter idea comes with important caveats; see later in this post.
Initialization state
The simple way to handle the is-initialized bit is to make the initialization state a static precondition on a buffer type. That means that we at least need two different buffer view types, one for working with uninitialized buffers and one for working with initialized buffers.
The uninitialized buffer type will represent uninitialized ownership of the buffer, which means that it will be expected to leave the buffer fully uninitialized before its scope ends. So any operations on that type which create initialized sub-ranges will need to produce strictly lifetime-restricted buffer views for those ranges: we have to be done with them (and have destroyed all their elements) before we can be done with the original buffer. This type either needs to be non-copyable or we need to prevent any copies from being used simultaneously, which is essentially the same thing. It can have consuming operations, but only to produce new buffers that maintain the same uninitialized ownership of the elements, e.g. to split the buffer into non-overlapping slices.
If we want to make a safe version of APIs such as Array.init(unsafeUninitializedCapacity:initializingWith:), we will probably also want an initializing buffer view type that dynamically tracks the length of the initialized prefix. This would also need to be a non-copyable type, and unlike most of the other buffer view types, it can't support any consuming operations to slice it up — those would be incompatible with tracking the initialized prefix length and propagating it back to the original caller (e.g. Array.init).
Any other primary buffer view types would have a static precondition that all the elements in them are initialized.
Initialized views
There are two main ways we could design initialized buffer views. One would be to treat these views like simple aggregates of the elements:
- if we have consuming ownership of the view, we have consuming ownership of the elements
- if we have mutating ownership of the view, we have mutating ownership of the elements
- if we have borrowing ownership of the view, we have borrowing ownership of the elements
If we did that, we'd only need a single initialized buffer view type. However, this would pretty severely restrict how you could work with views, especially immutable views. For example, you wouldn't be able to write a parser that to maintained a var remainingData: BufferView<UInt8> variable during the parse: this variable would represent consuming ownership of the entire buffer, and therefore the right to arbitrarily write to any element. Usually we want such a parser to accept the restriction of working with immutable data.
The other option is to separate the ownership of elements from the ownership of buffer views. They can't be completely separated, because we still need to use value ownership in order to establish exclusivity for the exclusive operations on elements, as discussed above. But we can encode the ownership of elements into the buffer view type name, so that we can have a high level of ownership of a buffer view value without implying a higher level of ownership of the elements. That means we need at least three types for initialized buffer views: one for consuming ownership of the elements, one for mutating ownership, and one for borrowing ownership.
The consuming buffer view type must be a non-copyable type with a deinit that destroys all of the elements in the view. Elements can be individually consumed with a consuming or mutating operation, leaving behind a view (if applicable) that no longer includes those elements. Similarly, new consuming buffer views can be sliced off with a consuming or mutating operation as long as this always creates disjoint views. If there are clients that require elements to be random-access consumed, that would require a new type that dynamically tracks which elements have already been destroyed; that overhead shouldn't be forced on all clients. It can also have operations to create mutating or borrowing buffer views.
The mutating buffer view type is like the uninitialized buffer view type in that it either needs to be non-copyable or we need some sort of novel restriction that prevents the original buffer view value from being used while the derived one is available, which is essentially tantamount to being non-copyable. It can have slicing operations to split it into disjoint mutating views, as well as operations to create mutating or borrowing views.
The borrowing buffer view type can be copyable as long as copies have the same lifetime restriction as the original.
Caveats on deriving buffer views
There are two API designs for deriving buffer views. One of them provides the derived views to a callback, which is very clear about the value dependency and likely nestedness of lifetime restrictions, but also has significant compositional problems and can lead to a "pyramid of doom". The alternative is to return the derived views, but this is problematic because the return value may still be dependent on the base value, depending on the derivation operation:
- A borrowing buffer view can be copied, so it can also be sliced to create new borrowing buffer views without any limitations other than preserving the original lifetime restriction.
- The non-borrowing buffer views can be consumed to produce one or more new buffer views without leaving any dependency on the original. The new buffer views must have the same lifetime restriction as the original view and must maintain compatible ownership of its elements. For example, a consuming buffer view cannot be consumed to produce a mutating buffer view because the obligation to destroy the elements would be lost. It would be okay to consume a mutating buffer view to produce a non-mutating buffer view, though, as long as the caller is comfortable with this being irrevocable.
- Similarly, the non-borrowing buffer views can have
mutatingoperations that produce slices as long as those slices have the same lifetime restriction, maintain compatible ownership of any elements they contain, and are disjoint from the (modified) original view. - Otherwise, the produced views must be exclusive with the original view for as long as they're still being used. For example, there can be a borrowing operation on a mutating buffer view to produce a borrowing buffer view, but the borrow of the mutating buffer view needs to last as long as the resulting view is alive.
This last point would require new basic language support in Swift where we recognize that certain function calls can return values that depend on self (or some other argument) and so extend the duration of any accesses associated with that argument to cover some scope relating to the return value. It seems reasonable to me to align this with the general rules for l-value access, which are well-established and reasonably predictable (if sometimes a little subtle). That would imply that, e.g., dependent return values passed as call arguments would have a lifetime scope associated with the exact duration of that call, just like an inout argument would, and any storage access associated with producing that return value would be extended to cover that exact scope. If the return value is used to initialize a local variable, the accesses would cover the scope of that variable. But this would have some strong inherent limits around things like conditionally-evaluated expressions (e.g. in an autoclosure or the ternary operator ? :) and non-immediate initialization, and for predictability we would probably apply those restrictions broadly instead of trying to "make it work" for cases that could theoretically be supported. For example, you would not be able to write:
var buffer: BufferView<Int>
buffer = myMutableBuffer.immutableView
because in the general case we would not be able to extend the duration of the access to myMutableBuffer to cover the full scope of buffer. (Consider that this assignment could be within an if or that there could be a defer that uses buffer between these two statements.)