fix #27259, implement covariance checking for strong mode and DDC

pkg/analyzer/lib/src/task/strong/checker.dart

 // Copyright (c) 2015, 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.
 
 // TODO(jmesserly): this was ported from package:dev_compiler, and needs to be
 // refactored to fit into analyzer.
 library analyzer.src.task.strong.checker;
 
+import 'dart:collection';
 import 'package:analyzer/analyzer.dart';
 import 'package:analyzer/dart/ast/ast.dart';
 import 'package:analyzer/dart/ast/standard_resolution_map.dart';
 import 'package:analyzer/dart/ast/token.dart' show TokenType;
 import 'package:analyzer/dart/ast/token.dart';
 import 'package:analyzer/dart/ast/visitor.dart';
 import 'package:analyzer/dart/element/element.dart';
 import 'package:analyzer/dart/element/type.dart';
 import 'package:analyzer/source/error_processor.dart' show ErrorProcessor;
 import 'package:analyzer/src/dart/element/element.dart';
+import 'package:analyzer/src/dart/element/member.dart';
 import 'package:analyzer/src/dart/element/type.dart';
 import 'package:analyzer/src/error/codes.dart' show StrongModeCode;
 import 'package:analyzer/src/generated/engine.dart' show AnalysisOptionsImpl;
 import 'package:analyzer/src/generated/resolver.dart' show TypeProvider;
 import 'package:analyzer/src/generated/type_system.dart';
 import 'package:analyzer/src/summary/idl.dart';
 
 import 'ast_properties.dart';
 
 /// Given an [expression] and a corresponding [typeSystem] and [typeProvider],
@@ skipping 15 matching lines @@
     return typeSystem.functionTypeToConcreteType(type);
   }
   return type;
 }
 
 bool hasStrictArrow(Expression expression) {
   var element = _getKnownElement(expression);
   return element is FunctionElement || element is MethodElement;
 }
 
+/// Given a generic class [element] find its covariant upper bound, using
+/// the type system [rules].
+///
+/// Unlike [TypeSystem.instantiateToBounds], this will change `dynamic` into
+/// `Object` to work around an issue with fuzzy arrows.
+InterfaceType _getCovariantUpperBound(TypeSystem rules, ClassElement element) {
+  var upperBound = rules.instantiateToBounds(element.type) as InterfaceType;
+  var typeArgs = upperBound.typeArguments;
+  // TODO(jmesserly): remove this. It is a workaround for fuzzy arrows.
+  // To prevent extra checks due to fuzzy arrows, we need to instantiate with
+  // `Object` rather than `dynamic`. Consider a case like:
+  //
+  //     class C<T> {
+  //       void forEach(f(T t)) {}
+  //     }
+  //
+  // If we try `(dynamic) ~> void <: (T) ~> void` with fuzzy arrows, we will
+  // treat `dynamic` as `bottom` and get `(bottom) -> void <: (T) -> void`
+  // which indicates that a check is required on the parameter `f`. This check
+  // is not sufficient when `T` is `dynamic`, however, because calling a
+  // function with a fuzzy arrow type is not safe and requires a dynamic call.
+  // See: https://github.com/dart-lang/sdk/issues/29295
+  //
+  // For all other values of T, the check is unnecessary: it is sound to pass
+  // a function that accepts any Object.
+  if (typeArgs.any((t) => t.isDynamic)) {
+    var newTypeArgs = typeArgs
+        .map((t) => t.isDynamic ? rules.typeProvider.objectType : t)
+        .toList();
+    upperBound = element.type.instantiate(newTypeArgs);
+  }
+  return upperBound;
+}
+
 DartType _elementType(Element e) {
   if (e == null) {
     // Malformed code - just return dynamic.
     return DynamicTypeImpl.instance;
   }
   return (e as dynamic).type;
 }
 
 Element _getKnownElement(Expression expression) {
   if (expression is ParenthesizedExpression) {
@@ skipping 32 matching lines @@
     field = setter.variable;
   } else {
     return null;
   }
   if (field.isSynthetic) return null;
   return field;
 }
 
 /// Looks up the declaration that matches [member] in [type] and returns it's
 /// declared type.
