How might linear types work in swift?

Thought I'd break this off from [Pitch] Introduce a way to annotate functions that are called at most once since I think it is interesting to consider and wanted to respond to @jrose but it's not super pertinent to that pitch.

I'd argue that Deinit types should not be able to store ~Deinit types (so it isn't too easy to avoid consuming them), so this example would need some internally unsafe, stdlib type like DeinitConsume<T: ~Deinit & ~Copyable> that calls a consuming method in it's deinit, and DeinitBomb<T: ~Deinit & ~Copyable> that traps in it's deinit if it wasn't defused via consumption. Or maybe we allow storing ~Deinit in a type that is allowed to have a programmer defined deinit, and require it to be consumed there? Note that neither of these approaches give linearity.

The point I'm making is about DI and other operations where the linear type needs to be consumed (via a method on the type) to uphold the correctness of the system, but I agree with what you are saying and I was too broad, I should have said ~Deinit without ~Escapable is not linear, not that it isn't useful in contexts besides called once closures. If the compiler believes a value has been initialized by some point due to consumption of a linear function, but it has not, and we allocated uninitiated memory on that assumption, we would expose it and violate memory safety. If we have a notion of ~Deinit for a value that can ever end up stored in a reference type, we cannot do anything "interesting" (from a safety perspective) for ~Deinit types by assuming a consuming method was used, since it can be owned by a reference type, which can be leaked. ~Deinit without ~Escapable allows you to store it in a global variable, too! In the context of called exactly once, Escapable ~Deinit probably isn't good enough, unless it is expected and safe for users to mem::forget it... which is equivalent to called at most once.

Pre-Pooping Your Pants With Rust - Faultlore has an example of "safe forget" in Rust, it would be even easier to write safe forget in Swift, which takes ownership of an Escapable ~Deinit and stores it in a cyclic reference type.

Escapable ~Deinit is ergonomically nice and I agree it's interesting because it does give you a hierarchy of of types like the file handles you describe, even though it isn't a linear type. I see this as a very powerful lint, rather than changing what code can be expressed safely. Safety can't depend on consuming it via a method, but all code that didn't intentionally avoid it does consume it appropriately.

For a type that just wants to ensure it's deinit always runs before execution proceeds past a scope (for all of these, we need to rule out abnormal exits that the CFG doesn't represent) ~Copyable ~Escapable is already good enough. The upshot of ~Deinit is ensuring that consuming operation can take parameters, return values the programmer needs to deal with, or throw errors.

5 Likes

Thinking more about it, I think ~Discardable is a better name, it fits in better with ~Escapable and ~Copyable. I had some discussions about what this could look like (motivated by @called(once)) and I feel like there are interesting ideas that I want to spell out fully. This isn't really a "design" so much as some thoughts.

I'll talk about the notion of what 'unsafe' code can assume about 'safe' code. Unsafe code usually has the aim of doing things the compiler can't verify (like working with uninitialized memory) and encapsulating them in a way that means safe code is never exposed to that UB, no matter how safe code uses it. Things we can add to the language that allow unsafe code to make more assumptions of safe code increase the kinds of unsafe code that can be safely encapsulated, which can be desirable. "Linear" types are interesting from a safety perspective for allowing unsafe code to assume that safe code either ran some desired logic with a mutating dependence on another value before graceful exits, or has been prevented from accessing a value due to exclusivity.

I'll also talk about graceful exits, which excludes fatalError, killing the process, unplugging the computer, things of that nature. We won't be able to invent types that ensure we do work in these cases. Rust unwinding is an interesting comparison, I think of Swift as always being in panic = "abort" which means that it is impossible to "catch" or attempt to recover from fatalError, so we don't need to leave the program in a good state when that happens.

Note that I'll talk about consuming things more than once in the context of Copyable. This describes copying the value, then consuming one of the copies. Thinking about consumption like this allows some ideas to generalize.

