Fuse top level type inference with dependency generation.

Fuse top level type inference with dependency generation.

This CL combines the two parts of top level type inference
(determining dependencies and inferring a type) into a single
operation.

The technique is: instead of evaluating top level types in
topologically sorted order (which requires that we figure out the
dependencies first, so that we can do topological sorting), we simply
iterate over the fields requiring inference and begin inferring them
in whatever order they are encountered.  If, while trying to infer the
type of one field, we discover a reference to field that hasn't been
type inferred yet, we make a recursive call to infer the second field.
If this recursion leads to a loop, then we mark all of the fields in
the loop as participating in a circularity (and set their types to
`dynamic` for error recovery purposes).

To facilitate experimentation, I've left the old code in place, but
disabled it using a const bool `fusedTopLevelInference`.  The old code
can be re-enabled by setting this bool to `false`.  Once we are sure
that we want to proceed with this approach, we can remove the old
code.

Note that there are some minor user-visible behavioral changes:

- When there is a circularity, we no longer consider the entire
  strongly connected component to be part of the circularity; we only
  consider the loop formed by following the first unresolved
  dependency of each field.  (I did this because of ease of
  implementation, and because it made it easier to reassure myself
  that the outcome of the algorithm is independent of the order in
  which fields are visited).  See
  pkg/front_end/testcases/inference_new/strongly_connected_component.dart
  for the user-visible consequence of this change.

- We no longer need to speculatively assume that method invocations
  depend on the types of their parameters when not supplying generic
  types; now they only depend on the types of their parameters when
  the method being invoked is known to be generic.  See
  pkg/front_end/testcases/inference_new/dependency_only_if_generic_method.dart.

- We no longer need to speculatively assume that invocations of `+`,
  `-`, `*`, and `%` depend on the types of their RHS; now they only
  depend on the types of their RHS when the type of the LHS is
  `int`. See
  pkg/front_end/testcases/inference_new/dependency_only_if_overloaded.dart.

R=sigmund@google.com

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

[Paul Berry, 2017-06-15 21:10:53]

paulberry@google.com changed reviewers:
+ danrubel@google.com, scheglov@google.com, sigmund@google.com

[Siggi Cherem (dart-lang), 2017-06-15 22:12:32]

lgtm. I think its fine to land, but Konstantin you've reviewed more of the
inference work, so please also take a look later.


Of all the visible effects, I wonder a bit about the first one (not detecting
all deps in the SCC). I'm guessing the limitations on inference are still the
same and the only visible change is how we report it to the user, correct? Do we
have any tests to see the messages we emit?

The reason I ask is that I recall that the lang team wanted to specify what
messages to present to users when a type could not be inferred. If so, do we
need to get buy-in from them about this visible change? Or is your intention to
eventually fill in the error message after we detect the first loop in an SCC?

https://codereview.chromium.org/2942623004/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/2942623004/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_inference_engine.dart:23: ///
This means that code is currently on the stackwhich is attempting to
stackwhich => stack which

[Paul Berry, 2017-06-15 22:16:52]

https://codereview.chromium.org/2942623004/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/2942623004/diff/1/pkg/front_end/lib/src/fasta...
pkg/front_end/lib/src/fasta/type_inference/type_inference_engine.dart:23: ///
This means that code is currently on the stackwhich is attempting to
On 2017/06/15 22:12:32, Siggi Cherem (dart-lang) wrote:
> stackwhich => stack which

Done.

[Paul Berry, 2017-06-15 22:22:59]

On 2017/06/15 22:12:32, Siggi Cherem (dart-lang) wrote:
> lgtm. I think its fine to land, but Konstantin you've reviewed more of the
> inference work, so please also take a look later.
> 
> 
> Of all the visible effects, I wonder a bit about the first one (not detecting
> all deps in the SCC). I'm guessing the limitations on inference are still the
> same and the only visible change is how we report it to the user, correct?

Correct.

> Do we
> have any tests to see the messages we emit?

No, not yet.  The front end error reporting story is still getting figured out
so I decided to postpone the error reporting until after the rest of type
inference was done.

> 
> The reason I ask is that I recall that the lang team wanted to specify what
> messages to present to users when a type could not be inferred. If so, do we
> need to get buy-in from them about this visible change? Or is your intention
to
> eventually fill in the error message after we detect the first loop in an SCC?

Hmm, I did not know about this.  Let's talk next time we meet.  I don't have
strong feelings about the form of the error messages.  But I do feel strongly
about only reporting a loop rather than the whole SCC, because that change was
part of how I made the analysis tractable (without it, I don't know how to work
out the SCC's, because all the SCC algorithms I know of depend on knowing the
dependencies before evaluating any nodes).