-FunctionType _getMemberType(InterfaceType type, ExecutableElement member) =>
-    _memberTypeGetter(member)(type);
-
-_MemberTypeGetter _memberTypeGetter(ExecutableElement member) {
-  String memberName = member.name;
-  final isGetter = member is PropertyAccessorElement && member.isGetter;
-  final isSetter = member is PropertyAccessorElement && member.isSetter;
-
-  FunctionType f(InterfaceType type) {
-    ExecutableElement baseMethod;
-
-    if (member.isPrivate) {
-      var subtypeLibrary = member.library;
-      var baseLibrary = type.element.library;
-      if (baseLibrary != subtypeLibrary) {
-        return null;
-      }
-    }
-
-    try {
-      if (isGetter) {
-        assert(!isSetter);
-        // Look for getter or field.
-        baseMethod = type.getGetter(memberName);
-      } else if (isSetter) {
-        baseMethod = type.getSetter(memberName);
-      } else {
-        baseMethod = type.getMethod(memberName);
-      }
-    } catch (e) {
-      // TODO(sigmund): remove this try-catch block (see issue #48).
-    }
-    if (baseMethod == null || baseMethod.isStatic) return null;
-    return baseMethod.type;
+FunctionType _getMemberType(InterfaceType type, ExecutableElement member) {
+  if (member.isPrivate && type.element.library != member.library) {
+    return null;
   }
 
-  return f;
+  var name = member.name;
+  var baseMember = member is PropertyAccessorElement
+      ? (member.isGetter ? type.getGetter(name) : type.getSetter(name))
+      : type.getMethod(name);
+  if (baseMember == null || baseMember.isStatic) return null;
+  return baseMember.type;
 }
 
-typedef FunctionType _MemberTypeGetter(InterfaceType type);
-
 /// Checks the body of functions and properties.
 class CodeChecker extends RecursiveAstVisitor {
   final StrongTypeSystemImpl rules;
   final TypeProvider typeProvider;
   final AnalysisErrorListener reporter;
   final AnalysisOptionsImpl _options;
   _OverrideChecker _overrideChecker;
 
   bool _failure = false;
   bool _hasImplicitCasts;
+  ClassElement _currentClass;
+  HashSet<ExecutableElement> _covariantPrivateMembers;
 
   CodeChecker(TypeProvider typeProvider, StrongTypeSystemImpl rules,
       AnalysisErrorListener reporter, this._options)
       : typeProvider = typeProvider,
         rules = rules,
         reporter = reporter {
     _overrideChecker = new _OverrideChecker(this);
   }
 
   bool get failure => _failure;
@@ skipping 27 matching lines @@
       _checkImplicitCast(expr, type);
     }
   }
 
   /// Analyzer checks boolean conversions, but we need to check too, because
   /// it uses the default assignability rules that allow `dynamic` and `Object`
   /// to be assigned to bool with no message.
   void checkBoolean(Expression expr) =>
       checkAssignment(expr, typeProvider.boolType);
 
-  void checkFunctionApplication(InvocationExpression node) {
+  void _checkFunctionApplication(InvocationExpression node) {
     var ft = _getTypeAsCaller(node);
 
     if (_isDynamicCall(node, ft)) {
       // If f is Function and this is a method invocation, we should have
       // gotten an analyzer error, so no need to issue another error.
       _recordDynamicInvoke(node, node.function);
     } else {
       checkArgumentList(node.argumentList, ft);
     }
   }
@@ skipping 71 matching lines @@
         default:
           assert(false);
       }
     }
     node.visitChildren(this);
   }
 
   @override
   void visitClassDeclaration(ClassDeclaration node) {
     _overrideChecker.check(node);
-    super.visitClassDeclaration(node);
+    assert(_currentClass == null);
+    _currentClass = node.element;
+    node.members.accept(this);
+    _currentClass = null;
   }
 
   @override
   void visitClassTypeAlias(ClassTypeAlias node) {
     _overrideChecker.check(node);
     super.visitClassTypeAlias(node);
   }
 
   @override
   void visitComment(Comment node) {
     // skip, no need to do typechecking inside comments (they may contain
     // comment references which would require resolution).
   }
 
   @override
   void visitCompilationUnit(CompilationUnit node) {
     _hasImplicitCasts = false;
+    _covariantPrivateMembers = new HashSet();
     node.visitChildren(this);
     setHasImplicitCasts(node, _hasImplicitCasts);
+    setCovariantPrivateMembers(node, _covariantPrivateMembers);
   }
 
   @override
   void visitConditionalExpression(ConditionalExpression node) {
     checkBoolean(node.condition);
     node.visitChildren(this);
   }
 
   /// Check constructor declaration to ensure correct super call placement.
   @override
