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