[Paul Berry, 2017-06-16 01:13:55]

Description was changed from

==========
Fuse top level type inference with dependency generation.

This CL combines the two parts of top level type inference
(determining dependencies and inferring a type) into a single
operation.

The technique is: instead of evaluating top level types in
topologically sorted order (which requires that we figure out the
dependencies first, so that we can do topological sorting), we simply
iterate over the fields requiring inference and begin inferring them
in whatever order they are encountered.  If, while trying to infer the
type of one field, we discover a reference to field that hasn't been
type inferred yet, we make a recursive call to infer the second field.
If this recursion leads to a loop, then we mark all of the fields in
the loop as participating in a circularity (and set their types to
`dynamic` for error recovery purposes).

To facilitate experimentation, I've left the old code in place, but
disabled it using a const bool `fusedTopLevelInference`.  The old code
can be re-enabled by setting this bool to `false`.  Once we are sure
that we want to proceed with this approach, we can remove the old
code.

Note that there are some minor user-visible behavioral changes:

- When there is a circularity, we no longer consider the entire
  strongly connected component to be part of the circularity; we only
  consider the loop formed by following the first unresolved
  dependency of each field.  (I did this because of ease of
  implementation, and because it made it easier to reassure myself
  that the outcome of the algorithm is independent of the order in
  which fields are visited).  See
  pkg/front_end/testcases/inference_new/strongly_connected_component.dart
  for the user-visible consequence of this change.

- We no longer need to speculatively assume that method invocations
  depend on the types of their parameters when not supplying generic
  types; now they only depend on the types of their parameters when
  the method being invoked is known to be generic.  See
  pkg/front_end/testcases/inference_new/dependency_only_if_generic_method.dart.

- We no longer need to speculatively assume that invocations of `+`,
  `-`, `*`, and `%` depend on the types of their RHS; now they only
  depend on the types of their RHS when the type of the LHS is
  `int`. See
  pkg/front_end/testcases/inference_new/dependency_only_if_overloaded.dart.
==========

to

==========
Fuse top level type inference with dependency generation.

This CL combines the two parts of top level type inference
(determining dependencies and inferring a type) into a single
operation.

The technique is: instead of evaluating top level types in
topologically sorted order (which requires that we figure out the
dependencies first, so that we can do topological sorting), we simply
iterate over the fields requiring inference and begin inferring them
in whatever order they are encountered.  If, while trying to infer the
type of one field, we discover a reference to field that hasn't been
type inferred yet, we make a recursive call to infer the second field.
If this recursion leads to a loop, then we mark all of the fields in
the loop as participating in a circularity (and set their types to
`dynamic` for error recovery purposes).

To facilitate experimentation, I've left the old code in place, but
disabled it using a const bool `fusedTopLevelInference`.  The old code
can be re-enabled by setting this bool to `false`.  Once we are sure
that we want to proceed with this approach, we can remove the old
code.

Note that there are some minor user-visible behavioral changes:

- When there is a circularity, we no longer consider the entire
  strongly connected component to be part of the circularity; we only
  consider the loop formed by following the first unresolved
  dependency of each field.  (I did this because of ease of
  implementation, and because it made it easier to reassure myself
  that the outcome of the algorithm is independent of the order in
  which fields are visited).  See
  pkg/front_end/testcases/inference_new/strongly_connected_component.dart
  for the user-visible consequence of this change.

- We no longer need to speculatively assume that method invocations
  depend on the types of their parameters when not supplying generic
  types; now they only depend on the types of their parameters when
  the method being invoked is known to be generic.  See
  pkg/front_end/testcases/inference_new/dependency_only_if_generic_method.dart.

- We no longer need to speculatively assume that invocations of `+`,
  `-`, `*`, and `%` depend on the types of their RHS; now they only
  depend on the types of their RHS when the type of the LHS is
  `int`. See
  pkg/front_end/testcases/inference_new/dependency_only_if_overloaded.dart.

R=sigmund@google.com

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

[Paul Berry, 2017-06-16 01:13:57]

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

[ahe, 2017-06-16 13:15:23]

ahe@google.com changed reviewers:
+ ahe@google.com

[ahe, 2017-06-16 13:15:23]

DBC

>  If, while trying to infer the
> type of one field, we discover a reference to field that hasn't been
> type inferred yet, we make a recursive call to infer the second field.
> If this recursion leads to a loop, then we mark all of the fields in
> the loop as participating in a circularity (and set their types to
> `dynamic` for error recovery purposes).

I like how you think! :-)

[scheglov, 2017-06-16 15:39:39]

LGTM