Noncopyable Generics in Swift: A Code Walkthrough

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 a deinit, 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, the deinit 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 the deinit method.”
  • There are two uses of the consuming keyword:
    • The init takes its parameter consuming. 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 is consuming. 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).
  • 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 the Box 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 the Box 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 declare UnsafeMutablePointer<Pointee: ~Copyable>, which is how come this code can put Wrapped inside one.

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 with Box, it does not need an explicit deinit 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 of Copyable-conforming generic struct List has non-Copyable type List<Element>.Link (aka Optional<Box<List<Element>.Node>>)

  • Like Box, the copyability of the generic placeholder Element is also supressed, so this type can safely hold both copyable and non-copyable types.
  • Like with UnsafeMutablePointer, the standard library's Optional 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 the Box.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 extend Optional, 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.
  • The code fully reinitializes self. It doesn't just update head to the new link. Let's say you tried to assign to head 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 passing self.head into a consuming initializer. But we didn't pass all of self. Just one of its properties. After this, self is in an unusual state – it has a kind of "hole" where head 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 consume self". 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.

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 and pop 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. The node variable is also partially consumed, in two parts. We put the next into head, and return the element to the caller.
  • Because the switch (partially) consumes self, it must be reinitialized on all paths, even when head turned out to be nil 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 therefore for...in, does not yet support non-copyable types. Sequence could be made to support it today by marking the protocol up as ~Copyable and having makeIterator() 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.
  • 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 :)


  1. 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!". ↩︎

  2. Don’t forget -enable-experimental-feature and NoncopyableGenerics need to be two separate entries. ↩︎

  3. In fact Doug already fixed it, just waiting on a nightly toolchain to post to remove this flag. ↩︎

  4. 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. ↩︎

  5. It can be educational to add some print statements into the methods of Box to see exactly when they run. ↩︎

  6. 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. ↩︎

69 Likes

Could you explain how you see the box's wrapped value interplaying with ~Escapable?

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 just 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).

This implicit Copyable is still the sharpest edge of noncopyable generics for me. I understand why it’s necessary to have previously-written extensions maintain their assumption of copyability, but we’ve literally just written a new type that’s opted out of Copyable - can we not find a way to at least make it so we require clients to state where Wrapped: Copyable and : Copyable explicitly when extending such types?

10 Likes

This is superb.

It could also be the basis for a Swift.org blog post (probably around the time of Swift 6's release, or whenever the relevant features mainlined). I realise non-copyable types are intended to be a niche feature, but I think the audience for this kind of introductory howto is much bigger as it includes people that are simply curious.

Maybe, right? If the compiler determines that the caller has no need for the value after Box's init, it can pass it directly, no?

Though this requires that the let variable be invalidatable, right? So it couldn't be e.g. a stored property (except if you're consuming it in deinit or equivalent?)?

Missing where Wrapped == Copyable?

Is it an intrinsic requirement that the compiler implement that synthesised deinit as a recursive algorithm rather than an iterative one?

Or perhaps more to the point, as depth-first rather than breadth-first?

Just out of tangential curiosity.

I wouldn't expect it to special-case a singly-linked list or anything, but it does seem plausible that it could recognise cases where back-references are impossible, and delete as it goes.

Yeah, while it makes sense as written given the current rules, I guarantee I'm going to first write the following instead, every single time:

mutating func pop() -> Element? {
    if let node = head?.move() {
        head = node.next
        return node.element
    } else {
        return nil
    }
}

It'll be great when that's one day supported as well, re. the partial consumption proposal etc.

[Tangentially] Nah, because with optional chaining situations for…in loops are often worse. And I say that even though I'm increasingly growing to hate the use of trailing closures to mimic basic blocks (given the compiler's inability to reason through the control flow, and thus how it breaks even the most rudimentary features like initialisation of lets).

The issue is that we're adding support for noncopyable generics with types like UnsafePointer and Optional. Extensions of these types _must_ preserve the notion of copyable on their generic arguments. "But we can have those types use the weird behavior and have new types opted into this feature require : Copyable" Well, yes, we can do that but then it's very awkward that extension Optional assumes Copyable and extension Foo may or may not depending on if it has noncopyable generic arguments.

1 Like

