IDL parser

PEG Parser: under review at http://codereview.chromium.org/8399029

Some features are not yet implemented (e.g. attributes).

BUG=
TEST=

Committed: https://code.google.com/p/dart/source/detail?r=869

[Jennifer Messerly, 2011-10-28 01:21:10]

I didn't look in detail through the IDL parser, but it's neat how
simple/tweakable it is :)

http://codereview.chromium.org/8404031/diff/2001/client/dom/scripts/idlparser...
File client/dom/scripts/idlparser.dart (right):

http://codereview.chromium.org/8404031/diff/2001/client/dom/scripts/idlparser...
client/dom/scripts/idlparser.dart:8: final int FREMONTCUT_SYNTAX = 2;
new name for this?

http://codereview.chromium.org/8404031/diff/2001/client/dom/scripts/idlparser...
client/dom/scripts/idlparser.dart:36: this.annotations = annotations;
you can use "this.annotations" in the arg list

http://codereview.chromium.org/8404031/diff/2001/client/dom/scripts/idlparser...
client/dom/scripts/idlparser.dart:37: this.interfaces = elements.filter((e) => e
is IDLInterface);
shouldn't need "this."

http://codereview.chromium.org/8404031/diff/2001/client/dom/scripts/idlparser...
client/dom/scripts/idlparser.dart:54: }
indent +2

http://codereview.chromium.org/8404031/diff/2001/client/dom/scripts/idlparser...
client/dom/scripts/idlparser.dart:62: //IDLType.nullable(IDLType base) {
remove or add TODO?

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart
File utils/peg/pegparser.dart (right):

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:1: #library('Peg Parser');
Do they intend to allow spaces in the name? (I'm not entirely sure what the
names are for... if it's descriptive, then spaces totally makes sense.)

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:4: * The following functions are combinators for
building Rules.
awesome comment!

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:42: if (spec is int)
I hesitate to suggest style for someone else's code. feel free to ignore style
nits :)

but fwiw, the C++ guide (and JS) generally has { } around if-body, unless it's a
single line if.
(http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Conditionals)

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:55: return new _AnyCharRule();
const?

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:62: codes.sort((a, b) =>  a < b ? -1 : a > b ? 1 : 0);
codes.sort((a, b) => a.compareTo(b));
...since num is Comparable?

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:68: List<bool> flags = new List<bool>(len);
style nit: repeated type name

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:70: flags[i] = false;
I wonder if we should have a BitList class somewhere in the core libs.
Not a big deal for these guys though, since presumably IDL isn't going to use
crazy 32-bit unicode chars :)

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:184: _Rule
OR([a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]) =>
something tells me you wanted spread/rest args :)

