[SR-6569] Recursive conditional conformances #49119

dmcyk · 2017-12-11T17:42:40Z


Previous ID	SR-6569
Radar	rdar://problem/36068136
Original Reporter	@dmcyk
Type	Improvement

Additional Detail from JIRA


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

md5: e6b335158cc4e2963fcaeb9f6bc8d539

Issue Description:

In the Swift 4.1 version toolchain snapshot from 19-12-2017 there's already some ongoing work with implementation of conditional conformances. In this version though, it is not possible to define somewhat recursive, safe-aware conditional conformances which would allow generic type to conform to a given protocol only if condition which regards the type itself is met.
I don't really know if there's any kind of a specific term for such property in type theory, but basically what I was trying to achieve was:

protocol Request {

    associatedtype ResponseType: Response
        where ResponseType.RequestType == Self
}

protocol Response {

    associatedtype RequestType: Request
        where RequestType.ResponseType == Self
}

struct BasicResponse<E: Request> { }

extension BasicResponse: Response where E.ResponseType == BasicResponse {

    typealias RequestType = E
}

Currently trying to compile such code using the toolchain results in following:

main.swift:15:56: error: same-type constraint type 'BasicResponse<E>' does not conform to required protocol 'Response'
extension BasicResponse: Response where E.ResponseType == BasicResponse {
                                                       ^
main.swift:15:1: error: 'Response' requires the types 'BasicResponse<E>' and 'E.ResponseType' be equivalent
extension BasicResponse: Response where E.ResponseType == BasicResponse {
^
main.swift:15:1: note: requirement specified as 'Self' == 'Self.RequestType.ResponseType' [with Self = BasicResponse<E>]
extension BasicResponse: Response where E.ResponseType == BasicResponse {
^

belkadan · 2017-12-12T17:27:56Z

cc @DougGregor

DougGregor · 2017-12-15T06:57:35Z

@swift-ci create

huonw · 2018-03-13T02:25:13Z

Reduced slightly:

protocol P {
    associatedtype A: P
}

struct Type<Param> {}
extension Type: P where Param: P, Param.A == Type<Param> {
    typealias A = Param
}

The problem here is a circular dependency on the conformance lookup table of Type: while constructing the entry for Type : P, we need to find that conformance to verify that the Param.Assoc == Type<Param> same-type constraint is valid. It doesn't even exist at that point, because we're deep in the middle of building it.

One possibility would be to special-case the 'current type conforms to current protocol' case, which should covers the original bug and probably most cases in the wild. But, I don't think this actually works to cover all cases (this differs to the original by having the type conform to both protocols):

protocol P1 {
    associatedtype A1: P2
}
protocol P2 {
    associatedtype A2: P1
}

struct Type<Param> {}
extension Type: P1 where Param: P1 & P2, Param.A1 == Type<Param>, Param.A2 == Type<Param> {
    typealias A1 = Param
}
extension Type: P2 where Param: P1 & P2, Param.A1 == Type<Param>, Param.A2 == Type<Param> {
    typealias A2 = Param
}

This currently gets 3 errors:

sr-6569-2.swift:12:51: error: same-type constraint type 'Type<Param>' does not conform to required protocol 'P2'
extension Type: P2 where Param: P1 & P2, Param.A1 == Type<Param>, Param.A2 == Type<Param> {
                                                  ^
sr-6569-2.swift:12:76: error: same-type constraint type 'Type<Param>' does not conform to required protocol 'P1'
extension Type: P2 where Param: P1 & P2, Param.A1 == Type<Param>, Param.A2 == Type<Param> {
                                                                           ^
sr-6569-2.swift:9:76: error: same-type constraint type 'Type<Param>' does not conform to required protocol 'P1'
extension Type: P1 where Param: P1 & P2, Param.A1 == Type<Param>, Param.A2 == Type<Param> {
                                                                           ^

It's the middle one that's problematic, since it's the cross-over, where the problem is that the Type : P1 conformance is needed while validating the Type : P2 one, and so the simple hack doesn't cover this.

huonw · 2018-03-13T03:09:42Z

Maybe we should be more aggressive about putting in placeholders as we start validating/checking the conformances, so we (successfully) find partial conformances, and latter fill them in, with the GSB (and anything else that operates that early) resilient to information being missing from those conformances.

huonw · 2018-03-15T09:49:42Z

Ah! I think I've got a strategy: currently we pull the fully minimised and canonical set of requirements out of the conformances referenced while building a generic signature, but we don't actually need to: the set of raw requirements (RequirementReprs) has just as much information, and, since we're building generic signature anyway, we're already going to be minimizing things away.

Approximate sketch: in the GSB, if a conformance returned by lookupConformance doesn't have the minimal conditional requirements, pull out the TrailingWhereClause of the extension defining the conformance (if those exist) and add those requirements (with appropriate substitution). This also requires being able to build a normal conformance without computing its conditional requirements and either having some sort of compute-the-requirements step or doing it on-demand, once the declcontext declaring the conformance has been validated.

huonw · 2018-03-15T13:11:20Z

Initial work breaking some of the recursion in #15268

huonw · 2018-04-10T02:21:00Z

This applies to non-conditional conformances too:

protocol A {
    associatedtype C : B where C.N == Self
}

protocol B {
    associatedtype N : A where N.C == Self
}

struct Z<L : B> : A where Z == L.N {
    typealias C = L
}

...:9:8: error: type 'Z<L>' does not conform to protocol 'A'
struct Z<L : B> : A where Z == L.N {
       ^
...:2:20: note: protocol requires nested type 'C'; do you want to add it?
    associatedtype C : B where C.N == Self
                   ^

huonw · 2018-05-01T06:09:29Z

The original example and the above with the conformance declared in a separate extension (i.e. extension Z: A {}), and the following now all crash.

protocol A {}

struct Z<L : B> where L.N == Z {}

extension Z: A {}

protocol B {
    associatedtype N : A
}

Assertion failed: ((bool)typeSig == (bool)extensionSig && "unexpected generic-ness mismatch on conformance"), function differenceAndStoreConditionalRequirements, file /Users/huon/projects/swift/swift/lib/AST/ProtocolConformance.cpp, line 404.
0  swift                    0x0000000106252cf8 llvm::sys::PrintStackTrace(llvm::raw_ostream&) + 40
1  swift                    0x0000000106253406 SignalHandler(int) + 694
2  libsystem_platform.dylib 0x00007fff50cd8f5a _sigtramp + 26
3  libsystem_platform.dylib 000000000000000000 _sigtramp + 2939318464
4  libsystem_c.dylib        0x00007fff50a761ae abort + 127
5  libsystem_c.dylib        0x00007fff50a3e1ac basename_r + 0
6  swift                    0x0000000103d07cb8 swift::NormalProtocolConformance::differenceAndStoreConditionalRequirements() + 552
7  swift                    0x0000000103afb25f swift::NormalProtocolConformance::NormalProtocolConformance(swift::Type, swift::ProtocolDecl*, swift::SourceLoc, swift::DeclContext*, swift::ProtocolConformanceState) + 383
8  swift                    0x0000000103abe66d swift::NormalProtocolConformance::NormalProtocolConformance(swift::Type, swift::ProtocolDecl*, swift::SourceLoc, swift::DeclContext*, swift::ProtocolConformanceState) + 61
9  swift                    0x0000000103abe3dd swift::ASTContext::getConformance(swift::Type, swift::ProtocolDecl*, swift::SourceLoc, swift::DeclContext*, swift::ProtocolConformanceState) + 333
10 swift                    0x0000000103bc5dc5 swift::ConformanceLookupTable::getConformance(swift::NominalTypeDecl*, swift::ConformanceLookupTable::ConformanceEntry*) + 581
11 swift                    0x0000000103bc638f swift::ConformanceLookupTable::lookupConformance(swift::ModuleDecl*, swift::NominalTypeDecl*, swift::ProtocolDecl*, swift::LazyResolver*, llvm::SmallVectorImpl<swift::ProtocolConformance*>&) + 543
12 swift                    0x0000000103ce5563 swift::ModuleDecl::lookupConformance(swift::Type, swift::ProtocolDecl*) + 1123
13 swift                    0x0000000103c1e4ac swift::GenericSignatureBuilder::lookupConformance(swift::CanType, swift::Type, swift::ProtocolType*) + 188
14 swift                    0x0000000103c16329 swift::GenericSignatureBuilder::resolveConcreteConformance(swift::GenericSignatureBuilder::ResolvedType, swift::ProtocolDecl*) + 377
15 swift                    0x0000000103c33a9c swift::GenericSignatureBuilder::addSameTypeRequirementToConcrete(swift::GenericSignatureBuilder::ResolvedType, swift::Type, swift::GenericSignatureBuilder::RequirementSource const*) + 1244
16 swift                    0x0000000103c340b9 swift::GenericSignatureBuilder::addSameTypeRequirementDirect(swift::GenericSignatureBuilder::ResolvedType, swift::GenericSignatureBuilder::ResolvedType, swift::GenericSignatureBuilder::FloatingRequirementSource, llvm::function_ref<void (swift::Type, swift::Type)>) + 425
17 swift                    0x0000000103c319be swift::GenericSignatureBuilder::addSameTypeRequirement(llvm::PointerUnion<swift::GenericSignatureBuilder::PotentialArchetype*, swift::Type>, llvm::PointerUnion<swift::GenericSignatureBuilder::PotentialArchetype*, swift::Type>, swift::GenericSignatureBuilder::FloatingRequirementSource, swift::GenericSignatureBuilder::UnresolvedHandlingKind, llvm::function_ref<void (swift::Type, swift::Type)>) + 1102
18 swift                    0x0000000103c19c7f swift::GenericSignatureBuilder::addRequirement(swift::Requirement const&, swift::GenericSignatureBuilder::FloatingRequirementSource, swift::ModuleDecl*) + 1695
19 swift                    0x0000000103c2942c swift::GenericSignatureBuilder::addRequirement(swift::RequirementRepr const*, swift::GenericSignatureBuilder::FloatingRequirementSource, swift::SubstitutionMap const*, swift::ModuleDecl*) + 2572
20 swift                    0x0000000103c34449 swift::GenericSignatureBuilder::addRequirement(swift::RequirementRepr const*, swift::ModuleDecl*) + 153
21 swift                    0x00000001038673b5 swift::TypeChecker::checkGenericParamList(swift::GenericSignatureBuilder*, swift::GenericParamList*, swift::GenericSignature*, swift::GenericTypeResolver*) + 389
22 swift                    0x000000010386c3bd swift::TypeChecker::checkGenericEnvironment(swift::GenericParamList*, swift::DeclContext*, swift::GenericSignature*, bool, swift::ExtensionDecl*, llvm::function_ref<void (swift::GenericSignatureBuilder&)>, bool) + 1117
23 swift                    0x000000010386cdd0 swift::TypeChecker::validateGenericTypeSignature(swift::GenericTypeDecl*) + 208
24 swift                    0x000000010383d328 swift::TypeChecker::validateDecl(swift::ValueDecl*) + 520
25 swift                    0x000000010384f07e (anonymous namespace)::DeclChecker::visitStructDecl(swift::StructDecl*) + 78
26 swift                    0x000000010383a742 (anonymous namespace)::DeclChecker::visit(swift::Decl*) + 1234
27 swift                    0x000000010383a266 swift::TypeChecker::typeCheckDecl(swift::Decl*) + 38
28 swift                    0x00000001038d3b28 swift::performTypeChecking(swift::SourceFile&, swift::TopLevelContext&, swift::OptionSet<swift::TypeCheckingFlags, unsigned int>, unsigned int, unsigned int, unsigned int, unsigned int) + 1688
29 swift                    0x0000000103510fb0 swift::CompilerInstance::parseAndTypeCheckMainFile(swift::PersistentParserState&, swift::DelayedParsingCallbacks*, swift::OptionSet<swift::TypeCheckingFlags, unsigned int>) + 432
30 swift                    0x000000010350fc58 swift::CompilerInstance::parseAndCheckTypes(swift::CompilerInstance::ImplicitImports const&) + 648
31 swift                    0x000000010350f598 swift::CompilerInstance::performSema() + 472
32 swift                    0x00000001029a6dc0 performCompile(swift::CompilerInstance&, swift::CompilerInvocation&, llvm::ArrayRef<char const*>, int&, swift::FrontendObserver*, swift::UnifiedStatsReporter*) + 1904
33 swift                    0x00000001029a563e swift::performFrontend(llvm::ArrayRef<char const*>, char const*, void*, swift::FrontendObserver*) + 3310
34 swift                    0x000000010296292d main + 2317
35 libdyld.dylib            0x00007fff509ca015 start + 1
Stack dump:
0.  Program arguments: /Users/huon/projects/swift/build/Ninja-RelWithDebInfoAssert/swift-macosx-x86_64/bin/swift -frontend -c -primary-file sr-6569-3.swift -target x86_64-apple-darwin17.6.0 -enable-objc-interop -module-name main -o /var/folders/3k/4q7m7bkn2k750rpr0jm8s9fr0000gn/T/sr-6569-3-7afe14.o 
1.  While type-checking 'Z' at sr-6569-3.swift:9:1
2.  While validating 'Z' at sr-6569-3.swift:9:1
<unknown>:0: error: unable to execute command: Abort trap: 6
<unknown>:0: error: compile command failed due to signal 6 (use -v to see invocation)

huonw · 2018-06-19T01:07:30Z

pull out the TrailingWhereClause of the extension defining the conformance (if those exist) and add those requirements (with appropriate substitution).

There probably needs to be care for extensions of generic type aliases, since they can add bounds too, e.g. the following two extensions are equivalent:

extension Range: Sequence, ... where Bound: Strideable, Bound.Stride : SignedInteger {}

public typealias CountableRange<Bound: Strideable> = Range<Bound>
  where Bound.Stride : SignedInteger
extension CountableRange: Sequence, ... {}

swift-ci transferred this issue from apple/swift-issues Apr 25, 2022

slavapestov self-assigned this Mar 31, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[SR-6569] Recursive conditional conformances #49119

[SR-6569] Recursive conditional conformances #49119

dmcyk commented Dec 11, 2017

belkadan commented Dec 12, 2017

DougGregor commented Dec 15, 2017

huonw mannequin commented Mar 13, 2018

huonw mannequin commented Mar 13, 2018

huonw mannequin commented Mar 15, 2018

huonw mannequin commented Mar 15, 2018

huonw mannequin commented Apr 10, 2018

huonw mannequin commented May 1, 2018

huonw mannequin commented Jun 19, 2018

[SR-6569] Recursive conditional conformances #49119

[SR-6569] Recursive conditional conformances #49119

Comments

dmcyk commented Dec 11, 2017

belkadan commented Dec 12, 2017

DougGregor commented Dec 15, 2017

huonw mannequin commented Mar 13, 2018

huonw mannequin commented Mar 13, 2018

huonw mannequin commented Mar 15, 2018

huonw mannequin commented Mar 15, 2018

huonw mannequin commented Apr 10, 2018

huonw mannequin commented May 1, 2018

huonw mannequin commented Jun 19, 2018