Refactor least upper bound computation; support bottom correctly.

pkg/analyzer/lib/src/generated/element.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.
 
 // This code was auto-generated, is not intended to be edited, and is subject to
 // significant change. Please see the README file for more information.
 
 library engine.element;
 
 import 'dart:collection';
@@ skipping 2031 matching lines @@
 
   /**
    * Return the name of this type, or `null` if the type does not have a name,
    * such as when the type represents the type of an unnamed function.
    */
   String get name;
 
   /**
    * Return the least upper bound of this type and the given [type], or `null`
    * if there is no least upper bound.
+   *
+   * Deprecated, since it is impossible to implement the correct algorithm
+   * without access to a [TypeProvider].  Please use
+   * [TypeSystem.getLeastUpperBound] instead.
    */
+  @deprecated
   DartType getLeastUpperBound(DartType type);
 
   /**
    * Return `true` if this type is assignable to the given [type]. A type
    * <i>T</i> may be assigned to a type <i>S</i>, written <i>T</i> &hArr;
    * <i>S</i>, iff either <i>T</i> <: <i>S</i> or <i>S</i> <: <i>T</i>.
    */
   bool isAssignableTo(DartType type);
 
   /**
@@ skipping 3185 matching lines @@
     newType.typeArguments =
         TypeImpl.substitute(typeArguments, argumentTypes, parameterTypes);
     return newType;
   }
 
   @override
   FunctionTypeImpl substitute3(List<DartType> argumentTypes) =>
       substitute2(argumentTypes, typeArguments);
 
   /**
+   * Compute the least upper bound of types [f] and [g], both of which are
+   * known to be function types.
+   *
+   * In the event that f and g have different numbers of required parameters,
+   * `null` is returned, in which case the least upper bound is the interface
+   * type `Function`.
+   */
+  static FunctionType computeLeastUpperBound(FunctionType f, FunctionType g) {
+    // TODO(paulberry): implement this.
+    return null;
+  }
+
+  /**
    * Return `true` if all of the name/type pairs in the first map ([firstTypes])
    * are equal to the corresponding name/type pairs in the second map
    * ([secondTypes]). The maps are expected to iterate over their entries in the
    * same order in which those entries were added to the map.
    */
   static bool _equals(
       Map<String, DartType> firstTypes, Map<String, DartType> secondTypes) {
     if (secondTypes.length != firstTypes.length) {
       return false;
     }
@@ skipping 535 matching lines @@
    * set of superinterfaces of <i>I<i>, let <i>S<sub>J</sub></i> be the set of
    * superinterfaces of <i>J</i> and let <i>S = (I &cup; S<sub>I</sub>) &cap;
    * (J &cup; S<sub>J</sub>)</i>. Furthermore, we define <i>S<sub>n</sub> =
    * {T | T &isin; S &and; depth(T) = n}</i> for any finite <i>n</i>, where
    * <i>depth(T)</i> is the number of steps in the longest inheritance path from
    * <i>T</i> to <i>Object</i>. Let <i>q</i> be the largest number such that
    * <i>S<sub>q</sub></i> has cardinality one. The least upper bound of <i>I</i>
    * and <i>J</i> is the sole element of <i>S<sub>q</sub></i>.
    */
   @override
+  @deprecated
   DartType getLeastUpperBound(DartType type);
 
   /**
    * Return the element representing the method with the given [name] that is
    * declared in this class, or `null` if this class does not declare a method
    * with the given name.
    */
   MethodElement getMethod(String name);
 
   /**
@@ skipping 184 matching lines @@
   /**
    * Returns a "smart" version of the "least upper bound" of the given types.
    *
    * If these types have the same element and differ only in terms of the type
    * arguments, attempts to find a compatible set of type arguments.
    *
    * Otherwise, calls [DartType.getLeastUpperBound].
    */
   static InterfaceType getSmartLeastUpperBound(
       InterfaceType first, InterfaceType second) {
+    // TODO(paulberry): this needs to be deprecated and replaced with a method
+    // in [TypeSystem], since it relies on the deprecated functionality of
+    // [DartType.getLeastUpperBound].
     if (first.element == second.element) {
       return _leastUpperBound(first, second);
     }
     return first.getLeastUpperBound(second);
   }
 
   /**
    * Return the "least upper bound" of the given types under the assumption that
    * the types have the same element and differ only in terms of the type
    * arguments.
@@ skipping 256 matching lines @@
       }
       buffer.write(">");
     }
   }
 
   @override
   PropertyAccessorElement getGetter(String getterName) => PropertyAccessorMember
       .from((element as ClassElementImpl).getGetter(getterName), this);
 
   @override
+  @deprecated
   DartType getLeastUpperBound(DartType type) {
     // quick check for self
     if (identical(type, this)) {
       return this;
     }
     // dynamic
     DartType dynamicType = DynamicTypeImpl.instance;
     if (identical(this, dynamicType) || identical(type, dynamicType)) {
       return dynamicType;
     }
     // TODO (jwren) opportunity here for a better, faster algorithm if this
     // turns out to be a bottle-neck
     if (type is! InterfaceType) {
       return null;
     }
-    // new names to match up with the spec
-    InterfaceType i = this;
-    InterfaceType j = type as InterfaceType;
-    // compute set of supertypes
-    Set<InterfaceType> si = computeSuperinterfaceSet(i);
-    Set<InterfaceType> sj = computeSuperinterfaceSet(j);
-    // union si with i and sj with j
-    si.add(i);
-    sj.add(j);
-    // compute intersection, reference as set 's'
-    List<InterfaceType> s = _intersection(si, sj);
-    // for each element in Set s, compute the largest inheritance path to Object
-    List<int> depths = new List<int>.filled(s.length, 0);
-    int maxDepth = 0;
-    for (int n = 0; n < s.length; n++) {
-      depths[n] = computeLongestInheritancePathToObject(s[n]);
-      if (depths[n] > maxDepth) {
-        maxDepth = depths[n];
-      }
-    }
-    // ensure that the currently computed maxDepth is unique,
-    // otherwise, decrement and test for uniqueness again
-    for (; maxDepth >= 0; maxDepth--) {
-      int indexOfLeastUpperBound = -1;
-      int numberOfTypesAtMaxDepth = 0;
-      for (int m = 0; m < depths.length; m++) {
-        if (depths[m] == maxDepth) {
-          numberOfTypesAtMaxDepth++;
-          indexOfLeastUpperBound = m;
-        }
-      }
-      if (numberOfTypesAtMaxDepth == 1) {
-        return s[indexOfLeastUpperBound];
-      }
-    }
-    // illegal state, log and return null- Object at maxDepth == 0 should always
-    // return itself as the least upper bound.
-    // TODO (jwren) log the error state
-    return null;
+    return computeLeastUpperBound(this, type);
   }
 
   @override
   MethodElement getMethod(String methodName) => MethodMember.from(
       (element as ClassElementImpl).getMethod(methodName), this);
 
   @override
   PropertyAccessorElement getSetter(String setterName) => PropertyAccessorMember
       .from((element as ClassElementImpl).getSetter(setterName), this);
 
@@ skipping 326 matching lines @@
     InterfaceTypeImpl newType = new InterfaceTypeImpl(element, prune);
     newType.typeArguments = newTypeArguments;
     return newType;
   }
 
   @override
   InterfaceTypeImpl substitute4(List<DartType> argumentTypes) =>
       substitute2(argumentTypes, typeArguments);
 
   /**
+   * Compute the least upper bound of types [i] and [j], both of which are
+   * known to be interface types.
+   *
+   * In the event that the algorithm fails (which might occur due to a bug in
+   * the analyzer), `null` is returned.
+   */
+  static InterfaceType computeLeastUpperBound(
+      InterfaceType i, InterfaceType j) {
+    // compute set of supertypes
+    Set<InterfaceType> si = computeSuperinterfaceSet(i);
+    Set<InterfaceType> sj = computeSuperinterfaceSet(j);
+    // union si with i and sj with j
+    si.add(i);
+    sj.add(j);
+    // compute intersection, reference as set 's'
+    List<InterfaceType> s = _intersection(si, sj);
+    // for each element in Set s, compute the largest inheritance path to Object
+    List<int> depths = new List<int>.filled(s.length, 0);
+    int maxDepth = 0;
+    for (int n = 0; n < s.length; n++) {
+      depths[n] = computeLongestInheritancePathToObject(s[n]);
+      if (depths[n] > maxDepth) {
+        maxDepth = depths[n];
+      }
+    }
+    // ensure that the currently computed maxDepth is unique,
+    // otherwise, decrement and test for uniqueness again
+    for (; maxDepth >= 0; maxDepth--) {
+      int indexOfLeastUpperBound = -1;
+      int numberOfTypesAtMaxDepth = 0;
+      for (int m = 0; m < depths.length; m++) {
+        if (depths[m] == maxDepth) {
+          numberOfTypesAtMaxDepth++;
+          indexOfLeastUpperBound = m;
+        }
+      }
+      if (numberOfTypesAtMaxDepth == 1) {
+        return s[indexOfLeastUpperBound];
+      }
+    }
+    // Should be impossible--there should always be exactly one type with the
+    // maximum depth.
+    assert(false);
+    return null;
+  }
+
+  /**
    * Return the length of the longest inheritance path from the given [type] to
    * Object.
    *
-   * See [InterfaceType.getLeastUpperBound].
+   * See [computeLeastUpperBound].
    */
   static int computeLongestInheritancePathToObject(InterfaceType type) =>
       _computeLongestInheritancePathToObject(
           type, 0, new HashSet<ClassElement>());
 
   /**
    * Returns the set of all superinterfaces of the given [type].
    *
-   * See [getLeastUpperBound].
+   * See [computeLeastUpperBound].
    */
   static Set<InterfaceType> computeSuperinterfaceSet(InterfaceType type) =>
       _computeSuperinterfaceSet(type, new HashSet<InterfaceType>());
 
   /**
    * Return the length of the longest inheritance path from a subtype of the
    * given [type] to Object, where the given [depth] is the length of the
    * longest path from the subtype to this type. The set of [visitedTypes] is
    * used to prevent infinite recursion in the case of a cyclic type structure.
    *
-   * See [computeLongestInheritancePathToObject], and [getLeastUpperBound].
+   * See [computeLongestInheritancePathToObject], and [computeLeastUpperBound].
    */
   static int _computeLongestInheritancePathToObject(
       InterfaceType type, int depth, HashSet<ClassElement> visitedTypes) {
     ClassElement classElement = type.element;
     // Object case
     if (classElement.supertype == null || visitedTypes.contains(classElement)) {
       return depth;
     }
     int longestPath = 1;
     try {
@@ skipping 23 matching lines @@
     } finally {
       visitedTypes.remove(classElement);
     }
     return longestPath;
   }
 
   /**
    * Add all of the superinterfaces of the given [type] to the given [set].
    * Return the [set] as a convenience.
    *
-   * See [computeSuperinterfaceSet], and [getLeastUpperBound].
+   * See [computeSuperinterfaceSet], and [computeLeastUpperBound].
    */
   static Set<InterfaceType> _computeSuperinterfaceSet(
       InterfaceType type, HashSet<InterfaceType> set) {
     Element element = type.element;
     if (element != null) {
       List<InterfaceType> superinterfaces = type.interfaces;
       for (InterfaceType superinterface in superinterfaces) {
         if (set.add(superinterface)) {
           _computeSuperinterfaceSet(superinterface, set);
         }
@@ skipping 3673 matching lines @@
 
   @override
   void visitElement(Element element) {
     int offset = element.nameOffset;
     if (offset != -1) {
       map[offset] = element;
     }
     super.visitElement(element);
   }
 }