Add Vector type to Kernel

Add Vector type to Kernel

There are four operations that work on Vectors: Vector creation, looking
up an item in a Vector, assigning a value to an item in a Vector, and
copying a Vector. The first three operations are allowed to only use
integer literals as number operands (length for Vector creation, index
for item lookup and assignment). Corresponding AST nodes are created for
these operations.

Vectors are used to represent contexts in Closure Conversion. The parent
context is stored as item 0 in its children contexts. The "golden" tests
for this transformation are adjusted accordingly.

The support for Vectors is added to ast-to-text, ast-to-binary, and
binary-to-ast transformations.

R=asgerf@google.com, kmillikin@google.com

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

[Dmitry Stefantsov, 2017-03-22 13:15:29]

Description was changed from

==========
Add Vector type to Kernel

There are three operations that work on Vectors: Vector creation,
accessing a value stored in an item in a Vector, and assigning a value
to an item in a Vector. Corresponding AST nodes are created for these
operations.

Vectors are used to represent contexts in Closure Conversion. The
"golden" tests for this transformation are adjusted accordingly.

The support for Vectors is added to ast-to-text, ast-to-binary, and
binary-to-ast transformations.
==========

to

==========
Add Vector type to Kernel

There are three operations that work on Vectors: Vector creation, looking up an
item in a Vector, and assigning a value to an item in a Vector. All operations
are allowed to only use integer literals as operands (length for Vector
creation, index for item lookup and assignment).  Corresponding AST nodes are
created for these operations.

Vectors are used to represent contexts in Closure Conversion. The
"golden" tests for this transformation are adjusted accordingly.

The support for Vectors is added to ast-to-text, ast-to-binary, and
binary-to-ast transformations.
==========

[Dmitry Stefantsov, 2017-03-22 13:16:30]

Description was changed from

==========
Add Vector type to Kernel

There are three operations that work on Vectors: Vector creation, looking up an
item in a Vector, and assigning a value to an item in a Vector. All operations
are allowed to only use integer literals as operands (length for Vector
creation, index for item lookup and assignment).  Corresponding AST nodes are
created for these operations.

Vectors are used to represent contexts in Closure Conversion. The
"golden" tests for this transformation are adjusted accordingly.

The support for Vectors is added to ast-to-text, ast-to-binary, and
binary-to-ast transformations.
==========

to

==========
Add Vector type to Kernel

There are three operations that work on Vectors: Vector creation,
looking up an item in a Vector, and assigning a value to an item in a
Vector. All operations are allowed to only use integer literals as
operands (length for Vector creation, index for item lookup and
assignment). Corresponding AST nodes are created for these operations.

Vectors are used to represent contexts in Closure Conversion. The
"golden" tests for this transformation are adjusted accordingly.

The support for Vectors is added to ast-to-text, ast-to-binary, and
binary-to-ast transformations.
==========

[Dmitry Stefantsov, 2017-03-22 14:21:48]

dmitryas@google.com changed reviewers:
+ kmillikin@google.com

[Dmitry Stefantsov, 2017-03-22 14:25:00]

Description was changed from

==========
Add Vector type to Kernel

There are three operations that work on Vectors: Vector creation,
looking up an item in a Vector, and assigning a value to an item in a
Vector. All operations are allowed to only use integer literals as
operands (length for Vector creation, index for item lookup and
assignment). Corresponding AST nodes are created for these operations.

Vectors are used to represent contexts in Closure Conversion. The
"golden" tests for this transformation are adjusted accordingly.

The support for Vectors is added to ast-to-text, ast-to-binary, and
binary-to-ast transformations.
==========

to

==========
Add Vector type to Kernel

There are four operations that work on Vectors: Vector creation, looking
up an item in a Vector, assigning a value to an item in a Vector, and
copying a Vector. The first three operations are allowed to only use
integer literals as number operands (length for Vector creation, index
for item lookup and assignment). Corresponding AST nodes are created for
these operations.

Vectors are used to represent contexts in Closure Conversion. The parent
context is stored as item 0 in its children contexts. The "golden" tests
for this transformation are adjusted accordingly.

The support for Vectors is added to ast-to-text, ast-to-binary, and
binary-to-ast transformations.
==========

[asgerf, 2017-03-22 14:33:21]

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

[asgerf, 2017-03-22 14:33:22]

Very nice.

At the places where only IntLiterals are allowed, why not just store an 'int'?
It seems wasteful to use an IntLiteral here.

Apart from that I have some comments about consistency with the rest of kernel.

https://codereview.chromium.org/2767773004/diff/80001/pkg/kernel/lib/ast.dart
File pkg/kernel/lib/ast.dart (right):

https://codereview.chromium.org/2767773004/diff/80001/pkg/kernel/lib/ast.dart...
pkg/kernel/lib/ast.dart:2755: final IntLiteral length;
The kernel AST is mutable, only List fields should be final.

