Issue 28100. Implement new strong mode instantiate to bound rules in analyzer.

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

Index: pkg/analyzer/lib/src/generated/type_system.dart
diff --git a/pkg/analyzer/lib/src/generated/type_system.dart b/pkg/analyzer/lib/src/generated/type_system.dart
index af7319888abb1324268ad314fce4fe792a13b473..f1abdf5c2d5321acc8d0a1daaab6b0bea114dbda 100644
--- a/pkg/analyzer/lib/src/generated/type_system.dart
+++ b/pkg/analyzer/lib/src/generated/type_system.dart
@@ -422,32 +422,80 @@ class StrongTypeSystemImpl extends TypeSystem {
    * each Ti in Bi with dynamic to get Ii, and then replacing Ti with
    * Ii in all of the remaining bounds.

[Leaf, 2017/01/20 20:31:53]

It's probably fine for now to have this on type_system.  I think it might be
worth eventually making this be a lazily computed property on the element for
classes, typedefs, and generic functions though, since you should be able to
compute this once per definition rather than once per use.  Maybe put a TODO
with a comment to that effect?

[scheglov, 2017/01/21 02:11:23]

Done.

    */
-  DartType instantiateToBounds(DartType type) {
+  DartType instantiateToBounds(DartType type, {List<bool> hasError}) {

[Leaf, 2017/01/20 20:31:52]

Is this just to avoid a breaking change to the API?  Otherwise couldn't you
return null?  It's a shame that this is the best way we have of doing out
params. :(

[scheglov, 2017/01/21 02:11:23]

I cannot return `null`.
This method should return a type.
If the type is malbounded, we replace all its type parameters with `dynamic`.

Maybe something like ValuePtr<T> would be better.

     List<TypeParameterElement> typeFormals = typeFormalsAsElements(type);
     int count = typeFormals.length;
     if (count == 0) {
       return type;
     }
 
-    // We build up a substitution replacing bound parameters with
-    // their instantiated bounds, {substituted/variables}
-    List<DartType> substituted = new List<DartType>();
-    List<DartType> variables = new List<DartType>();
+    List<TypeParameterType> getFreeParameters(DartType type) {

[Leaf, 2017/01/20 20:31:53]

This needs to be restricted to considering only type variables from the current
formal parameter list.  Example:

class A<T> {
  void m<S extends T>() {}; 
  m();
}

This should not be an error.  For the purposes of considering the default bounds
of m, S is ground.  T is a type parameter, but it is bound in an outer scope.

[scheglov, 2017/01/21 02:11:23]

Done.

+      List<TypeParameterType> parameters = null;
+
+      void appendParameters(DartType type) {
+        if (type is TypeParameterType) {
+          parameters ??= <TypeParameterType>[];
+          parameters.add(type);
+        } else if (type is ParameterizedType) {
+          type.typeArguments.forEach(appendParameters);
+        }
+      }
+
+      appendParameters(type);
+      return parameters;
+    }
+
+    List<bool> isGround = new List<bool>.filled(count, false);

[Leaf, 2017/01/20 20:31:52]

I think this section of code is right.  I wonder if it would be clearer to write
it using a direct map from variables to their default definitions, rather than
having separate isGround and arguments arrays?  Something like:

// Invariant: all ground
Map<TypeParameterType, DartType> defaults = {};
// Invariant: not ground
Map<TypeParameterType, DartType> partials = {};

for each type parameter t
  if it has no bound then
    defaults[t] = dynamic
  else if t.bound is ground 
    defaults[t] = t.bound
  else 
    partials[t] = t.bound

while(hasProgress) {
  for each type parameter t in keys(partials)
    freeParameters = getFreeParameters(partials[t])
    if freeParameters.all((t) => defaults[t] != null) // all free parameters are
now resolved
      defaults[t] = partials[t].substitute2(freeParameters,
freeParameters.map((t) => defaults[t])
      partials.remove(t)
      hasProgress = true

As an optimization, you could also keep a map from t to
getFreeParameters(partial[t])  so you only compute it once per bound.  Not sure
if it's worth it though.

Your call, I'm ok with the existing code if it makes more sense this way, but I
think the above structure might be more "obviously" right.

[scheglov, 2017/01/21 02:11:23]

I update the code to be more like this.

+
+    Map<TypeParameterType, int> parameterToIndex = {};
     for (int i = 0; i < count; i++) {
-      TypeParameterElement param = typeFormals[i];
-      DartType bound = param.bound ?? DynamicTypeImpl.instance;
-      DartType variable = param.type;
-      // For each Ti extends Bi, first compute Ii by replacing
-      // Ti in Bi with dynamic (simultaneously replacing all
-      // of the previous Tj (j < i) with their instantiated bounds.
-      substituted.add(DynamicTypeImpl.instance);
-      variables.add(variable);
-      // Now update the substitution to replace Ti with Ii instead
-      // of dynamic in subsequent rounds.
-      substituted[i] = bound.substitute2(substituted, variables);
-    }
-
-    return instantiateType(type, substituted);
+      TypeParameterElement parameter = typeFormals[i];
+      parameterToIndex[parameter.type] = i;
+    }
+
+    List<DartType> arguments =
+        typeFormals.map((p) => p.bound ?? DynamicTypeImpl.instance).toList();
+
+    bool hasProgress = true;
+    while (hasProgress) {
+      hasProgress = false;
+      for (int i = 0; i < count; i++) {
+        if (!isGround[i]) {
+          DartType argument = arguments[i];
+          List<TypeParameterType> freeParameters = getFreeParameters(argument);
+          if (freeParameters == null) {
+            isGround[i] = true;
+            hasProgress = true;
+          } else {
+            List<TypeParameterType> subParameters = [];
+            List<DartType> subArguments = [];
+            for (TypeParameterType freeParameter in freeParameters) {
+              int freeParameterIndex = parameterToIndex[freeParameter];
+              if (isGround[freeParameterIndex]) {
+                DartType value = arguments[freeParameterIndex];
+                subParameters.add(freeParameter);
+                subArguments.add(value);
+              }
+            }
+            if (subParameters.isNotEmpty) {
+              arguments[i] = argument.substitute2(subArguments, subParameters);
+              hasProgress = true;
+            }
+          }
+        }
+      }
+    }
+
+    // If we stopped making progress, and not all types are ground,
+    // then the whole type is malbounded and an error should be reported.
+    if (isGround.any((f) => !f)) {
+      arguments = new List<DartType>.filled(count, DynamicTypeImpl.instance);
+      if (hasError != null) {
+        hasError[0] = true;
+      }
+    }
+
+    return instantiateType(type, arguments);
   }
 
   @override
@@ -1129,7 +1177,7 @@ abstract class TypeSystem {
    * classic Dart `dynamic` will be used for all type arguments, whereas
    * strong mode prefers the actual bound type if it was specified.
    */
-  DartType instantiateToBounds(DartType type);
+  DartType instantiateToBounds(DartType type, {List<bool> hasError});
 
   /**
    * Given a [DartType] [type] and a list of types
@@ -1424,7 +1472,7 @@ class TypeSystemImpl extends TypeSystem {
    * Instantiate a parameterized type using `dynamic` for all generic
    * parameters.  Returns the type unchanged if there are no parameters.
    */
-  DartType instantiateToBounds(DartType type) {
+  DartType instantiateToBounds(DartType type, {List<bool> hasError}) {
     List<DartType> typeFormals = typeFormalsAsTypes(type);
     int count = typeFormals.length;
     if (count > 0) {