search

swiftlang / swift

The Swift Programming Language
https://swift.org
Apache License 2.0
67.58k stars 10.36k forks source link

Underconstrained protocol crashes the compiler #75817

Open JessyCatterwaul opened 2 months ago

JessyCatterwaul commented 2 months ago

Description

I'm trying to figure out ways to reduce the necessary -requirement-machine-max-rule-count for this library, which currently requires 8000 instead of the default 4000 to compile. The process is difficult because of compiler crashes when attempting to move constraints outwards.

Reproduction

I'm sorry this isn't simpler, but this is as far as I've been able to reduce it.

Uncomment the constraint, and this will compile.

protocol FloatingPointScalar: SIMDScalar & BinaryFloatingPoint & Codable {
  associatedtype Matrix3x3
}

protocol FloatingPointVector<Scalar>: SIMD { }
extension SIMD2: FloatingPointVector { }
extension SIMD3: FloatingPointVector where Scalar.Matrix3x3: Matrix3x3<Scalar> { }

protocol Matrix<Scalar> {
  associatedtype Scalar: FloatingPointScalar
  associatedtype Column: FloatingPointVector<Scalar>
  associatedtype Columns
  associatedtype Row: FloatingPointVector<Scalar>
}

protocol SquareMatrix<Scalar>: Matrix where Row == Column { }

protocol Matrix2<Scalar>: Matrix where Columns == (Column, Column), Row == SIMD2<Scalar> { }

protocol Matrix2x3<Scalar>: Matrix2 where Column == SIMD3<Scalar>
//, Scalar.Matrix3x3: Matrix3x3<Scalar>
{ }

protocol Matrix3<Scalar>: Matrix where
  Columns == (Column, Column, Column), Row == SIMD3<Scalar>,
  Scalar.Matrix3x3: Matrix3x3<Scalar>
{ }

protocol Matrix3x3<Scalar>: Matrix3 & SquareMatrix { }

Stack dump

