Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[SR-13989] The compiler is unable to type-check this expression in reasonable time for an expression that should not compile #56384

Closed
swift-ci opened this issue Dec 24, 2020 · 5 comments
Closed

[SR-13989] The compiler is unable to type-check this expression in reasonable time for an expression that should not compile #56384

swift-ci opened this issue Dec 24, 2020 · 5 comments
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself type checker Area → compiler: Semantic analysis

Comments

@swift-ci
Copy link
Collaborator

Previous ID SR-13989
Radar rdar://problem/72657288
Original Reporter Nikic (JIRA User)
Type Bug
Status Resolved
Resolution Done

Attachment: Download

Environment

Apple Swift version 5.3.2 (swiftlang-1200.0.45 clang-1200.0.32.28)

Target: x86_64-apple-darwin19.6.0

Additional Detail from JIRA
Votes 0
Component/s Compiler
Labels Bug, TypeChecker
Assignee Nikic (JIRA)
Priority Medium

md5: 03df7bd68c221fb53aaa1ff519724fd4

Issue Description:

With Xcode 12.3 and swift 5.3.2 the compiler is unable to solve the following expression in reasonable time.

 12> let a: Int = 1
a: Int = 1
 13> let b: Int32 = 2
b: Int32 = 2
 14> UInt32(a + a + a * 3 + a + b)
error: repl.swift:14:1: error: the compiler is unable to type-check this expression in reasonable time; try breaking up the expression into distinct sub-expressions
UInt32(a + a + a + a + b)
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 14> UInt32(a + a + a + a + a)
$R10: UInt32 = 5

However, this expression should not compile in the first place because

 16> UInt32(a + b)
error: repl.swift:16:10: error: binary operator '+' cannot be applied to operands of type 'Int' and 'Int32'
UInt32(a + b)
       ~ ^ ~


repl.swift:16:10: note: overloads for '+' exist with these partially matching parameter lists: (Int, Int), (Int32, Int32)
UInt32(a + b)

The following expression compiles instantly

 16> UInt32((a + a + a  + a) + Int(b))
$R12: UInt32 = 6

Expected result :

The compiler should warn that this expression does not compile instead of timing out.
@stephentyrone
Copy link
Member

@swift-ci create

@stephentyrone
Copy link
Member

CC @hborla, @xedin

@hborla
Copy link
Member

hborla commented May 26, 2021

This reports a helpful error in Swift 5.5:

error: binary operator '+' cannot be applied to operands of type 'Int' and 'Int32'
UInt32(a + a + a * 3 + a + b)
       ~~~~~~~~~~~~~~~~~ ^ ~
note: overloads for '+' exist with these partially matching parameter lists: (Int, Int), (Int32, Int32)
UInt32(a + a + a * 3 + a + b)
                         ^

Could you please verify using a Swift 5.5 development toolchain from https://swift.org/download/#snapshots? Thank you!

@swift-ci
Copy link
Collaborator Author

Comment by Marco (JIRA)

Hi Holly,

The new error is indeed helpful, thank you for fixing it !
The performance however, can be improved.

The performance of overloading matching is already severely degraded at only 4 terms.
It took between 15 and 20 seconds to fail on my machine (2.9 GHz 6-Core Intel Core i9 - late 2018, on power, so no CPU throttling should apply)

4 terms operation

main.swift:19:19: error: binary operator '+' cannot be applied to operands of type 'Int' and 'Int32'
 UInt32(a + b + a + b) // 15 seconds
        ~~~~~~~~~ ^ ~
main.swift:19:19: note: overloads for '+' exist with these partially matching parameter lists: (Int, Int), (Int32, Int32)
 UInt32(a + b + a + b) // 15 seconds
                  ^
main.swift:19:17: error: cannot convert value of type 'Int' to expected argument type 'Int32'
 UInt32(a + b + a + b) // 15 seconds
                ^
                Int32( )
main.swift:19:11: error: binary operator '+' cannot be applied to operands of type 'Int' and 'Int32'
 UInt32(a + b + a + b) // 15 seconds
        ~ ^ ~
main.swift:19:11: note: overloads for '+' exist with these partially matching parameter lists: (Int, Int), (Int32, Int32)
 UInt32(a + b + a + b) // 15 seconds
          ^

At 5 terms operation, it seems that the compiler found something else that matches the signature of this expression (I'm guessing because it tries to suggest that parameter #1 could be either a Float or a Double)

main.swift:21:16: error: cannot convert value of type 'Int32' to expected argument type 'Int'
UInt32(a + a + b + a + a) // 26 seconds
               ^
               Int( )
main.swift:21:1: error: no exact matches in call to initializer 
UInt32(a + a + b + a + a) // 26 seconds
^
main.swift:21:1: note: candidate expects value of type 'Float' for parameter #​1
UInt32(a + a + b + a + a) // 26 seconds
^
main.swift:21:1: note: candidate expects value of type 'Double' for parameter #​1
UInt32(a + a + b + a + a) // 26 seconds
^
main.swift:21:1: note: candidate expects value of type 'Float80' for parameter #​1
UInt32(a + a + b + a + a) // 26 seconds

I did not try to add more terms, so I cannot say whether the time increase is constant or exponential per new terms added, but it would be trivial to test.

I'm attaching a sample I took of the swift-frontend process when this was running.

+ 2487 swift::constraints::ConstraintSystem::salvage() (in swift-frontend) + 290 [0x1032de772]
 + 1249 swift::constraints::ConstraintSystem::solveImpl(llvm::SmallVectorImpl<swift::constraints::Solution>&) (in swift-frontend) + 449 [0x10325e7f1]
 + ! 388 swift::constraints::ComponentStep::take(bool) (in swift-frontend) + 710 [0x10326f266]

If I understood this sample correctly, it seems that the ConstraintSystemSolver is struggling with this specific example.

Should I open a new bug for the performance improvement ?

All the best, Marco.

@swift-ci
Copy link
Collaborator Author

Comment by Marco (JIRA)

Here is the code that I used to reproduce this

//
//  main.swift
//  swift5-5test
//
//  Created by Marco on 26/05/2021.
//


import Foundation


print("Hello, World!")


let a: Int = 1
let b: Int32 = 2


// UInt32(a + b) // 0.7 seconds


// UInt32(a + b + a) // 1.2 seconds


// UInt32(a + b + a + b) // 15 - 20 seconds


// UInt32(a + a + b + a + a) // 26 seconds

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself type checker Area → compiler: Semantic analysis
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@stephentyrone @hborla @swift-ci