Implement override-based type inference for instance methods.

pkg/front_end/lib/src/fasta/type_inference/type_inference_engine.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.md file.
 
 import 'package:front_end/src/base/instrumentation.dart';
 import 'package:front_end/src/dependency_walker.dart' as dependencyWalker;
 import 'package:front_end/src/fasta/errors.dart';
 import 'package:front_end/src/fasta/kernel/kernel_shadow_ast.dart';
 import 'package:front_end/src/fasta/type_inference/type_inference_listener.dart';
 import 'package:front_end/src/fasta/type_inference/type_inferrer.dart';
 import 'package:front_end/src/fasta/type_inference/type_schema_environment.dart';
 import 'package:kernel/ast.dart'
-    show Class, DartType, DynamicType, Field, InterfaceType, Member, Procedure;
+    show
+        Class,
+        DartType,
+        DynamicType,
+        Field,
+        FunctionType,
+        InterfaceType,
+        Member,
+        Procedure,
+        TypeParameter,
+        TypeParameterType;
 import 'package:kernel/class_hierarchy.dart';
 import 'package:kernel/core_types.dart';
 import 'package:kernel/type_algebra.dart';
 
 /// Data structure for tracking dependencies among fields, getters, and setters
 /// that require type inference.
 ///
 /// TODO(paulberry): see if it's possible to make this class more lightweight
 /// by changing the API so that the walker is passed to computeDependencies().
 /// (This should allow us to drop the _typeInferenceEngine field).
 class AccessorNode extends dependencyWalker.Node<AccessorNode> {
   final TypeInferenceEngineImpl _typeInferenceEngine;
 
   final KernelMember member;
 
   bool isImmediatelyEvident = false;
 
-  AccessorState state = AccessorState.NotInferredYet;
+  InferenceState state = InferenceState.NotInferredYet;
 
-  /// If [state] is [AccessorState.Inferring], and type inference for this
+  /// If [state] is [InferenceState.Inferring], and type inference for this
   /// accessor is waiting on type inference of some other accessor, the accessor
   /// that is being waited on.
   ///
   /// Otherwise `null`.
   AccessorNode currentDependency;
 
   final overrides = <Member>[];
 
   final crossOverrides = <Member>[];
 
   AccessorNode(this._typeInferenceEngine, this.member);
 
   get candidateOverrides => overrides.isNotEmpty ? overrides : crossOverrides;
 
   @override
-  bool get isEvaluated => state == AccessorState.Inferred;
+  bool get isEvaluated => state == InferenceState.Inferred;
 
   @override
   List<AccessorNode> computeDependencies() {
     return _typeInferenceEngine.computeAccessorDependencies(this);
   }
 
   @override
   String toString() => member.toString();
 }
 
-/// Enum tracking the type inference state of an accessor.
-enum AccessorState {
-  /// The accessor's type has not been inferred yet.
+/// Enum tracking the type inference state of an accessor or method.
+enum InferenceState {
+  /// The accessor or method's type has not been inferred yet.
   NotInferredYet,
 
-  /// Type inference is in progress for the accessor.
+  /// Type inference is in progress for the accessor or method.
   ///
   /// This means that code is currently on the stack which is attempting to
-  /// determine the type of the accessor.
+  /// determine the type of the accessor or method.
   Inferring,
 
-  /// The accessor's type has been inferred.
+  /// The accessor or method's type has been inferred.
   Inferred
 }
 
+/// Data structure for tracking dependencies among methods that require type
+/// inference.
+class MethodNode {
+  final KernelProcedure procedure;
+
+  InferenceState state = InferenceState.NotInferredYet;
+
+  final overrides = <Procedure>[];
+
+  MethodNode(this.procedure);
+
+  @override
+  String toString() => procedure.toString();
+}
+
 /// Keeps track of the global state for the type inference that occurs outside
 /// of method bodies and initalizers.
 ///
 /// This class describes the interface for use by clients of type inference
 /// (e.g. DietListener).  Derived classes should derive from
 /// [TypeInferenceEngineImpl].
 abstract class TypeInferenceEngine {
   ClassHierarchy get classHierarchy;
 
   CoreTypes get coreTypes;
@@ skipping 54 matching lines @@
   ///
   /// Requires [fusedTopLevelInference] to be `true`.
   static const bool fullTopLevelInference = true;
 
   final Instrumentation instrumentation;
 
   final bool strongMode;
 
   final accessorNodes = <AccessorNode>[];
 
+  final methodNodes = <MethodNode>[];
+
   final initializingFormals = <KernelVariableDeclaration>[];
 
   @override
   CoreTypes coreTypes;
 
   @override
   ClassHierarchy classHierarchy;
 
   TypeSchemaEnvironment typeSchemaEnvironment;
 
@@ skipping 47 matching lines @@
     } else {
       // Member is a getter/setter that doesn't override anything, so we can't
       // infer a type for it; therefore it has no dependencies.
       return const [];
     }
   }
 
   /// Creates an [AccessorNode] to track dependencies of the given [member].
   AccessorNode createAccessorNode(KernelMember member);
 
