pkg/kernel/lib/transformations/vip_type_check.dart

// 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}');
  }
}