[SR-3668] "Expression was too complex" errors for short dictionary literals of simple closure expressions

[swift-ci]

Previous ID	SR-3668
Radar	rdar://problem/30213053
Original Reporter	chowell (JIRA User)
Type	Bug

Environment

macOS 10.12.2, MacBook Pro (Retina, 15-inch, Mid 2014) Swift version 3.1-dev (LLVM 7e421db87c, Clang 80a3776e67, Swift a43bebb7c1)

Additional Detail from JIRA

| | | |------------------|-----------------| |Votes | 0 | |Component/s | Compiler | |Labels | Bug, Performance, TypeChecker | |Assignee | None | |Priority | Medium | md5: e03eaff993e24b14bc7af8e8623ef449

Issue Description:

A short dictionary literal with values that are simple closure expressions can cause the Swift compiler to report an "expression was too complex to be solved in reasonable time" error, following a large increase in CPU and memory usage. This happens most readily when the closure expression contains an operator that is heavily overloaded, which is true for many common expression operators. This problem is not new; the latest code in current master is affected, but so are the Swift 3.0.2 and Swift 2.3 toolchains in Xcode 8.2.1. (I tested using the "swift" command REPL in all cases: for current master this is the integrated development REPL, while for the Xcode toolchains it's the LLDB-based REPLs.)

Only dictionary literals suffer from this problem; array literals seem to be completely unaffected.

A trivial example using ==, which seems to be the most heavily overloaded operator:

let d: [Int: (Int) -> Bool] =
    [ 0: { $0 == $0 }, 1: { $0 == $0 }, 2: { $0 == $0 }, 3: { $0 == $0 } ]

For current master and Xcode's Swift 3.0.2, this is just over the threshhold of failure; if one element is removed from the literal, the expression is evaluated successfully, although still with high CPU and memory usage. (For Xcode's Swift 2.3, the failure threshhold is three elements rather than four.)

Another example with unary minus, which is much less heavily overloaded:

let d: [Int: (Int) -> Int] =
    [ 0: { -$0 }, 1: { -$0 }, 2: { -$0 }, 3: { -$0 }, 4: { -$0 },
      5: { -$0 }, 6: { -$0 }, 7: { -$0 }, 8: { -$0 } ]

