Implement subtype relation for kernel based elements.

pkg/compiler/lib/src/kernel/world_builder.dart

 // Copyright (c) 2017, 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 dart2js.kernel.world_builder;
 
 import 'package:kernel/ast.dart' as ir;
 
 import '../common.dart';
 import '../common/resolution.dart';
 import '../compile_time_constants.dart';
 import '../constants/constant_system.dart';
 import '../constants/constructors.dart';
 import '../constants/evaluation.dart';
 import '../constants/expressions.dart';
 import '../constants/values.dart';
 import '../common_elements.dart';
 import '../elements/elements.dart';
 import '../elements/entities.dart';
 import '../elements/types.dart';
 import '../js_backend/constant_system_javascript.dart';
 import '../js_backend/native_data.dart';
 import '../js_backend/no_such_method_registry.dart';
 import '../native/native.dart' as native;
 import '../native/resolver.dart';
+import '../ordered_typeset.dart';
 import '../ssa/kernel_impact.dart';
 import '../universe/call_structure.dart';
+import '../util/util.dart' show Link, LinkBuilder;
 import 'element_adapter.dart';
 import 'elements.dart';
 
 part 'native_basic_data.dart';
 part 'native_class_resolver.dart';
 part 'no_such_method_resolver.dart';
+part 'types.dart';
 
 /// World builder used for creating elements and types corresponding to Kernel
 /// IR nodes.
 // TODO(johnniwinther): Implement [ResolutionWorldBuilder].
 class KernelWorldBuilder extends KernelElementAdapterMixin {
   CommonElements _commonElements;
   native.BehaviorBuilder _nativeBehaviorBuilder;
   final DiagnosticReporter reporter;
   ElementEnvironment _elementEnvironment;
   DartTypeConverter _typeConverter;
   KernelConstantEnvironment _constantEnvironment;
+  _KernelDartTypes _types;
 
   /// Library environment. Used for fast lookup.
   KEnv _env;
 
   /// List of library environments by `KLibrary.libraryIndex`. This is used for
   /// fast lookup into library classes and members.
   List<KLibraryEnv> _libraryEnvs = <KLibraryEnv>[];
 
   /// List of class environments by `KClass.classIndex`. This is used for
   /// fast lookup into class members.
@@ skipping 21 matching lines @@
   Map<ir.TreeNode, KLocalFunction> _localFunctionMap =
       <ir.TreeNode, KLocalFunction>{};
 
   KernelWorldBuilder(this.reporter, ir.Program program)
       : _env = new KEnv(program) {
     _elementEnvironment = new KernelElementEnvironment(this);
     _commonElements = new CommonElements(_elementEnvironment);
     _constantEnvironment = new KernelConstantEnvironment(this);
     _nativeBehaviorBuilder =
         new KernelBehaviorBuilder(_commonElements, _constantEnvironment);
+    _types = new _KernelDartTypes(this);
     _typeConverter = new DartTypeConverter(this);
   }
 
   KMethod get _mainFunction {
     return _env.program.mainMethod != null
         ? _getMethod(_env.program.mainMethod)
         : null;
   }
 
   KLibrary get _mainLibrary {
@@ skipping 13 matching lines @@
   }
 
   @override
   CommonElements get commonElements => _commonElements;
 
   @override
   ElementEnvironment get elementEnvironment => _elementEnvironment;
 
   ConstantEnvironment get constantEnvironment => _constantEnvironment;
 
+  DartTypes get types => _types;
+
   @override
   native.BehaviorBuilder get nativeBehaviorBuilder => _nativeBehaviorBuilder;
 
   LibraryEntity lookupLibrary(Uri uri) {
     KLibraryEnv libraryEnv = _env.lookupLibrary(uri);
     return _getLibrary(libraryEnv.library, libraryEnv);
   }
 
   KLibrary _getLibrary(ir.Library node, [KLibraryEnv libraryEnv]) {
     return _libraryMap.putIfAbsent(node, () {
@@ skipping 279 matching lines @@
     return env.thisType;
   }
 
   InterfaceType _getRawType(KClass cls) {
     KClassEnv env = _classEnvs[cls.classIndex];
     _ensureThisAndRawType(cls, env);
     return env.rawType;
   }
 
   void _ensureSupertypes(KClass cls, KClassEnv env) {
-    if (env.supertypes == null) {
+    if (env.orderedTypeSet == null) {
       _ensureThisAndRawType(cls, env);
 
       ir.Class node = env.cls;
 
-      Set<InterfaceType> supertypes = new Set<InterfaceType>();
+      if (node.supertype == null) {
+        env.orderedTypeSet = new OrderedTypeSet.singleton(env.thisType);
+      } else {
+        InterfaceType processSupertype(ir.Supertype node) {
+          InterfaceType type = _typeConverter.visitSupertype(node);
+          KClass superclass = type.element;
+          KClassEnv env = _classEnvs[superclass.classIndex];
+          _ensureSupertypes(superclass, env);
+          return type;
+        }
 
-      InterfaceType addSupertype(ir.Supertype node) {
-        if (node == null) return null;
-        InterfaceType type = _typeConverter.visitSupertype(node);
-        KClass superclass = type.element;
-        KClassEnv env = _classEnvs[superclass.classIndex];
-        _ensureSupertypes(superclass, env);
-        for (InterfaceType supertype in env.supertypes) {
-          supertypes.add(
-              supertype.subst(type.typeArguments, env.thisType.typeArguments));
+        env.supertype = processSupertype(node.supertype);
+        LinkBuilder<InterfaceType> linkBuilder =
+            new LinkBuilder<InterfaceType>();
+        if (node.mixedInType != null) {
+          linkBuilder.addLast(processSupertype(node.mixedInType));
         }
-        return type;
+        node.implementedTypes.forEach((ir.Supertype supertype) {
+          linkBuilder.addLast(processSupertype(supertype));
+        });
+        Link<InterfaceType> interfaces = linkBuilder.toLink();
+        OrderedTypeSetBuilder setBuilder =
+            new _KernelOrderedTypeSetBuilder(this, cls);
+        env.orderedTypeSet =
+            setBuilder.createOrderedTypeSet(env.supertype, interfaces);
       }
-
-      env.supertype = addSupertype(node.supertype);
-      addSupertype(node.mixedInType);
-      node.implementedTypes.forEach(addSupertype);
-
-      env.supertypes = supertypes.toList();
     }
   }
 
+  OrderedTypeSet _getOrderedTypeSet(KClass cls) {
+    KClassEnv env = _classEnvs[cls.classIndex];
+    _ensureSupertypes(cls, env);
+    return env.orderedTypeSet;
+  }
+
+  int _getHierarchyDepth(KClass cls) {
+    KClassEnv env = _classEnvs[cls.classIndex];
+    _ensureSupertypes(cls, env);
+    return env.orderedTypeSet.maxDepth;
+  }
+
+  InterfaceType _substByContext(InterfaceType type, InterfaceType context) {
+    return type.subst(
+        context.typeArguments, _getThisType(context.element).typeArguments);
+  }
+
   InterfaceType _getSuperType(KClass cls) {
     KClassEnv env = _classEnvs[cls.classIndex];
     _ensureSupertypes(cls, env);
     return env.supertype;
   }
 
   void _forEachSupertype(KClass cls, void f(InterfaceType supertype)) {
     KClassEnv env = _classEnvs[cls.classIndex];
     _ensureSupertypes(cls, env);
-    env.supertypes.forEach(f);
+    env.orderedTypeSet.supertypes.forEach(f);
+  }
+
+  void _forEachClassMember(
+      KClass cls, void f(ClassEntity cls, MemberEntity member)) {
+    KClassEnv env = _classEnvs[cls.classIndex];
+    env.forEachMember((ir.Member member) {
+      f(cls, getMember(member));
+    });
+    _ensureSupertypes(cls, env);
+    if (env.supertype != null) {
+      _forEachClassMember(env.supertype.element, f);
+    }
   }
 
   @override
   FunctionType getFunctionType(ir.FunctionNode node) {
     DartType returnType = getDartType(node.returnType);
     List<DartType> parameterTypes = /*<DartType>*/ [];
     List<DartType> optionalParameterTypes = /*<DartType>*/ [];
     for (ir.VariableDeclaration variable in node.positionalParameters) {
       if (parameterTypes.length == node.requiredParameterCount) {
         optionalParameterTypes.add(getDartType(variable.type));
@@ skipping 167 matching lines @@
 }
 
 /// Environment for fast lookup of class members.
 // TODO(johnniwinther): Add member lookup.
 class KClassEnv {
   final ir.Class cls;
 
   InterfaceType thisType;
   InterfaceType rawType;
   InterfaceType supertype;
-  List<InterfaceType> supertypes;
+  OrderedTypeSet orderedTypeSet;
 
   Map<String, ir.Member> _constructorMap;
   Map<String, ir.Member> _memberMap;
 
   Iterable<ConstantExpression> _metadata;
 
   KClassEnv(this.cls);
 
   void _ensureMaps() {
     if (_memberMap == null) {
@@ skipping 18 matching lines @@
     _ensureMaps();
     return _memberMap[name];
   }
 
   /// Return the [ir.Member] for the member [name] in [library].
   ir.Member lookupConstructor(String name, {bool setter: false}) {
     _ensureMaps();
     return _constructorMap[name];
   }
 
+  void forEachMember(f(ir.Member member)) {
+    _ensureMaps();
+    _memberMap.values.forEach(f);
+  }
+
   Iterable<ConstantExpression> getMetadata(KernelWorldBuilder worldBuilder) {
     if (_metadata == null) {
       _metadata = worldBuilder.getMetadata(cls.annotations);
     }
     return _metadata;
   }
 }
 
 class KernelElementEnvironment implements ElementEnvironment {
   final KernelWorldBuilder worldBuilder;
@@ skipping 29 matching lines @@
   }
 
   @override
   InterfaceType createInterfaceType(
       ClassEntity cls, List<DartType> typeArguments) {
     return new InterfaceType(cls, typeArguments);
   }
 
   @override
   bool isSubtype(DartType a, DartType b) {
-    // TODO(johnniwinther): Implement this.
-    return false;
+    return worldBuilder.types.isSubtype(a, b);
   }
 
   @override
   FunctionType getFunctionType(KFunction function) {
     throw new UnimplementedError('KernelElementEnvironment.getFunctionType');
   }
 
   @override
   FunctionType getLocalFunctionType(KLocalFunction function) {
     return function.functionType;
@@ skipping 38 matching lines @@
   }
 
   @override
   void forEachMixin(ClassEntity cls, void f(ClassEntity mixin)) {
     throw new UnimplementedError('KernelElementEnvironment.forEachMixin');
   }
 
   @override
   void forEachClassMember(
       ClassEntity cls, void f(ClassEntity declarer, MemberEntity member)) {
-    // TODO(johnniwinther): Implement this.
+    worldBuilder._forEachClassMember(cls, f);
   }
 
   @override
   MemberEntity lookupLibraryMember(LibraryEntity library, String name,
       {bool setter: false, bool required: false}) {
     MemberEntity member =
         worldBuilder.lookupLibraryMember(library, name, setter: setter);
     if (member == null && required) {
       throw new SpannableAssertionFailure(CURRENT_ELEMENT_SPANNABLE,
           "The member '${name}' was not found in library '${library.name}'.");
@@ skipping 269 matching lines @@
   }
 
   InterfaceType getMixinTypeForClass(KClass cls) {
     KClassEnv env = builder._classEnvs[cls.classIndex];
     ir.Supertype mixedInType = env.cls.mixedInType;
     if (mixedInType == null) return null;
     return builder.createInterfaceType(
         mixedInType.classNode, mixedInType.typeArguments);
   }
 }