sort classes in dependency order, or load lazily if needed, fixes #78

lib/src/codegen/js_codegen.dart

 // Copyright (c) 2015, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 library dev_compiler.src.codegen.js_codegen;
 
-import 'dart:collection' show HashSet;
+import 'dart:collection' show HashSet, HashMap;
 import 'dart:io' show Directory, File;
 
 import 'package:analyzer/analyzer.dart' hide ConstantEvaluator;
 import 'package:analyzer/src/generated/ast.dart' hide ConstantEvaluator;
 import 'package:analyzer/src/generated/constant.dart';
 import 'package:analyzer/src/generated/element.dart';
 import 'package:analyzer/src/generated/scanner.dart'
     show StringToken, Token, TokenType;
 import 'package:source_maps/source_maps.dart' as srcmaps show Printer;
 import 'package:source_maps/source_maps.dart' show SourceMapSpan;
@@ skipping 42 matching lines @@
 
   ClassDeclaration currentClass;
   ConstantEvaluator _constEvaluator;
 
   final _exports = <String>[];
   final _lazyFields = <VariableDeclaration>[];
   final _properties = <FunctionDeclaration>[];
   final _privateNames = new HashSet<String>();
   final _pendingPrivateNames = <String>[];
 
+  /// Classes we have not emitted yet. Values can be [ClassDeclaration] or
+  /// [ClassTypeAlias].
+  final _pendingClasses = new HashMap<ClassElement, CompilationUnitMember>();
+
+  /// Memoized results of [_lazyClass].
+  final _lazyClassMemo = new HashMap<ClassElement, bool>();
+
+  /// Memoized results of [_inLibraryCycle].
+  final _libraryCycleMemo = new HashMap<LibraryElement, bool>();
+
   JSCodegenVisitor(this.libraryInfo, this.rules, this._checkerReporter);
 
