Begin implementing subtype matching for type inference.

Begin implementing subtype matching for type inference.

R=scheglov@google.com

Committed: https://github.com/dart-lang/sdk/commit/932a749bbcd40c042554141f2d836af914ed160c

[Paul Berry, 2017-05-04 13:09:44]

paulberry@google.com changed reviewers:
+ ahe@google.com, jmesserly@google.com, leafp@google.com, scheglov@google.com

[scheglov, 2017-05-04 15:31:35]

LGTM

[Paul Berry, 2017-05-04 15:40:50]

Description was changed from

==========
Begin implementing subtype matching for type inference.
==========

to

==========
Begin implementing subtype matching for type inference.

R=scheglov@google.com

Committed:
https://github.com/dart-lang/sdk/commit/932a749bbcd40c042554141f2d836af914ed160c
==========

[Paul Berry, 2017-05-04 15:40:51]

Committed patchset #2 (id:20001) manually as
932a749bbcd40c042554141f2d836af914ed160c (presubmit successful).

[Jennifer Messerly, 2017-05-04 18:06:01]

Some suggestions, but overall this lgtm!

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
File pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart
(right):

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart:10: ///
which [subtype] is a subtype of [supertype].  If such a set can be found, it
very very minor style thing, first sentence of a doc comment should be a
standalone paragraph.

