Implement instance member inference

pkg/analyzer/lib/src/task/strong_mode.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.task.strong_mode;
 
+import 'dart:collection';
+
 import 'package:analyzer/src/generated/ast.dart';
 import 'package:analyzer/src/generated/element.dart';
+import 'package:analyzer/src/generated/resolver.dart';
 
 /**
  * An object used to find static variables whose types should be inferred and
  * classes whose members should have types inferred. Clients are expected to
  * visit a [CompilationUnit].
  */
 class InferrenceFinder extends SimpleAstVisitor {
   /**
    * The static variables that should have types inferred for them.
    */
@@ skipping 54 matching lines @@
    * refer to fields whose type was inferred.
    */
   void _addVariables(NodeList<VariableDeclaration> variables) {
     for (VariableDeclaration variable in variables) {
       if (variable.initializer != null) {
         staticVariables.add(variable.element);
       }
     }
   }
 }
+
+/**
+ * An object used to infer the type of instance fields and the return types of
+ * instance methods within a single compilation unit.
+ */
+class InstanceMemberInferrer {
+  /**
+   * The type provider used to look up types.
+   */
+  final TypeProvider typeProvider;
+
+  /**
+   * The type system used to compute the least upper bound of types.
+   */
+  TypeSystem typeSystem;
+
+  /**
+   * The inheritance manager used to find overridden method.
+   */
+  InheritanceManager inheritanceManager;
+
+  /**
+   * The classes that have been visited while attempting to infer the types of
+   * instance members of some base class. The base class will be the first
+   * element of the list, the current class will be the last.

[Leaf, 2015/08/22 00:06:55]

Are the references to ordering and list here out of date, or do Dart HashSets
double as lists?

[Brian Wilkerson, 2015/08/24 16:52:58]

It was out of date, and has been removed.

I was going to try to minimize the loss of information by keeping the order in
which we visited classes and only failing to infer in the actual cycle, but
decided that we could wait until later to decide whether that was worth doing.

+   */
+  HashSet<ClassElementImpl> elementsBeingInferred =
+      new HashSet<ClassElementImpl>();
+
+  /**
+   * Initialize a newly create inferrer.
+   */
+  InstanceMemberInferrer(this.typeProvider) {
+    typeSystem = new TypeSystemImpl(typeProvider);
+  }
+
+  /**
+   * Infer type information for all of the instance members in the given
+   * compilation [unit].
+   */
+  void inferCompilationUnit(CompilationUnitElement unit) {
+    inheritanceManager = new InheritanceManager(unit.library);
+    unit.types.forEach((ClassElement classElement) {
+      try {
+        _inferClass(classElement);
+      } on _CycleException {
+        // This is a short circuit return to prevent types that inherit from
+        // types containing a circular reference from being inferred.
+      }
+    });
+  }
+
+  /**
+   * Compute the best return type for a method that must be compatible with the
+   * return types of each of the given [overriddenMethods].
+   */
+  DartType _computeReturnType(List<ExecutableElement> overriddenMethods) {
+    DartType returnType = null;
+    int length = overriddenMethods.length;
+    for (int i = 0; i < length; i++) {
+      DartType type = _getReturnType(overriddenMethods[i]);
+      if (returnType == null) {
+        returnType = type;
+      } else {
+        if (returnType != type) {
+          return typeProvider.dynamicType;
+        }
+      }
+    }
+    return returnType == null ? typeProvider.dynamicType : returnType;
+  }
+
+  /**
+   * Return the element for the single parameter of the given [setter], or
+   * `null` if the executable element is not a setter or does not have a single

[Leaf, 2015/08/22 00:06:55]

This doesn't actually check that the executable element is a setter does it?

[Brian Wilkerson, 2015/08/24 16:52:57]

No, but it does now.

+   * parameter.
+   */
+  ParameterElement _getParameter(ExecutableElement setter) {
+    if (setter != null) {
+      List<ParameterElement> parameters = setter.parameters;
+      if (parameters.length == 1) {
+        return parameters[0];
+      }
+    }
+    return null;
+  }
+
+  DartType _getReturnType(ExecutableElement element) {
+    DartType returnType = element.returnType;
+    if (returnType == null) {
+      FunctionType functionType = element.type;

[Leaf, 2015/08/22 00:06:55]

When does this happen (we have no returnType, but do have a type which is a
FunctionType)?  The comment on ExecutableElement.returnType suggests that
returnType should only be null if the element model is not fully populated, is
that what's going on here?

[Brian Wilkerson, 2015/08/24 16:52:57]

In the absence of bugs, it doesn't. I was just being defensive (perhaps overly
so).

[Paul Berry, 2015/08/24 19:56:24]

FWIW, I think I would argue in this case that this is probably overly defensive,
since the implementation of FunctionType.returnType simply delegates (by way of
FunctionTypeImpl.baseReturnType) to Element.returnType.

[Brian Wilkerson, 2015/08/24 21:20:57]

Ok. I've removed it.

+      if (functionType != null) {
+        returnType = functionType.returnType;
+      }
+    }
+    if (returnType == null) {
+      return typeProvider.dynamicType;
+    }
+    return returnType;
+  }
+
+  /**
+   * If the given [accessorElement] represents a non-synthetic instance getter
+   * for which no return type was provided, infer the return type of the getter.
+   */
+  void _inferAccessor(PropertyAccessorElement accessorElement) {
+    if (!accessorElement.isSynthetic &&
+        accessorElement.isGetter &&
+        !accessorElement.isStatic &&
+        accessorElement.hasImplicitReturnType &&
+        _getReturnType(accessorElement).isDynamic) {
+      List<ExecutableElement> overriddenGetters = inheritanceManager
+          .lookupOverrides(
+              accessorElement.enclosingElement, accessorElement.name);
+      if (_onlyGetters(overriddenGetters)) {
+        DartType newType = _computeReturnType(overriddenGetters);
+        _setReturnType(accessorElement, newType);
+        (accessorElement.variable as FieldElementImpl).type = newType;
+        _setParameterType(accessorElement.correspondingSetter, newType);
+      }
+    }
+  }
+
+  /**
+   * Infer type information for all of the instance members in the given
+   * [classElement].
+   */
+  void _inferClass(ClassElement classElement) {
+    if (classElement is ClassElementImpl) {
+      if (classElement.hasBeenInferred) {
+        return;
+      }
+      if (!elementsBeingInferred.add(classElement)) {
+        // We have found a circularity in the class hierarchy. For now we just
+        // stop trying to infer any type information for any classes that
+        // inherit from any class in the cycle. We could potentially limit the
+        // algorithm to only not inferring types in the classes in the cycle,
+        // but it isn't clear that the results would be significantly better.
+        throw new _CycleException();
+      }
+      try {
+        //
+        // Ensure that all of instance members in the supertypes have had types
+        // inferred for them.
+        //
+        _inferType(classElement.supertype);
+        classElement.mixins.forEach(_inferType);
+        classElement.interfaces.forEach(_inferType);
+        if (classElement.hasBeenInferred) {

[Leaf, 2015/08/22 00:06:55]

Can this happen?  We know it was false on entry to this function and we've put
the classElement in the elementsBeingInferred set, so if any of the _inferType
calls reached this classElement again they should have thrown _CycleException
before reaching the code which sets hasBeenInferred.  Is there some other path
that can set this?

[Brian Wilkerson, 2015/08/24 16:52:57]

No, this was left over from when I was going to search for cycles. Good catch!

+          return;
+        }
+        //
+        // Then infer the types for the members.
+        //
+        classElement.fields.forEach(_inferField);
+        classElement.accessors.forEach(_inferAccessor);
+        classElement.methods.forEach(_inferMethod);
+        classElement.hasBeenInferred = true;
+      } finally {
+        elementsBeingInferred.remove(classElement);
+      }
+    }
+  }
+
+  /**
+   * If the given [fieldElement] represents a non-synthetic instance field for
+   * which no type was provided, infer the type of the field.
+   */
+  void _inferField(FieldElement fieldElement) {
+    if (!fieldElement.isSynthetic &&
+        !fieldElement.isStatic &&
+        fieldElement.hasImplicitType &&
+        fieldElement.type.isDynamic) {
+      //
+      // First look for overridden getters with the same name as the field.
+      //
+      List<ExecutableElement> overriddenGetters = inheritanceManager
+          .lookupOverrides(fieldElement.enclosingElement, fieldElement.name);
+      DartType newType = typeProvider.dynamicType;
+      if (_onlyGetters(overriddenGetters)) {
+        List<ExecutableElement> overriddenSetters = inheritanceManager
+            .lookupOverrides(
+                fieldElement.enclosingElement, fieldElement.name + '=');
+        newType = _computeReturnType(overriddenGetters);
+        if (!_isCompatible(newType, overriddenSetters)) {
+          newType = typeProvider.dynamicType;
+        }
+      }
+      //
+      // Then, if none was found, infer the type from the initialization
+      // expression.
+      //
+      if (newType.isDynamic && fieldElement.initializer != null) {

[Leaf, 2015/08/22 00:06:55]

I think we only want to do this if either this is not an override, or else if it
is final.  Consider:

class A {
  dynamic x;
}

class B extends A {
  var x = 3;
}

Inferring x as having type int will cause an error later on, since the setter
will not be a subtype of the setter from the supertype.  If x is final, it's ok,
and if x wasn't present in any of the superclasses it's ok.

[Brian Wilkerson, 2015/08/24 16:52:58]

Done

+        newType = fieldElement.initializer.returnType;

[Leaf, 2015/08/22 00:06:55]

The old code postponed doing this initializer based inference until after all of
the override based inference was completed.  I can't really see where this would
matter - the fields can't refer to each other right?  Are there any places this
could matter?

[Brian Wilkerson, 2015/08/24 16:52:58]

It's possible for the code to be invalid (and therefore have references to other
instance fields). Consider

class C {
  var f0 = 0;
  var f1 = f1 + 1;
}

I don't think that basing the inferred type of f1 on the non-inferred type of f0
will be a problem. I can't think of anything other than invalid code that could
be impacted.

+      }

[Leaf, 2015/08/22 00:06:55]

Siggi's code avoids inferring from the initializer when the type is bottom,
which I think is probably a good idea.  Is it an invariant that returnType won't
be bottom here?

[Brian Wilkerson, 2015/08/24 16:52:57]

No. I just saw that case while looking through the tests. I'll fix the code and
add a unit test.

+      (fieldElement as FieldElementImpl).type = newType;
+      _setReturnType(fieldElement.getter, newType);
+      _setParameterType(fieldElement.setter, newType);
+    }
+  }
+
+  /**
+   * If the given [methodElement] represents a non-synthetic instance method
+   * for which no return type was provided, infer the return type of the method.
+   */
+  void _inferMethod(MethodElement methodElement) {
+    if (!methodElement.isSynthetic &&
+        !methodElement.isStatic &&
+        methodElement.hasImplicitReturnType &&
+        _getReturnType(methodElement).isDynamic) {
+      List<ExecutableElement> overriddenMethods = inheritanceManager
+          .lookupOverrides(methodElement.enclosingElement, methodElement.name);
+      if (_onlyMethods(overriddenMethods)) {
+        MethodElementImpl element = methodElement as MethodElementImpl;
+        _setReturnType(element, _computeReturnType(overriddenMethods));
+      }
+    }
+  }
+
+  /**
+   * Infer type information for all of the instance members in the given
+   * interface [type].
+   */
+  void _inferType(InterfaceType type) {
+    if (type != null) {
+      ClassElement element = type.element;
+      if (element != null) {
+        _inferClass(element);
+      }
+    }
+  }
+
+  /**
+   * Return `true` if the given [type] is compatible with the argument types of
+   * all of the given [setters].
+   */
+  bool _isCompatible(DartType type, List<ExecutableElement> setters) {
+    for (ExecutableElement setter in setters) {
+      ParameterElement parameter = _getParameter(setter);
+      if (parameter != null && !type.isAssignableTo(parameter.type)) {

[Leaf, 2015/08/22 00:06:55]

Once we've added a type system, we need to make this be DDC assignability. 
Maybe add a TODO?  Also, I think this check is backwards (doesn't matter in
regular dart since it's a symmetric relation there, I think).  In DDC, we need
the new setter type (type -> void) to be a subtype of the superclass setter type
(parameter.type -> void), so we want parameter.type <: type.

[Brian Wilkerson, 2015/08/24 16:52:58]

Done

+        return false;
+      }
+    }
+    return true;
+  }
+
+  /**
+   * Return `true` if the list of [elements] contains only getters.
+   */
+  bool _onlyGetters(List<ExecutableElement> elements) {
+    for (ExecutableElement element in elements) {
+      if (!(element is PropertyAccessorElement && element.isGetter)) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  /**
+   * Return `true` if the list of [elements] contains only methods.
+   */
+  bool _onlyMethods(List<ExecutableElement> elements) {
+    for (ExecutableElement element in elements) {
+      if (element is! MethodElement) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  /**
+   * Set the type of the sole parameter of the given [element] to the given [type].
+   */
+  void _setParameterType(PropertyAccessorElement element, DartType type) {
+    if (element is PropertyAccessorElementImpl) {
+      ParameterElement parameter = _getParameter(element);
+      if (parameter is ParameterElementImpl) {
+        parameter.type = type;
+        FunctionType functionType = element.type;
+        if (functionType is FunctionTypeImpl) {
+          element.type =
+              new FunctionTypeImpl(element, functionType.prunedTypedefs);
+        }
+      }
+    }
+  }
+
+  /**
+   * Set the return type of the given [element] to the given [type].
+   */
+  void _setReturnType(ExecutableElement element, DartType type) {
+    if (element is ExecutableElementImpl) {
+      element.returnType = type;
+      FunctionType functionType = element.type;

[Leaf, 2015/08/22 00:06:55]

The code sequence from here down is duplicated above, and is fairly non-obvious
(to me) why it needs to be done.  Maybe factor out to a helper with a comment
(or just comment, even just a pointer to where to look for why this needs
doing)?

[Brian Wilkerson, 2015/08/24 16:52:57]

Comments added. (I can't easily abstract the code to a separate method because
ExecutableElementImpl and PropertyAccessorElementImpl don't have a common
supertype that defines the behavior I need.)

+      if (functionType is FunctionTypeImpl) {
+        element.type =
+            new FunctionTypeImpl(element, functionType.prunedTypedefs);
+      }
+    }
+  }
+}
+
+/**
+ * A class of exception that is not used anywhere else.
+ */
+class _CycleException implements Exception {}