Swift type checking is undecidable

[dabrahams (Dave Abrahams)]

@Slava_Pestov

Yeah, it's pretty interesting. As @scanon explains, once you add "enough" constraints to make the nested type graph finite, you can completely solve the problem; but also, in the absence of protocol "where" clauses, the problem is trivially solvable too (every nested type is unique). It's the uncanny valley in between where you have some same-type constraints but some infinite structure as well that we run into difficulties.

Considering that we want to change the language semantics in a way that will force some ambiguities to be diagnosed/resolved at runtime when infinite types are allowed, I wonder whether the right answer to both problems is to close the infinite type door.