The implicit requirement here is that Wrapped: Copyable.

1 Like

I know. My question was largely rhetorical. Not to argue the decision - it makes sense why it's implicit for extensions, as @Ben_Cohen explains in the post - but rather just emphasising that it's going to be a very frequent question and point of confusion, alas.

The part of it that's not rhetorical is the implication that perhaps there should at least be a language mode or switch or something that let's the compiler warn you when you're relying on this implicit behaviour, so that those of us that prefer to do so can make the constraint explicit instead.

I don't expect to ever migrate the world that way, but that's not the point. I can at least make my own projects more readable.

3 Likes

some examples like this using the noncopyable atomic type would be most welcome as well!

I appreciate that perspective, though I disagree with it. But I'd ask folks to keep feedback about that feature to the review proposal, rather than bifurcating that particular discussion into this thread. You're welcome to quote from this post there.

Atomic's generic argument currently always requires a copyable type. I'm not sure it makes sense to support non-copyable atomic values, but perhaps there is a use case that could convince me otherwise.

What is interesting though with atomics is that with the Box example we can model heap allocated atomics using the non-copyable infrastructure (we can already do this with ManagedBuffer, but with no reference counting now!) Box<Atomic<Int>>.

@Ben_Cohen Thank you for this very helpful walkthrough.

To track this, I've filed a Swift website issue to update the walkthrough into a blog post or documentation article after the relevant proposals have been approved and implemented in a release.

4 Likes

Yes, if the optimizer is able to see that the last use is passing it into that function. Though this optimization is not guaranteed.

Exactly. Since you cannot use that value after it's been consumed, it does not matter that you appear to be able to "mutate" it via a consuming function.

It is possible that this could be fixed but my suspicion is that that fix would be fragile to variations (similar to how the tail-call optimization is fragile rather than guaranteed – not that this particular case could be TCOd I don't think).

2 Likes

I need to think about it some more, but I've been toying with the idea of non-copyably boxing UnsafeContinuation as a means of ensuring that the continuation must eventually be consumed. Then to ensure that it is only consumed once I'd like to wrap the boxed continuation in an Atomic. I've been doing something very much like this with ManagedAtomic. Making it all work still requires a notion of consuming escaping funcs, but I can get someway down the road on this if I could "Atomicize" a Box.

When I think about it, the whole "UnsafeContinuation must be consumed exactly once" thing seems to be crying out for this.

So comparing @Ben_Cohen 's List code above where Node is marked ~Copyable

got me thinking about @lorentey 's implementation of the Michael/Scott LockFreeQueue in swift-atomics. I'm kind of wondering now if the need for Node to be ~Copyable in the basic List and ManagedAtomic in the LockFreeQueue is not an indicator that we'd like Atomic to be capable of something similar.

I get the whole comment about:

// While this is a nice illustration of the use of atomic strong references,
// this is a somewhat sloppy implementation of an old algorithm.

But it doesn't seem that sloppy.

:+1: :+1: This is a great write up. Looking forward to seeing it in the blog.

I don’t understand how this works if Wrapped is a non-Trivial, non-Copyable type.

2 Likes

The documentation for initialize(to:) states:

The destination memory must be uninitialized or the pointer’s Pointee must be a trivial type.

Since the destination memory is uninitialized (as returned by allocate(capacity:), then the precondition on type triviality does not apply.

That's how I get it. I read that initialize does not destroy the previous value, but takes care of correctly storing its input, regardless of its type (i.e. it's not semantically equivalent to memcpy).

1 Like

But the value is not Copyable, so it can’t be copied into the allocation.

1 Like

Isn't it "moved", instead of "copied", because wrapped is consuming, even it some bits are copied in the newly allocated memory? I have a hard time reasoning in terms of the abstract Swift memory model, but...

3 Likes

Ah, that makes sense. In fact, I am now vaguely recalling a pitch/review of a version of the UnsafeMutablePointer API that consumes its arguments. So the value won’t have a stable address, but it won’t exist in two places either. (And I now recall that this is why atomics need their own stable address attribute.)

@Ben_Cohen, perhaps it’s worth adding a link to that UnsafeMutablePointer discussion for anyone who forgot about it or missed it like me?

2 Likes