Notes from Prototyping #104 - Extend `For Each` statement with query comprehensions

I've prototyped the feature originally suggested in issue #104. See that issue for context/motivation.

A [video summary](https://www.youtube.com/watch?v=ynBHLuicCYs) demonstrating the prototype can be seen here:

[](http://www.youtube.com/watch?v=ynBHLuicCYs)

The source for the prototype can be found in branch [prototypes/enhanced-for-each](https://github.com/AnthonyDGreen/roslyn/tree/prototypes/enhanced-for-each) of my fork.

This prototype extends the `For Each` construct with:

1. Support for all query operators, e.g.

```VB.NET
For Each x In y
Where P(x)

Next
```

2. Support for declaring multiple variables sourced from multiple collections in a comma delimited list (#48), e.g.

``` VB.NET
For Each x In A,
y In B

Next
```

> ADG: I like this syntax in general, but it's especially important to avoid requiring the awkward syntax:
> `For Each x In y From y In B` which means exactly the same thing but... well, just look at it!

**Note**: (1) and (2) can be used in combination.

3. Support for implicit line-continuation after the `Each` keyword, e.g.

``` VB.NET
For Each
x In A
Join
y In B
On
x.Id Equals y.Id

Next
```

# Language Design

## Syntax

`For Each` _ControlVariable_ `In` _Expression_ [ `,` _AdditionalRangeVariables_ ] [ _QueryClauses_ ]
[ _Statements_ ]
`Next`

1. If _AdditionalRangeVariables_ or _QueryClauses_ is specified, _ControlVariable_ must take the form of:

_identifier_ [ `As` _Type_ ]

This restriction is imposed by query expressions, which always declare new range variables and never reference existing l-values as range variables.

**Note**: It is illegal to use the nullable modifier `?` without specifying an `As` clause today in both `For Each` control variables and range variable declarations.

2. _AdditionalRangeVariables_ is a comma-separated list of collection range variables of the form:

_identifier2_ [ `As` _Type2_ ] `In` _expression2_ [, _identifier3_ [ `As` _Type3_ ] `In` _expression3_ [ `,` ... ] ]

3. _QueryClauses_ is a list of query clauses (**without restriction**) as specified elsewhere (in the spec).

4. **NEW** An optional newline may now follow the `Each` keyword.
* This is consistent with what is permitted after `From`.
* It is **already** legal for a newline to follow the `In` keyword.

5. An optional newline may follow the comma before _AdditionalRangeVariables_ and any comma between range variables.

6. All other rules regarding line continuation (newlines) within and between collection range variables and query clauses is as specified in the spec.

## Semantics

Given a `For Each` statement of the form:

`For Each I [ As T ] In E [, AdditionalRangeVariables ] [ QueryClauses ]`

Where _AdditionalRangeVariables_ and/or _QueryClauses_ are present:

1. The identifier `I` and optional `As` clause specifying type `T` after the `Each` keyword, and the expression after the `In` keyword are _first_ used to synthesize a query expression.
a. If the optional `As` clause is specified, the query will be synthesized as if written `From I As T In E`
b. If the optional `As` clause is omitted, the query will be synthesized as if written `From I In E`
* Note: `Option Infer Off` does not cause an error to be reported in this case (as it would not were the query explicitly written).

c. `E` must therefore satisfy the **Queryable** pattern (have a `Select` method)
d. If _AdditionalRangeVariables_ is specified the list of collection range variable declarators are appended to the `From` operator as though it had been written `From I As T In E, I2 As T2 In T2, ...`

2. Any subsequent query clauses are then applied.
a. If 0 range variables are in scope after completely constructing the query, an error is reported.
b. If any range variables are unnamed, an error is reported.

3. The result of synthesized query expression is then bound as the source collection
a. The type of the synthesized query expression must therefore satisfy the **Collection** pattern (have a `GetEnumerator` method).

4. If exactly one range variable, with name `v`, remains in scope after applying all query operators (i.e. the query resulted in a sequence of scalars), the loop is bound as if written:

``` VB.NET
Dim $temp = $QueryExpression
For Each v In QueryExpression
...
Next
```

**Note**: The `Select` operator may remove the original range variables from the result and/or introduce new range variables with different names. The name of the `$current` variable is the name in scope at the end, not at the start!

**Note**: In the common case only a single range variable is ever introduced and therefore has the same name as the identifier following the `Each` keyword (though this is **not** required). Normally, the collection expression of a `For Each` is bound after the declaration of the control variable and as such can refer to the control variable. In the case that the collection expression is a query the it is illegal to use the same name as the control variable for any range variable in the query expression because it is prohibited for range variables to shadow local variables. But as prototyped, the synthesized query expression is bound _before_ the rest of the `For Each` statement so the declaration of the `For Each` control variable `x` does not cause collisions with the range variable `x` that appears in the query even if they both share the same name.

**Note**: IDE will have to do cascading rename/find-references to account for this behavior.

5. If more than one range variable remains in scope after applying all query operators (i.e. the query resulted in a sequence of anonymous type objects), a new variable is declared within the body of the loop (i.e. captured per iteration) for each range variable and initialized with the value of the anonymous type property corresponding to that variable:

``` VB.NET
Dim $temp = $QueryExpression
For Each $current In QueryExpression
Dim v1 = $current.v1,
v2 = $current.v2, ...
...
Next
```

> **ADG**: *As implemented, I cache the result of `$enumerator.Current` in `$current` to avoid multiple calls to `.Current` and whatever side-effects they might have.*

> **ADG**: *There's an optimization opportunity here, I think. If a range variabe is never written to we could elide it entirely and rewrite all references to it as references to the anonymous type property instead.*

## Other Issues

### 1. Can we optimize this to generate imperative code and not invoke method/allocate lambdas/enumerables/etc.?

**In the case that the source collection is `IQueryable`**, lowering should definitely bind it using LINQ. The performance implications of executing the query remotely on the server rather than in-memory using imperative code cannot be overstated.

**In the case that the query expression is **NOT** using IQueryable and using well-known methods** (e.g. `System.Linq.Enumerable` methods), we can generate all of the iteration code imperatively. I was not originally particular about this point but upon considering the number of use cases this would open up I'm not a strong proponent. The Roslyn compilers avoid LINQ for fear of allocations. Because we know that the intermediate `IEnumerable` objects don't "escape" we could elite them entirely and generate all the query operators imperatively. This is particularly seductive in the case of `For Each x In A, y In B` where no query operators are even used. Though as implemented this invokes `SelectMany` it's very understandable that a user would expect this to be equivalent to nested `For Each` loops.

That said, **we should make this pattern-based** by recognizing some set of attributes on the query methods to allow arbitrary collection types to opt into this optimized code-gen as the compiler data structures don't always implement `IEnumerable(Of T)`. Another similar optimization we should open up to 3rd-party collections is the one where `For Each` over arrays and strings today use an indexer rather than the enumerator. Today code in Roslyn is sometimes forced to use `For` rather than `For Each` to get perf benefits that would be free were the code using plain arrays.

### 2. Multiple control variables

It's understandable that given that this works today:

``` VB.NET
For Each M(p).X In s1
For Each N(p).Y In s2

Next
Next
```

One might expect this to work:

``` VB.NET
For Each M(p).X In s1,
N(p).Y In s2

Next
```

I can be done. It's not particularly hard but is utterly out of the question unless we **specify** that this code must transform into nested `For Each` loops. As implemented `For Each x In A, y In B` lowers to a call to `SelectMany` and as such neither declarator is permitted to reference an existing l-value. Doing this moves changing the code-gen strategy from the realm of **optimization** to **requirement**. And again, in the `IQueryable` case generating the code imperatively would be **disastrous**.

> **ADG**: *I'm **very** inclined to call this scenario unsupported.*

### 3. Multiple next variables

All of these cases are logically consistent within the language as it works today. That is to say that they make sense. They might even be inexpensive.

**Should this work?**

``` VB.NET
For Each x In A,
y In B
Where x = y
Select z = 1

...

Next z
```

**Should this work?**

``` VB.NET
For Each x In A,
y In B
Where x = y

...

Next y, x
```

**Should this work?**

``` VB.NET
For Each x In A,
y In B
Where x = y

For Each z In C

...

Next z, y, x
```

> **ADG**: *I hear Chuck Stoner screaming. I don't like **NOT** doing logically consistent things out of sheer laziness. But one issue I have with letting you refer to each range variable as though it were a separate variable in a separate loop is that it's not sustainable. There are other proposals #186 and #207 to support explicit `Continue For x` and `Exit For y` statements. Those statements do not make sense in combination with these variables **at all**.*

### 4. If the query operators return a type that would otherwise be optimized during rewrite (vector arrays or strings), should we bail on optimized rewriting?

e.g. if the query results in an array should we still optimize the `For Each` into a `For`?

> **ADG**: *I suppose this optimization is in conflict with issue (1).*

# Syntax API Design

## Shape

### Design 1 (Currently implemented)

The current design aims to be minimally disruptive by extending the existing `ForEachStatementSyntax` with new optional children:

* `ForKeyword As SyntaxToken`
* `EachKeyword As SyntaxToken`
* `ControlVariable As SyntaxNode`
* `InKeyword As SyntaxToken`
* `Expression As ExpressionSyntax`
* Optional `CommaToken As SyntaxToken`
* Optional `AdditionalRangeVariables As SeparatedSyntaxList(Of CollectionRangeVariableSyntax)`
* Optional `QueryClauses As SyntaxList(Of QueryClauseSyntax)`

Note: All previous `SyntaxFactory` and `Update` methods had to be manually recreated for back-compat.

**Pros/Cons**

* **Pro**: This means we don't need to duplicate a lot of code that today works with `For Each` blocks in order to work with a new special `EnhancedForEachBlockSyntax`. Of course, that code might make faulty assumptions when the new syntax changes semantics a little, e.g. assuming only 1 control variable is in scope or that it's declarator is the declarator of the `ForEachStatementSyntax`, etc.

* **Pro**: The comma and the comma-separated list are separate to preserve the convention (invariant?) that comma separated syntax lists never begin with a comma (that commas are always at odd indices). There could be perf implications of changing this.

* **Con**: This violates the convention that when two adjacent children (the comma and the additional variables) must either both be present or both be absent that they are represented as a single node. Doing so would require the creation of a `CommaAddionalVariablesSyntax` node.

* **Pro**: Not adding such an intermediary also has the benefit that the `Parent` of the additional `CollectionRangeVariableSyntax` nodes is the `ForEachStatementSyntax` itself much like the control variable declarator, for whatever that's worth.

### Design 2 - Query Expression on the Side

A `For Each` statement consists of the tokens `For Each` and **either** all the stuff that's there today or a query expression where the first query operator is a new query operator that's just like a `FromQueryClause` but without the `From` keyword.

```
For Each ( control [As Clause] In expression | QueryExpression )

ImplicitFromClause ::= CollectionRangeVariable [, ...]
```

**Pros/Cons**

* **Pro**: Just adds a new query operator
* **Con**: New single-use "implicit `From`" query clause.
* **Pro**: Less disruptive to query code as range variables are always parented by query clauses (never `ForEachStatementSyntax`) and query clauses are always parented by query expressions.
* **Con**: A little more disruptive to `For Each` statement because it retroactively makes the last 4 children of a ForEachStatementSyntax optional.

### Design 3 - Query Clauses on the Side, hold the `From` keyword

A hybrid of (1) and (2). The `ForEachStatementSyntax` is still extended with query clauses, but the whole additional range variables thing is stuffed into a new special-case query clause just for this.

```
For Each control [As Clause] In expression [ QueryClause+ ]

ImplicitFromClause ::= , CollectionRangeVariable [, ...]
```

**Pros/Cons**

* **Pro**: Collection range variables always parented by "query clause", but query clause sometimes parented by `For Each` statements.
* **Pro**: None of the existing children become optional.
* **Con**: New single-use "comma implicit `From`" query clause.

## Other issues

### While I'm in there...

Modifying the syntax API to support to support this is doable but disruptive. Not to the author of the feature, that work is easy enough. But it is a bit disruptive to consumers. A second more disruptive change would be supporting tuple deconstruction in queries and/or `For Each`. If we're going to be doing reconstructive surgery on `ForEachStatementSyntax` and/or `CollectionRangeVariable`, it could be nice to fix it all at once. e.g.

What if we unified all declarators across the **VB Syntax API** to "fit" the union of possibilities: (Expression | ModifiedIdentifier AsClause | Tuple), while still enforcing the current restrictions on what concrete derivatives can actually be used within any given construct?

### Collisions with other potential upcoming features

I'm proposing we extend the existing `For Each` statement (and block) nodes to add queries. But with async streams in the wild it's foreseeable that we might either add an `Await Each` (or whatever) construct to the language. At which point is that another modification to the existing `For Each` or a new block? If there are now two statements, `ForEachStatementSyntax` and `AwaitEachStatementSyntax` does all this work have to be duplicated to support query clauses over async streams? And what about async query expressions (as opposed to synchronous query expressions over async sequences)? If there's an `Async From` expression or `Async Where` clause how does it combine with this feature across both synchronous and asynchronous `For Each`!?!?!?!? Do we have 2x2x2=8 new blocks?

> **ADG**:* **Of course not**! But it's good to keep this in mind.*