antlr.v4.runtime.tree.Trees source code

1 /*
2  * Copyright (c) 2012-2019 The ANTLR Project. All rights reserved.
3  * Use of this file is governed by the BSD 3-clause license that
4  * can be found in the LICENSE.txt file in the project root.
5  */
6 
7 module antlr.v4.runtime.tree.Trees;
8 
9 import std.array;
10 import std.conv;
11 import std.variant;
12 import antlr.v4.runtime.InterfaceRecognizer;
13 import antlr.v4.runtime.ParserRuleContext;
14 import antlr.v4.runtime.RuleContext;
15 import antlr.v4.runtime.CommonToken;
16 import antlr.v4.runtime.Token;
17 import antlr.v4.runtime.TokenConstantDefinition;
18 import antlr.v4.runtime.atn.ATN;
19 import antlr.v4.runtime.tree.TerminalNode;
20 import antlr.v4.runtime.tree.ErrorNode;
21 import antlr.v4.runtime.tree.Tree;
22 import antlr.v4.runtime.tree.TerminalNodeImpl;
23 import antlr.v4.runtime.tree.ParseTree;
24 import antlr.v4.runtime.misc.Utils;
25 import antlr.v4.runtime.misc.Interval;
26 import antlr.v4.runtime.misc.Predicate;
27 
28 /**
29  * TODO add class description
30  * @uml
31  * A set of utility routines useful for all kinds of ANTLR trees
32  */
33 class Trees
34 {
35 
36     private this()
37     {
38     }
39 
40     /**
41      * @uml
42      * Print out a whole tree in LISP form. {@link #getNodeText} is used on the
43      * node payloads to get the text for the nodes.  Detect
44      * parse trees and extract data appropriately.
45      */
46     public static string toStringTree(Tree t)
47     {
48         return toStringTree(t, cast(string[])null);
49     }
50 
51     /**
52      * @uml
53      * Print out a whole tree in LISP form. {@link #getNodeText} is used on the
54      * node payloads to get the text for the nodes.  Detect
55      * parse trees and extract data appropriately.
56      */
57     public static string toStringTree(Tree t, InterfaceRecognizer recog)
58     {
59         string[] ruleNames = recog !is null ? recog.getRuleNames() : null;
60         string[] ruleNamesList = ruleNames !is null ? ruleNames : null;
61         return t.toStringTree ~ to!string(ruleNamesList);
62     }
63 
64     /**
65      * @uml
66      * rint out a whole tree in LISP form. {@link #getNodeText} is used on the
67      * node payloads to get the text for the nodes.
68      */
69     public static string toStringTree(Tree t, string[] ruleNames)
70     {
71         string s = Utils.escapeWhitespace(getNodeText(t, ruleNames), false);
72         if ( t.getChildCount()==0 ) return s;
73         auto buf = appender!(string);
74 		buf.put("(");
75 		s = Utils.escapeWhitespace(getNodeText(t, ruleNames), false);
76 		buf.put(s);
77 		buf.put(' ');
78 		for (int i = 0; i<t.getChildCount(); i++) {
79 			if ( i>0 ) buf.put(' ');
80 			buf.put(toStringTree(t.getChild(i), ruleNames));
81 		}
82 		buf.put(")");
83 		return buf.data;
84     }
85 
86     public static string getNodeText(Tree t, InterfaceRecognizer recog)
87     {
88         string[] ruleNames = recog !is null ? recog.getRuleNames() : null;
89         string[] ruleNamesList = ruleNames !is null ? ruleNames : null;
90         return getNodeText(t, ruleNamesList);
91 
92     }
93 
94     public static string getNodeText(Tree t, string[] ruleNames)
95     {
96 	if (ruleNames) {
97             if (t.classinfo == RuleContext.classinfo) {
98                 int ruleIndex = (cast(RuleContext)t).getRuleContext().getRuleIndex();
99                 string ruleName = ruleNames[ruleIndex];
100                 int altNumber = (cast(RuleContext) t).getAltNumber();
101                 if (altNumber != ATN.INVALID_ALT_NUMBER) {
102                     return ruleName ~ ":" ~ to!string(altNumber);
103                 }
104                 return ruleName;
105             }
106             else if (t.classinfo == ErrorNode.classinfo) {
107                 return "..."; // t.toString();
108             }
109             else if (t.classinfo == TerminalNode.classinfo) {
110                 Token symbol = (cast(TerminalNode)t).getSymbol();
111                 if (symbol !is null) {
112                     string s = to!string(symbol.getText);
113                     return s;
114                 }
115             }
116         }
117         // no recog for rule names
118         Object payload = t.getPayload();
119         if (payload.classinfo == Token.classinfo) {
120             return to!string((cast(Token)payload).getText);
121         }
122         return t.getPayload().toString();
123     }
124 
125     /**
126      * @uml
127      * Return ordered list of all children of this node
128      */
129     public static Tree[] getChildren(Tree t)
130     {
131         Tree[] kids;
132         for (int i=0; i<t.getChildCount(); i++) {
133             kids ~= t.getChild(i);
134         }
135         return kids;
136     }
137 
138     /**
139      * @uml
140      * Return a list of all ancestors of this node.  The first node of
141      * list is the root and the last is the parent of this node.
142      */
143     public static Tree[] getAncestors(Tree t)
144     {
145         Tree[] emptyTrees;
146 	if (t.getParent() is null) return emptyTrees;
147         Tree[] ancestors;
148         t = t.getParent();
149         while (t !is null) {
150             ancestors = t ~ ancestors; // insert at start
151             t = t.getParent();
152         }
153         return ancestors;
154     }
155 
156     /**
157      * @uml
158      * Return true if t is u's parent or a node on path to root from u.
159      * Use == not equals().
160      */
161     public static bool isAncestorOf(Tree t, Tree u)
162     {
163         if (t is null || u is null || t.getParent() is null) return false;
164 		Tree p = u.getParent();
165 		while (p !is null) {
166 			if (t is p) return true;
167 			p = p.getParent();
168 		}
169 		return false;
170     }
171 
172     public static ParseTree[] findAllTokenNodes(ParseTree t, int ttype)
173     {
174         return findAllNodes(t, ttype, true);
175     }
176 
177     public static ParseTree[] findAllRuleNodes(ParseTree t, int ruleIndex)
178     {
179         return findAllNodes(t, ruleIndex, false);
180     }
181 
182     public static ParseTree[] findAllNodes(ParseTree t, int index, bool findTokens)
183     {
184         ParseTree[] nodes;
185         _findAllNodes(t, index, findTokens, nodes);
186         return nodes;
187     }
188 
189     public static void _findAllNodes(ParseTree t, int index, bool findTokens, ParseTree[] nodes)
190     {
191 	// check this node (the root) first
192         if ( findTokens && t.classinfo == TerminalNode.classinfo) {
193             TerminalNode tnode = cast(TerminalNode)t;
194             if (tnode.getSymbol().getType() == index) nodes ~= t;
195         }
196         else if (!findTokens && t.classinfo == ParserRuleContext.classinfo) {
197             ParserRuleContext ctx = cast(ParserRuleContext)t;
198             if ( ctx.getRuleIndex() == index ) nodes ~= t;
199         }
200         // check children
201         for (int i = 0; i < t.getChildCount(); i++){
202             _findAllNodes(t.getChild(i), index, findTokens, nodes);
203         }
204     }
205 
206     /**
207      * @uml
208      * Get all descendents; includes t itself.
209      */
210     public static ParseTree[] getDescendants(ParseTree t)
211     {
212         ParseTree[] nodes;
213         nodes ~= t;
214 
215         int n = t.getChildCount();
216         for (int i = 0 ; i < n ; i++){
217             nodes ~= getDescendants(t.getChild(i));
218         }
219         return nodes;
220     }
221 
222     public static ParseTree[] descendants(ParseTree t)
223     {
224         return getDescendants(t);
225     }
226 
227     /**
228      * @uml
229      * Find smallest subtree of t enclosing range startTokenIndex..stopTokenIndex
230      * inclusively using postorder traversal.  Recursive depth-first-search.
231      */
232     public static ParserRuleContext getRootOfSubtreeEnclosingRegion(ParseTree t, int startTokenIndex,
233         int stopTokenIndex)
234     {
235 	int n = t.getChildCount();
236         for (int i = 0; i<n; i++) {
237             ParseTree child = t.getChild(i);
238             ParserRuleContext r = getRootOfSubtreeEnclosingRegion(child, startTokenIndex, stopTokenIndex);
239             if (r !is null) return r;
240         }
241         if (t.classinfo == ParserRuleContext.classinfo) {
242             ParserRuleContext r = cast(ParserRuleContext)t;
243             if (startTokenIndex >= r.getStart().getTokenIndex() && // is range fully contained in t?
244                 (r.getStop() is null || stopTokenIndex <= r.getStop().getTokenIndex()) )
245                 {
246                     // note: r.getStop()==null likely implies that we bailed out of parser and there's nothing to the right
247                     return r;
248                 }
249         }
250         return null;
251     }
252 
253     /**
254      * @uml
255      * Replace any subtree siblings of root that are completely to left
256      * or right of lookahead range with a CommonToken(Token.INVALID_TYPE,"...")
257      * node. The source interval for t is not altered to suit smaller range!
258      *
259      * WARNING: destructive to t.
260      */
261     public static void stripChildrenOutOfRange(ParserRuleContext t, ParserRuleContext root,
262         int startIndex, int stopIndex)
263     {
264         if (t is null) return;
265         for (int i = 0; i < t.getChildCount(); i++) {
266             ParseTree child = t.getChild(i);
267             Interval range = child.getSourceInterval();
268             if (child.classinfo == ParserRuleContext.classinfo && (range.b < startIndex || range.a > stopIndex) ) {
269                 if (isAncestorOf(child, root)) { // replace only if subtree doesn't have displayed root
270                     Variant v = "...";
271                     CommonToken abbrev = new CommonToken(TokenConstantDefinition.INVALID_TYPE, v);
272                     t.children[i] =  new TerminalNodeImpl(abbrev);
273                 }
274             }
275         }
276     }
277 
278     /**
279      * @uml
280      * Return first node satisfying the pred
281      */
282     public static Tree findNodeSuchThat(Tree t, Predicate!Tree pred)
283     {
284         if (pred.test(t) ) return t;
285 
286         int n = t.getChildCount();
287         for (int i = 0 ; i < n ; i++){
288             Tree u = findNodeSuchThat(t.getChild(i), pred);
289             if (u !is null ) return u;
290         }
291         return null;
292     }
293 
294 }