Add a strong mode implementation of LUB to fasta; use it to infer ?:

Add a strong mode implementation of LUB to fasta; use it to infer ?:

R=ahe@google.com, leafp@google.com

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

[Paul Berry, 2017-05-01 18:54:58]

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

[Paul Berry, 2017-05-02 17:36:16]

paulberry@google.com changed reviewers:
+ rnystrom@google.com

[ahe, 2017-05-02 18:32:57]

lgtm

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
File pkg/front_end/lib/src/fasta/type_inference/type_inferrer.dart (right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_inferrer.dart:8: import
'package:front_end/src/fasta/type_inference/type_schema_environment.dart';
Long line.

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

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:21: if
(identical(type1, type2)) {
Should this be == ?

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:64: if
(identical(type1, type2)) {
== ?

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:117:
assert(false);
internalError.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:145: ///
- If a positional parameter is optional or missing in one, it becomes
I don't understand why a missing parameter would become optional.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:155: //
TODO(rnystrom): Right now, this assumes f and g do not have any type
Is this copied from somewhere?

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/co...
File pkg/front_end/test/fasta/compile.status (right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/co...
pkg/front_end/test/fasta/compile.status:29: inference/conditional_lub: Pass
I think this test is now marked flaky. You probably need to list all the tests
except conditional_lub.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ko...
File pkg/front_end/test/fasta/kompile.status (right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ko...
pkg/front_end/test/fasta/kompile.status:60: inference/conditional_lub: Pass
Ditto.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ou...
File pkg/front_end/test/fasta/outline.status (right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ou...
pkg/front_end/test/fasta/outline.status:8: inference/conditional_lub: Pass
Ditto.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ty...
File pkg/front_end/test/fasta/type_inference/type_schema_environment_test.dart
(right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ty...
pkg/front_end/test/fasta/type_inference/type_schema_environment_test.dart:12:
import 'package:test_reflective_loader/test_reflective_loader.dart';
Why do we need to use this for new tests?

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ty...
pkg/front_end/test/fasta/type_inference/type_schema_environment_test.dart:30:
final testLib = new Library(Uri.parse('file:///test.dart'));
Dummy URL, for example, org-dartlang:///test.dart.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ty...
pkg/front_end/test/fasta/type_inference/type_schema_environment_test.dart:190:
expect(env.getGreatestLowerBound(A, A), same(A));
You may want to also test this variant:

Class aClass = _addClass(_class("A"));
var a1 = new InterfaceType(aClass);
var a2 = new InterfaceType(aClass);

In general, you can't assume that types are canonicalized.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/testcases/inf...
File pkg/front_end/testcases/inference/conditional_lub.dart (right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/testcases/inf...
pkg/front_end/testcases/inference/conditional_lub.dart:11: var /*@topType=num*/
z = b ? x : y;
It's getting closer and closer to rocket science now :-)

https://codereview.chromium.org/2849213002/diff/1/pkg/kernel/lib/type_environ...
File pkg/kernel/lib/type_environment.dart (right):

https://codereview.chromium.org/2849213002/diff/1/pkg/kernel/lib/type_environ...
pkg/kernel/lib/type_environment.dart:148: bool isBottom(DartType type) => type
is BottomType;
This is Null, right?

[ahe, 2017-05-02 18:35:03]

lgtm

Some topics for our next 1:1, but nothing blocking.

[Bob Nystrom, 2017-05-02 23:22:18]

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
File pkg/front_end/lib/src/fasta/type_inference/type_inference_engine.dart
(right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_inference_engine.dart:179:
this.classHierarchy = classHierarchy;
Drive-by: Is this correct? It's re-assigning the field to itself. Should the RHS
be "hierarchy"?

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
File pkg/front_end/lib/src/fasta/type_inference/type_inferrer.dart (right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_inferrer.dart:8: import
'package:front_end/src/fasta/type_inference/type_schema_environment.dart';
On 2017/05/02 18:32:56, ahe wrote:
> Long line.

Note that the style specifically allows long lines for imports:

https://www.dartlang.org/guides/language/effective-dart/style#avoid-lines-lon...

"We make an exception for strings containing URIs—mainly imports and exports.
Those can remain single-line strings even if they go over the line limit. This
makes it easier to search source files for a given path."

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

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:145: ///
- If a positional parameter is optional or missing in one, it becomes
On 2017/05/02 18:32:56, ahe wrote:
> I don't understand why a missing parameter would become optional.

Consider:

a(callback(i)) => callback(1);
b(callback()) => callback();

var fn = cond ? a : b;
fn((???) {});

What is the parameter signature at "???" that would create a function that both
a and b can successfully call? The answer is:

([i]) {}

where it takes a single optional parameter.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:155: //
TODO(rnystrom): Right now, this assumes f and g do not have any type
On 2017/05/02 18:32:56, ahe wrote:
> Is this copied from somewhere?

Yes:
https://github.com/dart-lang/sdk/blob/3b790e5311ce3877b1f63a9a0d2beecd11cd6d0...

[Leaf, 2017-05-02 23:28:46]

lgtm

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
File pkg/front_end/lib/src/fasta/type_inference/type_inferrer.dart (right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_inferrer.dart:99:
typeSchemaEnvironment.getLeastUpperBound(thenType, otherwiseType);
This is, I believe, the current behavior of the analyzer, but it doesn't match
the informal spec I've written.

https://github.com/dart-lang/sdk/pull/29371/files#diff-6b8db6ca7f59343ee73beb...

This is so that given this code:

```
  String s = true ? 3 : "hello";
```

we infer `String` as the type of the conditional expression and issue an error
because `3` is not assignable to `String`.  Currently we just accept this code.

If you'd rather start by achieving feature parity with the analyzer and then
move from there to spec compliance that's fine with me - just wanted to point
out that there are some divergences between analyzer and the spec (including
some corner-case correctness functionality that the analyzer doesn't implement).

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

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:21: if
(identical(type1, type2)) {
On 2017/05/02 18:32:56, ahe wrote:
> Should this be == ?

There could be a separate entry point that first tested for full equality, but
since this is a recursive algorithm, testing for equality on every recursive
call (O(n)) makes it quadratic.  The identity check isn't needed for
correctness, it just cuts off fast if the types are the same.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:145: ///
- If a positional parameter is optional or missing in one, it becomes
On 2017/05/02 18:32:56, ahe wrote:
> I don't understand why a missing parameter would become optional.

We're looking for a function type that can be used anywhere either of the two
input function types can be used.   So for example, if we have 
DOWN((int, int) -> int, (int) -> int)), then ([int, int]) -> int is the correct
choice, because it is a subtype of the one with two required parameters, and
also of the one with only one required parameter.   And similarly for when one
of the input arguments has optional parameters.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:156: //
parameters. Revisit that in the presence of generic methods.
Ouch.  This should be fixed.  I'll write up spec verbiage, but basically they
need to have the same number of type parameters, and the bounds need to be
equal.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:317: //
TODO(leafp): Use matchTypes or something similar here to handle the
Remove this todo.  it's tracked elsewhere as a language issue.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:320: //
TODO(leafp): Figure out the right final algorithm and implement it.
likewise.

[Paul Berry, 2017-05-03 17:31:25]

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
File pkg/front_end/lib/src/fasta/type_inference/type_inference_engine.dart
(right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_inference_engine.dart:179:
this.classHierarchy = classHierarchy;
On 2017/05/02 23:22:17, Bob Nystrom wrote:
> Drive-by: Is this correct? It's re-assigning the field to itself. Should the
RHS
> be "hierarchy"?

Oops! That's most certainly wrong.  I'll fix in a follow-up CL.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
File pkg/front_end/lib/src/fasta/type_inference/type_inferrer.dart (right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_inferrer.dart:99:
typeSchemaEnvironment.getLeastUpperBound(thenType, otherwiseType);
On 2017/05/02 23:28:45, Leaf wrote:
> This is, I believe, the current behavior of the analyzer, but it doesn't match
> the informal spec I've written.
> 
>
https://github.com/dart-lang/sdk/pull/29371/files#diff-6b8db6ca7f59343ee73beb...
> 
> This is so that given this code:
> 
> ```
>   String s = true ? 3 : "hello";
> ```
> 
> we infer `String` as the type of the conditional expression and issue an error
> because `3` is not assignable to `String`.  Currently we just accept this
code.
> 
> If you'd rather start by achieving feature parity with the analyzer and then
> move from there to spec compliance that's fine with me - just wanted to point
> out that there are some divergences between analyzer and the spec (including
> some corner-case correctness functionality that the analyzer doesn't
implement).

Ah, thank you.  I've added a TODO comment.

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

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:21: if
(identical(type1, type2)) {
On 2017/05/02 23:28:46, Leaf wrote:
> On 2017/05/02 18:32:56, ahe wrote:
> > Should this be == ?
> 
> There could be a separate entry point that first tested for full equality, but
> since this is a recursive algorithm, testing for equality on every recursive
> call (O(n)) makes it quadratic.  The identity check isn't needed for
> correctness, it just cuts off fast if the types are the same.

I've added a comment explaining this.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:64: if
(identical(type1, type2)) {
On 2017/05/02 18:32:56, ahe wrote:
> == ?

Ditto

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:117:
assert(false);
On 2017/05/02 18:32:56, ahe wrote:
> internalError.

internalError has the disadvantage of causing a crash even in unchecked mode (we
wouldn't be able to fall back to dynamic as a defensive measure).

I'm going to keep it as is for defensiveness.  If you feel strongly about it,
let me know and we can discuss further.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:145: ///
- If a positional parameter is optional or missing in one, it becomes
On 2017/05/02 23:28:46, Leaf wrote:
> On 2017/05/02 18:32:56, ahe wrote:
> > I don't understand why a missing parameter would become optional.
> 
> We're looking for a function type that can be used anywhere either of the two
> input function types can be used.   So for example, if we have 
> DOWN((int, int) -> int, (int) -> int)), then ([int, int]) -> int is the
correct
> choice, because it is a subtype of the one with two required parameters, and
> also of the one with only one required parameter.   And similarly for when one
> of the input arguments has optional parameters.

Thanks for the explanations.  I've updated the comment to make this clearer.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:156: //
parameters. Revisit that in the presence of generic methods.
On 2017/05/02 23:28:46, Leaf wrote:
> Ouch.  This should be fixed.  I'll write up spec verbiage, but basically they
> need to have the same number of type parameters, and the bounds need to be
> equal.

Thanks.  I've added my name to the TODO comment as well.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:317: //
TODO(leafp): Use matchTypes or something similar here to handle the
On 2017/05/02 23:28:46, Leaf wrote:
> Remove this todo.  it's tracked elsewhere as a language issue.

Done.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_schema_environment.dart:320: //
TODO(leafp): Figure out the right final algorithm and implement it.
On 2017/05/02 23:28:45, Leaf wrote:
> likewise.

Done.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/co...
File pkg/front_end/test/fasta/compile.status (right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/co...
pkg/front_end/test/fasta/compile.status:29: inference/conditional_lub: Pass
On 2017/05/02 18:32:56, ahe wrote:
> I think this test is now marked flaky. You probably need to list all the tests
> except conditional_lub.

Thanks.  Konstantin took care of this in a CL that landed before mine.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ko...
File pkg/front_end/test/fasta/kompile.status (right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ko...
pkg/front_end/test/fasta/kompile.status:60: inference/conditional_lub: Pass
On 2017/05/02 18:32:56, ahe wrote:
> Ditto.

Acknowledged.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ou...
File pkg/front_end/test/fasta/outline.status (right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ou...
pkg/front_end/test/fasta/outline.status:8: inference/conditional_lub: Pass
On 2017/05/02 18:32:56, ahe wrote:
> Ditto.

Acknowledged.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ty...
File pkg/front_end/test/fasta/type_inference/type_schema_environment_test.dart
(right):

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ty...
pkg/front_end/test/fasta/type_inference/type_schema_environment_test.dart:12:
import 'package:test_reflective_loader/test_reflective_loader.dart';
On 2017/05/02 18:32:56, ahe wrote:
> Why do we need to use this for new tests?

test_reflective_loader has two big advantages over standard test-package tests:

- It supports solo_test, which is really handy during development, especially
when testing in the debugger.

- It allows shared test code and data to be stored in the class as methods and
fields (a new instance of the class is constructed for each test execution, so
we minimize interference between tests).  That can be done with standard
test-package tests but it's a lot less convenient.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ty...
pkg/front_end/test/fasta/type_inference/type_schema_environment_test.dart:30:
final testLib = new Library(Uri.parse('file:///test.dart'));
On 2017/05/02 18:32:56, ahe wrote:
> Dummy URL, for example, org-dartlang:///test.dart.

Done.

https://codereview.chromium.org/2849213002/diff/1/pkg/front_end/test/fasta/ty...
pkg/front_end/test/fasta/type_inference/type_schema_environment_test.dart:190:
expect(env.getGreatestLowerBound(A, A), same(A));
On 2017/05/02 18:32:56, ahe wrote:
> You may want to also test this variant:
> 
> Class aClass = _addClass(_class("A"));
> var a1 = new InterfaceType(aClass);
> var a2 = new InterfaceType(aClass);
> 
> In general, you can't assume that types are canonicalized.

Done.  I made a similar addition to the LUB test.

https://codereview.chromium.org/2849213002/diff/1/pkg/kernel/lib/type_environ...
File pkg/kernel/lib/type_environment.dart (right):

https://codereview.chromium.org/2849213002/diff/1/pkg/kernel/lib/type_environ...
pkg/kernel/lib/type_environment.dart:148: bool isBottom(DartType type) => type
is BottomType;
On 2017/05/02 18:32:57, ahe wrote:
> This is Null, right?

I discussed this with Leaf yesterday.  The intention is that Null and Bottom
should be represented as distinct types, with bottom as a subtype of Null.

Eventually, once we have non-nullability, Null will be a subtype of all nullable
types but not of non-nullable types, so it won't be true bottom.

For now I'm just trying to refactor the existing code without changing
functionality.

[Paul Berry, 2017-05-03 17:36:53]

Description was changed from

==========
Add a strong mode implementation of LUB to fasta; use it to infer ?:
==========

to

==========
Add a strong mode implementation of LUB to fasta; use it to infer ?:

R=ahe@google.com, leafp@google.com

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

[Paul Berry, 2017-05-03 17:36:54]

Committed patchset #1 (id:1) manually as
d842f35bb2b374e1639345178a7d2997a208cf15 (presubmit successful).