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

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

R=leafp@google.com, brianwilkerson@google.com
BUG= https://github.com/dart-lang/sdk/issues/28100

Committed: https://github.com/dart-lang/sdk/commit/919d70d0cb99ea9d8cc9dcc4f41e6b7fd95be82d

[Brian Wilkerson, 2017-01-20 17:41:05]

Sorry, but I'm not really familiar enough with the spec to know whether this
does what it's suppose to, so I'm going to defer to Leaf.

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

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/error/erro...
File pkg/analyzer/lib/error/error.dart (right):

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/error/erro...
pkg/analyzer/lib/error/error.dart:629:
StrongModeCode.UNABLE_INSTANTIATE_TO_BOUNDS,
Maybe a better name might be "NO_DEFAULT_BOUNDS"?

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/src/error/...
File pkg/analyzer/lib/src/error/codes.dart (right):

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/src/error/...
pkg/analyzer/lib/src/error/codes.dart:4911: "Unable to instantiate to bounds.",
Maybe "Type has no default bounds", "Try adding explicit type parameters to
type"?

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/src/genera...
File pkg/analyzer/lib/src/generated/type_system.dart (right):

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/src/genera...
pkg/analyzer/lib/src/generated/type_system.dart:423: * Ii in all of the
remaining bounds.
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?

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/src/genera...
pkg/analyzer/lib/src/generated/type_system.dart:425: DartType
instantiateToBounds(DartType type, {List<bool> hasError}) {
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. :(

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/src/genera...
pkg/analyzer/lib/src/generated/type_system.dart:432: List<TypeParameterType>
getFreeParameters(DartType type) {
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.

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/src/genera...
pkg/analyzer/lib/src/generated/type_system.dart:448: List<bool> isGround = new
List<bool>.filled(count, false);
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.

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/test/generated...
File pkg/analyzer/test/generated/strong_mode_test.dart (right):

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/test/generated...
pkg/analyzer/test/generated/strong_mode_test.dart:1961: 
Nice!  Can you add a couple of tests for the generic method versions of these? 
And a test for the nested case that I mentioned in a previous comment would be
good too.

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

PTAL

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/error/erro...
File pkg/analyzer/lib/error/error.dart (right):

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/error/erro...
pkg/analyzer/lib/error/error.dart:629:
StrongModeCode.UNABLE_INSTANTIATE_TO_BOUNDS,
On 2017/01/20 20:31:52, Leaf wrote:
> Maybe a better name might be "NO_DEFAULT_BOUNDS"?

Done.

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/src/error/...
File pkg/analyzer/lib/src/error/codes.dart (right):

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/src/error/...
pkg/analyzer/lib/src/error/codes.dart:4911: "Unable to instantiate to bounds.",
On 2017/01/20 20:31:52, Leaf wrote:
> Maybe "Type has no default bounds", "Try adding explicit type parameters to
> type"?

Done.

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/src/genera...
File pkg/analyzer/lib/src/generated/type_system.dart (right):

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/src/genera...
pkg/analyzer/lib/src/generated/type_system.dart:423: * Ii in all of the
remaining bounds.
On 2017/01/20 20:31:53, Leaf wrote:
> 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?

Done.

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/src/genera...
pkg/analyzer/lib/src/generated/type_system.dart:425: DartType
instantiateToBounds(DartType type, {List<bool> hasError}) {
On 2017/01/20 20:31:52, Leaf wrote:
> 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. :(

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.

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/src/genera...
pkg/analyzer/lib/src/generated/type_system.dart:432: List<TypeParameterType>
getFreeParameters(DartType type) {
On 2017/01/20 20:31:53, Leaf wrote:
> 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.

Done.

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/lib/src/genera...
pkg/analyzer/lib/src/generated/type_system.dart:448: List<bool> isGround = new
List<bool>.filled(count, false);
On 2017/01/20 20:31:52, Leaf wrote:
> 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.

I update the code to be more like this.

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/test/generated...
File pkg/analyzer/test/generated/strong_mode_test.dart (right):

https://codereview.chromium.org/2640143007/diff/1/pkg/analyzer/test/generated...
pkg/analyzer/test/generated/strong_mode_test.dart:1961: 
On 2017/01/20 20:31:53, Leaf wrote:
> Nice!  Can you add a couple of tests for the generic method versions of these?

> And a test for the nested case that I mentioned in a previous comment would be
> good too.

Done.

[Leaf, 2017-01-23 17:45:33]

lgtm, thanks!

https://codereview.chromium.org/2640143007/diff/20001/pkg/analyzer/lib/src/ge...
File pkg/analyzer/lib/src/generated/type_system.dart (right):

https://codereview.chromium.org/2640143007/diff/20001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/type_system.dart:451:
type.typeArguments.forEach(appendParameters);
Just a passing note that when Brian lands function type syntax this will likely
need to be updated, since I think that will provide a new way to embed type
parameters directly (e.g. <T extends L<T Function(T x)>>) that likely won't be a
ParameterizedType.

It may be worth putting a method on DartType called .freeTypeVariables, and then
writing this as something like

parameters.addAll(type.freeTypeVariables().intersect(all));

[scheglov, 2017-01-23 18:12:38]

Description was changed from

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

R=brianwilkerson@google.com, leafp@google.com
BUG= https://github.com/dart-lang/sdk/issues/28100
==========

to

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

R=leafp@google.com, brianwilkerson@google.com
BUG= https://github.com/dart-lang/sdk/issues/28100

Committed:
https://github.com/dart-lang/sdk/commit/919d70d0cb99ea9d8cc9dcc4f41e6b7fd95be82d
==========

[scheglov, 2017-01-23 18:12:39]

Committed patchset #2 (id:20001) manually as
919d70d0cb99ea9d8cc9dcc4f41e6b7fd95be82d (presubmit successful).