https://codereview.chromium.org/2767773004/diff/80001/pkg/kernel/lib/ast.dart...
pkg/kernel/lib/ast.dart:2769: length.accept(v);
transformChildren should replace the children, not just visit them.

https://codereview.chromium.org/2767773004/diff/80001/pkg/kernel/lib/text/ast...
File pkg/kernel/lib/text/ast_to_text.dart (right):

https://codereview.chromium.org/2767773004/diff/80001/pkg/kernel/lib/text/ast...
pkg/kernel/lib/text/ast_to_text.dart:1044: writeWord('=');
Please change to writeSpaced('=')

[karlklose, 2017-03-22 14:34:18]

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

[karlklose, 2017-03-22 14:34:19]

https://codereview.chromium.org/2767773004/diff/80001/pkg/kernel/test/closure...
File pkg/kernel/test/closures/suite.dart (right):

https://codereview.chromium.org/2767773004/diff/80001/pkg/kernel/test/closure...
pkg/kernel/test/closures/suite.dart:67: // TODO(dmitryas): uncomment this when
Vectors are added to VM.
Maybe file a bug and reference its number in the TODO (instead of your name).

[Dmitry Stefantsov, 2017-03-23 11:22:43]

PTAL

https://codereview.chromium.org/2767773004/diff/80001/pkg/kernel/lib/ast.dart
File pkg/kernel/lib/ast.dart (right):

https://codereview.chromium.org/2767773004/diff/80001/pkg/kernel/lib/ast.dart...
pkg/kernel/lib/ast.dart:2755: final IntLiteral length;
On 2017/03/22 14:33:22, asgerf wrote:
> The kernel AST is mutable, only List fields should be final.

Thanks! Done.

https://codereview.chromium.org/2767773004/diff/80001/pkg/kernel/lib/ast.dart...
pkg/kernel/lib/ast.dart:2769: length.accept(v);
On 2017/03/22 14:33:22, asgerf wrote:
> transformChildren should replace the children, not just visit them.

Of course. Thanks! Fixed.

https://codereview.chromium.org/2767773004/diff/80001/pkg/kernel/lib/text/ast...
File pkg/kernel/lib/text/ast_to_text.dart (right):

https://codereview.chromium.org/2767773004/diff/80001/pkg/kernel/lib/text/ast...
pkg/kernel/lib/text/ast_to_text.dart:1044: writeWord('=');
On 2017/03/22 14:33:22, asgerf wrote:
> Please change to writeSpaced('=')

Thanks! Done.

https://codereview.chromium.org/2767773004/diff/80001/pkg/kernel/test/closure...
File pkg/kernel/test/closures/suite.dart (right):

https://codereview.chromium.org/2767773004/diff/80001/pkg/kernel/test/closure...
pkg/kernel/test/closures/suite.dart:67: // TODO(dmitryas): uncomment this when
Vectors are added to VM.
On 2017/03/22 14:34:19, karlklose wrote:
> Maybe file a bug and reference its number in the TODO (instead of your name).

Good idea! Done.

[asgerf, 2017-03-23 11:53:51]

Another round of comments

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dart
File pkg/kernel/lib/ast.dart (right):

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:2753: /// Expression of the form `MakeVector(N)` where
`N` is an integer literal.
`N` is no longer an integer literal. It would be more useful to say e.g. "where
`N` is the length of the vector".

The form `MakeVector(N)` doesn't really mean much. I used that style to document
some AST nodes that have an obvious correspondence to a Dart syntactic form, but
this is not the case here.

I would like to see some documentation to explain what a "vector" is and what
they are used for, and this seems like a good place to do it (or perhaps on
VectorType).

