Add NativeEnqueuer to work with the Enqueuer.

sdk/lib/_internal/compiler/implementation/native_handler.dart

Index: sdk/lib/_internal/compiler/implementation/native_handler.dart
diff --git a/sdk/lib/_internal/compiler/implementation/native_handler.dart b/sdk/lib/_internal/compiler/implementation/native_handler.dart
index db579d390c26495a605b23c06d6d02738e870184..874e8296c0ad9b1ca09ef483e462ccf75f7d1441 100644
--- a/sdk/lib/_internal/compiler/implementation/native_handler.dart
+++ b/sdk/lib/_internal/compiler/implementation/native_handler.dart
@@ -8,70 +8,331 @@ import 'dart:uri';
 import 'dart2jslib.dart' hide SourceString;
 import 'elements/elements.dart';
 import 'js_backend/js_backend.dart';
+import 'resolution/resolution.dart' show ResolverVisitor;
 import 'scanner/scannerlib.dart';
 import 'ssa/ssa.dart';
 import 'tree/tree.dart';
 import 'util/util.dart';
 
-void processNativeClasses(Enqueuer world,
-                          CodeEmitterTask emitter,
-                          Collection<LibraryElement> libraries) {
-  for (LibraryElement library in libraries) {
-    processNativeClassesInLibrary(world, emitter, library);
-  }
+
+/// This class is a temporary work-around until we get a more powerful DartType.
+class SpecialType {
+  final String name;
+  const SpecialType._(this.name);
+
+  /// The type Object, but no subtypes:
+  static const JsObject = const SpecialType._('=Object');
+
+  /// The specific implementation of List that is JavaScript Array:
+  static const JsArray = const SpecialType._('=List');
 }
 
-void addSubtypes(ClassElement cls,
-                 NativeEmitter emitter) {
-  for (DartType type in cls.allSupertypes) {
-    List<Element> subtypes = emitter.subtypes.putIfAbsent(
-        type.element,
-        () => <ClassElement>[]);
-    subtypes.add(cls);
+
+/**
+ * This could be an abstract class but we use it as a stub for the dart_backend.
+ */
+class NativeEnqueuer {
+  /// Initial entry point to native enqueuer.
+  void processNativeClasses(Collection<LibraryElement> libraries) {}
+
+  void registerElement(Element element) {}
+
+  /// Method is a member of a native class.
+  void registerMethod(Element method) {}
+
+  /// Compute types instantiated due to getting a native field.
+  void registerFieldLoad(Element field) {}
+
+  /// Compute types instantiated due to setting a native field.
+  void registerFieldStore(Element field) {}
+
+  /**
+   * Handles JS-calls, which can be an instantiation point for types.
+   *
+   * For example, the following code instantiates and returns native classes
+   * that are `_DOMWindowImpl` or a subtype.
+   *
+   *     JS('_DOMWindowImpl', 'window')
+   *
+   */
+  // TODO(sra): The entry from codegen will not have a resolver.
+  void registerJsCall(Send node, ResolverVisitor resolver) {}
+
+  /// Emits a summary information using the [log] function.
+  void logSummary(log(message)) {}
+}
+
+
+class NativeEnqueuerBase implements NativeEnqueuer {
+
+  /**
+   * The set of all native classes.  Each native class is in [nativeClasses] and
+   * exactly one of [unusedClasses], [pendingClasses] and [registeredClasses].
+   */
+  final Set<ClassElement> nativeClasses = new Set<ClassElement>();
+
+  final Set<ClassElement> registeredClasses = new Set<ClassElement>();
+  final Set<ClassElement> pendingClasses = new Set<ClassElement>();
+  final Set<ClassElement> unusedClasses = new Set<ClassElement>();
+
+  /**
+   * Records matched constraints ([SpecialType] or [DartType]).  Once a type
+   * constraint has been matched, there is no need to match it again.
+   */
+  final Set matchedTypeConstraints = new Set();
+
+  /// Pending actions.  Classes in [pendingClasses] have action thunks in
+  /// [queue] to register the class.
+  final queue = new Queue();
+  bool flushing = false;
+
+
+  final Enqueuer world;
+  final Compiler compiler;
+  final bool enableLiveTypeAnalysis;
+
+  ClassElement _annotationCreatesClass;
+  ClassElement _annotationReturnsClass;
+
+  /// Subclasses of [NativeEnqueuerBase] are constructed by the backend.
+  NativeEnqueuerBase(this.world, this.compiler, this.enableLiveTypeAnalysis);
+
+  void processNativeClasses(Collection<LibraryElement> libraries) {
+    libraries.forEach(processNativeClassesInLibrary);
+    if (!enableLiveTypeAnalysis) {
+      nativeClasses.forEach((c) => enqueueClass(c, 'forced'));
+      flushQueue();
+    }
+  }
+
+  void processNativeClassesInLibrary(LibraryElement library) {
+    // Use implementation to ensure the inclusion of injected members.
+    library.implementation.forEachLocalMember((Element element) {
+      if (element.kind == ElementKind.CLASS) {
+        ClassElement classElement = element;
+        if (classElement.isNative()) {
+          nativeClasses.add(classElement);
+          unusedClasses.add(classElement);
+
+          // Resolve class to ensure the class has valid inheritance info.
+          classElement.ensureResolved(compiler);
+        }
+      }
+    });
+  }
+
+  ClassElement get annotationCreatesClass {
+    if (_annotationCreatesClass == null) findAnnotationClasses();
+    return _annotationCreatesClass;
+  }
+
+  ClassElement get annotationReturnsClass {
+    if (_annotationReturnsClass == null) findAnnotationClasses();
+    return _annotationReturnsClass;
+  }
+
+  void findAnnotationClasses() {
+    ClassElement find(name) {
+      Element e = compiler.findHelper(name);
+      if (e == null || e is! ClassElement) {
+        compiler.cancel("Could not find implementation class '${name}'");
+      }
+      return e;
+    }
+    _annotationCreatesClass = find(const SourceString('Creates'));
+    _annotationReturnsClass = find(const SourceString('Returns'));
+  }
+
+
+  enqueueClass(ClassElement classElement, cause) {
+    assert(unusedClasses.contains(classElement));
+    unusedClasses.remove(classElement);
+    pendingClasses.add(classElement);
+    queue.add(() { processClass(classElement, cause); });
+  }
+
+  void flushQueue() {
+    if (flushing) return;
+    flushing = true;
+    while (!queue.isEmpty) {
+      (queue.removeFirst())();
+    }
+    flushing = false;
+  }
+
+  processClass(ClassElement classElement, cause) {
+    assert(!registeredClasses.contains(classElement));
+
+    bool firstTime = registeredClasses.isEmpty;
+    pendingClasses.remove(classElement);
+    registeredClasses.add(classElement);
+
+    world.registerInstantiatedClass(classElement);
+
+    // Also parse the node to know all its methods because otherwise it will
+    // only be parsed if there is a call to one of its constructors.
+    classElement.parseNode(compiler);
+
+    if (firstTime) {
+      queue.add(onFirstNativeClass);
+    }
+  }
+
+  registerElement(Element element) {
+    if (element.isFunction()) return registerMethod(element);
+  }
+
+  registerMethod(Element method) {
+    if (isNativeMethod(method)) {
+      processNativeBehavior(
+          NativeBehavior.ofMethod(method, compiler),
+          method);
+      flushQueue();
+    }
+  }
+
+  bool isNativeMethod(Element element) {
+    // Native method?
+    Node node = element.parseNode(compiler);
+    if (node is! FunctionExpression) return false;
+    node = node.body;
+    Token token = node.getBeginToken();
+    if (token.stringValue == 'native') return true;
+    return false;
+  }
+
+  void registerFieldLoad(Element field) {
+    processNativeBehavior(
+        NativeBehavior.ofFieldLoad(field, compiler),
+        field);
+    flushQueue();
+  }
+
+  void registerFieldStore(Element field) {
+    processNativeBehavior(
+        NativeBehavior.ofFieldStore(field, compiler),
+        field);
+    flushQueue();
+  }
+
+  void registerJsCall(Send node, ResolverVisitor resolver) {
+    processNativeBehavior(
+        NativeBehavior.ofJsCall(node, compiler, resolver),
+        node);
+    flushQueue();
+  }
+
+  processNativeBehavior(NativeBehavior behavior, cause) {
+    bool allUsedBefore = unusedClasses.isEmpty;
+    for (var type in behavior.typesInstantiated) {

[ahe, 2012/12/04 09:15:19]

When I see code like this, I assume this is equivalent:

Collection<DartType> types = behavior.typesInstantiated;
for (DartType type in types) {
  ...

However, SpecialType does not implement DartType.  So my version would fail.

I think that is problematic because a compiler will always have a natural
concept of "type", and the concept "type" should be reserved for expressing only
that concept.  Otherwise it will cause confusion.  There are a few ways to
accomplish this:

* Use different words to describe concepts that are type-like.  For example,
HType.  However, this is problematic as you then have to convert between
DartTypes and HTypes.  It is also problematic because people will accept
fallacious arguments like:

The JavaScript backend is a separate component from the front-end, and in the
backend, the concept of "type" is clearly HType.  So in the backend, we can call
fields "type", not "htype".

This argument is fallacious because nobody works exclusively on the backend or
the frontend, so everyone will get confused when there isn't agreement about a
core concept such as "type" throughout the compiler.

* Make sure that all types implement DartType.  This is actually easy.

In case you're counting, we now have at least four different kinds of types in
dart2js:

1. HType
2. DartType
3. SpecialType
4. ConcreteType

It would be great if we all could agree to stop this, and also not compound the
situation further.  As far as I can tell, a good first step would be to have
SpecialType and ConcreteType implement DartType.

+      if (matchedTypeConstraints.contains(type)) continue;
+      matchedTypeConstraints.add(type);
+      if (type is SpecialType) {
+        // The two special types (=Object, =List) are always instantiated.
+        continue;
+      }
+      assert(type is DartType);

[ahe, 2012/12/04 09:15:19]

There is a more natural way to express this in Dart:

DartType dartType = type;

That also gives you a considerably better error message than this:

Internal error:
'file:///mnt/data/b/build/slave/dart2js-linux-release-host-checked/build/dart/sdk/lib/_internal/compiler/implementation/native_handler.dart':
Failed assertion: line 312 pos 14: 'type is DartType' is not true.

I assume the problem is that "type" is null.

+      enqueueUnusedClassesMatching(
+          (nativeClass)  => compiler.types.isSubtype(nativeClass.type, type),
+          cause,
+          'subtypeof($type)');
+    }
+
+    // Give an info so that library developers can compile with -v to find why
+    // all the native classes are included.
+    if (unusedClasses.isEmpty && !allUsedBefore) {
+      compiler.log('All native types marked as used due to $cause.');
+    }
+  }
+
+  enqueueUnusedClassesMatching(bool predicate(classElement),
+                               cause,
+                               [String reason]) {
+    Collection matches = unusedClasses.filter(predicate);
+    matches.forEach((c) => enqueueClass(c, cause));
+  }
+
+  onFirstNativeClass() {
+    staticUse(name) => world.registerStaticUse(compiler.findHelper(name));
+
+    staticUse(const SourceString('dynamicFunction'));
+    staticUse(const SourceString('dynamicSetMetadata'));
+    staticUse(const SourceString('defineProperty'));
+    staticUse(const SourceString('toStringForNativeObject'));
+    staticUse(const SourceString('hashCodeForNativeObject'));
+
+    addNativeExceptions();
   }
 
-  List<Element> directSubtypes = emitter.directSubtypes.putIfAbsent(
-      cls.superclass,
-      () => <ClassElement>[]);
-  directSubtypes.add(cls);
+  addNativeExceptions() {
+    enqueueUnusedClassesMatching((classElement) {
+        // TODO(sra): Annotate exception classes in dart:html.
+        String name = classElement.name.slowToString();
+        if (name.contains('Exception')) return true;
+        if (name.contains('Error')) return true;
+        return false;
+      },
+      'native exception');
+  }
+}
+
+
+class NativeResolutionEnqueuer extends NativeEnqueuerBase {
+
+  NativeResolutionEnqueuer(Enqueuer world, Compiler compiler)
+    : super(world, compiler, compiler.enableNativeLiveTypeAnalysis);
+
+  void logSummary(log(message)) {
+    log('Resolved ${registeredClasses.length} native elements used, '
+        '${unusedClasses.length} native elements dead.');
+  }
 }
 
-void processNativeClassesInLibrary(Enqueuer world,
-                                   CodeEmitterTask emitter,
-                                   LibraryElement library) {
-  bool hasNativeClass = false;
-  final compiler = emitter.compiler;
-  // Use implementation to ensure the inclusion of injected members.
-  library.implementation.forEachLocalMember((Element element) {
-    if (element.kind == ElementKind.CLASS) {
-      ClassElement classElement = element;
-      if (classElement.isNative()) {
-        hasNativeClass = true;
-        world.registerInstantiatedClass(classElement);
-        // Also parse the node to know all its methods because
-        // otherwise it will only be parsed if there is a call to
-        // one of its constructor.
-        classElement.parseNode(compiler);
-        // Resolve to setup the inheritance.
-        classElement.ensureResolved(compiler);
-        // Add the information that this class is a subtype of
-        // its supertypes. The code emitter and the ssa builder use that
-        // information.
-        addSubtypes(classElement, emitter.nativeEmitter);
+
+class NativeCodegenEnqueuer extends NativeEnqueuerBase {
+
+  final CodeEmitterTask emitter;
+
+  NativeCodegenEnqueuer(Enqueuer world, Compiler compiler, this.emitter)
+    : super(world, compiler, compiler.enableNativeLiveTypeAnalysis);
+
+  void processNativeClasses(Collection<LibraryElement> libraries) {
+    super.processNativeClasses(libraries);
+
+    // HACK HACK - add all the resolved classes.
+    for (final classElement
+         in compiler.enqueuer.resolution.nativeEnqueuer.registeredClasses) {
+      if (unusedClasses.contains(classElement)) {
+        enqueueClass(classElement, 'was resolved');
       }
     }
-  });
-  if (hasNativeClass) {
-    world.registerStaticUse(compiler.findHelper(
-        const SourceString('dynamicFunction')));
-    world.registerStaticUse(compiler.findHelper(
-        const SourceString('dynamicSetMetadata')));
-    world.registerStaticUse(compiler.findHelper(
-        const SourceString('defineProperty')));
-    world.registerStaticUse(compiler.findHelper(
-        const SourceString('toStringForNativeObject')));
-    world.registerStaticUse(compiler.findHelper(
-        const SourceString('hashCodeForNativeObject')));
+    flushQueue();
+  }
+
+  processClass(ClassElement classElement, cause) {
+    super.processClass(classElement, cause);
+    // Add the information that this class is a subtype of its supertypes.  The
+    // code emitter and the ssa builder use that information.
+    addSubtypes(classElement, emitter.nativeEmitter);
+  }
+
+  void addSubtypes(ClassElement cls, NativeEmitter emitter) {
+    for (DartType type in cls.allSupertypes) {
+      List<Element> subtypes = emitter.subtypes.putIfAbsent(
+          type.element,
+          () => <ClassElement>[]);
+      subtypes.add(cls);
+    }
+
+    List<Element> directSubtypes = emitter.directSubtypes.putIfAbsent(
+        cls.superclass,
+        () => <ClassElement>[]);
+    directSubtypes.add(cls);
+  }
+
+  void logSummary(log(message)) {
+    log('Compiled ${registeredClasses.length} native classes, '
+        '${unusedClasses.length} native classes omitted.');
   }
 }
 
@@ -88,6 +349,246 @@ void maybeEnableNative(Compiler compiler,
   }
 }
 
+/**
+ * A summary of the behavior of a native element.
+ *
+ * Native code can return values of one type and cause native subtypes of
+ * another type to be instantiated.  By default, we compute both from the
+ * declared type.
+ *
+ * A field might yield any native type that 'is' the field type.
+ *
+ * A method might create and return instances of native subclasses of its
+ * declared return type, and a callback argument may be called with instances of
+ * the callback parameter type (e.g. Event).
+ *
+ * If there is one or more @Creates annotations, the union of the named types
+ * replaces the inferred instantiated type, and the return type is ignored for
+ * the purpose of inferring instantiated types.
+ *
+ *     @Creates(IDBCursor)    // Created asynchronously.
+ *     @Creates(IDBRequest)   // Created synchronously (for return value).
+ *     IDBRequest request = objectStore.openCursor();
+ *
+ * If there is one or more @Returns annotations, the union of the named types
+ * replaces the declared return type.
+ *
+ *     @Returns(IDBRequest)
+ *     IDBRequest request = objectStore.openCursor();
+ */
+class NativeBehavior {
+
+  /// [DartType]s or [SpecialType]s returned or yielded by the native element.
+  final Collection typesReturned = [];
+
+  /// [DartType]s or [SpecialType]s instantiated by the native element.
+  final Collection typesInstantiated = [];
+
+  static final NativeBehavior NONE = new NativeBehavior();
+
+  //NativeBehavior();
+
+  static NativeBehavior ofJsCall(Send jsCall, Compiler compiler, resolver) {
+    // The first argument of a JS-call is a string encoding various attributes
+    // of the code.
+    //
+    //  'Type1|Type2'.  A union type.
+    //  '=Object'.      A JavaScript Object, no subtype.
+    //  '=List'.        A JavaScript Array, no subtype.
+
+    var argNodes = jsCall.arguments;
+    if (argNodes.isEmpty) {
+      compiler.cancel("JS expression has no type", node: jsCall);
+    }
+
+    var firstArg = argNodes.head;
+    LiteralString specLiteral = firstArg.asLiteralString();
+    if (specLiteral != null) {
+      String specString = specLiteral.dartString.slowToString();
+      // Various things that are not in fact types.
+      if (specString == 'void') return NativeBehavior.NONE;
+      if (specString == '' || specString == 'var') {
+        var behavior = new NativeBehavior();
+        behavior.typesReturned.add(compiler.objectClass.computeType(compiler));
+        return behavior;
+      }
+      var behavior = new NativeBehavior();
+      for (final typeString in specString.split('|')) {
+        var type = _parseType(typeString, compiler,
+            (name) => resolver.resolveTypeFromString(name),
+            jsCall);
+        behavior.typesInstantiated.add(type);
+        behavior.typesReturned.add(type);
+      }
+      return behavior;
+    }
+
+    // TODO(sra): We could accept a type identifier? e.g. JS(bool, '1<2').  It
+    // is not very satisfactory because it does not work for void, dynamic.
+
+    compiler.cancel("Unexpected JS first argument", node: firstArg);
+  }
+
+  static NativeBehavior ofMethod(Element method, Compiler compiler) {
+    DartType type = method.computeType(compiler);
+    var behavior = new NativeBehavior();
+    behavior.typesReturned.add(type.returnType);
+    behavior._capture(type, compiler);
+
+    // TODO(sra): Optional arguments are currently missing from the
+    // DartType. This should be fixed so the following work-around can be
+    // removed.
+    method.computeSignature(compiler).forEachOptionalParameter(
+        (Element parameter) {
+          behavior._escape(parameter.computeType(compiler), compiler);
+        });
+
+    behavior._overrideWithAnnotations(method, compiler);
+    return behavior;
+  }
+
+  static NativeBehavior ofFieldLoad(Element field, Compiler compiler) {
+    DartType type = field.computeType(compiler);
+    var behavior = new NativeBehavior();
+    behavior.typesReturned.add(type);
+    behavior._capture(type, compiler);
+    behavior._overrideWithAnnotations(field, compiler);
+    return behavior;
+  }
+
+  static NativeBehavior ofFieldStore(Element field, Compiler compiler) {
+    DartType type = field.computeType(compiler);
+    var behavior = new NativeBehavior();
+    behavior._escape(type, compiler);
+    // We don't override the default behaviour - the annotations apply to
+    // loading the field.
+    return behavior;
+  }
+
+  void _overrideWithAnnotations(Element element, Compiler compiler) {
+    if (element.metadata.isEmpty) return;
+
+    DartType lookup(String name) {
+      Element e = element.buildScope().lookup(new SourceString(name));
+      if (e == null) return null;
+      if (e is! ClassElement) return null;
+      e.ensureResolved(compiler);
+      return e.computeType(compiler);
+    }
+
+    var creates =
+        _collect(element, compiler,
+            compiler.enqueuer.resolution.nativeEnqueuer.annotationCreatesClass,
+            lookup);
+    var returns =
+        _collect(element, compiler,
+            compiler.enqueuer.resolution.nativeEnqueuer.annotationReturnsClass,
+            lookup);
+
+    if (creates != null) {
+      typesInstantiated..clear()..addAll(creates);
+    }
+    if (returns != null) {
+      typesReturned..clear()..addAll(returns);
+    }
+  }
+
+  /**
+   * Returns a list of type constraints from the annotations of
+   * [annotationClass].
+   * Returns `null` if no constraints.
+   */
+  static _collect(Element element, Compiler compiler, Element annotationClass,
+                  lookup(str)) {
+    var types = null;
+    for (Link<MetadataAnnotation> link = element.metadata;
+         !link.isEmpty;
+         link = link.tail) {
+      MetadataAnnotation annotation = link.head.ensureResolved(compiler);
+      var value = annotation.value;
+      if (value is! ConstructedConstant) continue;
+      if (value.type is! InterfaceType) continue;
+      if (!identical(value.type.element, annotationClass)) continue;
+
+      var fields = value.fields;
+      // TODO(sra): Better validation of the constant.
+      if (fields.length != 1 || fields[0] is! StringConstant) {
+        compiler.cancel(
+            'Annotations needs one string: ${annotation.parseNode(compiler)}');
+      }
+      String specString = fields[0].toDartString().slowToString();
+      for (final typeString in specString.split('|')) {
+        var type = _parseType(typeString, compiler, lookup, annotation);
+        if (types == null) types = [];
+        types.add(type);
+      }
+    }
+    return types;
+  }
+
+  /// Models the behavior of having intances of [type] escape from Dart code
+  /// into native code.
+  void _escape(DartType type, Compiler compiler) {
+    type = type.unalias(compiler);
+    if (type is FunctionType) {
+      // A function might be called from native code, passing us novel
+      // parameters.
+      _escape(type.returnType, compiler);
+      for (Link<DartType> parameters = type.parameterTypes;
+           !parameters.isEmpty;
+           parameters = parameters.tail) {
+        _capture(parameters.head, compiler);
+      }
+    }
+  }
+
+  /// Models the behavior of Dart code receiving instances and methods of [type]
+  /// from native code.  We usually start the analysis by capturing a native
+  /// method that has been used.
+  void _capture(DartType type, Compiler compiler) {
+    type = type.unalias(compiler);
+    if (type is FunctionType) {
+      _capture(type.returnType, compiler);
+      for (Link<DartType> parameters = type.parameterTypes;
+           !parameters.isEmpty;
+           parameters = parameters.tail) {
+        _escape(parameters.head, compiler);
+      }
+    } else {
+      typesInstantiated.add(type);
+    }
+  }
+
+  static _parseType(String typeString, Compiler compiler,
+      lookup(name), locationNodeOrElement) {
+    if (typeString == '=Object') return SpecialType.JsObject;
+    if (typeString == '=List') return SpecialType.JsArray;
+    if (typeString == 'dynamic') {
+      return  compiler.dynamicClass.computeType(compiler);
+    }
+    DartType type = lookup(typeString);
+    if (type != null) return type;
+
+    int index = typeString.indexOf('<');
+    if (index < 1) {
+      compiler.cancel("Type '$typeString' not found",
+          node: _errorNode(locationNodeOrElement, compiler));
+    }
+    type = lookup(typeString.substring(0, index));
+    if (type != null)  {
+      // TODO(sra): Parse type parameters.
+      return type;
+    }
+    compiler.cancel("Type '$typeString' not found",
+        node: _errorNode(locationNodeOrElement, compiler));
+  }
+
+  static _errorNode(locationNodeOrElement, compiler) {
+    if (locationNodeOrElement is Node) return locationNodeOrElement;
+    return locationNodeOrElement.parseNode(compiler);
+  }
+}
+
 void checkAllowedLibrary(ElementListener listener, Token token) {
   LibraryElement currentLibrary = listener.compilationUnitElement.getLibrary();
   if (!currentLibrary.canUseNative) {