1/*
2 * [The "BSD licence"]
3 * Copyright (c) 2005-2008 Terence Parr
4 * All rights reserved.
5 *
6 * Conversion to C#:
7 * Copyright (c) 2008 Sam Harwell, Pixel Mine, Inc.
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 * 3. The name of the author may not be used to endorse or promote products
19 *    derived from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
23 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
24 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
26 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
30 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33namespace Antlr.Runtime.Tree
34{
35    public interface ITreeAdaptor<T>
36    {
37        #region Construction
38
39        /** <summary>
40         *  Create a tree node from Token object; for CommonTree type trees,
41         *  then the token just becomes the payload.  This is the most
42         *  common create call.
43         *  </summary>
44         *
45         *  <remarks>
46         *  Override if you want another kind of node to be built.
47         *  </remarks>
48         */
49        T Create(IToken payload);
50
51        /** <summary>Duplicate a single tree node.</summary>
52         *  <remarks>Override if you want another kind of node to be built.</remarks>
53         */
54        T DupNode(T treeNode);
55
56        /** <summary>Duplicate tree recursively, using dupNode() for each node</summary> */
57        T DupTree(T tree);
58
59        /** <summary>
60         *  Return a nil node (an empty but non-null node) that can hold
61         *  a list of element as the children.  If you want a flat tree (a list)
62         *  use "t=adaptor.nil(); t.addChild(x); t.addChild(y);"
63         *  </summary>
64         */
65        T Nil();
66
67        /** <summary>
68         *  Return a tree node representing an error.  This node records the
69         *  tokens consumed during error recovery.  The start token indicates the
70         *  input symbol at which the error was detected.  The stop token indicates
71         *  the last symbol consumed during recovery.
72         *  </summary>
73         *
74         *  </remarks>
75         *  You must specify the input stream so that the erroneous text can
76         *  be packaged up in the error node.  The exception could be useful
77         *  to some applications; default implementation stores ptr to it in
78         *  the CommonErrorNode.
79         *
80         *  This only makes sense during token parsing, not tree parsing.
81         *  Tree parsing should happen only when parsing and tree construction
82         *  succeed.
83         *  </remarks>
84         */
85        T ErrorNode(ITokenStream input, IToken start, IToken stop, RecognitionException e);
86
87        /** <summary>Is tree considered a nil node used to make lists of child nodes?</summary> */
88        bool IsNil(T tree);
89
90        /** <summary>
91         *  Add a child to the tree t.  If child is a flat tree (a list), make all
92         *  in list children of t.  Warning: if t has no children, but child does
93         *  and child isNil then you can decide it is ok to move children to t via
94         *  t.children = child.children; i.e., without copying the array.  Just
95         *  make sure that this is consistent with have the user will build
96         *  ASTs.  Do nothing if t or child is null.
97         *  </summary>
98         */
99        void AddChild(T t, T child);
100
101        /** <summary>
102         *  If oldRoot is a nil root, just copy or move the children to newRoot.
103         *  If not a nil root, make oldRoot a child of newRoot.
104         *  </summary>
105         *
106         *  <remarks>
107         *    old=^(nil a b c), new=r yields ^(r a b c)
108         *    old=^(a b c), new=r yields ^(r ^(a b c))
109         *
110         *  If newRoot is a nil-rooted single child tree, use the single
111         *  child as the new root node.
112         *
113         *    old=^(nil a b c), new=^(nil r) yields ^(r a b c)
114         *    old=^(a b c), new=^(nil r) yields ^(r ^(a b c))
115         *
116         *  If oldRoot was null, it's ok, just return newRoot (even if isNil).
117         *
118         *    old=null, new=r yields r
119         *    old=null, new=^(nil r) yields ^(nil r)
120         *
121         *  Return newRoot.  Throw an exception if newRoot is not a
122         *  simple node or nil root with a single child node--it must be a root
123         *  node.  If newRoot is ^(nil x) return x as newRoot.
124         *
125         *  Be advised that it's ok for newRoot to point at oldRoot's
126         *  children; i.e., you don't have to copy the list.  We are
127         *  constructing these nodes so we should have this control for
128         *  efficiency.
129         *  </remarks>
130         */
131        T BecomeRoot(T newRoot, T oldRoot);
132
133        /** <summary>
134         *  Given the root of the subtree created for this rule, post process
135         *  it to do any simplifications or whatever you want.  A required
136         *  behavior is to convert ^(nil singleSubtree) to singleSubtree
137         *  as the setting of start/stop indexes relies on a single non-nil root
138         *  for non-flat trees.
139         *  </summary>
140         *
141         *  <remarks>
142         *  Flat trees such as for lists like "idlist : ID+ ;" are left alone
143         *  unless there is only one ID.  For a list, the start/stop indexes
144         *  are set in the nil node.
145         *
146         *  This method is executed after all rule tree construction and right
147         *  before setTokenBoundaries().
148         *  </remarks>
149         */
150        T RulePostProcessing(T root);
151
152        /** <summary>For identifying trees.</summary>
153         *
154         *  <remarks>
155         *  How to identify nodes so we can say "add node to a prior node"?
156         *  Even becomeRoot is an issue.  Use System.identityHashCode(node)
157         *  usually.
158         *  </remarks>
159         */
160        int GetUniqueID(T node);
161
162
163        // R e w r i t e  R u l e s
164
165        /** <summary>
166         *  Create a node for newRoot make it the root of oldRoot.
167         *  If oldRoot is a nil root, just copy or move the children to newRoot.
168         *  If not a nil root, make oldRoot a child of newRoot.
169         *  </summary>
170         *
171         *  <returns>
172         *  Return node created for newRoot.
173         *  </returns>
174         *
175         *  <remarks>
176         *  Be advised: when debugging ASTs, the DebugTreeAdaptor manually
177         *  calls create(Token child) and then plain becomeRoot(node, node)
178         *  because it needs to trap calls to create, but it can't since it delegates
179         *  to not inherits from the TreeAdaptor.
180         *  </remarks>
181         */
182        T BecomeRoot(IToken newRoot, T oldRoot);
183
184        /** <summary>
185         *  Create a new node derived from a token, with a new token type.
186         *  This is invoked from an imaginary node ref on right side of a
187         *  rewrite rule as IMAG[$tokenLabel].
188         *  </summary>
189         *
190         *  <remarks>
191         *  This should invoke createToken(Token).
192         *  </remarks>
193         */
194        T Create(int tokenType, IToken fromToken);
195
196        /** <summary>
197         *  Same as create(tokenType,fromToken) except set the text too.
198         *  This is invoked from an imaginary node ref on right side of a
199         *  rewrite rule as IMAG[$tokenLabel, "IMAG"].
200         *  </summary>
201         *
202         *  <remarks>
203         *  This should invoke createToken(Token).
204         *  </remarks>
205         */
206        T Create(int tokenType, IToken fromToken, string text);
207
208        /** <summary>
209         *  Create a new node derived from a token, with a new token type.
210         *  This is invoked from an imaginary node ref on right side of a
211         *  rewrite rule as IMAG["IMAG"].
212         *  </summary>
213         *
214         *  <remarks>
215         *  This should invoke createToken(int,String).
216         *  </remarks>
217         */
218        T Create(int tokenType, string text);
219
220        #endregion
221
222
223        #region Content
224
225        /** <summary>For tree parsing, I need to know the token type of a node</summary> */
226        int GetType(T t);
227
228        /** <summary>Node constructors can set the type of a node</summary> */
229        void SetType(T t, int type);
230
231        string GetText(T t);
232
233        /** <summary>Node constructors can set the text of a node</summary> */
234        void SetText(T t, string text);
235
236        /** <summary>
237         *  Return the token object from which this node was created.
238         *  Currently used only for printing an error message.
239         *  The error display routine in BaseRecognizer needs to
240         *  display where the input the error occurred. If your
241         *  tree of limitation does not store information that can
242         *  lead you to the token, you can create a token filled with
243         *  the appropriate information and pass that back.  See
244         *  BaseRecognizer.getErrorMessage().
245         *  </summary>
246         */
247        IToken GetToken(T t);
248
249        /** <summary>
250         *  Where are the bounds in the input token stream for this node and
251         *  all children?  Each rule that creates AST nodes will call this
252         *  method right before returning.  Flat trees (i.e., lists) will
253         *  still usually have a nil root node just to hold the children list.
254         *  That node would contain the start/stop indexes then.
255         *  </summary>
256         */
257        void SetTokenBoundaries(T t, IToken startToken, IToken stopToken);
258
259        /** <summary>Get the token start index for this subtree; return -1 if no such index</summary> */
260        int GetTokenStartIndex(T t);
261
262        /** <summary>Get the token stop index for this subtree; return -1 if no such index</summary> */
263        int GetTokenStopIndex(T t);
264
265        #endregion
266
267
268        #region Navigation / Tree Parsing
269
270        /** <summary>Get a child 0..n-1 node</summary> */
271        T GetChild(T t, int i);
272
273        /** <summary>Set ith child (0..n-1) to t; t must be non-null and non-nil node</summary> */
274        void SetChild(T t, int i, T child);
275
276        /** <summary>Remove ith child and shift children down from right.</summary> */
277        T DeleteChild(T t, int i);
278
279        /** <summary>How many children?  If 0, then this is a leaf node</summary> */
280        int GetChildCount(T t);
281
282        /** <summary>
283         *  Who is the parent node of this node; if null, implies node is root.
284         *  If your node type doesn't handle this, it's ok but the tree rewrites
285         *  in tree parsers need this functionality.
286         *  </summary>
287         */
288        T GetParent(T t);
289        void SetParent(T t, T parent);
290
291        /** <summary>
292         *  What index is this node in the child list? Range: 0..n-1
293         *  If your node type doesn't handle this, it's ok but the tree rewrites
294         *  in tree parsers need this functionality.
295         *  </summary>
296         */
297        int GetChildIndex(T t);
298        void SetChildIndex(T t, int index);
299
300        /** <summary>
301         *  Replace from start to stop child index of parent with t, which might
302         *  be a list.  Number of children may be different after this call.
303         *  </summary>
304         *
305         *  <remarks>
306         *  If parent is null, don't do anything; must be at root of overall tree.
307         *  Can't replace whatever points to the parent externally.  Do nothing.
308         *  </remarks>
309         */
310        void ReplaceChildren(T parent, int startChildIndex, int stopChildIndex, T t);
311
312        #endregion
313    }
314}
315