@@ skipping 105 matching lines @@
   @override
   void visitForStatement(ForStatement node) {
     if (node.condition != null) {
       checkBoolean(node.condition);
     }
     node.visitChildren(this);
   }
 
   @override
   void visitFunctionExpressionInvocation(FunctionExpressionInvocation node) {
-    checkFunctionApplication(node);
+    _checkFunctionApplication(node);
     node.visitChildren(this);
   }
 
   @override
   void visitIfStatement(IfStatement node) {
     checkBoolean(node.condition);
     node.visitChildren(this);
   }
 
   @override
@@ skipping 106 matching lines @@
       //
       // ... from case like:
       //
       //     SomeType s;
       //     s.someDynamicField(...); // static get, followed by dynamic call.
       //
       // The first case is handled here, the second case is handled below when
       // we call [checkFunctionApplication].
       setIsDynamicInvoke(node.methodName, true);
     } else {
-      checkFunctionApplication(node);
+      _checkImplicitCovarianceCast(node, target, element);
+      _checkFunctionApplication(node);
     }
-    node.visitChildren(this);
+    // Don't visit methodName, we already checked things related to the call.
+    node.target?.accept(this);
+    node.typeArguments?.accept(this);
+    node.argumentList?.accept(this);
   }
 
   @override
   void visitPostfixExpression(PostfixExpression node) {
     _checkUnary(node.operand, node.operator, node.staticElement);
     node.visitChildren(this);
   }
 
   @override
   void visitPrefixedIdentifier(PrefixedIdentifier node) {
@@ skipping 28 matching lines @@
     node.visitChildren(this);
   }
 
   @override
   void visitReturnStatement(ReturnStatement node) {
     _checkReturnOrYield(node.expression, node);
     node.visitChildren(this);
   }
 
   @override
+  void visitSimpleIdentifier(SimpleIdentifier node) {
+    // Only visit SimpleIdentifiers when we're in a class, and at the
+    // class declaration level itself.
+    if (_currentClass != null && node.parent is! ClassMember) {

[vsm, 2017/07/05 22:57:34]

Does this check match the comment?  I.e., what if the node's grandparent is a
ClassMember?

[Jennifer Messerly, 2017/07/06 01:11:10]

sorry, it should say "not at the class declaration level" ... the idea was to
not visit the MethodDeclaration's own SimpleIdentifier, which has a reference to
the MethodElement (and same for fields).

... however, I realized that this code here is not necessary! "Implicit this"
references are an exact type -- if we're in `class C<T>`, we know for `this` has
type C<T>, and not some `C<S>` where `S <: T` (of course, `this` can be some
type `D` where `D <: C<T>`, but that's safe, we're worried only about the `C<S>`
case.

I already applied that optimization when we track private members, but I
completely forgot about it for the return type checks. Oops :)

+      _checkImplicitCovarianceCast(node, null, node.staticElement);
+    }
+  }
+
+  @override
   void visitSuperConstructorInvocation(SuperConstructorInvocation node) {
     var element = node.staticElement;
     if (element != null) {
       var type = resolutionMap.staticElementForConstructorReference(node).type;
       checkArgumentList(node.argumentList, type);
     }
     node.visitChildren(this);
   }
 
   @override
@@ skipping 28 matching lines @@
           variableElement.kind == ElementKind.FIELD) {
         _validateTopLevelInitializer(variableElement.name, node.initializer);
       }
     }
     return super.visitVariableDeclaration(node);
   }
 
   @override
   void visitVariableDeclarationList(VariableDeclarationList node) {
     TypeAnnotation type = node.type;
-    if (type == null) {
-      // No checks are needed when the type is var. Although internally the
-      // typing rules may have inferred a more precise type for the variable
-      // based on the initializer.
-    } else {
-      for (VariableDeclaration variable in node.variables) {
-        var initializer = variable.initializer;
-        if (initializer != null) {
+
+    for (VariableDeclaration variable in node.variables) {
+      var initializer = variable.initializer;
+      if (initializer != null) {
+        if (type != null) {
           checkAssignment(initializer, type.type);
         }
       }
     }
+
     node.visitChildren(this);
   }
 
   @override
   void visitWhileStatement(WhileStatement node) {
     checkBoolean(node.condition);
     node.visitChildren(this);
   }
 
   @override
@@ skipping 33 matching lines @@
       // back to it. So these two implicit casts are equivalent:
       //
       //     y = /*implicit cast*/(y + 42);
       //     /*implicit assignment cast*/y += 42;
       //
       _checkImplicitCast(expr.leftHandSide, lhsType,
           from: returnType, opAssign: true);
     }
   }
 
-  void _checkFieldAccess(AstNode node, AstNode target, SimpleIdentifier field) {
-    if (field.staticElement == null &&
-        !typeProvider.isObjectMember(field.name)) {
+  void _checkFieldAccess(
+      AstNode node, Expression target, SimpleIdentifier field) {
+    var element = field.staticElement;
+    _checkImplicitCovarianceCast(node, target, element);
+    if (element == null && !typeProvider.isObjectMember(field.name)) {
       _recordDynamicInvoke(node, target);
     }
     node.visitChildren(this);
   }
 
   /// Checks if an implicit cast of [expr] from [from] type to [to] type is
   /// needed, and if so records it.
   ///
   /// If [from] is omitted, uses the static type of [expr].
   ///
@@ skipping 74 matching lines @@
         //     /*implicit assignment cast*/y++;
         //
         _checkImplicitCast(operand, lhsType, from: returnType, opAssign: true);
       }
     }
   }
 
   DartType _getDefiniteType(Expression expr) =>
       getDefiniteType(expr, rules, typeProvider);
 