+  /// Creates a [MethodNode] to track dependencies of the given [procedure].
+  MethodNode createMethodNode(KernelProcedure procedure);
+
   @override
   void finishTopLevel() {
+    for (var methodNode in methodNodes) {
+      inferMethodIfNeeded(methodNode);
+    }
     for (var accessorNode in accessorNodes) {
       if (fusedTopLevelInference) {
         assert(expandedTopLevelInference);
         inferAccessorFused(accessorNode, null);
       } else {
         if (accessorNode.isEvaluated) continue;
         new _AccessorWalker().walk(accessorNode);
       }
     }
     for (var formal in initializingFormals) {
       formal.type = _inferInitializingFormalType(formal);
     }
   }
 
   /// Retrieve the [TypeInferrer] for the given [member], which was created by
   /// a previous call to [createTopLevelTypeInferrer].
   TypeInferrerImpl getMemberTypeInferrer(KernelMember member);
 
+  DartType getNamedParameterType(FunctionType functionType, String name) {
+    return functionType.getNamedParameter(name) ?? const DynamicType();
+  }
+
+  DartType getPositionalParameterType(FunctionType functionType, int i) {
+    if (i < functionType.positionalParameters.length) {
+      return functionType.positionalParameters[i];
+    } else {
+      return const DynamicType();

[Siggi Cherem (dart-lang), 2017/06/21 20:19:08]

report an error instead? (same thing when the name is not found in
getNamedParameterType?)

Do we want to check this preemtively when we call recordOverride? or we prefer
to do it here so we can still infer a type for the other arguments that do
match?

(also, I'm not sure if this is already specified in Leaf doc, or if we need to
add it there)

[Paul Berry, 2017/06/21 20:54:47]

Good question--I should have been clearer here.  Leaf's doc says:

"If there is no corresponding parameter position in the overridden method to
infer from and the signatures are compatible, it is treated as dynamic (e.g.
overriding a one parameter method with a method that takes a second optional
parameter).  Note: if there is no corresponding parameter position in the
overriden method to infer from and the signatures are incompatible (e.g.
overriding a one parameter method with a method that takes a second non-optional
parameter), the inference result is not defined and tools are free to either
emit an error, or to defer the error to override checking."

So I think we're ok.  For the case where the parameter is optional, we're
treating the type as dynamic, as per spec.  For the case where the parameter is
non-optional, we're deferring the error to override checking, which the spec
allows.

I've added a comment to clarify.  The comment is at the call site because in a
follow up CL I'm planning to move getPositionalParameterType out of this file to
reduce code duplication.

+    }
+  }
+
   /// Performs type inference on the given [accessorNode].
   void inferAccessor(AccessorNode accessorNode) {
-    assert(accessorNode.state == AccessorState.NotInferredYet);
-    accessorNode.state = AccessorState.Inferring;
+    assert(accessorNode.state == InferenceState.NotInferredYet);
+    accessorNode.state = InferenceState.Inferring;
     var member = accessorNode.member;
     if (strongMode) {
       var inferredType = tryInferAccessorByInheritance(accessorNode);
       var typeInferrer = getMemberTypeInferrer(member);
       if (inferredType == null) {
         if (member is KernelField) {
           typeInferrer.isImmediatelyEvident = true;
           inferredType = accessorNode.isImmediatelyEvident
               ? typeInferrer.inferDeclarationType(
                   typeInferrer.inferFieldTopLevel(member, null, true))
               : const DynamicType();
           if (!typeInferrer.isImmediatelyEvident) {
             inferredType = const DynamicType();
           }
         } else {
           inferredType = const DynamicType();
         }
       }
-      if (accessorNode.state == AccessorState.Inferred) {
+      if (accessorNode.state == InferenceState.Inferred) {
         // A circularity must have been detected; at the time it was detected,
         // inference for this node was completed.
         return;
       }
       member.setInferredType(this, typeInferrer.uri, inferredType);
     }
-    accessorNode.state = AccessorState.Inferred;
+    accessorNode.state = InferenceState.Inferred;
     // TODO(paulberry): if type != null, then check that the type of the
     // initializer is assignable to it.
     // TODO(paulberry): the following is a hack so that outlines don't contain
     // initializers.  But it means that we rebuild the initializers when doing
     // a full compile.  There should be a better way.
     if (member is KernelField) {
       member.initializer = null;
     }
   }
 
   /// Makes a note that the given [accessorNode] is part of a circularity, so
   /// its type can't be inferred.
   void inferAccessorCircular(AccessorNode accessorNode) {
     var member = accessorNode.member;
     // TODO(paulberry): report the appropriate error.
     var uri = getMemberTypeInferrer(member).uri;
-    accessorNode.state = AccessorState.Inferred;
+    accessorNode.state = InferenceState.Inferred;
     member.setInferredType(this, uri, const DynamicType());
     // TODO(paulberry): the following is a hack so that outlines don't contain
     // initializers.  But it means that we rebuild the initializers when doing
     // a full compile.  There should be a better way.
     if (member is KernelField) {
       member.initializer = null;
     }
   }
 
   /// Performs fused type inference on the given [accessorNode].
   void inferAccessorFused(AccessorNode accessorNode, AccessorNode dependant) {
     switch (accessorNode.state) {
-      case AccessorState.Inferred:
+      case InferenceState.Inferred:
         // Already inferred.  Nothing to do.
         break;
-      case AccessorState.Inferring:
+      case InferenceState.Inferring:
         // An accessor depends on itself (possibly by way of intermediate
         // accessors).  Mark all accessors involved as circular and infer a type
         // of `dynamic` for them.
         var node = accessorNode;
         while (node != null) {
           var nextNode = node.currentDependency;
           inferAccessorCircular(node);
           node.currentDependency = null;
           node = nextNode;
         }
         break;
-      case AccessorState.NotInferredYet:
+      case InferenceState.NotInferredYet:
         // Mark the "dependant" accessor (if any) as depending on this one, and
         // invoke accessor inference for this node.
         dependant?.currentDependency = accessorNode;
         // All accessors are "immediately evident" when doing fused inference.
         accessorNode.isImmediatelyEvident = true;
         inferAccessor(accessorNode);
         dependant?.currentDependency = null;
         break;
     }
   }
 
+  /// Performs type inference on the given [methodNode].
+  void inferMethodIfNeeded(MethodNode methodNode) {
+    switch (methodNode.state) {
+      case InferenceState.Inferred:
+        // Already inferred.  Nothing to do.
+        break;
+      case InferenceState.Inferring:
+        // An method depends on itself (possibly by way of intermediate
+        // methods).  This should never happen, because it would require a
+        // circular class hierarchy (which Fasta prevents).
+        internalError('Circular method inference');
+        break;
+      case InferenceState.NotInferredYet:
+        methodNode.state = InferenceState.Inferring;
+        _inferMethod(methodNode);
+        methodNode.state = InferenceState.Inferred;
+        break;
+    }
+  }
+
   @override
   void prepareTopLevel(CoreTypes coreTypes, ClassHierarchy hierarchy) {
     this.coreTypes = coreTypes;
     this.classHierarchy = hierarchy;
     this.typeSchemaEnvironment =
         new TypeSchemaEnvironment(coreTypes, hierarchy, strongMode);
   }
 
   @override
   void recordInitializingFormal(KernelVariableDeclaration formal) {
     initializingFormals.add(formal);
   }
 
   @override
   void recordMember(KernelMember member) {
-    accessorNodes.add(createAccessorNode(member));
+    if (member is KernelProcedure && !member.isGetter && !member.isSetter) {
+      methodNodes.add(createMethodNode(member));
+    } else {
+      accessorNodes.add(createAccessorNode(member));
+    }
   }
 
   DartType tryInferAccessorByInheritance(AccessorNode accessorNode) {
     DartType inferredType;
     for (var override in accessorNode.candidateOverrides) {
       var nextInferredType =
           _computeOverriddenAccessorType(override, accessorNode);
       if (inferredType == null) {
         inferredType = nextInferredType;
       } else if (inferredType != nextInferredType) {
         // Overrides don't have matching types.
         // TODO(paulberry): report an error
         return const DynamicType();
       }
     }
     return inferredType;
   }
 
+  List<FunctionType> _computeMethodOverriddenTypes(MethodNode methodNode) {
+    var overriddenTypes = <FunctionType>[];
+    for (var override in methodNode.overrides) {
+      MethodNode overrideNode = KernelProcedure.getMethodNode(override);
+      if (overrideNode != null) {
+        inferMethodIfNeeded(overrideNode);
+      }
+      if (override.function == null) {
+        // This can happen if there are errors.  Just skip this override.
+        continue;
+      }
+      var overriddenType = override.function.functionType;
+      var superclass = override.enclosingClass;
+      if (!superclass.typeParameters.isEmpty) {
+        var thisClass = methodNode.procedure.enclosingClass;
+        var superclassInstantiation = classHierarchy
+            .getClassAsInstanceOf(thisClass, superclass)
+            .asInterfaceType;
+        overriddenType = Substitution
+            .fromInterfaceType(superclassInstantiation)
+            .substituteType(overriddenType);
+      }
+      var methodTypeParameters = methodNode.procedure.function.typeParameters;
+      if (overriddenType.typeParameters.length != methodTypeParameters.length) {
+        // Generic arity mismatch.  Don't do any inference for this method.
+        // TODO(paulberry): report an error.
+        return <FunctionType>[];
+      } else if (overriddenType.typeParameters.isNotEmpty) {
+        var substitutionMap = <TypeParameter, DartType>{};
+        for (int i = 0; i < methodTypeParameters.length; i++) {
+          substitutionMap[overriddenType.typeParameters[i]] =
+              new TypeParameterType(methodTypeParameters[i]);
+        }
+        overriddenType = substituteTypeParams(
+            overriddenType, substitutionMap, methodTypeParameters);
+      }
+      overriddenTypes.add(overriddenType);
+    }
+    return overriddenTypes;
+  }
+
   DartType _computeOverriddenAccessorType(
       Member override, AccessorNode accessorNode) {
     if (fusedTopLevelInference) {
       AccessorNode dependency = KernelMember.getAccessorNode(override);
       if (dependency != null) {
         inferAccessorFused(dependency, accessorNode);
       }
     }
     DartType overriddenType;
     if (override is Field) {
@@ skipping 25 matching lines @@
     assert(KernelVariableDeclaration.isImplicitlyTyped(formal));
     Class enclosingClass = formal.parent.parent.parent;
     for (var field in enclosingClass.fields) {
       if (field.name.name == formal.name) {
         return field.type;
       }
     }
     // No matching field.  The error should be reported elsewhere.
     return const DynamicType();
   }
+
+  void _inferMethod(MethodNode methodNode) {
+    var typeInferrer = getMemberTypeInferrer(methodNode.procedure);
+
+    // First collect types of overridden methods
+    var overriddenTypes = _computeMethodOverriddenTypes(methodNode);
+
+    // Now infer types.
+    DartType matchTypes(Iterable<DartType> types) {
+      if (!strongMode) return const DynamicType();
+      var iterator = types.iterator;
+      if (!iterator.moveNext()) {
+        // No overridden types.  Infer `dynamic`.
+        return const DynamicType();
+      }
+      var inferredType = iterator.current;
+      while (iterator.moveNext()) {
+        if (inferredType != iterator.current) {
+          // TODO(paulberry): Types don't match.  Report an error.

[Siggi Cherem (dart-lang), 2017/06/21 20:19:08]

Random questions:

When not doing inference, are there checks elsewhere about types being
consistent? When doing inference, does this mean we compute the overriden types
twice (once here and once to do the check later in the compiler)? If so, do we
care or want to try to avoid doing it twice? I can imagine we could compute
overriden types lazily as needed here and rely on the regular checker to detect
when types don't match, but I'm not sure if that's really feasible and how much
it helps (it might make it harder to produce good error messages). 

I don't believe there is anything to change here, but just wanted to ask in case
you already have plans in mind.

[Paul Berry, 2017/06/21 20:54:47]

Peter has added some checks, but I believe that he has been focusing on things
that are spec mode errors, so probably most of the checks you are talking about
are not written yet.

I haven't thought too hard about how those checks should work yet.  My suspicion
is that the computational cost of computing the overridden types twice is going
to be small (since the slow cases all involve generics, which are used less
frequently), but I'm open to trying to avoid redundant work if it turns out to
be a bottleneck.

+          return const DynamicType();
+        }
+      }
+      return inferredType;
+    }
+
+    if (KernelProcedure.hasImplicitReturnType(methodNode.procedure)) {
+      var inferredType =
+          matchTypes(overriddenTypes.map((type) => type.returnType));
+      instrumentation?.record(
+          Uri.parse(typeInferrer.uri),
+          methodNode.procedure.fileOffset,
+          'topType',
+          new InstrumentationValueForType(inferredType));
+      methodNode.procedure.function.returnType = inferredType;
+    }
+    var positionalParameters =
+        methodNode.procedure.function.positionalParameters;
+    for (int i = 0; i < positionalParameters.length; i++) {
+      if (KernelVariableDeclaration
+          .isImplicitlyTyped(positionalParameters[i])) {
+        var inferredType = matchTypes(
+            overriddenTypes.map((type) => getPositionalParameterType(type, i)));
+        instrumentation?.record(
+            Uri.parse(typeInferrer.uri),
+            positionalParameters[i].fileOffset,
+            'topType',
+            new InstrumentationValueForType(inferredType));
+        positionalParameters[i].type = inferredType;
+      }
+    }
+    var namedParameters = methodNode.procedure.function.namedParameters;
+    for (int i = 0; i < namedParameters.length; i++) {
+      if (KernelVariableDeclaration.isImplicitlyTyped(namedParameters[i])) {
+        var name = namedParameters[i].name;
+        var inferredType = matchTypes(
+            overriddenTypes.map((type) => getNamedParameterType(type, name)));
+        instrumentation?.record(
+            Uri.parse(typeInferrer.uri),
+            namedParameters[i].fileOffset,
+            'topType',
+            new InstrumentationValueForType(inferredType));
+        namedParameters[i].type = inferredType;
+      }
+    }
+  }
 }
 
 /// Subtype of [dependencyWalker.DependencyWalker] which is specialized to
 /// perform top level type inference.
 class _AccessorWalker extends dependencyWalker.DependencyWalker<AccessorNode> {
   _AccessorWalker();
 
   @override
   void evaluate(AccessorNode f) {
     f._typeInferenceEngine.inferAccessor(f);
   }
 
   @override
   void evaluateScc(List<AccessorNode> scc) {
     // Mark every accessor as part of a circularity.
     for (var f in scc) {
       f._typeInferenceEngine.inferAccessorCircular(f);
     }
   }
 }