Peek past balanced parens to see if they are an expression or lambda.

Peek past balanced parens to see if they are function parameters (followed by '{' or '=>') or an expression.
The VM uses the same look-ahead technique.

This avoids the need to parse a formal parameters list first as an expression list and then convert it into formal parameters by re-parsing the expression fragments.

A map is maintained to avoid rescanning the tokens.  The map is from position of open paren to token following close paren.

There is no practical measurable performance difference but there are some measurable differences on pathological inputs that contain insane numbers of parens.  The map prevents these pathological inputs from having a performance effect other than a small constant factor.

The worst is insanely deep parens.

(((x)))  parens 2000 deep      old: 260ms, new: 640ms       - mostly hash table access.
(((x+x)+(x+x))+((x+x)+(x+x)))  old: 2.24,  new: 2.40        - 16k expression.
f()()()...  900 calls deep,    old: 480ms, new: 390ms
f = ()=>()=>()=> ... =>1;      old: 870ms, new: 840ms       - 100 functions deep.

frogsh: old: 1.370 new: 1.380


BUG=
TEST=

[sra1, 2011-10-31 05:30:17]

I think we should parse formal lists this way.

- avoids the need for crazy tree rewriting
- makes no performance difference in ordinary code
- pathological cases are limited to a small constant slower
- the VM parser does a similar lookahead

[jimhug, 2011-10-31 14:16:46]

This looks really good to me.  I'm pretty sold by the fact that it is simpler
and shorter code without any noticeable perf impacts.  Thanks for doing this!

The one remaining worry I have is if there might be any interactions between
this change and diet parsing support.  We aren't currently using diet parsing as
at the moment it causes a perf degredation.  However, this mode will be
important for tooling even if the perf issues with the tokenizer never get
resolved.  Could you do the experiment of manually setting the options.dart
(dietParse option) to true and ensure that the tests all still pass?

http://codereview.chromium.org/8400017/diff/10002/parser.dart
File parser.dart (right):

http://codereview.chromium.org/8400017/diff/10002/parser.dart#newcode16
parser.dart:16: TokenSource tokenizer;
Note: This change seems good independent of the rest.

http://codereview.chromium.org/8400017/diff/10002/parser.dart#newcode1136
parser.dart:1136: if (pos > _highestCachePosition)
Style: The return either needs to be on the same line as the if or it needs {}'s
surrounding it.

http://codereview.chromium.org/8400017/diff/10002/parser.dart#newcode1609
parser.dart:1609: class DivertedTokenSource implements TokenSource {
Now that you've provided this, I'd love to do an experiment where we first
Tokenize and then parse the file.  I can' work out in my head how that will turn
out  - since I think it will have to do with cache contention issues more than
anything else.

http://codereview.chromium.org/8400017/diff/10002/parser.dart#newcode1618
parser.dart:1618: ++_pos;
Style: prefer _pos++ for this bare increment.

[jimhug, 2011-11-22 18:22:06]

lgtm