[SR-6724] Swift 4.1 crash when using conditional conformance

[swift-ci]

Previous ID	SR-6724
Radar	rdar://problem/39199261
Original Reporter	chriseidhof (JIRA User)
Type	Bug

Additional Detail from JIRA

| | | |------------------|-----------------| |Votes | 0 | |Component/s | Compiler | |Labels | Bug, CompilerCrash, ConditionalConformance | |Assignee | @slavapestov | |Priority | Medium | md5: 59c72f96768a3e17927760f3da82c35d

Issue Description:

I managed to crash the compiler without emitting an error message as I was experimenting with some conditional conformance stuff.

I tried to come up with a minimal example, and couldn't make it much shorter than this:

// A "CustomStringConvertible" alternative
protocol Show {
    var text: String { get }
}

// We can show ints.
extension Int: Show {
    var text: String { return "\(self)" }
}

// A protocol to represent "data-type generic" functions:
protocol Generic {
    associatedtype Rep
    var to: Rep { get }
}

// Recursion
struct Rec<A> where A: Generic {
    let value: A
}

// If the Rep conforms to show, this should conform to show as well.
extension Rec: Show where A.Rep: Show {
    var text: String {
        return value.to.text
    }
}

// Test is an empty struct. This is the most minimal example I could come up with.
struct Test<A>: Generic {
    typealias Rep = Rec<Test<A>>

    var to: Rec<Test<A>> {
        return Rec(value: self)
    }
}

let test = Test<Int>()
test.to.text

My feeling is that extension Rec: Show where A.Rep: Show is what made it break.

[swift-ci]

Comment by Chris Eidhof (JIRA)

Here's a slightly larger example, in context: https://gist.github.com/chriseidhof/1b758b854ed72096490620a8d6128718

[belkadan]

cc @DougGregor

[d4adc30e-df4b-4925-bfeb-69e631c0be69]

It does indeed seem to be the conditional conformance that's problematic.

Slightly reduced:

protocol P1 {
    func f()
}
protocol P2 {
    associatedtype Rep
}

struct Rec<A: P2> {}
extension Rec: P1 where A.Rep: P1 {
    func f() {}
}
struct Test: P2 {
    typealias Rep = Rec<Test>
}

let value = Rec<Test>()
value.f()

The crash is infinite recursion:

...

    frame #&#8203;75: 0x0000000102ce7acb swift`swift::GenericSignature::enumeratePairedRequirements(this=0x00000001160d6f98, fn=function_ref<bool (swift::Type, llvm::ArrayRef<swift::Requirement>)> @ 0x00007ffeef405f68)>) const at GenericSignature.cpp:447
    frame #&#8203;76: 0x0000000102ce9f9a swift`swift::GenericSignature::getSubstitutionMap(this=0x00000001160d6f98, subs=swift::TypeSubstitutionFn @ 0x00007ffeef406060, lookupConformance=swift::LookupConformanceFn @ 0x00007ffeef406050)>, llvm::function_ref<llvm::Optional<swift::ProtocolConformanceRef> (swift::CanType, swift::Type, swift::ProtocolType*)>) const at GenericSignature.cpp:493
    frame #&#8203;77: 0x0000000102e6b8be swift`swift::TypeBase::getContextSubstitutionMap(this=0x00000001160de500, module=0x0000000114820340, dc=0x00000001160ca9d0, genericEnv=0x0000000000000000) at Type.cpp:3325
    frame #&#8203;78: 0x0000000102dde277 swift`swift::ModuleDecl::lookupConformance(this=0x0000000114820340, type=Type @ 0x00007ffeef406358, protocol=0x00000001160ca238) at Module.cpp:683
    frame #&#8203;79: 0x0000000102e71c33 swift`swift::LookUpConformanceInModule::operator(this=0x00007ffeef4069f8, dependentType=CanType @ 0x00007ffeef406408, conformingReplacementType=Type @ 0x00007ffeef406400, conformedProtocol=0x00000001160cf070)(swift::CanType, swift::Type, swift::ProtocolType*) const at Type.cpp:2916
    frame #&#8203;80: 0x0000000102e90635 swift`llvm::Optional<swift::ProtocolConformanceRef> llvm::function_ref<llvm::Optional<swift::ProtocolConformanceRef> (callable=140732912396792, params=CanType @ 0x00007ffeef406450, params=Type @ 0x00007ffeef406448, params=0x00000001160cf070)>::callback_fn<swift::LookUpConformanceInModule>(long, swift::CanType, swift::Type, swift::ProtocolType*) at STLExtras.h:98
    frame #&#8203;81: 0x0000000102e7dc88 swift`llvm::function_ref<llvm::Optional<swift::ProtocolConformanceRef> (swift::CanType, swift::Type, swift::ProtocolType*)>::operator(this=0x00007ffeef4069a0, params=CanType @ 0x00007ffeef4064c0, params=Type @ 0x00007ffeef4064b8, params=0x00000001160cf070)(swift::CanType, swift::Type, swift::ProtocolType*) const at STLExtras.h:114
    frame #&#8203;82: 0x0000000102ced90e swift`swift::GenericSignature::getSubstitutionMap(this=0x00007ffeef406968, depTy=Type @ 0x00007ffeef4065c8, reqs=ArrayRef<swift::Requirement> @ 0x00007ffeef4065b8)>, llvm::function_ref<llvm::Optional<swift::ProtocolConformanceRef> (swift::CanType, swift::Type, swift::ProtocolType*)>) const::$_6::operator()(swift::Type, llvm::ArrayRef<swift::Requirement>) const at GenericSignature.cpp:507
    frame #&#8203;83: 0x0000000102ced67b swift`bool llvm::function_ref<bool (swift::Type, llvm::ArrayRef<swift::Requirement>)>::callback_fn<swift::GenericSignature::getSubstitutionMap(callable=140732912396648, params=Type @ 0x00007ffeef406678, params=ArrayRef<swift::Requirement> @ 0x00007ffeef406668)>, llvm::function_ref<llvm::Optional<swift::ProtocolConformanceRef> (swift::CanType, swift::Type, swift::ProtocolType*)>) const::$_6>(long, swift::Type, llvm::ArrayRef<swift::Requirement>) at STLExtras.h:98
    frame #&#8203;84: 0x0000000102ce9dda swift`llvm::function_ref<bool (swift::Type, llvm::ArrayRef<swift::Requirement>)>::operator(this=0x00007ffeef4068b8, params=Type @ 0x00007ffeef4066d8, params=ArrayRef<swift::Requirement> @ 0x00007ffeef4066c8)(swift::Type, llvm::ArrayRef<swift::Requirement>) const at STLExtras.h:114
    frame #&#8203;85: 0x0000000102ce7acb swift`swift::GenericSignature::enumeratePairedRequirements(this=0x00000001160d6f98, fn=function_ref<bool (swift::Type, llvm::ArrayRef<swift::Requirement>)> @ 0x00007ffeef4068b8)>) const at GenericSignature.cpp:447