We can define ~Discardable as types which don't have implicit destruction or programmer defined deinit. These types are interesting even when they aren't paired with ~Escapable or ~Copyable! Such a type is required to be consumed anywhere it might normally have been released. Members that are also ~Discardable need to be consumed when that happens. If you were holding such a value, you'd need to consume it before throwing, unless you can store it in a global or are throwing the value. This means it needs to be passed to a function as a consuming parameter, or have a consuming method called. During separate checking, the body of that function with the consuming parameter had to consume it or pass the obligation further! Because ~Discardable does not require ~Escapable, this isn't a very strong requirement; it does not tell us that the value will be consumed before graceful program exits. You can store an instance of this type in a reference type, and then involve the reference type in a cycle. In Rust, this would be something like mem::forget, which is safe (after the leakpocalypse) to make it clear that the compiler cannot prevent safe code from doing this. Unsafe code needs to assume safe code may "forget" to consume these values, so unsafe code cannot rely on consumption to uphold correctness.

There is a design fork regarding if ~Discardable values can be stored in Discardable values. There is a way to make it work which is equivalently safe, but it's easier to decide this isn't allowed, and provide DeinitConsume<T: ~Discardable & ~Copyable> (calls a provided consuming method during deinit) and DeinitBomb<T: ~Discardable & ~Copyable> (fatalError if the ~Discardable wasn't consumed out) with conditional Copyable conformances. These will have an unsafe internal implementation, but they don't do anything safe code shouldn't do, we are just restricting storing ~Discardable in Discardable to make this mistake harder and avoid complexity about always consume in Discardable types (the alternative just requires consuming ~Discardable members in deinit + rules about what you do before you consume yourself). Note that DeinitConsume is restrictive, it can't use an async consuming method...

If you see where this is going and object to the existence of DeinitConsume, DeinitBomb, see if you can find a definition for ~Discardable which makes it unsafe for them to exist, but does not lead to ~Discardable implies ~Escapable. I believe this is not really possible.

Thinking through avoiding these Deinit types...

If you forbid ~Discardable from being stored in Discardable, but allow it to escape, then you can store it in a global. Jumping ahead of the forget we will define, instead we will use a global, which stores a 'recursive forgetter'; it stores some ~Discardable T and another instance of the forgetter. It has a consume, takes T which conform to some protocol for consumption, and uses that to consume them (except, it won't do that). Any time we want to forget a ~Discardable, we store it in a forgetter, put the existing forgetter inside it, and then store it in the global. This seems equivalent from safety perspective to forgetting a DeinitBomb, but makes it harder to do reasonable things (storing Escapable, ~Discardable in a reference type). If we also forbid storing in a global, how does this differ from ~Escapable which depends on a local value?

Now we can write our own, safe, forget method in Swift:

class Cyclic<T: ~Discardable & ~Copyable> {
  let bomb: DeinitBomb<T>
  var cycle: Cyclic?

  init(_ t: consuming T) {
    self.bomb = DeinitBomb(t)
  }
}

/// Consume a ~Discardable value without calling a consuming method on it.
func forget<T: ~Discardable & ~Copyable>(_ t: consuming T) {
  let v = Cyclic(t)
  // close the cycle
  v.cycle = v
  // release our reference to v, refcount remains > 0
}

So, unsafe code clearly can't assume safe code won't forget to consume ~Discardable values before graceful exits, so far as upholding safety goes. When I say 'forget', I mean that you can forget to actually consume the value in the intended way. But we can also see that this forget implementation didn't violate the requirements of ~Discardable, it won't discard t without consuming it (the bomb would go off) yet this will not happen before a graceful exit. As I understand it, this is not sufficient for linearity, linearity requires consumption "eventually" for graceful exits, but this will happen never. You could also say this is sufficient for "static" linearity but not "dynamic" linearity. The type is used exactly once... for safety we are interested in knowing which values end up with exactly one consuming method use. I'll call this static linearity "weakly" linear.

But we have other protocols! What do these all mean together? Let's write a weird sort of truth table to think about it. Our names aren't going to take into account how "long" you get before you must do things, but our analysis of consumption will, since "forever" allows you to forget.

Name Discardable Copyable Escapable How many consumptions?
Unrestricted :white_check_mark: :white_check_mark: :white_check_mark: 0..N
Unrestricted :white_check_mark: :white_check_mark: :prohibited: 0..N
Affine :white_check_mark: :prohibited: :white_check_mark: 0..1
Affine :white_check_mark: :prohibited: :prohibited: 0..1
Weakly Relevant :prohibited: :white_check_mark: :white_check_mark: 1..N OR forget
Relevant :prohibited: :white_check_mark: :prohibited: 1..N
Weakly Linear :prohibited: :prohibited: :white_check_mark: 1 OR forget
Linear :prohibited: :prohibited: :prohibited: 1

Our "unrestricted" type is pretty normal, you can consume it as many times as you want, and you don't need to consume it. These are most types in Swift. It might be ~Escapable, such that you lose access to it after some scope, but that doesn't affect how many times you can consume it before then. "Affine" types can be consumed up to once; our existing ~Copyable types, @called(once) proposal is affine, since you can call it up to once. "Relevant" types can be consumed as many times as you want... but you must consume it before graceful exit. And "linear" types must be consumed exactly once.

We have "weakly" variants of relevant and linear types, what are these? This is maybe the wrong word from a theory perspective (since it doesn't refer to weakening) but I like it. They can be conceptualized as really powerful lints, but they don't increase the kinds of unsafe operations that can be safely encapsulated. For a weakly linear type, you can safely discharge your obligation via forget, so unsafe code can't rely on the linear property. But these weak variants are still very useful; in exchange for not being "strong", they can be stored in reference types and handled more ergonomically. If you've ever used @discardableResult, a weakly relevant type is the extremely "infectious" inverse of that; short of forgetting it, a weakly relevant result must be consumed at least once. A programmer cannot just store your returned value in a variable to discharge the obligation to do something with it, it is an error to not consume it somehow. Non @discardableResult (pretend it only considers consuming use) is easy to escape, weakly relevant / linear is "harder", but for all of them it is safe and expected to forget to always consume.

It might seem wrong from a theory perspective that we have this "weak" distinction, there shouldn't be multiple kinds of linear types. You can argue our "weakly linear" is linear up to leak / forget, and our "linear" is linear up to ungraceful exit, and that linear up to ungraceful exit is the important property. I think languages with linear types normally wouldn't permit cycles... debating the name distracts from the safety motivation to have these types, which is to prove that something must have happened.

Note that we already have some of these! We have the first 4 today. Affine types (especially ~Escapable) can already do a lot. If all you want is to ensure some operation happens, ~Copyable, ~Escapable ensures your deinit will run before graceful exits, unless you called a consuming method that used discard self, or deadlock / loop infinitely / similar. You can write code that assumes the deinit of a ~Copyable, ~Escapable value has run if the programmer is allowed to access the value it had a mutating dependence on. However, your deinit is not invoked by code, so it can't take parameters, return a value, throw an error that must be handled, perform async operations, and so on. In this way, a weakly linear type (which is Escapable) is an expressivity gain over this, although it is a correctness loss since it is now safe to never consume it, whereas it was impossible to forget to deinit something ~Copyable, ~Escapable when the lifetime of its dependency ends. Our "true" linear type is both an expressivity gain and a correctness gain (at a high ergonomic cost).

Although this table has the "fundamental" types, we can invent some more kinds by composing them. For exactly N consuming operations, we can use linear types which return more linear types, instantiating N variants which each return the next. We can also achieve exactly N, in any order, by returning a tuple of linear types, or at least N with a tuple of relevant types. We could also define relevant types using consuming operations on linear types that return more linear types... This might be easier to work with than the relevant types we'd get naively, since Swift may insert copies in surprising places.

You might object that ~Escapable still allows you to defer consumption "for a long time", but the important distinction is that the compiler is aware of this. forget is problematic because under separate checking, calling it appears to discharge the relevant or linear requirement. This is because the kinds of things we want to do with linear and relevant types use exclusive dependency to uphold safety. They are linear, and use their dependency on some other value to ensure that until the consuming operation is done, the value they depend on cannot be accessed. As long as you can keep both around, that is fine, and wherever the dependency "runs out" you'll need to discharge your obligation to the linear type. This is also how you make sense of holding a linear type over an await, or before going into an infinite loop; if the await blocks forever swift concurrency forward progress isn't happening, and we aren't getting a graceful exit or won't be able to access the depended on value for the rest of the program. The property we are chasing is a value which is consumed before the dependency can be accessed again OR graceful exit.

I have a lot more I want to say about these concepts, but I want to highlight that while it can be dynamically safe to go from weakly linear or weakly relevant to affine (this is what DeinitBomb and friends do) it can never be safe to go from relevant or linear to escapable affine via a type and enforce the requirement via deinit, if you think it is desirable to increase what safe code can be encapsulated. No "internal" dynamic check can detect forget and so no assumption of "eventually" can be made. An "external" check could, however; if all consumptions flipped a shared bit, then at the point where you assume the value has been consumed you could assert the bit has been flipped.

3 Likes

I do not worry about things like forget because their entire raison d’être is to preserve resources for some permanent purpose. I do not see it as unsafe that a linear type used in such a thing may never actually be consumed. You would not be able to prove that the consumption will happen by some specific point in the program’s static control flow, but you cannot hope to prove such thing with an escapable linear type anyhow. If your safety goal requires you to prove that something will have been consumed by a particular point (e.g. so that you can release its resources), you need to specifically be using a non-escapable linear type.

Additionally, I do not think “strongly linear” types are practical. Statically guaranteeing that such a type is never held in a context that will not be unwound during a graceful exit would be very cumbersome. It would impose a recursive hard restriction that containing types can never be stored in something that might e.g. participate in a reference cycle. Types would normally be assumed to permit this for usability, progressive disclosure, and source compatibility reasons, so using one of these strongly-linear types anywhere would set users up for a thankless annotation burden, one which would often conclude with a discovery that, ten layers up, some value is actually stored in a class property after all. Moreover, the requirement to actually unwind other contexts becomes a pretty significant burden on the compiler, the runtime, and the system’s ability to promptly exit, all in service of a relatively uncommon need to do something special during during a graceful exit. Having such values just register themselves dynamically with the system seems overall much simpler.

2 Likes

Hi John.

I want to ask for some clarification regarding the requirement for non-escapability here. Why shouldn’t an escapable linear type be allowed in the code below? Requiring ~Escapable here feels overly restrictive.

func process(foo: consuming Foo, completion: @Sendable @escaping (consuming Foo) -> Void) {
  if Bool.random() {
    foo.close()
  } else {
    let transferBox = NCTransferBoxClass(foo) // workaround until exactlyOnce closures  introduced for Task.init
    
    Task {
      let foo = transferBox.value.take()!
      completion(foo)
    }
  }
}

struct Foo: ~Copyable {
  consuming func close() {}
}

IIUC compiler can still guarantee exactly-once consumption without forcing Foo to be ~Escapable, even when transitioning across escaping boundaries, threads or isolation regions.
If every branch either locally consumes the resource or explicitly transfers ownership to another context, why must linearity need to be tied to ~Escapable? Are there ownership-tracking blockers?

Perhaps it makes sense to look at the ~Escapable requirement not as a fundamental theoretical necessity for linearity, but rather as a pragmatic / intentional semantic design constraint or perhaps simply a current implementation limitation that can be lifted in future.

I didn’t say linearity had to be tied to non-escapability. I said that you would also need non-escapability if you wanted to use linearity to prove that something specific happens before some point in the static control flow.

In your example, we know that foo is consumed on every path through process — linearity is satisfied — but we do not know the higher-level point that close is called before process returns. This is because the else branch consumes foo to pass it to NCTransferBoxClass.init, at which we can no longer reason locally about what happens to it. We as humans know that it is stored in the box, which is consumed to become a capture of the closure; the capture is then accessed within the closure body to retrieve the value of foo from the box, effectively transferring it to the closure body, where it can then be consumed to pass to close. But the compiler does not know that this is the same foo, and even if it did, close is called in an escaping closure on this path, and so we cannot reason that it is called before process returns.

The point is this: Linearity alone is useful as a way to prove that there is always some context that maintains its responsibility for explicitly consuming the thing. However, if you are trying to use this to prove that some ultimate action is taken before some specific point in the program — say, because you need to clean up some underlying allocations then, or because you need to hand an initialized buffer back to your own caller — then linearity alone cannot give you that, because escapability by definition allows use in ways with no fixed relationship to the scopes of the program. Thus for those specific uses, linearity needs to be coupled with non-escapability.

For what it’s worth, while all the code in process in your example locally obeys linearity, there is a possible problem with NCTransferBoxClass. Optional<Foo> must be a linear type and therefore must be consumed somehow in the deinit, since the box class is not itself linear. You can think of this as representing the dynamic possibility that there’s still a Foo there. This should be possible with a consuming switch and a precondition failure in the some case, but that does mean you have to have a box class specialized for this kind of dynamic linearity escape. Anyway, the box is entirely unnecessary in your example, you can just capture foo directly.

7 Likes

I'm saying 'safe' to mean 'sound' and checked by the compiler. Sound code doesn't exhibit undefined behavior, when combined with any other sound code. Safe code is always sound, or it wouldn't compile (barring all the obvious exceptions, unfortunately :downcast_face_with_sweat:). Unsafe code can (and should!) be sound, but it requires the programmer to pay close attention. In particular, the programmer makes sure their unsafe code never assumes more than soundness of the code they didn't write. I think about it like this (rust nomicon).

We can define it and say it is sound to not consume a linear type, but I don't think this is useful for writing unsafe code. What is the "point" of such a linear type? I think it makes complete sense (and is unavoidable) to say it is sound to not consume a weakly linear (escapable linear) type though.

I understand a linear type to be defined as a type which must be used (consumed) exactly once before a graceful exit. It should be unsound to avoid that. We shouldn't call a type linear if it doesn't have that property.

I think we completely agree on what can be done with the different kinds of types, and only disagree about what conversions can be done (with what static checking) and on which of the types should be called what.

This is less than exactly once. What makes this meaningfully different from an affine type in terms of what may be assumed? All I see is the ability for the compiler to use a shared trapping deinit, which is a code size win but doesn't change anything about safety. In practice, a weakly linear type and an affine type allow the same assumptions for unsafe code; used at most once. The reason they were not used is different (the affine type can be dropped, the weakly linear type must be stored in a global, a cycle, etc), but the effect is the same.

This doesn't mean they have the same expressiveness! The weakly linear type forces the programmer to be much more explicit about consumption, and pushes the programmer strongly towards doing it.

With a careful definition I think we could mitigate issues with unwinding. (Afaik) it is UB to unwind C++ or Objective-C exceptions through Swift frames, and we don't allow you to recover from fatal errors. Rust has a ton of complexity here because you can't assume that panicking stops the program, and it is sound to panic, and panic is done via unwinding so your unsafe code needs to be "exception safe" and uphold memory safety even if the code it is interacting with panics and then recovers. Panicing is like our fatalException and isn't externally visible. See unwinding, and Vec::push_all for an example of what this leads to. Safe code in Swift can panic, but cannot recover. (Afaik) fatalError does not unwind, and so it would actually be safe to implement push_all in this way in Swift, since the uninitialized memory cannot be observed by other code or dropped. In the same way, I think we can avoid reasoning about unwinding. We have errors, but they only unwind in the sense of deinit and defer, are essentially return values, and are fully visible to the CFG. Is the concern a future unwinding feature?

The point I'm trying to get at is that linearity with escapability (weak linearity / linearity up to forget) is not different to affinity from a safety perspective (excluding the need to synthesize a deinit). Maybe it would be a little different if we had a way to query reachability, but we don't. Knowing some context maintained responsibility for consumption (that it is not required to act on) is not useful for increasing what can be assumed about sound code, to write better unsafe code.

Called exactly once implies (to me) that ultimate action (calling) is taken before some specific point in the program (with that specific point being graceful exit).

I'm not arguing we should add such types (I think they'd be neat but that's probably not enough motivation). But if we only introduce weakly linear types (that don't have these restrictions) then called at most once would be sufficient to consume them, if we wrap them in a type that fatalErrors when it is discarded. We can introduce some "called exactly once" that is as strong as these weakly linear types, but there is no obligation to only consume weakly linear types there, it is only a lint, which can be defeated in safe code.

If we want to leave open the option to add linear types, we can introduce called exactly once, but I think we should treat it as what you call strongly linear, and not allow a dynamic conversion that weakens that. An external check like I describe in the last post doesn't reduce the assumptions that can be made... this would be the case if you imagine withDynamicCallCountChecking(linear, body) taking a linear closure, giving a weakly linear closure to body, and trapping after calling body if it wasn't invoked. The thing we cannot do is convert a linear closure to a closure that traps on the second call, we need to also trap when it isn't called. Truly escaping uses can't do this conversion, which is necessary; they can't be proven to actually call the function before graceful exit. We could still have this conversion if it was unsafe, although we would need a way to propagate the lifetime dependency (like into a relevant Task handle that needs to be awaited, which might even be something which could be expressed safely).

I think it would be fine to add weakly linear closures for the codesize win of sharing a trapping deinit like you mention, and to make the ergonomically nice weakly linear type easy to consume there. I don't think this type can be called 'called exactly once' though, if sound code can avoid calling it / it is sound to never consume it.

3 Likes