Attachment: Download

Issue Description:

When the swift parser encounters a square bracket ('['), it needs to determine whether an Array or a Dictionary is starting. Swift does this by parsing the next expr, and then checking for a ':'. The parser then backtracks, throwing the results away, and parses the whole square bracketed expr list, re-parsing the first expr a second time.
<https://github.com/apple/swift/blob/b2f60bf97857aaf898d8c2fffbdff91ef32cf7f0/lib/Parse/ParseExpr.cpp#L3379:L3399>
In nested square brackets, each level doubles the number of re-parses of the head element.

That is:

• when parsing a bracketed expression list, swift parses the first expression twice.

• parsing an expression parses all sub-expressions

• -> swift parses the first expr of a sbl 2^d times, d = depth of the bracketing.

So this will never finish parsing:

let b =     [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[ 
            [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[
            [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[ 
            [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[       
            [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[
            [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[
            [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[ 
            [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[
            1           
              ]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
            ]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
            ]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
            ]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
            ]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
            ]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]        
            ]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
            ]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]

To see that the parser is responsible, and not type checking, replace this code:
<https://github.com/apple/swift/blob/b2f60bf97857aaf898d8c2fffbdff91ef32cf7f0/lib/Parse/ParseExpr.cpp#L3379:L3399>
with

 bool ParseDict = false;

This removes non-empty dictionaries and the speculative parsing needed to identify them from the grammer. Now, the parser dose not hang.

The other brackets '(' and '{' do not have this issue, it is specific to '[' and the backtracking used to distinguish `[ x ]` from `[ x:y ]`.

There are several options here.

*Do nothing.
The example above was developed as a test of the compiler's cutoff of nested structures, anyone not torturing the parser is at lower risk.

*Impose an lower cutoff on square brackets then other structures.

*Remember the results of the first speculative parse.
While in a speculative-parse, store and retain the whether each '[' started an arr or dict.
This still parses heads twice, but not (2^d)-times.