My recursive parser is wet behind the ears (well, it's not DRY at least)

Question

I have an issue opened on GitHub since mid-November, to refactor & DRY up the Rubberduck Parser module (the idea is to model the code in a VBA project or code module, so it can be browsed and inspected programmatically).

Yes, I've written this ........crap. I'm guilty of Ctrl+C/Ctrl+V coding here, of which I'm very unproud, but I'm not sure if it's because I messed up or because it's just the way it has to be (please, no!).

[ComVisible(false)]
public class Parser
{
    private readonly IEnumerable<ISyntax> _grammar;

    public Parser(IEnumerable<ISyntax> grammar)
    {
        _grammar = grammar;
    }

    public SyntaxTreeNode Parse(VBProject project)
    {
        var nodes = new List<SyntaxTreeNode>();
        try
        {
            var components = project.VBComponents.Cast<VBComponent>().ToList();
            foreach (var component in components)
            {
                var lineCount = component.CodeModule.CountOfLines;
                if (lineCount <= 0)
                {
                    continue;
                }

                var code = component.CodeModule.Lines[1, lineCount];
                var isClassModule = component.Type == vbext_ComponentType.vbext_ct_ClassModule
                                    || component.Type == vbext_ComponentType.vbext_ct_Document
                                    || component.Type == vbext_ComponentType.vbext_ct_MSForm;

                nodes.Add(Parse(project.Name, component.Name, code, isClassModule));
            }
        }
        catch
        {
            // todo: handle exception like a chief
            Debug.Assert(false);
        }

        return new ProjectNode(project, nodes);
    }

    /// <summary>
    /// Converts VBA code into a <see cref="SyntaxTreeNode"/>.
    /// </summary>
    /// <param name="projectName">The name of the VBA Project, used for scoping public nodes.</param>
    /// <param name="componentName">The name of the module, used for scoping private nodes.</param>
    /// <param name="code">The code to parse.</param>
    /// <returns></returns>
    public SyntaxTreeNode Parse(string projectName, string componentName, string code, bool isClassModule)
    {
        var content = SplitLogicalCodeLines(projectName, componentName, code);
        var memberNodes = ParseModuleMembers(projectName, componentName, content).ToList();

        var result = new ModuleNode(projectName, componentName, memberNodes, isClassModule);
        return result;
    }

A bit of VBA theory here. In VBA, a code line can be "continued" using a "line continuation character", like this:

Dim foo As Integer, _
    bar As String, _
    baz As SomethingElse

The code module will give me 3 lines for the above, but it's really 1 "logical" code line, with one instruction that declares 3 variables. The SplitLogicalCodeLines method scans the VBA source code and returns a LogicalCodeLine for each, well, logical code line:

    private IEnumerable<LogicalCodeLine> SplitLogicalCodeLines(string projectName, string componentName, string content)
    {
        const string lineContinuationMarker = "_";

        var lines = content.Split('\n').Select(line => line.Replace("\r", string.Empty)).ToList();

        var logicalLine = new StringBuilder();
        var startLine = 0;
        var isContinuing = false;
        for (var index = 0; index < lines.Count; index++)
        {
            if (!isContinuing)
            {
                startLine = index + 1;
            }

            var line = lines[index];
            if (line.EndsWith(lineContinuationMarker))
            {
                isContinuing = true;
                logicalLine.Append(line.Remove(line.Length - 1));
            }
            else
            {
                logicalLine.Append(line);
                yield return new LogicalCodeLine(projectName, componentName, startLine, index + 1, logicalLine.ToString());
                logicalLine.Clear();
                isContinuing = false;
            }
        }
    }

Each logical code line can contain a number of instructions, each separated by an instruction separator character - in VBA that's the colon (:). I've implemented that part in the LogicalCodeLine structure, and there's a little issue with properly splitting instructions when an instruction contains a string literal that contains a colon, so I'm not including that struct for review.

So far so good? Here's the annoying/offending code: ParseCodeBlock is pretty much a carbon copy of ParseModuleMembers - this is what I'd like to clean up:

    private IEnumerable<SyntaxTreeNode> ParseModuleMembers(string publicScope, string localScope, IEnumerable<LogicalCodeLine> logicalCodeLines)
    {
        var currentLocalScope = localScope;
        var lines = logicalCodeLines.ToArray();
        for (var index = 0; index < lines.Length; index++)
        {
            var line = lines[index];
            if (string.IsNullOrWhiteSpace(line.Content))
            {
                continue;
            }

            var instructions = line.SplitInstructions();
            foreach (var instruction in instructions)
            {
                var parsed = false;
                foreach (var syntax in _grammar.Where(s => !s.IsChildNodeSyntax))
                {
                    SyntaxTreeNode node;
                    if (!syntax.IsMatch(publicScope, currentLocalScope, instruction, out node))
                    {
                        continue;
                    }

                    if (syntax.Type.HasFlag(SyntaxType.HasChildNodes))
                    {
                        var codeBlockNode = node as CodeBlockNode;
                        if (codeBlockNode != null)
                        {
                            if (node is ProcedureNode)
                            {
                                currentLocalScope = localScope + "." + (node as ProcedureNode).Identifier.Name;
                                yield return  ParseProcedure(publicScope, currentLocalScope, node as ProcedureNode, lines, ref index);
                                currentLocalScope = localScope; 
                                parsed = true;
                                break;
                            }

                            yield return ParseCodeBlock(publicScope, currentLocalScope, codeBlockNode, lines, ref index);
                            currentLocalScope = localScope;
                            parsed = true;
                            break;
                        }
                    }

                    yield return node;
                    parsed = true;
                }

                if (!parsed)
                {
                    yield return new ExpressionNode(instruction, currentLocalScope);
                }
            }
        }
    }

ParseCodeBlock is very similar:

    private SyntaxTreeNode ParseCodeBlock(string publicScope, string localScope, CodeBlockNode codeBlockNode, IEnumerable<LogicalCodeLine> logicalLines, ref int index)
    {
        var ifBlockNode = codeBlockNode as IfBlockNode;
        if (ifBlockNode != null && !string.IsNullOrEmpty(ifBlockNode.Expression.Value))
        {
            return codeBlockNode;
        }

        var result = codeBlockNode;
        var grammar = result.ChildSyntaxType == null
            ? _grammar.Where(syntax => !syntax.IsChildNodeSyntax).ToList()
            : _grammar.Where(syntax => syntax.IsChildNodeSyntax && syntax.GetType() == result.ChildSyntaxType).ToList();

        var logicalCodeLines = logicalLines as LogicalCodeLine[] ?? logicalLines.ToArray();
        var lines = logicalCodeLines.ToArray();

        var currentIndex = ++index;
        while (currentIndex < lines.Length && !result.EndOfBlockMarkers.Any(marker => lines[currentIndex].Content.Trim().StartsWith(marker)))
        {
            var line = lines[currentIndex];
            if (string.IsNullOrWhiteSpace(line.Content))
            {
                currentIndex++;
                continue;
            }

            var instructions = line.SplitInstructions();
            foreach (var instruction in instructions)
            {
                var parsed = false;
                foreach (var syntax in grammar)
                {
                    SyntaxTreeNode node;
                    if (!syntax.IsMatch(publicScope, localScope, instruction, out node))
                    {
                        continue;
                    }

                    var childNode = node as CodeBlockNode;
                    if (childNode != null)
                    {
                        node = ParseCodeBlock(publicScope, localScope, childNode, logicalCodeLines, ref currentIndex);
                    }

                    result.AddNode(node);
                    parsed = true;
                    break;
                }

                if (!parsed)
                {
                    result.AddNode(new ExpressionNode(instruction, localScope));
                }
            }

            if (lines[currentIndex + 1].Content.Trim().StartsWith(ReservedKeywords.Else))
            {
                break;
            }

            currentIndex++;
        }

        index = currentIndex;
        return result;
    }

And, cherry on top, ParseProcedure is just as annoying:

    private SyntaxTreeNode ParseProcedure(string publicScope, string localScope, ProcedureNode procedureNode, IEnumerable<LogicalCodeLine> logicalLines, ref int index)
    {
        var result = procedureNode;
        var grammar = VBAGrammar.GetGrammarSyntax().Where(s => !s.IsChildNodeSyntax).ToList();

        var logicalCodeLines = logicalLines as LogicalCodeLine[] ?? logicalLines.ToArray();
        var lines = logicalCodeLines.ToArray();

        var currentIndex = ++index;
        while (currentIndex < lines.Length && !result.EndOfBlockMarkers.Any(marker => lines[currentIndex].Content.Trim().StartsWith(marker)))
        {
            var line = lines[currentIndex];
            if (string.IsNullOrWhiteSpace(line.Content))
            {
                currentIndex++;
                continue;
            }

            var instructions = line.SplitInstructions();
            foreach (var instruction in instructions)
            {
                var parsed = false;
                foreach (var syntax in grammar)
                {
                    SyntaxTreeNode node;
                    if (!syntax.IsMatch(publicScope, localScope, instruction, out node))
                    {
                        continue;
                    }

                    if (node.HasChildNodes)
                    {
                        var childNode = node as CodeBlockNode;
                        if (childNode != null)
                        {
                            node = ParseCodeBlock(publicScope, localScope, childNode, logicalCodeLines, ref currentIndex);
                        }
                    }

                    result.AddNode(node);
                    parsed = true;
                    break;
                }

                if (!parsed)
                {
                    result.AddNode(new ExpressionNode(instruction, localScope));
                }
            }
            currentIndex++;
        }

        index = currentIndex;
        return result;
    }
}

How do I clean up this mess and keep all my parser tests passing?

---

Some additional context:

• A procedure is a code block that defines a scope.
• A code block has child nodes and a block ending marker, and wouldn't define a scope unless it's a ProcedureNode.
• Anything that can't be parsed, is because the syntax hasn't been implemented yet - the code generates an ExpressionNode when that happens. Eventually the parser will only produce an ExpresionNode for expressions - for now I can use the Rubberduck Code Explorer and see exactly what fails to parse correctly and what ISyntax implementations need to be worked on:

Answer 1

Extract methods, extract methods everywhere, PLEASE! It's embarassing, after extracting the body of this code:

foreach (var instruction in instructions)
{
    var parsed = false;
    foreach (var syntax in grammar)
    {
        SyntaxTreeNode node;
        if (!syntax.IsMatch(publicScope, localScope, instruction, out node))
        {
            continue;
        }

        if (node.HasChildNodes)
        {
            var childNode = node as CodeBlockNode;
            if (childNode != null)
            {
                node = ParseCodeBlock(publicScope, localScope, childNode, logicalCodeLines, ref currentIndex);
            }
        }

        result.AddNode(node);
        parsed = true;
        break;
    }

    if (!parsed)
    {
        result.AddNode(new ExpressionNode(instruction, localScope));
    }
}

which appears in the exactly same form in ParseProcedure and in ParseCodeBlock, I could, of course re-use it and make the code more readable and mantainable:

private bool ParseCodeBlockInstruction(string publicScope, string localScope, IEnumerable<LogicalCodeLine> logicalLines,
            Instruction instruction, CodeBlockNode codeBlockNode, IEnumerable<ISyntax> grammar, ref int index)
{
    var result = codeBlockNode;
    foreach (var syntax in grammar)
    {
        SyntaxTreeNode node;
        if (!syntax.IsMatch(publicScope, localScope, instruction, out node))
        {
            continue;
        }

        var childNode = node as CodeBlockNode;
        if (childNode != null)
        {
            node = ParseCodeBlock(publicScope, localScope, childNode, logicalLines, ref index);
        }

        result.AddNode(node);
        return true;
    }
    return false;
}

After this you should also extract the correspondent bit of code in ParseModuleMembers. This time the reason is because the logic is a bit hard to follow up, and that parsed flag that appeared everywhere in those three methods doesn't really help:

private class ParsedSyntaxTreeNode
{
    public SyntaxTreeNode Node { get; set; }
    public bool Parsed { get; set; }
    public int Index { get; set; }
}

private IEnumerable<ParsedSyntaxTreeNode> ParseModuleInstruction(string publicScope, string localScope, IEnumerable<LogicalCodeLine> lines,
    Instruction instruction, int index)
{
    foreach (var syntax in _grammar.Where(s => !s.IsChildNodeSyntax))
    {
        string currentLocalScope = localScope;
        SyntaxTreeNode node;
        if (!syntax.IsMatch(publicScope, currentLocalScope, instruction, out node))
        {
            continue;
        }

        if (syntax.Type.HasFlag(SyntaxType.HasChildNodes))
        {
            var codeBlockNode = node as CodeBlockNode;
            if (codeBlockNode != null)
            {
                if (node is ProcedureNode)
                {
                    currentLocalScope = localScope + "." + (node as ProcedureNode).Identifier.Name;
                    var parsedProcNode = ParseProcedure(publicScope, currentLocalScope, node as ProcedureNode, lines, ref index);
                    yield return new ParsedSyntaxTreeNode()
                    {
                        Node = parsedProcNode,
                        Parsed = true,
                        Index = index
                    };
                    yield break;
                }

                var parsedCodeNode = ParseCodeBlock(publicScope, currentLocalScope, codeBlockNode, lines, ref index);
                yield return new ParsedSyntaxTreeNode()
                {
                    Node = parsedCodeNode,
                    Parsed = true,
                    Index = index
                };
                yield break;
            }
        }

        yield return new ParsedSyntaxTreeNode()
        {
            Node = node,
            Parsed = true,
            Index = index
        };
    }
    yield return new ParsedSyntaxTreeNode(){Index = index, Parsed = false};
}

I would also swap your while in the ParseCodeBlock by a for and get rid of of the increments that are made in the existing while body, and give more meaning to what we are doing: processing all lines.

for (++index; index < lines.Length; ++index)
{
    int indexCaptured = index;
    if (result.EndOfBlockMarkers.Any(marker => lines[indexCaptured].Content.Trim().StartsWith(marker)))
    {
        break;
    }
    var line = lines[index];
    if (string.IsNullOrWhiteSpace(line.Content))
    {
        continue;
    }

    var instructions = line.SplitInstructions();
    foreach (var instruction in instructions)
    {
        bool hadMatch = ParseCodeBlockInstruction(publicScope, localScope, logicalCodeLines, instruction, codeBlockNode, grammar, ref index);
        if (!hadMatch)
        {
            result.AddNode(new ExpressionNode(instruction, localScope));
        }
    }

    if (lines[index + 1].Content.Trim().StartsWith(ReservedKeywords.Else))
    {
        break;
    }
}
index = Math.Max(index, lines.Length);

Refactored code on pastebin.

Answer 2

I would say that a lot of the pain you are experiencing is because you are passing a ton of stuff into these methods and your parser feels obligated to be in charge of them all. What if you took the logic in these methods and put them in a method or methods on the objects themselves? You could also separate the logic further if you did this so you could have methods like GetNodes(). If you successfully break out methods that do the same thing, you can apply an interface to the objects. After that you might consider an abstract base class that allows them to inherit some methods that you only have to define in one place. I think managing the Nodes collection is a good place to start.

Also, it seems to me that your code is wayyyy too concerned with iterating over a collection too many times and it's helping to complicate matters. There are other ways to write performant code that don't require turning IEnumerables into arrays (you might as well not even have IEnumerable in your method signatures at this point) or having the majority of your code use for/foreach loops.