fix #28008, fix #28009 implement FutureOr<T>

pkg/analyzer/lib/src/generated/type_system.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.
 
 library analyzer.src.generated.type_system;
 
 import 'dart:collection';
 import 'dart:math' as math;
 
 import 'package:analyzer/dart/ast/ast.dart' show AstNode;
 import 'package:analyzer/dart/ast/token.dart' show TokenType;
 import 'package:analyzer/dart/element/element.dart';
 import 'package:analyzer/dart/element/type.dart';
 import 'package:analyzer/error/listener.dart' show ErrorReporter;
 import 'package:analyzer/src/dart/element/element.dart';
 import 'package:analyzer/src/dart/element/member.dart' show TypeParameterMember;
 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 AnalysisContext, AnalysisOptionsImpl;
 import 'package:analyzer/src/generated/resolver.dart' show TypeProvider;
 import 'package:analyzer/src/generated/utilities_dart.dart' show ParameterKind;
-import 'package:analyzer/src/generated/utilities_general.dart'
-    show JenkinsSmiHash;
 
 bool _isBottom(DartType t, {bool dynamicIsBottom: false}) {
   return (t.isDynamic && dynamicIsBottom) || t.isBottom || t.isDartCoreNull;
 }
 
 bool _isTop(DartType t, {bool dynamicIsBottom: false}) {
   // TODO(leafp): Document the rules in play here
+  if (t.isDartAsyncFutureOr) {
+    return _isTop((t as InterfaceType).typeArguments[0]);
+  }
   return (t.isDynamic && !dynamicIsBottom) || t.isObject;
 }
 
 typedef bool _GuardedSubtypeChecker<T>(T t1, T t2, Set<Element> visited);
 
 /**
- * A special union type of `Future<T> | T` used for Strong Mode inference.
- */
-class FutureUnionType extends TypeImpl {
-  // TODO(jmesserly): a Set would be better.
-  //
-  // For now we know `Future<T> | T` is the only valid use, so we can rely on
-  // the order, which simplifies some things.
-  //
-  // This will need clean up before this can function as a real union type.
-  final List<DartType> _types;
-
-  /**
-   * Creates a union of `Future<T> | T`.
-   */
-  FutureUnionType._(DartType type, TypeProvider provider, TypeSystem system)
-      : _types = [
-          provider.futureType.instantiate([type]),
-          type
-        ],
-        super(null, null);
-
-  DartType get futureOfType => _types[0];
-
-  @override
-  int get hashCode {
-    int hash = 0;
-    for (var t in types) {
-      hash = JenkinsSmiHash.combine(hash, t.hashCode);
-    }
-    return JenkinsSmiHash.finish(hash);
-  }
-
-  DartType get type => _types[1];
-
-  Iterable<DartType> get types => _types;
-
-  @override
-  bool operator ==(Object obj) {
-    if (obj is FutureUnionType) {
-      if (identical(obj, this)) return true;
-      return types.length == obj.types.length &&
-          types.toSet().containsAll(obj.types);
-    }
-    return false;
-  }
-
-  @override
-  void appendTo(StringBuffer buffer) {
-    buffer.write('(');
-    for (int i = 0; i < _types.length; i++) {
-      if (i != 0) {
-        buffer.write(' | ');
-      }
-      (_types[i] as TypeImpl).appendTo(buffer);
-    }
-    buffer.write(')');
-  }
-
-  @override
-  bool isMoreSpecificThan(DartType type,
-          [bool withDynamic = false, Set<Element> visitedElements]) =>
-      throw new UnsupportedError(
-          'Future unions are not part of the Dart 1 type system');
-
-  @override
-  TypeImpl pruned(List<FunctionTypeAliasElement> prune) =>
-      throw new UnsupportedError('Future unions are not substituted');
-
-  @override
-  DartType substitute2(List<DartType> args, List<DartType> params,
-          [List<FunctionTypeAliasElement> prune]) =>
-      throw new UnsupportedError('Future unions are not used in typedefs');
-
-  /**
-   * Creates a union of `T | Future<T>`, unless `T` is already a future or a
-   * future-union, in which case it simply returns `T`.
-   *
-   * Conceptually this is used as the inverse of the `flatten(T)` operation,
-   * defined as:
-   *
-   * - `flatten(Future<T>) -> T`
-   * - `flatten(T) -> T`
-   *
-   * Thus the inverse will give us `T | Future<T>`.
-   *
-   * If [type] is top (dynamic or Object) then the resulting union type is
-   * equivalent to top, so we simply return it.
-   *
-   * For a similar reason `Future<T> | Future<Future<T>>` is equivalent to just
-   * `Future<T>`, so we return it. Note that it is not possible to get a
-   * `Future<T>` as a result of `flatten`, so a this case likely indicates a
-   * type error in the code, but it will be reported elsewhere.
-   */
-  static DartType from(
-      DartType type, TypeProvider provider, TypeSystem system) {
-    if (_isTop(type)) {
-      return type;
-    }
-    if (!identical(type, type.flattenFutures(system))) {
-      // As noted above, this most likely represents erroneous input.
-      return type;
-    }
-
-    if (type is FutureUnionType) {
-      return type;
-    }
-    return new FutureUnionType._(type, provider, system);
-  }
-}
-
-/**
  * Implementation of [TypeSystem] using the strong mode rules.
  * https://github.com/dart-lang/dev_compiler/blob/master/STRONG_MODE.md
  */
 class StrongTypeSystemImpl extends TypeSystem {
   /**
    * True if implicit casts should be allowed, otherwise false.
    *
    * This affects the behavior of [isAssignableTo].
    */
   final bool implicitCasts;
 
   /**
    * A list of non-nullable type names (e.g., 'int', 'bool', etc.).
    */
   final List<String> nonnullableTypes;
 
   final TypeProvider typeProvider;
 
   StrongTypeSystemImpl(this.typeProvider,
       {this.implicitCasts: true,
       this.nonnullableTypes: AnalysisOptionsImpl.NONNULLABLE_TYPES});
 
   bool anyParameterType(FunctionType ft, bool predicate(DartType t)) {
     return ft.parameters.any((p) => predicate(p.type));
   }
 
   @override
+  bool get isStrong => true;
+
+  @override
   FunctionType functionTypeToConcreteType(FunctionType t) {
     // TODO(jmesserly): should we use a real "fuzzyArrow" bit on the function
     // type? That would allow us to implement this in the subtype relation.
     // TODO(jmesserly): we'll need to factor this differently if we want to
     // move CodeChecker's functionality into existing analyzer. Likely we can
     // let the Expression have a strict arrow, then in places were we do
     // inference, convert back to a fuzzy arrow.
 
     if (!t.parameters.any((p) => p.type.isDynamic)) {
       return t;
@@ skipping 613 matching lines @@
         return check(t1, t2, visited);
       } finally {
         visited.remove(element);
       }
     };
   }
 
   /// If [t1] or [t2] is a type parameter we are inferring, update its bound.
   /// Returns `true` if we could possibly find a compatible type,
   /// otherwise `false`.
