Inserted string validation as separate task in compiler.

Inserted string validation as separate task in compiler.

A LiteralString that has been validated now has a QuotedString
on it that records extra information (string without quotes,
quoting style and string length). Later stages expect that 
QuotedString to be there and the string to be valid.

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

[ahe, 2012-01-25 08:18:52]

Initial comments.

I think this is a great idea, but I'd like this to be incorporated another task.
Preferably, this should happen in the parser listeners.

Here is why: adding a visitor that only looks a leaf nodes is expensive and part
of the reason why dartc is slow. While it feels "right" to separate clearly
distinct operations in separate phases, each new phase has a huge overhead.

Case in point: the normalization phase in dartc. The visitor NormalizerVisitor
does much more than the small legacy normalizers ParenNormalizer,
BlockNormalizer, ForLoopInitNormalizer, and VarNormalizer. However, when you
profile dartc, the legacy normalizers account for almost 4 times as many ticks
as NormalizerVisitor. This translates into almost half a second of the overall
runtime of dartc.

The legacy normalizers have other problems as they are implemented using an
inefficient visitor pattern.

Regardless, the conclusion is sound: if you only need to look at a fraction of
nodes in a graph, the dominant part becomes traversing the graph.

[Lasse Reichstein Nielsen, 2012-01-25 08:31:47]

On 2012/01/25 08:18:52, ahe wrote:
> Initial comments.
> 
> I think this is a great idea, but I'd like this to be incorporated another
task.
> Preferably, this should happen in the parser listeners.

I really, really wanted to do it that way, but wasn't able to find a way to do
it without changing the parser (which I didn't want to do without consulting
you).

The problem is that the listener sees strings before being told that they are
part of a string interpolation. Many strings in a string interpolation won't
have initial quotes, so it won't be able to detect they type of string.
If there was possible for the listener to know whether each string was part of a
string interpolation, and which of the strings are the first and last in an
interpolation, it should be simple to move the validation to the listener.
I.e., let's talk.




> 
> Here is why: adding a visitor that only looks a leaf nodes is expensive and
part
> of the reason why dartc is slow. While it feels "right" to separate clearly
> distinct operations in separate phases, each new phase has a huge overhead.
> 
> Case in point: the normalization phase in dartc. The visitor NormalizerVisitor
> does much more than the small legacy normalizers ParenNormalizer,
> BlockNormalizer, ForLoopInitNormalizer, and VarNormalizer. However, when you
> profile dartc, the legacy normalizers account for almost 4 times as many ticks
> as NormalizerVisitor. This translates into almost half a second of the overall
> runtime of dartc.
> 
> The legacy normalizers have other problems as they are implemented using an
> inefficient visitor pattern.
> 
> Regardless, the conclusion is sound: if you only need to look at a fraction of
> nodes in a graph, the dominant part becomes traversing the graph.

[ahe, 2012-01-25 08:39:44]

