blob: 819b5fa34ce5173239f92b73491d7e3403b44085 [file] [log] [blame]
// 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 kernel.transformations.vip_type_check;
import 'dart:io';
import '../kernel.dart';
import '../ast.dart';
import '../core_types.dart';
import '../type_algebra.dart';
import '../type_checker.dart';
import '../class_hierarchy.dart';
import '../text/ast_to_text.dart';
import '../clone.dart';
Program transformProgram(Program program) {
try {
program.accept(new FactoryReturnTypeFixer());
new GenericInstantiator(program);
print(programToString(program));
new TypeChecker1(program).checkProgram(program);
return program;
} on TypeCheckFail catch (e) {
exit(-1);
}
// return program.accept(new TypeChecker());
}
int findFileOffset(TreeNode context) {
while (context != null && context.fileOffset == TreeNode.noOffset) {
context = context.parent;
}
return context?.fileOffset ?? TreeNode.noOffset;
}
void report(Program program, TreeNode where, String message) {
var context = where;
while (context is! Member) {
context = context.parent;
}
final fileOffset = findFileOffset(where);
if (fileOffset != TreeNode.noOffset) {
final fileUri = (context is Procedure || context is Field)
? context.fileUri
: (context.enclosingClass ?? context.enclosingLibrary).fileUri;
var program = context.enclosingProgram;
var source = program.uriToSource[fileUri];
var location = program.getLocation(fileUri, fileOffset);
var lineStart = source.lineStarts[location.line - 1];
var lineEnd = (location.line < source.lineStarts.length)
? source.lineStarts[location.line]
: (source.source.length - 1);
if (lineStart < source.source.length &&
lineEnd < source.source.length &&
lineStart < lineEnd) {
print("\nIn ${fileUri}:${location.line}\n");
print(
new String.fromCharCodes(source.source.getRange(lineStart, lineEnd)));
print("");
}
}
if (context is! Field) {
context = context.function;
}
var name = "", body = context;
if (context is FunctionNode) {
final parent = context.parent;
if (parent is Member) {
name = "${parent.parent.name}::${parent.name.name}";
} else if (parent is FunctionDeclaration) {
name = parent.variable.name;
} else {
name = "anonymous function";
}
body = context.body;
} else {
final field = context as Field;
name = "field initializer for ${field.parent}.${field.name}";
}
var host = "";
print('''
In ${name}:
${message}
${debugNodeToStringX(body.parent.parent, where)}
''');
}
class GenericInstantiator extends RecursiveVisitor {
final Program program;
final TypeKindAnalyzer typeKindAnalyzer;
CoreTypes get coreTypes => typeKindAnalyzer.coreTypes;
GenericInstantiator(this.program)
: typeKindAnalyzer = new TypeKindAnalyzer(program) {
processProgram();
}
void processProgram() {
for (var library in program.libraries) {
for (var class_ in library.classes.toList(growable: false)) {
if (class_.typeParameters.isNotEmpty) {
continue;
}
for (var constructor in class_.constructors) {
if (constructor.function.typeParameters.isNotEmpty) {
continue;
}
constructor.accept(this);
}
for (var procedure in class_.procedures) {
if (procedure.function.typeParameters.isNotEmpty) {
continue;
}
procedure.accept(this);
}
class_.fields.forEach((f) => f.accept(this));
}
for (var procedure in library.procedures) {
procedure.accept(this);
}
for (var field in library.fields) {
field.accept(this);
}
}
}
@override
visitConstructorInvocation(ConstructorInvocation node) {
final List<DartType> types = node.arguments.types;
if (types.isNotEmpty) {
final Class klass = node.target.enclosingClass;
final Class clone =
instantiate(klass, types.map((t) => typeKindAnalyzer.toTypeKind(t, where: node)).toList());
if (!identical(clone, klass)) {
final name = node.target.name;
final ctor = clone.constructors
.firstWhere((ctor) => ctor.name == node.target.name);
node.target = ctor;
}
}
}
final Set<Instantiation> insns = new Set<Instantiation>();
List<Instantiation> insnsWorklist = new List<Instantiation>();
Class instantiate(Class klass, List<TypeKind> types) {
final insn = new Instantiation(klass, types);
if (insns.add(insn)) {
print('Instantiating ${insn.klass} with ${insn.types}');
if (!insn.types.every((t) => t == TypeKind.Reference)) {
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;
}
}
final cloner = new CloneVisitor(
typeSubstitution: typeSubstitution,
renamer: (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;
} else {
insn.node = insn.klass;
}
insnsWorklist.add(insn);
return insn.klass;
} else {
return insns.lookup(insn).klass;
}
}
void drainWorklist(TypeCheckingVisitor visitor) {
while (insnsWorklist.isNotEmpty) {
final items = insnsWorklist;
insnsWorklist = new List<Instantiation>();
for (var insn in items) {
typeKindAnalyzer.substitution =
new Map<TypeParameter, TypeKind>.fromIterables(
insn.klass.typeParameters, insn.types);
insn.klass.accept(this);
typeKindAnalyzer.substitution = null;
}
}
}
}
class FactoryReturnTypeFixer extends RecursiveVisitor {
@override
void visitProcedure(Procedure proc) {
if (proc.isFactory && proc.function.returnType == const DynamicType()) {
final function = proc.function;
final host = proc.parent as Class;
assert(function.typeParameters.length == host.typeParameters.length);
function.returnType = new InterfaceType(
host,
function.typeParameters
.map((p) => new TypeParameterType(p))
.toList());
}
}
}
enum Assignable { Ok, Check, Fail }
class TypeCheckFail {
final message;
TypeCheckFail(this.message);
}
class TypeKindAnalyzer {
final Program program;
final CoreTypes coreTypes;
final Class DoubleClass;
final Class SmiClass;
Map<TypeParameter, TypeKind> substitution;
TypeKindAnalyzer(Program program) : this._(program, new CoreTypes(program));
TypeKindAnalyzer._(this.program, this.coreTypes)
: DoubleClass = coreTypes.getClass('dart:core', '_Double'),
SmiClass = coreTypes.getClass('dart:core', '_Integer');
TypeKind toTypeKind(DartType type, {TreeNode where}) {
if (type is InterfaceType) {
final classNode = type.classNode;
if (classNode == coreTypes.numClass) {
throw "num type is forbiden";
}
if (classNode == coreTypes.intClass || classNode == SmiClass) {
return TypeKind.Integer;
} else if (classNode == coreTypes.doubleClass ||
classNode == DoubleClass) {
return TypeKind.Double;
} else {
return TypeKind.Reference;
}
} else if (type is FunctionType) {
return TypeKind.Reference;
} else if (type is BottomType) {
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 TypeChecker1 extends TypeChecker {
final Class DoubleClass;
final Class SmiClass;
TypeChecker1(Program program)
: this._(new CoreTypes(program), new ClassHierarchy(program));
TypeChecker1._(CoreTypes coreTypes, ClassHierarchy hierarchy)
: DoubleClass = coreTypes.getClass('dart:core', '_Double'),
SmiClass = coreTypes.getClass('dart:core', '_Integer'),
super(coreTypes, hierarchy);
TypeKind toTypeKind(TreeNode where, DartType type) {
if (type is InterfaceType) {
final classNode = type.classNode;
if (classNode == coreTypes.numClass) {
fail(where, "num type is forbiden");
}
if (classNode == coreTypes.intClass || classNode == SmiClass) {
return TypeKind.Integer;
} else if (classNode == coreTypes.doubleClass ||
classNode == DoubleClass) {
return TypeKind.Double;
} else {
return TypeKind.Reference;
}
} else if (type is FunctionType) {
return TypeKind.Reference;
} else if (type is BottomType) {
return TypeKind.Reference;
} else if (type is TypeParameterType &&
mapping.containsKey(type.parameter)) {
return mapping[type.parameter];
} else {
fail(where,
"Can't establish whether ${type} is integer, double or reference");
}
}
bool isInteger(DartType type) => toTypeKind(null, type) == TypeKind.Integer;
bool isDouble(DartType type) => toTypeKind(null, type) == TypeKind.Double;
bool isNumeric(DartType type) => toTypeKind(null, type) != TypeKind.Reference;
Assignable isAssignable(TreeNode where, DartType from, DartType to) {
if (to == const DynamicType()) {
fail(where, "Destination has type dynamic.");
}
if (from == const DynamicType()) {
fail(where, "Source expression has type dynamic");
}
if (from == to) {
return Assignable.Ok;
}
final fromKind = toTypeKind(where, from);
final toKind = toTypeKind(where, to);
if (fromKind != toKind) {
return Assignable.Fail;
}
if (fromKind == TypeKind.Reference) {
if (environment.isSubtypeOf(from, to)) {
return Assignable.Ok;
} else if (environment.isSubtypeOf(to, from)) {
return Assignable.Check;
} else {
return Assignable.Fail;
}
}
return Assignable.Ok;
}
/// Check that [from] is a subtype of [to].
///
/// [where] is an AST node indicating roughly where the check is required.
void checkAssignable(TreeNode where, DartType from, DartType to) {
switch (isAssignable(where, from, to)) {
case Assignable.Fail:
case Assignable.Check:
fail(where, '${from} is not assignable to ${to}');
break;
case Assignable.Ok:
break;
}
}
Expression checkAndDowncastExpression(
Expression expression, DartType from, DartType to) {
if (expression.parent is Field &&
expression.parent.initializer == expression &&
expression is NullLiteral) {
switch (toTypeKind(expression, to)) {
case TypeKind.Integer:
return new IntLiteral(0);
case TypeKind.Double:
return new DoubleLiteral(0.0);
case TypeKind.Reference:
return expression;
}
}
switch (isAssignable(expression, from, to)) {
case Assignable.Ok:
return expression;
case Assignable.Check:
return new AsExpression(expression, to);
case Assignable.Fail:
fail(expression, '${from} is not assignable to ${to}');
return expression;
}
}
List<InterfaceType> expand(List<InterfaceType> l) {
while (true) {
final t = l.last;
final sup = t.classNode.supertype;
if (sup == null) {
break;
}
final sub = Substitution.fromInterfaceType(t);
l.add(sub.substituteType(sup.asInterfaceType));
}
return l;
}
DartType leastUpperBound(TreeNode where, DartType a, DartType b) {
if (a == b) {
return a;
} else if (environment.isSubtypeOf(a, b)) {
return b;
} else if (environment.isSubtypeOf(b, a)) {
return a;
} else {
if (a is InterfaceType && b is InterfaceType) {
final List<InterfaceType> aSupers = expand([a]);
final List<InterfaceType> bSupers = expand([b]);
if (aSupers.last == bSupers.last) {
InterfaceType lub = aSupers.last;
for (var i = aSupers.length - 2, j = bSupers.length - 2;
0 <= i && 0 <= j;
--i, --j) {
if (aSupers[i] == bSupers[j]) {
lub = aSupers[i];
} else {
break;
}
}
return lub;
}
}
fail(where, "Can't compute least-upper-bound of ${a} and ${b}");
return const BottomType();
}
}
static int findFileOffset(TreeNode context) {
while (context != null && context.fileOffset == TreeNode.noOffset) {
context = context.parent;
}
return context?.fileOffset ?? TreeNode.noOffset;
}
void fail(TreeNode where, String message) {
var context = where;
while (context is! Member) {
context = context.parent;
}
final fileOffset = findFileOffset(where);
if (fileOffset != TreeNode.noOffset) {
final fileUri = (context is Procedure || context is Field)
? context.fileUri
: (context.enclosingClass ?? context.enclosingLibrary).fileUri;
var program = context.enclosingProgram;
var source = program.uriToSource[fileUri];
var location = program.getLocation(fileUri, fileOffset);
var lineStart = source.lineStarts[location.line - 1];
var lineEnd = (location.line < source.lineStarts.length)
? source.lineStarts[location.line]
: (source.source.length - 1);
if (lineStart < source.source.length &&
lineEnd < source.source.length &&
lineStart < lineEnd) {
print("\nIn ${fileUri}:${location.line}\n");
print(new String.fromCharCodes(
source.source.getRange(lineStart, lineEnd)));
print("");
}
}
if (context is! Field) {
context = context.function;
}
var name = "", body = context;
if (context is FunctionNode) {
final parent = context.parent;
if (parent is Member) {
name = "${parent.parent.name}::${parent.name.name}";
} else if (parent is FunctionDeclaration) {
name = parent.variable.name;
} else {
name = "anonymous function";
}
body = context.body;
} else {
final field = context as Field;
name = "field initializer for ${field.parent}.${field.name}";
}
var host = "";
print('''
In ${name}:
${message}
${debugNodeToStringX(body.parent.parent, where)}
''');
throw new TypeCheckFail('FAIL AT ${where}: ${message}');
}
}