-  bool _inferTypeParameterSubtypeOf(
-      DartType t1, DartType t2, Set<Element> visited) {
+  bool _inferTypeParameterSubtypeOf(DartType t1, DartType t2) {
     return false;
   }
 
   /**
    * This currently does not implement a very complete least upper bound
    * algorithm, but handles a couple of the very common cases that are
    * causing pain in real code.  The current algorithm is:
    * 1. If either of the types is a supertype of the other, return it.
    *    This is in fact the best result in this case.
    * 2. If the two types have the same class element, then take the
@@ skipping 105 matching lines @@
   }
 
   bool _isSubtypeOf(DartType t1, DartType t2, Set<Element> visited,
       {bool dynamicIsBottom: false}) {
     if (identical(t1, t2)) {
       return true;
     }
 
     // Guard recursive calls
     _GuardedSubtypeChecker<DartType> guardedSubtype = _guard(_isSubtypeOf);
-    _GuardedSubtypeChecker<DartType> guardedInferTypeParameter =
-        _guard(_inferTypeParameterSubtypeOf);
 
     // The types are void, dynamic, bottom, interface types, function types,
-    // and type parameters. We proceed by eliminating these different classes
-    // from consideration.
+    // FutureOr<T> and type parameters.
+    //
+    // We proceed by eliminating these different classes from consideration.
 
     // Trivially true.
     if (_isTop(t2, dynamicIsBottom: dynamicIsBottom) ||
         _isBottom(t1, dynamicIsBottom: dynamicIsBottom)) {
       return true;
     }
 
     // Trivially false.
     if (_isTop(t1, dynamicIsBottom: dynamicIsBottom) ||
         _isBottom(t2, dynamicIsBottom: dynamicIsBottom)) {
-      return guardedInferTypeParameter(t1, t2, visited);
+      return _inferTypeParameterSubtypeOf(t1, t2);
     }
 
     // S <: T where S is a type variable
     //  T is not dynamic or object (handled above)
     //  True if T == S
     //  Or true if bound of S is S' and S' <: T
     if (t1 is TypeParameterType) {
       if (t2 is TypeParameterType &&
           t1.definition == t2.definition &&
           guardedSubtype(t1.bound, t2.bound, visited)) {
         return true;
       }
-      if (guardedInferTypeParameter(t1, t2, visited)) {
+      if (_inferTypeParameterSubtypeOf(t1, t2)) {
         return true;
       }
       DartType bound = t1.element.bound;
       return bound == null ? false : guardedSubtype(bound, t2, visited);
     }
 
     if (t2 is TypeParameterType) {
-      return guardedInferTypeParameter(t1, t2, visited);
+      return _inferTypeParameterSubtypeOf(t1, t2);
     }
 
-    if (t1 is FutureUnionType) {
+    // Handle FutureOr<T> union type.
+    if (t1 is InterfaceType && t1.isDartAsyncFutureOr) {
+      var t1TypeArg = t1.typeArguments[0];
+      if (t2 is InterfaceType && t2.isDartAsyncFutureOr) {
+        var t2TypeArg = t2.typeArguments[0];
+        // FutureOr<A> <: FutureOr<B> iff A <: B
+        return isSubtypeOf(t1TypeArg, t2TypeArg);
+      }
+
       // given t1 is Future<A> | A, then:
-      // (Future<A> | A) <: t2 iff t2 <: Future<A> and t2 <: A.
-      return guardedSubtype(t1.futureOfType, t2, visited) &&
-          guardedSubtype(t1.type, t2, visited);
+      // (Future<A> | A) <: t2 iff Future<A> <: t2 and A <: t2.
+      var t1Future = typeProvider.futureType.instantiate([t1TypeArg]);
+      return isSubtypeOf(t1Future, t2) && isSubtypeOf(t1TypeArg, t2);
     }
-    if (t2 is FutureUnionType) {
+
+    if (t2 is InterfaceType && t2.isDartAsyncFutureOr) {
       // given t2 is Future<A> | A, then:
       // t1 <: (Future<A> | A) iff t1 <: Future<A> or t1 <: A
-      return guardedSubtype(t1, t2.futureOfType, visited) ||
-          guardedSubtype(t1, t2.type, visited);
+      var t2TypeArg = t2.typeArguments[0];
+      var t2Future = typeProvider.futureType.instantiate([t2TypeArg]);
+      return isSubtypeOf(t1, t2Future) || isSubtypeOf(t1, t2TypeArg);
     }
 
     // Void only appears as the return type of a function, and we handle it
     // directly in the function subtype rules. We should not get to a point
     // where we're doing a subtype test on a "bare" void, but just in case we
     // do, handle it safely.
     // TODO(rnystrom): Determine how this can ever be reached. If it can't,
     // remove it.
     if (t1.isVoid || t2.isVoid) {
       return t1.isVoid && t2.isVoid;
     }
 
-    // We've eliminated void, dynamic, bottom, and type parameters.  The only
-    // cases are the combinations of interface type and function type.
+    // We've eliminated void, dynamic, bottom, type parameters, and FutureOr.
+    // The only cases are the combinations of interface type and function type.
 
     // A function type can only subtype an interface type if
     // the interface type is Function
     if (t1 is FunctionType && t2 is InterfaceType) {
       return t2.isDartCoreFunction;
     }
 
     // An interface type can only subtype a function type if
     // the interface type declares a call method with a type
     // which is a super type of the function type.
@@ skipping 69 matching lines @@
 
 /**
  * The interface `TypeSystem` defines the behavior of an object representing
  * the type system.  This provides a common location to put methods that act on
  * types but may need access to more global data structures, and it paves the
  * way for a possible future where we may wish to make the type system
  * pluggable.
  */
 abstract class TypeSystem {
   /**
+   * Whether the type system is strong or not.
+   */
+  bool get isStrong;
+
+  /**
    * The provider of types for the system
    */
   TypeProvider get typeProvider;
 
   /**
    * Make a function type concrete.
    *
    * Normally we treat dynamically typed parameters as bottom for function
    * types. This allows type tests such as `if (f is SingleArgFunction)`.
    * It also requires a dynamic check on the parameter type to call these
@@ skipping 353 matching lines @@
 
 /**
  * Implementation of [TypeSystem] using the rules in the Dart specification.
  */
 class TypeSystemImpl extends TypeSystem {
   final TypeProvider typeProvider;
 
   TypeSystemImpl(this.typeProvider);
 
   @override
+  bool get isStrong => false;
+
   FunctionType functionTypeToConcreteType(FunctionType t) => t;
 
   /**
    * Instantiate a parameterized type using `dynamic` for all generic
    * parameters.  Returns the type unchanged if there are no parameters.
    */
   DartType instantiateToBounds(DartType type, {List<bool> hasError}) {
     List<DartType> typeFormals = typeFormalsAsTypes(type);
     int count = typeFormals.length;
     if (count > 0) {
@@ skipping 116 matching lines @@
       //
       //     <TFrom, TTo extends Iterable<TFrom>>
       //
       // Or if the type parameter's bound depends on itself such as:
       //
       //     <T extends Clonable<T>>
       DartType declaredUpperBound = typeParam.element.bound;
       if (declaredUpperBound != null) {
         // Assert that the type parameter is a subtype of its bound.
         _inferTypeParameterSubtypeOf(typeParam,
-            declaredUpperBound.substitute2(inferredTypes, fnTypeParams), null);
+            declaredUpperBound.substitute2(inferredTypes, fnTypeParams));
       }
 
       // Now we've computed lower and upper bounds for each type parameter.
       //
       // To decide on which type to assign, we look at the return type and see
       // if the type parameter occurs in covariant or contravariant positions.
       //
       // If the type is "passed in" at all, or if our lower bound was bottom,
       // we choose the upper bound as being the most useful.
       //
       // Otherwise we choose the more precise lower bound.
       _TypeParameterVariance variance =
           new _TypeParameterVariance.from(typeParam, declaredReturnType);
 
       _TypeParameterBound bound = _bounds[typeParam];
       DartType lowerBound = bound.lower;
       DartType upperBound = bound.upper;
 
-      // Collapse future unions if we inferred them somehow.
-      //
-      // TODO(jmesserly): in our initial upward phase it would be fine to
-      // keep the FutureUnionType for the argument downward context.
-      //
-      // We need to track in `inferGenericFunctionCall` whether we are going up
-      // or down. This would also allow for an improved heuristic: if we are
-      // doing our final inference, the downward context can take priority.
-      if (lowerBound is FutureUnionType) {
-        // lowerBound <: T, where lowerBound is Future<A> | A.
-        // So we choose lowerBound as LUB(A, Future<A>).
-        //
-        // This will typically lead to top with the current rules, but it will
-        // work with `bottom` or if we remove Future flattening.
-        var f = lowerBound as FutureUnionType;
-        lowerBound = _typeSystem.getLeastUpperBound(f.futureOfType, f.type);
-      }
-      if (upperBound is FutureUnionType) {
-        // T <: upperBound, where upperBound is Future<A> | A.
-        // Therefore we need T <: Future<A> or T <: A.
-        //
-        // This is just an arbitrarily heuristic.
-        var f = upperBound as FutureUnionType;
-        if (_typeSystem.isSubtypeOf(lowerBound, f.type)) {
-          upperBound = f.type;
-        } else if (_typeSystem.isSubtypeOf(lowerBound, f.futureOfType)) {
-          upperBound = f.futureOfType;
-        } else {
-          upperBound = f.type;
-        }
-      }
-
       // See if the bounds can be satisfied.
       // TODO(jmesserly): also we should have an error for unconstrained type
       // parameters, rather than silently inferring dynamic.
       if (upperBound.isBottom ||
           !_typeSystem.isSubtypeOf(lowerBound, upperBound)) {
         // Inference failed.
         if (errorReporter == null) {
           return null;
         }
         errorReporter.reportErrorForNode(StrongModeCode.COULD_NOT_INFER,
@@ skipping 19 matching lines @@
           variance.passedIn && !upperBound.isDynamic || lowerBound.isBottom
               ? upperBound
               : lowerBound;
     }
 
     // Return the instantiated type.
     return genericType.instantiate(inferredTypes) as dynamic/*=T*/;
   }
 
   @override
-  bool _inferTypeParameterSubtypeOf(
-      DartType t1, DartType t2, Set<Element> visited) {
+  bool _inferTypeParameterSubtypeOf(DartType t1, DartType t2) {
     if (t1 is TypeParameterType) {
       _TypeParameterBound bound = _bounds[t1];
       if (bound != null) {
         // Ensure T1 <: T2, where T1 is a type parameter we are inferring.
         // T2 is an upper bound, so merge it with our existing upper bound.
         //
         // We already know T1 <: U, for some U.
         // So update U to reflect the new constraint T1 <: GLB(U, T2)
         //
         bound.upper = _typeSystem.getGreatestLowerBound(bound.upper, t2);
@@ skipping 122 matching lines @@
       } else {
         passedOut = true;
       }
     } else if (type is FunctionType) {
       _visitFunctionType(typeParam, type, paramIn);
     } else if (type is InterfaceType) {
       _visitInterfaceType(typeParam, type, paramIn);
     }
   }
 }