Proposal: store instantiate-to-bounds result in kernel

[stereotype441]

[Edit eernstg Apr 2018: Note that as of today the instantiate-to-bounds algorithm has a feature spec.]

---

Dart 2.0 specifies a nontrivial algorithm for inferring type arguments from bounds: the "instantiate to bounds" algorithm. This algorithm needs to be used in several situations:

• When a generic type is named (e.g. as a variable or parameter type, in an "as" or "is" test, or as a type literal expression)
• During invocation of a generic class constructor when no type parameters are supplied
• During type inference of a generic method call when no type parameters are supplied

In most situations, these three cases can all be handled by the front end. However, there is one exception: when a generic method is invoked dynamically, the runtime must supply type parameters using the instantiate to bounds algorithm. This might happen, for example, when executing code like this:

f<T extends ..., U extends ...>() { ... }
g(dynamic d) {
  d();
}
main() {
  g(f);
}

This is really unfortunate, because it means that the instantiate-to-bounds algorithm needs to be replicated in all runtimes, and we need to test it carefully to make sure the implementations don't diverge.

It seems like it would be much easier to have the kernel representation for a generic function or method include a default set of generic types; the front end could fill in this set of types using instantiate-to-bounds at compile time, and the runtime could simply use it when needed. There would no longer be any need to replicate the instantiate-to-bounds algorithm in all the runtimes.

@leafpetersen does this seem feasible to you? (Am I missing some crucial detail that would prevent this from working?)
@kmillikin this would require changes to the kernel format--what do you think?
CC: @sigmundch

[stereotype441]

CC: @stefantsov @sjindel-google

[leafpetersen]

Yes, my informal expectation was that kernel would record this information for the backend to use. Basically, I think of it as a set of "default arguments" for the type arguments that get computed by the frontend, and the backend just consumes them. For the common case that the default arguments are all "dynamic", you can presumably just elide them for compactness.

[sjindel-google]

Done in https://dart-review.googlesource.com/c/sdk/+/48424

[leafpetersen]

cc @rakudrama @efortuna

[efortuna]

thank youuuuuu!!!!!

[chloestefantsova]

The front-end part of this change is not landed yet. The field currently contains null at all times.

[sjindel-google]

@stefantsov: when will you able to revisit this? I have an outstanding review in the VM which implements this support there, and can't be landed until it's available in the CFE.

[chloestefantsova]

@sjindel-google It's very close to the top of my list, but I don't want to give promises because of the slight fuzziness on the other issues with seemingly higher priority.

[chloestefantsova]

A brief status update. I'm working on the issue in two separate CLs:

• CL 50941 handles default types for classes and typedefs. It also contains a non-trivial refactoring of the existing code, because having the default types allows for more elegant solutions in many places.
• CL 50945 runs instantiate-to-bound on functions. It depends on CL 50941. Currently it works for local functions and function expressions, and I'm going to add the support for methods and top-level functions soon.

Sorry for delaying this for some time. I hope I'll get it working soon now that I have enough time to finish the task.

[chloestefantsova]

Another issue kicked in after the changes in the mentioned CLs. Namely, checks for the correct number of type arguments for types are need to be made early in the process in order to make everything work. I started implementing these checks in CL 51128. CL 50941 and CL 50945 are rebased to depend on that CL.

[chloestefantsova]

CL 51128 is out for review. Basically, without changes from this CL we can't tell if the number of supplied type arguments in the supertypes, the mixins, and the bounds is correct or not (yes, until the CL is landed, you may try and use List<int, String> as a supertype and observe very Dart 1-ish behavior of getting List<dynamic> for that). Currently, I'm rebasing the remaining two CLs and (possibly) fixing arising issues in them. Will keep this thread updated.

[chloestefantsova]

Ok, so the number of related CLs is still growing :-) There are 5 of them currently, and it should soon become 6. Here are the links to the existing ones, in the order from least dependent to most dependent:

1. [fasta] Report type argument number mismatch during outline building
2. [fasta] Normalize type arguments as in Dart 1 when not in strong mode
3. [fasta] Store calculated bounds of type variables as their defaults
4. [fasta] Update expectation files after CL 50941
5. [fasta] Run instantiate-to-bound on functions

The first 4 are sent out for the review. That's what it takes for the preparation to the actual fix :-)

[chloestefantsova]

Small status update: CL 51128 has landed recently.

[chloestefantsova]

CL 51600 has landed. CL 50941 got a +1, but it needs to be landed only together with CL 51620 that updates the expectation files.

[chloestefantsova]

CL 50941 and CL 51620 have landed.

[chloestefantsova]

CL 50945 is out for review, and it's the last piece of the puzzle. I hope to get it landed soon. I'll update the thread when it's done.

[chloestefantsova]

I believe the front-end part of this issue is resolved as of 6fc4854.