[Pitch] Noncopyable Generics

Evolution Pitches
42

I think theoretically this can be done by deferring an error to an implementation of P. Although I'm not in favor of this approach, just saying.
Think of this like if func f() -> G<Self> is a legit requirement of the protocol. And the protocol doesn't impose any other restrictions apart from itself (e.g. it doesn't refine Copyable).
Then when you write an implementation, you have to provide f(), but you can't:

struct PImpl: P, ~Copyable {
  func f() -> G<Self> { // This is where the compiler might emit an error, cause now Self is known to be ~Copyable
  }
}

In other words PImpl can't conform to P and not conform to Copyable simultaneously because of f() and its return type (and not because P refines Copyable).

The same goes for all the other restrictions of non-copyable types. If there's a static function that take Self as an argument without specifying ownership type - only copyable types would be able to conform to the protocol, as there's no default.

(But I'm in favor of early diagnostic.)

43

On the other hand, I think that would actually be a great idea.

Imagine a bit later someone rewrites G like this to make it friendly to non-copyable types:

struct G<T: ~Copyable>: ~Copyable {}
extension G: Copyable where T: Copyable {}

Now people will complain that protocol P forces them to make their type Copyable even though it's no longer required because of the change in G. Users will ask for P to adopt : ~Copyable.

So I suppose it's a bit strange that we would have a protocol with a function that can't be implemented on some types (types which were explicitly made non-copyable). But to me it'd be even stranger if all the existing protocols out there could not be used with non-copyable types until they are updated with : ~Copyable. The vast majority of protocols don't require a copyable Self for their implementation, making the annotation burden pretty high for early diagnostics in a few edge cases.

4 Likes
44

The new issue is that the unsatisfiable constraint is invisibleā€”as I said earlier, if Iā€™m holding a value of a P-conforming type, the surprising thing is that I canā€™t pass it as an argument to a parameter of type T: P, not that I canā€™t pass it to a type of T: P & Copyable, similarly to how it was a source of repeated surprise and confusion before implicit existential opening that I couldnā€™t pass a value of type P.

2 Likes
45

It's a bit strange either way, I think. The way the ~Copyable constraint fails to propagate is unlike any other constraint in the language AFAIK.

But I have to admit that protocols will need to explicitly opt-in to supporting non-copyable types. Otherwise, protocol evolution becomes too limited.

Currently, adding a protocol requirement is a source/binary-compatible change if you also provide a default implementation. If it were possible for non-copyable types to conform, default implementations used for that purpose would need to consider non-copyable types as well, and if such a default implementation were not possible, certain requirements (e.g. f -> G<Self>) could not safely be added at all.

It is kind of unfortunate because it means non-copyable types (and possibly also future non-escapable types) will always be quite limited in terms of generics support, but it's also important that we don't limit protocol evolution in this way.

Perhaps the syntax could do with tweaking.

protocol P: ~Copyable { ... }

It's a bit confusing that this means "P supports ~Copyable" (but doesn't propagate that support) rather than "P requires ~Copyable" (and propagates that requirement).

3 Likes
46

I suppose it depends on your definition of "safely". The default implementation could just call fatalErrorā€¦ which is memory-safe. :wink:

But you make a valid point. If default implementations need to care about non-copyable types when evolving the protocol, then whether the protocol needs a copyable Self or not needs to be stated up-front to prepare for that evolution. At minimum, any public protocol would need to care about this.

I suppose we could introduce a @frozen protocol which would not have this issue, but at this point it's simpler to just mark it : ~Copyable.

Either that, or it'll put a bit of pressure for people to add : ~Copyable to all their protocols and it'll become some kind of standard boilerplate code. Probably we will get an inconsistent mix of both.

3 Likes
47

I think the biggest problem is to think about ~Copyable as a constraint when itā€™s in fact not a constraint. Iā€™d say itā€™s rather a constraint-remover (unconstraint?). I think that itā€™s a bit unfortunate that we used the same syntax for this as for real constraints, which makes this misconception easy to make. But the ship has probably sailed on the syntax.

5 Likes
48

I think the key thing, though, is that the behavior of ~Copyable here is exactly the same as the lack of any other protocol constraint on a generic type. A <T: Equatable> isn't statically Hashable, but it isn't statically not Hashable either, you don't know one way or another. Similarly, <T: ~Copyable> is suppressing the implicit Copyable constraint, but that doesn't give you static information that the type isn't copyable, you don't know either way. So that's where the "maybe Copyable" reading comes from.

10 Likes
49

Agreed. I think my preferred reading for ~ is "without" (or more precisely: "without assuming"), but talking about the absence of a constraint is necessarily fraught in human language.

6 Likes
50

I was joking before, but ā€œnot implicitly copyableā€ really is what it means.

2 Likes
51

