An Informal Introduction to Move-Only Types

I've recently found myself explaining our move-only types work to a lot of different people. As a result of those conversations, I thought it would help to have an informal sketch to help outline why move-only types are interesting, clarify a few subtle points (like what "move" really means), and briefly explain some of the issues we'll need to tackle in order to bring this to Swift.

Note: This is deliberately light on details -- those will be covered in various pitch and proposal documents. Some of those have already appeared (the "take" operator and "take" and "borrow" argument modifiers proposals), others will continue to appear over the next month or so.

An Informal Introduction to Move-Only Types

Background: Why do we care?

When you look at where current programming languages spend their CPU cycles, memory management is consistently at or near the top of the list. This is true whether you use a garbage collector, reference counting, or custom logic to determine when a particular piece of memory is in use. This complexity in turn exists in large part because references (pointers) get copied. The existence of these copies forces us to come up with some system to identify at run time what pieces of memory are still accessible.

Working with pointers in general has another serious problem: There is really no way for a compiler to examine a particular bit of pointer arithmetic in a language like C and determine whether it is safe. So high-level languages will eventually have to stop providing unverified support for raw pointers, and new memory management idioms must be based on guarantees that can be verified by a compiler. Different languages are trying different approaches to this, and time will tell which of the many techniques being explored will prove most effective at balancing verifiable correctness with simple programming models that are accessible to a large population of developers.

These same problems can occur with non-pointer values that are used as “handles” for some resource that is separate from the value itself. For example, you might track the integer index of an object in an array or the key of some data stored in a database. Just as with pointers, it can cause a variety of problems if those values get copied to many locations and we lose track of which ones are still valid.

Moving vs. Copying

As mentioned above, “copying” is one of the key reasons for runtime memory-management complexity. So what if we could mark a certain piece of data as not copyable? Or similarly, what if there could only be one reference to a particular piece of data? Or we could guarantee that a certain database key was stored in one place and never duplicated?

Such a property is easy for the compiler to verify: It just needs to produce an error whenever you do something that would require copying the data or reference. It also allows the compiler to omit most runtime memory management: For example, if you can never have more than one reference, you don’t need to count the references, so you can avoid garbage collection or reference counting overhead for that object. In general, if you can declare that a particular type of data cannot be copied, you can potentially provide guaranteed correct behavior with no runtime cost.

Unfortunately, compilers “copy” data for a lot of mundane reasons. For example, when you pass a value as a function argument, that data is “copied” from memory into a register. That means a truly non-copyable piece of data can only be passed by reference, never by value. Truly non-copyable data is tricky to work with.

But not all copies cause problems: In many cases, the “copy” exists in order to move a piece of data to a more appropriate location. For example, when you compute “x = x + 1”, the result may naturally end up in a different location (machine register or memory address) than it started. This isn’t really a “copy” since the first location is no longer valid. Similarly, when you return a value from a function, the original value inside the function is no longer valid. This makes it useful to distinguish between "regular copies" which result in two or more valid instances of the data, and "moves" which result in a single instance of the data in a new location, with the old location no longer being considered valid. Note that in "x = x + 1" and other cases, moves are really just side-effects of some other operation.

Aside : There is such a thing as truly non-copyable (“immoveable”) data. Locks and hardware registers are two examples, but they’re different enough from the cases I'm interested in here that I won't discuss them any further.

Limited Lifecycles

A value that can be moved but not copied has a very well-defined lifecycle. It is created, passed into functions and back out again, moved into different variables, and finally stops being valid. Throughout this lifecycle, there is only ever a single valid copy of this value. Among other things, this gives it a well-defined end of life that can be determined at compile time. This is unlike a regular copyable value which requires run-time support to correctly determine when every copy has stopped being used.

