Merge WorldImpl with ResolutionWorldBuilderImpl

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

 // Copyright (c) 2012, 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 universe;
 
 import 'dart:collection';
 
 import '../cache_strategy.dart';
 import '../common.dart';
 import '../common/backend_api.dart' show Backend;
 import '../common/names.dart' show Identifiers;
 import '../common/resolution.dart' show Resolution;
 import '../compiler.dart' show Compiler;
+import '../core_types.dart';
 import '../dart_types.dart';
 import '../elements/elements.dart';
 import '../elements/entities.dart';
-import '../universe/class_set.dart' show Instantiation;
+import '../universe/class_set.dart';
+import '../universe/function_set.dart' show FunctionSetBuilder;
 import '../util/enumset.dart';
 import '../util/util.dart';
-import '../world.dart' show World, ClosedWorld, OpenWorld, WorldImpl;
+import '../world.dart' show World, ClosedWorld, ClosedWorldImpl, OpenWorld;
 import 'selector.dart' show Selector;
 import 'use.dart' show DynamicUse, DynamicUseKind, StaticUse, StaticUseKind;
 
 /// The known constraint on receiver for a dynamic call site.
 ///
 /// This can for instance be used to constrain this dynamic call to `foo` to
 /// 'receivers of the exact instance `Bar`':
 ///
 ///     class Bar {
 ///        void foo() {}
@@ skipping 127 matching lines @@
   /// Registers that [type] is checked in this universe. The unaliased type is
   /// returned.
   DartType registerIsCheck(DartType type);
 
   /// All directly instantiated types, that is, the types of the directly
   /// instantiated classes.
   // TODO(johnniwinther): Improve semantic precision.
   Iterable<DartType> get instantiatedTypes;
 }
 
