Consider an alternative representation for binary expressions in the syntax model

[CyrusNajmabadi]

Background and Motivation

The IDE has found that we effectively cannot ever write a recursive algorithm that processes syntax trees (which also includes using the SyntaxWalker or SyntaxRewriter classes). This is because in realistic, non-pathological cases, we encounter trees that contain node-paths so long, that any sort of recursion blows the stack. Specifically, the node paths are all similar to the form:

T X =
    "..." +
    "..." + 
    "..." + 
    // etc
    "...";

Basically, the user has a large, repetitive expression that they either generated, or they built manually. This is very common with string expressions (where people like to break things into lines), but also occurs with other binary operators.

Unfortunately, because we chose to represent these expressions with an unbalanced tree, we end up with the following

        +
"..."    +
 "..."    +
  "..."    +
//etc
            +
      "..."   "..."

In all other places where we see long lists of constructs, we have actually used lists in the syntax model, not unbalanced trees. For example, we are never really gated on hte number of statements in a block, since that's represented as a SyntaxList<StatementSyntax> and processing that list is practically done with iteration, not recursion.

Proposed API

The proposal here is fairly drastic, but i think worth consideration. I think we should effectively stop producing BinaryExpression nodes (marking them as obsolete), and move to a new NAryExpression node like so:

+[Obsolete("No longer created")]
public sealed class BinaryExpressionSyntax : ExpressionSyntax
{
    public ExpressionSyntax Left { get; }
    public ExpressionSyntax Right { get; }
}

+public sealed class NAryExpressionSyntax : ExpressionSyntax
+{
+    public SeparatedSyntaxList<ExpressionSyntax> Expressions { get; }
+}

The change here is that instead of producing unbalanced binary trees for long expressions like the one above, we would instead then produce a linear sequence of "..." + "..." + etc. within the NAryExpressionSyntax.

We would only produce such a sequence for all the consecutive expressions using the same operator (and as such the same precedence). In other words, if you had:

a * b * c * d + e + f + g + h

That would be represented as:

                      NAryExpression (SyntaxKind.AddExpression)
                     /                                         \
                    /                                      + e + f + g + h
  NAryExpression (SyntaxKind.MultiplyExpression)               
                     |
               a * b * c * d

But this would still be much better, with only one level of nesting, instead of 8.

Risks

Risks are very large here. We'd be effectively dramatically changing the syntax we create for a core case. We have stated from the beginning that that is something we might do, but we've never done so before.

However, my feeling is htat this is worth it. Primarily because the existing model is problematic for everyone. Compiler, IDE, and all our analyzer authors end up constantly having to work around this all the time. And we continually get stack overflow issues from release to release where this is missed. Since everyone has has to deal with this anyways, and it's an ongoing tax to do so, we might as well bite the bullet and move to this safer model.

As a plus, it means that we no longer have to ban certain APIs from being used as they would now be effectively safe for real world code.

[RikkiGibson]

I don't think I understand how a SyntaxKind like Add or Multiply would be represented within the NAryExpression. Particularly because it is sealed. Could you please clarify?

[CyrusNajmabadi]

@RikkiGibson the same ay they are represented with a BinaryExpression (which is already sealed). You can have many kinds mapping to a particular type.

[JimMore]

Wouldn't it be easier to create a non-recursive SyntaxWalker and use that instead?

[CyrusNajmabadi]

@JimMore can you give an example? For example, here's the impl of VisitBinaryExpression in the CSharpSyntaxRewriter:

        public override SyntaxNode? VisitBinaryExpression(BinaryExpressionSyntax node)
            => node.Update((ExpressionSyntax?)Visit(node.Left) ?? throw new ArgumentNullException("left"), VisitToken(node.OperatorToken), (ExpressionSyntax?)Visit(node.Right) ?? throw new ArgumentNullException("right"));

What were you thinking of updating this to to be non-recursive? Thanks! :)

[JimMore]

Sorry, non-recursive probably wasn't the best term to use. I was thinking using an explicit stack in the visitor rather than the call stack.

[svick]

As an alternative, types like SyntaxWalker could be changed to switch to a new thread when the stack of the current thread is running out. That seems like a much less disruptive change to me.

[CyrusNajmabadi]

This doesn't help as it doesn't address the core problem of standard recursion not working.

[JimMore]

Another option would be to balance the tree when a certain depth is reached. Obviously this would only work for associative operators, but for string concatenation that's fine. Realistically, do you need to handle other operators? A long chain of divisions for instance seems very unlikely, and you could argue that MemberAccessExpression has the same problem, or a chain of function calls. Balancing the tree would work in most realistic cases and would not require any external changes.