blob: cec8abc4279d287f67ba10c2c508fcf986d1c203 [file] [log] [blame]
library kernel.transformations.vip_instantiate_generics;
import '../class_hierarchy.dart';
import '../core_types.dart';
import '../type_algebra.dart';
import '../type_environment.dart';
import '../visitor.dart';
import '../ast.dart';
import '../clone.dart';
// TODO: instantiate static invocations and factory methods too.
Program transformProgram(
CoreTypes coreTypes, ClassHierarchy hierarchy, Program program) {
new FixPointGenericInstantiator(coreTypes, program).processProgram();
return program;
}
enum TypeKind { Reference, Integer, Double }
class TypeKindAnalyzer {
final Program program;
final CoreTypes coreTypes;
Map<TypeParameter, TypeKind> substitution;
TypeKindAnalyzer(this.program, this.coreTypes);
TypeKind toTypeKind(DartType type, {TreeNode where}) {
if (type is InterfaceType) {
final classNode = type.classNode;
if (classNode == coreTypes.numClass) {
return TypeKind.Reference;
}
if (classNode == coreTypes.intClass) {
return TypeKind.Integer;
} else if (classNode == coreTypes.doubleClass) {
return TypeKind.Double;
} else {
return TypeKind.Reference;
}
} else if (type is FunctionType) {
return TypeKind.Reference;
} else if (type is BottomType || type is VoidType || type is DynamicType) {
return TypeKind.Reference;
} else if (type is TypeParameterType &&
substitution?.containsKey(type.parameter) == true) {
return substitution[type.parameter];
} else {
// report(program, where, "Can't establish whether ${type} is integer, double or reference");
throw "Can't establish whether ${type} is integer, double or reference";
}
}
}
class Generic<T> {
final T original;
final Set<TypeParameter> typeParameters;
final Set<InterfaceType> nestedTypes = new Set<InterfaceType>();
final Set<MethodInstantiation> invocations = new Set<MethodInstantiation>();
final Set<Instantiation> instantiations = new Set<Instantiation>();
Generic(this.original, this.typeParameters);
toString() {
if (original is Class) {
Class o = original as Class;
return "generic class ${o.enclosingLibrary.name}::${o.name}";
} else {
Procedure o = original as Procedure;
final parentName =
o.enclosingClass?.name ?? o.enclosingLibrary?.name ?? '';
return "generic proc ${parentName}::${o.name}";
}
}
void dump([String prefix = '']) {
print('${prefix}-- ${this}');
for (var type in nestedTypes) {
print('${prefix} type ${type}');
}
for (var invocation in invocations) {
print('${prefix} invoke ${invocation}');
}
}
}
class GenericClass extends Generic<Class> {
final List<GenericProcedure> nestedGenerics =
new List<GenericProcedure>();
GenericClass(Class original, Set<TypeParameter> typeParameters)
: super(original, typeParameters);
@override
void dump([String prefix = '']) {
super.dump(prefix);
for (var proc in nestedGenerics) {
proc.dump(prefix + ' ');
}
}
}
class GenericProcedure extends Generic<Procedure> {
final GenericClass parent;
GenericProcedure(Procedure original, Set<TypeParameter> typeParameters,
{this.parent})
: super(original, typeParameters);
}
class FixPointGenericInstantiator extends RecursiveVisitor {
final Program program;
final TypeKindAnalyzer typeKindAnalyzer;
final Set<Instantiation> instantiations = new Set<Instantiation>();
List<Instantiation> worklist = <Instantiation>[];
final Map<TreeNode, Generic> generics = <TreeNode, Generic>{};
final Map<String, List<GenericProcedure>> genericMethods =
<String, List<GenericProcedure>>{};
CoreTypes get coreTypes => typeKindAnalyzer.coreTypes;
FixPointGenericInstantiator(CoreTypes coreTypes, this.program)
: typeKindAnalyzer = new TypeKindAnalyzer(program, coreTypes) {
processProgram();
for (var generic in generics.values) {
generic.dump();
}
processWorklist();
print(instantiations);
}
void processWorklist() {
while (worklist.isNotEmpty) {
final current = worklist;
worklist = <Instantiation<Generic>>[];
for (var insn in current) {
if (insn.klass is GenericClass) {
instantiateClass(insn);
} else {
assert(insn.klass is String, "expected String, got ${insn.klass}");
instantiateMethods(insn);
}
}
}
}
Map<TypeParameter, DartType> makeSubstitution(
List<TypeParameter> typeParameters, List<TypeKind> kinds) {
final typeSubstitution = <TypeParameter, DartType>{};
for (var i = 0; i < typeParameters.length; i++) {
final param = typeParameters[i];
switch (kinds[i]) {
case TypeKind.Reference:
break;
case TypeKind.Integer:
typeSubstitution[param] = coreTypes.intClass.rawType;
break;
case TypeKind.Double:
typeSubstitution[param] = coreTypes.doubleClass.rawType;
break;
}
}
return typeSubstitution;
}
void instantiateMethods(Instantiation<String> insn) {
for (var generic in genericMethods[insn.klass] ?? const <Null>[]) {
generic.instantiations.add(insn);
final s = Substitution.fromMap(makeSubstitution(
generic.original.function.typeParameters, insn.types));
final hostS = [Substitution.empty];
if (generic.parent != null) {
hostS.addAll(generic.parent.instantiations.map(substitutionFromClassInstantiation));
}
for (var s2 in hostS) {
final s3 = Substitution.combine(s, s2);
for (var type in generic.nestedTypes) {
final newType = s3.substituteType(type);
if (type != newType) {
recordClassInstantiation(newType);
}
}
}
}
}
Substitution substitutionFromClassInstantiation(Instantiation<GenericClass> insn) => Substitution.fromMap(
makeSubstitution(insn.klass.original.typeParameters, insn.types));
Substitution Function(Instantiation) substitutionFromMethodInstantiation(GenericProcedure generic) {
return (Instantiation insn) => Substitution.fromMap(makeSubstitution(generic.original.function.typeParameters, insn.types));
}
void instantiateClass(Instantiation<GenericClass> insn) {
insn.klass.instantiations.add(insn);
final s = substitutionFromClassInstantiation(insn);
for (var type in insn.klass.nestedTypes) {
final newType = s.substituteType(type);
if (type != newType) {
recordClassInstantiation(newType);
}
}
for (var generic in insn.klass.nestedGenerics) {
for (var s2 in [Substitution.empty]..addAll(generic.instantiations.map(substitutionFromMethodInstantiation(generic)))) {
final s3 = Substitution.combine(s, s2);
for (var type in generic.nestedTypes) {
final newType = s3.substituteType(type);
if (type != newType) {
recordClassInstantiation(newType);
}
}
}
}
}
GenericClass currentClass;
GenericProcedure currentMethod;
static bool anyTypeParameters(List<DartType> types) =>
types.any((dt) => dt is TypeParameterType);
bool anyPrimitives(List<DartType> types) =>
types.any((dt) => typeKindAnalyzer.toTypeKind(dt) != TypeKind.Reference);
void handleInterfaceType(InterfaceType type, {TreeNode where}) {
if (anyTypeParameters(type.typeArguments)) {
final Generic current = (currentMethod != null &&
type.typeArguments.any((dt) =>
dt is TypeParameterType &&
currentMethod.typeParameters.contains(dt.parameter)))
? currentMethod
: currentClass;
current.nestedTypes.add(type);
} else if (anyPrimitives(type.typeArguments)) {
// Instantiate eagerly.
recordClassInstantiation(type);
}
}
void handleMethodInstantiation(MethodInstantiation method) {
if (anyTypeParameters(method.typeArguments)) {
final Generic current = (currentMethod != null &&
method.typeArguments.any((dt) =>
dt is TypeParameterType &&
currentMethod.typeParameters.contains(dt.parameter)))
? currentMethod
: currentClass;
current.invocations.add(method);
} else if (anyPrimitives(method.typeArguments)) {
// Instantiate eagerly.
recordMethodInstantiation(method);
}
}
void recordClassInstantiation(InterfaceType type) {
final generic = toGenericClass(type.classNode);
final insn = new Instantiation<GenericClass>(
generic, typesToKinds(type.typeArguments));
assert(insn.types.any((k) => k != TypeKind.Reference));
// Check if already instantiated.
if (!instantiations.add(insn)) {
return;
}
worklist.add(insn);
}
void recordMethodInstantiation(MethodInstantiation method) {
final insn = new Instantiation<String>(
method.name, typesToKinds(method.typeArguments));
assert(insn.types.any((k) => k != TypeKind.Reference));
if (!instantiations.add(insn)) {
return;
}
worklist.add(insn);
}
GenericClass toGenericClass(Class klass) {
return generics.putIfAbsent(klass,
() => new GenericClass(klass, new Set.from(klass.typeParameters)));
}
void processClass(Class klass) {
if (klass.typeParameters.isNotEmpty) {
currentClass = toGenericClass(klass);
}
if (klass.supertype != null) {
handleInterfaceType(klass.supertype.asInterfaceType, where: klass);
}
for (var st in klass.implementedTypes) {
handleInterfaceType(st.asInterfaceType, where: klass);
}
for (var constructor in klass.constructors) {
constructor.accept(this);
}
for (var procedure in klass.procedures) {
if (procedure.function.typeParameters.isNotEmpty) {
currentMethod = generics.putIfAbsent(
procedure,
() => new GenericProcedure(
procedure, new Set.from(procedure.function.typeParameters),
parent: !procedure.isStatic ? currentClass : null));
if (!procedure.isStatic) {
genericMethods
.putIfAbsent(procedure.name.name, () => <GenericProcedure>[])
.add(currentMethod);
if (currentClass != null) {
currentClass.nestedGenerics.add(currentMethod);
}
}
}
procedure.accept(this);
currentMethod = null;
}
klass.fields.forEach((f) => f.accept(this));
currentClass = null;
}
void processProgram() {
for (var library in program.libraries) {
library.classes.toList(growable: false).forEach(processClass);
for (var procedure in library.procedures) {
if (procedure.function.typeParameters.isNotEmpty) {
currentMethod = generics.putIfAbsent(
procedure,
() => new GenericProcedure(
procedure, new Set.from(procedure.function.typeParameters)));
}
procedure.accept(this);
currentMethod = null;
}
for (var field in library.fields) {
field.accept(this);
}
}
}
@override
visitFunctionNode(FunctionNode node) {
if (node.typeParameters.isNotEmpty && node.parent is! Member) {
throw "Generic closures are currently unsupported";
}
}
@override
visitConstructorInvocation(ConstructorInvocation node) {
final List<DartType> types = node.arguments.types;
if (types.isNotEmpty) {
final Class klass = node.target.enclosingClass;
handleInterfaceType(new InterfaceType(klass, types.toList()),
where: node);
}
}
@override
visitMethodInvocation(MethodInvocation node) {
final List<DartType> types = node.arguments.types;
if (types.isNotEmpty) {
handleMethodInstantiation(new MethodInstantiation(node.name.name, types));
}
}
List<TypeKind> typesToKinds(List<DartType> types,
{ignoreTypeParameters: true}) =>
types.map((t) {
return (ignoreTypeParameters && t is TypeParameterType)
? TypeKind.Reference
: typeKindAnalyzer.toTypeKind(t);
}).toList(growable: false);
static bool containsPrimitives(List<TypeKind> kinds) =>
kinds.any((k) => k != TypeKind.Reference);
}
class GenericInstantiator extends RecursiveVisitor {
final Program program;
final TypeKindAnalyzer typeKindAnalyzer;
CoreTypes get coreTypes => typeKindAnalyzer.coreTypes;
GenericInstantiator(CoreTypes coreTypes, this.program)
: typeKindAnalyzer = new TypeKindAnalyzer(program, coreTypes) {
processProgram();
}
void processClass(Class class_) {
for (var constructor in class_.constructors) {
constructor.accept(this);
}
for (var procedure in class_.procedures) {
procedure.accept(this);
}
class_.fields.forEach((f) => f.accept(this));
}
void processProgram() {
for (var library in program.libraries) {
library.classes.toList(growable: false).forEach(processClass);
for (var procedure in library.procedures) {
procedure.accept(this);
}
for (var field in library.fields) {
field.accept(this);
}
}
//drainWorklist();
}
final Set<MethodInvocation> instantiated = new Set<MethodInvocation>();
@override
visitStaticInvocation(StaticInvocation node) {
final types = node.arguments.types;
if (types.isNotEmpty) {
final kinds = typesToKinds(types, ignoreTypeParameters: true);
if (containsPrimitives(kinds)) {
final suffix = new List.generate(kinds.length, (idx) {
switch (kinds[idx]) {
case TypeKind.Reference:
return 'R';
case TypeKind.Double:
return 'D';
case TypeKind.Integer:
return 'I';
}
}).join();
print('>>> static call ${node.name.name}%T(${suffix})');
//node.name = new Name('${node.name.name}%T(${suffix})', node.name.library);
// instantiated.add(node);
}
}
}
@override
visitMethodInvocation(MethodInvocation node) {
final types = node.arguments.types;
if (types.isNotEmpty) {
// Proceed to instantiate.
final kinds = typesToKinds(types, ignoreTypeParameters: true);
if (containsPrimitives(kinds)) {
final suffix = new List.generate(kinds.length, (idx) {
switch (kinds[idx]) {
case TypeKind.Reference:
return 'R';
case TypeKind.Double:
return 'D';
case TypeKind.Integer:
return 'I';
}
}).join();
print('>>> method call ${node.name.name}%T(${suffix})');
node.name =
new Name('${node.name.name}%T(${suffix})', node.name.library);
instantiated.add(node);
}
}
}
@override
visitDirectMethodInvocation(DirectMethodInvocation node) {}
List<TypeKind> typesToKinds(List<DartType> types,
{ignoreTypeParameters: true}) =>
types.map((t) {
return (ignoreTypeParameters && t is TypeParameterType)
? TypeKind.Reference
: typeKindAnalyzer.toTypeKind(t);
}).toList(growable: false);
static bool containsPrimitives(List<TypeKind> kinds) =>
kinds.any((k) => k != TypeKind.Reference);
@override
visitConstructorInvocation(ConstructorInvocation node) {
final List<DartType> types = node.arguments.types;
if (types.isNotEmpty) {
final Class klass = node.target.enclosingClass;
final kinds = typesToKinds(types, ignoreTypeParameters: true);
final Class clone = instantiate(klass, kinds);
if (!identical(clone, klass)) {
final name = node.target.name;
final ctor = clone.constructors.firstWhere((ctor) => ctor.name == name);
node.target = ctor;
var j = 0;
for (var i = 0; i < types.length; i++) {
if (kinds[i] == TypeKind.Reference) {
types[j++] = types[i];
}
}
types.length = j;
}
}
}
final Set<Instantiation> insns = new Set<Instantiation>();
List<Instantiation> insnsWorklist = new List<Instantiation>();
static List<DartType> removePrimitives(
List<DartType> types, List<TypeKind> kinds) {
List<DartType> result = <DartType>[];
for (var i = 0; i < types.length; i++) {
if (kinds[i] == TypeKind.Reference) result.add(types[i]);
}
return result;
}
InterfaceType instantiateInterfaceType(InterfaceType supertype) {
final kinds = typesToKinds(supertype.typeArguments);
final klass = instantiate(supertype.classNode, kinds);
return new InterfaceType(
klass, removePrimitives(supertype.typeArguments, kinds));
}
Class instantiate(Class klass, List<TypeKind> types) {
final insn = new Instantiation(klass, types);
if (insns.add(insn)) {
if (!containsPrimitives(insn.types)) {
insn.node = insn.klass;
return insn.node;
}
print('Instantiating ${insn.klass} with ${insn.types}');
final orig = insn.klass;
final suffix = insn.types.map((t) {
switch (t) {
case TypeKind.Reference:
return "R";
case TypeKind.Double:
return "D";
case TypeKind.Integer:
return "I";
}
}).join('');
Map<TypeParameter, DartType> typeSubstitution =
<TypeParameter, DartType>{};
for (var i = 0; i < orig.typeParameters.length; i++) {
final param = orig.typeParameters[i];
final kind = insn.types[i];
switch (kind) {
case TypeKind.Reference:
break;
case TypeKind.Integer:
typeSubstitution[param] = coreTypes.intClass.rawType;
break;
case TypeKind.Double:
typeSubstitution[param] = coreTypes.doubleClass.rawType;
break;
}
}
var supertype = Substitution
.fromMap(typeSubstitution)
.substituteSupertype(klass.supertype);
if (supertype != klass.supertype) {}
final cloner = new CloneVisitor(
typeSubstitution: typeSubstitution,
classRenamer: (Class node) {
if (identical(node, orig)) {
return "${orig.name}%${suffix}";
}
return node.name;
});
final clone = cloner.visitClass(orig);
orig.enclosingLibrary.addClass(clone);
insn.node = clone;
insnsWorklist.add(insn);
return insn.node;
} else {
return insns.lookup(insn).node;
}
}
void drainWorklist() {
while (insnsWorklist.isNotEmpty) {
final items = insnsWorklist;
insnsWorklist = new List<Instantiation>();
for (var insn in items) {
processClass(insn.node);
}
}
}
}
class Instantiation<ClassT> {
final ClassT klass;
final List<TypeKind> types;
ClassT node;
Instantiation(this.klass, this.types);
bool operator ==(other) {
return other is Instantiation<ClassT> &&
this.klass == other.klass &&
_listEquals(this.types, other.types);
}
int get hashCode => klass.hashCode ^ _listHash(types);
toString() => 'Instantiation(${klass} with ${types})';
}
class MethodInstantiation {
final String name;
final List<DartType> typeArguments;
MethodInstantiation(this.name, this.typeArguments);
@override
bool operator ==(other) {
return other is MethodInstantiation &&
other.name == this.name &&
_listEquals(other.typeArguments, this.typeArguments);
}
@override
int get hashCode => name.hashCode ^ _listHash(typeArguments);
}
bool _listEquals<T>(List<T> a, List<T> b) {
if (a.length != b.length) return false;
for (var i = 0; i < a.length; i++) {
if (a[i] != b[i]) return false;
}
return true;
}
int _listHash<T>(List<T> a) {
int result = a.length;
for (var i = 0; i < a.length; i++) {
result |= a[i].hashCode;
}
return result;
}