Again, this is just over the failure threshhold for current master, and it will pass if one element is removed. (For Xcode's Swift 3.0.2, the failure threshhold is seven elements; for Swift 2.3, it is six elements.)

Other operators, like infix +, *, |, \<, and prefix \~, lie between these extremes in terms of how many closure expression values are needed in the literal to trigger an error.

I don't think it makes a difference whether the closures that use infix operators take two distinct operands or a single one; I chose the latter to simplify the testcases. Also, the types of the closure operands or results doesn't seem to matter for this, and neither does the type of the dictionary keys (again, I chose Int for simplicity).

While these testcases are obviously contrived, I first encountered this problem while working on Stanford's online course "Developing iOS 9 Apps with Swift", which is linked to from Apple's own Swift developer resources web page. That course's first lectures and its initial programming project implement a calculator app. This app uses a dictionary, initialized by a literal, with values that are enums which themselves have associated values, and some of these associated values are simple closure expressions. The dictionary allows each operation key's mathematical operation to be looked up and invoked in a simple and elegant manner, and it can be easily extended to add more operations just by adding more elements to the literal--but this is where you get bitten by the "expression was too complex" problem. (In fact, SR-2102, which is marked as Resolved, seems to be an instance of this very problem and is obviously derived from the Stanford course.)

While Stanford's course used Xcode 7.3 and Swift 2.2, I was working on it in Xcode 8.2.1 with Swift 3.0.2; I found the problem affected not just the compiler but also SourceKitService, so syntax highlighting was also affected. I'm running macOS 10.12.2 and found it difficult to test Swift 2.2 on this platform, but since it does affect Swift 2.3, it seems likely to have been in Swift 2.2 as well.

[swift-ci]

Comment by Colin Douglas Howell (JIRA)

Apologies for the extra Environment edits; I was struggling to get all the text I wanted to format properly before giving up.

[swift-ci]

Comment by Colin Douglas Howell (JIRA)

I've found an interesting exception to this which only seems to affect Swift 3.0.2 (as tested in Xcode 8.2.1).

The examples mentioned above all use the syntactic sugar for a Dictionary type annotation, "[KeyType: ValueType]".

If instead, we use a type annotation of the form "Dictionary\<KeyType, ValueType>", Swift 3.0.2 seems to handle these dictionary literals much like array literals are handled: there is no excessive CPU or memory consumption, and no errors of "expression was too complex" are produced.

As an example,

let d: [Int: (Int) -> Bool] =
    [ 0: { $0 == $0 }, 1: { $0 == $0 }, 2: { $0 == $0 }, 3: { $0 == $0 } ]

generates an "expression was too complex" error. However,

let d: Dictionary<Int, (Int) -> Bool> =
    [ 0: { $0 == $0 }, 1: { $0 == $0 }, 2: { $0 == $0 }, 3: { $0 == $0 } ]

or even

let d: Dictionary<Int, (Int) -> Bool> =
    [ 0: { $0 == $0 }, 1: { $0 == $0 }, 2: { $0 == $0 }, 3: { $0 == $0 },
      4: { $0 == $0 }, 5: { $0 == $0 }, 6: { $0 == $0 }, 7: { $0 == $0 },
      8: { $0 == $0 }, 9: { $0 == $0 }, 10: { $0 == $0 }, 11: { $0 == $0 },
      12: { $0 == $0 }, 13: { $0 == $0 }, 14: { $0 == $0 }, 15: { $0 == $0 },
      16: { $0 == $0 }, 17: { $0 == $0 }, 18: { $0 == $0 }, 19: { $0 == $0 } ]

both evaluate instantly with no error.

This seems to affect all operators I've tested, including prefix \~, except for unary minus and unary plus. Also, it only applies to Swift 3.0.2; neither the current master nor Xcode 8.2.1's Swift 2.3 toolchain show this behavior.

As I said, for closure expressions with unary minus or unary plus, using a type annotation of "Dictionary\<KeyType, ValueType>" for the declaration makes no difference on Swift 3.0.2. Both of the following declarations fail:

let d: [Int: (Int) -> Int] =
    [ 0: { -$0 }, 1: { -$0 }, 2: { -$0 }, 3: { -$0 }, 4: { -$0 },
      5: { -$0 }, 6: { -$0 } ]

let d: Dictionary<Int, (Int) -> Int> =
    [ 0: { -$0 }, 1: { -$0 }, 2: { -$0 }, 3: { -$0 }, 4: { -$0 },
      5: { -$0 }, 6: { -$0 } ]

and so do the declarations:

let d: [Int: (Int) -> Int] =
    [ 0: { +$0 }, 1: { +$0 }, 2: { +$0 }, 3: { +$0 }, 4: { +$0 },
      5: { +$0 }, 6: { +$0 }, 7: { +$0 }, 8: { +$0 }, 9: { +$0 } ]

let d: Dictionary<Int, (Int) -> Int> =
    [ 0: { +$0 }, 1: { +$0 }, 2: { +$0 }, 3: { +$0 }, 4: { +$0 },
      5: { +$0 }, 6: { +$0 }, 7: { +$0 }, 8: { +$0 }, 9: { +$0 } ]

[swift-ci]

Comment by Colin Douglas Howell (JIRA)

(Though my previous comment was for Swift 3.0.2, the following refers to current master.)

I've been investigating this problem further, and I think I now have a much clearer idea why it only affects dictionary literals and not array literals. When the type checker's constraint solver generates its initial constraints, array expressions use a performance optimization that dictionary expressions don't get.

Consider the array declaration:

let a: [(Int, (Int) -> Int)] = [(0, {+$0}), (1, {+$0})]

versus the dictionary declaration:

let d: [Int: (Int) -> Int] = [0: {+$0}, 1: {+$0}]

(I deliberately made the array declaration an array of (Int, (Int) -> Int) tuples for greater consistency with the dictionary, whose elements are treated as (key, value) tuples.)

If I turn on constraint debugging output in the integrated REPL (":constraints debug on") just before entering each of these declarations, it starts by printing the initial constraints for the expression. For the array declaration, the printed expression starts with the line:

(array_expr type='[(Int, (Int) -> Int)]' location=<REPL Input>:1:32 range=[<REPL Input>:1:32 - line:1:55]

The expression's overall type has already been set to match the contextual type, which comes from the declaration's type annotation:

Contextual Type: [(Int, (Int) -> Int)] at [<REPL Input>:1:8 - line:1:28]

But for the dictionary declaration, no such setting is done. The printed expression begins with:

(dictionary_expr type='$T14' location=<REPL Input>:1:30 range=[<REPL Input>:1:30 - line:1:49]

The type is just an ordinary type variable which must be solved like all the others, even though the contextual type has the type annotation information:

Contextual Type: [Int : (Int) -> Int] at [<REPL Input>:1:8 - line:1:26]

A few additional constraints are added relating to the dictionary_expr's type variable, but these don't seem to be enough to keep the number of potential solutions from growing exponentially with the number of elements in the literal.

By contrast, when the array expression's overall type is set, additional constraints are also added for each of the expression's elements, and the solver seems able to solve each in isolation, so the performance is far better.

I found this difference in handling was because of a difference between ConstraintGenerator::visitArrayExpr() and ConstraintGenerator::visitDictionaryExpr(), both in lib/Sema/CSGen.cpp. The code in lines 1698-1727 of this file, within visitArrayExpr(), checks for a contextual type and, if one exists, applies it to the array_expr and adds corresponding constraints for its elements. Nothing like this is done in visitDictionaryExpr().

The optimization for array expressions was added in May 2014 by the commit:

https://github.com/apple/swift/commit/a22b391e2ac7d52d2eaf2717588e15f8cd4b3afa

The committer remarked "There's a lot more that can be done with this...", but it doesn't seem like anything else has been. I don't see any obvious reason why an equivalent optimization could not be added to visitDictionaryExpr(), though it might be a little more complicated.

[swift-ci]

Comment by Colin Douglas Howell (JIRA)

(I'd like to apologize for my previous comment, The committer remarked "There's a lot more that can be done with this...", but it doesn't seem like anything else has been. When I said that, I hadn't realized that commit had actually added the entire infrastructure for examining contextual type information, which I see has certainly been used since by other parts of constraint generation.)

[swift-ci]

Comment by Colin Douglas Howell (JIRA)

I've just submitted a fix for this bug as pull request #6973. The fix passes swift/test, and I've manually tested it on dictionary literal expressions like those mentioned above; it definitely solves the problem.

[DougGregor]

@swift-ci create