There are probably multiple things going on here. CC @huonw

There are indeed multiple things going on here. Please open another bug for needing to write typealias B = _A even though it defaults to Self, and this one can focus on the crash.

I believe the crash is might be because the U2 typealias is scoped within P4, which is conditional, and, I think the crashing extension has different constraints to the conformance of S to P4. Reduced (by creduce):

protocol a {
    associatedtype b 
    associatedtype c
    }
protocol d: a where b: a{
    typealias e = b.c
}
struct f<b, c>:  a {}
extension f: d where b: a{}
struct g<h, i>{}
extension f {
    var j: g<e, c> {
        fatalError()
    }
}

Adding where b: a to extension f that example lets the code compile fine (as does changing the bounds on the original extension S to return f(A<U2, U>.self)).

// if the extension that crashes is commented out and replaced with the other variant the
// "Same-type constraint 'T' == 'S<_A, T.U>' is recursive" error is produced
// it seems like this should be valid code.

I think the recursion is hinted at by the expanded form: the second generic parameter (called U) of the S has to be T.U, that is, the U nested type of the type T, but that type T is the S we're looking at, so to work out what T is equal to, we have to know what it is equal to. In this specific case, it's even worse than just that plain recursion, because T.U is being passed to the parameter U that defines what the associated type U is.

@swift-ci create

Comment by Matthew Johnson (JIRA)

I think the recursion is hinted at by the expanded form: the second generic parameter (called U) of the S has to be T.U, that is, the U nested type of the type T, but that type T is the S we're looking at, so to work out what T is equal to, we have to know what it is equal to. In this specific case, it's even worse than just that plain recursion, because T.U is being passed to the parameter U that defines what the associated type U is.

Here's where I think this is going wrong. The `S` in the same-type constraint is not the same `S` that is getting extended. For a more concrete example, let's consider nested arrays. The following produces the same error as above:

protocol ElementProtocol {
    associatedtype BaseElement: BaseElementProtocol
}
protocol BaseElementProtocol: ElementProtocol where BaseElement == Self {}
protocol ArrayProtocol {
    associatedtype Element: ElementProtocol
}
protocol NestedArrayProtocol: ArrayProtocol where Element: ArrayProtocol, Element.Element.BaseElement == Element.BaseElement {
    associatedtype BaseElement = Element.BaseElement
}
extension Array: ElementProtocol where Element: ElementProtocol {
    typealias BaseElement = Element.BaseElement
}
extension Array: ArrayProtocol where Element: ElementProtocol {}
extension Array: NestedArrayProtocol where Element: ElementProtocol, Element: ArrayProtocol, Element.Element.BaseElement == Element.BaseElement {}

// The following gives an error "'BaseElement' is not a member type of 'Element'" despite the
// presence of the `Element: ElementProtocol` constraint.
// It also gives a "Redundant conformance constraint 'Element': 'ElementProtocol'" warning.
// The constraint does not currently change compiler behavior which is in line with the warning.
// However, the constraint really should bring `Element.BaseElement` into scope.
// This also gives "Same-type constraint 'Element' == 'Array<Element.BaseElement>' is recursive"
// The intent of this code is to be equivalent to Self == Array<Array<Element.BaseElement>>.
// The constraint refers to the inner array and the extension refers to the outer array.
extension Array where Element: ElementProtocol, Element == Array<Element.BaseElement> {}

The immediate algorithm that comes to mind for checking whether a specific Array type meets this constraint is to first verify `Element: ElementProtocol, Element`. Then evaluate `Element.BaseElement`. Then check whether `Element == Array<Element.BaseElement>`.

For `Array<Int>` with `extension Int: BaseElementProtocol {}` in scope the compiler would see that `Int: ElementProtocol` is true. Then it evaluate `Int.BaseElement == Int`. Then it would see that `Int != Array<Int>` so the constraint extension does not apply.

For `Array<Array<Int>>` with `extension Int: BaseElementProtocol {}` in scope the compiler would see that `Array<Int>: ElementProtocol` is true. Then it evaluate `Array<Int>.BaseElement == Int`. Then it would see that `Array<Int> == Array<Int>` so the constraint extension does apply.

For `Array<Array<Array<Int>>>` it would proceed as for `Array<Array<Int>>` but in the final step would see that `Array<Int> != Array<Array<Int>>` so the extension does not apply.

Please let me know if there is any problem with the above logic. If is sound, let me know if I should file a separate bug for this error.

FWIW, I encountered another crash while working up the above example:

protocol ElementProtocol {
    associatedtype BaseElement: BaseElementProtocol = Self
}
protocol BaseElementProtocol: ElementProtocol where BaseElement == Self {}
protocol ArrayProtocol {
    associatedtype Element: ElementProtocol
}
protocol NestedArrayProtocol: ArrayProtocol where Element: ArrayProtocol, Element.Element.BaseElement == Element.BaseElement {
    associatedtype BaseElement = Element.BaseElement
}
extension Array: ArrayProtocol where Element: ElementProtocol {}
extension Array: NestedArrayProtocol where Element: ElementProtocol, Element: ArrayProtocol, Element.Element.BaseElement == Element.BaseElement {
    // with the typealias uncommented you do not get a crash.
    // typealias BaseElement = Element.BaseElement
}

I have created another ticket for that crash here: https://bugs.swift.org/browse/SR-8324