[SR-10130] Type-check time regression

[zienag]

Previous ID	SR-10130
Radar	rdar://problem/48992848
Original Reporter	@zienag
Type	Bug

Environment

$ swift --version
Apple Swift version 5.0 (swiftlang-1001.0.69 clang-1001.0.45.2)
Target: x86_64-apple-darwin18.2.0

and

$ swift --version
Apple Swift version 4.2.1 (swiftlang-1000.11.42 clang-1000.11.45.1)
Target: x86_64-apple-darwin18.2.0

Additional Detail from JIRA

Votes	3
Component/s	Compiler
Labels	Bug
Assignee	@xedin
Priority	Medium

md5: f9286493c3d7b5a218f3e92d60bde680

relates to:

• SR-10461 Unable to type check expression, Xcode 10.2 regression

Issue Description:

The following code compiles successfully in swift 4.2, and fails in swift 5:

let itemsPerRow = 10
let size: CGFloat = 20
let margin: CGFloat = 10
let foo = (0..<100)
  .map { (row: CGFloat($0 / itemsPerRow), col: CGFloat($0 % itemsPerRow)) }
  .map {
    CGRect(x: $0.col * (size + margin) + margin,
           y: $0.row * (size + margin) + margin,
           width: size,
           height: size)
}
print(foo)

Error:

test/main.swift:24:4: error: the compiler is unable to type-check this expression in reasonable time; try breaking up the expression into distinct sub-expressions
  .map {
~~~^~~~~

[theblixguy]

cc @xedin

[xedin]

Unfortunately this is an expected breakage due to new operator overloads introduced by SIMD. As a workaround you can split expression in the second `map` into multiple variables e.g. `x` and `y` before using it in the constructor.

[swift-ci]

Comment by Alexander Skvortsov (JIRA)

Return value of each `map` closure is explicit (it's `(row: CGFloat, col: CGFloat)` and `CGRect`), which type-checking does it exactly need?

[swift-ci]

Comment by Alexander Skvortsov (JIRA)

Ok, seems like it can't choose type for `0..<100` and `itemsPerRow`. Isn't there an option to just check the default case (i.e. `Range<Int>` and `Int`) first? Does the compiler really need to check all other options if default one works fine?

[xedin]

The problem here are operators, `0..<100` is just a consequence. Type checker has to figure out what is the best type for each CGRect constructor argument, which leads to exponential behavior in the solver, because `+`, for example, has a lot of overloads and since 4.2 it gained some more new generic ones too related to SIMD.

[swift-ci]

Comment by Alexander Skvortsov (JIRA)

All types used in CGRect constructor are explicitly specified in code:

$0.col * (size + margin) + margin

`$0.col` is explicitly `CGFloat` (as it was initialised by `CGFloat` constructor), `size` and `margin` type are explicitly defined as `CGFloat` in declarations. Same for all other constructor args.

[zienag]

If I understood you correctly, according to your explanation the following code would fail as well:

let itemsPerRow = 10
let size: CGFloat = 20
let margin: CGFloat = 10
let col: CGFloat = 5
let row: CGFloat = 2
let rect = CGRect(x: col * (size + margin) + margin,
                  y: row * (size + margin) + margin,
                  width: size,
                  height: size)

But it is working well. If I split CGRect initializer, it gives another error:

let foo = (0..<100)
  .map { (row: CGFloat($0 / itemsPerRow), col: CGFloat($0 % itemsPerRow)) }
  .map {
    let x = $0.col * (size + margin) + margin
    let y = $0.row * (size + margin) + margin
    return CGRect(x: x,
                  y: y,
                  width: size,
                  height: size)
}
// Error:
main.swift:26:27: error: ambiguous reference to member '/'
  .map { (row: CGFloat($0 / itemsPerRow), col: CGFloat($0 % itemsPerRow)) }
                          ^

The workaround that actually works is to explicitly specify type of range, and leave everything else intact:

let foo = (0..<100 as Range<Int>)
  .map { (row: CGFloat($0 / itemsPerRow), col: CGFloat($0 % itemsPerRow)) }
  .map {
    CGRect(x: $0.col * (size + margin) + margin,
           y: $0.row * (size + margin) + margin,
           width: size,
           height: size)
}

But, the most weird part is when you try split CGRect initializer AND specify range's type:

let foo = (0..<100 as Range<Int>)
  .map { (row: CGFloat($0 / itemsPerRow), col: CGFloat($0 % itemsPerRow)) }
  .map {
    let x = $0.col * (size + margin) + margin
    let y = $0.row * (size + margin) + margin
    return CGRect(x: x,
                  y: y,
                  width: size,
                  height: size)
}
// Error:
main.swift:26:27: error: ambiguous reference to member '/'
  .map { (row: CGFloat($0 / itemsPerRow), col: CGFloat($0 % itemsPerRow)) }
                          ^

The compiler is acting really weirdly, and, if you ask me, I can't imagine why it can be an expected behavior.

[xedin]

The problem here is that everything starting from `let foo = ` is considered a single expression, it helps somewhat that `size`, `margin` and other variables have fixed types, but the rest of the types used here are overloaded - `map`, operators (including range operator ..<), CGFloat, CGRect constructors etc. Once you specify type for range it makes it easier for solver to deduce type signature of the `map` which helps to resolve the rest.

Splitting second map into `x, y` and CGRect calls makes body of the closure type-check separately from the rest of the expression, that's probably what is the source of ambiguity with `/` because function signature is deduced to a different type. I think if you specify second map function signature explicitly it would type-check just fine without a need to specify `as Range<Int>`.

[swift-ci]

Comment by Alexander Skvortsov (JIRA)

Can you please once again explain why the return value of `map { (row: CGFloat($0 / itemsPerRow), col: CGFloat($0 % itemsPerRow)) }` is ambiguous? For me it's clearly `(row: CGFloat, col: CGFloat)`, it does't depend on any of types of variables used inside. How `CGRect`-closure can even affect this?

[xedin]

DeeSee (JIRA User) Swift type-checker employs bi-directional inference, so types could come from closure body too, and since there is no explicit type set for e.g. $0 it could be inferred either from one of the `map` overloads (which is itself generic) or from operator it's used it in (either / or %) and operators are overloaded e.g. https://swiftdoc.org/v4.2/operator/slash/ as well as CGFloat constructor, so it what might be obvious to the human, is not always obvious to the algorithm.

[swift-ci]

Comment by Alexander Skvortsov (JIRA)

> so types could come from closure body too

How they could come from closure body if it consists of only one return statement with explicitly specified return type? I don't currently mean the details of current type inference implementation in Swift, because obviously it's a subject to improve (especially considering such weird compiler errors)

[slavapestov]

Still slow, I'll add it to the test suite.