-  Element get currentLibrary => libraryInfo.library;
+  LibraryElement get currentLibrary => libraryInfo.library;
 
   JS.Program emitLibrary(LibraryUnit library) {
     var jsDefaultValue = '{}';
     var unit = library.library;
     if (unit.directives.isNotEmpty) {
       var annotation = _getJsNameAnnotation(unit.directives.first);
       if (annotation != null) {
         var arguments = annotation.arguments.arguments;
         if (!arguments.isEmpty) {
           var namedExpression = arguments.first as NamedExpression;
           var literal = namedExpression.expression as SimpleStringLiteral;
           jsDefaultValue = literal.stringValue;
         }
       }
     }
     var body = <JS.Statement>[];
 
-    // Visit parts first, since the "part" declarations come before code
-    // in the main library's compilation unit.
-    for (var unit in library.parts) {
-      body.add(_visit(unit));
+    // Collect classes we need to emit, used for:
+    // * tracks what we've emitted so we don't emit twice
+    // * provides a mapping from ClassElement back to the ClassDeclaration.
+    for (var unit in library.partsThenLibrary) {
+      for (var decl in unit.declarations) {
+        if (decl is ClassDeclaration || decl is ClassTypeAlias) {
+          _pendingClasses[decl.element] = decl;
+        }
+      }
     }
 
-    // Visit main library
-    body.add(_visit(library.library));
+    for (var unit in library.partsThenLibrary) body.add(_visit(unit));
+
+    assert(_pendingClasses.isEmpty);
 
     if (_exports.isNotEmpty) body.add(js.comment('Exports:'));
 
     // TODO(jmesserly): make these immutable in JS?
     for (var name in _exports) {
       body.add(js.statement('$_EXPORTS.# = #;', [name, name]));
     }
 
     var name = jsLibraryName(libraryInfo.library);
 
@@ skipping 109 matching lines @@
   visitFunctionTypeAlias(FunctionTypeAlias node) {
     // TODO(vsm): Do we need to record type info the generated code for a
     // typedef?
   }
 
   @override
   JS.Expression visitTypeName(TypeName node) => _emitTypeName(node.type);
 
   @override
   JS.Statement visitClassTypeAlias(ClassTypeAlias node) {
+    // If we've already emitted this class, skip it.
+    var classElem = node.element;
+    if (_pendingClasses.remove(classElem) == null) return null;
+
     var name = node.name.name;
     var heritage =
         js.call('dart.mixin(#)', [_visitList(node.withClause.mixinTypes)]);
     var classDecl = new JS.ClassDeclaration(
         new JS.ClassExpression(new JS.VariableDeclaration(name), heritage, []));
     if (isPublic(name)) _exports.add(name);
-    return _addTypeParameters(node.typeParameters, name, classDecl);
-  }
 
-  @override
-  visitTypeParameter(TypeParameter node) => new JS.Parameter(node.name.name);
-
-  JS.Statement _addTypeParameters(
-      TypeParameterList node, String name, JS.Statement clazz) {
-    if (node == null) return clazz;
-
-    var genericName = '$name\$';
-    var genericDef = js.statement(
-        'let # = dart.generic(function(#) { #; return #; });', [
-      genericName,
-      _visitList(node.typeParameters),
-      clazz,
-      name
-    ]);
-
-    // TODO(jmesserly): we may not want this to be `dynamic` if the generic
-    // has a lower bound, e.g. `<T extends SomeType>`.
-    // https://github.com/dart-lang/dart-dev-compiler/issues/38
-    var typeArgs =
-        new List.filled(node.typeParameters.length, js.call('dart.dynamic'));
-
-    var dynInst = js.statement('let # = #(#);', [name, genericName, typeArgs]);
-
-    // TODO(jmesserly): is it worth exporting both names? Alternatively we could
-    // put the generic type constructor on the <dynamic> instance.
-    if (isPublic(name)) _exports.add('${name}\$');
-    return new JS.Block([genericDef, dynInst]);
+    return _finishClassDef(classElem, classDecl);
   }
 
   @override
   JS.Statement visitClassDeclaration(ClassDeclaration node) {
+    // If we've already emitted this class, skip it.
+    var classElem = node.element;
+    if (_pendingClasses.remove(classElem) == null) return null;
     if (_getJsNameAnnotation(node) != null) return null;
 
     currentClass = node;
 
-    // dart:core Object is a bit special.
-    var isObject = node.element.type.isObject;
+    var name = classElem.name;
+    if (isPublic(name)) _exports.add(name);
 
-    var body = <JS.Statement>[];
-
-    var name = node.name.name;
     var ctors = <ConstructorDeclaration>[];
     var fields = <FieldDeclaration>[];
     var staticFields = <FieldDeclaration>[];
     for (var member in node.members) {
       if (member is ConstructorDeclaration) {
         ctors.add(member);
       } else if (member is FieldDeclaration) {
         (member.isStatic ? staticFields : fields).add(member);
       }
     }
 
+    var classExpr = new JS.ClassExpression(new JS.VariableDeclaration(name),
+        _classHeritage(node), _emitClassMethods(node, ctors, fields));
+
+    var body = _finishClassMembers(name, classExpr, ctors, staticFields);
+    currentClass = null;
+
+    return _finishClassDef(classElem, body);
+  }
+
+  /// Given a class element and body, complete the class declaration.
+  /// This handles generic type parameters, laziness (in library-cycle cases),
+  /// and ensuring dependencies are loaded first.
+  JS.Statement _finishClassDef(ClassElement classElem, JS.Statement body) {
+    var name = classElem.name;
+    var genericName = '$name\$';
+
+    JS.Statement genericDef;
+    JS.Expression genericInst;
+    if (classElem.typeParameters.isNotEmpty) {
+      genericDef = _emitGenericClassDef(classElem, body);
+      var dynamicArgs = new List.filled(
+          classElem.typeParameters.length, js.call('dart.dynamic'));
+
+      var target = genericName;
+      if (_needQualifiedName(classElem)) {
+        target = js.call('#.#', [_EXPORTS, genericName]);
+      }
+      genericInst = js.call('#(#)', [target, dynamicArgs]);
+    }
+
+    // The base class and all mixins must be declared before this class.
+    if (_lazyClass(classElem)) {
+      // TODO(jmesserly): the lazy class def is a simple solution for now.
+      // We may want to consider other options in the future.
+
+      if (genericDef != null) {
+        return js.statement(
+            '{ #; dart.defineLazyClassGeneric(#, #, { get: # }); }', [
+          genericDef,
+          _EXPORTS,
+          js.string(name, "'"),
+          genericName
+        ]);
+      }
+
+      return js.statement(
+          'dart.defineLazyClass(#, { get #() { #; return #; } });', [
+        _EXPORTS,
+        name,
+        body,
+        name
+      ]);
+    }
+
+    if (genericDef != null) {
+      body = js.statement('{ #; let # = #; }', [genericDef, name, genericInst]);
+    }
+
+    if (classElem.type.isObject) return body;
+
+    // If we're not lazy, we still need to ensure our dependencies are
+    // generated first.
+    var classDefs = <JS.Statement>[];
+    _emitClassIfNeeded(classDefs, classElem.supertype.element);
+    for (var m in classElem.mixins) {
+      _emitClassIfNeeded(classDefs, m.element);
+    }
+    classDefs.add(body);
+    return _statement(classDefs);
+  }
+
+  void _emitClassIfNeeded(List<JS.Statement> defs, ClassElement base) {
+    // We can only emit classes from this library.
+    if (base.library != currentLibrary) return;
+
+    var baseNode = _pendingClasses[base];
+    if (baseNode != null) defs.add(visitClassDeclaration(baseNode));
+  }
+
+  /// Returns true if the supertype or mixins aren't loaded.
+  /// If that is the case, we'll emit a lazy class definition.
+  bool _lazyClass(ClassElement cls) {
+    if (cls.type.isObject) return false;
+
+    assert(cls.library == currentLibrary);
+    var result = _lazyClassMemo[cls];
+    if (result != null) return result;
+
+    result = _classMightNotBeLoaded(cls.supertype.element);
+    for (var mixin in cls.mixins) {
+      if (result) break;
+      result = _classMightNotBeLoaded(mixin.element);
+    }
+    return _lazyClassMemo[cls] = result;
+  }
+
+  /// Curated order to minimize lazy classes needed by dart:core and its
+  /// transitive SDK imports.
+  static const CORELIB_ORDER = const [
+    'dart.core',
+    'dart.collection',
+    'dart._internal'
+  ];
+
+  /// Returns true if the class might not be loaded.
+  ///
+  /// If the class is from our library, this can happen because it's lazy.
+  ///
+  /// If the class is from a different library, it could happen if we're in
+  /// a library cycle. In other words, if that different library depends back
+  /// on this library via some transitive import path.
+  ///
+  /// If we could control the global import ordering, we could eliminate some
+  /// of these cases, by ordering the imports of the cyclic libraries in an
+  /// optimal way. For example, we could order the libraries in a cycle to
+  /// minimize laziness. However, we currently assume we cannot control the
+  /// order that the cycle of libraries will be loaded in.
+  bool _classMightNotBeLoaded(ClassElement cls) {
+    if (cls.library == currentLibrary) return _lazyClass(cls);
+
+    // The SDK is a special case: we optimize the order to prevent laziness.
+    if (cls.library.isInSdk) {
+      // SDK is loaded before non-SDK libraies
+      if (!currentLibrary.isInSdk) return false;
+
+      // Compute the order of both SDK libraries. If unknown, assume it's after.
+      var classOrder = CORELIB_ORDER.indexOf(cls.library.name);
+      if (classOrder == -1) classOrder = CORELIB_ORDER.length;
+
+      var currentOrder = CORELIB_ORDER.indexOf(currentLibrary.name);
+      if (currentOrder == -1) currentOrder = CORELIB_ORDER.length;
+
+      // If the dart:* library we are currently compiling is loaded after the
+      // class's library, then we know the class is available.
+      if (classOrder != currentOrder) return currentOrder < classOrder;
+
+      // If we don't know the order of the class's library or the current
+      // library, do the normal cycle check. (Not all SDK libs are cycles.)
+    }
+
+    return _inLibraryCycle(cls.library);
+  }
+
+  /// Returns true if [library] depends on the [currentLibrary] via some
+  /// transitive import.
+  bool _inLibraryCycle(LibraryElement library) {
+    // SDK libs don't depend on things outside the SDK.
+    // (We can reach this via the recursive call below.)
+    if (library.isInSdk && !currentLibrary.isInSdk) return false;
+
+    var result = _libraryCycleMemo[library];
+    if (result != null) return result;
+
+    result = library == currentLibrary;
+    _libraryCycleMemo[library] = result;
+    for (var e in library.imports) {
+      if (result) break;
+      result = _inLibraryCycle(e.importedLibrary);
+    }
+    for (var e in library.exports) {
+      if (result) break;
+      result = _inLibraryCycle(e.exportedLibrary);
+    }
+    return _libraryCycleMemo[library] = result;
+  }
+
+  JS.Statement _emitGenericClassDef(ClassElement cls, JS.Statement body) {
+    var name = cls.name;
+    var genericName = '$name\$';
+    var typeParams = cls.typeParameters.map((p) => new JS.Parameter(p.name));
+    // TODO(jmesserly): is it worth exporting both names? Alternatively we could
+    // put the generic type constructor on the <dynamic> instance.
+    if (isPublic(name)) _exports.add(genericName);
+    return js.statement('let # = dart.generic(function(#) { #; return #; });', [
+      genericName,
+      typeParams,
+      body,
+      name
+    ]);
+  }
+
+  JS.Expression _classHeritage(ClassDeclaration node) {
+    if (node.element.type.isObject) return null;
+
+    JS.Expression heritage = null;
+    if (node.extendsClause != null) {
+      heritage = _visit(node.extendsClause.superclass);
+    } else {
+      heritage = _emitTypeName(rules.provider.objectType);
+    }
+    if (node.withClause != null) {
+      var mixins = _visitList(node.withClause.mixinTypes);
+      mixins.insert(0, heritage);
+      heritage = js.call('dart.mixin(#)', [mixins]);
+    }
+    return heritage;
+  }
+
+  /// Emit class members that can be generated as methods.
+  /// Anything not handled here will be addressed in [_finishClassMembers].
+  List<JS.Method> _emitClassMethods(ClassDeclaration node,
+      List<ConstructorDeclaration> ctors, List<FieldDeclaration> fields) {
+    var element = node.element;
+    var isObject = element.type.isObject;
+    var name = node.name.name;
+
     var jsMethods = <JS.Method>[];
     // Iff no constructor is specified for a class C, it implicitly has a
     // default constructor `C() : super() {}`, unless C is class Object.
     if (ctors.isEmpty && !isObject) {
       jsMethods.add(_emitImplicitConstructor(node, name, fields));
     }
 
     for (var member in node.members) {
       if (member is ConstructorDeclaration) {
         jsMethods.add(_emitConstructor(member, name, fields, isObject));
       } else if (member is MethodDeclaration) {
         jsMethods.add(_visit(member));
       }
     }
 
     // Support for adapting dart:core Iterator/Iterable to ES6 versions.
     // This lets them use for-of loops transparently.
     // https://github.com/lukehoban/es6features#iterators--forof
-    if (node.element.library.isDartCore && node.element.name == 'Iterable') {
+    if (element.library.isDartCore && element.name == 'Iterable') {
       JS.Fun body = js.call('''function() {
         var iterator = this.iterator;
         return {
           next() {
             var done = iterator.moveNext();
             return { done: done, current: done ? void 0 : iterator.current };
           }
         };
       }''');
       jsMethods.add(new JS.Method(js.call('Symbol.iterator'), body));
     }
+    return jsMethods.where((m) => m != null).toList(growable: false);
+  }
 
-    JS.Expression heritage = null;
-    if (node.extendsClause != null) {
-      heritage = _visit(node.extendsClause.superclass);
-    } else if (!isObject) {
-      heritage = _emitTypeName(rules.provider.objectType);
-    }
-    if (node.withClause != null) {
-      var mixins = _visitList(node.withClause.mixinTypes);
-      mixins.insert(0, heritage);
-      heritage = js.call('dart.mixin(#)', [mixins]);
-    }
-    body.add(new JS.ClassDeclaration(new JS.ClassExpression(
-        new JS.VariableDeclaration(name), heritage,
-        jsMethods.where((m) => m != null).toList(growable: false))));
-
-    if (isPublic(name)) _exports.add(name);
+  /// Emit class members that need to come after the class declaration, such
+  /// as static fields. See [_emitClassMethods] for things that are emitted
+  /// insite the ES6 `class { ... }` node.
+  JS.Statement _finishClassMembers(String name, JS.ClassExpression cls,
+      List<ConstructorDeclaration> ctors, List<FieldDeclaration> staticFields) {
+    var body = <JS.Statement>[];
+    body.add(new JS.ClassDeclaration(cls));
 
     // Named constructors
     for (ConstructorDeclaration member in ctors) {
       if (member.name != null) {
         body.add(js.statement('dart.defineNamedConstructor(#, #);', [
           name,
           js.string(member.name.name, "'")
         ]));
       }
     }
 
     // Static fields
     var lazyStatics = <VariableDeclaration>[];
     for (FieldDeclaration member in staticFields) {
       for (VariableDeclaration field in member.fields.variables) {
         var fieldName = field.name.name;
         if (field.isConst || _isFieldInitConstant(field)) {
           var init = _visit(field.initializer);
           if (init == null) init = new JS.LiteralNull();
           body.add(js.statement('#.# = #;', [name, fieldName, init]));
         } else {
           lazyStatics.add(field);
         }
       }
     }
     var lazy = _emitLazyFields(name, lazyStatics);
     if (lazy != null) body.add(lazy);
-
-    currentClass = null;
-    return _addTypeParameters(node.typeParameters, name, _statement(body));
+    return _statement(body);
   }
 
   /// Generates the implicit default constructor for class C of the form
   /// `C() : super() {}`.
   JS.Method _emitImplicitConstructor(
       ClassDeclaration node, String name, List<FieldDeclaration> fields) {
     // If we don't have a method body, skip this.
     if (fields.isEmpty) return null;
 
     dynamic body = _initializeFields(fields);
@@ skipping 359 matching lines @@
       var className = (variable.enclosingElement as ClassElement).name;
       return js.call('#.#', [className, name]);
     } else if (e is ParameterElement && e.isInitializingFormal) {
       name = _fieldParameterName(name);
     }
     return new JS.VariableUse(name);
   }
 
   JS.Expression _emitTypeName(DartType type) {
     var name = type.name;
-    var lib = type.element.library;
+    var element = type.element;
     if (name == '') {
       // TODO(jmesserly): remove when we're using coercion reifier.
       return _unimplementedCall('Unimplemented type $type');
     }
 
     var typeArgs = null;
     if (type is ParameterizedType) {
       // TODO(jmesserly): this is a workaround for an analyzer bug, see:
-      // https://github.com/dart-lang/dart-dev-compiler/commit/a212d59ad046085a626dd8d16881cdb8e8b9c3fa
-      if (type is! FunctionType || type.element is FunctionTypeAlias) {
+      // https://github.com/dart-lang/dev_compiler/commit/a212d59ad046085a626dd8d16881cdb8e8b9c3fa
+      if (type is! FunctionType || element is FunctionTypeAlias) {
         var args = type.typeArguments;
         if (args.any((a) => a != rules.provider.dynamicType)) {
           name = '$name\$';
           typeArgs = args.map(_emitTypeName);
         }
       }
     }
 
     JS.Expression result;
-    if (lib != currentLibrary && lib != null) {
-      result = js.call('#.#', [_libraryName(lib), name]);
+    if (_needQualifiedName(element)) {
+      result = js.call('#.#', [_libraryName(element.library), name]);
     } else {
       result = new JS.VariableUse(name);
     }
 
     if (typeArgs != null) {
       result = js.call('#(#)', [result, typeArgs]);
     }
     return result;
   }
 
+  bool _needQualifiedName(Element element) {
+    var lib = element.library;
+
+    return lib != null &&
+        (lib != currentLibrary ||
+            element is ClassElement && _lazyClass(element));
+  }
+
   JS.Node _emitDPutIfDynamic(
       Expression target, SimpleIdentifier id, Expression rhs) {
     if (rules.isDynamicTarget(target)) {
       return js.call('dart.dput(#, #, #)', [
         _visit(target),
         js.string(id.name, "'"),
         _visit(rhs)
       ]);
     } else {
       return null;
@@ skipping 291 matching lines @@
 
       // TODO(jmesserly): use a dummy setter to indicate writable.
       if (!node.isFinal) {
         methods.add(new JS.Method(
             new JS.PropertyName(name), js.call('function(_) {}'),
             isSetter: true));
       }
     }
 
     return js.statement(
-        'dart.defineLazyProperties(#, { # })', [objExpr, methods]);
+        'dart.defineLazyProperties(#, { # });', [objExpr, methods]);
   }
 
   void _flushLibraryProperties(List<JS.Statement> body) {
     if (_properties.isEmpty) return;
     body.add(js.statement('dart.copyProperties($_EXPORTS, { # });',
         [_properties.map(_emitTopLevelProperty)]));
     _properties.clear();
   }
 
   @override
@@ skipping 996 matching lines @@
 
     // TODO(jmesserly): in many cases marking the end will be unncessary.
     printer.mark(_location(node.end));
   }
 
   String _getIdentifier(AstNode node) {
     if (node is SimpleIdentifier) return node.name;
     return null;
   }
 }