-abstract class ResolutionWorldBuilder implements WorldBuilder {
+abstract class ResolutionWorldBuilder implements WorldBuilder, OpenWorld {
   /// Set of (live) local functions (closures) whose signatures reference type
   /// variables.
   ///
   /// A live function is one whose enclosing member function has been enqueued.
   Iterable<Element> get closuresWithFreeTypeVariables;
 
   /// Set of (live) `call` methods whose signatures reference type variables.
   ///
   /// A live `call` method is one whose enclosing class has been instantiated.
   Iterable<Element> get callMethodsWithFreeTypeVariables;
@@ skipping 15 matching lines @@
   Iterable<Element> get fieldSetters;
 
   /// Call [f] for all classes with instantiated types. This includes the
   /// directly and abstractly instantiated classes but also classes whose type
   /// arguments are used in live factory constructors.
   void forEachInstantiatedClass(f(ClassElement cls, InstantiationInfo info));
 
   /// Returns `true` if [member] is invoked as a setter.
   bool hasInvokedSetter(Element member);
 
-  /// The [OpenWorld] being created by this world builder.
-  // TODO(johnniwinther): Merge this with [ResolutionWorldBuilder].
-  OpenWorld get openWorld;
-
   /// The closed world computed by this world builder.
   ///
   /// This is only available after the world builder has been closed.
   ClosedWorld get closedWorldForTesting;
 }
 
 /// The type and kind of an instantiation registered through
 /// `ResolutionWorldBuilder.registerTypeInstantiation`.
 class Instance {
   final InterfaceType type;
@@ skipping 237 matching lines @@
   final SelectorConstraintsStrategy selectorConstraintsStrategy;
 
   bool hasRuntimeTypeSupport = false;
   bool hasIsolateSupport = false;
   bool hasFunctionApplySupport = false;
 
   /// Used for testing the new more precise computation of instantiated types
   /// and classes.
   bool useInstantiationMap = false;
 
-  WorldImpl _openWorld;
-
   final Backend _backend;
   final Resolution _resolution;
+  bool _closed = false;
+  ClosedWorld _closedWorldCache;
+  FunctionSetBuilder _allFunctions;
+
+  final Set<TypedefElement> _allTypedefs = new Set<TypedefElement>();
+
+  final Map<ClassElement, Set<MixinApplicationElement>> _mixinUses =
+      new Map<ClassElement, Set<MixinApplicationElement>>();
+
+  // We keep track of subtype and subclass relationships in four
+  // distinct sets to make class hierarchy analysis faster.
+  final Map<ClassElement, ClassHierarchyNode> _classHierarchyNodes =
+      <ClassElement, ClassHierarchyNode>{};
+  final Map<ClassElement, ClassSet> _classSets = <ClassElement, ClassSet>{};
+
+  final Map<ClassElement, Map<ClassElement, bool>> _subtypeCoveredByCache =
+      <ClassElement, Map<ClassElement, bool>>{};
+
+  final Set<Element> alreadyPopulated;
+
+  final CacheStrategy cacheStrategy;
+
+  bool get isClosed => _closed;
 
   ResolutionWorldBuilderImpl(Backend backend, Resolution resolution,
       CacheStrategy cacheStrategy, this.selectorConstraintsStrategy)
       : this._backend = backend,
-        this._resolution = resolution {
-    _openWorld = new WorldImpl(this, backend, resolution.coreClasses,
-        resolution.coreTypes, cacheStrategy);
+        this._resolution = resolution,
+        this.cacheStrategy = cacheStrategy,
+        alreadyPopulated = cacheStrategy.newSet() {
+    _allFunctions = new FunctionSetBuilder();
   }
 
   Iterable<ClassElement> get processedClasses => _processedClasses.keys
       .where((cls) => _processedClasses[cls].isInstantiated);
 
-  OpenWorld get openWorld => _openWorld;
+  CommonElements get commonElements => _resolution.commonElements;
+
+  CoreTypes get coreTypes => _resolution.coreTypes;
 
   ClosedWorld get closedWorldForTesting {
-    if (!_openWorld.isClosed) {
+    if (!_closed) {
       throw new SpannableAssertionFailure(
           NO_LOCATION_SPANNABLE, "The world builder has not yet been closed.");
     }
-    return _openWorld.closedWorldCache;
+    return _closedWorldCache;
   }
 
   /// All directly instantiated classes, that is, classes with a generative
   /// constructor that has been called directly and not only through a
   /// super-call.
   // TODO(johnniwinther): Improve semantic precision.
   Iterable<ClassElement> get directlyInstantiatedClasses {
     Set<ClassElement> classes = new Set<ClassElement>();
     getInstantiationMap().forEach((ClassElement cls, InstantiationInfo info) {
       if (info.hasInstantiation) {
@@ skipping 89 matching lines @@
   void forEachInstantiatedClass(f(ClassElement cls, InstantiationInfo info)) {
     getInstantiationMap().forEach(f);
   }
 
   bool _hasMatchingSelector(
       Map<Selector, SelectorConstraints> selectors, Element member) {
     if (selectors == null) return false;
     for (Selector selector in selectors.keys) {
       if (selector.appliesUnnamed(member)) {
         SelectorConstraints masks = selectors[selector];
-        if (masks.applies(member, selector, _openWorld)) {
+        if (masks.applies(member, selector, this)) {
           return true;
         }
       }
     }
     return false;
   }
 
   /// Returns the instantiation map used for computing the closed world.
   ///
   /// If [useInstantiationMap] is `true`, redirections are removed and
@@ skipping 52 matching lines @@
   }
 
   void registerDynamicUse(
       DynamicUse dynamicUse, MemberUsedCallback memberUsed) {
     Selector selector = dynamicUse.selector;
     String methodName = selector.name;
     switch (dynamicUse.kind) {
       case DynamicUseKind.INVOKE:
         if (_registerNewSelector(dynamicUse, _invokedNames)) {
           _processInstanceMembers(methodName, (_MemberUsage usage) {
-            if (dynamicUse.appliesUnnamed(usage.entity, _openWorld)) {
+            if (dynamicUse.appliesUnnamed(usage.entity, this)) {
               memberUsed(usage.entity, usage.invoke());
               return true;
             }
             return false;
           });
         }
         break;
       case DynamicUseKind.GET:
         if (_registerNewSelector(dynamicUse, _invokedGetters)) {
           _processInstanceMembers(methodName, (_MemberUsage usage) {
-            if (dynamicUse.appliesUnnamed(usage.entity, _openWorld)) {
+            if (dynamicUse.appliesUnnamed(usage.entity, this)) {
               memberUsed(usage.entity, usage.read());
               return true;
             }
             return false;
           });
           _processInstanceFunctions(methodName, (_MemberUsage usage) {
-            if (dynamicUse.appliesUnnamed(usage.entity, _openWorld)) {
+            if (dynamicUse.appliesUnnamed(usage.entity, this)) {
               memberUsed(usage.entity, usage.read());
               return true;
             }
             return false;
           });
         }
         break;
       case DynamicUseKind.SET:
         if (_registerNewSelector(dynamicUse, _invokedSetters)) {
           _processInstanceMembers(methodName, (_MemberUsage usage) {
-            if (dynamicUse.appliesUnnamed(usage.entity, _openWorld)) {
+            if (dynamicUse.appliesUnnamed(usage.entity, this)) {
               memberUsed(usage.entity, usage.write());
               return true;
             }
             return false;
           });
         }
         break;
     }
   }
 
@@ skipping 187 matching lines @@
     // and that may not have happened yet.
     // So instead we use the enclosing class, which we know have had
     // its metadata parsed and analyzed.
     // Note: this assumes that there are no non-native fields on native
     // classes, which may not be the case when a native class is subclassed.
     bool isNative = _backend.isNative(cls);
     _MemberUsage usage = _instanceMemberUsage.putIfAbsent(member, () {
       _MemberUsage usage = new _MemberUsage(member, isNative: isNative);
       useSet.addAll(usage.appliedUse);
       if (member.isField && isNative) {
-        _openWorld.registerUsedElement(member);
+        registerUsedElement(member);
       }
       if (member.isFunction &&
           member.name == Identifiers.call &&
           !cls.typeVariables.isEmpty) {
         callMethodsWithFreeTypeVariables.add(member);
       }
 
       if (_hasInvokedGetter(member)) {
         useSet.addAll(usage.read());
       }
@@ skipping 16 matching lines @@
         // getters on the function.
         _instanceFunctionsByName
             .putIfAbsent(memberName, () => new Set<_MemberUsage>())
             .add(usage);
       }
 
       memberUsed(usage.entity, useSet);
       return usage;
     });
   }
+
+  /// Returns an iterable over all mixin applications that mixin [cls].
+  Iterable<MixinApplicationElement> allMixinUsesOf(ClassElement cls) {
+    Iterable<MixinApplicationElement> uses = _mixinUses[cls];
+    return uses != null ? uses : const <MixinApplicationElement>[];
+  }
+
+  /// Called to add [cls] to the set of known classes.
+  ///
+  /// This ensures that class hierarchy queries can be performed on [cls] and
+  /// classes that extend or implement it.
+  void registerClass(ClassElement cls) => _registerClass(cls);
+
+  void _registerClass(ClassElement cls, {bool isDirectlyInstantiated: false}) {
+    _ensureClassSet(cls);
+    if (isDirectlyInstantiated) {
+      _updateClassHierarchyNodeForClass(cls, directlyInstantiated: true);
+    }
+  }
+
+  void registerTypedef(TypedefElement typdef) {
+    _allTypedefs.add(typdef);
+  }
+
+  ClassHierarchyNode _ensureClassHierarchyNode(ClassElement cls) {
+    cls = cls.declaration;
+    return _classHierarchyNodes.putIfAbsent(cls, () {
+      ClassHierarchyNode parentNode;
+      if (cls.superclass != null) {
+        parentNode = _ensureClassHierarchyNode(cls.superclass);
+      }
+      return new ClassHierarchyNode(parentNode, cls);
+    });
+  }
+
+  ClassSet _ensureClassSet(ClassElement cls) {
+    cls = cls.declaration;
+    return _classSets.putIfAbsent(cls, () {
+      ClassHierarchyNode node = _ensureClassHierarchyNode(cls);
+      ClassSet classSet = new ClassSet(node);
+
+      for (InterfaceType type in cls.allSupertypes) {
+        // TODO(johnniwinther): Optimization: Avoid adding [cls] to
+        // superclasses.
+        ClassSet subtypeSet = _ensureClassSet(type.element);
+        subtypeSet.addSubtype(node);
+      }
+      if (cls.isMixinApplication) {
+        // TODO(johnniwinther): Store this in the [ClassSet].
+        MixinApplicationElement mixinApplication = cls;
+        if (mixinApplication.mixin != null) {
+          // If [mixinApplication] is malformed [mixin] is `null`.
+          registerMixinUse(mixinApplication, mixinApplication.mixin);
+        }
+      }
+
+      return classSet;
+    });
+  }
+
+  void _updateSuperClassHierarchyNodeForClass(ClassHierarchyNode node) {
+    // Ensure that classes implicitly implementing `Function` are in its
+    // subtype set.
+    ClassElement cls = node.cls;
+    if (cls != commonElements.functionClass &&
+        cls.implementsFunction(commonElements)) {
+      ClassSet subtypeSet = _ensureClassSet(commonElements.functionClass);
+      subtypeSet.addSubtype(node);
+    }
+    if (!node.isInstantiated && node.parentNode != null) {
+      _updateSuperClassHierarchyNodeForClass(node.parentNode);
+    }
+  }
+
+  void _updateClassHierarchyNodeForClass(ClassElement cls,
+      {bool directlyInstantiated: false, bool abstractlyInstantiated: false}) {
+    ClassHierarchyNode node = _ensureClassHierarchyNode(cls);
+    _updateSuperClassHierarchyNodeForClass(node);
+    if (directlyInstantiated) {
+      node.isDirectlyInstantiated = true;
+    }
+    if (abstractlyInstantiated) {
+      node.isAbstractlyInstantiated = true;
+    }
+  }
+
+  ClosedWorld closeWorld(DiagnosticReporter reporter) {
+    Map<ClassElement, Set<ClassElement>> typesImplementedBySubclasses =
+        new Map<ClassElement, Set<ClassElement>>();
+
+    /// Updates the `isDirectlyInstantiated` and `isIndirectlyInstantiated`
+    /// properties of the [ClassHierarchyNode] for [cls].
+
+    void addSubtypes(ClassElement cls, InstantiationInfo info) {
+      if (!info.hasInstantiation) {
+        return;
+      }
+      if (cacheStrategy.hasIncrementalSupport && !alreadyPopulated.add(cls)) {
+        return;
+      }
+      assert(cls.isDeclaration);
+      if (!cls.isResolved) {
+        reporter.internalError(cls, 'Class "${cls.name}" is not resolved.');
+      }
+
+      _updateClassHierarchyNodeForClass(cls,
+          directlyInstantiated: info.isDirectlyInstantiated,
+          abstractlyInstantiated: info.isAbstractlyInstantiated);
+
+      // Walk through the superclasses, and record the types
+      // implemented by that type on the superclasses.
+      ClassElement superclass = cls.superclass;
+      while (superclass != null) {
+        Set<Element> typesImplementedBySubclassesOfCls =
+            typesImplementedBySubclasses.putIfAbsent(
+                superclass, () => new Set<ClassElement>());
+        for (DartType current in cls.allSupertypes) {
+          typesImplementedBySubclassesOfCls.add(current.element);
+        }
+        superclass = superclass.superclass;
+      }
+    }
+
+    // Use the [:seenClasses:] set to include non-instantiated
+    // classes: if the superclass of these classes require RTI, then
+    // they also need RTI, so that a constructor passes the type
+    // variables to the super constructor.
+    forEachInstantiatedClass(addSubtypes);
+
+    _closed = true;
+    return _closedWorldCache = new ClosedWorldImpl(
+        backend: _backend,
+        commonElements: commonElements,
+        coreTypes: coreTypes,
+        resolverWorld: this,
+        functionSetBuilder: _allFunctions,
+        allTypedefs: _allTypedefs,
+        mixinUses: _mixinUses,
+        typesImplementedBySubclasses: typesImplementedBySubclasses,
+        classHierarchyNodes: _classHierarchyNodes,
+        classSets: _classSets);
+  }
+
+  void registerMixinUse(
+      MixinApplicationElement mixinApplication, ClassElement mixin) {
+    // TODO(johnniwinther): Add map restricted to live classes.
+    // We don't support patch classes as mixin.
+    assert(mixin.isDeclaration);
+    Set<MixinApplicationElement> users =
+        _mixinUses.putIfAbsent(mixin, () => new Set<MixinApplicationElement>());
+    users.add(mixinApplication);
+  }
+
+  void registerUsedElement(Element element) {
+    if (element.isInstanceMember && !element.isAbstract) {
+      _allFunctions.add(element);
+    }
+  }
+
+  ClosedWorld get closedWorldCache {
+    assert(isClosed);
+    return _closedWorldCache;
+  }
 }
 
 /// World builder specific to codegen.
 ///
 /// This adds additional access to liveness of selectors and elements.
 abstract class CodegenWorldBuilder implements WorldBuilder {
   void forEachInvokedName(
       f(String name, Map<Selector, SelectorConstraints> selectors));
 
   void forEachInvokedGetter(
@@ skipping 618 matching lines @@
     if (hasClosurization) {
       return MemberUses.NONE;
     }
     hasNormalUse = hasClosurization = true;
     return _pendingUse.removeAll(MemberUses.ALL_STATIC);
   }
 
   @override
   EnumSet<MemberUse> get _originalUse => MemberUses.ALL_STATIC;
 }