Hi Swift Evolution,
For the past few weeks I've been testing out the new generic non-copyable features, by trying to create non-copyable data structures. At the same time, these features are being proposed and reviewed through the Swift evolution process.
Non-copyable generics aren't for every-day code – but we've put a lot of care into making them stay out of your way until you need them, and then keeping them usable once you do. They will allow libraries to unlock more performance and safety for end users.
The first of those proposals, SE-0427, generated a lot of great discussion. But it also showed there can be some confusion around how it works, and what things like ~Copyable
actually mean.
I've found the best way to understand this feature is to play around with it. That has been difficult until recently because not all the necessary pieces were available in a nightly toolchain. In particular the ability to create pointers and optionals of non-copyable types. But that changed when @lorentey landed support support for these last week. At the same time, some of the other proposals that are coming out are a little more obscure than the basic generics support, and so haven't had as much discussion. These are also much easier to understand once you actually try and use them all together, and see the impact of not having them.
To help tie all these pieces together, I wrote up some code that uses all these proposals in order to build a basic singly-linked list type. This code is similar to the code you can find in chapter 2 of @Gankra's excellent tutorial about linked lists in Rust, which I encourage you to read to get a better feel for how it handles ownership.[1]
To compile these examples you will need a recent main
toolchain from swift.org, and to use three -enable-experimental-feature
flags: NoncopyableGenerics
, MoveOnlyPartialConsumption
, and BorrowingSwitch
. To do this in Xcode, add them to the Other Swift Flags project setting[2]. To use them in a SwiftPM project, use .experimentalFeature("NoncopyableGenerics")
.
Because of a bug I found while putting this post together, you will also need to add the flag -disable-round-trip-debug-types
. Hopefully that one won't be around much longer.[3] Also bear in mind, when you grab the nightly toolchain from main
you are using a compiler that is in development. You should expect to find bugs. We want you to find bugs! That compiler also has assertions enabled – that means, there are tests inside the compiler that might fail when you give it interesting new code. When those tests fail, you get a stack dump back from swiftc
. Please don't be alarmed – that debug output just helps a compiler engineer figure out what went wrong. Posting those to bug reports, along with a minimal reproducer, is very helpful. Thank you!
OK let's get started. If you want to follow along, you can type in yourself as you go, but you can also find the final code here.
A basic Box
type
To build a linked list, we first need some indirection[4]. So we create a box type:
struct Box<Wrapped: ~Copyable>: ~Copyable {
private let pointer: UnsafeMutablePointer<Wrapped>
init(_ wrapped: consuming Wrapped) {
pointer = .allocate(capacity: 1)
pointer.initialize(to: wrapped)
}
deinit {
pointer.deinitialize(count: 1)
pointer.deallocate()
}
consuming func move() -> Wrapped {
let wrapped = pointer.move()
pointer.deallocate()
discard self
return wrapped
}
}
This simple type demonstrates many features of non copyable types, both existing and newly introduced:
- This is a struct that opts out of the default
Copyable
conformance via: ~Copyable
. This allows it to have adeinit
, like a class. This type uses no reference counting to know when to destroy the box. The type cannot be copied, so when it goes out of scope, thedeinit
is called by the compiler. - To get the indirection, this type uses an
UnsafeMutablePointer
but it keeps that unsafety private. Ultimately, a type like this might belong in the standard library to allow users to achieve this without using any unsafety themselves. - Its API only exposes 3 things: put something in the box, destroy the box automatically, and move the thing out of the box. That last operation also destroys the box. The
discard self
tells the compiler “I have destroyed this box manually, you don’t need to do call thedeinit
method.” - There are two uses of the
consuming
keyword:- The
init
takes its parameterconsuming
. If you put a non-copyable type into the box, it is consumed and you don’t have it any more. If you were to put a copyable type into it, you could still use it at the cost of the compiler making a copy. - The
move
operation isconsuming
. This means when you call this method on a box, that box is consumed and you cannot use it any more (which is good, because that method frees the memory and returns the wrapped value to you, so it would segfault if you tried to read it afterwards).
- The
- NEW The generic placeholder
Wrapped
, which can stand in for the type of anything you want to put in the box, is also marked~Copyable
. This means that theBox
type cannot make any copies of its wrapped type.- This is where we need our first experimental feature,
-enable-experimental-feature NoncopyableGenerics
- Important detail: this does not mean that the box can only hold non-copyable types. It can hold ints and strings just fine. What this
~Copyable
annotation means is just that theBox
type doesn’t know if the type it holds is copyable, which means it can safely hold both copyable and non-copyable types. - NEW The recent toolchains from
main
declareUnsafeMutablePointer<Pointee: ~Copyable>
, which is how come this code can putWrapped
inside one.
- This is where we need our first experimental feature,
We can now see this in action, including things the compiler will stop us doing to ensure that the noncopyability of the box type is preserved[5]:
let intbox = Box(1)
let boxbox = Box(intbox) // intbox moved, but not destroyed
// let i = intbox.move() // forbidden: 'intbox' consumed more than once
let intbox2 = boxbox.move() // allowed
// boxbox destroyed and deallocates its pointer
// let intbox3 = boxbox.move() // forbidden: 'boxbox' consumed more than once
let i = intbox2.move() // allowed
// intbox2 goes out of scope and deallocates its pointer
You might be surprised to see that you can call a consuming
method on a let
variable (boxbox.move()
). Consuming methods are not like mutation. You are giving away the value, and as such, it doesn't matter that it is immutable.
We can also give Box
methods when the type is copyable. Because copyability is the default, we can just not specify that the wrapped type isn't copyable, by leaving off the ~Copyable
:
extension Box {
var wrapped: Wrapped { pointer.pointee }
}
This computed property returns a copy of the boxed value. This is obviously only possible when the box holds a copyable type (say an Int
or a String
).
The List
type
Now that we have this, we can use it to create a very basic singly-linked list:
struct List<Element: ~Copyable>: ~Copyable {
struct Node: ~Copyable {
var element: Element
var next: Link
}
typealias Link = Box<Node>?
var head: Link = nil
}
This is very similar to the Box
type:
- Like
Box
,List
uses no reference counting. When it goes out of scope, it will destroy all its links. Unlike withBox
, it does not need an explicitdeinit
to do this, similar to how a struct that holds a class doesn't need a deinit.[6] - The
List
supresses its own ability to be copied via: ~Copyable
. Note that it must do this, because it contains a non-copyable type (an optional box). If you forgot to add this, the compiler will tell you:Stored property
head
ofCopyable
-conforming generic structList
has non-Copyable typeList<Element>.Link
(akaOptional<Box<List<Element>.Node>>
) - Like
Box
, the copyability of the generic placeholderElement
is also supressed, so this type can safely hold both copyable and non-copyable types. - Like with
UnsafeMutablePointer
, the standard library'sOptional
type now supports holding non-copyable types.
Pushing and popping
OK now we have our list, let's put stuff in it:
extension List where Element: ~Copyable {
mutating func push(_ element: consuming Element) {
self = List(head: Box(Node(element: element, next: self.head)))
}
}
This code replaces the head of the list with a new box containing the pushed element, and then a link to the previous head (which might be nil
, if the list was empty). Note that just like our box init, element
must be taken as consuming
because this might be a non-copyable type, and we want to store it. Unsurprisingly this is a mutating operation. And you don't have to explicitly create an optional of the box – just like always, the compiler will do this for you.
You might find two things slightly odd about this code:
-
The extension restates that
Element: ~Copyable
. Without this,Element
is assumed to be copyable – that original supression of the type's copyability isn't carried forward from the declaration of the type. We already saw this in action earlier, on theBox.wrapped
getter.
This is important for two reasons:- Source compatability. Types in the standard library have adopted
~Copyable
on their generic placholders. There is a lot of code out there that assumes that, when you extendOptional
, you can make a copy of the wrapped type. We cannot break this code. - But even if we were willing to (perhaps under a language version like Swift 6), this would be the wrong thing to do. Non-copyable generics are an advanced feature, and we don't want to force them on folks who want to do something as simple as put a helper method on optional. For this reason, you must always opt in to supporting non-copyable types.
- Source compatability. Types in the standard library have adopted
-
The code fully reinitializes
self
. It doesn't just updatehead
to the new link. Let's say you tried to assign tohead
instead:head = Box(Node(element: element, next: head))
You would get an error:
Cannot partially reinitialize
self
after it has been consumed; only full reinitialization is allowed.The cause is this code:
next: self.head
. We are passingself.head
into a consuming initializer. But we didn't pass all ofself
. Just one of its properties. After this,self
is in an unusual state – it has a kind of "hole" wherehead
used to be. This is called "partial consumption".- Enabling this requires the
-enable-experimental-feature MoveOnlyPartialConsumption
. Without this, you will get the error "Cannot partially consumeself
". This feature is currently in review and has the grand total of 1 review comment. I am not surprised – you really cannot understand this feature without using it, which is what prompted me to write this post. - In theory the compiler could see that this "hole" is created, but then filled, before the function exits. So it is possible some of these restrictions can be loosened with further analysis on the part of the compiler in future. But for now, you must do this full reinitialization.
- Enabling this requires the
Next let's get the elements back out:
extension List where Element: ~Copyable {
mutating func pop() -> Element? {
switch head?.move() {
case nil:
self = .init()
return nil
case let node?:
self = List(head: node.next)
return node.element
}
}
}
A lot of recurring themes here:
- We have to restate that we want this code to work with non-copyable elements. Yes, this gets annoying – the choice here is to annoy advanced users slightly to keep Swift approachable for everyday use. In practice, we'd probably just put both
push
andpop
under the same extension. - We're leaning heavily on non-copyable support in
Optional
, and can see that even the regular sugar in pattern matching works and optional chaining works as we'd hope. - We partially consume
self
into the switch. Thenode
variable is also partially consumed, in two parts. We put thenext
intohead
, and return theelement
to the caller. - Because the switch (partially) consumes
self
, it must be reinitialized on all paths, even when head turned out to benil
and so no "hole" existed. Again, perhaps more clever analysis by the compiler in future could allow some of this boilerplate to be omitted.
And now we have a fully functional linked list. To give it a whirl:
var list: List<String> = .init()
list.push("one")
list.push("two")
var listlist: List<List<String>> = .init()
listlist.push(list)
// list.push("three") // now forbidden, list was consumed
list = listlist.pop()! // but if we move it back out...
list.push("three") // this is allowed again
while let element = list.pop() {
print(element, terminator: ", ")
}
// prints "three, two, one,"
Supporting Iteration
Finally, let's try adding iteration support to our list. Here, things start to get a little fiddly – mainly because there are more language features needed to support this use case ergnomically:
Sequence
, and thereforefor...in
, does not yet support non-copyable types.Sequence
could be made to support it today by marking the protocol up as~Copyable
and havingmakeIterator()
be consuming. However this is probably not desirable. Mostly, you want iteration to be a borrowing operation. Accomplishing this needs more language features.- So for now, we're going to do this via adding a
forEach
method to the list. As a reminder,forEach
is bad and you should feel bad for using it on regular copyable types. But needs must, so we can hold our noses and write it like this for now.
- So for now, we're going to do this via adding a
- To make implementing this easier, we really need coroutine accessors which are available via the underscored
_read
keyword used by the standard library.- But for now, to avoid wading into that particular territory, we'll just substitute in more closure-taking methods.
Adding these features will be the subject of future language evolution proposals. Without them the code is going to look a little involved, but not especially complicated.
To support non-consuming iteration, we need methods that borrow, but don't consume, our noncopyable things. Let's start by adding one to the Box
type:
extension Box where Wrapped: ~Copyable {
func with(_ body: (borrowing Wrapped)->Void) {
body(pointer.pointee)
}
}
This is a method that takes a closure, and applies it to the wrapped value. The closure explicitly borrows, rather than consumes, the wrapped element, meaning the box is left intact.
Next, let's use this to iterate recursively over our nodes. To keep things structured, we will add a method to the List.Node
type, and then after that delegate to it from the List
type:
extension List.Node where Element: ~Copyable {
func forEach(_ body: (borrowing Element)->Void) {
body(element)
next?.with { node in
node.forEach(body)
}
}
Similar to Box.with
, this takes a closure declared as borrowing Element
, runs it on the node's element, then uses optional chaining to call forEach
recursively on the next link.
That optional chaining is doing a lot of work for us. Let's desugar it into a switch
:
extension List.Node where Element: ~Copyable {
func forEach(_ body: (borrowing Element)->Void) {
body(element)
switch next {
case .none: return
case .some(_borrowing box):
box.with { node in
node.forEach(body)
}
}
}
}
Here we see our final experimental feature, -enable-experimental-feature BorrowingSwitch
, which allows us to borrow rather than consume the element wrapped inside an optional, with that _borrowing
keyword replacing the let
. This proposal is still in pitch phase, and is likely to change to instead allow a let
to be borrowing. For now, we're using the syntax that will compile with the nightly toolchain.
Finally, now that extension on List.Node
is in place, we can write forEach
on the list type, which just forwards on to the node:
extension List where Element: ~Copyable {
func forEach(_ body: (borrowing Element)->Void) {
head?.with { node in node.forEach(body) }
}
}
Now, instead of popping elements off the list, we can just iterate them:
list.push("one")
list.push("two")
list.push("three")
list.forEach { element in
print(element, terminator: ", ")
}
// prints "three, two, one,"
print()
while let element = list.pop() {
print(element, terminator: ", ")
}
// prints "three, two, one,"
That's enough example code for now. I encourage you to play around this this, to get a feel for this new feature. Experimentation the best way to understand it – it can be surprising what works and what does not work. You might want to try adding a mutating version of forEach
, or a method that reverses the list. If you want a real challenge, maybe try a more complicated acyclic data structure, like a tree. One thing though – while I encourage you to read the Rust linked list tutorial, the later chapters don't really apply. Swift's approach to a doubly linked list would just be to use classes and weak references, at least with the language as it stands today.
Remember, when using a nightly toolchain, you are using an in-development compiler with assertions turned on. Do not be surprised when it produces an error with a stack trace. This is most common when the code you wrote is invalid – but it also happens with valid code sometimes.
Finding new ways to trigger these assertions is immensely valuable to the engineers that work on the compiler. Please do post examples – either on this thread, or filing an issue on GitHub - apple/swift: The Swift Programming Language. Thank you for being a human fuzzer :)
That series opens with a bit of throat-clearing, that I won't repeat here, about why yes, linked lists are not a very useful data structure for most real-world purposes, but which ends with the reason I'm using them here, which is "They're simple and great for teaching!". ↩︎
Don’t forget
-enable-experimental-feature
andNoncopyableGenerics
need to be two separate entries. ↩︎In fact Doug already fixed it, just waiting on a nightly toolchain to post to remove this flag. ↩︎
With copyable types, you would not need to create a manual box, but instead could use the
indirect
keyword on an enum. This is not yet supported for non-copyable types, as there are some open design questions around how this would work. ↩︎It can be educational to add some print statements into the methods of
Box
to see exactly when they run. ↩︎There is a caveat here. Because of the way our list is constructed, destructing it happens by recursing all the way to the end and then calling deinitializers all the way back. If the list is truly huge (why are you creating huge linked lists? stop that) you will blow the stack. This affects Swift today if you did the same with classes or an indirect enum. But good news! You can now give this list type an explicit
deinit
that can destroy the list from the front. But implementing that is a bit beyond this post. ↩︎