Fixes incorrect generic function type capture

Fixes incorrect generic function type capture

This improves how generic function types are modeled. In particular, we can now handle types like <T>T -> T, in printing, equality, and the type parameter is correctly removed when it is instantiated.

This preserves the existing lazy "substitute" operation, and makes the "instantiate" operation interact with it correctly. Given a type like:

    {T/T}<S>T -> S

we can substitute S/T to get:

    {S/T}<S>T -> S

then if we instantiate as <int> we'll get the correct:

    {S/T, int/S}T -> S, which == S -> int

This also converts typedefs over to the new system, as this seemed like the most natural thing. (However this does *not* change how the type name is evaluated, in particular given the type name "F", where "F" is a typedef `<T>T -> T`, will result in the function type `{dynamic/T}T->T` exactly as it did before. If we want to write the type `<T>T->T` we will need a different mechanism.)

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

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

[Jennifer Messerly, 2015-12-03 03:55:52]

Description was changed from

==========
Fixes incorrect generic function type capture
This improves how generic function types are modeled. In particular,
we can now handle types like <T>T -> T, in printing, equality, and
the type parameter is correctly removed when it is instantiated.
==========

to

==========
Fixes incorrect generic function type capture

This improves how generic function types are modeled. In particular, we can now
handle types like <T>T -> T, in printing, equality, and the type parameter is
correctly removed when it is instantiated.

This preserves the existing lazy "substitute" operation, and makes the
"instantiate" operation interact with it correctly. Given a type like:

    {T/T}<S>T -> S

we can substitute S/T to get:

    {S/T}<S>T -> S

then if we instantiate as <int> we'll get the correct:

    {S/T, int/S}T -> S, which == S -> int

This also converts typedefs over to the new system, as this seemed like the most
natural thing. (However this does *not* change how the type name is evaluated,
in particular given the type name "F", where "F" is a typedef `<T>T -> T`, will
result in the function type `{dynamic/T}T->T` exactly as it did before. If we
want to write the type `<T>T->T` we will need a different mechanism.)
==========

[Jennifer Messerly, 2015-12-03 03:55:52]

jmesserly@google.com changed reviewers:
+ brianwilkerson@google.com, leafp@google.com

[Brian Wilkerson, 2015-12-03 15:03:17]

LGTM

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

https://codereview.chromium.org/1488383004/diff/20001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:4589: * Return the type resulting
from instantiating the given [argumentTypes] for
"instantiating" --> "instantiating (replacing)"?

https://codereview.chromium.org/1488383004/diff/20001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:4918: [List<DartType> typeArguments,
It might be better to leave these as required arguments, given that it's a
private constructor and only the last argument (as far as I can see) is ever
omitted.

https://codereview.chromium.org/1488383004/diff/20001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:5361: if (argumentTypes.isEmpty) {
How often will argumentTypes be empty? If it's often enough, then waiting this
long to bail has a performance cost. Performance would be better if we checked
this condition before computing the parameterTypes, but it would allow some
error conditions to go unnoticed. Could we use "boundTypeParameters.length"
rather than "parameterTypes.length" in the previous 'if' statement? (Of course,
if it's not often enough, then the performance hit won't matter.)

https://codereview.chromium.org/1488383004/diff/20001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:6486: // TODO(jmesserly): rename
this to instantiate?
I like the idea of having a consistent nomenclature. It would be especially nice
if we could design the 'instantiate' method so that we only needed one of them
(unlike the current mess with 'substituteN'). Maybe as a follow-on CL.

[Jennifer Messerly, 2015-12-03 17:35:04]

Thanks Brian!

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

https://codereview.chromium.org/1488383004/diff/20001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:4589: * Return the type resulting
from instantiating the given [argumentTypes] for
On 2015/12/03 15:03:17, Brian Wilkerson wrote:
> "instantiating" --> "instantiating (replacing)"?