1.  Apple Swift version 6.0 (swiftlang-6.0.0.7.6 clang-1600.0.24.1)
2.  Compiling with the current language version
3.  While evaluating request TypeCheckSourceFileRequest
4.  While type-checking 'Matrix2x3'
5.  While evaluating request RequirementRequest
6.  While evaluating request ResolveTypeRequest(while resolving type , SIMD3<Scalar>)
7.  While building rewrite system for generic signature <τ_0_0 where τ_0_0 : Matrix2x3>
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           0x0000000109ce9194 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) + 56
1  swift-frontend           0x0000000109ce73e8 llvm::sys::RunSignalHandlers() + 112
2  swift-frontend           0x0000000109ce9760 SignalHandler(int) + 292
3  libsystem_platform.dylib 0x0000000189697584 _sigtramp + 56
4  libsystem_pthread.dylib  0x0000000189666c20 pthread_kill + 288
5  libsystem_c.dylib        0x0000000189573a30 abort + 180
6  swift-frontend           0x0000000106090f34 swift::rewriting::RewriteSystem::simplifySubstitutions(swift::rewriting::Term, swift::rewriting::Symbol, swift::rewriting::PropertyMap const*, swift::rewriting::RewritePath*) + 0
7  swift-frontend           0x000000010609193c swift::rewriting::RewriteSystem::simplifyLeftHandSideSubstitutions(swift::rewriting::PropertyMap const*) + 1408
8  swift-frontend           0x000000010605e0b4 swift::rewriting::PropertyMap::buildPropertyMap() + 1752
9  swift-frontend           0x00000001060707d8 swift::rewriting::RequirementMachine::computeCompletion(swift::rewriting::RewriteSystem::ValidityPolicy) + 240
10 swift-frontend           0x0000000106070d80 swift::rewriting::RequirementMachine::initWithGenericSignature(swift::GenericSignature) + 760
11 swift-frontend           0x000000010607a2dc swift::rewriting::RewriteContext::getRequirementMachine(swift::CanGenericSignature) + 412
12 swift-frontend           0x0000000105f8c8c8 swift::GenericSignatureImpl::getLocalRequirements(swift::Type) const + 416
13 swift-frontend           0x0000000105f888f0 swift::GenericEnvironment::getOrCreateArchetypeFromInterfaceType(swift::Type) + 60
14 swift-frontend           0x0000000105f89758 swift::QueryInterfaceTypeSubstitutions::operator()(swift::SubstitutableType*) const + 448
15 swift-frontend           0x00000001060d96b0 swift::InFlightSubstitution::substType(swift::SubstitutableType*, unsigned int) + 48
16 swift-frontend           0x00000001060dd81c std::__1::optional<swift::Type> llvm::function_ref<std::__1::optional<swift::Type> (swift::TypeBase*)>::callback_fn<substType(swift::Type, unsigned int, swift::InFlightSubstitution&)::$_0>(long, swift::TypeBase*) + 868
17 swift-frontend           0x00000001060bc504 swift::Type::transformWithPosition(swift::TypePosition, llvm::function_ref<std::__1::optional<swift::Type> (swift::TypeBase*, swift::TypePosition)>) const + 92
18 swift-frontend           0x00000001060d9e60 substType(swift::Type, unsigned int, swift::InFlightSubstitution&) + 312
19 swift-frontend           0x00000001060dd6d4 std::__1::optional<swift::Type> llvm::function_ref<std::__1::optional<swift::Type> (swift::TypeBase*)>::callback_fn<substType(swift::Type, unsigned int, swift::InFlightSubstitution&)::$_0>(long, swift::TypeBase*) + 540
20 swift-frontend           0x00000001060bc504 swift::Type::transformWithPosition(swift::TypePosition, llvm::function_ref<std::__1::optional<swift::Type> (swift::TypeBase*, swift::TypePosition)>) const + 92
21 swift-frontend           0x00000001060d9e60 substType(swift::Type, unsigned int, swift::InFlightSubstitution&) + 312
22 swift-frontend           0x00000001060d961c swift::Type::subst(llvm::function_ref<swift::Type (swift::SubstitutableType*)>, llvm::function_ref<swift::ProtocolConformanceRef (swift::CanType, swift::Type, swift::ProtocolDecl*)>, swift::SubstOptions) const + 340
23 swift-frontend           0x0000000105b487fc swift::Type llvm::function_ref<swift::Type (swift::SubstitutableType*)>::callback_fn<swift::TypeResolution::applyUnboundGenericArguments(swift::GenericTypeDecl*, swift::Type, swift::SourceLoc, llvm::ArrayRef<swift::Type>) const::$_0 const>(long, swift::SubstitutableType*) + 380
24 swift-frontend           0x00000001060d96b0 swift::InFlightSubstitution::substType(swift::SubstitutableType*, unsigned int) + 48
25 swift-frontend           0x00000001060dd81c std::__1::optional<swift::Type> llvm::function_ref<std::__1::optional<swift::Type> (swift::TypeBase*)>::callback_fn<substType(swift::Type, unsigned int, swift::InFlightSubstitution&)::$_0>(long, swift::TypeBase*) + 868
26 swift-frontend           0x00000001060bc504 swift::Type::transformWithPosition(swift::TypePosition, llvm::function_ref<std::__1::optional<swift::Type> (swift::TypeBase*, swift::TypePosition)>) const + 92
27 swift-frontend           0x00000001060d9e60 substType(swift::Type, unsigned int, swift::InFlightSubstitution&) + 312
28 swift-frontend           0x00000001060d961c swift::Type::subst(llvm::function_ref<swift::Type (swift::SubstitutableType*)>, llvm::function_ref<swift::ProtocolConformanceRef (swift::CanType, swift::Type, swift::ProtocolDecl*)>, swift::SubstOptions) const + 340
29 swift-frontend           0x0000000105aa16c0 swift::TypeChecker::checkGenericArgumentsForDiagnostics(swift::ModuleDecl*, llvm::ArrayRef<swift::Requirement>, llvm::function_ref<swift::Type (swift::SubstitutableType*)>) + 216
30 swift-frontend           0x0000000105b2e748 swift::TypeResolution::applyUnboundGenericArguments(swift::GenericTypeDecl*, swift::Type, swift::SourceLoc, llvm::ArrayRef<swift::Type>) const + 2528
31 swift-frontend           0x0000000105b43e2c applyGenericArguments(swift::Type, swift::TypeResolution, swift::SILTypeResolutionContext*, swift::DeclRefTypeRepr*) + 4340
32 swift-frontend           0x0000000105b40cfc resolveTypeDecl(swift::TypeDecl*, swift::DeclContext*, swift::TypeResolution, swift::SILTypeResolutionContext*, swift::UnqualifiedIdentTypeRepr*) + 204
33 swift-frontend           0x0000000105b3fc2c (anonymous namespace)::TypeResolver::resolveDeclRefTypeReprRec(swift::DeclRefTypeRepr*, swift::TypeResolutionOptions) + 2328
34 swift-frontend           0x0000000105b30764 (anonymous namespace)::TypeResolver::resolveType(swift::TypeRepr*, swift::TypeResolutionOptions) + 256
35 swift-frontend           0x0000000105b2eec4 evaluateTypeResolution(swift::TypeResolution const*, swift::TypeRepr*, swift::SILTypeResolutionContext*) + 124
36 swift-frontend           0x0000000105b48a50 swift::ResolveTypeRequest::OutputType swift::Evaluator::getResultUncached<swift::ResolveTypeRequest, swift::ResolveTypeRequest::OutputType swift::evaluateOrDefault<swift::ResolveTypeRequest>(swift::Evaluator&, swift::ResolveTypeRequest, swift::ResolveTypeRequest::OutputType)::'lambda'()>(swift::ResolveTypeRequest const&, swift::ResolveTypeRequest::OutputType swift::evaluateOrDefault<swift::ResolveTypeRequest>(swift::Evaluator&, swift::ResolveTypeRequest, swift::ResolveTypeRequest::OutputType)::'lambda'()) + 432
37 swift-frontend           0x0000000105aa2848 swift::RequirementRequest::evaluate(swift::Evaluator&, swift::WhereClauseOwner, unsigned int, swift::TypeResolutionStage) const + 696
38 swift-frontend           0x00000001060cc810 swift::RequirementRequest::OutputType swift::Evaluator::getResultUncached<swift::RequirementRequest, swift::WhereClauseOwner::visitRequirements(swift::TypeResolutionStage, llvm::function_ref<bool (swift::Requirement, swift::RequirementRepr*)>) const &&::$_0>(swift::RequirementRequest const&, swift::WhereClauseOwner::visitRequirements(swift::TypeResolutionStage, llvm::function_ref<bool (swift::Requirement, swift::RequirementRepr*)>) const &&::$_0) + 640
39 swift-frontend           0x00000001060c6e64 swift::WhereClauseOwner::visitRequirements(swift::TypeResolutionStage, llvm::function_ref<bool (swift::Requirement, swift::RequirementRepr*)>) const && + 772
40 swift-frontend           0x0000000105982d6c swift::checkAccessControl(swift::Decl*) + 4320
41 swift-frontend           0x0000000105a63fbc (anonymous namespace)::DeclChecker::visit(swift::Decl*) + 1704
42 swift-frontend           0x0000000105a63904 swift::TypeChecker::typeCheckDecl(swift::Decl*) + 152
43 swift-frontend           0x0000000105b4a94c swift::TypeCheckSourceFileRequest::evaluate(swift::Evaluator&, swift::SourceFile*) const + 660
44 swift-frontend           0x0000000105b51fdc swift::TypeCheckSourceFileRequest::OutputType swift::Evaluator::getResultUncached<swift::TypeCheckSourceFileRequest, swift::TypeCheckSourceFileRequest::OutputType swift::evaluateOrDefault<swift::TypeCheckSourceFileRequest>(swift::Evaluator&, swift::TypeCheckSourceFileRequest, swift::TypeCheckSourceFileRequest::OutputType)::'lambda'()>(swift::TypeCheckSourceFileRequest const&, swift::TypeCheckSourceFileRequest::OutputType swift::evaluateOrDefault<swift::TypeCheckSourceFileRequest>(swift::Evaluator&, swift::TypeCheckSourceFileRequest, swift::TypeCheckSourceFileRequest::OutputType)::'lambda'()) + 620
45 swift-frontend           0x0000000105b4a69c swift::performTypeChecking(swift::SourceFile&) + 328
46 swift-frontend           0x0000000104a6ffe8 swift::CompilerInstance::performSema() + 260
47 swift-frontend           0x000000010469e690 performCompile(swift::CompilerInstance&, int&, swift::FrontendObserver*) + 1528
48 swift-frontend           0x000000010469d458 swift::performFrontend(llvm::ArrayRef<char const*>, char const*, void*, swift::FrontendObserver*) + 3572
49 swift-frontend           0x000000010462450c swift::mainEntry(int, char const**) + 3680
50 dyld                     0x00000001892de0e0 start + 2360

