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 {

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

I have a broad concern about this implementation strategy: previously, all of
our analysis tasks have had the property that they only set fields in the
element model that were previously null, and they express all their dependencies
using the task model.  That had the advantage that if a subtle dependency change
causes us to re-execute some tasks that we've executed previously, we can be
confident that the results from the previous execution won't pollute the results
of the re-execution.

The algorithm in this class doesn't have that property, since it decided which
types to infer based on looking for types that are "dynamic", and then it
*replaces* those types with the inferred types.  This means that if type
inference is re-run, it won't re-infer already-inferred types.  I worry about a
situation arising where, for example, class A extends class B, and a change to
class B requires inference to be re-run on class A, but since class A has
already had inference run on it once before, it will not re-infer properly.

This probably isn't a problem today because changing class B will cause class
A's element model to be re-built from scratch (wiping out any inference
results), but one day we might try to make things more incremental, and that
could cause subtle breakages.  Similar problems might arise if the type of a
declaration in class A is in turn inferred from some other elements.

Consider adding a TODO comment to capture some of these issues.  In the future
we might want the element model to keep track of a "preliminary type" distinct
from the "static type" in order to avoid these problems.

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

I added you comments (reworded slightly) as a comment in the class.

[Leaf, 2015/08/24 21:32:09]

Just as a passing comment - we've discussed keeping track of what types were
inferred (and why), which might also provide a handle on addressing this.

+  /**
+   * 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.
+   */
+  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++) {

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

Why not "for (DartType type in overriddenMethods)"?

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

Historic reasons that no longer apply. I'm happy to change it if you'd like.

+      DartType type = _getReturnType(overriddenMethods[i]);
+      if (returnType == null) {
+        returnType = type;
+      } else {
+        if (returnType != type) {

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

If I understand correctly, this means that if there are multiple overridden
methods declaring different return types, we will infer "dynamic"; is that
correct?

If so, consider adding an explanatory comment to this effect, since a casual
reader might expect us to do some sort of "greatest lower bound" computation
here.

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

Done

+          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
+   * parameter.
+   */
+  ParameterElement _getParameter(ExecutableElement setter) {
+    if (setter is PropertyAccessorElement && setter.isSetter) {
+      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;
+      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();

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

I'm concerned that this will lead to nondeterministic results when a circularity
exists, since the order in which we visit classes will determine which classes
get evaluated before the _CycleException is thrown.

Maybe we should consider using the task model to handle the circularities, since
it already has the capability of resuming analysis in a deterministic fashion
when a circularity is found.

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

I can't think of a case where there is any nondeterminism, can you?.

If we try to infer types for members of a class C and there is a circularity in
the inheritance structure, then none of the members of C will be inferred. (In
other words, we only infer members for a class if all of that classes supertypes
can be inferred.) If we cannot infer members for a class C then we will not
infer members for any subtype of C.

If the members of a supertype of C are successfully inferred in the process of
inferring members for C, then it must be the case that neither that class nor
any of its superclasses are involved in any circularity, and hence would have
had member types inferred in exactly the same way no matter when the inference
were done.

+      }
+      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);
+        //
+        // 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 = null;
+      if (_onlyGetters(overriddenGetters)) {
+        List<ExecutableElement> overriddenSetters = inheritanceManager
+            .lookupOverrides(
+                fieldElement.enclosingElement, fieldElement.name + '=');
+        newType = _computeReturnType(overriddenGetters);
+        if (!_isCompatible(newType, overriddenSetters)) {
+          newType = null;
+        }
+      }
+      //
+      // Then, if none was found, infer the type from the initialization
+      // expression.
+      //
+      if (newType == null) {
+        if (fieldElement.initializer != null &&
+            (fieldElement.isFinal || overriddenGetters.isEmpty)) {
+          newType = fieldElement.initializer.returnType;
+        }
+      }
+      if (newType != null && !newType.isBottom) {
+        (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 && !typeSystem.isSubtypeOf(parameter.type, type)) {
+        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 elements.isNotEmpty;

[Leaf, 2015/08/24 18:24:48]

I can't work out why this matters, nor why it should be different for
_onlyGetters vs _onlyMethods.  What's happening here?  

The comment should probably be updated as well " ... is non-empty and contains
only getters".

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

I'm confused by this too.  If the non-empty behavior is crucial here, it would
be nice to have a comment explaining why; also, I think it would be worth
changing the name of the method, since I believe the default assumption when
seeing a method called "_onlyGetters" would be to assume that the empty list
vacuously satisfies this query.

Alternatively, move the non-empty check to the call site so there won't be any
confusion (e.g. line 199 changes to "if (overriddenGetters.isNotEmpty &&
_onlyGetters(overriddenGetters))").

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

When _computeReturnType is passed an empty list it will return 'dynamic', which
causes a problem in _inferField because then we cannot tell whether or not to
infer based on the initializer. I thought it would be better to solve the
problem by not passing in an empty list, and this was a convenient place to add
that check. I've moved the check to the call sites in the hope that it's more
readable.

We don't have that issue with methods because if we cannot infer the return type
from an overridden method we revert to the default of 'dynamic' anyway.
Done.

[Leaf, 2015/08/24 21:32:09]

Ah, missed that, makes sense.  I think this way of writing it is clearer though,
thanks.  But now the comment is wrong again... :}

+  }
+
+  /**
+   * 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) {
+        //
+        // Update the type of the parameter.
+        //
+        parameter.type = type;
+        //
+        // Update the type of the setter to reflect the new parameter 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) {
+      //
+      // Update the return type of the element, which is stored in two places:
+      // directly in the element and indirectly in the type of the element.
+      //
+      element.returnType = type;
+      FunctionType functionType = element.type;
+      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 {}