...

    frame #&#8203;35017: 0x0000000101b49ae8 swift`swift::CompilerInstance::parseAndCheckTypes(this=0x0000000114808600, implicitImports=0x00007ffeefbfb7c8) at Frontend.cpp:613
    frame #&#8203;35018: 0x0000000101b4922c swift`swift::CompilerInstance::performSema(this=0x0000000114808600) at Frontend.cpp:459
    frame #&#8203;35019: 0x00000001000dff76 swift`performCompile(Instance=0x0000000114808600, Invocation=0x00007ffeefbfcf00, Args=ArrayRef<const char *> @ 0x00007ffeefbfbb60, ReturnValue=0x00007ffeefbfc364, observer=0x0000000000000000, Stats=0x0000000000000000) at FrontendTool.cpp:889
    frame #&#8203;35020: 0x00000001000de21e swift`swift::performFrontend(Args=ArrayRef<const char *> @ 0x00007ffeefbfc590, Argv0="/Users/huon/projects/swift/build/Ninja-DebugAssert/swift-macosx-x86_64/bin/swift", MainAddr=0x000000010000ae00, observer=0x0000000000000000) at FrontendTool.cpp:1782

Notes to future-fixer: the call is trying to build the SpecializedProtocolConformance for Rec<Test> : P1, which needs to create a SubstitutionMap to substitute into the NormalProtocolConformance for Rec : P1, but creating that SubstitutionMap means pulling out the ProtocolConformanceRefs for any requirements... including the A.Rep : Show one. In this case, that requirement is exactly Rec<Test> : P1, meaning the ProtocolConformanceRef needs to store exactly the SpecializedProtocolConformance we're in the middle of building! A possible approach is making SpecializedProtocolConformance construction lazier/staged: first create the conformance and then fill it in.

Also, this crashes even for non-direct recursion:

protocol P1 {
    func f()
}
protocol P2 {
    associatedtype Rep
}

struct Rec<A: P2> {}
extension Rec: P1 where A.Rep: P1 {
    func f() {}
}
// create a circle
struct Step1: P2 { typealias Rep = Rec<Step2> }
struct Step2: P2 { typealias Rep = Rec<Step3> }
struct Step3: P2 { typealias Rep = Rec<Step4> }
struct Step4: P2 { typealias Rep = Rec<Step5> }
struct Step5: P2 { typealias Rep = Rec<Step6> }
struct Step6: P2 { typealias Rep = Rec<Step1> }

let value = Rec<Step1>()
value.f()

[d4adc30e-df4b-4925-bfeb-69e631c0be69]

@swift-ci create

[slavapestov]

Still crashes, now with request evaluator spew:

<unknown>:0: error: circular reference
<unknown>:0: note: through reference here
<unknown>:0: note: through reference here
<unknown>:0: note: through reference here
<unknown>:0: note: through reference here
<unknown>:0: note: through reference here
<unknown>:0: error: circular reference
<unknown>:0: note: through reference here
<unknown>:0: note: through reference here
<unknown>:0: note: through reference here
<unknown>:0: note: through reference here
<unknown>:0: note: through reference here
<unknown>:0: error: unable to execute command: Illegal instruction: 4
<unknown>:0: error: compile command failed due to signal 4 (use -v to see invocation)

[slavapestov]

Related to https://github.com/apple/swift/issues/51259 and rdar://69901318