22064912: Swift 2.0b4: swiftc infinite loop with type conforming to semi-mutually-recursive protocol

[openradar-mirror]

Description

Summary:
More infinite loopage.

Steps to Reproduce:

1. This code:
   protocol FixpointType: _FixpointType {
   typealias Algebra : AlgebraicType
   }

protocol FixpointType {
typealias Algebra
init( : Algebra)
var out: Algebra { get }
}

protocol AlgebraicType {
typealias Recur : _FixpointType
}

enum Expr<T: FixpointType>: AlgebraicType {
typealias Recur = T
case Null
func map(transform: T -> U) -> Expr { return .Null }
}

func out<Fix: FixpointType>(v: Fix) -> Fix.Algebra { return v.out }

func cata<T, Fix: FixpointType where Fix.Algebra == Expr>(f: Expr -> T)(_ term: Fix) -> T {
return f({ $0.map(cata(f)) }(out(term)))
}

Expected Results:
should not infinite loop and crash swiftc

Actual Results:
but totally does:
rob@Resonance ~/Desktop> swiftc -v boom.swift
Apple Swift version 2.0 (swiftlang-700.0.47.4 clang-700.0.59.1)
Target: x86_64-apple-darwin14.4.0
/Applications/Xcode-beta.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/swift -frontend -c -primary-file boom.swift -target x86_64-apple-darwin14.4.0 -enable-objc-interop -color-diagnostics -module-name boom -o /var/folders/9y/f7n4rvx901nctm_5d16c1wm40000gn/T/boom-d6304d.o
:0: error: unable to execute command: Segmentation fault: 11
:0: error: swift frontend command failed due to signal (use -v to see invocation)

509 swift 0x000000010ebc2ee3 swift::TypeBase::gatherAllSubstitutions(swift::ModuleDecl_, llvm::SmallVectorImplswift::Substitution&, swift::LazyResolver_, swift::DeclContext_) + 211
510 swift 0x000000010eb94ca6 swift::ModuleDecl::lookupConformance(swift::Type, swift::ProtocolDecl_, swift::LazyResolver_) + 1958
511 swift 0x000000010eb93f66 swift::BoundGenericType::getSubstitutions(swift::ModuleDecl_, swift::LazyResolver_, swift::DeclContext_) + 1606

Regression:
N/A

Notes:
N/A

Product Version: Xcode-beta (7A165t)
Created: 2015-07-30 02:05:44.645750
Originated: 2015-07-29T22:05:00
Open Radar Link: http://www.openradar.me/22064912