| // Copyright (c) 2016, 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, Queue; |
| |
| import 'package:kernel/core_types.dart'; |
| import 'package:kernel/kernel.dart'; |
| import 'package:kernel/type_environment.dart'; |
| |
| import '../compiler/js_names.dart' as js_ast; |
| import 'kernel_helpers.dart'; |
| import 'native_types.dart'; |
| |
| /// Dart allows all fields to be overridden. |
| /// |
| /// To prevent a performance/code size penalty for allowing this, we analyze |
| /// private classes within each library that is being compiled to determine |
| /// if those fields should be virtual or not. In effect, we devirtualize fields |
| /// when possible by analyzing the class hierarchy and using knowledge of |
| /// which members are private and thus, could not be overridden outside of the |
| /// current library. |
| class VirtualFieldModel { |
| final _modelForLibrary = HashMap<Library, _LibraryVirtualFieldModel>(); |
| |
| _LibraryVirtualFieldModel _getModel(Library library) => _modelForLibrary |
| .putIfAbsent(library, () => _LibraryVirtualFieldModel.build(library)); |
| |
| /// Returns true if a field is virtual. |
| bool isVirtual(Field field) => |
| _getModel(field.enclosingLibrary).isVirtual(field); |
| } |
| |
| /// This is a building block of [VirtualFieldModel], used to track information |
| /// about a single library that has been analyzed. |
| class _LibraryVirtualFieldModel { |
| /// Fields that are private (or public fields of a private class) and |
| /// overridden in this library. |
| /// |
| /// This means we must generate them as virtual fields using a property pair |
| /// in JavaScript. |
| final _overriddenPrivateFields = HashSet<Field>(); |
| |
| /// Private classes that can be extended outside of this library. |
| /// |
| /// Normally private classes cannot be accessed outside this library, however, |
| /// this can happen if they are extended by a public class, for example: |
| /// |
| /// class _A { int x = 42; } |
| /// class _B { int x = 42; } |
| /// |
| /// // _A is now effectively public for the purpose of overrides. |
| /// class C extends _A {} |
| /// |
| /// The class _A must treat is "x" as virtual, however _B does not. |
| final _extensiblePrivateClasses = HashSet<Class>(); |
| |
| _LibraryVirtualFieldModel.build(Library library) { |
| var allClasses = library.classes; |
| |
| // The set of public types is our initial extensible type set. |
| // From there, visit all immediate private types in this library, and so on |
| // from those private types, marking them as extensible. |
| var classesToVisit = |
| Queue<Class>.from(allClasses.where((c) => !c.name.startsWith('_'))); |
| while (classesToVisit.isNotEmpty) { |
| var c = classesToVisit.removeFirst(); |
| |
| // For each supertype of a public type in this library, |
| // if we encounter a private class, we mark it as being extended, and |
| // add it to our work set if this is the first time we've visited it. |
| for (var superclass in getImmediateSuperclasses(c)) { |
| if (superclass.name.startsWith('_') && |
| superclass.enclosingLibrary == library) { |
| if (_extensiblePrivateClasses.add(superclass)) { |
| classesToVisit.add(superclass); |
| } |
| } |
| } |
| } |
| |
| // Class can only look up inherited members with an O(N) scan through |
| // the class, so we build up a mapping of all fields in the library ahead of |
| // time. |
| Map<String, Field> getInstanceFieldMap(Class c) { |
| var instanceFields = c.fields.where((f) => !f.isStatic); |
| return HashMap.fromIterables( |
| instanceFields.map((f) => f.name.name), instanceFields); |
| } |
| |
| var allFields = |
| HashMap.fromIterables(allClasses, allClasses.map(getInstanceFieldMap)); |
| |
| for (var class_ in allClasses) { |
| Set<Class> superclasses; |
| |
| // Visit accessors in the current class, and see if they override an |
| // otherwise private field. |
| for (var member in class_.members) { |
| // Ignore abstract/static accessors, methods, constructors. |
| if (member.isAbstract || |
| member is Procedure && (!member.isAccessor || member.isStatic) || |
| member is Constructor) { |
| continue; |
| } |
| assert(member is Field || member is Procedure && member.isAccessor); |
| |
| // Ignore public accessors in extensible classes. |
| if (!member.name.isPrivate && |
| (!class_.name.startsWith('_') || |
| _extensiblePrivateClasses.contains(class_))) { |
| continue; |
| } |
| |
| if (superclasses == null) { |
| superclasses = Set(); |
| void collectSupertypes(Class c) { |
| if (!superclasses.add(c)) return; |
| var s = c.superclass; |
| if (s != null) collectSupertypes(s); |
| var m = c.mixedInClass; |
| if (m != null) collectSupertypes(m); |
| } |
| |
| collectSupertypes(class_); |
| superclasses.remove(class_); |
| superclasses.removeWhere((s) => s.enclosingLibrary != library); |
| } |
| |
| // Look in all super classes to see if we're overriding a field in our |
| // library, if so mark that field as overridden. |
| var name = member.name.name; |
| _overriddenPrivateFields.addAll(superclasses |
| .map((c) => allFields[c][name]) |
| .where((f) => f != null)); |
| } |
| } |
| } |
| |
| /// Returns true if a field inside this library is virtual. |
| bool isVirtual(Field field) { |
| // If the field was marked non-virtual, we know for sure. |
| if (field.isStatic) return false; |
| |
| var class_ = field.enclosingClass; |
| if (class_.isEnum) { |
| // Enums are not extensible. |
| return false; |
| } |
| var libraryUri = class_.enclosingLibrary.importUri; |
| if (libraryUri.scheme == 'dart' && libraryUri.path.startsWith('_')) { |
| // There should be no extensible fields in private SDK libraries. |
| return false; |
| } |
| |
| if (!field.name.isPrivate) { |
| // Public fields in public classes (or extensible private classes) |
| // are always virtual. |
| // They could be overridden by someone using our library. |
| if (!class_.name.startsWith('_')) return true; |
| if (_extensiblePrivateClasses.contains(class_)) return true; |
| } |
| |
| // Otherwise, the field is effectively private and we only need to make it |
| // virtual if it's overridden. |
| return _overriddenPrivateFields.contains(field); |
| } |
| } |
| |
| /// Tracks how fields, getters and setters are represented when emitting JS. |
| /// |
| /// Dart classes have implicit features that must be made explicit: |
| /// |
| /// - virtual fields induce a getter and setter pair. |
| /// - getters and setters are independent. |
| /// - getters and setters can be overridden. |
| /// |
| class ClassPropertyModel { |
| final NativeTypeSet extensionTypes; |
| final TypeEnvironment types; |
| |
| /// Fields that are virtual, that is, they must be generated as a property |
| /// pair in JavaScript. |
| /// |
| /// The value property stores the symbol used for the field's storage slot. |
| final virtualFields = <Field, js_ast.TemporaryId>{}; |
| |
| /// The set of inherited getters, used because JS getters/setters are paired, |
| /// so if we're generating a setter we may need to emit a getter that calls |
| /// super. |
| final inheritedGetters = HashSet<String>(); |
| |
| /// The set of inherited setters, used because JS getters/setters are paired, |
| /// so if we're generating a getter we may need to emit a setter that calls |
| /// super. |
| final inheritedSetters = HashSet<String>(); |
| |
| final extensionMethods = Set<String>(); |
| |
| final extensionAccessors = Set<String>(); |
| |
| ClassPropertyModel.build(this.types, this.extensionTypes, |
| VirtualFieldModel fieldModel, Class class_) { |
| // Visit superclasses to collect information about their fields/accessors. |
| // This is expensive so we try to collect everything in one pass. |
| for (var base in getSuperclasses(class_)) { |
| for (var member in base.members) { |
| if (member is Constructor || |
| member is Procedure && (!member.isAccessor || member.isStatic)) { |
| continue; |
| } |
| |
| // Ignore private names from other libraries. |
| if (member.name.isPrivate && |
| member.enclosingLibrary != class_.enclosingLibrary) { |
| continue; |
| } |
| |
| var name = member.name.name; |
| if (member is Field) { |
| inheritedGetters.add(name); |
| if (!member.isFinal) inheritedSetters.add(name); |
| } else { |
| var accessor = member as Procedure; |
| assert(accessor.isAccessor); |
| (accessor.isGetter ? inheritedGetters : inheritedSetters).add(name); |
| } |
| } |
| } |
| |
| _collectExtensionMembers(class_); |
| |
| var virtualAccessorNames = HashSet<String>() |
| ..addAll(inheritedGetters) |
| ..addAll(inheritedSetters) |
| ..addAll(extensionAccessors); |
| |
| // Visit accessors in the current class, and see if they need to be |
| // generated differently based on the inherited fields/accessors. |
| for (var field in class_.fields) { |
| // Also ignore abstract fields. |
| if (field.isAbstract || field.isStatic) continue; |
| |
| var name = field.name.name; |
| if (virtualAccessorNames.contains(name) || |
| fieldModel.isVirtual(field) || |
| field.isCovariant || |
| field.isGenericCovariantImpl) { |
| virtualFields[field] = js_ast.TemporaryId(name); |
| } |
| } |
| } |
| |
| CoreTypes get coreTypes => extensionTypes.coreTypes; |
| |
| void _collectExtensionMembers(Class class_) { |
| if (extensionTypes.isNativeClass(class_)) return; |
| |
| // Find all generic interfaces that could be used to call into members of |
| // this class. This will help us identify which parameters need checks |
| // for soundness. |
| var allNatives = HashSet<String>(); |
| _collectNativeMembers(class_, allNatives); |
| if (allNatives.isEmpty) return; |
| |
| // For members on this class, check them against all generic interfaces. |
| var seenConcreteMembers = HashSet<String>(); |
| _findExtensionMembers(class_, seenConcreteMembers, allNatives); |
| |
| // For members of the superclass, we may need to add checks because this |
| // class adds a new unsafe interface. Collect those checks. |
| var visited = HashSet<Class>()..add(class_); |
| var existingMembers = HashSet<String>(); |
| |
| void visitImmediateSuper(Class c) { |
| // For members of mixins/supertypes, check them against new interfaces, |
| // and also record any existing checks they already had. |
| var oldCovariant = HashSet<String>(); |
| _collectNativeMembers(c, oldCovariant); |
| var newCovariant = allNatives.difference(oldCovariant); |
| if (newCovariant.isEmpty) return; |
| |
| existingMembers.addAll(oldCovariant); |
| |
| void visitSuper(Class c) { |
| if (visited.add(c)) { |
| _findExtensionMembers(c, seenConcreteMembers, newCovariant); |
| var m = c.mixedInClass; |
| if (m != null) visitSuper(m); |
| var s = c.superclass; |
| if (s != null) visitSuper(s); |
| } |
| } |
| |
| visitSuper(c); |
| } |
| |
| if (class_.superclass != null) { |
| var mixins = <Class>[]; |
| var superclass = getSuperclassAndMixins(class_, mixins); |
| mixins.forEach(visitImmediateSuper); |
| visitImmediateSuper(superclass); |
| } |
| } |
| |
| /// Searches all concrete instance members declared on this type, skipping |
| /// already [seenConcreteMembers], and adds them to [extensionMembers] if |
| /// needed. |
| /// |
| /// By tracking the set of seen members, we can visit superclasses and mixins |
| /// and ultimately collect every most-derived member exposed by a given type. |
| void _findExtensionMembers( |
| Class c, HashSet<String> seenConcreteMembers, Set<String> allNatives) { |
| // We only visit each most derived concrete member. |
| // To avoid visiting an overridden superclass member, we skip members |
| // we've seen, and visit starting from the class, then mixins in |
| // reverse order, then superclasses. |
| for (var m in c.members) { |
| var name = m.name.name; |
| if (m.isAbstract || m is Constructor) continue; |
| if (m is Procedure) { |
| if (m.isStatic) continue; |
| if (seenConcreteMembers.add(name) && allNatives.contains(name)) { |
| (m.isAccessor ? extensionAccessors : extensionMethods).add(name); |
| } |
| } else if (m is Field) { |
| if (m.isStatic) continue; |
| if (seenConcreteMembers.add(name) && allNatives.contains(name)) { |
| extensionAccessors.add(name); |
| } |
| } |
| } |
| } |
| |
| /// Collects all supertypes that may themselves contain native subtypes, |
| /// excluding [Object], for example `List` is implemented by several native |
| /// types. |
| void _collectNativeMembers(Class c, Set<String> members) { |
| if (extensionTypes.hasNativeSubtype(c)) { |
| for (var m in c.members) { |
| if (!m.name.isPrivate && |
| (m is Procedure && !m.isStatic || m is Field && !m.isStatic)) { |
| members.add(m.name.name); |
| } |
| } |
| } |
| var m = c.mixedInClass; |
| if (m != null) _collectNativeMembers(m, members); |
| for (var i in c.implementedTypes) { |
| _collectNativeMembers(i.classNode, members); |
| } |
| var s = c.superclass; |
| if (s != null) _collectNativeMembers(s, members); |
| } |
| } |