Done. Yeah I wondered if there was a better name for this method...

https://codereview.chromium.org/1488383004/diff/20001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:4918: [List<DartType> typeArguments,
On 2015/12/03 15:03:17, Brian Wilkerson wrote:
> It might be better to leave these as required arguments, given that it's a
> private constructor and only the last argument (as far as I can see) is ever
> omitted.

Done. Yeah I can just pass the 3 null's explicitly above.

https://codereview.chromium.org/1488383004/diff/20001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:5361: if (argumentTypes.isEmpty) {
On 2015/12/03 15:03:17, Brian Wilkerson wrote:
> How often will argumentTypes be empty? If it's often enough, then waiting this
> long to bail has a performance cost. Performance would be better if we checked
> this condition before computing the parameterTypes, but it would allow some
> error conditions to go unnoticed. Could we use "boundTypeParameters.length"
> rather than "parameterTypes.length" in the previous 'if' statement? (Of
course,
> if it's not often enough, then the performance hit won't matter.)

Good call. Done! In fact I don't even need parameterTypes...think that was
something I forgot to clean up.

https://codereview.chromium.org/1488383004/diff/20001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:6486: // TODO(jmesserly): rename
this to instantiate?
On 2015/12/03 15:03:17, Brian Wilkerson wrote:
> I like the idea of having a consistent nomenclature. It would be especially
nice
> if we could design the 'instantiate' method so that we only needed one of them
> (unlike the current mess with 'substituteN'). Maybe as a follow-on CL.

+1 yeah ... I'll expand the comment, seems like this method should become
"instantiate" and we should likewise have a boundTypeParameters field for
interface types, so there's a symmetry there.

I feel like that would make sense, given:

    class C<T> { T method1() { ... } T method2(T t) { ... } }

that's sort of like: <T> ( method1: () -> T, method2: T -> T, .... )

once you instantiate it becomes:

    {int/T}( method1: () -> T, method2: T -> T, ... )

It wouldn't really change any end-user-observable behavior since classes can't
be nested right now. But if we did get nested classes the distinction would
suddenly make sense. And it would make the API behavior more consistent between
FunctionType/InterfaceType.


@Leaf & Brian, does the above seem right to y'all?

[Brian Wilkerson, 2015-12-03 17:42:16]

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

https://codereview.chromium.org/1488383004/diff/20001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:4589: * Return the type resulting
from instantiating the given [argumentTypes] for
> Yeah I wondered if there was a better name for this method...

Me too. I think of "instantiate" as "create an instance of a class", but if it's
commonly used terminology in type theory, then I'm ok with it.

https://codereview.chromium.org/1488383004/diff/20001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:6486: // TODO(jmesserly): rename
this to instantiate?
> does the above seem right to y'all?

It seems consistent to me. I'm fine with postponing that work until a future CL
if you want.

[Leaf, 2015-12-03 18:46:35]

This is looking really great John.  LGTM modulo the generalization of the free
variable computation.  Also fine with me if the free variable issue gets
resolved in a followup, since this is strictly improving the state of things.

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

https://codereview.chromium.org/1488383004/diff/20001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:4589: * Return the type resulting
from instantiating the given [argumentTypes] for
On 2015/12/03 17:42:16, Brian Wilkerson wrote:
> > Yeah I wondered if there was a better name for this method...
> 
> Me too. I think of "instantiate" as "create an instance of a class", but if
it's
> commonly used terminology in type theory, then I'm ok with it.

Yeah, instantiate is the most common term that I know of - it's actually almost
by analogy of creating an instance of a class: the universal type is like a
template from which you stamp out particular concrete instances.  Other
possibilities might be "reduce" or "apply", "makeConcrete"?  I'm not coming up
with anything else I like very much right now.

https://codereview.chromium.org/1488383004/diff/20001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:6486: // TODO(jmesserly): rename
this to instantiate?
On 2015/12/03 17:42:16, Brian Wilkerson wrote:
> > does the above seem right to y'all?
> 
> It seems consistent to me. I'm fine with postponing that work until a future
CL
> if you want.

