fix #25487, infer block lambdas from return statements

pkg/analyzer/lib/src/generated/resolver.dart

 // Copyright (c) 2014, 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.resolver;
 
 import 'dart:collection';
 
 import 'package:analyzer/dart/ast/ast.dart';
 import 'package:analyzer/dart/ast/token.dart';
@@ skipping 4584 matching lines @@
    * Type provider, needed for type matching.
    */
   final TypeProvider _typeProvider;
 
   /**
    * The type system in use.
    */
   final TypeSystem _typeSystem;
 
   /**
+   * When no context type is available, this will track the least upper bound
+   * of all return statements in a lambda.
+   *
+   * This will always be kept in sync with [_returnStack].
+   */
+  final List<DartType> _inferredReturn = <DartType>[];
+
+  /**
    * A stack of return types for all of the enclosing
    * functions and methods.
    */
   // TODO(leafp) Handle the implicit union type for Futures
   // https://github.com/dart-lang/sdk/issues/25322
-  List<DartType> _returnStack = <DartType>[];
+  final List<DartType> _returnStack = <DartType>[];
 
   InferenceContext._(this._errorListener, TypeProvider typeProvider,
       this._typeSystem, this._inferenceHints)
       : _typeProvider = typeProvider;
 
   /**
    * Get the return type of the current enclosing function, if any.
    *
    * The type returned for a function is the type that is expected
    * to be used in a return or yield context.  For ordinary functions
    * this is the same as the return type of the function.  For async
    * functions returning Future<T> and for generator functions
    * returning Stream<T> or Iterable<T>, this is T.
    */
   DartType get returnContext =>
       _returnStack.isNotEmpty ? _returnStack.last : null;
 
   /**
+   * Records the type of the expression of a return statement.
+   *
+   * This will be used for inferring a block bodied lambda, if no context
+   * type was available.
+   */
+  void addReturnOrYieldType(DartType type) {
+    if (_returnStack.isEmpty) {
+      return;
+    }
+    DartType context = _returnStack.last;
+    if (context == null || context.isDynamic) {
+      DartType inferred = _inferredReturn.last;
+      inferred = _typeSystem.getLeastUpperBound(_typeProvider, type, inferred);
+      _inferredReturn[_inferredReturn.length - 1] = inferred;
+    }
+  }
+
+  /**
    * Match type [t1] against type [t2] as follows.
    * If `t1 = I<dynamic, ..., dynamic>`, then look for a supertype
    * of t1 of the form `K<S0, ..., Sm>` where `t2 = K<S0', ..., Sm'>`
    * If the supertype exists, use the constraints `S0 <: S0', ... Sm <: Sm'`
    * to derive a concrete instantation for I of the form `<T0, ..., Tn>`,
    * such that `I<T0, .., Tn> <: t2`
    */
   List<DartType> matchTypes(DartType t1, DartType t2) =>
       (t1 is InterfaceType && t2 is InterfaceType) ? _matchTypes(t1, t2) : null;
 
   /**
    * Pop a return type off of the return stack.
+   *
+   * Also record any inferred return type using [setType], unless this node
+   * already has a context type. This recorded type will be the least upper
+   * bound of all types added with [addReturnOrYieldType].
    */