More comments.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/leg.dart
File frog/leg/leg.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/leg.dart#newco...
frog/leg/leg.dart:15: #import('util/characters.dart');
I'd like to avoid this import. Could you turn string_validator into a library
instead?

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree/nodes.dart
File frog/leg/tree/nodes.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree/nodes.dar...
frog/leg/tree/nodes.dart:618: const StringQuoting($DQ, false, false);
Is is possible to use named arguments here?

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree/nodes.dar...
frog/leg/tree/nodes.dart:695: QuotedString quotedString = null;
I think this should be final.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree/nodes.dar...
frog/leg/tree/nodes.dart:701: bool isValid() => quotedString !== null;
This method will answer false for valid strings that haven't been validated yet.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree_validator...
File frog/leg/tree_validator.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree_validator...
frog/leg/tree_validator.dart:58: final Node  node;
Please revert this change.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree_validator...
frog/leg/tree_validator.dart:63: String nodeString = new
Unparser(true).unparse(node );
Ditto.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/warnings.dart
File frog/leg/warnings.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/warnings.dart#...
frog/leg/warnings.dart:90: 'Unexpected character or end-of-string in string
escape at index #{1}');
I'm not a big fan of telling the user: I'm not sure what happened, but it was
either this or that. So if you think it is important to distinguish between
"unexpected character" and "end-of-string" (I don't ;-), please make two error
codes. But I'd just write:

"unexpected character in string escape"

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/warnings.dart#...
frog/leg/warnings.dart:90: 'Unexpected character or end-of-string in string
escape at index #{1}');
"Unexpected" should be lowercase to be consistent with other messages (except
the inconsistent ones :-)

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/warnings.dart#...
frog/leg/warnings.dart:90: 'Unexpected character or end-of-string in string
escape at index #{1}');
" at index #{1}" should be removed. Instead this position should be reported by
the diagnostic system.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/warnings.dart#...
frog/leg/warnings.dart:92: 'Line terminator in single-line string at index
#{1}');
Lowercase and remove "at index #{1}".

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/warnings.dart#...
frog/leg/warnings.dart:94: 'Invalid character U+#{2} in string escape at index
#{1}');
Lowercase and remove "at index #{1}".

[karlklose, 2012-01-25 08:47:26]

The functionality LGTM, but I agree with Peter that the validation should happen
during an already existing traversal of the syntax tree or during parsing.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/string_validat...
File frog/leg/string_validator.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/string_validat...
frog/leg/string_validator.dart:71: // String has one quote. Check it if has
three.
one -> at least one

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/string_validat...
frog/leg/string_validator.dart:89: * Returns the number of actual scalar values
in the corresponding Dart
It returns whether the string is valid or not, doesn't it?

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree/nodes.dart
File frog/leg/tree/nodes.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree/nodes.dar...
frog/leg/tree/nodes.dart:618: const StringQuoting($DQ, false, false);
It would be nice to have named arguments here.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree_validator...
File frog/leg/tree_validator.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree_validator...
frog/leg/tree_validator.dart:58: final Node  node;
Remove extra space again.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree_validator...
frog/leg/tree_validator.dart:63: String nodeString = new
Unparser(true).unparse(node );
ditto.

[Lasse Reichstein Nielsen, 2012-01-26 10:14:20]

Please take a new look.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/leg.dart
File frog/leg/leg.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/leg.dart#newco...
frog/leg/leg.dart:15: #import('util/characters.dart');
On 2012/01/25 08:39:44, ahe wrote:
> I'd like to avoid this import. Could you turn string_validator into a library
> instead?

Done.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/string_validat...
File frog/leg/string_validator.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/string_validat...
frog/leg/string_validator.dart:71: // String has one quote. Check it if has
three.
On 2012/01/25 08:47:26, karlklose wrote:
> one -> at least one

Done.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/string_validat...
frog/leg/string_validator.dart:89: * Returns the number of actual scalar values
in the corresponding Dart
True. Old comment is old.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree/nodes.dart
File frog/leg/tree/nodes.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree/nodes.dar...
frog/leg/tree/nodes.dart:618: const StringQuoting($DQ, false, false);
On 2012/01/25 08:47:26, karlklose wrote:
> It would be nice to have named arguments here.

Done.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree/nodes.dar...
frog/leg/tree/nodes.dart:695: QuotedString quotedString = null;
It is now that we find the value during parsing.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree/nodes.dar...
frog/leg/tree/nodes.dart:701: bool isValid() => quotedString !== null;
Yes.
Renaming to isValidated().

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree_validator...
File frog/leg/tree_validator.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree_validator...
frog/leg/tree_validator.dart:58: final Node  node;
On 2012/01/25 08:47:26, karlklose wrote:
> Remove extra space again.

Done.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/tree_validator...
frog/leg/tree_validator.dart:63: String nodeString = new
Unparser(true).unparse(node );
On 2012/01/25 08:47:26, karlklose wrote:
> ditto.

Done.

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/warnings.dart
File frog/leg/warnings.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/1/frog/leg/warnings.dart#...
frog/leg/warnings.dart:90: 'Unexpected character or end-of-string in string
escape at index #{1}');
I'm removing all of these, since I'm not using them any more.

[Lasse Reichstein Nielsen, 2012-01-26 12:06:31]

Changed based on offline discussions.

https://chromiumcodereview.appspot.com/9271037/diff/1014/frog/leg/scanner/lis...
File frog/leg/scanner/listener.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/1014/frog/leg/scanner/lis...
frog/leg/scanner/listener.dart:480: }
Abstracted this block into popLiteralString.
Changed canceler.cancel to recoverableError.