Agreed, I think instantiate would be a good choice here.

https://codereview.chromium.org/1488383004/diff/60001/pkg/analyzer/lib/src/ge...
File pkg/analyzer/lib/src/generated/element.dart (right):

https://codereview.chromium.org/1488383004/diff/60001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:5218: bool operator ==(Object
object) {
It doesn't seem to have been done before either, but I wonder if it would be
worth having a fast cutoff here when the two objects are identical?

https://codereview.chromium.org/1488383004/diff/60001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:5255: for (DartType arg in
typeArguments) {
I think you're re-inventing Simon Peyton Jones' rapier here.   :)

http://research.microsoft.com/pubs/67490/inline.pdf

I don't think this is 100% right yet though: if you take this approach I think
you need to compute the full free variable set for the type arguments, rather
than just checking for the case that an argument is a type variable.  Consider:

{List<S>/T}<S> S -> T

You want this to print as <S0> S0 -> List<S> rather than <S> S -> List<S>

The other way to tackle this is to provide a source of generativity (e.g. a 64
bit global counter somewhere) and use some encoding scheme (e.g. a character
that is not valid in normal Dart identifiers) to embed a generative tag in the
variable name.

https://codereview.chromium.org/1488383004/diff/60001/pkg/analyzer/test/gener...
File pkg/analyzer/test/generated/resolver_test.dart (right):

https://codereview.chromium.org/1488383004/diff/60001/pkg/analyzer/test/gener...
pkg/analyzer/test/generated/resolver_test.dart:13255:
expect(f.staticType.toString(), '<S₀>(S₀) → dynamic');
It's a little unfortunate that this ends up printed with a subscript.  If you go
the route of computing the free variables of the type arguments when you
generate the fresh names, then you could use the same routine to compute the
free type variables of the body of the type, and restrict the set of type
arguments that you consider as names to avoid.  

Concretely, if you had:

{S/S}<S> S -> dynamic

then you would compute FV(<S> S -> dynamic) == {}

and so you could safely compute the set of names to avoid as being empty.

More generally, if you have:

{T_0/S_0, ..., T_N/S_N} FunctionType

then the set of names to avoid are precisely the union of the FV(T_i) s.t. S_i
is in FV(FunctionType)

since for any T_i that is not in FV(FunctionType), substituting T_i/S_i into
FunctionType is a no-op.

Not sure that this is worth worrying about now, but maybe a TODO?

[Jennifer Messerly, 2015-12-03 19:20:57]

Thanks. I'll fix that toString issue and re-send

https://codereview.chromium.org/1488383004/diff/60001/pkg/analyzer/lib/src/ge...
File pkg/analyzer/lib/src/generated/element.dart (right):

https://codereview.chromium.org/1488383004/diff/60001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:5218: bool operator ==(Object
object) {
On 2015/12/03 18:46:35, Leaf wrote:
> It doesn't seem to have been done before either, but I wonder if it would be
> worth having a fast cutoff here when the two objects are identical?  

Done.

https://codereview.chromium.org/1488383004/diff/60001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:5255: for (DartType arg in
typeArguments) {
On 2015/12/03 18:46:35, Leaf wrote:
> I think you're re-inventing Simon Peyton Jones' rapier here.   :)
> 
> http://research.microsoft.com/pubs/67490/inline.pdf
> 
> I don't think this is 100% right yet though: if you take this approach I think
> you need to compute the full free variable set for the type arguments, rather
> than just checking for the case that an argument is a type variable. 
Consider:
> 
> {List<S>/T}<S> S -> T
> 
> You want this to print as <S0> S0 -> List<S> rather than <S> S -> List<S>
> 
> The other way to tackle this is to provide a source of generativity (e.g. a 64
> bit global counter somewhere) and use some encoding scheme (e.g. a character
> that is not valid in normal Dart identifiers) to embed a generative tag in the
> variable name.

