Type inference discrepancy

[eernstg]

Consider the following program:

class A<X> {}
class B<Y extends Iterable<X>, X> implements A<X> {}

main() {
  A<String> a = B();
  print(a.runtimeType); 
}

This program compiles, runs, and prints B<Iterable<String>, String>. However, the analyzer (from DartPad, version 3.4.0-175.0.dev) reports the following error:

'Iterable<Object?>' doesn't conform to the bound 'Iterable<String>' of the type parameter 'Y'.

It seems reasonable that the two tools should agree on the outcome. I'll use the label 'area-analyzer' because the behavior of the CFE seems preferable.

[bwilkerson]

Does the specification say what the right behavior is?

@stereotype441 Is this likely to be in shared code or is this specific to the analyzer?

[stereotype441]

@stereotype441 Is this likely to be in shared code or is this specific to the analyzer?

I believe this is in code that's specific to the analyzer and CFE. However, @chloestefantsova has been doing some work recently to try to unify some of the analyzer and CFE type inference logic; she may know better than I do.

[chloestefantsova]

I believe this is in code that's specific to the analyzer and CFE. However, @chloestefantsova has been doing some work recently to try to unify some of the analyzer and CFE type inference logic; she may know better than I do.

That's a very interesting case to investigate. The discrepancy seem to show in the way the Analyzer and the CFE pass the intermediary results between the phases of the inference. It seems that in the Analyzer the preliminary chosen type String for X doesn't show in line https://github.com/dart-lang/sdk/blob/d6ecb92d1889ec2444277d59bd8b13cffeb1d6e0/pkg/analyzer/lib/src/dart/element/generic_inferrer.dart#L479 when the final types are chosen for both X and Y. I'll investigate further and come back with what I'll find.

UPD: I think the relevant section in the spec is this one: https://github.com/dart-lang/language/blob/main/resources/type-system/inference.md#constraint-solution-for-a-set-of-type-variables.

[chloestefantsova]

I gave the spec and the implementations another read, and I think the CFE is closer to the algorithm specified in https://github.com/dart-lang/language/blob/main/resources/type-system/inference.md#constraint-solution-for-a-set-of-type-variables.

1. During the downwards inference of A<String> a = B(); yields the constraints _ <: Y <: _ and _ <: X <: String and the partial solution Y = _, X = String.
2. The upwards inference doesn't yield more information, and we use the partial solution from step 1 to determine the solution for the current phase.
3. Partial solution from the previous phase for Y is _. It is not known since it contains _. The constraint set from the upwards phase is empty for Y, and the constraint solution for the empty set is _. Y does have an explicit bound, which is Iterable<X>. We compute B1' by substituting the partial solution from the previous phase in B1, which is the bound of Y. We end up with Iterable<String>. Then we add the constraint Y <: Iterable<String> to the set of constraints for Y and find the constraint set solution for the updated set.
4. We end up with the solution Iterable<String> for Y.

@eernstg WDYT about my analysis above?

I believe the following patch implements the reusing of the partial solution from the previous phase in the Analyzer.

diff --git a/pkg/analyzer/lib/src/dart/element/generic_inferrer.dart b/pkg/analyzer/lib/src/dart/element/generic_inferrer.dart
index 566a8039c9e..6287182d2be 100644
--- a/pkg/analyzer/lib/src/dart/element/generic_inferrer.dart
+++ b/pkg/analyzer/lib/src/dart/element/generic_inferrer.dart
@@ -455,8 +455,10 @@ class GenericInferrer {
   /// Computes (or recomputes) a set of [inferredTypes] based on the constraints
   /// that have been recorded so far.
   List<DartType> _chooseTypes({required bool preliminary}) {
-    var inferredTypes = List<DartType>.filled(
-        _typeFormals.length, UnknownInferredType.instance);
+    var inferredTypes = [
+      for (var typeParam in _typeFormals)
+        _typesInferredSoFar[typeParam] ?? UnknownInferredType.instance
+    ];
     for (int i = 0; i < _typeFormals.length; i++) {
       // TODO(kallentu): : Clean up TypeParameterElementImpl casting once
       // variance is added to the interface.

[eernstg]

WDYT about my analysis above?

Looks good to me! However, when the topic is inference I would double-check with @leafpetersen, @stereotype441, or you! :smile:

[leafpetersen]

LGTM