frontend type inference emits "UnknownType" instead of DynamicType

[sigmundch]

Consider this example:

foo<T>(Iterable<T> Function(int) f) {}

main() {
  foo((int x) => (x > 1) ? [] : [1, 2].map((e) => 1));

  foo((int x) {
    if (x > 1) {
      return [];
    } else {
      return [1, 2].map((e) => e);
    }
  });
}

It appears that type inference correctly infers that the first closure return an Iterable<dynamic>, but it doesn't infer the same thing for the second closure. Instead it generates Iterable<UnknownType>. This causes failures down the line (we noticed the failure also as a crash in the dart2js backend).

Here is the output from dumping the IR with fasta-compile:

> pkg/front_end/tool/fasta compile --strong --dump-ir m.dart                                                                                          
static method foo<T extends core::Object>((core::int) → core::Iterable<self::foo::T> f) → dynamic {}
static method main() → dynamic {                                                     
  self::foo<dynamic>((core::int x) → core::Iterable<dynamic> => (x.{core::num::>}(1) ?{core::Object} <dynamic>[] : <core::int>[1, 2].{core::Iterable::map}<c
ore::int>((core::int e) → core::int => 1)) as{TypeError} core::Iterable<dynamic>);
  self::foo<dynamic>((core::int x) → core::Iterable<<UnknownType>> {                
    if(x.{core::num::>}(1)) {                                                      
      return <dynamic>[];                              
    }                                                                            
    else {                                                              
      return <core::int>[1, 2].{core::Iterable::map}<core::int>((core::int e) → core::int => e);
    }                                                                                    
  });                                                                             
}                        
                                                                                                                                       
Unhandled exception:     
Unsupported operation: serialization of generic DartTypes                                                                                      
#0      BinaryPrinter.defaultDartType (package:kernel/binary/ast_to_binary.dart:1745:5)
#1      UnknownType.accept (package:front_end/src/fasta/type_inference/type_schema.dart:72:16)                                                           
#2      BinaryPrinter.writeNode (package:kernel/binary/ast_to_binary.dart:229:10)                                  
#3      BinaryPrinter.writeNodeList (package:kernel/binary/ast_to_binary.dart:221:7)
#4      BinaryPrinter.visitInterfaceType (package:kernel/binary/ast_to_binary.dart:1644:7)
#5      InterfaceType.accept (package:kernel/ast.dart:4883:34)
#6      BinaryPrinter.writeNode (package:kernel/binary/ast_to_binary.dart:229:10)              
#7      BinaryPrinter.visitFunctionNode (package:kernel/binary/ast_to_binary.dart:949:5)         
#8      FunctionNode.accept (package:kernel/ast.dart:1991:30)                                                                        
#9      BinaryPrinter.writeNode (package:kernel/binary/ast_to_binary.dart:229:10)                                          
#10     BinaryPrinter.visitFunctionExpression (package:kernel/binary/ast_to_binary.dart:1308:5)
#11     FunctionExpression.accept (package:kernel/ast.dart:3510:36)                                                                 
#12     BinaryPrinter.writeNode (package:kernel/binary/ast_to_binary.dart:229:10)
#13     BinaryPrinter.writeNodeList (package:kernel/binary/ast_to_binary.dart:221:7)                             
#14     BinaryPrinter.visitArguments (package:kernel/binary/ast_to_binary.dart:1125:5)            
#15     Arguments.accept (package:kernel/ast.dart:2686:30)                                         
#16     BinaryPrinter.writeNode (package:kernel/binary/ast_to_binary.dart:229:10)                        
#17     BinaryPrinter.visitStaticInvocation (package:kernel/binary/ast_to_binary.dart:1108:5
...

@kmillikin - can someone on the FE side take a look?

[kmillikin]

Yes, I'll take a look. UnknownType should not survive type inference.

[kmillikin]

In the if case there are two returns, one of a List<dynamic> and one of an Iterable<int>. The LUB of these is Object which is not a subtype of the return expectation Iterable<T> for any T so the inference algorithm tries to use the return type expectation.

That expectation is Iterable<UnknownType> so we should use the greatest closure of that (I guess? @leafpetersen).

Proposed fix: https://dart-review.googlesource.com/c/sdk/+/52521

[leafpetersen]

Oy, Dart "least" upper bound. Here's a sketch of what I think should be happening:

There are two pieces of "state" associated with block body function inference:

• The downwards context K
• The (optional) inferred return type M

K is taken from the context of occurrence (empty if not present)
M is initially empty

For each return statement return e1, where inferring e1 in context K produces e2 of type T

• If M is empty, then M is T
• If M is U, then set M set to LUB(T, U)

For each return statement return;,

• M is set to void
  • Note that it is implicitly an error if there are both void and non-void returns, but this is not an inference error per-se.

The final inferred return type of the function is:

• if M is not empty after visiting all return statements:
  - Let S be the greatest closure of K
  - the inferred type is M if M <: S
  - the inferred type is S otherwise
• Otherwise it should be void, but currently we infer Null
  • Infer void return type for function literal #32843
  • I'm working on fixing this part, will follow up separately.

So for this specific example, K is Iterable<?>.

Visiting return [] produces return <dynamic>[] of type List<dynamic>, with M set to List<dynamic>

Visiting return [1, 2].map((e) => e); produces return <int>[1, 2].map<int>((e) => e); of type Iterable<int> since the downward context does not constrain the argument to map but upwards inference does.

LUB(List<dynamic>, Iterable<int>) == Object

The greatest closure of Iterable<?> is Iterable<Object>, and Object </: Iterable<Object> (even though List<dynamic> <: Iterable<Object> and Iterable<int> <: Iterable<Object>), so the inferred return type is Iterable<Object>.

You can think of this as inserting an implicit cast to the greatest closure of the downwards context on each return expression, except that of course the cast is unnecessary by construction.

[kmillikin]

It's interesting that you say that the greatest closure is Iterable<Object>. There's this comment here that indicates it is:

https://github.com/dart-lang/sdk/blob/master/pkg/front_end/lib/src/fasta/type_inference/type_schema_elimination.dart#L13

And there's this code here that implements Iterable<dynamic>:

https://github.com/dart-lang/sdk/blob/master/pkg/front_end/lib/src/fasta/type_inference/type_schema_elimination.dart#L113

It was changed deliberately in https://codereview.chromium.org/2872763002/ and the comments were left stale.

(Edited to add: that comment is confusing to me anyway because it seems to have swapped covariant and contravariant, or am I thinking of it wrong?)