Consider for example a file descriptor. A file descriptor is an integer that represents a currently-open file. It’s important that after you close a file descriptor, that particular value can no longer be used. If a file descriptor is a “move-only type”, then we can arrange for the close operation to end the lifecycle and be certain that there are no valid copies elsewhere that could be accidentally misused. Note that this isn’t a reference — a move-only file descriptor is still just an integer under the covers and will still be efficiently handled as such at runtime. But at compile time, it will be an opaque entity with strong lifetime guarantees.

A similar issue arises whenever you have a pointer (a “view”) into another data structure. It is important that the pointer does not outlive the data structure it points into. There are several ways to provide this guarantee: One way is to wrap the pointer in a move-only type and force its lifetime to end before the data structure does. This is sufficient to ensure that the pointer can never be used after the data structure itself is gone. And this can all be proved at compile time without any runtime overhead.

Move-only types are not a panacea, of course, and they are not appropriate for every kind of data. For example, you cannot cache a move-only value because caches must store copies of the data. Similarly, there are limitations on how you can use move-only values as elements of other structures and collections.

Move-Only Types vs. Swift

Today’s Swift really likes to copy things. A simple statement like let x = a.b implicitly makes a copy of the value in question. Similarly, when you write for x in collec tion , each value in the collection will be implicitly copied into the variable x . Likewise for if let x = optional . The optimizer can frequently remove such copies, but whether any particular copy actually gets removed depends on precisely how the optimizer works, which can vary from release to release. So in order to support move-only values and types in Swift that must never be copied, we’ll need some new syntax that allows values to be explicitly “borrowed” and “taken.”

“Borrowing” is a key tool for working with move-only types that allows the value to be temporarily used in another location. Depending on the precise context, a “borrow” might be implemented by the compiler as moving the value to some place and then back again, or it might be implemented by creating a temporary reference to the original value. Regardless of the implementation, the key notion is that a “borrow” provides temporary, limited use of a value that might not be copyable.

Borrowing turns out to be useful even for copyable values. Because borrow operations are intrinsically limited in time, they allow the compiler to optimize memory management. For example, borrowing a reference can avoid reference-counting operations that would be necessary if the same reference were copied and then later invalidated.

Unlike a “borrow”, a “take” explicitly ends the lifetime of the original. If you call a function by writing f(take x) , you are explicitly moving x into the function and invalidating the local variable in the process. If you write let x = take a.b , then you are explicitly invalidating the property a.b and also the entire structure a . (In contrast, let x = borrow a.b allows a to continue being valid.) As with borrow , take is helpful today as a tool for fine-tuning reference counting operations but will be essential for working with move-only values when they become available.

So the first step in bringing move-only support to Swift is to add operations with different lifetime-management behaviors. This will include constructs such as for borrow x in collection that let you iterate over the items in a collection without requiring an implicit copy and f(take x) that explicitly invalidates the local value as part of passing it into a function. We’re also exploring variations of these that would allow you to temporarily gain mutable access to a value. These would allow you to efficiently mutate an element “in place” in various scenarios, which is a useful optimization tool for copyable values and an essential prerequisite for move-only values.

Move-Only Types and Generics

One of the most difficult issues bringing move-only types to Swift is the fact that Any is copyable. Were we to allow Any to store move-only types, then we would need to make Any itself un-copyable. This would break a lot of code.

Instead, we expect to refine the definition of Any . By making Any a synonym for any Copyable , we can ensure that Any is itself always copyable at the cost of limiting it to only store copyable values. This redefinition would preserve the behavior of current code that uses Any . Of course, this means we need to introduce a new type that can hold any value whether it is copyable or not. We’re still trying to come up with a good name for this. (We’ve considered any Moveable and any ?Copyable as possible ways to describe all types that are at least moveable and may or may not be copyable.)

Introducing a new “top type” to Swift’s type system is going to require some deep surgery to many parts of the compiler and will no doubt have additional implications for the operation of our generics system that we have yet to fully understand.

Of course, the bulk of our standard library collections are generic, so we’ll need to carefully assess the impact on those and see how far those can be generalized to support move-only types.

