Bitwise operation between UInt and Int makes type check exceed time limit

[ecnelises]

Description

This code triggers 'the compiler is unable to type-check this expression in reasonable time' error.

Steps to reproduce

func test() -> Int {
  let pieces = [1, 2, 3, 4]
  let snum = (UInt(pieces[0]) << 24) | (UInt(pieces[1]) << 16) | (UInt(pieces[2]) << 8) | pieces[3]
  return Int(snum % 1000)
}

error: repl.swift:11:14: error: the compiler is unable to type-check this expression in reasonable time; try breaking up the expression into distinct sub-expressions
  let snum = (UInt(pieces[0]) << 24) | (UInt(pieces[1]) << 16) | (UInt(pieces[2]) << 8) | Int(pieces[3])
             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Expected behavior

Swift doesn't allow bitwise or between UInt and Int type. With simpler code, the compiler outputs expected error message:

func test() -> Int {
  let pieces = [1, 2, 3, 4]
  let snum = UInt(pieces[0]) | UInt(pieces[1]) | UInt(pieces[2]) | pieces[3]
  return Int(snum % 1000)
}

error: repl.swift:13:66: error: binary operator '|' cannot be applied to operands of type 'UInt' and 'Int'
  let snum = UInt(pieces[0]) | UInt(pieces[1]) | UInt(pieces[2]) | pieces[3]
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ^ ~~~~~~~~~

Environment

• Swift compiler version info

Apple Swift version 5.7 (swiftlang-5.7.0.127.4 clang-1400.0.29.50)
Target: arm64-apple-darwin21.6.0

• Xcode version info: N/A
• Deployment target: N/A

[AnthonyLatsis]

Each of these similar examples hit the threshold as well:

do {
  let x: UInt
  let y: Int

  let _ = (x << x) | (x << x) | (x << x) | (x << x) | y

  let _ = (UInt(y) << x) | (UInt(y) << x) | (UInt(y) << x) | y
}

[Rajveer100]

What could be the fix for error: the compiler is unable to type-check this expression in reasonable time; try breaking up the expression into distinct sub-expressions because this seems to be an internal compiler (type checker) threshold, I mean where could one start with for the fix...

This actually seems like a bigger issue not limited to just this example and complexity of the expressions, several people have encountered this as seen in many discussion forums, which lead them to break them into simpler expressions making them write more code, but many other cases, like it also depends on the CPU...(I think 15 seconds is the time limit for Swift for it to analyse)...

[Rajveer100]

@AnthonyLatsis @ecnelises

[AnthonyLatsis]

This is a performance issue with the type checker. Performance can mean a lot of things, including time, memory usage, and other data metrics specific to a particular algorithm. Getting an idea of how to solve this at least theoretically requires theoretical and practical knowledge of how expression solving works and its weak spots. You can find a more or less detailed theoretical breakdown of the type checker in the repository’s docs directory.

Keep in mind though, this is by no means a good first issue.

[Rajveer100]

Hmm, alright, seems quite deep! Thanks for the explanation!

[peacedudes]

The root cause of this is reproducible with:

let x = 0 + 0 + 0 + 0 + "0"

expression failed to parse:
error: repl.swift:1:10: error: the compiler is unable to type-check this expression in reasonable time; try breaking up the expression into distinct sub-expressions
let x = 0 + 0 + 0 + 0 + "0"
^~~~~~~~~~~~~~~~~~~

. . .

It's curious to start with 0 + "0" and see reasonable compiler warnings become progressively less helpful as another term is added. The errors I'm seeing in latest playground go like this.

(1)

expression failed to parse:
error: Untitled Page.xcplaygroundpage:4:11: error: binary operator '+' cannot be applied to operands of type 'Int' and 'String'
let x = 0 + "0"
~ ^ ~~~

Untitled Page.xcplaygroundpage:4:11: note: overloads for '+' exist with these partially matching parameter lists: (Int, Int), (String, String)
let x = 0 + "0"
^

(2, 3)

expression failed to parse:
error: Untitled Page.xcplaygroundpage:4:15: error: operator function '+' requires that 'RunLoop.SchedulerTimeType.Stride' conform to 'Sequence'
let x = 0 + 0 + "0"
^

Swift.RangeReplaceableCollection:3:35: note: where 'Other' = 'RunLoop.SchedulerTimeType.Stride'
@inlinable public static func + (lhs: Other, rhs: Self) -> Self where Other : Sequence, Self.Element == Other.Element
^

(4) as shown above; where the compiler lost it's way

This bug is old and slows compile times when it happens.

[Rajveer100]

Thanks for the explanation! @peacedudes