[swift-evolution] Inconsistencies in recursive types

[Jaden Geller]

Comments inline:

> On Mar 13, 2017, at 6:38 AM, Dimitri Racordon via swift-evolution <swift-evolution at swift.org> wrote:
> 
> Hello swift-evolution,
> 
> I noticed there’s some inconsistencies with recursive types and how the compiler handles them. Consider the following cases:
> 
> 
> 1. Swift is right to refuse compiling this, since there’s no way to initialise an instance of `First `:
> 
> struct First {
>     let item: First
> }
> // Error: Value type 'First' cannot have a stored property that references itself
> 
> However, the message suggests more a compiler limitation rather than the actual impossibility to initialize the declared type.
> 

This is a compiler limitation that isn’t going to go away. Structs are value types whose size is equal to the sum of their property sizes. Here, we have a circular dependency, so it is impossible to compute the size.

This is not an arbitrary restriction. Consider:

struct List<T> {
    var head: T
    var tail: List<T>?
}

The size of `List` is infinite! Every `Optional<T>` must be big enough to store the type `T` in case the value is not `nil`. Thus, `List` must be big enough to store a `T` AND another list (of the same size):

size(of: List<T>) = size(of: T) + size(of: List<T>)

It’s easy to see that, assuming `size(of: T)` is non-zero, it is impossible to satisfy this constraint. Yes, Swift could special case the case where there are no other members, but this would be entirely useless (you can’t store state) and would considerably muck up the semantics.

Note that enums allow members to be marked `indirect`. This would be a reasonable feature for Swift to eventually support for structs as well. In this case, the indirect member would be the size of a pointer, so the size would be statically known and satisfied.

> 
> 2. Swift is also right not to compile this, but the error messages are even less insightful:
> 
> struct First {
>     let item: Second
> }
> // Error: Value type 'First' cannot have a stored property that references itself
> 
> 
> struct Second {
>     let item: First
> }
> // Error: Value type 'Second' cannot have a stored property that references itself
> 
> The problem isn’t that the value types reference themselves. Instead, the problem is that there’s a cyclic dependency between `First` and `Second` that makes it impossible for neither of these structures to be instantiated.
> 

This is an identical problem to #1. The error message could probably be improved. This isn’t a “reference” in the sense of a pointer, but in the sense that there is literally a dependency. 

> 
> 3. Swift should let me do that:
> 
> struct First {
>     let item: First?
> }
> 
> The compiler prevents me to declare the above struct, even if there actually is a way to initialise an instance of `First` (e.g. `First(item: nil)`). The message is identical to that of case #1 (maybe it actually is a compiler limitation after all?)
> 

This is an identical problem to #1. An option does *not* introduce any indirection. Swift will however allow the following:

struct First {
    let item: [First]
}

This is because `Array<T>`—if you look at its declaration—does not *directly* store any type `T`. Instead, it stores a pointer to a buffer holding `T`s, allocated at runtime. These semantics may be a big confusing at first, but this is the tradeoff for the better performance value types can sometimes bring.

> 
> 4. Swift shouldn’t compile this:
> 
> class First {
>     let item: First
>     init(item: First) {
>         self.item = item
>     }
> }
> 
> Like in case #1, there’s no way to instantiate `First`. The fact that it’s a reference rather than a value doesn’t change the problem.
> 

This is not a bug IMO. It is not the compiler’s job to prevent you from compiling code that includes a type that cannot be instantiated.

Unlike the previous cases, the compiler actually *can* generate code for these types. You _could_ even unsafely instantiate these types. In the previous cases, the compiler could not compute the size of the types.

> 
> 5. Similarly to case #4, Swift shouldn’t compile this:
> 
> indirect enum First {
>     case item(First)
> }
> 

Ditto #4.

> 
> 6. Cases #4 #5 could be written like case #2, and should also raise compilation errors.
> 

Ditto #4.

> 
> Does someone know if these issues have already been discussed and/or addressed?
> 
> Thanks,
> Dimitri Racordon
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution


I hope I was able to clear up your confusion. Let me know if you have any other questions.

Cheers,
Jaden Geller

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170313/82f09722/attachment.html>