DOH. You're right... I was hoping not to have to visit into anything as it's
slightly annoying to do. Wishful thinking got the better of me :)

BTW, considered the global counter -- it would definitely work but it seems like
the numbers could get quite large. Not sure how odd that would look as we don't
do it anywhere else. Certainly many languages are willing to include ID's in
their toStrings, e.g. Python and Ruby:
|>>> object()
<object object at 0x1015fd090>

irb(main):001:0> Object.new
=> #<Object:0x007f8d02007508>

https://codereview.chromium.org/1488383004/diff/60001/pkg/analyzer/test/gener...
File pkg/analyzer/test/generated/resolver_test.dart (right):

https://codereview.chromium.org/1488383004/diff/60001/pkg/analyzer/test/gener...
pkg/analyzer/test/generated/resolver_test.dart:13255:
expect(f.staticType.toString(), '<S₀>(S₀) → dynamic');
On 2015/12/03 18:46:35, Leaf wrote:
> It's a little unfortunate that this ends up printed with a subscript.  If you
go
> the route of computing the free variables of the type arguments when you
> generate the fresh names, then you could use the same routine to compute the
> free type variables of the body of the type, and restrict the set of type
> arguments that you consider as names to avoid.  
> 
> Concretely, if you had:
> 
> {S/S}<S> S -> dynamic
> 
> then you would compute FV(<S> S -> dynamic) == {}
> 
> and so you could safely compute the set of names to avoid as being empty.
> 
> More generally, if you have:
> 
> {T_0/S_0, ..., T_N/S_N} FunctionType
> 
> then the set of names to avoid are precisely the union of the FV(T_i) s.t. S_i
> is in FV(FunctionType)
> 
> since for any T_i that is not in FV(FunctionType), substituting T_i/S_i into
> FunctionType is a no-op.
> 
> Not sure that this is worth worrying about now, but maybe a TODO?


Yeah this one bothered me too. Well, if I'm going to need to implement the FV
function anyway, might as well use it to fix this. :)

[Jennifer Messerly, 2015-12-03 22:48:07]

PTAL. Fixed both printing issues.

https://codereview.chromium.org/1488383004/diff/60001/pkg/analyzer/lib/src/ge...
File pkg/analyzer/lib/src/generated/element.dart (right):

https://codereview.chromium.org/1488383004/diff/60001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/element.dart:5255: for (DartType arg in
typeArguments) {
On 2015/12/03 19:20:56, John Messerly wrote:
> On 2015/12/03 18:46:35, Leaf wrote:
> > I think you're re-inventing Simon Peyton Jones' rapier here.   :)
> > 
> > http://research.microsoft.com/pubs/67490/inline.pdf
> > 
> > I don't think this is 100% right yet though: if you take this approach I
think
> > you need to compute the full free variable set for the type arguments,
rather
> > than just checking for the case that an argument is a type variable. 
> Consider:
> > 
> > {List<S>/T}<S> S -> T
> > 
> > You want this to print as <S0> S0 -> List<S> rather than <S> S -> List<S>
> > 
> > The other way to tackle this is to provide a source of generativity (e.g. a
64
> > bit global counter somewhere) and use some encoding scheme (e.g. a character
> > that is not valid in normal Dart identifiers) to embed a generative tag in
the
> > variable name.
> 
> DOH. You're right... I was hoping not to have to visit into anything as it's
> slightly annoying to do. Wishful thinking got the better of me :)
> 
> BTW, considered the global counter -- it would definitely work but it seems
like
> the numbers could get quite large. Not sure how odd that would look as we
don't
> do it anywhere else. Certainly many languages are willing to include ID's in
> their toStrings, e.g. Python and Ruby:
> |>>> object()
> <object object at 0x1015fd090>
> 
> irb(main):001:0> Object.new
> => #<Object:0x007f8d02007508>

