[SR-263] Implement a general solution to prevent deadlocks when generic types rely on their own metadata recursively

[slavapestov]

Previous ID	SR-263
Radar	None
Original Reporter	@slavapestov
Type	Bug
Status	Closed
Resolution	Done

Additional Detail from JIRA

Votes	1
Component/s	Compiler, Standard Library
Labels	Bug, Runtime
Assignee	@rjmccall
Priority	Medium

md5: f708bd18dd8ca57bb3b0279f9380be5e

blocks:

• SR-257 Resilient value type support -- umbrella bug

is duplicated by:

• SR-1686 Program with recursive class crashes because of “cyclic metadata dependency”
• SR-1722 Recursive enum (via Array as indirection) compiles but causes runtime deadlock.
• SR-3779 Program with struct nested in generic struct crashes because of “cyclic metadata dependency”
• SR-4383 Runtime Error: cyclic metadata dependency detected, aborting
• SR-4732 "Tree" enum crashes at runtime "cyclic metadata dependency detected, aborting"
• SR-5790 Recursive generic class causing runtime error
• SR-5828 Cyclical metadata graphs should either not be formed or be a compile failure
• SR-2549 [CRTP] Non-generic class inheriting from a generic class with Self as generic parameter locks execution
• SR-4358 Generic trouble

relates to:

• SR-5828 Cyclical metadata graphs should either not be formed or be a compile failure

Issue Description:

[Description by John McCall]

Recent changes taught the compiler to avoid emitting references to the type metadata for an ivar that the compiler can statically compute a fixed size of. This permits a large number of recursive class structures to be defined; however, there are some missing cases:

1. It does not suffice when the recursive metadata reference is an incidental aspect of a dependently-sized type expression. For example:

class Foo<T> {
var x: (T, Foo<T>)
}

Tuples, and fragile types in general, could be special cased; however:

2. It does not suffice when the recursive metadata reference is used in a type argument of a resilient type. For example:

class Foo<T> {
var x: ResilientStruct<Foo<T>>
}

This will provably not be an infinite type at runtime because Foo is a class. If Foo were a struct, it could still quite easily be finite, depending on how the type parameter is used.

3. It does not suffice when the recursive metadata reference appears somewhere other than an ivar's layout. For example:

class Bar<T> : Base<Bar<T>> {}

The correct fix is to develop a more complicated model that permits runtime type metadata to be briefly "incomplete" during instantiation.

[slavapestov]

rdar://18157434

[rjmccall]

Fixed in a whole series of PRs; expected in 4.2.

[rjmccall]

There's an incomplete case here involving non-generic types which is unfortunately being exposed a lot because of the resilient-ification of Foundation types like `Date`, but the main piece of work is done.