A Basic Noncopyable Singly Linked List in Swift

list.swift

// To run this code on a Mac with Xcode installed:
// Download the latest toolchain from https://www.swift.org/download/#trunk-development-main and install it
// From a command line:
// export TOOLCHAINS=`plutil -extract CFBundleIdentifier raw -o - /Library/Developer/Toolchains/swift-latest.xctoolchain/Info.plist`
// xcrun swiftc -parse-as-library -enable-experimental-feature NoncopyableGenerics -enable-experimental-feature MoveOnlyPartialConsumption -Xfrontend -disable-round-trip-debug-types -enable-experimental-feature BorrowingSwitch linkedlist.swift


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
  }
  
  func with(_ body: (borrowing Wrapped)->Void) {
    body(pointer.pointee)
  }
}

extension Box {
  var wrapped: Wrapped { pointer.pointee }
}

struct List<Element: ~Copyable>: ~Copyable {
  struct Node: ~Copyable {
    var element: Element
    var next: Link
  }
  typealias Link = Box<Node>?
  
  var head: Link = nil
}

extension List.Node where Element: ~Copyable {
  func forEach(_ body: (borrowing Element)->Void) {
    body(element)
    next?.with { node in
      node.forEach(body)
    }
// Desugars to:
//    switch next {
//    case .none: return
//    case .some(_borrowing box):
//      box.with { node in
//        node.forEach(body)
//      }
//    }
  }
}

extension List where Element: ~Copyable {
  mutating func push(_ element: consuming Element) {
    self = List(head: Box(
             Node(element: element, next: self.head)))
  }
  
  mutating func pop() -> Element? {
    switch head?.move() {
    case nil:
      self = .init()
      return nil
    case let node?:
      self = List(head: node.next)
      return node.element
    }
  }
}

extension List where Element: ~Copyable {
  func forEach(_ body: (borrowing Element)->Void) {
    head?.with { node in node.forEach(body) }
  }
}

@main
struct Main {
  static func main() {
    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

    list.forEach { element in
      print(element, terminator: ", ")
    }
    // prints "three, two, one, "
    print()
    while let element = list.pop() {
      print(element, terminator: ", ")
    }
    // prints "three, two, one, "
    print()
  }
}

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 that there can 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. But that has been difficult until recently because not all the necessary pieces were available in a nightly toolchain, even under an experimental flag. 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, 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 they handle ownership.¹

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². 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. 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³. 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 value 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).
• 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⁴:

    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 just leaving off the ~Copyable:

extension Box {
  var wrapped: Wrapped { pointer.pointee }
}

This var 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.⁵
• 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.com/apple/swift. Thank you for being a human fuzzer :)

Footnotes

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

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

5. 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. ↩