Compiler crash with generic protocols: "meet operation was not commutative"

[tristanlabelle]

Description
The Swift compiler crashes in LLVM using a combination of generics and protocols as illustrated below.

Steps to reproduce
Run this code using swift code.swift:

public protocol Derived<A, B> : Base where T == any Derived<A, B> {
    associatedtype A
    associatedtype B
}

public protocol Base {
    associatedtype T
}

Output:

Meet operation was not commutative:

LHS: [concrete: Derived<[Derived].A, [Derived].B>]
RHS: [concrete: Derived<[Derived:A], [Derived:B]>]
Abstract differences with LHS < RHS:
Abstract differences with RHS < LHS:
- [Derived].A (#0) -> [Derived:A]
Concrete differences with LHS < RHS:
Concrete differences with RHS < LHS:
Concrete conflicts:

LHS ∧ RHS: [concrete: Derived<[Derived:A], [Derived].B>]
RHS ∧ LHS: [concrete: Derived<[Derived:A], [Derived:B]>]
Stack dump:
0.      Program arguments: /Library/Developer/CommandLineTools/usr/bin/swift-frontend -frontend -interpret IMapCrashRepro.swift -Xllvm -aarch64-use-tbi -enable-objc-interop -sdk /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk -color-diagnostics -target-sdk-version 13.1 -module-name IMapCrashRepro
1.      Apple Swift version 5.7.2 (swiftlang-5.7.2.135.5 clang-1400.0.29.51)
2.      Compiling with the current language version
3.      While evaluating request TypeCheckSourceFileRequest(source_file "IMapCrashRepro.swift")
4.      While type-checking 'Derived' (at IMapCrashRepro.swift:1:8)
5.      While evaluating request RequirementSignatureRequest(IMapCrashRepro.(file).Derived@IMapCrashRepro.swift:1:17)
6.      While evaluating request RequirementSignatureRequestRQM(IMapCrashRepro.(file).Derived@IMapCrashRepro.swift:1:17)
Stack dump without symbol names (ensure you have llvm-symbolizer in your PATH or set the environment var `LLVM_SYMBOLIZER_PATH` to point to it):
0  swift-frontend           0x0000000108f7b5b0 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) + 56
1  swift-frontend           0x0000000108f7a5b4 llvm::sys::RunSignalHandlers() + 112
2  swift-frontend           0x0000000108f7bc34 SignalHandler(int) + 344
3  libsystem_platform.dylib 0x00000001a5ca42a4 _sigtramp + 56
4  libsystem_pthread.dylib  0x00000001a5c75cec pthread_kill + 288
5  libsystem_c.dylib        0x00000001a5bae2c8 abort + 180
6  swift-frontend           0x00000001059527d4 (anonymous namespace)::ConcreteTypeMatcher::dump(llvm::raw_ostream&) const + 0
7  swift-frontend           0x000000010592142c swift::rewriting::PropertyMap::unifyConcreteTypes(swift::rewriting::Term, llvm::Optional<swift::rewriting::Symbol>&, llvm::SmallVectorImpl<std::__1::pair<swift::rewriting::Symbol, unsigned int> >&, swift::rewriting::Symbol, unsigned int) + 696
8  swift-frontend           0x000000010591df7c swift::rewriting::PropertyMap::buildPropertyMap() + 1452
9  swift-frontend           0x000000010592ddd0 swift::rewriting::RequirementMachine::computeCompletion(swift::rewriting::RewriteSystem::ValidityPolicy) + 236
10 swift-frontend           0x000000010592e8e8 swift::rewriting::RequirementMachine::initWithProtocolWrittenRequirements(llvm::ArrayRef<swift::ProtocolDecl const*>, llvm::DenseMap<swift::ProtocolDecl const*, llvm::SmallVector<swift::StructuralRequirement, 4u>, llvm::DenseMapInfo<swift::ProtocolDecl const*>, llvm::detail::DenseMapPair<swift::ProtocolDecl const*, llvm::SmallVector<swift::StructuralRequirement, 4u> > >) + 900
11 swift-frontend           0x000000010592f6ec swift::RequirementSignatureRequestRQM::evaluate(swift::Evaluator&, swift::ProtocolDecl*) const + 1960
12 swift-frontend           0x0000000105875db8 llvm::Expected<swift::RequirementSignatureRequestRQM::OutputType> swift::Evaluator::getResultCached<swift::RequirementSignatureRequestRQM, (void*)0>(swift::RequirementSignatureRequestRQM const&) + 1288
13 swift-frontend           0x0000000105862b54 swift::RequirementSignatureRequest::evaluate(swift::Evaluator&, swift::ProtocolDecl*) const + 376
14 swift-frontend           0x00000001057bb824 llvm::Expected<swift::RequirementSignatureRequest::OutputType> swift::Evaluator::getResultCached<swift::RequirementSignatureRequest, (void*)0>(swift::RequirementSignatureRequest const&) + 1040
15 swift-frontend           0x000000010575ee4c swift::ProtocolDecl::getRequirementSignature() const + 108
16 swift-frontend           0x0000000105353680 swift::ASTVisitor<(anonymous namespace)::DeclChecker, void, void, void, void, void, void>::visit(swift::Decl*) + 1728
17 swift-frontend           0x000000010534ff4c (anonymous namespace)::DeclChecker::visit(swift::Decl*) + 400
18 swift-frontend           0x000000010534fdb0 swift::TypeChecker::typeCheckDecl(swift::Decl*, bool) + 204
19 swift-frontend           0x0000000105419cb0 swift::TypeCheckSourceFileRequest::evaluate(swift::Evaluator&, swift::SourceFile*) const + 540
20 swift-frontend           0x000000010541c95c llvm::Expected<swift::TypeCheckSourceFileRequest::OutputType> swift::Evaluator::getResultUncached<swift::TypeCheckSourceFileRequest>(swift::TypeCheckSourceFileRequest const&) + 576
21 swift-frontend           0x0000000105419a40 swift::performTypeChecking(swift::SourceFile&) + 120
22 swift-frontend           0x000000010463aa60 bool llvm::function_ref<bool (swift::SourceFile&)>::callback_fn<swift::CompilerInstance::performSema()::$_6>(long, swift::SourceFile&) + 16
23 swift-frontend           0x00000001046351d4 swift::CompilerInstance::forEachFileToTypeCheck(llvm::function_ref<bool (swift::SourceFile&)>) + 288
24 swift-frontend           0x0000000104635078 swift::CompilerInstance::performSema() + 148
25 swift-frontend           0x00000001045c8180 swift::performFrontend(llvm::ArrayRef<char const*>, char const*, void*, swift::FrontendObserver*) + 4364
26 swift-frontend           0x0000000104569294 swift::mainEntry(int, char const**) + 3940
27 dyld                     0x00000001a594be50 start + 2544
zsh: abort      swift IMapCrashRepro.swift

The crash does not repro when using a single generic type parameter on Derived.

Expected behavior
The code should compile, or generate an error if the code is not valid (I'm not well-versed enough in Swift to be sure).

Environment

• Swift compiler version info: Apple Swift version 5.7.2 (swiftlang-5.7.2.135.5 clang-1400.0.29.51), and with the latest trunk: swift-DEVELOPMENT-SNAPSHOT-2023-02-02-a
• Xcode version info: Version 14.2 (14C18)
• Deployment target: irrelevant

[compnerd]

CC: @slavapestov

[AnthonyLatsis]

Simpler:

protocol Derived<A, B> where C == any Derived<Never, B> {
  associatedtype A
  associatedtype B

  associatedtype C
}