antlr.v4.runtime.tree.Trees source code

1 /*
2  * [The "BSD license"]
3  *  Copyright (c) 2013 Terence Parr
4  *  Copyright (c) 2013 Sam Harwell
5  *  Copyright (c) 2017 Egbert Voigt
6  *  All rights reserved.
7  *
8  *  Redistribution and use in source and binary forms, with or without
9  *  modification, are permitted provided that the following conditions
10  *  are met:
11  *
12  *  1. Redistributions of source code must retain the above copyright
13  *     notice, this list of conditions and the following disclaimer.
14  *  2. Redistributions in binary form must reproduce the above copyright
15  *     notice, this list of conditions and the following disclaimer in the
16  *     documentation and/or other materials provided with the distribution.
17  *  3. The name of the author may not be used to endorse or promote products
18  *     derived from this software without specific prior written permission.
19  *
20  *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
21  *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
22  *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
23  *  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
24  *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
25  *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26  *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27  *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28  *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
29  *  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30  */
31 
32 module antlr.v4.runtime.tree.Trees;
33 
34 import std.array;
35 import std.conv;
36 import antlr.v4.runtime.InterfaceRecognizer;
37 import antlr.v4.runtime.ParserRuleContext;
38 import antlr.v4.runtime.RuleContext;
39 import antlr.v4.runtime.CommonToken;
40 import antlr.v4.runtime.Token;
41 import antlr.v4.runtime.TokenConstantDefinition;
42 import antlr.v4.runtime.atn.ATN;
43 import antlr.v4.runtime.tree.TerminalNode;
44 import antlr.v4.runtime.tree.ErrorNode;
45 import antlr.v4.runtime.tree.Tree;
46 import antlr.v4.runtime.tree.TerminalNodeImpl;
47 import antlr.v4.runtime.tree.ParseTree;
48 import antlr.v4.runtime.misc.Utils;
49 import antlr.v4.runtime.misc.Interval;
50 import antlr.v4.runtime.misc.Predicate;
51 
52 // Class Trees
53 /**
54  * TODO add class description
55  * @uml
56  * A set of utility routines useful for all kinds of ANTLR trees
57  */
58 class Trees
59 {
60 
61     private this()
62     {
63     }
64 
65     /**
66      * @uml
67      * Print out a whole tree in LISP form. {@link #getNodeText} is used on the
68      * node payloads to get the text for the nodes.  Detect
69      * parse trees and extract data appropriately.
70      */
71     public static string toStringTree(Tree t)
72     {
73         return toStringTree(t, cast(string[])null);
74     }
75 
76     /**
77      * @uml
78      * Print out a whole tree in LISP form. {@link #getNodeText} is used on the
79      * node payloads to get the text for the nodes.  Detect
80      * parse trees and extract data appropriately.
81      */
82     public static string toStringTree(Tree t, InterfaceRecognizer recog)
83     {
84         string[] ruleNames = recog !is null ? recog.getRuleNames() : null;
85         string[] ruleNamesList = ruleNames !is null ? ruleNames : null;
86         return t.toStringTree ~ to!string(ruleNamesList);
87     }
88 
89     /**
90      * @uml
91      * rint out a whole tree in LISP form. {@link #getNodeText} is used on the
92      * node payloads to get the text for the nodes.
93      */
94     public static string toStringTree(Tree t, string[] ruleNames)
95     {
96         string s = Utils.escapeWhitespace(getNodeText(t, ruleNames), false);
97         if ( t.getChildCount()==0 ) return s;
98         auto buf = appender!(string);
99 		buf.put("(");
100 		s = Utils.escapeWhitespace(getNodeText(t, ruleNames), false);
101 		buf.put(s);
102 		buf.put(' ');
103 		for (int i = 0; i<t.getChildCount(); i++) {
104 			if ( i>0 ) buf.put(' ');
105 			buf.put(toStringTree(t.getChild(i), ruleNames));
106 		}
107 		buf.put(")");
108 		return buf.data;
109     }
110 
111     public static string getNodeText(Tree t, InterfaceRecognizer recog)
112     {
113         string[] ruleNames = recog !is null ? recog.getRuleNames() : null;
114         string[] ruleNamesList = ruleNames !is null ? ruleNames : null;
115         return getNodeText(t, ruleNamesList);
116 
117     }
118 
119     public static string getNodeText(Tree t, string[] ruleNames)
120     {
121 	if (ruleNames) {
122             if (t.classinfo == RuleContext.classinfo) {
123                 int ruleIndex = (cast(RuleContext)t).getRuleContext().getRuleIndex();
124                 string ruleName = ruleNames[ruleIndex];
125                 int altNumber = (cast(RuleContext) t).getAltNumber();
126                 if (altNumber != ATN.INVALID_ALT_NUMBER) {
127                     return ruleName ~ ":" ~ to!string(altNumber);
128                 }
129                 return ruleName;
130             }
131             else if (t.classinfo == ErrorNode.classinfo) {
132                 return "..."; // t.toString();
133             }
134             else if (t.classinfo == TerminalNode.classinfo) {
135                 Token symbol = (cast(TerminalNode)t).getSymbol();
136                 if (symbol !is null) {
137                     string s = symbol.getText();
138                     return s;
139                 }
140             }
141         }
142         // no recog for rule names
143         Object payload = t.getPayload();
144         if (payload.classinfo == Token.classinfo) {
145             return (cast(Token)payload).getText();
146         }
147         return t.getPayload().toString();
148     }
149 
150     /**
151      * @uml
152      * Return ordered list of all children of this node
153      */
154     public static Tree[] getChildren(Tree t)
155     {
156         Tree[] kids;
157         for (int i=0; i<t.getChildCount(); i++) {
158             kids ~= t.getChild(i);
159         }
160         return kids;
161     }
162 
163     /**
164      * @uml
165      * Return a list of all ancestors of this node.  The first node of
166      * list is the root and the last is the parent of this node.
167      */
168     public static Tree[] getAncestors(Tree t)
169     {
170         Tree[] emptyTrees;
171 	if (t.getParent() is null) return emptyTrees;
172         Tree[] ancestors;
173         t = t.getParent();
174         while (t !is null) {
175             ancestors = t ~ ancestors; // insert at start
176             t = t.getParent();
177         }
178         return ancestors;
179     }
180 
181     /**
182      * @uml
183      * Return true if t is u's parent or a node on path to root from u.
184      * Use == not equals().
185      */
186     public static bool isAncestorOf(Tree t, Tree u)
187     {
188         if (t is null || u is null || t.getParent() is null) return false;
189 		Tree p = u.getParent();
190 		while (p !is null) {
191 			if (t is p) return true;
192 			p = p.getParent();
193 		}
194 		return false;
195     }
196 
197     public static ParseTree[] findAllTokenNodes(ParseTree t, int ttype)
198     {
199         return findAllNodes(t, ttype, true);
200     }
201 
202     public static ParseTree[] findAllRuleNodes(ParseTree t, int ruleIndex)
203     {
204         return findAllNodes(t, ruleIndex, false);
205     }
206 
207     public static ParseTree[] findAllNodes(ParseTree t, int index, bool findTokens)
208     {
209         ParseTree[] nodes;
210         _findAllNodes(t, index, findTokens, nodes);
211         return nodes;
212     }
213 
214     public static void _findAllNodes(ParseTree t, int index, bool findTokens, ParseTree[] nodes)
215     {
216 	// check this node (the root) first
217         if ( findTokens && t.classinfo == TerminalNode.classinfo) {
218             TerminalNode tnode = cast(TerminalNode)t;
219             if (tnode.getSymbol().getType() == index) nodes ~= t;
220         }
221         else if (!findTokens && t.classinfo == ParserRuleContext.classinfo) {
222             ParserRuleContext ctx = cast(ParserRuleContext)t;
223             if ( ctx.getRuleIndex() == index ) nodes ~= t;
224         }
225         // check children
226         for (int i = 0; i < t.getChildCount(); i++){
227             _findAllNodes(t.getChild(i), index, findTokens, nodes);
228         }
229     }
230 
231     /**
232      * @uml
233      * Get all descendents; includes t itself.
234      */
235     public static ParseTree[] getDescendants(ParseTree t)
236     {
237         ParseTree[] nodes;
238         nodes ~= t;
239 
240         int n = t.getChildCount();
241         for (int i = 0 ; i < n ; i++){
242             nodes ~= getDescendants(t.getChild(i));
243         }
244         return nodes;
245     }
246 
247     public static ParseTree[] descendants(ParseTree t)
248     {
249         return getDescendants(t);
250     }
251 
252     /**
253      * @uml
254      * Find smallest subtree of t enclosing range startTokenIndex..stopTokenIndex
255      * inclusively using postorder traversal.  Recursive depth-first-search.
256      */
257     public static ParserRuleContext getRootOfSubtreeEnclosingRegion(ParseTree t, int startTokenIndex,
258         int stopTokenIndex)
259     {
260 	int n = t.getChildCount();
261         for (int i = 0; i<n; i++) {
262             ParseTree child = t.getChild(i);
263             ParserRuleContext r = getRootOfSubtreeEnclosingRegion(child, startTokenIndex, stopTokenIndex);
264             if (r !is null) return r;
265         }
266         if (t.classinfo == ParserRuleContext.classinfo) {
267             ParserRuleContext r = cast(ParserRuleContext)t;
268             if (startTokenIndex >= r.getStart().getTokenIndex() && // is range fully contained in t?
269                 (r.getStop() is null || stopTokenIndex <= r.getStop().getTokenIndex()) )
270                 {
271                     // note: r.getStop()==null likely implies that we bailed out of parser and there's nothing to the right
272                     return r;
273                 }
274         }
275         return null;
276     }
277 
278     /**
279      * @uml
280      * Replace any subtree siblings of root that are completely to left
281      * or right of lookahead range with a CommonToken(Token.INVALID_TYPE,"...")
282      * node. The source interval for t is not altered to suit smaller range!
283      *
284      * WARNING: destructive to t.
285      */
286     public static void stripChildrenOutOfRange(ParserRuleContext t, ParserRuleContext root,
287         int startIndex, int stopIndex)
288     {
289         if (t is null) return;
290         for (int i = 0; i < t.getChildCount(); i++) {
291             ParseTree child = t.getChild(i);
292             Interval range = child.getSourceInterval();
293             if (child.classinfo == ParserRuleContext.classinfo && (range.b < startIndex || range.a > stopIndex) ) {
294                 if (isAncestorOf(child, root)) { // replace only if subtree doesn't have displayed root
295                     CommonToken abbrev = new CommonToken(TokenConstantDefinition.INVALID_TYPE, "...");
296                     t.children[i] =  new TerminalNodeImpl(abbrev);
297                 }
298             }
299         }
300     }
301 
302     /**
303      * @uml
304      * Return first node satisfying the pred
305      */
306     public static Tree findNodeSuchThat(Tree t, Predicate!Tree pred)
307     {
308         if (pred.test(t) ) return t;
309 
310         int n = t.getChildCount();
311         for (int i = 0 ; i < n ; i++){
312             Tree u = findNodeSuchThat(t.getChild(i), pred);
313             if (u !is null ) return u;
314         }
315         return null;
316     }
317 
318 }