A couple of points worth mentioning:
- Vectors are fixed-length
- Not user-visible objects
- Access to vectors is untyped and without bounds checks
- Vectors are introduced by closure conversion

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:2800: /// Expressoins of the form `v[i] = x` where `v`
is a vector expression, `i` is
Expressoins -> Expression

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:2836: /// Expression of the form `CopyVector(v)` where
`v` is a vector expressoin.
expressoin -> expression

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:3765: class VectorType extends DartType {
Please check all existing DartTypeVisitors and override visitVectorType if
necessary.  I know _TypeSubstitutor in type_algebra.dart needs it.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/type_ch...
File pkg/kernel/lib/type_checker.dart (right):

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/type_ch...
pkg/kernel/lib/type_checker.dart:694: return const DynamicType();
Visit the "vector" subexpression to ensure it is type checked.

We could also check that the "vector" subexpression has static type VectorType.
(Otherwise why have the VectorType?)

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/type_ch...
pkg/kernel/lib/type_checker.dart:699: return
node.value.getStaticType(environment);
We should not use getStaticType from the type checker as it does not recursively
type check all subexpressions, it only does what is necessary to compute the
type of that one expression.

The correct form would be:
  visitExpression(node.vector);
  return visitExpression(node.value);

As above, we could also check that the vector has type VectorType.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/type_ch...
pkg/kernel/lib/type_checker.dart:704: return node.getStaticType(environment);
Same as above.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/type_ch...
pkg/kernel/lib/type_checker.dart:709: return node.getStaticType(environment);
Even though there are no subexpressions here, please refrain from calling
getStaticType altogether and just return const VectorType().

[Kevin Millikin (Google), 2017-03-23 12:01:04]

LGTM.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dart
File pkg/kernel/lib/ast.dart (right):

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:2753: /// Expression of the form `MakeVector(N)` where
`N` is an integer literal.
'integer literal' ==> 'integer'.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:2772: /// an integer literal used as an index.
'integer literal' ==> 'integer'.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:2800: /// Expressoins of the form `v[i] = x` where `v`
is a vector expression, `i` is
'Expressoins' ==> 'Expressions'.
'integer literal' ==> 'integer'.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:2836: /// Expression of the form `CopyVector(v)` where
`v` is a vector expressoin.
'expressoin' ==> 'expression'.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/binary/...
File pkg/kernel/lib/binary/tag.dart (right):

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/binary/...
pkg/kernel/lib/binary/tag.dart:106: static const int VectorCreation = 103;
I can't figure out why there are sometimes gaps between tags.

[Kevin Millikin (Google), 2017-03-23 12:01:50]

But please also update binary.md.

[Dmitry Stefantsov, 2017-03-27 10:57:09]

PTAL

Asger, can you please check if I made the right changes in "type_checker.dart",
"type_algebra.dart", and "type_propagation/builder.dart".

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dart
File pkg/kernel/lib/ast.dart (right):

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:2753: /// Expression of the form `MakeVector(N)` where
`N` is an integer literal.
On 2017/03/23 12:01:03, Kevin Millikin (Google) wrote:
> 'integer literal' ==> 'integer'.

Done.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:2753: /// Expression of the form `MakeVector(N)` where
`N` is an integer literal.
On 2017/03/23 11:53:50, asgerf wrote:
> `N` is no longer an integer literal. It would be more useful to say e.g.
"where
> `N` is the length of the vector".
> 
> The form `MakeVector(N)` doesn't really mean much. I used that style to
document
> some AST nodes that have an obvious correspondence to a Dart syntactic form,
but
> this is not the case here.
> 
> I would like to see some documentation to explain what a "vector" is and what
> they are used for, and this seems like a good place to do it (or perhaps on
> VectorType).
> 
> A couple of points worth mentioning:
> - Vectors are fixed-length
> - Not user-visible objects
> - Access to vectors is untyped and without bounds checks
> - Vectors are introduced by closure conversion

Yes. It makes sense. I put the detailed comment next to VectorType.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:2772: /// an integer literal used as an index.
On 2017/03/23 12:01:03, Kevin Millikin (Google) wrote:
> 'integer literal' ==> 'integer'.

Done.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:2800: /// Expressoins of the form `v[i] = x` where `v`
is a vector expression, `i` is
On 2017/03/23 11:53:50, asgerf wrote:
> Expressoins -> Expression

Done.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:2800: /// Expressoins of the form `v[i] = x` where `v`
is a vector expression, `i` is
On 2017/03/23 12:01:03, Kevin Millikin (Google) wrote:
> 'Expressoins' ==> 'Expressions'.
> 'integer literal' ==> 'integer'.

Done.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:2836: /// Expression of the form `CopyVector(v)` where
`v` is a vector expressoin.
On 2017/03/23 11:53:50, asgerf wrote:
> expressoin -> expression

Done.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:2836: /// Expression of the form `CopyVector(v)` where
`v` is a vector expressoin.
On 2017/03/23 12:01:03, Kevin Millikin (Google) wrote:
> 'expressoin' ==> 'expression'.

Done.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:3765: class VectorType extends DartType {
On 2017/03/23 11:53:50, asgerf wrote:
> Please check all existing DartTypeVisitors and override visitVectorType if
> necessary.  I know _TypeSubstitutor in type_algebra.dart needs it.

Thanks! Done.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/binary/...
File pkg/kernel/lib/binary/tag.dart (right):

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/binary/...
pkg/kernel/lib/binary/tag.dart:106: static const int VectorCreation = 103;
On 2017/03/23 12:01:03, Kevin Millikin (Google) wrote:
> I can't figure out why there are sometimes gaps between tags.

Apparently, for no reason in this case :) Changed the numbers so that there's no
gap.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/type_ch...
File pkg/kernel/lib/type_checker.dart (right):

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/type_ch...
pkg/kernel/lib/type_checker.dart:694: return const DynamicType();
On 2017/03/23 11:53:51, asgerf wrote:
> Visit the "vector" subexpression to ensure it is type checked.
> 
> We could also check that the "vector" subexpression has static type
VectorType.
> (Otherwise why have the VectorType?)

Done.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/type_ch...
pkg/kernel/lib/type_checker.dart:699: return
node.value.getStaticType(environment);
On 2017/03/23 11:53:51, asgerf wrote:
> We should not use getStaticType from the type checker as it does not
recursively
> type check all subexpressions, it only does what is necessary to compute the
> type of that one expression.
> 
> The correct form would be:
>   visitExpression(node.vector);
>   return visitExpression(node.value);
> 
> As above, we could also check that the vector has type VectorType.

Done.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/type_ch...
pkg/kernel/lib/type_checker.dart:704: return node.getStaticType(environment);
On 2017/03/23 11:53:51, asgerf wrote:
> Same as above.

Done.

https://codereview.chromium.org/2767773004/diff/100001/pkg/kernel/lib/type_ch...
pkg/kernel/lib/type_checker.dart:709: return node.getStaticType(environment);
On 2017/03/23 11:53:51, asgerf wrote:
> Even though there are no subexpressions here, please refrain from calling
> getStaticType altogether and just return const VectorType().

Done.

[asgerf, 2017-03-27 11:15:39]

LGTM

https://codereview.chromium.org/2767773004/diff/140001/pkg/kernel/lib/ast.dart
File pkg/kernel/lib/ast.dart (right):

https://codereview.chromium.org/2767773004/diff/140001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:3792: ///     contexts.
Great! Please use markdown syntax, though.

https://codereview.chromium.org/2767773004/diff/140001/pkg/kernel/lib/type_pr...
File pkg/kernel/lib/type_propagation/builder.dart (right):

https://codereview.chromium.org/2767773004/diff/140001/pkg/kernel/lib/type_pr...
pkg/kernel/lib/type_propagation/builder.dart:1808: return builder.vectorNode;
Just throw an exception here. This visitor analyses the signature of a native
method, and they can't use a VectorType in their signature.

[Dmitry Stefantsov, 2017-03-27 12:17:24]

https://codereview.chromium.org/2767773004/diff/140001/pkg/kernel/lib/ast.dart
File pkg/kernel/lib/ast.dart (right):

https://codereview.chromium.org/2767773004/diff/140001/pkg/kernel/lib/ast.dar...
pkg/kernel/lib/ast.dart:3792: ///     contexts.
On 2017/03/27 11:15:39, asgerf wrote:
> Great! Please use markdown syntax, though.

Done.

https://codereview.chromium.org/2767773004/diff/140001/pkg/kernel/lib/type_pr...
File pkg/kernel/lib/type_propagation/builder.dart (right):

https://codereview.chromium.org/2767773004/diff/140001/pkg/kernel/lib/type_pr...
pkg/kernel/lib/type_propagation/builder.dart:1808: return builder.vectorNode;
On 2017/03/27 11:15:39, asgerf wrote:
> Just throw an exception here. This visitor analyses the signature of a native
> method, and they can't use a VectorType in their signature.

Done.

[Dmitry Stefantsov, 2017-03-27 13:52:47]

Description was changed from

==========
Add Vector type to Kernel

There are four operations that work on Vectors: Vector creation, looking
up an item in a Vector, assigning a value to an item in a Vector, and
copying a Vector. The first three operations are allowed to only use
integer literals as number operands (length for Vector creation, index
for item lookup and assignment). Corresponding AST nodes are created for
these operations.

Vectors are used to represent contexts in Closure Conversion. The parent
context is stored as item 0 in its children contexts. The "golden" tests
for this transformation are adjusted accordingly.

The support for Vectors is added to ast-to-text, ast-to-binary, and
binary-to-ast transformations.
==========

to

==========
Add Vector type to Kernel

There are four operations that work on Vectors: Vector creation, looking
up an item in a Vector, assigning a value to an item in a Vector, and
copying a Vector. The first three operations are allowed to only use
integer literals as number operands (length for Vector creation, index
for item lookup and assignment). Corresponding AST nodes are created for
these operations.

Vectors are used to represent contexts in Closure Conversion. The parent
context is stored as item 0 in its children contexts. The "golden" tests
for this transformation are adjusted accordingly.

The support for Vectors is added to ast-to-text, ast-to-binary, and
binary-to-ast transformations.

R=asgerf@google.com, kmillikin@google.com

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

[Dmitry Stefantsov, 2017-03-27 13:52:49]

Committed patchset #9 (id:160001) manually as
9ab86da19cc8e3e55266066bcebf09f6bbc5f612 (presubmit successful).