The VM needs to account for super-bounded types (supertypes of the instantiated-to-bounds type) in type check optimizations

[sstrickl]

When developing CL 312400, I originally put a check in the VM when in DEBUG mode that verified that each type argument for an InterfaceType read from kernel is a subtype of the corresponding type argument when the class type parameters were instantiated to bounds.

However, that check turned out to be too strong for the CFE as it stands currently, as the CFE can produce kernel where this assumption is broken (from a failing build):

output: ../../runtime/vm/compiler/frontend/kernel_translation_helper.cc: 3335: error:
Expected Type: ExhaustivenessCache<X0, dynamic, dynamic, dynamic, X1> to be a subtype of
  Type: ExhaustivenessCache<Object, Object, Object, Object, Object>,
but Type: dynamic is not a subtype of Type: Object

I then introduced a weaker check, that only checked that fully instantiated types read from kernel were subtypes of the type where the class is instantiated to bounds. This allowed the build to succeed, but that check failed on some tests (see this example from the log for one of the failing trybots):

/==============================================================================================\
| co19/Language/Generics/Superbounded_types/class_A05_t01 broke (Pass -> Crash, expected Pass) |
\==============================================================================================/

...

../../runtime/vm/compiler/frontend/kernel_translation_helper.cc: 3333: error:
Expected non-nullable version of Type: A to be a subtype of Type: A<num>

So currently there are cases where the CFE can generate raw (all type arguments are dynamic) or partially raw types for classes where the (partially) raw type is an invalid instantiation of the class. I'm guessing there's a similar issue with TypedefTypes as well, though I haven't verified that on the VM side.

Should the CFE provide a guarantee that all types generated by the CFE are valid subtypes of the instantiated to bounds type?

[sstrickl]

/cc @johnniwinther @chloestefantsova for the CFE

[eernstg]

Should the CFE provide a guarantee that all types generated by the CFE are valid subtypes of the instantiated to bounds type?

Not quite, IIUC. We do not maintain a constraint that every type in a Dart program is an error unless every declared type parameter bound is satisfied (we use the phrase regular-bounded to characterize a type of the form C<T1 .. Tk> where all actual type arguments satisfy the declared bounds for C, with suitable substitutions). In other words, some types are allowed to violate the declared bounds, in specific ways.

This kind of type is known as a super-bounded type, cf. https://github.com/dart-lang/language/blob/ccadba7019d3f39885c9652011de02a8f6879ed2/specification/dartLangSpec.tex#L7211.

I would assume that the CFE will reflect this language-level rule: The CFE would then only generate regular-bounded "types" when an expression like C<T1 .. Tk>(...) is used to create a new object, but in other situations (like e is T, e as T, T v = e;, and so on), the type (T) can be super-bounded.

A super-bounded type is, roughly, a type where all bounds have been satisfied, except that some subterms can denote a top type (like dynamic or Object?). For example:

class C<X extends num> {}
class D<X extends D<X>> {}

void foo(C<Object?> c, D<D<dynamic>> d) {} // OK.
C<Object> get g => throw 0; // Error, `C<Object>` is not well-bounded.

Instantiation to bounds can yield a super-bounded type: D means D<D<dynamic>>. So it is not safe, in general, to assume that every type which is obtained by instantiation to bounds (full or partial) is regular-bounded. On the other hand, it is a bug if there is any code that attempts to create an object whose run-time type isn't regular-bounded.

[sstrickl]

Okay, thanks for the clarification, Erik! I think that means the change in 7cc005e is fine and valid, but there may be cases where the CFE may provide a super-bounded type that we should treat as if it were the instantiated-to-bounds type (e.g., optimization of checking the runtime type of instances), and so I should do a followup to make that change. I'll leave this issue open, but move it over to my side of the pond :)

[eernstg]

Sounds good, thanks!

(Also, I'm sure it would still be useful if @johnniwinther or @chloestefantsova could clarify how the CFE has chosen to handle super-bounded types, and if there's anything extra to think about).

[eernstg]

I should mention that the language specification section about super-bounded types specifies pre-nnbd rules. The rules for the language with null safety are under review in dart-lang/language#2605.

[chloestefantsova]

Sounds good, thanks!

(Also, I'm sure it would still be useful if @johnniwinther or @chloestefantsova could clarify how the CFE has chosen to handle super-bounded types, and if there's anything extra to think about).

We do that like you described: we retain the super-bounded types written by the programmer and we may generate a super-bounded type as the output of the instantiate-to-bound algorithm.