Where We Are So Far

The description above is based in part on design discussions that go back many years, including the “Ownership Manifesto” that was published in 2017. Over the last year, a couple of our compiler engineers have been actively experimenting to see how this might all fit together. For example, these experiments pointed out to us that borrow and take concepts were essential before even the most basic move-only types could be made useful.

We still have a long ways to go, but we’re making steady progress:

  • We’ve started writing up design proposals for the various kinds of borrow, take, and related keywords and how they will work. The first of these are currently in Swift Evolution review and we will continue to share those with the community as we proceed.
  • We have some prototype implementations behind a feature flag in the compiler. This is of course veryexperimental, but we encourage people to try it and give us feedback on what works, what doesn’t work, and whether the direction we’re going looks like it will be generally useful.
  • One of our goals is to efficiently support pointers into collection contents via a new BufferView type. We’re just starting to understand how that might work in practice. One thing that has become clear: The fullest implementation of this will require more than just move-only types. We’ll also need some additional tools to ensure the lifetime of a BufferView ends before the collection it references.
  • We’re just beginning to explore the implications for generics and what will be needed to have a new top type.
  • We’re also just beginning to understand the impact for the standard library collection types.
  • We’ve also been talking with people working on C++ interop. C++ can express types that lack the ability to be copied, and importing such types will rely on the same internal mechanisms that are used to represent Swift non-copyable types.

How Other Languages Handle This

For completeness, I’ll summarize a few alternate viewpoints:

  • Lifetime variables: Rust’s “lifetime variables” express lifetime dependencies between different objects in a way that allows the compiler to verify correctness at compile time and completely avoid a lot of runtime lifetime management. This gives more flexibility than just move-only types, but many developers seem to find this system difficult to learn and difficult to work with in practice. Swift’s focus on ease-of-use that has led us to look instead for approaches that can easily handle the most important lifetime constraints without the complex generality of Rust’s approach.

  • Immutable/Functional: Functional languages rely on fully-immutable values, which makes copying largely irrelevant. This makes these languages very uniform with strong guarantees that allow a lot of sophisticated optimizations. But immutability has a number of drawbacks, especially for less-experienced developers who can find some of the constructs awkward. A lot of the current work in Swift (and other languages) involves ways to provide mutability in most cases, restricting it only as necessary to provide key safety guarantees.

  • Enhanced Pointers: C and C-family languages such as C++ and Objective-C allow you to use raw pointers to optimize reference management. In practice, this has proven error-prone and language designers are trying to find ways to eliminate the use of raw pointers, similar to how language designers in the 1960s began introducing structured programming constructs in order to eliminate the need for goto. You can view some of these new constructs as being ways to "augment" or "enhance" pointers with additional safety properties. But I prefer to think of them as more abstract concepts -- "views", "ownership", and "references" -- that just happen to be implemented as pointers, just as while loops and if statement are ultimately implemented in terms of machine-level branch instructions.

74 Likes

Good explanation.

But with regards to this section:

And then later:

I think the term "copy" is unhelpful and potentially misleading, and I hope we can think of a better alternative.

When we talk about copies here, my understanding is that we're really talking about arbitrary lifetime extensions - i.e. the ability to retain some class instance which will live until you, at your leisure, choose to release it, or for POD types: the ability to create a value containing the same bits as another value, but in independent storage (e.g. escaping the stack frame and copying the value in to a global or class instance).

I don't think we're talking about copy in the sense of shuffling data in/out of registers. We're also not talking about copies in the sense of copy-on-write (although those kinds of copies may be affected by controlling the copies we are talking about). Correct me if I'm wrong, but the only reason these notions enter the text in the first place is due to the potential confusion caused by the term "copy".