https://www.dartlang.org/guides/language/effective-dart/documentation#do-make...

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart:27:
class _ProtoConstraint {
maybe add a doc comment on what this is tracking?

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart:77:
bool isSubtypeMatch(DartType subtype, DartType supertype) {
great comments and structure in this method, BTW!

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart:106: //
`Null` is a subtype match for any type `Q` under no constraints.
it may be worth a note that non-nullable types will change this?

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart:218:
environment.hierarchy.getTypeAsInstanceOf(subtype, supertype.classNode);
I think this is right, but just checking my understanding with an example :)

class B<S> {}
class C<T> implements B<T> {}
class D<T> extends C<List<T>> {}

B<Iterable<num>> b = new D(); 

Here we're solving for `D<T>` and matching it as a subtype of `B<Iterable<num>>`
It should find `B<List<T>>` ... then we will recurse and match `List<T>` as the
subtype of `Iterable<num>` ... ultimately getting the constraint that `T <: num`

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart:229:
bool _isNull(DartType type) =>
how would you feel about calling this "_isBottom" ?

I think in the current type system design we have a bottom type that is distinct
from Null (and it will become more important with non-null type explorations).
So It may be worth naming it in terms of Bottom rather than Null, since
conceptually we're dealing with the Bottom type, that just happens to be mutual
subtypes with Null right now (aside: that may be a bug in fact, I added a
comment to https://github.com/dart-lang/sdk/issues/28513#issuecomment-299257980
)

... that said ... it may just mean an _isBottom and _isNull check are both
necessary once those two types become distinct.

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
File pkg/front_end/lib/src/fasta/type_inference/type_schema.dart (right):

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_schema.dart:10: bool
isKnown(DartType schema) => schema.accept(new _IsKnownVisitor());
since the visitor is stateless, would it be worth a lazy static/top-level field
so we aren't allocating a new one each time?

e.g.

class _IsKnownVisitor {
  ...
  static final instance = new _IsKnownVisitor();
  ...
}


... IDK whether this codebase is doing this sort of optimization at this point,
but it's a pretty easy one as they go :)

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
File pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart
(right):

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:34: void
addLowerBound(TypeConstraint constraint, DartType lower) {
this feels conceptually like it's an operation that might make more sense on
TypeConstraint?

since it's a mutation operation, putting it on the object can give the reader at
the call site bit more sense of what is being mutated. Otherwise I would wonder
if it's mutating the TypeSchemaEnvironment.

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:35:
constraint.lower = getLeastUpperBound(constraint.lower, lower);
fyi ... we started with an implementation like this too in Analyzer ... we moved
to tracking individual constraints to be able to issue error messages with
better information about what went wrong.

[Paul Berry, 2017-05-04 19:56:10]

Items marked "Done" are addressed by https://codereview.chromium.org/2862063002

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
File pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart
(right):

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart:10: ///
which [subtype] is a subtype of [supertype].  If such a set can be found, it
On 2017/05/04 18:06:01, Jennifer Messerly wrote:
> very very minor style thing, first sentence of a doc comment should be a
> standalone paragraph.
> 
>
https://www.dartlang.org/guides/language/effective-dart/documentation#do-make...

Done.

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart:27:
class _ProtoConstraint {
On 2017/05/04 18:06:01, Jennifer Messerly wrote:
> maybe add a doc comment on what this is tracking?

Done.

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart:77:
bool isSubtypeMatch(DartType subtype, DartType supertype) {
On 2017/05/04 18:06:01, Jennifer Messerly wrote:
> great comments and structure in this method, BTW!

Thanks, though Leaf deserves most of the credit, since I mostly copied and
pasted from https://github.com/dart-lang/sdk/pull/29371/files :)

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart:106: //
`Null` is a subtype match for any type `Q` under no constraints.
On 2017/05/04 18:06:01, Jennifer Messerly wrote:
> it may be worth a note that non-nullable types will change this?

Done.

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart:218:
environment.hierarchy.getTypeAsInstanceOf(subtype, supertype.classNode);
On 2017/05/04 18:06:01, Jennifer Messerly wrote:
> I think this is right, but just checking my understanding with an example :)
> 
> class B<S> {}
> class C<T> implements B<T> {}
> class D<T> extends C<List<T>> {}
> 
> B<Iterable<num>> b = new D(); 
> 
> Here we're solving for `D<T>` and matching it as a subtype of
`B<Iterable<num>>`
> It should find `B<List<T>>` ... then we will recurse and match `List<T>` as
the
> subtype of `Iterable<num>` ... ultimately getting the constraint that `T <:
num`
> 

Yes, that's my understanding as well.

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart:229:
bool _isNull(DartType type) =>
On 2017/05/04 18:06:01, Jennifer Messerly wrote:
> how would you feel about calling this "_isBottom" ?
> 
> I think in the current type system design we have a bottom type that is
distinct
> from Null (and it will become more important with non-null type explorations).
> So It may be worth naming it in terms of Bottom rather than Null, since
> conceptually we're dealing with the Bottom type, that just happens to be
mutual
> subtypes with Null right now (aside: that may be a bug in fact, I added a
> comment to
https://github.com/dart-lang/sdk/issues/28513#issuecomment-299257980
> )
> 
> ... that said ... it may just mean an _isBottom and _isNull check are both
> necessary once those two types become distinct.

Hmm, good point.  At the moment I don't have a very clear picture of what's
going on with bottom vs null, so I'm going to leave the name (and the behavior)
as is for now.  But I'll add a comment to remind myself to look into it again
once I get enough functionality working that I can compare the behavior of the
old (analyzer-based) and new (kernel-based) type inference algorithms.

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
File pkg/front_end/lib/src/fasta/type_inference/type_schema.dart (right):

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_schema.dart:10: bool
isKnown(DartType schema) => schema.accept(new _IsKnownVisitor());
On 2017/05/04 18:06:01, Jennifer Messerly wrote:
> since the visitor is stateless, would it be worth a lazy static/top-level
field
> so we aren't allocating a new one each time?
> 
> e.g.
> 
> class _IsKnownVisitor {
>   ...
>   static final instance = new _IsKnownVisitor();
>   ...
> }
> 
> 
> ... IDK whether this codebase is doing this sort of optimization at this
point,
> but it's a pretty easy one as they go :)

Actually what I'd really love to do is change this to

bool isKnown(DartType schema) => schema.accept(const _IsKnownVisitor());

(that way the compiler double checks that the visitor is stateless)

I'll do that in a follow-up CL.

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
File pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart
(right):

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:34: void
addLowerBound(TypeConstraint constraint, DartType lower) {
On 2017/05/04 18:06:01, Jennifer Messerly wrote:
> this feels conceptually like it's an operation that might make more sense on
> TypeConstraint?
> 
> since it's a mutation operation, putting it on the object can give the reader
at
> the call site bit more sense of what is being mutated. Otherwise I would
wonder
> if it's mutating the TypeSchemaEnvironment.

Hmm, good point.  I'm not too thrilled with this API either.  I'll experiment
with this in a follow-up CL.

https://codereview.chromium.org/2856383003/diff/20001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:35:
constraint.lower = getLeastUpperBound(constraint.lower, lower);
On 2017/05/04 18:06:01, Jennifer Messerly wrote:
> fyi ... we started with an implementation like this too in Analyzer ... we
moved
> to tracking individual constraints to be able to issue error messages with
> better information about what went wrong.

Thanks--I noticed that while reading through the analyzer code.  My current plan
is to have a derived version of TypeSchemaEnvironment that does additional
tracking for the purposes of better error reporting; if type inference fails,
we'll re-analyze the method using the derived class (that way we can avoid
paying the extra tracking penalty in the common case of analyzing code that is
error free).  I'm imagining that the derived TypeSchemaEnvironment would make
use of a derived version of TypeConstraint that stores the extra constraint
tracking information.

I'll play with this in the same follow-up CL.