Support for extending native classes

First cut at extending native classes.

Subclasses of native classes have to be treated largely like native classes since they require interceptors.

The ugly part is collecting the set of subclasses of native classes without resolving all classes.  Only plausible classes are resolved.  Plausible classes have a superclass name that is native class (or subclass of native class).  The name-keyed graph is collected and inverted to identify the true subclasses of native classes.

Things that are missing from this CL:

1. I discussed with Peter a better way of finding which classes are subclasses of native classes by resolving the superclass.  Peter's proposal will still require the graph inversion step but should be more precise.

2. It would be a good idea to replace the 'defineNativeSubclass' calls with more declarative static data on the class and post-process the classes.

3. We need to make sure that fields of subclasses of native classes do not conflict with any (potentially undeclared) properties of the base native class.

4. The compiler should do additional checking
   - The constructor must be a factory constructor.
   - No fields can have initializers.

R=ahe@google.com

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

[ahe, 2013-08-12 20:47:35]

I promised to take a closer look tomorrow, but I hope you have time to document
mapTypeToInterceptor first (I've given some concrete suggestions below).

https://chromiumcodereview.appspot.com/15026006/diff/28001/sdk/lib/_internal/...
File sdk/lib/_internal/compiler/implementation/js_backend/backend.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/28001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/backend.dart:203: Element
mapTypeToInterceptor;
Please document this field.

https://chromiumcodereview.appspot.com/15026006/diff/28001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/backend.dart:709: //} else
if (cls.isNative()) {
Remove comment.

https://chromiumcodereview.appspot.com/15026006/diff/28001/sdk/lib/_internal/...
File sdk/lib/_internal/compiler/implementation/js_backend/emitter.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/28001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/emitter.dart:3492: *
[findInterceptorForType].
I'd like more documentation here, could you answer these questions:

* What is the data structure used for?

* What are the components of the data structure?

[sra1, 2013-08-12 23:06:14]

https://chromiumcodereview.appspot.com/15026006/diff/28001/sdk/lib/_internal/...
File sdk/lib/_internal/compiler/implementation/js_backend/backend.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/28001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/backend.dart:203: Element
mapTypeToInterceptor;
On 2013/08/12 20:47:35, ahe wrote:
> Please document this field.

Done.

https://chromiumcodereview.appspot.com/15026006/diff/28001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/backend.dart:709: //} else
if (cls.isNative()) {
On 2013/08/12 20:47:35, ahe wrote:
> Remove comment.

Done.

https://chromiumcodereview.appspot.com/15026006/diff/28001/sdk/lib/_internal/...
File sdk/lib/_internal/compiler/implementation/js_backend/emitter.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/28001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/emitter.dart:3492: *
[findInterceptorForType].
On 2013/08/12 20:47:35, ahe wrote:
> I'd like more documentation here, could you answer these questions:
> 
> * What is the data structure used for?
> 
> * What are the components of the data structure?

This is described where the variable is declared.
I'll add a comment to look there, so there is one comment answering your
questions.

[ahe, 2013-08-13 18:31:47]

Comments so far, I need to read native_helper.dart and the tests.

Nothing blocking, so expect approval later tonight.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
File sdk/lib/_internal/compiler/implementation/js_backend/backend.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/backend.dart:203: /**
Add newline before comment.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/backend.dart:204: * This
element is a top-level variable that the compiler initializes to a
Consider:

... top-level variable (in generated output) that ...

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
File sdk/lib/_internal/compiler/implementation/js_backend/emitter.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/emitter.dart:3224:
assert(!isDeferred(element));
assert(invariant(element, !isDeferred(element));

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/emitter.dart:3505: if
(element is ClassElement) {
element.isClass()

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
File sdk/lib/_internal/compiler/implementation/js_backend/native_emitter.dart
(right):

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/native_emitter.dart:277:
Map<ClassElement, List<ClassElement>> computeExtensionPoints(
Please document what this method does and what an extension point is.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
File sdk/lib/_internal/compiler/implementation/native_handler.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:149: //  class B
extends foo.A {}
This comment is weird.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:172: return
nativeSuperclassOf(classElement.superclass);
How does this cope with cycles in the inheritance graph?

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:177:
//print('Force resolve $element');
Remove comment.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:201: // NEXT: make
subclassed classes use different register function; add in a
We normally use // TODO(username): ...

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:209: SourceString
findExtendsNameOfClass(ClassElement classElement) {
I'm concerned about this method, and I would really appreciate if you would
commit to using the parser to obtain an AST node soonish.

I understand you're under pressure, but code like this has a tendency to cause a
problems real soon. So please consider it a rather high priority to clean this
up :-)

FWIW, it should be relatively easy to use PartialParser to extract this
information.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:224: Token
skipTypeParameters(Token token) {
This should be:

    BeginGroupToken beginGroupToken = token;
    Token endToken = beginGroupToken.endGroup;
    return endToken.next;

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:233: if
(token.stringValue == 'abstract') token = token.next;
You need to use identical, not ==. Otherwise, you do slow string comparison.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:234: if
(token.stringValue != 'class') return null;
Ditto.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:239: if
(token.stringValue == '<') {
Ditto.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:242: if
(token.stringValue != 'extends') return null;
Ditto.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:245: for (;;) {
As a general rule, infinite loops on user data is a recipe for hanging
compilers. Especially in dart2js where EOF.next is EOF.

This is why all 'infinite' loops in the parser look like this:

    while (!identical(token.kind, EOF_TOKEN)) {

In this case, identical is overkill for legacy reasons.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:247: if
(token.stringValue != '.') break;
identical.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
File sdk/lib/_internal/lib/foreign_helper.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/lib/foreign_helper.dart:238: 
Extra line.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
File sdk/lib/_internal/lib/interceptors.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/lib/interceptors.dart:253: * followed by an [Interceptor]
class for the type.
I'm not sure how critical this is for performance, but I think you could easily
use a JS object literal. '$type' is a mangled name that is safe to use as a key
in a JS object.

Note: I'm planning on changing that for mirrors, but I will provide a method to
extract the mangled name from a Type object.

Also note: I'm about to add a class that makes it rather convenient to work with
caches based on JS object literals. Look for JsCache in js_helper.dart.

[sra1, 2013-08-14 04:36:47]

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
File sdk/lib/_internal/compiler/implementation/js_backend/backend.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/backend.dart:203: /**
On 2013/08/13 18:31:47, ahe wrote:
> Add newline before comment.

Done.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/backend.dart:204: * This
element is a top-level variable that the compiler initializes to a
On 2013/08/13 18:31:47, ahe wrote:
> Consider:
> 
> ... top-level variable (in generated output) that ...

Done.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
File sdk/lib/_internal/compiler/implementation/js_backend/emitter.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/emitter.dart:3224:
assert(!isDeferred(element));
On 2013/08/13 18:31:47, ahe wrote:
> assert(invariant(element, !isDeferred(element));

Done.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
File sdk/lib/_internal/compiler/implementation/js_backend/native_emitter.dart
(right):

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/js_backend/native_emitter.dart:277:
Map<ClassElement, List<ClassElement>> computeExtensionPoints(
On 2013/08/13 18:31:47, ahe wrote:
> Please document what this method does and what an extension point is.

Done.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
File sdk/lib/_internal/compiler/implementation/native_handler.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:149: //  class B
extends foo.A {}
On 2013/08/13 18:31:47, ahe wrote:
> This comment is weird.

Done.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:172: return
nativeSuperclassOf(classElement.superclass);
On 2013/08/13 18:31:47, ahe wrote:
> How does this cope with cycles in the inheritance graph?

Called after resolving.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:177:
//print('Force resolve $element');
On 2013/08/13 18:31:47, ahe wrote:
> Remove comment.

Done.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:201: // NEXT: make
subclassed classes use different register function; add in a
On 2013/08/13 18:31:47, ahe wrote:
> We normally use // TODO(username): ...

Removed, since it is done.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:233: if
(token.stringValue == 'abstract') token = token.next;
On 2013/08/13 18:31:47, ahe wrote:
> You need to use identical, not ==. Otherwise, you do slow string comparison.

What guarantees they are the same instance of String?

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:245: for (;;) {
On 2013/08/13 18:31:47, ahe wrote:
> As a general rule, infinite loops on user data is a recipe for hanging
> compilers. Especially in dart2js where EOF.next is EOF.
> 
> This is why all 'infinite' loops in the parser look like this:
> 
>     while (!identical(token.kind, EOF_TOKEN)) {
> 
> In this case, identical is overkill for legacy reasons.

Done.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
File sdk/lib/_internal/lib/foreign_helper.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/lib/foreign_helper.dart:238: 
On 2013/08/13 18:31:47, ahe wrote:
> Extra line.

Done.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
File sdk/lib/_internal/lib/interceptors.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/lib/interceptors.dart:253: * followed by an [Interceptor]
class for the type.
On 2013/08/13 18:31:47, ahe wrote:
> I'm not sure how critical this is for performance, but I think you could
easily
> use a JS object literal. '$type' is a mangled name that is safe to use as a
key
> in a JS object.

It is not critical, at least for now.  For the type to be added to this list,
the type must already be in the constant pool.

> 
> Note: I'm planning on changing that for mirrors, but I will provide a method
to
> extract the mangled name from a Type object.

Unless you can do that for free, it will require metadata which might not
otherwise be required.  This list is the intersection of constant-pool types and
subtypes of native types which would usually be much smaller

> 
> Also note: I'm about to add a class that makes it rather convenient to work
with
> caches based on JS object literals. Look for JsCache in js_helper.dart.

[ahe, 2013-08-14 10:52:47]

Sorry, I lost track of time yesterday tracking down why I had broken the build.

However, I'm realizing now that large parts of this CL makes no sense to me
whatsoever, so I'd like to chat to you about that. Please contact me when you
have time to chat.

What is bothering me is that, as far as I can tell, 'findInterceptorForType' is
only used from tests, and I cannot guess how it would be useful outside a test.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
File sdk/lib/_internal/compiler/implementation/native_handler.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:172: return
nativeSuperclassOf(classElement.superclass);
On 2013/08/14 04:36:47, sra1 wrote:
> On 2013/08/13 18:31:47, ahe wrote:
> > How does this cope with cycles in the inheritance graph?
> 
> Called after resolving.

Sorry, I forgot we had solved this problem.

https://chromiumcodereview.appspot.com/15026006/diff/35001/sdk/lib/_internal/...
sdk/lib/_internal/compiler/implementation/native_handler.dart:233: if
(token.stringValue == 'abstract') token = token.next;
On 2013/08/14 04:36:47, sra1 wrote:
> On 2013/08/13 18:31:47, ahe wrote:
> > You need to use identical, not ==. Otherwise, you do slow string comparison.
> 
> What guarantees they are the same instance of String?

That is guaranteed by the language specification (compile-time constants are
canonicalized) and the string literals passed to the Keyword constructor.

[ahe, 2013-08-14 21:11:21]

lgtm

https://chromiumcodereview.appspot.com/15026006/diff/45001/sdk/lib/_internal/...
File sdk/lib/_internal/lib/native_helper.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/45001/sdk/lib/_internal/...
sdk/lib/_internal/lib/native_helper.dart:268: * Associates tags with an
interceptor.  Called from generated code.  The tags
Please make it clear that this method is called *before* main.

https://chromiumcodereview.appspot.com/15026006/diff/45001/sdk/lib/_internal/...
sdk/lib/_internal/lib/native_helper.dart:272: * subclasses.
It's not really clear what a tag is to me, and why a parameter called 'tags'
(plural) really is a single tag.

It would be great if you could add more details including examples that pulls
everything together (including an HTML document with a custom element). Assume
the reader has no prior knowledge of web components, etc.

https://chromiumcodereview.appspot.com/15026006/diff/45001/sdk/lib/_internal/...
sdk/lib/_internal/lib/native_helper.dart:289: void
defineNativeMethodsCommon(String tags, var interceptorClass, bool isLeaf) {
I don't understand why this method exists. It seems like all of this can be
computed by the emitter and emitted like this:

$.interceptorToTag = [
  class1,
  tag,
  class2,
  tag,
  class3,
  tag1,
  class4,
  tag2
];

$.interceptorsByTag = {
  tag1: $.InterceptorClass1,
  tag2: $.InterceptorClass2,
};

$.leafTags = {
  tag1: true,
  tag2: false,  
};

[sra1, 2013-08-15 19:09:39]

Committed patchset #10 manually as r26208 (presubmit successful).

[sra1, 2013-08-15 19:13:00]

https://chromiumcodereview.appspot.com/15026006/diff/45001/sdk/lib/_internal/...
File sdk/lib/_internal/lib/native_helper.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/45001/sdk/lib/_internal/...
sdk/lib/_internal/lib/native_helper.dart:268: * Associates tags with an
interceptor.  Called from generated code.  The tags
On 2013/08/14 21:11:22, ahe wrote:
> Please make it clear that this method is called *before* main.

Done.

https://chromiumcodereview.appspot.com/15026006/diff/45001/sdk/lib/_internal/...
sdk/lib/_internal/lib/native_helper.dart:289: void
defineNativeMethodsCommon(String tags, var interceptorClass, bool isLeaf) {
On 2013/08/14 21:11:22, ahe wrote:
> I don't understand why this method exists. It seems like all of this can be
> computed by the emitter and emitted like this:
> 
> $.interceptorToTag = [
>   class1,
>   tag,
>   class2,
>   tag,
>   class3,
>   tag1,
>   class4,
>   tag2
> ];
> 
> $.interceptorsByTag = {
>   tag1: $.InterceptorClass1,
>   tag2: $.InterceptorClass2,
> };
> 
> $.leafTags = {
>   tag1: true,
>   tag2: false,  
> };

I generally agree, but done naively like this would add >15k to swarm and even
more to trivial 'hello world' programs.
The code splits strings containing multiple tags and the interceptorClass is not
the run time interceptor (i.e. the .prototype).

With just a map we would replace

// 100 calls to foo
$.foo("tag1|tag2|...|tag50", $.InterceptorClass1)
...

with

// 300 properties here
$.interceptorsByTag = {
  tag1: $.InterceptorClass1.prototype,
  tag2: $.InterceptorClass1.prototype,
  ...
  tag50: $.InterceptorClass1.prototype,
  ...
};


Simply repeating the tags in $.leafTags adds 5k-10k and since they are
interspersed with different data, the compression is merely OK, not great.

The current encoding has the property that very small programs list the HTML and
SVG dispatch tags once, mostly all together in one string.  We could probably
emit a blob of data that can be processed, but it would effectively be the loop
that is 'unrolled' to the 'defineNativeMethods' family of calls.

One thing I have considered is 'registering' regular expressions to compress the
list of HTMLxxxElement names further.  That could not be a map key and would
require a specific test ordering.

One option I have not explored yet is to attach the information to the class or
class-static definition and extract it in finishClasses.

[ahe, 2013-08-15 19:24:01]

https://chromiumcodereview.appspot.com/15026006/diff/45001/sdk/lib/_internal/...
File sdk/lib/_internal/lib/native_helper.dart (right):

https://chromiumcodereview.appspot.com/15026006/diff/45001/sdk/lib/_internal/...
sdk/lib/_internal/lib/native_helper.dart:289: void
defineNativeMethodsCommon(String tags, var interceptorClass, bool isLeaf) {
On 2013/08/15 19:13:00, sra1 wrote:
> On 2013/08/14 21:11:22, ahe wrote:
> > I don't understand why this method exists. It seems like all of this can be
> > computed by the emitter and emitted like this:
> > 
> > $.interceptorToTag = [
> >   class1,
> >   tag,
> >   class2,
> >   tag,
> >   class3,
> >   tag1,
> >   class4,
> >   tag2
> > ];
> > 
> > $.interceptorsByTag = {
> >   tag1: $.InterceptorClass1,
> >   tag2: $.InterceptorClass2,
> > };
> > 
> > $.leafTags = {
> >   tag1: true,
> >   tag2: false,  
> > };
> 
> I generally agree, but done naively like this would add >15k to swarm and even
> more to trivial 'hello world' programs.
> The code splits strings containing multiple tags and the interceptorClass is
not
> the run time interceptor (i.e. the .prototype).
> 
> With just a map we would replace
> 
> // 100 calls to foo
> $.foo("tag1|tag2|...|tag50", $.InterceptorClass1)
> ...
> 
> with
> 
> // 300 properties here
> $.interceptorsByTag = {
>   tag1: $.InterceptorClass1.prototype,
>   tag2: $.InterceptorClass1.prototype,
>   ...
>   tag50: $.InterceptorClass1.prototype,
>   ...
> };
> 
> 
> Simply repeating the tags in $.leafTags adds 5k-10k and since they are
> interspersed with different data, the compression is merely OK, not great.
> 
> The current encoding has the property that very small programs list the HTML
and
> SVG dispatch tags once, mostly all together in one string.  We could probably
> emit a blob of data that can be processed, but it would effectively be the
loop
> that is 'unrolled' to the 'defineNativeMethods' family of calls.
> 
> One thing I have considered is 'registering' regular expressions to compress
the
> list of HTMLxxxElement names further.  That could not be a map key and would
> require a specific test ordering.
> 
> One option I have not explored yet is to attach the information to the class
or
> class-static definition and extract it in finishClasses.
> 

Thank you for the explanation. When I formulated this question, I overlooked the
split on line 294. Had I looked at swarm, this would have been obvious. But I'm
beginning to understand this much better which will be handy later :-)