Name and hoist types

lib/src/compiler/type_utilities.dart

Index: lib/src/compiler/type_utilities.dart
diff --git a/lib/src/compiler/type_utilities.dart b/lib/src/compiler/type_utilities.dart
new file mode 100644
index 0000000000000000000000000000000000000000..0614029713dd2091e1e045730f5d863a64630c12
--- /dev/null
+++ b/lib/src/compiler/type_utilities.dart
@@ -0,0 +1,229 @@
+// 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.
+
+import 'dart:collection' show HashMap, HashSet;
+
+import 'package:analyzer/dart/element/element.dart';
+import 'package:analyzer/dart/element/type.dart';
+
+import '../js_ast/js_ast.dart' as JS;
+import '../js_ast/js_ast.dart' show js;
+import 'js_names.dart' as JS;
+
+Set<TypeParameterElement> freeTypeParameters(DartType t) {
+  var result = new HashSet<TypeParameterElement>();
+  void find(DartType t) {
+    if (t is TypeParameterType) {
+      result.add(t.element);
+    } else if (t is FunctionType) {
+      find(t.returnType);
+      t.parameters.forEach((p) => find(p.type));
+      t.typeFormals.forEach((p) => find(p.bound));
+      t.typeFormals.forEach(result.remove);
+    } else if (t is InterfaceType) {
+      t.typeArguments.forEach(find);
+    }
+  }
+  find(t);
+  return result;
+}
+
+/// _CacheTable tracks cache variables for variables that
+/// are emitted in place with a hoisted variable for a cache.
+class _CacheTable {
+  /// Mapping from types to their canonical names.
+  final _names = new HashMap<DartType, JS.TemporaryId>();
+  Iterable<DartType> get keys => _names.keys.toList();
+
+  JS.Statement _dischargeType(DartType type) {
+    var name = _names.remove(type);
+    if (name != null) {
+      return js.statement('let #;', [name]);
+    }
+    return null;
+  }
+
+  /// Emit a list of statements declaring the cache variables for
+  /// types tracked by this table.  If [typeFilter] is given,
+  /// only emit the types listed in the filter.
+  List<JS.Statement> discharge([Iterable<DartType> typeFilter]) {
+    var decls = <JS.Statement>[];
+    var types = typeFilter ?? keys;
+    for (var t in types) {
+      var stmt = _dischargeType(t);
+      if (stmt != null) decls.add(stmt);
+    }
+    return decls;
+  }
+
+  bool isNamed(DartType type) => _names.containsKey(type);
+
+  /// If [type] is not already in the table, choose a new canonical
+  /// variable to contain it. Emit an expression which uses [typeRep] to
+  /// lazily initialize the cache in place.
+  JS.Expression nameType(DartType type, JS.Expression typeRep) {
+    var temp = _names[type];
+    if (temp == null) {
+      _names[type] = temp = chooseTypeName(type);
+    }
+    return js.call('# || (# = #)', [temp, temp, typeRep]);
+  }
+
+  String _typeString(DartType type, {bool flat: false}) {
+    if (type is ParameterizedType && type.name != null) {
+      var clazz = type.name;
+      var params = type.typeArguments;
+      if (params == null) return clazz;
+      if (params.every((p) => p.isDynamic)) return clazz;
+      var paramStrings = params.map(_typeString);
+      var paramString = paramStrings.join("\$");
+      return "${clazz}Of${paramString}";
+    }
+    if (type is FunctionType) {
+      if (flat) return "Fn";
+      var rType = _typeString(type.returnType, flat: true);
+      var paramStrings = type.normalParameterTypes
+          .take(3)
+          .map((p) => _typeString(p, flat: true));
+      var paramString = paramStrings.join("And");
+      var count = type.normalParameterTypes.length;
+      if (count > 3 ||
+          type.namedParameterTypes.isNotEmpty ||
+          type.optionalParameterTypes.isNotEmpty) {
+        paramString = "${paramString}__";
+      } else if (count == 0) {
+        paramString = "Void";
+      }
+      return "${paramString}To${rType}";
+    }
+    if (type is TypeParameterType) return type.name;
+    if (type.name != null) return type.name;
+    return "type";
+  }
+
+  /// Heuristically choose a good name for the cache and generator
+  /// variables.
+  JS.Identifier chooseTypeName(DartType type) {
+    return new JS.TemporaryId(_typeString(type));
+  }
+}
+
+/// _GeneratorTable tracks types which have been
+/// named and hoisted.
+class _GeneratorTable extends _CacheTable {
+  final _defs = new HashMap<DartType, JS.Expression>();
+
+  JS.Statement _dischargeType(DartType t) {
+    var name = _names.remove(t);
+    if (name != null) {
+      JS.Expression init = _defs.remove(t);
+      assert(init != null);
+      return js.statement(
+          'let # = () => ((# = dart.constFn(#))());', [name, name, init]);
+    }
+    return null;
+  }
+
+  /// If [type] does not already have a generator name chosen for it,
+  /// assign it one, using [typeRep] as the initializer for it.
+  /// Emit an expression which calls the generator name.
+  JS.Expression nameType(DartType type, JS.Expression typeRep) {
+    var temp = _names[type];
+    if (temp == null) {
+      _names[type] = temp = chooseTypeName(type);
+      _defs[type] = typeRep;
+    }
+    return js.call('#()', [temp]);
+  }
+}
+
+class TypeTable {
+  /// Cache variable names for types emitted in place.
+  final _cacheNames = new _CacheTable();
+
+  /// Cache variable names for definite function types emitted in place.
+  final _definiteCacheNames = new _CacheTable();
+
+  /// Generator variable names for hoisted types.
+  final _generators = new _GeneratorTable();
+
+  /// Generator variable names for hoisted definite function types.
+  final _definiteGenerators = new _GeneratorTable();
+
+  /// Mapping from type parameters to the types which must have their
+  /// cache/generator variables discharged at the binding site for the
+  /// type variable since the type definition depends on the type
+  /// parameter.
+  final _scopeDependencies =
+      new HashMap<TypeParameterElement, List<DartType>>();
+
+  /// Emit a list of statements declaring the cache variables and generator
+  /// definitions tracked by the table.  If [formals] is present, only
+  /// emit the definitions which depend on the formals.
+  List<JS.Statement> discharge([List<TypeParameterElement> formals]) {
+    var filter = formals?.expand((p) => _scopeDependencies[p] ?? []);
+    var stmts = [
+      _cacheNames,
+      _definiteCacheNames,
+      _generators,
+      _definiteGenerators
+    ].expand((c) => c.discharge(filter)).toList();
+    formals?.forEach(_scopeDependencies.remove);
+    return stmts;
+  }
+
+  /// Record the dependencies of the type on its free variables
+  bool recordScopeDependencies(DartType type) {
+    var fvs = freeTypeParameters(type);
+    // TODO(leafp): This is a hack to avoid trying to hoist out of
+    // generic functions and generic function types.  This often degrades
+    // readability to little or no benefit.  It would be good to do this
+    // when we know that we can hoist it to an outer scope, but for
+    // now we just disable it.
+    if (fvs.any((i) => i.enclosingElement is FunctionTypedElement)) {
+      return true;
+    }
+    void addScope(TypeParameterElement i) {
+      List<DartType> types = _scopeDependencies[i];
+      if (types == null) _scopeDependencies[i] = types = [];
+      types.add(type);
+    }
+    fvs.forEach(addScope);
+    return false;
+  }
+
+  /// Given a type [type], and a JS expression [typeRep] which implements it,
+  /// add the type and its representation to the table, returning an
+  /// expression which implements the type (but which caches the value).
+  ///
+  /// If [hoist] is true, then the JS representation will be hoisted up
+  /// as far as possible and shared between instances of the type.  For
+  /// example, the generated code for dart.is(x, type) ends up as:
+  ///   let cacheVar;
+  ///   ...
+  ///   dart.is(x, (cacheVar || cacheVar = type))
+  ///
+  /// If [hoist] is false, the cache variable will be hoisted up as
+  /// far as possible and shared between instances of the type, but the
+  /// initializer expression will be emitted in place.  The generated code
+  /// for dart.is(x, type) in this case ends up as:
+  ///   let generator = () => (generator = dart.constFn(type))()
+  ///   ....
+  ///   dart.is(x, generator())
+  ///
+  /// The boolean parameter [definite] distinguishes between definite function
+  /// types and other types (since the same DartType may have different
+  /// representations as definite and indefinite function types).
+  JS.Expression nameType(DartType type, JS.Expression typeRep,
+      {bool hoistType, bool definite: false}) {
+    assert(hoistType != null);
+    var table = hoistType
+        ? (definite ? _definiteGenerators : _generators)
+        : (definite ? _definiteCacheNames : _cacheNames);
+    if (!table.isNamed(type)) {
+      if (recordScopeDependencies(type)) return typeRep;
+    }
+    return table.nameType(type, typeRep);
+  }
+}