-  void popReturnContext() {
-    assert(_returnStack.isNotEmpty);
+  void popReturnContext(BlockFunctionBody node) {
+    assert(_returnStack.isNotEmpty && _inferredReturn.isNotEmpty);
     if (_returnStack.isNotEmpty) {
       _returnStack.removeLast();
     }
+    if (_inferredReturn.isNotEmpty) {
+      DartType inferred = _inferredReturn.removeLast();
+      if (!inferred.isBottom) {
+        setType(node, inferred);
+      }
+    }
   }
 
   /**
-   * Push a [returnType] onto the return stack.
+   * Push a block function body's return type onto the return stack.
    */
-  void pushReturnContext(DartType returnType) {
+  void pushReturnContext(BlockFunctionBody node) {
+    DartType returnType = getType(node);
     _returnStack.add(returnType);
+    _inferredReturn.add(BottomTypeImpl.instance);
   }
 
   /**
    * Place an info node into the error stream indicating that a
    * [type] has been inferred as the type of [node].
    */
   void recordInference(Expression node, DartType type) {
     StaticInfo info = InferredType.create(_typeSystem, node, type);
     if (!_inferenceHints || info == null) {
       return;
@@ skipping 2986 matching lines @@
     }
     node.accept(elementResolver);
     node.accept(typeAnalyzer);
     return null;
   }
 
   @override
   Object visitBlockFunctionBody(BlockFunctionBody node) {
     _overrideManager.enterScope();
     try {
-      inferenceContext.pushReturnContext(InferenceContext.getType(node));
+      inferenceContext.pushReturnContext(node);
       super.visitBlockFunctionBody(node);
     } finally {
       _overrideManager.exitScope();
-      inferenceContext.popReturnContext();
+      inferenceContext.popReturnContext(node);
     }
     return null;
   }
 
   @override
   Object visitBreakStatement(BreakStatement node) {
     //
     // We do not visit the label because it needs to be visited in the context
     // of the statement.
     //
@@ skipping 457 matching lines @@
       _currentFunctionBody = node.body;
       _enclosingFunction = node.element;
       _overrideManager.enterScope();
       try {
         DartType functionType = InferenceContext.getType(node);
         if (functionType is FunctionType) {
           functionType =
               matchFunctionTypeParameters(node.typeParameters, functionType);
           if (functionType is FunctionType) {
             _inferFormalParameterList(node.parameters, functionType);
-            DartType returnType = _computeReturnOrYieldType(
-                functionType.returnType,
-                _enclosingFunction.isGenerator,
-                _enclosingFunction.isAsynchronous);
+            DartType returnType =
+                _computeReturnOrYieldType(functionType.returnType);
             InferenceContext.setType(node.body, returnType);
           }
         }
         super.visitFunctionExpression(node);
       } finally {
         _overrideManager.exitScope();
       }
     } finally {
       _currentFunctionBody = outerFunctionBody;
       _enclosingFunction = outerFunction;
@@ skipping 189 matching lines @@
     return null;
   }
 
   @override
   Object visitMethodDeclaration(MethodDeclaration node) {
     ExecutableElement outerFunction = _enclosingFunction;
     FunctionBody outerFunctionBody = _currentFunctionBody;
     try {
       _currentFunctionBody = node.body;
       _enclosingFunction = node.element;
-      DartType returnType = _computeReturnOrYieldType(
-          _enclosingFunction.type?.returnType,
-          _enclosingFunction.isGenerator,
-          _enclosingFunction.isAsynchronous);
+      DartType returnType =
+          _computeReturnOrYieldType(_enclosingFunction.type?.returnType);
       InferenceContext.setType(node.body, returnType);
       super.visitMethodDeclaration(node);
     } finally {
       _currentFunctionBody = outerFunctionBody;
       _enclosingFunction = outerFunction;
     }
     return null;
   }
 
   @override
@@ skipping 75 matching lines @@
     //
     InferenceContext.setType(node.argumentList, node.staticElement?.type);
     safelyVisit(node.argumentList);
     node.accept(elementResolver);
     node.accept(typeAnalyzer);
     return null;
   }
 
   @override
   Object visitReturnStatement(ReturnStatement node) {
-    InferenceContext.setType(node.expression, inferenceContext.returnContext);
-    return super.visitReturnStatement(node);
+    Expression e = node.expression;
+    InferenceContext.setType(e, inferenceContext.returnContext);
+    super.visitReturnStatement(node);
+    DartType type = e?.staticType;
+    // Generators cannot return values, so don't try to do any inference if
+    // we're processing erroneous code.
+    if (type != null && _enclosingFunction?.isGenerator == false) {
+      if (_enclosingFunction.isAsynchronous) {
+        type = type.flattenFutures(typeSystem);
+      }
+      inferenceContext.addReturnOrYieldType(type);
+    }
+    return null;
   }
 
   @override
   Object visitShowCombinator(ShowCombinator node) => null;
 
   @override
   Object visitSuperConstructorInvocation(SuperConstructorInvocation node) {
     //
     // We visit the argument list, but do not visit the optional identifier
     // because it needs to be visited in the context of the constructor
@@ skipping 101 matching lines @@
     }
     // TODO(brianwilkerson) If the loop can only be exited because the condition
     // is false, then propagateFalseState(condition);
     node.accept(elementResolver);
     node.accept(typeAnalyzer);
     return null;
   }
 
   @override
   Object visitYieldStatement(YieldStatement node) {
+    Expression e = node.expression;
     DartType returnType = inferenceContext.returnContext;
-    if (returnType != null && _enclosingFunction != null) {
+    bool isGenerator = _enclosingFunction?.isGenerator ?? false;
+    if (returnType != null && isGenerator) {
       // If we're not in a generator ([a]sync*, then we shouldn't have a yield.
       // so don't infer
-      if (_enclosingFunction.isGenerator) {
-        // If this just a yield, then we just pass on the element type
-        DartType type = returnType;
-        if (node.star != null) {
-          // If this is a yield*, then we wrap the element return type
-          // If it's synchronous, we expect Iterable<T>, otherwise Stream<T>
-          InterfaceType wrapperType = _enclosingFunction.isSynchronous
-              ? typeProvider.iterableType
-              : typeProvider.streamType;
-          type = wrapperType.substitute4(<DartType>[type]);
-        }
-        InferenceContext.setType(node.expression, type);
+
+      // If this just a yield, then we just pass on the element type
+      DartType type = returnType;
+      if (node.star != null) {
+        // If this is a yield*, then we wrap the element return type
+        // If it's synchronous, we expect Iterable<T>, otherwise Stream<T>
+        InterfaceType wrapperType = _enclosingFunction.isSynchronous
+            ? typeProvider.iterableType
+            : typeProvider.streamType;
+        type = wrapperType.substitute4(<DartType>[type]);
+      }
+      InferenceContext.setType(e, type);
+
+    }
+    super.visitYieldStatement(node);
+    DartType type = e?.staticType;
+    if (type != null && isGenerator) {
+      // If this just a yield, then we just pass on the element type
+      if (node.star != null) {
+        // If this is a yield*, then we unwrap the element return type
+        // If it's synchronous, we expect Iterable<T>, otherwise Stream<T>
+        InterfaceType wrapperType = _enclosingFunction.isSynchronous
+            ? typeProvider.iterableType
+            : typeProvider.streamType;
+        List<DartType> candidates = _findImplementedTypeArgument(type, wrapperType);
+        type = InterfaceTypeImpl.findMostSpecificType(candidates, typeSystem);
+      }
+      if (type != null) {
+        inferenceContext.addReturnOrYieldType(type);
       }
     }
-    return super.visitYieldStatement(node);
+    return null;
   }
 
   /**
    * Checks each promoted variable in the current scope for compliance with the following
    * specification statement:
    *
    * If the variable <i>v</i> is accessed by a closure in <i>s<sub>1</sub></i> then the variable
    * <i>v</i> is not potentially mutated anywhere in the scope of <i>v</i>.
    */
   void _clearTypePromotionsIfAccessedInClosureAndProtentiallyMutated(
       AstNode target) {
     for (Element element in _promoteManager.promotedElements) {
       if (_currentFunctionBody.isPotentiallyMutatedInScope(element)) {
         if (_isVariableAccessedInClosure(element, target)) {
           _promoteManager.setType(element, null);
         }
       }
     }
   }
 
+
   /**
    * Checks each promoted variable in the current scope for compliance with the following
    * specification statement:
    *
    * <i>v</i> is not potentially mutated in <i>s<sub>1</sub></i> or within a closure.
    */
   void _clearTypePromotionsIfPotentiallyMutatedIn(AstNode target) {
     for (Element element in _promoteManager.promotedElements) {
       if (_isVariablePotentiallyMutatedIn(element, target)) {
         _promoteManager.setType(element, null);
       }
     }
   }
 
   /**
    * Given the declared return type of a function, compute the type of the
    * values which should be returned or yielded as appropriate.  If a type
    * cannot be computed from the declared return type, return null.
    */
-  DartType _computeReturnOrYieldType(
-      DartType declaredType, bool isGenerator, bool isAsynchronous) {
+  DartType _computeReturnOrYieldType(DartType declaredType) {
+    bool isGenerator = _enclosingFunction.isGenerator;
+    bool isAsynchronous = _enclosingFunction.isAsynchronous;
+
     // Ordinary functions just return their declared types.
     if (!isGenerator && !isAsynchronous) {
       return declaredType;
     }
     if (isGenerator) {
       if (declaredType is! InterfaceType) {
         return null;
       }
       // If it's synchronous, we expect Iterable<T>, otherwise Stream<T>
       InterfaceType rawType = isAsynchronous
           ? typeProvider.streamDynamicType
           : typeProvider.iterableDynamicType;
       // Match the types to instantiate the type arguments if possible
       List<DartType> typeArgs =
-          inferenceContext.matchTypes(rawType, declaredType);
+      inferenceContext.matchTypes(rawType, declaredType);

[Leaf, 2016/02/24 15:38:40]

I think this code should be changed to use your new _findImplementedTypeArgument
helper just as in visitYieldStatement above.  This arguably an abuse of
matchTypes here, or at least a larger hammer than is needed.  I'm pretty sure
that all this code is intended to do is what your new code does.  Also -
formatting?

[Jennifer Messerly, 2016/02/24 17:43:16]

Ah, thanks Leaf ... that makes so much more sense!

Originally I misunderstood what matchTypes does, and tried to reuse the code
here, factoring it out into its own method. But then it wouldn't handle a case
like:

    yield* [1, 2, 3] // List<int> matched against Iterable<> should give "int"

And then I looked into matchTypes and saw it was for the opposite kind of case,
when we're inferring a constructor from a context.

I'm not entirely sure that the new code would be right either -- it seems
potentially a bit too powerful as well. The new code is similar to flatten case
below for Futures, which I found has a bug:
https://github.com/dart-lang/sdk/issues/25854.

Based on that, I'm leaning towards looking into it in a follow up change.

But yeah I'll fix formatting. Funny that it helped us find some real problems in
the code. ;)

       return (typeArgs?.length == 1) ? typeArgs[0] : null;
     }
     // Must be asynchronous to reach here, so strip off any layers of Future
     return declaredType.flattenFutures(typeSystem);
   }
 
   /**
+   * Starting from t1, search its class hierarchy for types of the form
+   * `t2<R>`, and return a list of the resulting R's
+   *
+   * For example, given t1 = `List<int>` and t2 = `Iterable<T>`, this will
+   * return [int].
+   */
+  // TODO(jmesserly): this is very similar to code used for flattening futures.
+  // The only difference is, because of a lack of TypeProvider, the other method
+  // has to match the Future type by its name and library. Here was are passed
+  // in the correct type.
+  List<DartType> _findImplementedTypeArgument(DartType t1, InterfaceType t2) {
+    List<DartType> result = <DartType>[];
+    HashSet<ClassElement> visitedClasses = new HashSet<ClassElement>();
+    void recurse(InterfaceTypeImpl type) {
+      if (type.element == t2.element  && type.typeArguments.isNotEmpty) {
+        result.add(type.typeArguments[0]);
+      }
+      if (visitedClasses.add(type.element)) {
+        if (type.superclass != null) {
+          recurse(type.superclass);
+        }
+        type.mixins.forEach(recurse);
+        type.interfaces.forEach(recurse);
+        visitedClasses.remove(type.element);
+      }
+    }
+    if (t1 is InterfaceType) {
+      recurse(t1);
+    }
+    return result;
+  }
+
+  /**
    * The given expression is the expression used to compute the iterator for a
    * for-each statement. Attempt to compute the type of objects that will be
    * assigned to the loop variable and return that type. Return `null` if the
    * type could not be determined. The [iteratorExpression] is the expression
    * that will return the Iterable being iterated over.
    */
   DartType _getIteratorElementType(Expression iteratorExpression) {
     DartType expressionType = iteratorExpression.bestType;
     if (expressionType is InterfaceType) {
       InterfaceType interfaceType = expressionType;
@@ skipping 4114 matching lines @@
     nonFields.add(node);
     return null;
   }
 
   @override
   Object visitNode(AstNode node) => node.accept(TypeResolverVisitor_this);
 
   @override
   Object visitWithClause(WithClause node) => null;
 }