What a good point! So really the ONLY thing P: ~Copyable does in practice is disallowing things that return Self in the actual protocol. If you had a protocol that did that and you were to try to create an extension that conformed to ~Copyable, it would have to have an error like you said.

Honestly that doesnā€™t really seem that different from the proposal. I think of the two cases:

  • Adding ~Copyable conformance retroactively
    • Youā€™d have an error either way and not have any way around it.
  • Creating a new protocol with a ~Copyable extension at the start.
    • Here you would also hit an error.

Is there another case? Someone else adding a ~Copyable conformance outside your module and it breaks when you add a Self returning function later? @Slava_Pestov, would it be that big of a deal to do it like @dmt said?

52

Not necessarily. Consider this admittedly contrived scenario in which AdditiveArithmetic: ~Copyable:

struct OwnedNumber: ~Copyable {
  private var value: Int
}

extension OwnedNumber: AdditiveArithmetic {
  static func + (lhs: borrowing OwnedNumber, rhs: borrowing OwnedNumber) -> OwnedNumber {
    .init(value: lhs.value + rhs.value)
  }
}

More generally, (non-consuming) methods returning Self would be guaranteed to return a new instance, since they obviously can't return the current one.

I'm not sure whether this would be legal off the top of my head:

extension OwnedNumber {
  consuming func stupidNop() -> OwnedNumber {
    return self
  }
}

If so, there is absolutely no reason why a consuming func couldn't return self.

1 Like
53

That's not quite it. Here is an analogous example in the Swift 5.9 language:

protocol P /* : ~Hashable */ {
  static func foo(_: Set<Self>)
}

P doesn't state a Self: Hashable requirement, however in practice any conforming type must be Hashable because Set<Self> is otherwise malformed. So for to work, you must explicitly state the requirement:

protocol P: Hashable {
  static func foo(_: Set<Self>)
}
3 Likes
54

This brings up an adjacent point of interest: in a number of scenarios, the Hashable constraint is currently implicitly inferredā€”

func f<T, U>(_: Dictionary<T, U>) { /* ... */ }
/* T: Hashable */

Would be curious to reckon systematically where this proposed design diverges from the design of implicit Hashable.

55

Right. Here, we're inferring T: Hashable by looking at the types appearing---for lack of a less implementation-centric term---as immediate child nodes of the function declaration in the AST.

This means the inference does not extend to the function's body:

func f<T>() { // not T: Hashable
  Set<T> 
}

So if we generalized the above to protocols, then I think

protocol P {
  func f() -> Set<Self>
}

Would mean this (which of course is not allowed)

protocol P {
  func f() -> Set<Self> where Self: Hashable
}

and not this:

protocol P where Self: Hashable {
  func f() -> Set<Self>
}

And indeed, we accept this:

protocol P {
  func f<T>(_: Set<T>) // where T: Hashable
}
1 Like
56

One of the goals of this pitch is to describe how an implicit Copyable is the right thing to assume for every type you declare in the language. The constraint type ~Copyable is the way you remove that assumption. If you used ~Copyable on a type but Copyable still ends up being unconditionally required of that type, then it's an error:

protocol I {} // <- has an assumed Copyable requirement

struct S: I, ~Copyable {}
// error: S has ~Copyable but is required to be Copyable

let _: any I & ~Copyable
// error: existential has ~Copyable but is required to be Copyable

func test<T: I & ~Copyable>(_ t: T) {}
// error: T has ~Copyable but is required to be Copyable

enum E: ~Copyable {}
extension E: Copyable {} 
// error: E has ~Copyable but is required to be Copyable

The last one is interesting. You can have E conditionally conform to Copyable, but not unconditionally. In addition, if any of those types have Copyable requirements coming in from an extension default, those requirements get cancelled out / removed. So perhaps the terminology around inverses / ~Copyable should better emphasize the nature of them only operating on default / implicit / assumed requirements.

Perhaps the ~ should be read "remove default", thus ~Copyable is "remove default Copyable"

57

Right, this is a bit of a wrinkle I'd like to discuss. Here's an example of what @xwu is talking about:

protocol A: ~Copyable {}

struct S: A, ~Copyable {}

func use(_ a: some A) {}
// without sugar = func use<T: A & Copyable>(_ a: T) {}

use(S()) // error: S does not conform to 'Copyable'

That some A, like any A, is actually introducing a fresh type variable which assumes a default Copyable requirement. So, following the same principle of "Copyable is everywhere" that the pitch takes, we really are defining some X to be some X & Copyable, and any X as any X & Copyable, etc.

While that is at least consistent, I think we could do better for type parameters if we make heavier use of programmer-defined defaults. Suppose we were to say that only unconstrained type parameters have a default Copyable requirement. For other ones that are constrained, they gain whichever defaults belong to that type constraint. This means that the protocol A above would be rewritten to look like this, to get the same behavior in that example:

protocol A: ~Copyable {
  default extension where Self: Copyable
}

Otherwise, for other protocols, we get a behavior that people might expect:

protocol B: ~Copyable {}

struct R: B, ~Copyable {}

func use(_ a: some B) {}
// without sugar = func use<T: B>(_ a: T) {}

use(R()) // ok

The parts that I'm stuck on with this idea is how far to take it. We could limit it to just generic parameters, but Self in a protocol is a generic parameter too. So it would be weird to have C become noncopyable here because Self became constrained:

protocol C: B {}

In theory it could apply to other nominal types, too. So R above wouldn't need to write ~Copyable in its inheritance clause. There's a big downside to that, though: it would become very nonobvious that R is noncopyable if the ~Copyable were omitted:

struct R: B {}

This is in-part why I decided against this idea: if the rule that Copyable implicitly appears everywhere is at least consistent, people who want to make use of noncopyable generics can understand where ~Copyable needs to be written.

1 Like
58

This is a good point; there are definitely corner cases where the rule chooses the wrong default, but it's also easy to correct it:

struct J<T: P & ~Copyable>: Copyable {
  var u: T.U // T.U is known to be copyable
}

I don't know whether the problem you describe would be a mistake that goes beyond one attempt to compile the program and get errors about the lack of Copyable. The reason why it was lost could be buried somewhere in the where clause as well:

struct J<T> 
  where T: P, T: ~Copyable {
  // ..
}

My hope was that with appropriate diagnostics, the reason why some type is noncopyable would always be pointed-out (in this case, ideally, pointing at the ~Copyable constraint in the where clause).

Let me try to give a bit more background on my reasoning for the rule in the pitch, since it seems controversial:

The goal behind this implicit conditional-copyable conformance rule is to reduce the visual clutter of writing:

// Example 1
enum TestResult<Result: ~Copyable>: ~Copyable {
  case lostConnection
  case coffeeWentStale
  case success(Result)
}
/// ... perhaps many lines later ...
extension TestResult: Copyable where Result: Copyable {}

instead of simply

// Example 2
enum TestResult<Result: ~Copyable> {
  case lostConnection
  case coffeeWentStale
  case success(Result)
}

every time you want to write a generic value type that can contain something noncopyable, and you want the maximum flexibility for users of your type in the case when it has nothing noncopyable. The pitched rule basically reserves a fully-written-out enum E<T: ~Copyable>: ~Copyable for when you want maximum control over when it is copyable, if ever. That maximum flexibility scenario sounded to me like the most common case.

Example 1 seems like a poor experience: we would have people always writing or looking for that extension of TestResult to determine if it can ever be copied, because of it having an explicit ~Copyable on it. It always becomes an existence search.

In contrast, Example 2 is still clear by inspection that TestResult can be Copyable, as there's nothing written on TestResult about it's copyability. It just becomes conditional instead.

While I can be convinced to live without this implicit conditionally-Copyable behavior, in practice I think writing value types like TestResult will be annoying without it.

59

Yes, I got it from the pitch.

You mean there will be diagnostic at client side, when an instance of J<NC> is being copied? This would be helpful of course, but not ideal. I imagine there could be circumstances when it's too late, i.e. if J is from a third party library, and it was tested on a copyable T. Then a fix would be deferred by some time. It would be better if this mistake couldn't happen at all.

I agree that in most cases T is exactly that type that will be used in a stored property, but it's not 100%.
My suggestion is to reduce application scope of the rule: Apply the rule, only if for each non-copyable generic parameter there's at least one stored property which type is also conditionally copyable depending on the parameter.
This would allow usage of the rule in most cases.

struct K<T: ~Copyable> { // ok, the rule can be applied
  var x: T
}
struct L<T: ~Copyable> { // ok
  var x: K<T> // K<T> is conditionally Copyable
}

And produce an error, when the rule can't be applied. Something like "Unable to synthesise conditional Copyable constraint, because the type doesn't contain a stored property with conditional Copyable conformance depending on 'T'":

struct J<T: P & ~Copyable> { // error
  var u: T.U // Copyableness is independent from T
}
struct Q<T: ~Copyable> { // error
  var x: T { ... } // not a stored property
}
struct W<T: ~Copyable> { // error
  var x: AnotherModuleType<T> // we can't guarantee AnotherModuleType<T> will always be conditionally Copyable, even if now it is
}

Notice that L and W examples are almost identical, but for L we can safely synthesise conditional conformance, because K is in the same module (or package): if it will be upgraded from "conditionally copyable" to "always copyable" in the future - L will be recompiled as well and produce an error, allowing to make appropriate fixes to L.
But in case of W, AnotherModuleType is compiled independently from W. If we will allow the synthesis here, and AnotherModuleType is upgraded to "always copyable" - it would be a source breaking change, but it shouldn't be.