And I think it is important that we straighten this out - the text has to jump through some awkward hoops as a result of this terminology issue. Firstly it simply declares things like register shuffling as not a problem, including using the extremely confusing phrase "in many cases, copy exists in order to move". This leads to having to define a notion of "regular copies", and in order to explain what they are, we have to suddenly switch gears and start talking about lifetimes instead.

IMO, tightening the terminology helps us focus, and helps everybody understand what these features do and when to use them.


I also think the term "move-only" is problematic, for similar reasons. Firstly, it is factually incorrect - you can still borrow these values, so they are in no sense "move only".

What they are are non-copyable (see note above: in other words, you cannot arbitrarily extend their lifetimes; they have constrained lifetimes).

Similarly, the text refers to "truly non-copyable data". What it means is data which is both non-copyable AND non-moveable (in effect, borrow-only). Of course, it is difficult to talk about this if we stick to the term "move-only" as a synonym for non-copyable, as the former implicitly excludes borrows, meaning we would be left with the phrase "immovable move-only data" --- which, yeah.


By the way, I have mentioned both of these issues previously (and in other reviews). I didn't get any direct responses on the terminology issue. Hopefully the issues I've pointed out with this text illustrate why I believe this is still a significant issue.

This is still a somewhat-simplified ownership model. More easily digestible. Even with these features, I don't believe we would have the full expressive power to, say, store a value with a bound lifetime (say, a non-escaping closure) in a struct/Array, and have that struct/Array be bound to the value's lifetime (Rust's more verbose model can express that, with the drawbacks as mentioned in the text).

But it's still valuable, I'm really excited for it, and I think it will be a really great addition to the language. I appreciate that naming things is very, very hard, but I also think it is one of the most important aspects to ensure that Swift's ownership model remains usable even as it becomes more expressive.

2 Likes

Why?

It would be better to let let x = take a.b only take/move what developer really want to take/move - b only! Not the entire object a, thus a.c or a.* something else can still stay validated for later access.

Partial-move is more flexible in programming practice, and this is the same rule Rust follows.

How would that interact with computed properties and resilience?

  • What if a.b is actually a wrapper around a.c, and taking a.b actually takes a.c?
  • Conversely, what if a.c actually returns a.b.c?
  • What is the status of a as a whole after being partially taken? Does it count as partially initialized, and can it be restored to fully initialized by putting b back?
  • What if a is resilient, meaning these relationships could change in the future?

It seems likely that this could only work for stored properties of non-resilient/frozen types, but outwardly distinguishing between stored and computed properties goes against the grain of Swift.

6 Likes

I just fielded a question about this elsewhere, so I figured it may be useful to note a handful of clarifications here too:

  1. Retaining an object is, in the compiler's view of things, copying it. It doesn't refer to NSCopying-style deep copies here.
  2. Copy-on-write is not something the Swift compiler does automatically for your structs or enums, it's something specific types implement by hand
  3. Copy-on-write does not delete copies at all, it converts them to retains, which as discussed in point 1 are still considered copies
  4. The optimizer does delete copies, which is different from copy-on-write. First the optimizer tries to delete as many unnecessary copies as it can, and then some of the remaining ones may end up being retains due to CoW.
  5. What the optimizer does under the hood is not really part of the language model. It's allowed to do whatever it wants as long as it can prove there's no way for you to tell the difference between what's specified to happen and what actually happened.
16 Likes

I am not a Rust expert, so please correct me if I’m wrong, but I don’t think that’s how partial moves work in Rust (from this page, emphasis added):

Partial moves

Within the destructuring of a single variable, both by-move and by-reference pattern bindings can be used at the same time. Doing this will result in a partial move of the variable, which means that parts of the variable will be moved while other parts stay. In such a case, the parent variable cannot be used afterwards as a whole, however the parts that are only referenced (and not moved) can still be used.

I would take that to mean that, according to Rust rules, let x = take a.b would invalidate a, and one would have to write let (x,y) = (take a.b, a.c) in order to continue using the value from a.c. The example code on that page certainly suggests this is how it works.

1 Like

I think for-loops should already use borrow. Collections that actually implement a read accessor in their subscript(position:) would not actually use any copies. Collections that instead use just get would necessarily create a copy if the optimizer cannot help. Nevertheless, most high-quality collection should implement the read accessor so I think borrowing should be the default for for-loops.

The terminology here is indeed a little confusing, but I've not been able to come up with anything better. If you have suggestions, I'd love to hear them.

I've found two ways to define "move": Either "move" is a "consuming copy" or it's a "change of location". I prefer the former, which is what led me to start thinking of "immoveable", "move-only/uncopyable", and "copyable" as three gradations of copyability.

I think we agree on the key point, though: "copyability", "lifetime", and "ownership" are highly intertwined concepts. And we would all like to find clear ways to utilize these concepts to build efficient, easy-to-understand software.

Tim

P.S. Discussions like this often remind me of a math professor who was fond of the "Red Herring Principle," which says "Something can be a 'red herring' without being either red or a herring."

2 Likes

Want to further note/emphasize here the importance of “what’s specified to happen”—this notably doesnt mean that there’s absolutely no way to, say, write a program whose printed output depends on optimizer behavior, because Swift deliberately leaves certain behaviors unspecified.

4 Likes

This will include constructs such as for borrow x in collection that let you iterate over the items in a collection without requiring an implicit copy and f(take x) that explicitly invalidates the local value as part of passing it into a function.

Should a sufficiently intelligent compiler be able to optimize this borrowing automatically? Is there an alternative here to do for borrow/take what ARC did for release/retain?

I'm having a hard time seeing strong motivations in the "Why do we care?" section that justify adding yet even more complexity to a language that is increasingly jam-packed full of it. After all, Swift is not a general purpose or low-level programming language like Rust or C++, despite its claim. It is for building iOS/macOS apps, and perhaps its priorities should reflect that.

4 Likes

This is incorrect, Swift is being used in low level systems work quite a bit.

16 Likes

It's really not though, relative to its overall use.

1 Like

This is not the case, partial moves do allow you to do fancier accesses—Rust special-cases partial moves within a function's scope. It tracks which fields have been invalidated and allows you to continue to freely access the other fields. The object as a whole is immediately invalidated so you can't call methods or pass it around unless you re-assign to the fields that have been moved-out-of, but you can still safely access a.c after you've already moved out of a.b.

Here's a rust playground that demonstrates this behavior:

I think to have this same kind of behavior in Swift to flexibly move out of a type, the closest match is (as @jayton suggests) only the stored properties of @frozen types. But this isn't a very satisfying answer and all of @jayton's questions are good ones.

7 Likes

Fascinating! I’m shocked and impressed that they went to the trouble of implementing that.

Thank you for putting together that excellent example playground!

2 Likes

Possibly, and that's certainly a point we're discussing as we continue to work through the details. I personally believe that we will in time find many cases where the compiler can consistently make these decisions automatically.

But there are definitely cases where developers need confidence that the compiler will do what they expect. In particular, anything that impacts the calling conventions used by stable ABIs needs to be specified sufficiently that any future version of the compiler will produce compatible code.

I hope someday we can change your mind about that. :slightly_smiling_face:

Tim

5 Likes

I think your way of thinking about it was fine. a, the object as a whole, is invalidated. Rust essentially just permits the name a.c to still be used as a special case.

Anyway, as a general rule, destructuring needs to be restricted outside of the implementation of most types. It requires knowledge of the type's implementation, and it can break invariants very easily.

4 Likes

Ownership features in Swift have always been in pursuit of two goals. One goal is to make Swift more capable for building low-level systems code; if you aren't interested in that, that's fine. The other goal is to give high-level programmers better tools to solve performance, correctness, and expressivity problems when they do encounter them. It's expected that high-level programmers will see these problems less often than low-level programmers, but they will see them occasionally, and if they can't solve them at all within the bounds of Swift, Swift isn't really doing its job.

Move-only types allow programmers to express unique ownership of resources, and a lot of resources are naturally uniquely owned — there's really only one client that should be using them at a time. You can always wrap something that's uniquely owned in an object with shared ownership, but that usually creates problems: additional overheads, for one, but more importantly, the question of what happens when multiple clients use it at once. Answering that question often leads to further overheads (e.g. synchronizing low-level accesses) and/or API complexity.

For example, a lot of C libraries rely on unique ownership: you create an object with one call and then destroy it with another call, with no extra reference-counting mechanism. Those libraries are often still interesting to use from high-level applications — maybe it's an audio synthesis library, and your application wants to programmatically generate an audio stream for some reason. If you want to make a Swift library which wraps that today, you have three choices:

  • You can expose the underlying unsafety of the C API by requiring your clients to manually destroy the objects you give them. This is obviously not a great solution because it's really easy to mess up and maybe crash the process.
  • You can expose the object only via a callback, where you create the object, pass it to the callback, then automatically destroy it at the end. This is still exposing the unsafety in a way, because clients can stash the object you give them, which will end up dangling after the callback returns. More importantly, it's really limiting; the C library probably doesn't need all the work to happen within a single synchronous callback, but you're making your clients deal with that restriction anyway.
  • You can wrap the object in a normal class. That adds extra allocation and indirection overhead, and it might also add some reference-counting. More importantly, now your clients can have multiple references to the object, potentially from multiple concurrent contexts, and you have to decide what to do about that. In most cases, the underlying C library doesn't care what thread it object is used from as long as it's not used concurrently. If you make your class non-Sendable, you can know the object won't be used concurrently, but you're also sharply limiting your clients — they can't, for example, move the object between actors, even if only one actor will use it at a time. If you make your class Sendable, then either you're introducing a thread-safety hole, or you'd better make your class internally synchronize just in case it gets used concurrently.

Move-only types give you a fourth option, to wrap the object in a move-only type. Now the compiler will ensure that you only have one client at a time, and you don't need to add any extra allocation, indirection, or synchronization, so your Swift library is basically exactly as fast as the underlying C while suddenly becoming memory-safe and thread-safe. Your clients will have to live with the limits of a move-only type, but they might happily take that trade-off in exchange for the better performance. And if they don't want to accept those limitations, you can still offer a lower-performance wrapper implemented in terms of the high-performance one.

As an application programmer, this kind of feature can be the difference that makes better libraries like that possible so that you don't need to implement core parts of your application in unsafe, low-level languages like C.

41 Likes

I think it's probably a more essential feature in a language like Rust where the majority of types are move-only, rather than moving be a special case. Not having partial moves when all operations are moves by default ends up being more painful than necessary.

2 Likes

Well it really depends on what is exactly the semantic of take in Swift: Shallow take vs. Deep take

In Rust, everything is plain flat structure with simple storage field without any value indirection/mapping between them. But in Swift, we have computed property, observer property, property wrapper, furthermore also with subscript, @dynamicMemberLookup and KeyPath accessor; the problem becoming quite complicated. How to tackle take semantic of these indirect computation/functor accessor in Swift?

For example, a.x -> b.y -> c.z a typical transitive chaining/computing mapping; what does let foo= take a.x really mean? To explicitly take only a.x (shallow take) or jointly implicitly take both b.y and c.z (deep take) and make them invalidated after foo-taking expression.

If deep-take, the developer must get confused, why let foo = take a.x also block b.y and c.z access. So for Swift, shallow-take should be the default take semantic.

On the other hand, besides shallow vs deep take. How to define the priority of take and accessor-with-defer{}? If take a property with _modify { ... yield &something; defer {... rebinding value here } } accessor, how to take.. or take what?

Rust doesn't have nil. Swift has nil (at least for reference types). What happens when we allow move-types to be nil (assuming they work the same as references)?