Allow token reuse in RegExpr

Fixed a problem where Token objects referenced in more than one RegExpr
statement would potentially lead to render and parse errors. This was
the case with top-level Token objects that were also referenced in the
definition of other tokens (i.e. simultaneously top-level tokens and
sub-tokens). This problem was preventing auto-test macros to be
correctly parsed.

The following example illustrates the reuse of Token objects:

C#:
    var tokenA = new Token("A", "a");
    var tokenB = new Token("B", "b" & tokenA);
    var tokenC = new Token("C", "c" & tokenB);
    var tokenX = new Token("X", (tokenA | tokenB | tokenC).Repeat());

Rendered regular expression (capture group names simplified):
    ((?:(?<A>a)|(?<B>b(?<A>a))|(?<C>c(?<B>b(?<A>a))))*)

Rendered token hierarchy: https://bit.ly/3uOgLBb

Parse tree for test case 'abacba': https://bit.ly/3dR2Mnc

Change-Id: Ie31231d1b70172127107b77c937b3eb585dca73d
Reviewed-by: Joerg Bornemann <joerg.bornemann@qt.io>
Reviewed-by: Oliver Wolff <oliver.wolff@qt.io>

14 files changed, 144 insertions, 89 deletions

diff --git a/src/qtvstools.regexpr/expression/CharClassLiteral.cs b/src/qtvstools.regexpr/expression/CharClassLiteral.cs
index c37fbdeb..455e456a 100644
--- a/src/qtvstools.regexpr/expression/CharClassLiteral.cs
+++ b/src/qtvstools.regexpr/expression/CharClassLiteral.cs
@@ -45,9 +45,9 @@ namespace QtVsTools.SyntaxAnalysis
         public string LiteralChars { get; set; }
 
         protected override IEnumerable<RegExpr> OnRender(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRender(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRender(defaultTokenWs, parent, pattern, ref mode, tokenStack);
             if ((parent == null || !(parent is CharClass)) && NeedsGroup(LiteralChars))
                 pattern.AppendFormat("[{0}]", LiteralChars);
             else
diff --git a/src/qtvstools.regexpr/expression/CharClassRange.cs b/src/qtvstools.regexpr/expression/CharClassRange.cs
index 235a3463..6b5d2ab7 100644
--- a/src/qtvstools.regexpr/expression/CharClassRange.cs
+++ b/src/qtvstools.regexpr/expression/CharClassRange.cs
@@ -46,9 +46,9 @@ namespace QtVsTools.SyntaxAnalysis
         public CharClassLiteral UpperBound { get; set; }
 
         protected override IEnumerable<RegExpr> OnRender(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRender(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRender(defaultTokenWs, parent, pattern, ref mode, tokenStack);
 
             if (parent == null || !(parent is CharClass))
                 pattern.Append("[");
@@ -57,16 +57,16 @@ namespace QtVsTools.SyntaxAnalysis
         }
 
         protected override void OnRenderNext(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRenderNext(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRenderNext(defaultTokenWs, parent, pattern, ref mode, tokenStack);
             pattern.Append("-");
         }
 
         protected override void OnRenderEnd(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRenderEnd(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRenderEnd(defaultTokenWs, parent, pattern, ref mode, tokenStack);
 
             if (parent == null || !(parent is CharClass))
                 pattern.Append("]");
diff --git a/src/qtvstools.regexpr/expression/CharClassSet.cs b/src/qtvstools.regexpr/expression/CharClassSet.cs
index 91b394d6..4ce0d02a 100644
--- a/src/qtvstools.regexpr/expression/CharClassSet.cs
+++ b/src/qtvstools.regexpr/expression/CharClassSet.cs
@@ -56,9 +56,9 @@ namespace QtVsTools.SyntaxAnalysis
         bool HasNegative { get { return Negatives != null && Negatives.Any(); } }
 
         protected override IEnumerable<RegExpr> OnRender(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRender(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRender(defaultTokenWs, parent, pattern, ref mode, tokenStack);
 
             if (!HasPositive && !HasNegative)
                 return null;
@@ -86,17 +86,17 @@ namespace QtVsTools.SyntaxAnalysis
         }
 
         protected override void OnRenderNext(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRenderNext(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRenderNext(defaultTokenWs, parent, pattern, ref mode, tokenStack);
             if (!IsSubSet && HasPositive && HasNegative)
                 pattern.Append("-[");
         }
 
         protected override void OnRenderEnd(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRenderEnd(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRenderEnd(defaultTokenWs, parent, pattern, ref mode, tokenStack);
             if (!IsSubSet) {
                 if (HasPositive && HasNegative)
                     pattern.Append("]]");
diff --git a/src/qtvstools.regexpr/expression/RegExpr.cs b/src/qtvstools.regexpr/expression/RegExpr.cs
index 34c99104..e028f0be 100644
--- a/src/qtvstools.regexpr/expression/RegExpr.cs
+++ b/src/qtvstools.regexpr/expression/RegExpr.cs
@@ -79,7 +79,7 @@ namespace QtVsTools.SyntaxAnalysis
         /// external, application specific classes.
         /// </remarks>
         protected virtual IEnumerable<RegExpr> OnRender(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         { return null; }
 
         /// <summary>
@@ -91,7 +91,7 @@ namespace QtVsTools.SyntaxAnalysis
         /// <param name="mode">Rendering mode</param>
         ///
         protected virtual void OnRenderNext(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         { }
 
         /// <summary>
@@ -103,7 +103,7 @@ namespace QtVsTools.SyntaxAnalysis
         /// <param name="mode">Rendering mode</param>
         ///
         protected virtual void OnRenderEnd(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         { }
 
         public class RegExprException : System.Exception
diff --git a/src/qtvstools.regexpr/expression/RegExprAssert.cs b/src/qtvstools.regexpr/expression/RegExprAssert.cs
index 657e17ed..aa374e09 100644
--- a/src/qtvstools.regexpr/expression/RegExprAssert.cs
+++ b/src/qtvstools.regexpr/expression/RegExprAssert.cs
@@ -53,9 +53,9 @@ namespace QtVsTools.SyntaxAnalysis
         public RegExpr Expr { get; set; }
 
         protected override IEnumerable<RegExpr> OnRender(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRender(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRender(defaultTokenWs, parent, pattern, ref mode, tokenStack);
 
             if (mode.HasFlag(RenderMode.Assert))
                 throw new NestedAssertException();
@@ -80,9 +80,9 @@ namespace QtVsTools.SyntaxAnalysis
         }
 
         protected override void OnRenderEnd(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRenderEnd(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRenderEnd(defaultTokenWs, parent, pattern, ref mode, tokenStack);
             pattern.Append(")");
             mode &= ~RenderMode.Assert;
         }
diff --git a/src/qtvstools.regexpr/expression/RegExprChoice.cs b/src/qtvstools.regexpr/expression/RegExprChoice.cs
index 9222c235..4a01b370 100644
--- a/src/qtvstools.regexpr/expression/RegExprChoice.cs
+++ b/src/qtvstools.regexpr/expression/RegExprChoice.cs
@@ -40,9 +40,9 @@ namespace QtVsTools.SyntaxAnalysis
         public IEnumerable<RegExpr> Exprs { get; set; }
 
         protected override IEnumerable<RegExpr> OnRender(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRender(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRender(defaultTokenWs, parent, pattern, ref mode, tokenStack);
             if (!(parent is Token))
                 pattern.Append("(?:");
             pattern.Append("(?:");
@@ -50,16 +50,16 @@ namespace QtVsTools.SyntaxAnalysis
         }
 
         protected override void OnRenderNext(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRenderNext(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRenderNext(defaultTokenWs, parent, pattern, ref mode, tokenStack);
             pattern.Append(")|(?:");
         }
 
         protected override void OnRenderEnd(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRenderEnd(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRenderEnd(defaultTokenWs, parent, pattern, ref mode, tokenStack);
             pattern.Append(")");
             if (!(parent is Token))
                 pattern.Append(")");
diff --git a/src/qtvstools.regexpr/expression/RegExprLiteral.cs b/src/qtvstools.regexpr/expression/RegExprLiteral.cs
index 78f8509f..0c5f94a0 100644
--- a/src/qtvstools.regexpr/expression/RegExprLiteral.cs
+++ b/src/qtvstools.regexpr/expression/RegExprLiteral.cs
@@ -39,9 +39,9 @@ namespace QtVsTools.SyntaxAnalysis
         public string LiteralExpr { get; set; }
 
         protected override IEnumerable<RegExpr> OnRender(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRender(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRender(defaultTokenWs, parent, pattern, ref mode, tokenStack);
             pattern.Append(LiteralExpr);
             return null;
         }
diff --git a/src/qtvstools.regexpr/expression/RegExprRepeat.cs b/src/qtvstools.regexpr/expression/RegExprRepeat.cs
index ede360bb..93a89e00 100644
--- a/src/qtvstools.regexpr/expression/RegExprRepeat.cs
+++ b/src/qtvstools.regexpr/expression/RegExprRepeat.cs
@@ -52,9 +52,9 @@ namespace QtVsTools.SyntaxAnalysis
         }
 
         protected override IEnumerable<RegExpr> OnRender(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRender(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRender(defaultTokenWs, parent, pattern, ref mode, tokenStack);
 
             if (ExprNeedsGroup)
                 pattern.Append("(?:");
@@ -63,9 +63,9 @@ namespace QtVsTools.SyntaxAnalysis
         }
 
         protected override void OnRenderEnd(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRenderEnd(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRenderEnd(defaultTokenWs, parent, pattern, ref mode, tokenStack);
 
             if (ExprNeedsGroup)
                 pattern.Append(")");
diff --git a/src/qtvstools.regexpr/expression/RegExprSequence.cs b/src/qtvstools.regexpr/expression/RegExprSequence.cs
index 71e1491b..7b422b66 100644
--- a/src/qtvstools.regexpr/expression/RegExprSequence.cs
+++ b/src/qtvstools.regexpr/expression/RegExprSequence.cs
@@ -40,9 +40,9 @@ namespace QtVsTools.SyntaxAnalysis
         public IEnumerable<RegExpr> Exprs { get; set; }
 
         protected override IEnumerable<RegExpr> OnRender(RegExpr defaultTokenWs, RegExpr parent,
-            StringBuilder pattern, ref RenderMode mode)
+            StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
         {
-            base.OnRender(defaultTokenWs, parent, pattern, ref mode);
+            base.OnRender(defaultTokenWs, parent, pattern, ref mode, tokenStack);
             return Exprs;
         }
     }
diff --git a/src/qtvstools.regexpr/expression/RegExprToken.cs b/src/qtvstools.regexpr/expression/RegExprToken.cs
index 33f90be1..ab661e17 100644
--- a/src/qtvstools.regexpr/expression/RegExprToken.cs
+++ b/src/qtvstools.regexpr/expression/RegExprToken.cs
@@ -55,7 +55,6 @@ namespace QtVsTools.SyntaxAnalysis
         /// </remarks>
         public partial class Token : RegExpr, IEnumerable<IProductionRule>
         {
-            public string CaptureId { get; private set; }
             public string Id { get; set; }
 
             public bool SkipLeadingWhitespace { get; set; }
@@ -63,9 +62,9 @@ namespace QtVsTools.SyntaxAnalysis
 
             public RegExpr Expr { get; set; }
 
-            public Token Parent { get; set; }
-
-            public List<Token> Children { get; set; }
+            public HashSet<Token> Children { get; set; }
+            public Dictionary<string, Token> Parents { get; set; }
+            public IEnumerable<string> CaptureIds => Parents.Keys;
 
             public Token(string id, RegExpr skipWs, RegExpr expr)
             {
@@ -74,8 +73,8 @@ namespace QtVsTools.SyntaxAnalysis
                 LeadingWhitespace = skipWs;
                 Expr = expr;
                 Rules = new TokenRules();
-                CaptureId = GenerateCaptureId(Id);
-                Children = new List<Token>();
+                Children = new HashSet<Token>();
+                Parents = new Dictionary<string, Token>();
             }
 
             public Token(string id, SkipWhitespace skipWs, RegExpr expr)
@@ -84,8 +83,8 @@ namespace QtVsTools.SyntaxAnalysis
                 SkipLeadingWhitespace = (skipWs == SkipWhitespace.Enable);
                 Expr = expr;
                 Rules = new TokenRules();
-                CaptureId = GenerateCaptureId(Id);
-                Children = new List<Token>();
+                Children = new HashSet<Token>();
+                Parents = new Dictionary<string, Token>();
             }
 
             public Token(Enum id, RegExpr expr)
@@ -118,13 +117,15 @@ namespace QtVsTools.SyntaxAnalysis
 
             public static Token CreateRoot()
             {
-                return new Token { CaptureId = ParseTree.KeyRoot };
+                var rootToken = new Token();
+                rootToken.Parents[ParseTree.KeyRoot] = rootToken;
+                return rootToken;
             }
 
             protected override IEnumerable<RegExpr> OnRender(RegExpr defaultTokenWs, RegExpr parent,
-                StringBuilder pattern, ref RenderMode mode)
+                StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
             {
-                base.OnRender(defaultTokenWs, parent, pattern, ref mode);
+                base.OnRender(defaultTokenWs, parent, pattern, ref mode, tokenStack);
 
                 var tokenWs = GetTokenWhitespace(defaultTokenWs);
                 if (tokenWs != null)
@@ -135,30 +136,35 @@ namespace QtVsTools.SyntaxAnalysis
             }
 
             protected override void OnRenderNext(RegExpr defaultTokenWs, RegExpr parent,
-                StringBuilder pattern, ref RenderMode mode)
+                StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
             {
-                base.OnRenderNext(defaultTokenWs, parent, pattern, ref mode);
+                base.OnRenderNext(defaultTokenWs, parent, pattern, ref mode, tokenStack);
                 var tokenWs = GetTokenWhitespace(defaultTokenWs);
                 if (NeedsWhitespaceGroup(tokenWs, mode))
                     pattern.Append(")");
                 if (Expr != null) {
-                    if (!mode.HasFlag(RenderMode.Assert) && !string.IsNullOrEmpty(Id))
-                        pattern.AppendFormat("(?<{0}>", CaptureId);
-                    else
+                    if (!mode.HasFlag(RenderMode.Assert) && !string.IsNullOrEmpty(Id)) {
+                        string captureId = GenerateCaptureId(Id);
+                        Parents.Add(captureId, tokenStack.Peek());
+                        tokenStack.Peek().Children.Add(this);
+                        pattern.AppendFormat("(?<{0}>", captureId);
+                    } else {
                         pattern.Append("(?:");
-
+                    }
                 }
+                tokenStack.Push(this);
             }
 
             protected override void OnRenderEnd(RegExpr defaultTokenWs, RegExpr parent,
-                StringBuilder pattern, ref RenderMode mode)
+                StringBuilder pattern, ref RenderMode mode, Stack<Token> tokenStack)
             {
-                base.OnRenderEnd(defaultTokenWs, parent, pattern, ref mode);
+                base.OnRenderEnd(defaultTokenWs, parent, pattern, ref mode, tokenStack);
                 if (Expr != null)
                     pattern.Append(")");
                 var tokenWs = GetTokenWhitespace(defaultTokenWs);
                 if (tokenWs != null)
                     pattern.Append(")");
+                tokenStack.Pop();
             }
 
             /// <summary>
diff --git a/src/qtvstools.regexpr/parser/ParseTree.cs b/src/qtvstools.regexpr/parser/ParseTree.cs
index 4b8d0b38..6a9b1c6a 100644
--- a/src/qtvstools.regexpr/parser/ParseTree.cs
+++ b/src/qtvstools.regexpr/parser/ParseTree.cs
@@ -61,7 +61,6 @@ namespace QtVsTools.SyntaxAnalysis
                 public int End { get; set; }
                 public int GroupIdx { get; set; }
                 public int CaptureIdx { get; set; }
-                public ulong OrderKey { get; set; }
 
                 class NodeComparer : IComparer<Node>
                 {
@@ -81,8 +80,8 @@ namespace QtVsTools.SyntaxAnalysis
 
                 public Node Parent { get; set; }
 
-                SortedList<ulong, Node> _ChildNodes = new SortedList<ulong, Node>();
-                public SortedList<ulong, Node> ChildNodes { get { return _ChildNodes; } }
+                SortedList<int, Node> _ChildNodes = new SortedList<int, Node>();
+                public SortedList<int, Node> ChildNodes { get { return _ChildNodes; } }
 
                 ProductionObjects _ChildProductions = new ProductionObjects();
                 public ProductionObjects ChildProductions { get { return _ChildProductions; } }
@@ -128,7 +127,7 @@ namespace QtVsTools.SyntaxAnalysis
                     {
                         if (Parent == null)
                             return 0;
-                        return Parent.ChildNodes.IndexOfKey(OrderKey);
+                        return Parent.ChildNodes.IndexOfKey(Begin);
                     }
                 }
 
diff --git a/src/qtvstools.regexpr/parser/Parser.cs b/src/qtvstools.regexpr/parser/Parser.cs
index 41b0eb0a..bdb4e12b 100644
--- a/src/qtvstools.regexpr/parser/Parser.cs
+++ b/src/qtvstools.regexpr/parser/Parser.cs
@@ -107,47 +107,36 @@ namespace QtVsTools.SyntaxAnalysis
                             End = capture.Index + capture.Length,
                             GroupIdx = groupIdx,
                             CaptureIdx = captureIdx,
-                            OrderKey = (((ulong)groupIdx) << 32) | ((uint)captureIdx)
                         }))
-                    .OrderBy(c => c.Begin);
+                    .OrderBy(c => c.Begin)
+                    .ToList();
 
-                // Node list partitioned by token ID
+                // Node list partitioned by token
                 var nodesByToken = nodes
-                    .GroupBy(c => c.CaptureId)
+                    .GroupBy(node => node.Token)
                     .ToDictionary(g => g.Key, g => g.ToArray());
 
-                // Traverse token hierarchy
-                var stack = new Stack<Token>(Pattern.Root.Children);
-                while (stack.Any()) {
-                    var token = stack.Pop();
-
-                    // Get nodes captured by current token (if any)
-                    ParseTree.Node[] tokenNodes;
-                    if (!nodesByToken.TryGetValue(token.CaptureId, out tokenNodes))
-                        continue;
-
+                foreach (var node in nodes.Where(n => n.Token != Pattern.Root)) {
                     // Get nodes captured by parent token
-                    var parentNodes = nodesByToken[token.Parent.CaptureId];
-
-                    // Set parent <-> child relation for nodes of current token
-                    foreach (var node in tokenNodes) {
-                        // Find parent node
-                        int idx = Array.BinarySearch(parentNodes, node, ParseTree.Node.Comparer);
-                        if (idx < 0) {
-                            idx = (~idx) - 1;
-                            if (idx < 0)
-                                throw new ParseErrorException();
-                        }
-                        // Attach to parent node
-                        (node.Parent = parentNodes[idx]).ChildNodes.Add(node.OrderKey, node);
+                    Token parentToken;
+                    if (!node.Token.Parents.TryGetValue(node.CaptureId, out parentToken))
+                        throw new ParseErrorException("Unknown capture ID");
+                    ParseTree.Node[] parentNodes;
+                    if (!nodesByToken.TryGetValue(parentToken, out parentNodes))
+                        throw new ParseErrorException("Missing parent nodes");
+                    // Find parent node
+                    int idx = Array.BinarySearch(parentNodes, node, ParseTree.Node.Comparer);
+                    if (idx < 0) {
+                        idx = (~idx) - 1;
+                        if (idx < 0)
+                            throw new ParseErrorException("Parent node not found");
                     }
-
-                    // Move down token hierarchy
-                    token.Children.ForEach(x => stack.Push(x));
+                    // Attach to parent node
+                    (node.Parent = parentNodes[idx]).ChildNodes.Add(node.Begin, node);
                 }
 
                 // Return parse tree root
-                return nodesByToken[ParseTree.KeyRoot].FirstOrDefault();
+                return nodesByToken[Pattern.Root].FirstOrDefault();
             }
         }
 
diff --git a/src/tests/Test_QtVsTools.RegExpr/Test_QtVsTools.RegExpr.csproj b/src/tests/Test_QtVsTools.RegExpr/Test_QtVsTools.RegExpr.csproj
index 6c0fca7a..3e2aa58e 100644
--- a/src/tests/Test_QtVsTools.RegExpr/Test_QtVsTools.RegExpr.csproj
+++ b/src/tests/Test_QtVsTools.RegExpr/Test_QtVsTools.RegExpr.csproj
@@ -85,6 +85,7 @@
     <Compile Include="Test_MacroParser.cs" />
     <Compile Include="Test_XmlIntParser.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="Test_SubTokens.cs" />
   </ItemGroup>
   <ItemGroup>
     <None Include="packages.config" />
diff --git a/src/tests/Test_QtVsTools.RegExpr/Test_SubTokens.cs b/src/tests/Test_QtVsTools.RegExpr/Test_SubTokens.cs
new file mode 100644
index 00000000..4c88381c
--- /dev/null
+++ b/src/tests/Test_QtVsTools.RegExpr/Test_SubTokens.cs
@@ -0,0 +1,60 @@
+/****************************************************************************
+**
+** Copyright (C) 2021 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the Qt VS Tools.
+**
+** $QT_BEGIN_LICENSE:GPL-EXCEPT$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3 as published by the Free Software
+** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+using System;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+namespace QtVsTools.Test.RegExpr
+{
+    using static SyntaxAnalysis.RegExpr;
+
+    [TestClass]
+    public class Test_SubTokens
+    {
+        [TestMethod]
+        public void TestManyToMany()
+        {
+            var tokenA = new Token("A", "a");
+            var tokenB = new Token("B", "b" & tokenA);
+            var tokenC = new Token("C", "c" & tokenB);
+            var tokenX = new Token("X", (tokenA | tokenB | tokenC).Repeat());
+            var parser = tokenX.Render();
+            parser.Parse("abacba");
+        }
+
+        [TestMethod]
+        public void TestLookAhead()
+        {
+            var tokenA = new Token("A", "a");
+            var tokenB = new Token("B", "b" & !LookAhead[tokenA] & AnyChar);
+            var tokenX = new Token("X", (tokenA | tokenB).Repeat());
+            var parser = tokenX.Render();
+            parser.Parse("abc");
+        }
+    }
+}