blob: 26f687b4586a87045078d0f5bc0287b5e5b3e10a [file] [log] [blame]
library vipunen.inferrer;
import 'package:kernel/kernel.dart';
import 'package:kernel/core_types.dart';
import 'package:kernel/type_algebra.dart' as algebra;
import 'package:kernel/transformations/treeshaker.dart';
import 'package:kernel/vm/native_effects.dart';
import 'utils.dart';
import 'dispatch_table.dart' show ClassType;
enum TypeKind { Concrete, Subclass, Interface, Closure, Bottom }
enum SelectorKind {
Method,
Getter,
Setter,
}
class Selector {
final SelectorKind kind;
final Name name;
Selector(this.kind, this.name);
factory Selector.fromProcedure(Procedure procedure) {
SelectorKind kind;
switch (procedure.kind) {
case ProcedureKind.Getter:
kind = SelectorKind.Getter;
break;
case ProcedureKind.Setter:
kind = SelectorKind.Setter;
break;
case ProcedureKind.Operator:
case ProcedureKind.Method:
case ProcedureKind.Factory:
kind = SelectorKind.Method;
break;
}
return new Selector(kind, procedure.name);
}
Selector get asGetter => new Selector(SelectorKind.Getter, name);
Selector get asMethod => new Selector(SelectorKind.Method, name);
Selector modifyKindToAccess(Member target) {
if (target is Procedure) {
if (kind == SelectorKind.Method && target.kind == ProcedureKind.Getter) {
return asGetter; // This is a call-though-getter.
} else if (kind == SelectorKind.Getter &&
target.kind == ProcedureKind.Method) {
return asMethod; // This is a tear-off.
}
} else if (target is Field) {
if (kind == SelectorKind.Method) {
return asGetter; // This is a call-though-field.
}
}
return this;
}
int get hashCode => kind.hashCode ^ name.hashCode;
bool operator ==(other) =>
other is Selector && other.kind == kind && other.name == name;
String toString() {
if (kind == SelectorKind.Getter) return 'get:${name}';
if (kind == SelectorKind.Setter) return 'set:${name}';
assert(kind == SelectorKind.Method);
return '$name';
}
}
enum NumericType { Int, Double }
class ResolvedTarget {
const ResolvedTarget();
}
class SpecialTarget extends ResolvedTarget {
final String _name;
const SpecialTarget._(this._name);
static const SpecialTarget Bottom =
const SpecialTarget._('SpecialTarget.Bottom');
static const SpecialTarget Identity =
const SpecialTarget._('SpecialTarget.Identity');
String toString() => _name;
}
class AbstractSelector extends ResolvedTarget {
final InterfaceType interface;
final Selector selector;
final Member target;
AbstractSelector(this.interface, this.selector, this.target);
}
class DirectSelector extends AbstractSelector {
DirectSelector(InterfaceType interface, Selector selector, Member target)
: super(interface, selector, target);
toString() => 'direct ${(target.parent as Class).name}->${target.name}';
}
class VirtualSelector extends AbstractSelector {
VirtualSelector(InterfaceType interface, Selector selector, Member target)
: super(interface, selector, target);
toString() => 'virtual ${(target.parent as Class).name}->${target.name}';
}
class InterfaceSelector extends AbstractSelector {
InterfaceSelector(InterfaceType interface, Selector selector, Member target)
: super(interface, selector, target) {
assert(target != null);
}
toString() => 'interface ${interface.classNode.name}->${selector}';
}
class CallThroughFieldSelector extends ResolvedTarget {
final FunctionType callee;
final AbstractSelector getterTarget;
CallThroughFieldSelector(this.getterTarget, this.callee);
toString() => 'call-through-{field,getter} ${getterTarget}';
}
class TearOffSelector extends ResolvedTarget {
final AbstractSelector methodTarget;
TearOffSelector(this.methodTarget);
toString() => 'tear-off ${methodTarget}';
}
class ClosureCall extends ResolvedTarget {
final FunctionType callee;
ClosureCall(this.callee);
toString() => "invoke[${callee}]";
}
class UnaryOp extends ResolvedTarget {
final String op;
final NumericType type;
UnaryOp(this.op, this.type);
toString() => "UnaryOp(${type} ${op})";
}
class BinaryOp extends ResolvedTarget {
final String op;
final NumericType type;
final NumericType lhs;
final NumericType rhs;
BinaryOp(this.op, this.lhs, this.rhs)
: type = (isEitherDouble(lhs, rhs) || op == '/')
? NumericType.Double
: NumericType.Int;
String toString() => "BinaryOp(${lhs} ${op} ${rhs} -> ${type})";
static isEitherDouble(NumericType lhs, NumericType rhs) {
return lhs == NumericType.Double || rhs == NumericType.Double;
}
}
class ComparisonOp extends ResolvedTarget {
final String op;
final NumericType type;
final NumericType lhs;
final NumericType rhs;
ComparisonOp(this.op, this.lhs, this.rhs)
: type = BinaryOp.isEitherDouble(lhs, rhs)
? NumericType.Double
: NumericType.Int;
toString() => "ComparisonOp([${type}] ${lhs} ${op} ${rhs})";
}
class CompileType {
final TypeKind kind;
final DartType type;
bool get isConcrete => kind == TypeKind.Concrete;
bool get isSubclass => kind == TypeKind.Subclass;
bool get isInterface => kind == TypeKind.Interface;
bool get isClosure => kind == TypeKind.Closure;
bool get isBottom => kind == TypeKind.Bottom;
const CompileType._(this.type, this.kind);
CompileType.concrete(InterfaceType type) : this._(type, TypeKind.Concrete);
CompileType.subclass(InterfaceType type) : this._(type, TypeKind.Subclass);
CompileType.interface(InterfaceType type) : this._(type, TypeKind.Interface);
CompileType.closure(FunctionType type) : this._(type, TypeKind.Closure);
const CompileType.bottom() : this._(null, TypeKind.Bottom);
NumericType toNumericType(Inferrer compiler) {
if (isConcrete) {
final klass = (type as InterfaceType).classNode;
if (compiler.isIntegerClass(klass)) {
return NumericType.Int;
} else if (compiler.isDoubleClass(klass)) {
return NumericType.Double;
}
}
throw "Can't convert ${this} to numeric type";
}
ResolvedTarget resolveMethodInvocation(
Inferrer compiler, MethodInvocation node) {
// Special case comparision with `null`.
final bool isEquals = node.name.name == "==";
if (isEquals) {
assert(node.arguments.positional.length == 1);
assert(node.arguments.named.isEmpty);
if (node.arguments.positional.first is NullLiteral ||
node.receiver is NullLiteral) {
return SpecialTarget.Identity;
}
}
// Special case int/double and closures.
if (isConcrete) {
// TODO(vegorov) argument count needs to be check and arguments need
// to be resolved.
final InterfaceType interfaceType = type as InterfaceType;
Class klass = interfaceType.classNode;
// Handle all selectors which involve 'num' in the signature.
final bool isDouble = compiler.isDoubleClass(klass);
final bool isInt = compiler.isIntegerClass(klass);
if (isDouble || isInt) {
final lhs = toNumericType(compiler);
final rhsType = node.arguments.positional.isNotEmpty
? compiler.typeOf(node.arguments.positional.first)
: null;
if (rhsType != null && rhsType.isBottom) {
return SpecialTarget.Bottom;
}
final rhs = rhsType?.toNumericType(compiler);
final op = node.name.name;
// Unary & Binary operators for double/int.
switch (op) {
case "remainder":
case "+":
case "*":
case "-":
case "/":
case "%":
case "~/":
assert(node.arguments.positional.length == 1);
assert(node.arguments.named.isEmpty);
return new BinaryOp(op, lhs, rhs);
case "<":
case ">":
case "==":
case "<=":
case ">=":
assert(node.arguments.positional.length == 1);
assert(node.arguments.named.isEmpty);
return new ComparisonOp(op, lhs, rhs);
case "unary-":
assert(node.arguments.positional.length == 0);
assert(node.arguments.named.isEmpty);
return new UnaryOp(op, lhs);
case "clamp":
case "compareTo":
// TODO(vipunen): Need to add support for these.
throw 'TODO(vipunen): No support for $op atm ($this).';
}
// Unary & Binary bitwise operators for int.
if (isInt) {
switch (op) {
case "&":
case "|":
case "^":
case "<<":
case ">>":
assert(isInt);
assert(node.arguments.positional.length == 1);
assert(node.arguments.named.isEmpty);
assert(lhs == NumericType.Int);
assert(rhs == NumericType.Int);
return new BinaryOp(op, lhs, rhs);
case "~":
assert(isInt);
assert(node.arguments.positional.length == 0);
assert(node.arguments.named.isEmpty);
return new UnaryOp(op, lhs);
}
}
}
return resolveSelector(
compiler, new Selector(SelectorKind.Method, node.name));
} else if (isClosure) {
if (isEquals) {
return SpecialTarget.Identity;
}
if (node.name.name != "call") {
throw "only call and identity is supported on closures ${node}";
}
return new ClosureCall(type);
}
return resolveSelector(
compiler, new Selector(SelectorKind.Method, node.name));
}
ResolvedTarget resolveSelector(Inferrer compiler, Selector selector) {
final InterfaceType interfaceType = type as InterfaceType;
Member target;
Selector resolvedTargetSelector;
ResolvedTarget resolvedTarget;
if (isConcrete) {
Class klass = interfaceType.classNode;
if (klass == compiler.coreTypes.doubleClass) {
klass = compiler.DoubleClass;
} else if (klass == compiler.coreTypes.intClass) {
klass = compiler.SmiClass;
}
target = compiler.lookupCache.lookupSelector(klass, selector);
if (target != null) {
resolvedTargetSelector = selector.modifyKindToAccess(target);
resolvedTarget = compiler.addDirectUsage(
interfaceType, resolvedTargetSelector, target);
}
} else if (isSubclass) {
target = compiler.lookupCache
.lookupInterfaceSelector(interfaceType.classNode, selector);
if (target != null) {
resolvedTargetSelector = selector.modifyKindToAccess(target);
if (target is Procedure) {
resolvedTarget = compiler.addVirtualUsage(
interfaceType, resolvedTargetSelector, target);
} else if (target is Field) {
resolvedTarget = compiler.addDirectUsage(
interfaceType, resolvedTargetSelector, target);
} else {
UNREACHABLE();
}
}
} else if (isInterface) {
target = compiler.lookupCache
.lookupInterfaceSelector(interfaceType.classNode, selector);
if (target != null) {
resolvedTargetSelector = selector.modifyKindToAccess(target);
resolvedTarget =
compiler.addInterfaceUsage(interfaceType, resolvedTargetSelector);
}
}
if (resolvedTarget == null) {
return SpecialTarget.Bottom;
}
final bool isTearOff = selector.kind == SelectorKind.Getter &&
resolvedTargetSelector.kind == SelectorKind.Method;
final bool isCallThroughFieldOrGetter =
selector.kind == SelectorKind.Method &&
resolvedTargetSelector.kind == SelectorKind.Getter;
if (isTearOff) {
final AbstractSelector methodSelector = resolvedTarget;
ensureProcedureCanBeTornOff(methodSelector.target);
resolvedTarget = new TearOffSelector(resolvedTarget);
} else if (isCallThroughFieldOrGetter) {
final DartType type = target is Field
? target.type
: (target as Procedure).function.returnType;
ensureIsFunctionType(type, 'call-through-field usage');
resolvedTarget = new CallThroughFieldSelector(resolvedTarget, type);
}
return resolvedTarget;
}
String toString() => "CompileType(${kind}, ${type})";
}
class AnalysisData {
final Member m;
final FunctionNode func;
final Map /* ResolvedTarget | List<ResolvedTarget> */ targets = {};
AnalysisData(this.m, this.func);
}
class CollectAllocations extends RecursiveVisitor {
final Inferrer compiler;
CollectAllocations(this.compiler);
@override
visitConstructorInvocation(ConstructorInvocation node) {
compiler.markAllocated(node.constructedType.classNode);
super.visitConstructorInvocation(node);
// Each constructor will translate the field initializers declared on the
// class fields. So we'll ensure to collect also allocations from there.
processFieldInitializers(node.target.enclosingClass);
}
@override
visitStringLiteral(StringLiteral node) {
compiler.markAllocated(compiler.OneByteStringClass);
compiler.markAllocated(compiler.TwoByteStringClass);
}
@override
visitFunctionNode(FunctionNode node) {
super.visitFunctionNode(node);
final parent = node.parent;
if (parent is Member) {
final String nativeName = findNativeName(parent);
if (nativeName != null) {
compiler.nativeEffects
.getEffectsFor(nativeName, compiler.nativeEffectsHandler);
}
}
}
void processFieldInitializers(Class klass) {
if (klass.superclass != null) processFieldInitializers(klass.superclass);
for (final Field field in klass.fields) {
if (!field.isStatic && !field.isAbstract) {
field.initializer?.accept(this);
}
}
}
}
class _NativeEffectsHandler implements NativeEffectsHandler {
final CoreTypes coreTypes;
final Inferrer inferrer;
_NativeEffectsHandler(this.coreTypes, this.inferrer);
void markAllocated(String library, String klassname) {
final Class klass = coreTypes.getClass(library, klassname);
assert(klass != null);
inferrer.markAllocated(klass);
}
}
class DependencySet {
final Inferrer compiler;
final Map<Class, List<FunctionNode>> deps = <Class, List<FunctionNode>>{};
final Map<Class, List<Function>> depsFuncs = <Class, List<Function>>{};
DependencySet(this.compiler);
invalidate(Class klass) {
final klassDeps = deps[klass];
if (klassDeps != null) {
for (FunctionNode f in klassDeps) {
print('invalidating ${f} due to ${klass}');
compiler.worklist.add(f);
}
deps.remove(klass);
}
final klassDepsFuncs = depsFuncs[klass];
if (klassDepsFuncs != null) {
for (Function f in klassDepsFuncs) {
f();
}
depsFuncs.remove(klass);
}
}
record(Class klass) {
deps.putIfAbsent(klass, () => <FunctionNode>[]).add(compiler.d.func);
}
recordFunc(Class klass, Function what) {
depsFuncs.putIfAbsent(klass, () => <Function>[]).add(what);
}
}
class HierarchyInfo {
final Map<Class, List<Class>> map = <Class, List<Class>>{};
final DependencySet deps;
HierarchyInfo(Inferrer compiler) : deps = new DependencySet(compiler);
add(Class from, Class to) {
map.putIfAbsent(from, () => <Class>[]).add(to);
deps.invalidate(from);
}
List<Class> get(Class from) => map[from];
depend(Class klass) => deps.record(klass);
}
class ClassInfo<T> {
final Map<Class, T> map = <Class, T>{};
final DependencySet deps;
final T defaultValue;
ClassInfo(Inferrer compiler, this.defaultValue)
: deps = new DependencySet(compiler);
setInfo(Class klass, T value) {
map[klass] = value;
deps.invalidate(klass);
}
T getInfo(Class klass) => map[klass] ?? defaultValue;
depend(Class klass) => deps.record(klass);
}
class Inferrer extends RecursiveVisitor {
final CoreTypes coreTypes;
final NativeEffects nativeEffects = new VmNativeEffects();
NativeEffectsHandler nativeEffectsHandler;
final Set<FunctionNode> worklist = new Set<FunctionNode>();
final Set<FunctionNode> processed = new Set<FunctionNode>();
final Map<FunctionNode, AnalysisData> data = <FunctionNode, AnalysisData>{};
final LookupCache lookupCache = new LookupCache();
// Maps an interface to a set of classes which implement that interface.
final Map<Class, Set<Class>> interfaceCache = <Class, Set<Class>>{};
// For each class a set of names which are virtually dispatched against
// instances of this class. Used to construct vtables.
final Map<Class, Set<Selector>> virtuals = <Class, Set<Selector>>{};
final Map<Field, NumericType> fieldType = <Field, NumericType>{};
final Set<Class> allocated = new Set<Class>();
// For each interface a set of names which are virtually dispatched against.
final Map<Class, Set<Selector>> interfaceVirtuals = <Class, Set<Selector>>{};
DependencySet allocatedDeps;
HierarchyInfo subclasses;
HierarchyInfo implementations;
ClassInfo subclassTypes;
CompileType intType;
CompileType doubleType;
CompileType boolType;
CompileType stringType;
Class DoubleClass;
Class SmiClass;
Class StringBaseClass;
Class OneByteStringClass;
Class TwoByteStringClass;
Class StringBase;
Class GrowableListClass;
Class ListClass;
Class ClosureClass;
Procedure StringInterpolate;
Procedure ListFromLiteral;
InterfaceType objectKernelType;
AnalysisData d;
Inferrer(Program p) : coreTypes = new CoreTypes(p) {
nativeEffectsHandler = new _NativeEffectsHandler(coreTypes, this);
allocatedDeps = new DependencySet(this);
subclasses = new HierarchyInfo(this);
subclassTypes = new ClassInfo<int>(this, ClassType.Unknown);
implementations = new HierarchyInfo(this);
// String has two subclasses: one-byte and two-byte string. They don't
// extend string though
DoubleClass = coreTypes.getClass('dart:core', '_Double');
SmiClass = coreTypes.getClass('dart:core', '_Smi');
StringBaseClass = coreTypes.getClass('dart:core', '_StringBase');
OneByteStringClass = coreTypes.getClass('dart:core', '_OneByteString');
TwoByteStringClass = coreTypes.getClass('dart:core', '_TwoByteString');
StringBase = coreTypes.getClass('dart:core', '_StringBase');
GrowableListClass = coreTypes.getClass('dart:core', '_GrowableList');
ListClass = coreTypes.getClass('dart:core', '_List');
ClosureClass = coreTypes.getClass('dart:core', '_Closure');
StringInterpolate = findPrivateMember(StringBase, '_interpolate');
ListFromLiteral = findPrivateMember(coreTypes.listClass, '_fromLiteral');
intType = new CompileType.concrete(new InterfaceType(coreTypes.intClass));
doubleType =
new CompileType.concrete(new InterfaceType(coreTypes.doubleClass));
boolType = new CompileType.concrete(new InterfaceType(coreTypes.boolClass));
stringType = new CompileType.subclass(new InterfaceType(StringBaseClass));
objectKernelType = new InterfaceType(coreTypes.objectClass);
injectMagicClassIDValues(coreTypes);
}
Procedure findPrivateMember(Class klass, String name) {
for (final Procedure procedure in klass.procedures) {
if (procedure.name.name == name) return procedure;
}
throw 'Could not find "$name" in $klass';
}
void markAllocated(Class klass) {
if (allocated.add(klass)) {
allocatedDeps.invalidate(klass);
// We can bypass all class hierarchy information, since we will never do
// dynamic dispatches on "int"/"double".
if (klass == SmiClass || klass == DoubleClass) return;
// Step 0) We track the possible [ClassType] all subclasses of a given
// class can have. Ensure it's up-to-date.
final classType = getPredefinedCid(klass) == null
? ClassType.Vipunen
: ClassType.Classic;
Class current = klass;
while (current != null) {
final oldType = subclassTypes.getInfo(current);
if (oldType != classType) {
subclassTypes.setInfo(current, oldType | classType);
}
current = current.superclass;
}
// Step 1.1) Add implementations of newly allocated [klass] to virtual
// dispatches.
//
// If we discover later that more [Name]s are virtually dispatched
// against, it will be taken care of by [addVirtualUsage].
Set<Selector> virts = virtuals[klass];
final superClasses = new Set<Class>()..add(klass);
for (var superClass = klass.superclass;
superClass != null;
superClass = superClass.superclass) {
superClasses.add(superClass);
subclasses.add(superClass, klass);
if (virtuals.containsKey(superClass)) {
if (virts == null) {
virts = virtuals[klass] = new Set<Selector>();
}
virts.addAll(virtuals[superClass]);
}
}
// Step 1.2) Enqueue the new implementations of virtually dispatched
// [Name]s.
if (virts != null) {
addMembers(klass, virts);
}
// Step 2.1) Add implementations of newly allocated [klass] to interface
// dispatches.
//
// If we discover later that more [Name]s are interface dispatched
// against, it will be taken care of by [addInterfaceUsage].
final Set<Class> interfaces = resolveImplementedInterfaces(klass);
for (final Class iface in interfaces) {
if (!superClasses.contains(iface)) {
implementations.add(iface, klass);
}
}
// Step 2.2) Enqueue the new implementations of interface dispatched
// [Name]s.
for (final Class iface in interfaces) {
addMembers(klass, interfaceVirtuals[iface] ?? const []);
}
Class superClass = klass;
while (superClass != null) {
addMembers(klass, interfaceVirtuals[superClass] ?? const []);
superClass = superClass.superclass;
}
}
}
void addMembers(Class klass, Iterable<Selector> selectors) {
if (selectors != null && selectors.length > 0) {
for (final Selector selector in selectors) {
addMember(klass, selector);
}
}
}
void addMember(Class klass, Selector selector) {
final target = lookupCache.lookupSelector(klass, selector);
if (target == null) {
throw 'The class "$klass" does not have an implementation of selector '
'"$selector"!';
}
add(target, target.function);
}
void add(Member m, FunctionNode func) {
// Also might want to collect possible names as targets.
if (!processed.contains(func)) {
final d = data.putIfAbsent(func, () => new AnalysisData(m, func));
if (d.m != m) throw 'mismatch info ${m} vs ${d.m}';
worklist.add(func);
func.accept(new CollectAllocations(this));
}
}
Set<Class> resolveImplementedInterfaces(Class klass) {
return interfaceCache.putIfAbsent(klass, () {
final Set<Class> interfaces = new Set<Class>();
// The class implements all interfaces implemented by the base class (and
// it's transitive interfaces).
if (klass.superclass != null) {
interfaces.addAll(resolveImplementedInterfaces(klass.superclass));
}
// The class implements all interfaces declared in the implements class
// (and their transitive interfaces).
for (final Supertype type in klass.implementedTypes) {
final Class klass = type.classNode;
interfaces.addAll(resolveImplementedInterfaces(klass));
Class superclass = klass.superclass;
while (superclass != null) {
interfaces.add(superclass);
superclass = superclass.superclass;
}
}
// The class implements it's own interface.
interfaces.add(klass);
return interfaces;
});
}
final Map<Class, Map<Selector, Member>> devirtCache =
<Class, Map<Selector, Member>>{};
Member singleTarget(Class klass, Selector selector) {
return devirtCache
.putIfAbsent(klass, () => <Selector, Member>{})
.putIfAbsent(selector, () {
var target = null;
if (allocated.contains(klass)) {
target = lookupCache.lookupSelector(klass, selector);
}
for (var subKlass in subclasses.get(klass) ?? const <Class>[]) {
if (target == null) {
target = lookupCache.lookupSelector(subKlass, selector);
assert(target != null);
} else if (target != lookupCache.lookupSelector(subKlass, selector)) {
return null;
}
}
invalidate() {
devirtCache[klass].remove(selector);
}
if (!allocated.contains(klass)) {
allocatedDeps.recordFunc(klass, invalidate);
}
subclasses.deps.recordFunc(klass, invalidate);
return target;
});
}
ResolvedTarget addVirtualUsage(
InterfaceType interfaceType, Selector selector, Member root) {
final Class klass = interfaceType.classNode;
final Selector selector = new Selector.fromProcedure(root);
final Member tgt = singleTarget(klass, selector);
if (tgt != null) {
if (!allocated.contains(klass)) {
allocatedDeps.record(klass);
}
subclasses.depend(klass);
return addDirectUsage(interfaceType, selector, tgt);
}
final classType = subclassTypes.getInfo(klass);
if (classType == ClassType.Unknown || classType == ClassType.Vipunen) {
final selectors = virtuals.putIfAbsent(klass, () => new Set<Selector>());
subclassTypes.depend(klass);
if (selectors.add(selector)) {
if (allocated.contains(klass)) {
final tgt = lookupCache.lookupSelector(klass, selector);
if (!tgt.isAbstract) add(tgt, tgt.function);
}
for (var subKlass in subclasses.get(klass) ?? const <Class>[]) {
if (virtuals
.putIfAbsent(subKlass, () => new Set<Selector>())
.add(selector)) {
final tgt = lookupCache.lookupSelector(subKlass, selector);
if (!tgt.isAbstract) add(tgt, tgt.function);
}
}
}
return new VirtualSelector(interfaceType, selector, root);
} else {
// There can be virtual dispatches on 'this' even though one or all
// implementation classes are non-vipunen classes (this happens e.g.
// for "_StringBase.operator==" which dispatches on "this.length").
//
// We can therefore not assume to be able to make vtable-calls and
// will consequently fall back to interface calls which can handle all
// cases.
final Selector selector = new Selector.fromProcedure(root as Procedure);
return addInterfaceUsage(new InterfaceType(klass), selector);
}
}
addInterfaceTestUsage(InterfaceType type) {
// Ensure the interface is present in the [interfaceVirtuals] map.
final Class interfaceClass = type.classNode;
interfaceVirtuals.putIfAbsent(interfaceClass, () => new Set<Selector>());
}
// TODO(vipunen): Use similar de-virtualization logic as in [addVirtualUsage]
ResolvedTarget addInterfaceUsage(InterfaceType type, Selector selector) {
final Class interfaceClass = type.classNode;
if (interfaceClass == coreTypes.numClass) {
throw 'TODO(vipunen): No support to dispatch against "num" atm!';
}
final Set<Selector> selectors = interfaceVirtuals.putIfAbsent(
interfaceClass, () => new Set<Selector>());
if (selectors.add(selector)) {
// For all allocated classes which implement this interface, we'll enqueue
// the corresponding implementations.
final List<Class> implementationClasses =
implementations.get(interfaceClass);
if (implementationClasses != null) {
for (final Class implementationClass in implementationClasses) {
assert(allocated.contains(implementationClass));
final tgt = lookupCache.lookupSelector(implementationClass, selector);
if (tgt != null && !tgt.isAbstract) add(tgt, tgt.function);
}
}
final List<Class> subclassList = subclasses.get(interfaceClass);
if (subclassList != null) {
for (final Class subclass in subclassList) {
final tgt = lookupCache.lookupSelector(subclass, selector);
if (tgt != null && !tgt.isAbstract) add(tgt, tgt.function);
}
}
// Since [implementationClasses] does not contain the allocated classes
// themselves we'll do an extra check if the interface class is itself
// allocated.
if (allocated.contains(interfaceClass)) {
final tgt = lookupCache.lookupSelector(interfaceClass, selector);
if (tgt != null && !tgt.isAbstract) add(tgt, tgt.function);
}
// NOTE: We do not need to `interfaces.depend(interfaceClass)`: If new
// classes get added which implement [interfaceClass], then the
// [markAllocated] method takes care of add()'ing members we do dynamic
// dispatches against.
}
final tgt = lookupCache.lookupInterfaceSelector(interfaceClass, selector);
if (tgt == null) return SpecialTarget.Bottom;
return new InterfaceSelector(type, selector, tgt);
}
ResolvedTarget addDirectUsage(
InterfaceType interfaceType, Selector selector, Member member) {
if (member is Procedure) {
add(member, member.function);
}
return new DirectSelector(interfaceType, selector, member);
}
process() {
markAllocated(SmiClass);
markAllocated(DoubleClass);
FunctionNode func;
try {
while (worklist.isNotEmpty) {
func = worklist.first;
worklist.remove(func);
processed.add(func);
d = data[func];
print('processing ${d.m}');
processFunction(func);
}
} catch (e) {
print('exception occured while processing '
'${stringifyNode(func.parent)} (${d.m})');
print('');
print(
'worklist: ${worklist.map((f) => data[f].m.toString()).join(', ')}');
rethrow;
}
}
processFunction(FunctionNode func) {
final TreeNode parent = func.parent;
if (parent is Constructor) {
for (final Initializer init in parent.initializers) {
processInitializer(init);
}
processFieldInitializers(parent.enclosingClass);
}
super.visitFunctionNode(func);
}
processFieldInitializers(Class klass) {
if (klass.superclass != null) processFieldInitializers(klass.superclass);
for (final Field field in klass.fields) {
if (!field.isStatic && !field.isAbstract) {
field.initializer?.accept(this);
}
}
}
processInitializer(Initializer init) {
if (init is FieldInitializer) {
init.value?.accept(this);
} else if (init is SuperInitializer) {
add(init.target, init.target.function);
init.arguments.accept(this);
} else if (init is RedirectingInitializer) {
add(init.target, init.target.function);
init.arguments.accept(this);
} else if (init is LocalInitializer) {
init.variable.initializer?.accept(this);
} else {
throw 'Unimplemented initializer $init';
}
}
CompileType subclassType(InterfaceType interfaceType) {
final Class klass = interfaceType.classNode;
final subs = subclasses.get(klass);
if (subs == null) {
subclasses.depend(klass);
if (!allocated.contains(klass)) {
allocatedDeps.record(klass);
return const CompileType.bottom();
}
return new CompileType.concrete(interfaceType);
} else if (subs.length == 1 && !allocated.contains(klass)) {
allocatedDeps.record(klass);
subclasses.depend(klass);
return new CompileType.concrete(
unknownClassType(subs.first, objectKernelType));
} else {
return new CompileType.subclass(interfaceType);
}
}
CompileType interfaceType(DartType type, {node}) {
if (type == const DynamicType()) {
throw "$node needs to be fully typed";
}
if (type is InterfaceType) {
final klass = type.classNode;
if (klass == coreTypes.intClass ||
klass == coreTypes.boolClass ||
klass == coreTypes.doubleClass) {
return new CompileType.concrete(type);
}
if (klass == coreTypes.stringClass) {
return stringType;
}
if (klass == coreTypes.functionClass) {
// TODO(vipunen) we assume that Function can't be implemented
return new CompileType.closure(null);
}
final List<Class> possible = implementations.get(klass);
if (possible == null) {
// There are no implementation of this class.
implementations.depend(klass);
return subclassType(unknownClassType(klass, objectKernelType));
} else if (possible.length == 1 &&
subclasses.get(klass) == null &&
!allocated.contains(klass)) {
allocatedDeps.record(klass);
implementations.depend(klass);
subclasses.depend(klass);
// TODO(vipunen): This de-virtualization throws away the generic type
// information we have.
return new CompileType.concrete(new InterfaceType(possible.first));
}
return new CompileType.interface(type);
} else if (type is FunctionType) {
return new CompileType.closure(type);
} else if (type is TypeParameterType) {
// TODO(vipunen): Right now we treat each type parameter type as a
// subclass of Object.
return subclassType(objectKernelType);
}
throw "unsupported type ${type}";
}
CompileType typeOf(TreeNode node) {
if (node is IntLiteral) {
return intType;
} else if (node is DoubleLiteral) {
return doubleType;
} else if (node is StringLiteral || node is StringConcatenation) {
return stringType;
} else if (node is VariableGet) {
// TODO(vipunen): For final fields/variables we should take the type which
// is more precise (either the field/variable type or the initializer
// type).
if (node.variable.isFinal && node.variable.initializer is ListLiteral) {
return typeOf(node.variable.initializer);
}
final t = node.variable.type;
if (t == const DynamicType()) {
final Expression init = node.variable.initializer;
if (init != null) {
return typeOf(init);
}
throw "Need to infer the type of variable ${node
.variable} [${node.variable.runtimeType}]"
" for ${node} [${node.runtimeType}]"
" with initializer ${init}-\n\n${stringifyNode(node)}";
}
return interfaceType(node.variable.type);
} else if (node is VariableSet) {
return typeOf(node.value);
} else if (node is ConstructorInvocation) {
return new CompileType.concrete(node.constructedType);
} else if (node is ThisExpression) {
return subclassType(
unknownClassType(d.m.enclosingClass, objectKernelType));
} else if (node is PropertyGet || node is DirectPropertyGet) {
final target = d.targets[node];
assert(target != null);
if (target == SpecialTarget.Bottom) {
return const CompileType.bottom();
} else if (target is DirectSelector) {
final Member member = target.target;
if (member is Field) {
if (member.isFinal && member.initializer is ListLiteral) {
return typeOf(member.initializer);
}
}
return interfaceType(
substituteType(target.interface, memberType(member)));
} else if (target is VirtualSelector) {
return interfaceType(target.target.function.returnType);
} else if (target is InterfaceSelector) {
final rtarget = lookupCache.lookupInterfaceSelector(
target.interface.classNode, target.selector);
assert(rtarget != null);
return interfaceType(rtarget.function.returnType);
} else if (target is TearOffSelector) {
return new CompileType.closure(
target.methodTarget.target.function.functionType);
}
throw "can't compute type of get from ${target} / ${target.runtimeType}";
} else if (node is StaticGet) {
final Member member = node.target;
if (member is Field) {
return interfaceType(member.type, node: node.target);
}
} else if (node is StaticSet) {
return typeOf(node.value);
} else if (node is MethodInvocation) {
final target = d.targets[node];
assert(target != null);
if (target == SpecialTarget.Bottom) {
return const CompileType.bottom();
} else if (target is BinaryOp || target is UnaryOp) {
switch (target.type) {
case NumericType.Int:
return intType;
case NumericType.Double:
return doubleType;
}
} else if (target is ComparisonOp) {
return boolType;
} else if (target is ClosureCall) {
return interfaceType(target.callee.returnType, node: node);
} else if (target is DirectSelector) {
final Member member = target.target;
final substituted =
substituteType(target.interface, memberType(member));
assert(substituted != const DynamicType());
return interfaceType(substituted);
} else if (target is VirtualSelector) {
final Member member = target.target;
final substituted =
substituteType(target.interface, memberType(member));
assert(substituted != const DynamicType());
return interfaceType(substituted);
} else if (target is InterfaceSelector) {
final member = lookupCache.lookupSelector(
target.interface.classNode, target.selector);
final substituted =
substituteType(target.interface, memberType(member));
assert(substituted != const DynamicType());
return interfaceType(substituted);
} else if (target is CallThroughFieldSelector) {
final Member member = target.getterTarget.target;
final substituted =
substituteType(target.getterTarget.interface, memberType(member));
assert(substituted != const DynamicType());
ensureIsFunctionType(substituted, 'call-through-field usage');
return interfaceType((substituted as FunctionType).returnType);
}
throw "Can't infer return type of ${target} for ${node}!";
} else if (node is StaticInvocation) {
final Member target = node.target;
if (target is Procedure) {
if (target.kind == ProcedureKind.Factory) {
return new CompileType.interface(
new InterfaceType(target.enclosingClass));
}
}
return interfaceType(node.target.function.returnType, node: node);
} else if (node is Not) {
return boolType;
} else if (node is ConditionalExpression) {
// TODO(vipunen) we need to assert that type of [node.otherwise]
// is the same as type of [node.then].
return typeOf(node.then);
} else if (node is ListLiteral) {
final InterfaceType type =
new InterfaceType(GrowableListClass, <DartType>[node.typeArgument]);
return new CompileType.concrete(type);
} else if (node is Let) {
return typeOf(node.variable.initializer);
}
throw "Can't infer type ${node} [${node.runtimeType}] "
"(${stringifyNode(node)})";
}
visitDirectPropertyGet(DirectPropertyGet node) {
super.visitDirectPropertyGet(node);
final receiverType = typeOf(node.receiver);
final Member member = node.target;
final DirectSelector target = new DirectSelector(
receiverType.type as InterfaceType,
new Selector(SelectorKind.Getter, member.name),
member);
d.targets[node] =
member is Procedure ? new TearOffSelector(target) : target;
}
visitPropertyGet(PropertyGet node) {
super.visitPropertyGet(node);
final receiverType = typeOf(node.receiver);
final ResolvedTarget target = receiverType.resolveSelector(
this, new Selector(SelectorKind.Getter, node.name));
if (target == null) {
throw 'failed to resolve property get ${node} -- ${stringifyNode(node)}';
}
d.targets[node] = target;
}
visitPropertySet(PropertySet node) {
super.visitPropertySet(node);
final receiverType = typeOf(node.receiver);
final target = receiverType.resolveSelector(
this, new Selector(SelectorKind.Setter, node.name));
if (target == null) {
throw 'failed to resolve property set ${node}';
}
d.targets[node] = target;
}
visitConstructorInvocation(ConstructorInvocation node) {
super.visitConstructorInvocation(node);
add(node.target, node.target.function);
}
visitMethodInvocation(MethodInvocation node) {
super.visitMethodInvocation(node);
final receiver = node.receiver;
final CompileType type = typeOf(receiver);
final target = type.resolveMethodInvocation(this, node);
if (target == null) {
throw 'failed to resolve target of the call ${node}.';
}
d.targets[node] = target;
if (target is DirectSelector) {
final member = target.target;
if (member is Procedure) {
add(member, member.function);
} else {
UNREACHABLE();
}
}
}
visitIsExpression(IsExpression node) {
super.visitIsExpression(node);
final DartType type = node.type;
if (type is InterfaceType) {
addInterfaceTestUsage(type);
}
}
static bool hasSimpleInitializer(Field field) {
final init = field.initializer;
return init == null ||
init is StringLiteral ||
init is IntLiteral ||
init is DoubleLiteral ||
init is NullLiteral ||
init is BoolLiteral;
}
// Mapping from all static fields that are accessed to their initializer.
// For fields with simple initializers contains [null] as an initializer.
final Map<Field, Procedure> staticFields = <Field, Procedure>{};
recordStaticField(Field field, {bool mayCallInitializer: true}) {
Procedure init;
if (!staticFields.containsKey(field)) {
// Fields with simple initializer will be initialized when
// statics object is constructed. For all other fields we
// create procedure with a synthetic name init:<field-name>
// that contains the initializer and rewrite field initializer
// to be an invocation of that procedure.
if (!hasSimpleInitializer(field)) {
init = new Procedure(
new Name("init:${field.name.name}"),
ProcedureKind.Method,
new FunctionNode(new ReturnStatement(field.initializer),
returnType: field.type),
isStatic: true);
field.initializer = new StaticInvocation(init, new Arguments.empty());
field.initializer.parent = field;
}
staticFields[field] = init;
} else {
init = staticFields[field];
}
if (mayCallInitializer && init != null) {
add(init, init.function);
}
}
@override
visitStaticSet(StaticSet node) {
super.visitStaticSet(node);
if (node.target is Field) {
final Field field = node.target;
recordStaticField(field, mayCallInitializer: false);
} else if (node.target is Procedure) {
final Procedure proc = node.target;
throw 'Unsupported target for static set: ${node.target}';
} else {
throw 'Unsupported target for static set: ${node.target}';
}
}
@override
visitStaticGet(StaticGet node) {
super.visitStaticGet(node);
if (node.target is Field) {
final Field field = node.target;
if (field.type is InterfaceType) {
final klass = (field.type as InterfaceType).classNode;
if (klass == coreTypes.doubleClass) {
fieldType[field] = NumericType.Double;
} else if (klass == coreTypes.intClass) {
fieldType[field] = NumericType.Int;
}
}
recordStaticField(field, mayCallInitializer: true);
} else if (node.target is Procedure) {
final Procedure proc = node.target;
add(proc, proc.function);
} else {
throw 'unsupported target for the static get ${node}';
}
}
visitStaticInvocation(StaticInvocation node) {
super.visitStaticInvocation(node);
add(node.target, node.target.function);
}
visitDirectMethodInvocation(DirectMethodInvocation node) {
super.visitDirectMethodInvocation(node);
add(node.target, node.target.function);
}
visitFunctionNode(FunctionNode node) {
if (node == d.func) throw 'unexpected';
add(d.m, node);
}
@override
visitStringConcatenation(StringConcatenation node) {
super.visitStringConcatenation(node);
final List<ResolvedTarget> conv = node.expressions.map((expr) {
final CompileType t = typeOf(expr);
if (t.isBottom) return t;
final DartType dt = t.type;
if (dt is InterfaceType) {
if (isStringClass(dt.classNode)) return SpecialTarget.Identity;
}
final toStringMethod = t.resolveSelector(
this, new Selector(SelectorKind.Method, new Name('toString')));
if (toStringMethod == null) {
throw 'Could not find "toString" method on $t (${stringifyNode(node)})';
}
return toStringMethod;
}).toList(growable: false);
d.targets[node] = conv;
markAllocated(ListClass);
add(StringInterpolate, StringInterpolate.function);
}
visitListLiteral(ListLiteral literal) {
super.visitListLiteral(literal);
markAllocated(GrowableListClass);
markAllocated(ListClass);
add(ListFromLiteral, ListFromLiteral.function);
}
bool isUntaggedType(DartType type) {
if (type is InterfaceType) {
return isUntaggedClass(type.classNode);
}
return false;
}
bool isUntaggedClass(Class klass) =>
isDoubleClass(klass) || isIntegerClass(klass);
bool isDoubleType(DartType type) =>
(type is InterfaceType) && isDoubleClass(type.classNode);
bool isIntType(DartType type) =>
(type is InterfaceType) && isIntegerClass(type.classNode);
bool isDoubleClass(Class klass) =>
klass == coreTypes.doubleClass || klass == DoubleClass;
bool isIntegerClass(Class klass) =>
klass == coreTypes.intClass || klass == SmiClass;
bool isStringClass(Class klass) =>
klass == coreTypes.stringClass ||
klass == StringBaseClass ||
klass == OneByteStringClass ||
klass == TwoByteStringClass;
DartType substituteType(InterfaceType iface, DartType memberType) {
final map = getFullSubstitutionMap(iface);
return map == null ? null : algebra.substitute(memberType, map);
}
Map<InterfaceType, Map<TypeParameter, DartType>> subsitutionMaps =
new Map<InterfaceType, Map<TypeParameter, DartType>>();
Map<TypeParameter, DartType> getFullSubstitutionMap(InterfaceType type) {
return subsitutionMaps.putIfAbsent(type, () {
final Map<TypeParameter, DartType> map = <TypeParameter, DartType>{};
Class currentClass = type.classNode;
List<DartType> currentArguments = type.typeArguments;
while (currentClass != null) {
if (currentArguments != null) {
assert(currentClass.typeParameters.length == currentArguments.length);
for (int i = 0; i < currentClass.typeParameters.length; ++i) {
final parameter = currentClass.typeParameters[i];
final typeValue = currentArguments[i];
map[parameter] = algebra.substitute(typeValue, map);
}
}
currentArguments = currentClass.supertype?.typeArguments;
currentClass = currentClass.supertype?.classNode;
}
return map;
});
}
}