Expected behavior

A compiler error instead of a crash

Environment

swift-driver version: 1.113 Apple Swift version 6.0 (swiftlang-6.0.0.7.6 clang-1600.0.24.1) Target: arm64-apple-macosx14.0

Additional information

The constraint should actually be included at an earlier level, like this:

associatedtype Matrix3x3: NameOfModule.Matrix3x3<Self>

This will work in this example, but it does not scale. If you have any insight, please tell me if it's possible to use that instead of requiring a ridiculous -requirement-machine-max-rule-count. Here's the file in the latest commit that uses the problematic constraints.

slavapestov commented 2 months ago

The crash shouldn’t happen and I’ll take a look, but in general, same-type requirements that involve a concrete type (like Foo == Bar<Baz> etc) are not very efficient. If you eliminate some of those it should help.

slavapestov commented 2 months ago

Ah, it crashes here:

`Frozen rule should already be subst-simplified`: [Matrix3:Scalar].[FloatingPointScalar:Matrix3x3].[Matrix3x3:Column].[concrete: SIMD3<[Matrix3:Scalar].[FloatingPointScalar:Matrix3x3].[Matrix3x3:Scalar]>] => [Matrix3:Scalar].[FloatingPointScalar:Matrix3x3].[Matrix3x3:Column]

This rule should already have a [subst↓] next to it because it was imported from the Matrix3 protocol.

Indeed [Matrix3:Scalar].[FloatingPointScalar:Matrix3x3].[Matrix3x3:Scalar] reduces to [Matrix3:Scalar], because of the same-type requirement:

- [Matrix3:Scalar].[FloatingPointScalar:Matrix3x3].[Matrix3x3:Scalar] => [Matrix3:Scalar] [explicit]

And we already have the right rule obtained from applying this reduction:

- [Matrix3:Scalar].[FloatingPointScalar:Matrix3x3].[Matrix3x3:Column].[concrete: SIMD3<[Matrix3:Scalar]>] => [Matrix3:Scalar].[FloatingPointScalar:Matrix3x3].[Matrix3x3:Column]