How to avoid recursion?

The recursion problem

I remember when I was learning programming languages at college, we started with Camel coding a lot of recursive functions.

Recursion is sometimes a very elegant and easy way to write a function.

However, it can become a big problem when the number of recursion becomes important.

Imagine a “scholar” recursive function: Fibonacci.

You can basically code it with this way:

public static BigInteger Fibonacci(int n)
{
    switch (n)
    {
        case 0: return 0;
        case 1: return 1;
        default: return Fibonacci(n – 1) + Fibonacci(n – 2);
    }
}

In my first college programming languages courses, I learnt to write it like this.

However, I now think this is bad for 2 reasons:

  • To calculate Fibonacci(n – 1) we need to recalculate Fibonacci(n -2) which makes the perf in O(exp(n)).
    Indeed, to calculate Fibonacci(2) this algorithm needs to do 1 addition.
    To calculate Fibonacci(3), it needs to do 2 additions.
    To calculate Fibonacci(4), it needs to do 4 additions.
    To calculate Fibonacci(5), it needs to do 7 additions.
    To calculate Fibonacci(6), it needs to do 12 additions.
    To calculate Fibonacci(7), it needs to do 20 additions.
    To calculate Fibonacci(8), it needs to do 33 additions.
    To calculate Fibonacci(25), it needs to do 121392 additions.
    To calculate Fibonacci(50), it needs to do 2.04E+10 additions.
    etc.

    With this algorithm, Fibonacci(40) needs more than 12 seconds to run in my machine and almost 27 seconds for Fibonacci(41).

  • If n equals 100,000 we will have a StackOverflowException because the call stack becomes too big.

How to avoid recursion?

To avoid recursion, we can use two data structures that will help us a lot: Stack and Queue.

For the Fibonacci function, we can use the following code for example:

public static BigInteger Fibonacci(int n)
{
    if (n < 2)
    {
        return n;
    }
 
    var q = new Queue<BigInteger>();
    q.Enqueue(0);
    q.Enqueue(1);
    for (int i = 2; i <= n; i++)
    {
        BigInteger n2 = q.Dequeue();
        BigInteger n1 = q.Peek();
        q.Enqueue(n2 + n1);
    }
    q.Dequeue();
    return q.Dequeue();
}

So basically the idea here is to always have the two last values. So here I used a queue for the sample however, because the number of elements we need is always 2, we can remove the queue:

public static BigInteger Fibonacci(int n)
{
    if (n < 2)
    {
        return n;
    }
 
    BigInteger n2 = 0;
    BigInteger n1 = 1;
    for (int i = 2; i <= n; i++)
    {
        BigInteger n0 = n2 + n1;
        n2 = n1;
        n1 = n0;
    }
    return n1;
}
 

With this algorithm, the perf is O(n) and there is no more StackOverflowException and Fibonacci(41) that takes almost 27 seconds with the recursive way now takes less than 1 millisecond! (and of course, the bigger n is, the better the improvement ratio is).

With the non-recursive way, it takes me only 15 milliseconds for Fibonacci(100000).

Real world scenario

The relation between primes and Fibonacci is very interesting and I’m sure that there is plenty of usage but in my case, I will probably never use it outside students, recruiting or blogging work.