+  /// If we're calling into [member] through the [target], we may need to
+  /// insert a caller side check for soundness on the result of the expression
+  /// [node].
+  ///
+  /// This happens when [target] is an unsafe covariant interface, and [member]
+  /// could return a type that is not a subtype of the expected static type
+  /// given target's type. For example:
+  ///
+  ///     typedef F<T>(T t);
+  ///     class C<T> {
+  ///       F<T> f;
+  ///       C(this.f);
+  ///     }
+  ///     test1() {
+  ///       C<Object> c = new C<int>((int x) => x + 42));
+  ///       F<Object> f = c.f; // need an implicit cast here.
+  ///       f('hello');
+  ///     }
+  ///
+  /// Here target is `c`, the target type is `C<Object>`, the member is
+  /// `get f() -> F<T>`, and the expression node is `c.f`. When we call `c.f`
+  /// the expected static result is `F<Object>`. However `c.f` actually returns
+  /// `F<int>`, which is not a subtype of `F<Object>`. So this method will add
+  /// an implicit cast `(c.f as F<Object>)` to guard against this case.
+  ///
+  /// Note that it is possible for the cast to succeed, for example:
+  /// `new C<int>((Object x) => '$x'))`. It is safe to pass any object to that
+  /// function, including an `int`.
+  void _checkImplicitCovarianceCast(
+      Expression node, Expression target, Element member) {
+    // If we're calling an instance method or getter, then we
+    // want to check the result type.
+    //
+    // We intentionally ignore method tear-offs, because those methods have
+    // covariance checks for their parameters inside the method.
+    if (member is ExecutableElement && _isInstanceMember(member)) {
+      DartType targetType;
+      if (target == null) {
+        if (!_inCurrentClass(member)) return;
+        targetType = _currentClass.type;
+      } else {
+        targetType = target.staticType;
+      }
+      if (targetType is InterfaceType && targetType.typeArguments.isNotEmpty) {
+        if (member.isPrivate && target != null) {
+          _trackPrivateMemberCovariance(target, member);
+        }
+
+        // Get the lower bound of the declared return type (e.g. `F<Null>`) and
+        // see if it can be assigned to the expected type (e.g. `F<Object>`).
+        //
+        // That way we can tell if any lower `T` will work or not.
+        var classType = targetType.element.type;
+        var classLowerBound = classType.instantiate(new List.filled(
+            classType.typeParameters.length, typeProvider.nullType));
+        var memberLowerBound = _lookUpMember(classLowerBound, member).type;
+        var expectedType = member.returnType;
+
+        if (!rules.isSubtypeOf(memberLowerBound.returnType, expectedType)) {
+          if (node is MethodInvocation && member is! MethodElement) {
+            // If `o.m` is not a method, we need to cast `o.m` before the call:
+            // `(o.m as expectedType)(args)`.
+            // This cannot be represented by an `as` node without changing the
+            // Dart AST structure, so we record it as a special cast.
+            setImplicitOperationCast(node, expectedType);
+          } else {
+            setImplicitCast(node, expectedType);
+          }
+          _hasImplicitCasts = true;
+        }
+      }
+    }
+  }
+
+  /// We can eliminate covariance checks on private members if they are only
+  /// accessed through something with a known generic type, such as `this`.
+  ///
+  /// For these expressions, we will know the generic parameters exactly:
+  ///
+  /// - this
+  /// - super
+  /// - non-factory instance creation
+  ///
+  /// For example:
+  ///
+  ///     class C<T> {
+  ///       T _t;
+  ///     }
+  ///     class D<T> extends C<T> {
+  ///        method<S extends T>(T t, C<T> c) {
+  ///          // implicit cast: t as T;
+  ///          // implicit cast: c as C<T>;
+  ///
+  ///          // These do not need further checks. The type parameter `T` for
+  ///          // `this` must be the same as our `T`
+  ///          this._t = t;
+  ///          super._t = t;
+  ///          new C<T>()._t = t; // non-factory
+  ///
+  ///          // This needs further checks. The type of `c` could be `C<S>` for
+  ///          // some `S <: T`.
+  ///          c._t = t;
+  ///          // factory statically returns `C<T>`, dynamically returns `C<S>`.
+  ///          new F<T, S>()._t = t;
+  ///        }
+  ///     }
+  ///     class F<T, S extends T> extends C<T> {
+  ///       factory F() => new C<S>();
+  ///     }
+  ///
+  void _trackPrivateMemberCovariance(Expression target, ExecutableElement e) {
+    if (target == null) return; // implicit this or invalid code.
+    if (target is ThisExpression || target is SuperExpression) return;
+    if (target is InstanceCreationExpression &&
+        target.staticElement?.isFactory == false) {
+      return;
+    }
+    if (e is PropertyAccessorElement && e.isGetter) return;
+
+    _covariantPrivateMembers.add(e is Member ? (e as Member).baseElement : e);
+  }
+
+  bool _isInstanceMember(ExecutableElement e) =>
+      !e.isStatic &&
+      (e is MethodElement ||
+          e is PropertyAccessorElement && e.variable is FieldElement);
+
+  bool _inCurrentClass(ExecutableElement e) {
+    if (_currentClass == null) return false;
+    var match = _lookUpMember(_currentClass.type, e);
+    return match?.enclosingElement == e.enclosingElement;
+  }
+
+  ExecutableElement _lookUpMember(InterfaceType type, ExecutableElement e) {
+    var name = e.name;
+    var library = e.library;
+    return e is PropertyAccessorElement
+        ? (e.isGetter
+            ? type.lookUpInheritedGetter(name, library: library)
+            : type.lookUpInheritedSetter(name, library: library))
+        : type.lookUpInheritedMethod(name, library: library);
+  }
+
   /// Gets the expected return type of the given function [body], either from
   /// a normal return/yield, or from a yield*.
   DartType _getExpectedReturnType(FunctionBody body, {bool yieldStar: false}) {
     FunctionType functionType;
     var parent = body.parent;
     if (parent is Declaration) {
       functionType = _elementType(parent.element);
     } else {
       assert(parent is FunctionExpression);
       functionType =
@@ skipping 192 matching lines @@
       errorCode = StrongModeCode.DYNAMIC_CAST;
     } else if (parent is VariableDeclaration && parent.initializer == expr) {
       errorCode = StrongModeCode.ASSIGNMENT_CAST;
     } else {
       errorCode = opAssign
           ? StrongModeCode.DOWN_CAST_IMPLICIT_ASSIGN
           : StrongModeCode.DOWN_CAST_IMPLICIT;
     }
     _recordMessage(expr, errorCode, [from, to]);
     if (opAssign) {
-      setImplicitAssignmentCast(expr, to);
+      setImplicitOperationCast(expr, to);
     } else {
       setImplicitCast(expr, to);
     }
     _hasImplicitCasts = true;
   }
 
   void _recordMessage(AstNode node, ErrorCode errorCode, List arguments) {
     // Compute the right severity taking the analysis options into account.
     // We construct a dummy error to make the common case where we end up
     // ignoring the strong mode message cheaper.
@@ skipping 190 matching lines @@
 
   void check(Declaration node) {
     var element =
         resolutionMap.elementDeclaredByDeclaration(node) as ClassElement;
     if (element.type.isObject) {
       return;
     }
     _checkSuperOverrides(node, element);
     _checkMixinApplicationOverrides(node, element);
     _checkAllInterfaceOverrides(node, element);
+    _checkForCovariantGenerics(node, element);
+  }
+
+  /// Finds implicit casts that we need on parameters and type formals to
+  /// ensure soundness of covariant generics, and records them on the [node].
+  ///
+  /// The parameter checks can be retrived using [getClassCovariantParameters]
+  /// and [getSuperclassCovariantParameters].
+  ///
+  /// For each member of this class and non-overridden inherited member, we
+  /// check to see if any generic super interface permits an unsound call to the
+  /// concrete member. For example:
+  ///
+  ///     class C<T> {
+  ///       add(T t) {} // C<Object>.add is unsafe, need a check on `t`
+  ///     }
+  ///     class D extends C<int> {
+  ///       add(int t) {} // C<Object>.add is unsafe, need a check on `t`
+  ///     }
+  ///     class E extends C<int> {
+  ///       add(Object t) {} // no check needed, C<Object>.add is safe
+  ///     }
+  ///
+  void _checkForCovariantGenerics(Declaration node, ClassElement element) {
+    // 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 allCovariant = _findAllGenericInterfaces(element.type);
+    if (allCovariant.isEmpty) return;
+
+    var seenConcreteMembers = new HashSet<String>();
+    var members = _getConcreteMembers(element.type, seenConcreteMembers);
+
+    // For members on this class, check them against all generic interfaces.
+    var checks = _findCovariantChecks(members, allCovariant);
+    // Store those checks on the class declaration.
+    setClassCovariantParameters(node, checks);
+
+    // For members of the superclass, we may need to add checks because this
+    // class adds a new unsafe interface. Collect those checks.
+    checks = _findSuperclassCovariantChecks(
+        element, allCovariant, seenConcreteMembers);
+    // Store the checks on the class declaration, it will need to ensure the
+    // inherited members are appropriately guarded to ensure soundness.
+    setSuperclassCovariantParameters(node, checks);
+  }
+
+  /// For each member of this class and non-overridden inherited member, we
+  /// check to see if any generic super interface permits an unsound call to the
+  /// concrete member. For example:
+  ///
+  /// We must check non-overridden inherited members because this class could
+  /// contain a new interface that permits unsound access to that member. In
+  /// those cases, the class is expected to insert stub that checks the type
+  /// before calling `super`. For example:
+  ///
+  ///     class C<T> {
+  ///       add(T t) {}
+  ///     }
+  ///     class D {
+  ///       add(int t) {}
+  ///     }
+  ///     class E extends D implements C<int> {
+  ///       // C<Object>.add is unsafe, and D.m is marked for a check.
+  ///       //
+  ///       // one way to implement this is to generate a stub method:
+  ///       // add(t) => super.add(t as int);
+  ///     }
+  ///
+  Set<Element> _findSuperclassCovariantChecks(ClassElement element,
+      Set<ClassElement> allCovariant, HashSet<String> seenConcreteMembers) {
+    var visited = new HashSet<ClassElement>()..add(element);
+    var superChecks = new Set<Element>();
+    var existingChecks = new HashSet<Element>();
+
+    void visitImmediateSuper(InterfaceType type) {
+      // For members of mixins/supertypes, check them against new interfaces,
+      // and also record any existing checks they already had.
+      var oldCovariant = _findAllGenericInterfaces(type);
+      var newCovariant = allCovariant.difference(oldCovariant);
+      if (newCovariant.isEmpty) return;
+
+      void visitSuper(InterfaceType type) {
+        var element = type.element;
+        if (visited.add(element)) {
+          var members = _getConcreteMembers(type, seenConcreteMembers);
+          _findCovariantChecks(members, newCovariant, superChecks);
+          _findCovariantChecks(members, oldCovariant, existingChecks);
+          element.mixins.reversed.forEach(visitSuper);
+          var s = element.supertype;
+          if (s != null) visitSuper(s);
+        }
+      }
+
+      visitSuper(type);
+    }
+
+    element.mixins.reversed.forEach(visitImmediateSuper);
+    var s = element.supertype;
+    if (s != null) visitImmediateSuper(s);
+
+    superChecks.removeAll(existingChecks);
+    return superChecks;
+  }
+
+  /// Gets all concrete instance members declared on this type, skipping already
+  /// [seenConcreteMembers] and adding any found ones to it.
+  ///
+  /// 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.
+  static List<ExecutableElement> _getConcreteMembers(
+      InterfaceType type, HashSet<String> seenConcreteMembers) {
+    var members = <ExecutableElement>[];
+    for (var declaredMembers in [type.accessors, type.methods]) {
+      for (var member in declaredMembers) {
+        // 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.
+        if (!member.isStatic &&
+            !member.isAbstract &&
+            seenConcreteMembers.add(member.name)) {
+          members.add(member);
+        }
+      }
+    }
+    return members;
+  }
+
+  /// Find all covariance checks on parameters/type parameters needed for
+  /// soundness given a set of concrete [members] and a set of unsafe generic
+  /// [covariantInterfaces] that may allow those members to be called in an
+  /// unsound way.
+  ///
+  /// See [_findCovariantChecksForMember] for more inofrmation and an exmaple.

[vsm, 2017/07/05 22:57:34]

inof -> info

[Jennifer Messerly, 2017/07/06 01:11:10]

Done.

+  Set<Element> _findCovariantChecks(Iterable<ExecutableElement> members,
+      Iterable<ClassElement> covariantInterfaces,
+      [Set<Element> covariantChecks]) {
+    covariantChecks ??= new Set();
+    if (members.isEmpty) return covariantChecks;
+
+    for (var iface in covariantInterfaces) {
+      var unsafeSupertype = _getCovariantUpperBound(rules, iface);
+      for (var m in members) {
+        _findCovariantChecksForMember(m, unsafeSupertype, covariantChecks);
+      }
+    }
+    return covariantChecks;
+  }
+
+  /// Given a [member] and a covariant [unsafeSupertype], determine if any
+  /// type formals or parameters of this member need a check because of the
+  /// unsoundness in the unsafe covariant supertype.
+  ///
+  /// For example:
+  ///
+  ///     class C<T> {
+  ///       m(T t) {}
+  ///       g<S extends T>() => <S>[];
+  ///     }
+  ///     class D extends C<num> {
+  ///       m(num n) {}
+  ///       g<R extends num>() => <R>[];
+  ///     }
+  ///     main() {
+  ///        C<Object> c = new C<int>();
+  ///        c.m('hi');     // must throw for soundness
+  ///        c.g<String>(); // must throw for soundness
+  ///
+  ///        c = new D();
+  ///        c.m('hi');     // must throw for soundness
+  ///        c.g<String>(); // must throw for soundness
+  ///     }
+  ///
+  /// We've already found `C<Object>` is a potentially unsafe covariant generic
+  /// supertpe, and we call this method to see if any members need a check
+  /// because of `C<Object>`.
+  ///
+  /// In this example, we will call this method with:
+  /// - `C<T>.m` and `C<Object>`, finding that `t` needs a check.
+  /// - `C<T>.g` and `C<Object>`, finding that `S` needs a check.
+  /// - `D.m`    and `C<Object>`, finding that `n` needs a check.
+  /// - `D.g`    and `C<Object>`, finding that `R` needs a check.
+  ///
+  /// Given `C<T>.m` and `C<Object>`, we search for covariance checks like this
+  /// (`*` short for `dynamic`):
+  /// - get the type of `C<Object>.m`: `(Object) -> *`
+  /// - get the type of `C<T>.m`:      `(T) -> *`
+  /// - perform a subtype check `(T) -> * <: (Object) -> *`,
+  ///   and record any parameters/type formals that violate soundess.
+  /// - that checks `Object <: T`, which is false, thus we need a check on
+  ///   parameter `t` of `C<T>.m`
+  ///
+  /// Another example is `D.g` and `C<Object>`:
+  /// - get the type of `C<Object>.m`: `<S extends Object>() -> *`
+  /// - get the type of `D.g`:         `<R extends num>() -> *`
+  /// - perform a subtype check
+  ///   `<S extends Object>() -> * <: <R extends num>() -> *`,
+  ///   and record any parameters/type formals that violate soundess.
+  /// - that checks the type formal bound of `S` and `R` asserting
+  ///   `Object <: num`, which is false, thus we need a check on type formal `R`
+  ///   of `D.g`.
+  void _findCovariantChecksForMember(ExecutableElement member,
+      InterfaceType unsafeSupertype, Set<Element> covariantChecks) {
+    var f2 = _getMemberType(unsafeSupertype, member);
+    if (f2 == null) return;
+    var f1 = member.type;
+
+    // Find parameter or type formal checks that we need to ensure `f2 <: f1`.
+    //
+    // The static type system allows this subtyping, but it is not sound without
+    // these runtime checks.
+    void addCheck(Element e) {
+      covariantChecks.add(e is Member ? e.baseElement : e);
+    }
+
+    var fresh = FunctionTypeImpl.relateTypeFormals(f1, f2, (b2, b1, p2, p1) {
+      if (!rules.isSubtypeOf(b2, b1)) addCheck(p1);
+      return true;
+    });
+    if (fresh != null) {
+      f1 = f1.instantiate(fresh);
+      f2 = f2.instantiate(fresh);
+    }
+    FunctionTypeImpl.relateParameters(f1.parameters, f2.parameters, (p1, p2) {
+      if (!rules.isOverrideSubtypeOfParameter(p1, p2)) addCheck(p1);
+      return true;
+    });
+  }
+
+  /// Find all generic interfaces that are implemented by [type], including
+  /// [type] itself if it is generic.
+  ///
+  /// This represents the complete set of unsafe covariant interfaces that could
+  /// be used to call members of [type].
+  ///
+  /// Because we're going to instantiate these to their upper bound, we don't
+  /// have to track type parameters.
+  static Set<ClassElement> _findAllGenericInterfaces(InterfaceType type) {
+    var visited = new HashSet<ClassElement>();
+    var genericSupertypes = new Set<ClassElement>();
+
+    void visitTypeAndSupertypes(InterfaceType type) {
+      var element = type.element;
+      if (visited.add(element)) {
+        if (element.typeParameters.isNotEmpty) {
+          genericSupertypes.add(element);
+        }
+        var supertype = element.supertype;
+        if (supertype != null) visitTypeAndSupertypes(supertype);
+        element.mixins.forEach(visitTypeAndSupertypes);
+        element.interfaces.forEach(visitTypeAndSupertypes);
+      }
+    }
+
+    visitTypeAndSupertypes(type);
+
+    return genericSupertypes;
   }
 
   /// Checks that implementations correctly override all reachable interfaces.
   /// In particular, we need to check these overrides for the definitions in
   /// the class itself and each its superclasses. If a superclass is not
   /// abstract, then we can skip its transitive interfaces. For example, in:
   ///
   ///     B extends C implements G
   ///     A extends B with E, F implements H, I
   ///
@@ skipping 98 matching lines @@
   /// Check that individual methods and fields in [subType] correctly override
   /// the declarations in [baseType].
   ///
   /// The [errorLocation] node indicates where errors are reported, see
   /// [_checkSingleOverride] for more details.
   ///
   /// The set [seen] is used to avoid reporting overrides more than once. It
   /// is used when invoking this function multiple times when checking several
   /// types in a class hierarchy. Errors are reported only the first time an
   /// invalid override involving a specific member is encountered.
-  _checkIndividualOverridesFromType(
+  void _checkIndividualOverridesFromType(
       InterfaceType subType,
       InterfaceType baseType,
       AstNode errorLocation,
       Set<String> seen,
       bool isSubclass) {
     void checkHelper(ExecutableElement e) {
       if (e.isStatic) return;
       if (seen.contains(e.name)) return;
       if (_checkSingleOverride(e, baseType, null, errorLocation, isSubclass)) {
         seen.add(e.name);
@@ skipping 114 matching lines @@
   ///                              ^
   ///
   /// When checking for overrides from a type and it's super types, [node] is
   /// the AST node that defines [element]. This is used to determine whether the
   /// type of the element could be inferred from the types in the super classes.
   bool _checkSingleOverride(ExecutableElement element, InterfaceType type,
       AstNode node, AstNode errorLocation, bool isSubclass) {
     assert(!element.isStatic);
 
     FunctionType subType = _elementType(element);
-    // TODO(vsm): Test for generic
     FunctionType baseType = _getMemberType(type, element);
     if (baseType == null) return false;
 
     if (isSubclass && element is PropertyAccessorElement) {
       // Disallow any overriding if the base class defines this member
       // as a field.  We effectively treat fields as final / non-virtual,
       // unless they are explicitly marked as @virtual
       var field = _getMemberField(type, element);
       if (field != null && !field.isVirtual) {
         _checker._recordMessage(
             errorLocation, StrongModeCode.INVALID_FIELD_OVERRIDE, [
           element.enclosingElement.name,
           element.name,
           subType,
           type,
           baseType
         ]);
       }
     }
+
     if (!rules.isOverrideSubtypeOf(subType, baseType)) {
       ErrorCode errorCode;
       var parent = errorLocation?.parent;
       if (errorLocation is ExtendsClause ||
           parent is ClassTypeAlias && parent.superclass == errorLocation) {
         errorCode = StrongModeCode.INVALID_METHOD_OVERRIDE_FROM_BASE;
       } else if (parent is WithClause) {
         errorCode = StrongModeCode.INVALID_METHOD_OVERRIDE_FROM_MIXIN;
       } else {
         errorCode = StrongModeCode.INVALID_METHOD_OVERRIDE;
@@ skipping 65 matching lines @@
   }
 
   /// If node is a [ClassDeclaration] returns its members, otherwise if node is
   /// a [ClassTypeAlias] this returns an empty list.
   WithClause _withClause(Declaration node) {
     return node is ClassDeclaration
         ? node.withClause
         : (node as ClassTypeAlias).withClause;
   }
 }