Done.

https://codereview.chromium.org/1488383004/diff/60001/pkg/analyzer/test/gener...
File pkg/analyzer/test/generated/resolver_test.dart (right):

https://codereview.chromium.org/1488383004/diff/60001/pkg/analyzer/test/gener...
pkg/analyzer/test/generated/resolver_test.dart:13255:
expect(f.staticType.toString(), '<S₀>(S₀) → dynamic');
On 2015/12/03 19:20:56, John Messerly wrote:
> On 2015/12/03 18:46:35, Leaf wrote:
> > It's a little unfortunate that this ends up printed with a subscript.  If
you
> go
> > the route of computing the free variables of the type arguments when you
> > generate the fresh names, then you could use the same routine to compute the
> > free type variables of the body of the type, and restrict the set of type
> > arguments that you consider as names to avoid.  
> > 
> > Concretely, if you had:
> > 
> > {S/S}<S> S -> dynamic
> > 
> > then you would compute FV(<S> S -> dynamic) == {}
> > 
> > and so you could safely compute the set of names to avoid as being empty.
> > 
> > More generally, if you have:
> > 
> > {T_0/S_0, ..., T_N/S_N} FunctionType
> > 
> > then the set of names to avoid are precisely the union of the FV(T_i) s.t.
S_i
> > is in FV(FunctionType)
> > 
> > since for any T_i that is not in FV(FunctionType), substituting T_i/S_i into
> > FunctionType is a no-op.
> > 
> > Not sure that this is worth worrying about now, but maybe a TODO?
> 
> 
> Yeah this one bothered me too. Well, if I'm going to need to implement the FV
> function anyway, might as well use it to fix this. :)

Done.

[Leaf, 2015-12-03 23:00:56]

Nice!  lgtm.

[Jennifer Messerly, 2015-12-03 23:03:07]

Description was changed from

==========
Fixes incorrect generic function type capture

This improves how generic function types are modeled. In particular, we can now
handle types like <T>T -> T, in printing, equality, and the type parameter is
correctly removed when it is instantiated.

This preserves the existing lazy "substitute" operation, and makes the
"instantiate" operation interact with it correctly. Given a type like:

    {T/T}<S>T -> S

we can substitute S/T to get:

    {S/T}<S>T -> S

then if we instantiate as <int> we'll get the correct:

    {S/T, int/S}T -> S, which == S -> int

This also converts typedefs over to the new system, as this seemed like the most
natural thing. (However this does *not* change how the type name is evaluated,
in particular given the type name "F", where "F" is a typedef `<T>T -> T`, will
result in the function type `{dynamic/T}T->T` exactly as it did before. If we
want to write the type `<T>T->T` we will need a different mechanism.)
==========

to

==========
Fixes incorrect generic function type capture

This improves how generic function types are modeled. In particular, we can now
handle types like <T>T -> T, in printing, equality, and the type parameter is
correctly removed when it is instantiated.

This preserves the existing lazy "substitute" operation, and makes the
"instantiate" operation interact with it correctly. Given a type like:

    {T/T}<S>T -> S

we can substitute S/T to get:

    {S/T}<S>T -> S

then if we instantiate as <int> we'll get the correct:

    {S/T, int/S}T -> S, which == S -> int

This also converts typedefs over to the new system, as this seemed like the most
natural thing. (However this does *not* change how the type name is evaluated,
in particular given the type name "F", where "F" is a typedef `<T>T -> T`, will
result in the function type `{dynamic/T}T->T` exactly as it did before. If we
want to write the type `<T>T->T` we will need a different mechanism.)

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

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

[Jennifer Messerly, 2015-12-03 23:03:08]

Committed patchset #5 (id:80001) manually as
6cababc94c8b0c6c25c2cb10ee042bc29fc3f763 (presubmit successful).