As some of you know, I’m a developer in the U-SQL compiler team and U-SQL uses Roslyn (the C# compiler).

As the code is generally represented as a tree, one of the important task you have to do when you work on a compiler is tree manipulation.

For this, we can visit the tree or update the tree. This generally needs to go through the full tree.

The way to scan the tree can be the recursive one. In this case, it won’t have the performance problem we saw with the Fibonacci sample but we may have some StackOverflowException because of a potential excessive growth of the call stack.
Actually, the CSharpSyntaxRewriter implemented in Roslyn uses the recursive way and we saw some customer scripts failing because of it.

So concretely, the way it works is the following:

When we visit a node, it visits its children and then update itself.

For example:

public override CSharpSyntaxNode VisitBinaryExpression(BinaryExpressionSyntax node)
{
    var left = (ExpressionSyntax)this.Visit(node.Left);
    var operatorToken = (SyntaxToken)this.Visit(node.OperatorToken);
    var right = (ExpressionSyntax)this.Visit(node.Right);
    return node.Update(left, operatorToken, right);
}
 

Basically for “System.Console.WriteLine(“Hello” + ” “ + “{0}”, “world”);”, we will visit this tree with the mentioned index order:

Note that if arguments didn’t change, the update method will return the original node.

In order to avoid recursion, I created two new classes: CSharpNonRecursiveSyntaxWalker and CSharpNonRecursiveSyntaxRewriter to visit or update the tree without recursion (https://github.com/dotnet/roslyn/pull/12494).

How to make a syntax walker non recursive?

The non-recursive tree walker is very easy: instead of using recursion, we can use a Stack.

Roslyn provide a visitor: CSharpSyntaxVisitor. This visitor does nothing but providing virtual methods for each type of node that calls DefaultVisit that does nothing.

I created a new class CSharpNonRecursiveSyntaxWalker that does not visit children in each specific visit but push current node children in the stack and pop it while we have new elements in it:

public override void Visit(SyntaxNode node)
{
    int stackStart = _stack.Count;
    _stack.Push(node);
    while (_stack.Count > stackStart)
    {
        SyntaxNodeOrToken n = _stack.Pop();
        if (n.IsToken)
        {
            this.VisitToken(n.AsToken());
        }
        else if (!this.Skip(n.AsNode()))
        {
            this.VisitNode(n.AsNode());
            var children = n.ChildNodesAndTokens();
            for (int i = children.Count – 1; i >= 0; i–)
            {
                _stack.Push(children[i]);
            }
        }
    }
}
 

You can easily use CSharpNonRecursiveSyntaxWalker instead of CSharpSyntaxWalker. The only difference is that you have to overwrite VisitNode instead of Visit to do something for every node.

How to make a syntax rewriter non recursive?

This class needs to visit the full tree and update nodes.

This one is more complex because we need the transformed children to transform a node.

If you look at my previous sample graph the BinaryExpressionSyntax for “”Hello” + ” ” + “{0}”” needs the 18th, 24th and 25th visited nodes so they are not consecutive.

I first used a solution using a Stack of delegates (to summarize) and I use another stack to push the result that I pop to transform parent node.

However, Matt Warren proposed me a better solution because it is really closer to the current CSharpSyntaxRewriter than mine and also allows to reduce the number of instantiations.

This is how the CSharpNonRecursiveSyntaxRewriter class works.

We have three stacks: _undeconstructedStack, _untransformedStack and _transformedStack and two private CSharpSyntaxRewriter classes: _deconstructor and _reassembler.

_undeconstructedStack is the same stack that we used in the CSharpNonRecursiveSyntaxWalker.

When we pop a node from _undeconstructedStack, we push its children into this stack and we push the node, its number of children and the current count of _transformedStack (both together using a struct) into _understandformed.

However, we cannot use ChildNodesAndTokens as we did in the CSharpNonRecursiveSyntaxWalker because we need null nodes for reconstruction.

So for this, we use the _deconstructor variable. The NodeDeconstructor class overrides Visit and VisitToken to know all the children of the node needed to reconstruct it without visiting their own children.

private class NodeDeconstructor : CSharpSyntaxRewriter
{
    private List<SyntaxNodeOrToken> _elements;
 
    public void Deconstruct(SyntaxNode node, List<SyntaxNodeOrToken> elements)
    {
        _elements = elements;
        ((CSharpSyntaxNode)node).Accept(this);
    }
 
    public override SyntaxNode Visit(SyntaxNode node)
    {
        _elements.Add(node);
        return node;
    }
 
    public override SyntaxToken VisitToken(SyntaxToken token)
    {
        _elements.Add(token);
        return token;
    }
}
 

Then when all children are transformed (_transformedStack.Count == childCount + originalTransformedStackCount) we transform the node using reassembler.

As for NodeDeconstructor, this class hacks the CSharpSyntaxRewriter in order to reconstruct the current node using the already transformed children.

private class NodeReassembler : CSharpSyntaxRewriter
{
    private List<SyntaxNodeOrToken> _elements;
    private int _index;
 
    public SyntaxNodeOrToken Reassemble(SyntaxNodeOrToken original, List<SyntaxNodeOrToken> rewrittenElements)
    {
        _elements = rewrittenElements;
        _index = 0;
        return ((CSharpSyntaxNode)original).Accept(this);
    }
 
    public override SyntaxNode Visit(SyntaxNode node)
    {
        return _elements[_index++].AsNode();
    }
 
    public override SyntaxToken VisitToken(SyntaxToken token)
    {
        return _elements[_index++].AsToken();
    }
}
 

So to summarize this class works like this: Accept will call the specific Visit method (ex: the VisitBinaryExpression we saw earlier for a BinaryExpressionSyntax) which calls Visit on each children which is overridden to return the already transformed node.

Using this way, the latest transformed node is the expected result of the rewrite.

public SyntaxNode Rewrite(SyntaxNode node)
{
    int undeconstructedStart = _undeconstructedStack.Count;
    int untransformedStart = _untransformedStack.Count;
    int transformedStart = _transformedStack.Count;
 
    // add initial node so we have something to work on
    _undeconstructedStack.Push(node);
 
    // as long as there is more to deconstruct, there is more work to do
    while (_undeconstructedStack.Count > undeconstructedStart)
    {
        var nodeOrToken = _undeconstructedStack.Pop();
        if (nodeOrToken.IsNode)
        {
            node = nodeOrToken.AsNode();
 
            if (node == null)
            {
                // nulls just stay nulls, they don’t get transformed
                _transformedStack.Push(nodeOrToken);
            }
            else
            {
                SyntaxNodeOrToken rewriten;
                if (this.Skip(node, out rewriten))
                {
                    _transformedStack.Push(rewriten);
                }
                else
                {
                    // deconstruct node into child elements
                    _children.Clear();
                    _deconstructor.Deconstruct(node, _children);
 
                    // add child elements to undeconstructed stack in reverse order so
                    // the first child gets operated on next
                    for (int i = _children.Count – 1; i >= 0; i–)
                    {
                        _undeconstructedStack.Push(_children[i]);
                    }
 
                    // remember the node that will be tranformed later after the children are transformed
                    _untransformedStack.Push(new UntransformedNode(node, _children.Count, _transformedStack.Count));
                }
            }
        }
        else if (nodeOrToken.IsToken)
        {
            // we can transform tokens immediately
            var original = nodeOrToken.AsToken();
            SyntaxNodeOrToken rewriten;
            if (this.Skip(original, out rewriten))
            {
                _transformedStack.Push(rewriten);
            }
            else
            {
                var rewrittenToken = _trivializer.VisitToken(original); // rewrite trivia
                var transformed = this.VisitToken(original, rewrittenToken);
                _transformedStack.Push(transformed);
            }
        }
 
        // transform any nodes that can be transformed now
        while (_untransformedStack.Count > untransformedStart
            && _untransformedStack.Peek().HasAllChildrenOnStack(_transformedStack))
        {
            var untransformed = _untransformedStack.Pop();
 
            // gather transformed children for this node
            _children.Clear();
            for (int i = 0; i < untransformed.ChildCount; i++)
            {
                _children.Add(_transformedStack.Pop());
            }
 
            _children.Reverse();
 
            // reassemble original node with tranformed children
            var rewritten = _reassembler.Reassemble(untransformed.Node, _children);
 
            // now tranform the node
            var save = this.Original;
            this.Original = untransformed.Node;
            var transformed = this.VisitNode(untransformed.Node, rewritten.AsNode());
            this.Original = save;
 
            // add newly transformed node to the transformed stack
            _transformedStack.Push(transformed);
        }
    }
 
    Debug.Assert(_untransformedStack.Count == untransformedStart);
    Debug.Assert(_transformedStack.Count == transformedStart + 1);
 
    return _transformedStack.Pop().AsNode();
}
 

Now, you can inherit of this new class instead of CSharpSyntaxRewriter with the same change that for CSharpNonRecursiveSyntaxWalker: using VisitNode instead of Visit.

public virtual SyntaxNode VisitNode(SyntaxNode original, SyntaxNode rewritten)
{
    return ((CSharpSyntaxNode)rewritten).Accept(this);
}

Using the non-recursive implementation will improve reliability of your walker / rewriter trees with potential very big depth.

However, note that, in order to avoid recursion on rewriter, you cannot visit one part of the children and the other part of it later. For example, in U-SQL, I coded a constant folder that transforms
“anExpressionThatReturnsTrue || whateverExpression” into “true” skipping the visit of whateverExpression.

In order to allows short-circuiting scenarios, you can override ShouldRewriteChildren method:

protected virtual bool ShouldRewriteChildren(SyntaxNodeOrToken nodeOrToken, out SyntaxNodeOrToken rewritten)  

Note that using this rewriter may implies changes in your implementation.

Indeed, the pattern on Visit is often the following:

public override SyntaxNode VisitBinaryExpression(BinaryExpressionSyntax originalNode)
{
    var rewritten = base.VisitBinaryExpression(originalNode);
    //…
}
 

With the CSharpNonRecursiveSyntaxRewriter, this becomes:

public override SyntaxNode VisitBinaryExpression(BinaryExpressionSyntax rewritten)
{
    var originalNode = this. Original;
    //…
}
 

How to use annotations in Roslyn

TextSpan SyntaxTree annotation

In my previous post, I explained how to get a SyntaxTree from a U-SQL query.

Now we will see in future posts that we can change the tree significantly.

Why changing the tree? The main reason is to help the optimizer generating the best plan as possible.

For this, we are doing constant folding for example (I will write about it later). This means that we try to do some calculation in the compiler itself in order to give constants to the optimizer.

For example, imagine that we write a query like this:

DECLARE @X = 1 – 1;
@Q = SELECT (1.0 + 2 + @X) / @X AS Foo
    
FROM (VALUES(1)) AS T(r);

U-SQL, as a smart compiler, avoids useless operations at runtime by folding constants and transform the query to:

@Q = SELECT double.PositiveInfinity AS Foo
    
FROM (VALUES(1)) AS T(r);

For the following query, the compilation will fail (division by 0).

DECLARE @X = 1 – 1;
@Q = SELECT (1 + 2) + 1 / @X AS Foo
    
FROM (VALUES(1)) AS T(r);

Roslyn can give us the TextSpan of a node. The TextSpan struct includes the starting position of an expression and its length.

But at this point, the expression will no longer be “(1 + 2) + 1 / @X” but will be “3 + 1 / 0”. So if we want to give a pertinent error position to the user (“(1 + 2) + 1 ### / @X”) we need to have a way to find the original expression position and ideally, it would be great to have a way to get the original node.

To update the tree, we generally use the visitor pattern.
Roslyn provides the CSharpSyntaxRewriter for this.

Roslyn syntax nodes are immutable.
So that means that the BinaryExpressionSyntax associated to the division “(1.0 + 2 + @X) / @X” can’t be the same instance than “3.0 / 0” if we replace “(1.0 + 2 + @X)” by “3.0” and “@X” by “0”.

Note that it’s also true when you update a parent node. E.g. In the following sample e1 and n1 are not the same instance than e2 and n2.

var e1 = SyntaxFactory.IdentifierName("a");
var n1 = SyntaxFactory.IdentifierName("b");
var mae = SyntaxFactory.MemberAccessExpression(SyntaxKind.SimpleMemberAccessExpression, e1, n1);
var e2 = mae.Expression;
var n2 = mae.Name;

So we can’t just use a basic dictionary for example.

In order to keep an information on a SyntaxNode even after tree update, Roslyn provides a way using SyntaxAnnotation.

SyntaxAnnotation have 2 properties: Kind and Data.

So if you want to add a Boolean information you can use considering the value true if the annotation is present and false if it is not.

node.WithAdditionalAnnotations(new SyntaxAnnotation("USQLAnnotation"));

If you want to add a value information you can use

node.WithAdditionalAnnotations(new SyntaxAnnotation("USQLAnnotation", "foo"));

This is very easy to use but the fact that SyntaxAnnotation is a sealed class and that Data is a string limits the usage.

So as a workaround we can create our own annotations logic.

Basically we can use a Singleton with a Dictionary containing a list of our custom annotations as value.

However, as I wrote previously, in order to keep the annotation on tree after transformation we need to use Roslyn SyntaxAnnotation.

So we define a string key that is our dictionary key and our annotation data.

In our Singleton, we define two methods:

  • AddAnnotation that adds the SyntaxAnnotation with the key on the node and adds the custom annotation with the key in the dictionary
  • GetAnnotations that gets the key from the node SyntaxAnnotation and then return our custom annotations from the dictionary.
internal interface IUSqlAnnotation
{
}

internal class USqlAnnotationPool
{
  
private const string SyntaxAnnotationKey = "USQL";

   private Dictionary<string, List<IUSqlAnnotation>> annotations = new Dictionary<string, List<IUSqlAnnotation>>();
  
private int counter;

   private USqlAnnotationPool()
   {
   }

   private static readonly USqlAnnotationPool instance = new USqlAnnotationPool();
  
public static USqlAnnotationPool Instance
   {
      
get{ return instance; }
   }

   public T AddAnnotation<T>(T node, IUSqlAnnotation annotation)
      
where T : SyntaxNode
   {
      
var annotationKey = node.GetAnnotations("USQL").SingleOrDefault()?.Data;

       if (annotationKey == null)
       {
           annotationKey = SyntaxAnnotationKey + (++
this.counter).ToString();
          
this.annotations.Add(annotationKey, new List<IUSqlAnnotation>{ annotation });
           node = node.WithAdditionalAnnotations(
new SyntaxAnnotation(SyntaxAnnotationKey, annotationKey));
       }
      
else
       {
          
this.annotations[annotationKey].Add(annotation);
       }

       return node;
   }

   public IEnumerable<IUSqlAnnotation> GetAnnotations(SyntaxNode node)
   {
      
var annotationKey = node.GetAnnotations("USQL").SingleOrDefault()?.Data;
      
if (annotationKey == null)
       {
          
yield break;
       }

       foreach (var annotation in this.annotations[annotationKey])
       {
          
yield return annotation;
       }
   }
}

 

Then we can define two extension methods to make usage easier: AddAnnotation and GetAnnotations<T>.

internal static class RoslynExtensions
{
    
internal static T AddAnnotation<T>(this T node, IUSqlAnnotation annotation)
        
where T : SyntaxNode
    {

        
return USqlAnnotationPool.Instance.AddAnnotation(node, annotation);
    
}

    internal static IEnumerable<T> GetAnnotations<T>(this SyntaxNode node)
        
where T : IUSqlAnnotation
    {
        
return USqlAnnotationPool.Instance.GetAnnotations(node).OfType<T>();
    }
}

Finally, to keep original tree TextSpan, we can define our TextSpanAnnotation and add it to our SyntaxTree nodes using a SyntaxRewriter.

internal struct TextSpanAnnotation : IUSqlAnnotation
{
   public TextSpan TextSpan{ get; set; }
}

public class TextSpanAnnotator : CSharpSyntaxRewriter
{
  
private bool useDefaultAnnotation = true;

   public override SyntaxNode Visit(SyntaxNode node)
   {
      
if (node == null)
       {
          
return null;
       }

       node = base.Visit(node);
      
if (!useDefaultAnnotation)
       {
          
this.useDefaultAnnotation = true;
          
return node;
       }

       return AddAnnotation(node, GetTextSpan(node.GetFirstToken(), node.GetLastToken()), useDefaultAnnotation: true);
   }

   private TextSpan GetTextSpan(SyntaxToken firstToken, SyntaxToken lastToken)
   {

      
return new TextSpan(firstToken.SpanStart, lastToken.Span.End – firstToken.SpanStart);
   }

   private SyntaxNode AddAnnotation(SyntaxNode node, TextSpan span, bool useDefaultAnnotation = false)
   {
      
this.useDefaultAnnotation = useDefaultAnnotation;
      
return node.AddAnnotation(new TextSpanAnnotation{ TextSpan = span });
   }
}

Then we can improve the TextSpan position using specific Visit override:

   public override SyntaxNode VisitBinaryExpression(BinaryExpressionSyntax node)
   {
      
return AddAnnotation(base.VisitBinaryExpression(node), node.OperatorToken.Span);
   }

Finally, to add our TextSpanAnnotation into our tree nodes, we just need to use our TextSpanAnnotator:

syntaxTree = SyntaxFactory.SyntaxTree(new TextSpanAnnotator().Visit(syntaxTree.GetRoot()));

Then to get the position of a node in the original SyntaxTree, we can use the following code:

node.GetAnnotations<TextSpanAnnotation>().Single().TextSpan

Note that contrary to Roslyn annotations, adding a new IUSqlAnnotation to a node that already has one will not generate a new node.

This is probably better for performance but this is sometimes less convenient.

In this post, you saw how we extend the Roslyn annotation logic using our USqlAnnotationPool class.
With it, we are now capable to add whatever information we want on our SyntaxTree nodes.
These information are persisted with immutable syntax nodes along the different transformations we will apply on our tree and you will see in future posts that we are using this mechanism in many different contexts.

How do U-SQL use Roslyn?

Compiler theory

Before looking specifically to the U-SQL compiler, let’s start with a little bit of theory. How does compiler generally work?

In most cases, compiler defines a grammar that allows to parse the code into a tree.
Trees are a very good data structure to represent code that is easy to analyze / update using visitor pattern.

In compiler theory, this tree is called AST (Abstract Syntax Tree).

For example, with Roslyn, we get the following SyntaxTree parsing “Console.WriteLine(“Hello” + “World”);”

Building the syntax tree allows to check that the syntax is correct and to have a good data structure to modify the code at the compilation process (think to async / yield / etc. on C#).

Then compilers generally check the semantic in a pass (named binder in U-SQL).

In the previous sample, it means checking that

  • Usage of the AddExpression between string and string is allowed
  • Determine that string + string returns a string
  • Console.WriteLine with a string as parameter is an existing single method in the code context.

Finally, compilers generally have an error reporter step.

In U-SQL, we have 2 kinds of AST building in 2 steps

At the beginning, we use Yacc to parse U-SQL code and build our U-SQL AST.

This AST identifies expression parts.

Then we transform these expressions into C# code and get a Roslyn SyntaxTree on them.

How do we get a Roslyn SyntaxTree from U-SQL?

Imagine the following U-SQL query:

@Q = SELECT r * r * Math.[PI] AS Area
FROM (VALUES (1.0, 2.0)) AS T(r);

OUTPUT @Q TO "sample.out"
USING Outputters.Csv();

 

In the binder pass, we generate a C# code from this query using query expressions after making them syntactically correct in C#.

For example, in our sample, we will remove the square brackets around PI (in U-SQL only SQL tokens are supposed to be upper case).

Note that, Roslyn parsing is very tolerant with unknown syntax nodes. So it would also be possible to parse expressions without updating them first and then update the SyntaxTree itself to fix C# incorrect syntax.

After transforming these expressions into a correct C# code (for the syntax point of view at least), we generate a string that looks like the following code for our sample:

namespace Microsoft.USql
{
   class C
   {
      void M()
      {
         var EXTRACT0 = r * r * Math.PI;
      }
      double r;
   }
}

At this point, we can just parse this code using SyntaxFactory.ParseSyntaxTree to get our SyntaxTree.

Now that we got the SyntaxTree, we can play with Roslyn.