Does it look too bad to use [...] at the call sites?

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:216: class Grammar {
In theory, you could get by without this class? It seems like the main thing it
does is skip whitespace. (holds onto Symbols, too, but those could easily be
stored in variables)

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:227: //whitespace = OR([' ', '\t', '\r', '\n']);
remove?

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:228: this.whitespace = CHAR(' \t\r\n');
shouldn't need "this." anymore now that the bug is fixed

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:235: Symbol operator [](String name) {
Could define a setter too that would set the Symbol.def? Hmm, maybe that's too
strange because the types would be different.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:248: for (var symbol in _symbols.getValues())
style nit: curlies

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:264: // TODO: locate error and describe.
ah, error messages, the hard part of Packrat parsers :)

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:269: for (var rule in state.max_rule)
if we got here, isn't state.max_rule empty? should the check above be !isEmpty?

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:272: tokens.sort((a, b) =>
a.startsWith("'")==b.startsWith("'") ? a.compareTo(b)
style nit: long line, spaces etc

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:322: bool in_whitespace_mode = false;
style nit: camelCase

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:400: _Rule _compile_optional(rule) {
why not put this check in _compile?
style nit: name should be _compileOptional

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:404: _Rule _compile(rule) {
I found the name "compile" a bit confusing here. Not sure what to suggest
instead though.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:436: throw new ParseError(message);
include position?

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:445: _CharCodeRule(Function this._predicate,
this._name);
don't need to repeat the type "Function" here.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:447: if (pos == state._end)
I wonder if there's a way to do this without checking this condition in every
rule

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:504: if (pos + _len > state._end)
should be >=, to match a string at the end ?

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:680: if (match == null)
I often write this as:
return (match == null) ? [pos, null] : match;

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:771: // TODO: figure out how to discard the map and
parseInstance after parsing.
Well, normally you'd have the memoization be per-rule, in essence caching the
result of _Rule._match. That's how the "linear" complexity of PEGs is derived.
Of course, the memo becomes pretty expensive at that point, so common
optimization is to do it per-symbol. That would work pretty nicely with this
architecture since Grammar knows about all Symbols already. Maybe just mark the
symbol as memo/no-memo.

But if you wanted to keep this architecture you're using (with an explicit
memoization rule), probably you want the Grammar to know about MEMO rules so it
can init/clean them each time a top-level parse happens.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:787: return map[pos];
btw: instead of doing two lookups via "map.containsKey(pos)" then "map[pos]" you
can just do "map[pos]" and return the result if it's != null.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser_test.dart
File utils/peg/pegparser_test.dart (right):

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser_test.dar...
utils/peg/pegparser_test.dart:4: testParens() {
tests, awesome :)

[sra1, 2011-10-28 05:06:25]

Thanks for the review.
Vijay - any comments.

http://codereview.chromium.org/8404031/diff/2001/client/dom/scripts/idlparser...
File client/dom/scripts/idlparser.dart (right):

http://codereview.chromium.org/8404031/diff/2001/client/dom/scripts/idlparser...
client/dom/scripts/idlparser.dart:54: }
On 2011/10/28 01:21:10, John Messerly wrote:
> indent +2

Done.

http://codereview.chromium.org/8404031/diff/2001/client/dom/scripts/idlparser...
client/dom/scripts/idlparser.dart:62: //IDLType.nullable(IDLType base) {
On 2011/10/28 01:21:10, John Messerly wrote:
> remove or add TODO?

Done.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart
File utils/peg/pegparser.dart (right):

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:1: #library('Peg Parser');
On 2011/10/28 01:21:10, John Messerly wrote:
> Do they intend to allow spaces in the name? (I'm not entirely sure what the
> names are for... if it's descriptive, then spaces totally makes sense.)

My working hypothesis is if it was meant to be an identifier, the syntax would
be an identifier.

But we also have:
#import('...', prefix: 'a string');
:-)

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:42: if (spec is int)
On 2011/10/28 01:21:10, John Messerly wrote:
> I hesitate to suggest style for someone else's code. feel free to ignore style
> nits :)
> 
> but fwiw, the C++ guide (and JS) generally has { } around if-body, unless it's
a
> single line if.
> (http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Conditionals)

I'm experimenting. cpp style does not actually say the braces are needed here,
juts that both legs must have them if one leg does.  I read omission as
permission.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:55: return new _AnyCharRule();
On 2011/10/28 01:21:10, John Messerly wrote:
> const?

Done.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:62: codes.sort((a, b) =>  a < b ? -1 : a > b ? 1 : 0);
On 2011/10/28 01:21:10, John Messerly wrote:
> codes.sort((a, b) => a.compareTo(b));
> ...since num is Comparable?

I could, but the Frog code is kind of disgusting.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:68: List<bool> flags = new List<bool>(len);
On 2011/10/28 01:21:10, John Messerly wrote:
> style nit: repeated type name

Done.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:70: flags[i] = false;
On 2011/10/28 01:21:10, John Messerly wrote:
> I wonder if we should have a BitList class somewhere in the core libs.
> Not a big deal for these guys though, since presumably IDL isn't going to use
> crazy 32-bit unicode chars :)

