What is wrong with type inference?

Using Swift
1

When I try to compile the following expression:

let colorRectangles: [Rectangle] = (0..<colors.count).map { i in
    return Rectangle(
        x: 20.0 + 100.0 * Float(i % 7) + 10.0 * Float(i % 7),
        y: 80.0 + 100.0 * Float(i / 7) + 10.0 * Float(i / 7),
        width: 100.0,
        height: 100.0
    )
}

I get the familiar error: error: the compiler is unable to type-check this expression in reasonable time; try breaking up the expression into distinct sub-expressions. What confuses me is that this seems like a simple case where all types should be obvious. Breaking it into smaller parts or explicitly typing the closure parameter as (i: Int) in instead of i in fixes it. Another solution is to replace colors.count with an intermediate variable, like this:

let maxColorsCount = colors.count
let colorRectangles: [Rectangle] = (0..<maxColorsCount).map { i in
    return Rectangle(
        x: 20.0 + 100.0 * Float(i % 7) + 10.0 * Float(i % 7),
        y: 80.0 + 100.0 * Float(i / 7) + 10.0 * Float(i / 7),
        width: 100.0,
        height: 100.0
    )
}

All variables in this expression, except i, have explicit types. Rectangle has a single constructor that takes four Float parameters. Since colors.count is an Int, the range 0..<colors.count is inferred as Range. Given that map accepts a closure of type (Int) -> T, the type of i should be unambiguously inferred as Int. Yet, the compiler still struggles.

I see the same issue here:

let numbers = [Int](repeating: 0, count: 20)
let myFloats: [Float] = (0..<numbers.count).map { i in 
    return 20.0 + 100.0 * Float(i % 2) + 10.0 * Float(i * 5)
}

Again, using an intermediate variable for numbers.count resolves it. I know type inference can have exponential worst-case complexity, but these expressions feel straightforward. Even something like let result: Double = -(-(1 + 1) + -(1 + 1) - 1) + (-1 + 1 - (-1) + (-1)) takes too long to compile, despite its simplicity.

Can anyone explain what’s happening? Also, I’ve noticed that switching Double to Float in that last example allows it to compile, though it’s still slow (4.26 seconds on my machine). Why does this change make a difference?

Lastly, has anyone confirmed that Swift’s type inference algorithm is as efficient as it could be? Could tweaks like adjusting evaluation order or adding memoization improve it in cases like these?

2

This example is not self-contained, but I was able to reproduce the problem by adding a few more lines:

struct Rectangle {
 let x: Float
 let y: Float
 let width: Float
 let height: Float
}

let colors: [Int] = []

@xedin is working on some improvements in [ConstraintSystem] Return of the new disjunction favoring/selection algorithm by xedin · Pull Request #79461 · swiftlang/swift · GitHub. With those changes, the offending expression type checks in 16 milliseconds.

This also becomes fast.

Unfortunately this one is still slow.

You might find this interesting: How does compiler compile SwiftUI code? - #4 by Slava_Pestov

No, there are many ways its performance could be improved. (This is of course true for almost any non-trivial piece of code.)

11 Likes