https://chromiumcodereview.appspot.com/9271037/diff/1014/frog/leg/scanner/par...
File frog/leg/scanner/parser.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/1014/frog/leg/scanner/par...
frog/leg/scanner/parser.dart:25: token = parseLibraryTags(token);
changed LibraryTags to ScriptTags here and in listener.

[ahe, 2012-01-26 19:24:27]

LGTM!

Very nice.

Cheers,
Peter

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/scanner/lis...
File frog/leg/scanner/listener.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/scanner/lis...
frog/leg/scanner/listener.dart:155: void beginScriptTag(Token token) {
I'd like to keep the groups of begin/end sorted.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/scanner/lis...
frog/leg/scanner/listener.dart:461: final List<StringQuoting>
interpolationScope;
Please use Link.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/scanner/lis...
frog/leg/scanner/listener.dart:712: bool isLast = true;
This confused the heck out of me. A comment to remind the reader that the nodes
are pop'ed in reverse order could be helpful :-)

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/scanner/lis...
frog/leg/scanner/listener.dart:719: string = new LiteralString(string.token,
validation);
Perhaps add a comment that you're replacing the node here.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
File frog/leg/ssa/codegen.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
frog/leg/ssa/codegen.dart:502: Iterator<int> iter = string.iterator();
Do you think performance would suffer if this was named "iterator" :-)

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
frog/leg/ssa/codegen.dart:511: // Newlines in strings only occour in multiline
strings.
occour -> occur

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
frog/leg/ssa/codegen.dart:512: // They need to be written using escapes in JS..
Extra .

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
frog/leg/ssa/codegen.dart:528: } else {
For documentation, how about adding:

assert(code === $BACKSLASH);

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
File frog/leg/string_validator.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
frog/leg/string_validator.dart:150: if (0xd800 <= value && ( value <= 0xdfff ||
value > 0x10ffff)) {
Consider naming these in characters.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
frog/leg/string_validator.dart:159: // This handles borth unescaped characters
as well as those
borth -> both

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
frog/leg/string_validator.dart:162: if (code >= 0xd800 && (code <= 0xdfff ||
code > 0x10ffff)) {
Utility method?

[karlklose, 2012-01-27 09:11:59]

LGTM.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/compiler.dart
File frog/leg/compiler.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/compiler.da...
frog/leg/compiler.dart:80: optimizer, generator, emitter,
compileTimeConstantHandler];
This could go back to the previous line.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/scanner/lis...
File frog/leg/scanner/listener.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/scanner/lis...
frog/leg/scanner/listener.dart:744: : super(canceler, null);
This can go back to the previous line again.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
File frog/leg/ssa/codegen.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
frog/leg/ssa/codegen.dart:557: // Character escapes that identical in meaning in
JS.
that *are* identical

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
File frog/leg/string_validator.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
frog/leg/string_validator.dart:5: // Checks a tree structure for whether the
string literals are valid.
Update comment.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
frog/leg/string_validator.dart:136: // Expect four hex digits, including the one
just tread.
tread -> read?

[Lasse Reichstein Nielsen, 2012-01-27 11:39:04]

Good comments!

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/compiler.dart
File frog/leg/compiler.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/compiler.da...
frog/leg/compiler.dart:80: optimizer, generator, emitter,
compileTimeConstantHandler];
On 2012/01/27 09:11:59, karlklose wrote:
> This could go back to the previous line.

Done.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/scanner/lis...
File frog/leg/scanner/listener.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/scanner/lis...
frog/leg/scanner/listener.dart:155: void beginScriptTag(Token token) {
On 2012/01/26 19:24:28, ahe wrote:
> I'd like to keep the groups of begin/end sorted.

Done.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/scanner/lis...
frog/leg/scanner/listener.dart:712: bool isLast = true;
On 2012/01/26 19:24:28, ahe wrote:
> This confused the heck out of me. A comment to remind the reader that the
nodes
> are pop'ed in reverse order could be helpful :-)

Done.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/scanner/lis...
frog/leg/scanner/listener.dart:719: string = new LiteralString(string.token,
validation);
On 2012/01/26 19:24:28, ahe wrote:
> Perhaps add a comment that you're replacing the node here.

Done.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/scanner/lis...
frog/leg/scanner/listener.dart:744: : super(canceler, null);
On 2012/01/27 09:11:59, karlklose wrote:
> This can go back to the previous line again.

Done.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
File frog/leg/ssa/codegen.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
frog/leg/ssa/codegen.dart:502: Iterator<int> iter = string.iterator();
Absoleffinglutely. But I'll rename it anyway, just out of spite!

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
frog/leg/ssa/codegen.dart:511: // Newlines in strings only occour in multiline
strings.
On 2012/01/26 19:24:28, ahe wrote:
> occour -> occur

Done.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
frog/leg/ssa/codegen.dart:512: // They need to be written using escapes in JS..
On 2012/01/26 19:24:28, ahe wrote:
> Extra .

Done.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
frog/leg/ssa/codegen.dart:528: } else {
On 2012/01/26 19:24:28, ahe wrote:
> For documentation, how about adding:
> 
> assert(code === $BACKSLASH); 

Done.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
frog/leg/ssa/codegen.dart:557: // Character escapes that identical in meaning in
JS.
Good catch.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
File frog/leg/string_validator.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
frog/leg/string_validator.dart:5: // Checks a tree structure for whether the
string literals are valid.
On 2012/01/27 09:11:59, karlklose wrote:
> Update comment.

Done.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
frog/leg/string_validator.dart:115: // expect 1-7 hex digits.
Changing this to 1-6 in anticipation of spec v0.8.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
frog/leg/string_validator.dart:136: // Expect four hex digits, including the one
just tread.
On 2012/01/27 09:11:59, karlklose wrote:
> tread -> read?

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
frog/leg/string_validator.dart:150: if (0xd800 <= value && ( value <= 0xdfff ||
value > 0x10ffff)) {
On 2012/01/26 19:24:28, ahe wrote:
> Consider naming these in characters.

Done.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
frog/leg/string_validator.dart:159: // This handles borth unescaped characters
as well as those
On 2012/01/26 19:24:28, ahe wrote:
> borth -> both

Done.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
frog/leg/string_validator.dart:162: if (code >= 0xd800 && (code <= 0xdfff ||
code > 0x10ffff)) {
On 2012/01/26 19:24:28, ahe wrote:
> Utility method?

Done.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/string_vali...
frog/leg/string_validator.dart:168: if (!quoting.multiline && (code === $LF ||
code === $CR)) {
I'm removing this since the scanner already detects invalid line terminators.
Also allows me to merge the unicode scalar value checks.

[ahe, 2012-01-27 12:12:36]

Still LGTM :-)

A few nits.

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
File frog/leg/ssa/codegen.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/2002/frog/leg/ssa/codegen...
frog/leg/ssa/codegen.dart:557: // Character escapes that identical in meaning in
JS.
On 2012/01/27 11:39:04, Lasse Reichstein Nielsen wrote:
> Good catch.

You forgot to change it :-)

https://chromiumcodereview.appspot.com/9271037/diff/11001/frog/leg/scanner/li...
File frog/leg/scanner/listener.dart (right):

https://chromiumcodereview.appspot.com/9271037/diff/11001/frog/leg/scanner/li...
frog/leg/scanner/listener.dart:469: interpolationScope = const
EmptyLink<StringQuoting>();
FYI, you can initialize this in the field declaration.

https://chromiumcodereview.appspot.com/9271037/diff/11001/frog/leg/scanner/li...
frog/leg/scanner/listener.dart:722: // Parts of the string interpolation are
popped in reverse order,
Since all parts of the string interpolation is popped, not some of the parts, it
would be clearer if you change

"Parts of the string interpolation" to "String-interpolation parts"