The bitlist would probably be slower in access too.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:184: _Rule
OR([a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]) =>
On 2011/10/28 01:21:10, John Messerly wrote:
> something tells me you wanted spread/rest args :)
> 
> Does it look too bad to use [...] at the call sites?

Yes, it looks bad because [ means both sequence and choice.
It took me a long time to decide to do it this way.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:216: class Grammar {
On 2011/10/28 01:21:10, John Messerly wrote:
> In theory, you could get by without this class? It seems like the main thing
it
> does is skip whitespace. (holds onto Symbols, too, but those could easily be
> stored in variables)

In a different implementation the Grammar would be the collection of rules to
allow analysis.
It could also be a useful point for keeping a set of caches that need clearing.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:227: //whitespace = OR([' ', '\t', '\r', '\n']);
On 2011/10/28 01:21:10, John Messerly wrote:
> remove?

Done.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:228: this.whitespace = CHAR(' \t\r\n');
On 2011/10/28 01:21:10, John Messerly wrote:
> shouldn't need "this." anymore now that the bug is fixed

Done.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:235: Symbol operator [](String name) {
On 2011/10/28 01:21:10, John Messerly wrote:
> Could define a setter too that would set the Symbol.def? Hmm, maybe that's too
> strange because the types would be different.

The whole thing with having to define symbols and then define their rule is a
bit clunky.
I'll leave it as is for now.  I know Gilad wants to make the types the same.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:269: for (var rule in state.max_rule)
On 2011/10/28 01:21:10, John Messerly wrote:
> if we got here, isn't state.max_rule empty? should the check above be
!isEmpty?

Good catch.  I was wondering where the informative messages has gone :-)

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:272: tokens.sort((a, b) =>
a.startsWith("'")==b.startsWith("'") ? a.compareTo(b)
On 2011/10/28 01:21:10, John Messerly wrote:
> style nit: long line, spaces etc

Done.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:322: bool in_whitespace_mode = false;
On 2011/10/28 01:21:10, John Messerly wrote:
> style nit: camelCase

Done.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:400: _Rule _compile_optional(rule) {
On 2011/10/28 01:21:10, John Messerly wrote:
> why not put this check in _compile?
> style nit: name should be _compileOptional

It gives the user better errors if null throws at 'compile' time.

Done.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:404: _Rule _compile(rule) {
On 2011/10/28 01:21:10, John Messerly wrote:
> I found the name "compile" a bit confusing here. Not sure what to suggest
> instead though.

Me neither.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:436: throw new ParseError(message);
On 2011/10/28 01:21:10, John Messerly wrote:
> include position?

The position needs to be converted into something pretty.
I think I want to handle that in diagnose.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:447: if (pos == state._end)
On 2011/10/28 01:21:10, John Messerly wrote:
> I wonder if there's a way to do this without checking this condition in every
> rule

I din't think there is.  Every access to the text needs to be guarded somewhere,
explicitly or implicitly.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:504: if (pos + _len > state._end)
On 2011/10/28 01:21:10, John Messerly wrote:
> should be >=, to match a string at the end ?

It is correct.  Normally you check pos < end. But this is pos+len, the last
position of which is pos+len-1 < end  --->  pos+len <= end  so the negative is
pos+len > end.

This is well tested :-).

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:680: if (match == null)
On 2011/10/28 01:21:10, John Messerly wrote:
> I often write this as:
> return (match == null) ? [pos, null] : match;

I'm not a fan of ?:
I prefer if-then-else as an expression.
But it beats adding a bunch of curlies.
I know Google style is vehemently anti-pretty-formatting, but this way the
alternatives line up visually.

http://codereview.chromium.org/8404031/diff/2001/utils/peg/pegparser.dart#new...
utils/peg/pegparser.dart:787: return map[pos];
On 2011/10/28 01:21:10, John Messerly wrote:
> btw: instead of doing two lookups via "map.containsKey(pos)" then "map[pos]"
you
> can just do "map[pos]" and return the result if it's != null.

But null can be stored in the map!