001: /*
002: [The "BSD licence"]
003: Copyright (c) 2005-2007 Terence Parr
004: All rights reserved.
005:
006: Redistribution and use in source and binary forms, with or without
007: modification, are permitted provided that the following conditions
008: are met:
009: 1. Redistributions of source code must retain the above copyright
010: notice, this list of conditions and the following disclaimer.
011: 2. Redistributions in binary form must reproduce the above copyright
012: notice, this list of conditions and the following disclaimer in the
013: documentation and/or other materials provided with the distribution.
014: 3. The name of the author may not be used to endorse or promote products
015: derived from this software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
018: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
019: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
020: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
021: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
022: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
023: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
024: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
026: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028: package org.antlr.runtime.tree;
029:
030: import org.antlr.runtime.Token;
031:
032: /** How to create and navigate trees. Rather than have a separate factory
033: * and adaptor, I've merged them. Makes sense to encapsulate.
034: *
035: * This takes the place of the tree construction code generated in the
036: * generated code in 2.x and the ASTFactory.
037: *
038: * I do not need to know the type of a tree at all so they are all
039: * generic Objects. This may increase the amount of typecasting needed. :(
040: */
041: public interface TreeAdaptor {
042: // C o n s t r u c t i o n
043:
044: /** Create a tree node from Token object; for CommonTree type trees,
045: * then the token just becomes the payload. This is the most
046: * common create call.
047: */
048: public Object create(Token payload);
049:
050: /** Duplicate tree recursively, using dupNode() for each node */
051: public Object dupTree(Object tree);
052:
053: /** Duplicate a single tree node */
054: public Object dupNode(Object treeNode);
055:
056: /** Return a nil node (an empty but non-null node) that can hold
057: * a list of element as the children. If you want a flat tree (a list)
058: * use "t=adaptor.nil(); t.addChild(x); t.addChild(y);"
059: */
060: public Object nil();
061:
062: /** Is tree considered a nil node used to make lists of child nodes? */
063: public boolean isNil(Object tree);
064:
065: /** Add a child to the tree t. If child is a flat tree (a list), make all
066: * in list children of t. Warning: if t has no children, but child does
067: * and child isNil then you can decide it is ok to move children to t via
068: * t.children = child.children; i.e., without copying the array. Just
069: * make sure that this is consistent with have the user will build
070: * ASTs. Do nothing if t or child is null.
071: */
072: public void addChild(Object t, Object child);
073:
074: /** If oldRoot is a nil root, just copy or move the children to newRoot.
075: * If not a nil root, make oldRoot a child of newRoot.
076: *
077: * old=^(nil a b c), new=r yields ^(r a b c)
078: * old=^(a b c), new=r yields ^(r ^(a b c))
079: *
080: * If newRoot is a nil-rooted single child tree, use the single
081: * child as the new root node.
082: *
083: * old=^(nil a b c), new=^(nil r) yields ^(r a b c)
084: * old=^(a b c), new=^(nil r) yields ^(r ^(a b c))
085: *
086: * If oldRoot was null, it's ok, just return newRoot (even if isNil).
087: *
088: * old=null, new=r yields r
089: * old=null, new=^(nil r) yields ^(nil r)
090: *
091: * Return newRoot. Throw an exception if newRoot is not a
092: * simple node or nil root with a single child node--it must be a root
093: * node. If newRoot is ^(nil x) return x as newRoot.
094: *
095: * Be advised that it's ok for newRoot to point at oldRoot's
096: * children; i.e., you don't have to copy the list. We are
097: * constructing these nodes so we should have this control for
098: * efficiency.
099: */
100: public Object becomeRoot(Object newRoot, Object oldRoot);
101:
102: /** Given the root of the subtree created for this rule, post process
103: * it to do any simplifications or whatever you want. A required
104: * behavior is to convert ^(nil singleSubtree) to singleSubtree
105: * as the setting of start/stop indexes relies on a single non-nil root
106: * for non-flat trees.
107: *
108: * Flat trees such as for lists like "idlist : ID+ ;" are left alone
109: * unless there is only one ID. For a list, the start/stop indexes
110: * are set in the nil node.
111: *
112: * This method is executed after all rule tree construction and right
113: * before setTokenBoundaries().
114: */
115: public Object rulePostProcessing(Object root);
116:
117: /** For identifying trees.
118: *
119: * How to identify nodes so we can say "add node to a prior node"?
120: * Even becomeRoot is an issue. Use System.identityHashCode(node)
121: * usually.
122: */
123: public int getUniqueID(Object node);
124:
125: // R e w r i t e R u l e s
126:
127: /** Create a node for newRoot make it the root of oldRoot.
128: * If oldRoot is a nil root, just copy or move the children to newRoot.
129: * If not a nil root, make oldRoot a child of newRoot.
130: *
131: * Return node created for newRoot.
132: *
133: * Be advised: when debugging ASTs, the DebugTreeAdaptor manually
134: * calls create(Token child) and then plain becomeRoot(node, node)
135: * because it needs to trap calls to create, but it can't since it delegates
136: * to not inherits from the TreeAdaptor.
137: */
138: public Object becomeRoot(Token newRoot, Object oldRoot);
139:
140: /** Create a new node derived from a token, with a new token type.
141: * This is invoked from an imaginary node ref on right side of a
142: * rewrite rule as IMAG[$tokenLabel].
143: *
144: * This should invoke createToken(Token).
145: */
146: public Object create(int tokenType, Token fromToken);
147:
148: /** Same as create(tokenType,fromToken) except set the text too.
149: * This is invoked from an imaginary node ref on right side of a
150: * rewrite rule as IMAG[$tokenLabel, "IMAG"].
151: *
152: * This should invoke createToken(Token).
153: */
154: public Object create(int tokenType, Token fromToken, String text);
155:
156: /** Create a new node derived from a token, with a new token type.
157: * This is invoked from an imaginary node ref on right side of a
158: * rewrite rule as IMAG["IMAG"].
159: *
160: * This should invoke createToken(int,String).
161: */
162: public Object create(int tokenType, String text);
163:
164: // C o n t e n t
165:
166: /** For tree parsing, I need to know the token type of a node */
167: public int getType(Object t);
168:
169: /** Node constructors can set the type of a node */
170: public void setType(Object t, int type);
171:
172: public String getText(Object t);
173:
174: /** Node constructors can set the text of a node */
175: public void setText(Object t, String text);
176:
177: /** Return the token object from which this node was created.
178: * Currently used only for printing an error message.
179: * The error display routine in BaseRecognizer needs to
180: * display where the input the error occurred. If your
181: * tree of limitation does not store information that can
182: * lead you to the token, you can create a token filled with
183: * the appropriate information and pass that back. See
184: * BaseRecognizer.getErrorMessage().
185: */
186: public Token getToken(Object t);
187:
188: /** Where are the bounds in the input token stream for this node and
189: * all children? Each rule that creates AST nodes will call this
190: * method right before returning. Flat trees (i.e., lists) will
191: * still usually have a nil root node just to hold the children list.
192: * That node would contain the start/stop indexes then.
193: */
194: public void setTokenBoundaries(Object t, Token startToken,
195: Token stopToken);
196:
197: /** Get the token start index for this subtree; return -1 if no such index */
198: public int getTokenStartIndex(Object t);
199:
200: /** Get the token stop index for this subtree; return -1 if no such index */
201: public int getTokenStopIndex(Object t);
202:
203: // N a v i g a t i o n / T r e e P a r s i n g
204:
205: /** Get a child 0..n-1 node */
206: public Object getChild(Object t, int i);
207:
208: /** How many children? If 0, then this is a leaf node */
209: public int getChildCount(Object t);
210: }
|