[SR-8751] Crash when associatedtype starts with a letter before O in certain circumstances

[swift-ci]

Previous ID	SR-8751
Radar	rdar://problem/44458222
Original Reporter	neightchan (JIRA User)
Type	Bug

Environment

Version 10.0 beta 3 (10L201y)

Additional Detail from JIRA

Votes	0
Component/s	Compiler
Labels	Bug
Assignee	None
Priority	Medium

md5: 508bd4695a04093b16b45839c54edca3

Issue Description:

The following code compiles without issue:

protocol TreeProtocol {

    typealias NodeProtocol = _TreeNodeProtocol
    associatedtype Node : NodeProtocol where Node.Tree == Self
    associatedtype ValuesTraversedBreadthFirst : Sequence = FooVals<Self> where ValuesTraversedBreadthFirst.Iterator.Element == Node.Val
    
    var root: Node? { get }
    
}

protocol _TreeNodeProtocol {

    associatedtype Tree : TreeProtocol where Tree.Node == Self
    associatedtype Val

    var value: Val { get }
    var children: [Tree.Node] { get }

}

struct Foo<V> : TreeProtocol {

    struct Node : _TreeNodeProtocol {
        typealias Tree = Foo
        typealias Val = V

        var value: Val {
            fatalError()
        }
        var children: [Tree.Node] {
            fatalError()
        }
    }
    
    var root: Foo<V>.Node? {
        fatalError()
    }

}

struct FooVals<F : TreeProtocol> : Sequence {

    struct Iterator : IteratorProtocol {
        
        typealias Element = F.Node.Val
        
        mutating func next() -> F.Node.Val? {
            fatalError()
        }
    }
    
    func makeIterator() -> FooVals<F>.Iterator {
        fatalError()
    }

}

It stops compiling if you change the name of the ValuesTraversedBreadthFirst associatedtype to a word that starts with a letter before O.

For example, the following code crashes:

protocol TreeProtocol {

    typealias NodeProtocol = _TreeNodeProtocol
    associatedtype Node : NodeProtocol where Node.Tree == Self
    associatedtype NValuesTraversedBreadthFirst : Sequence = FooVals<Self> where NValuesTraversedBreadthFirst.Iterator.Element == Node.Val
    
    var root: Node? { get }
    
}

protocol _TreeNodeProtocol {

    associatedtype Tree : TreeProtocol where Tree.Node == Self
    associatedtype Val

    var value: Val { get }
    var children: [Tree.Node] { get }

}

struct Foo<V> : TreeProtocol {

    struct Node : _TreeNodeProtocol {
        typealias Tree = Foo
        typealias Val = V

        var value: Val {
            fatalError()
        }
        var children: [Tree.Node] {
            fatalError()
        }
    }
    
    var root: Foo<V>.Node? {
        fatalError()
    }

}

struct FooVals<F : TreeProtocol> : Sequence {

    struct Iterator : IteratorProtocol {
        
        typealias Element = F.Node.Val
        
        mutating func next() -> F.Node.Val? {
            fatalError()
        }
    }
    
    func makeIterator() -> FooVals<F>.Iterator {
        fatalError()
    }

}

/../../path/to/main.swift:11:10: warning: redundant conformance constraint 'Self.Node': '_TreeNodeProtocol'
protocol TreeProtocol {
         ^
/../../path/to/main.swift:14:27: note: conformance constraint 'Self.Node': '_TreeNodeProtocol' written here
    associatedtype Node : NodeProtocol where Node.Tree == Self
                          ^
/../../path/to/main.swift:11:10: warning: redundant conformance constraint 'Self.NValuesTraversedBreadthFirst': 'Sequence'
protocol TreeProtocol {
         ^
/../../path/to/main.swift:15:51: note: conformance constraint 'Self.NValuesTraversedBreadthFirst': 'Sequence' written here
    associatedtype NValuesTraversedBreadthFirst : Sequence = FooVals<Self> where NValuesTraversedBreadthFirst.Iterator.Element == Node.Val
                                                  ^
/../../path/to/main.swift:11:10: warning: redundant same-type constraint 'Self.Node.Tree.NValuesTraversedBreadthFirst.SubSequence' == 'Self.Node.Tree.NValuesTraversedBreadthFirst.SubSequence.SubSequence'
protocol TreeProtocol {
         ^
/../../path/to/main.swift:11:10: note: previous same-type constraint 'Self.Node.Tree.NValuesTraversedBreadthFirst.SubSequence' == 'Self.Node.Tree.NValuesTraversedBreadthFirst.SubSequence.SubSequence' implied here
protocol TreeProtocol {
         ^
error: Illegal instruction: 4

[belkadan]

Fun result of canonicalizing generic signatures by sorting alphabetically. cc @DougGregor

@swift-ci create

[swift-ci]

Comment by Graydon Hoare (JIRA)

In particular the crash here is infinite recursion overflowing the stack. Representative segment of backtrace:

swift::ProtocolConformance::getTypeWitnessAndDecl() const at ProtocolConformance.cpp:227
swift::ProtocolConformance::getTypeWitness() const at ProtocolConformance.cpp:234
getMemberForBaseType() at Type.cpp:2774
substType() const at Type.cpp:2987
swift::Type::transformRec() const at Type.cpp:3377
substType() at Type.cpp:2958
swift::Type::subst() const at Type.cpp:3043
swift::SpecializedProtocolConformance::getTypeWitnessAndDecl() const at ProtocolConformance.cpp:958
swift::ProtocolConformance::getTypeWitnessAndDecl() const at ProtocolConformance.cpp:227

[slavapestov]

Related to #49273 and rdar://69901318