001: /*
002: [The "BSD licence"]
003: Copyright (c) 2005-2006 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.test;
029:
030: import org.antlr.runtime.CommonToken;
031: import org.antlr.runtime.Token;
032: import org.antlr.runtime.tree.*;
033:
034: /** Test the tree node stream. */
035: public class TestTreeNodeStream extends BaseTest {
036:
037: /** Build new stream; let's us override to test other streams. */
038: public TreeNodeStream newStream(Object t) {
039: return new CommonTreeNodeStream(t);
040: }
041:
042: public void testSingleNode() throws Exception {
043: Tree t = new CommonTree(new CommonToken(101));
044:
045: TreeNodeStream stream = newStream(t);
046: String expecting = " 101";
047: String found = toNodesOnlyString(stream);
048: assertEquals(expecting, found);
049:
050: expecting = " 101";
051: found = stream.toString();
052: assertEquals(expecting, found);
053: }
054:
055: public void test4Nodes() throws Exception {
056: // ^(101 ^(102 103) 104)
057: Tree t = new CommonTree(new CommonToken(101));
058: t.addChild(new CommonTree(new CommonToken(102)));
059: t.getChild(0).addChild(new CommonTree(new CommonToken(103)));
060: t.addChild(new CommonTree(new CommonToken(104)));
061:
062: TreeNodeStream stream = newStream(t);
063: String expecting = " 101 102 103 104";
064: String found = toNodesOnlyString(stream);
065: assertEquals(expecting, found);
066:
067: expecting = " 101 2 102 2 103 3 104 3";
068: found = stream.toString();
069: assertEquals(expecting, found);
070: }
071:
072: public void testList() throws Exception {
073: Tree root = new CommonTree((Token) null);
074:
075: Tree t = new CommonTree(new CommonToken(101));
076: t.addChild(new CommonTree(new CommonToken(102)));
077: t.getChild(0).addChild(new CommonTree(new CommonToken(103)));
078: t.addChild(new CommonTree(new CommonToken(104)));
079:
080: Tree u = new CommonTree(new CommonToken(105));
081:
082: root.addChild(t);
083: root.addChild(u);
084:
085: CommonTreeNodeStream stream = new CommonTreeNodeStream(root);
086: String expecting = " 101 102 103 104 105";
087: String found = toNodesOnlyString(stream);
088: assertEquals(expecting, found);
089:
090: expecting = " 101 2 102 2 103 3 104 3 105";
091: found = stream.toString();
092: assertEquals(expecting, found);
093: }
094:
095: public void testFlatList() throws Exception {
096: Tree root = new CommonTree((Token) null);
097:
098: root.addChild(new CommonTree(new CommonToken(101)));
099: root.addChild(new CommonTree(new CommonToken(102)));
100: root.addChild(new CommonTree(new CommonToken(103)));
101:
102: CommonTreeNodeStream stream = new CommonTreeNodeStream(root);
103: String expecting = " 101 102 103";
104: String found = toNodesOnlyString(stream);
105: assertEquals(expecting, found);
106:
107: expecting = " 101 102 103";
108: found = stream.toString();
109: assertEquals(expecting, found);
110: }
111:
112: public void testListWithOneNode() throws Exception {
113: Tree root = new CommonTree((Token) null);
114:
115: root.addChild(new CommonTree(new CommonToken(101)));
116:
117: CommonTreeNodeStream stream = new CommonTreeNodeStream(root);
118: String expecting = " 101";
119: String found = toNodesOnlyString(stream);
120: assertEquals(expecting, found);
121:
122: expecting = " 101";
123: found = stream.toString();
124: assertEquals(expecting, found);
125: }
126:
127: public void testAoverB() throws Exception {
128: Tree t = new CommonTree(new CommonToken(101));
129: t.addChild(new CommonTree(new CommonToken(102)));
130:
131: TreeNodeStream stream = newStream(t);
132: String expecting = " 101 102";
133: String found = toNodesOnlyString(stream);
134: assertEquals(expecting, found);
135:
136: expecting = " 101 2 102 3";
137: found = stream.toString();
138: assertEquals(expecting, found);
139: }
140:
141: public void testLT() throws Exception {
142: // ^(101 ^(102 103) 104)
143: Tree t = new CommonTree(new CommonToken(101));
144: t.addChild(new CommonTree(new CommonToken(102)));
145: t.getChild(0).addChild(new CommonTree(new CommonToken(103)));
146: t.addChild(new CommonTree(new CommonToken(104)));
147:
148: TreeNodeStream stream = newStream(t);
149: assertEquals(101, ((Tree) stream.LT(1)).getType());
150: assertEquals(Token.DOWN, ((Tree) stream.LT(2)).getType());
151: assertEquals(102, ((Tree) stream.LT(3)).getType());
152: assertEquals(Token.DOWN, ((Tree) stream.LT(4)).getType());
153: assertEquals(103, ((Tree) stream.LT(5)).getType());
154: assertEquals(Token.UP, ((Tree) stream.LT(6)).getType());
155: assertEquals(104, ((Tree) stream.LT(7)).getType());
156: assertEquals(Token.UP, ((Tree) stream.LT(8)).getType());
157: assertEquals(Token.EOF, ((Tree) stream.LT(9)).getType());
158: // check way ahead
159: assertEquals(Token.EOF, ((Tree) stream.LT(100)).getType());
160: }
161:
162: public void testMarkRewindEntire() throws Exception {
163: // ^(101 ^(102 103 ^(106 107) ) 104 105)
164: // stream has 7 real + 6 nav nodes
165: // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
166: Tree r0 = new CommonTree(new CommonToken(101));
167: Tree r1 = new CommonTree(new CommonToken(102));
168: r0.addChild(r1);
169: r1.addChild(new CommonTree(new CommonToken(103)));
170: Tree r2 = new CommonTree(new CommonToken(106));
171: r2.addChild(new CommonTree(new CommonToken(107)));
172: r1.addChild(r2);
173: r0.addChild(new CommonTree(new CommonToken(104)));
174: r0.addChild(new CommonTree(new CommonToken(105)));
175:
176: CommonTreeNodeStream stream = new CommonTreeNodeStream(r0);
177: int m = stream.mark(); // MARK
178: for (int k = 1; k <= 13; k++) { // consume til end
179: stream.LT(1);
180: stream.consume();
181: }
182: assertEquals(Token.EOF, ((Tree) stream.LT(1)).getType());
183: assertEquals(Token.UP, ((Tree) stream.LT(-1)).getType());
184: stream.rewind(m); // REWIND
185:
186: // consume til end again :)
187: for (int k = 1; k <= 13; k++) { // consume til end
188: stream.LT(1);
189: stream.consume();
190: }
191: assertEquals(Token.EOF, ((Tree) stream.LT(1)).getType());
192: assertEquals(Token.UP, ((Tree) stream.LT(-1)).getType());
193: }
194:
195: public void testMarkRewindInMiddle() throws Exception {
196: // ^(101 ^(102 103 ^(106 107) ) 104 105)
197: // stream has 7 real + 6 nav nodes
198: // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
199: Tree r0 = new CommonTree(new CommonToken(101));
200: Tree r1 = new CommonTree(new CommonToken(102));
201: r0.addChild(r1);
202: r1.addChild(new CommonTree(new CommonToken(103)));
203: Tree r2 = new CommonTree(new CommonToken(106));
204: r2.addChild(new CommonTree(new CommonToken(107)));
205: r1.addChild(r2);
206: r0.addChild(new CommonTree(new CommonToken(104)));
207: r0.addChild(new CommonTree(new CommonToken(105)));
208:
209: CommonTreeNodeStream stream = new CommonTreeNodeStream(r0);
210: for (int k = 1; k <= 7; k++) { // consume til middle
211: //System.out.println(((Tree)stream.LT(1)).getType());
212: stream.consume();
213: }
214: assertEquals(107, ((Tree) stream.LT(1)).getType());
215: int m = stream.mark(); // MARK
216: stream.consume(); // consume 107
217: stream.consume(); // consume UP
218: stream.consume(); // consume UP
219: stream.consume(); // consume 104
220: stream.rewind(m); // REWIND
221:
222: assertEquals(107, ((Tree) stream.LT(1)).getType());
223: stream.consume();
224: assertEquals(Token.UP, ((Tree) stream.LT(1)).getType());
225: stream.consume();
226: assertEquals(Token.UP, ((Tree) stream.LT(1)).getType());
227: stream.consume();
228: assertEquals(104, ((Tree) stream.LT(1)).getType());
229: stream.consume();
230: // now we're past rewind position
231: assertEquals(105, ((Tree) stream.LT(1)).getType());
232: stream.consume();
233: assertEquals(Token.UP, ((Tree) stream.LT(1)).getType());
234: stream.consume();
235: assertEquals(Token.EOF, ((Tree) stream.LT(1)).getType());
236: assertEquals(Token.UP, ((Tree) stream.LT(-1)).getType());
237: }
238:
239: public void testMarkRewindNested() throws Exception {
240: // ^(101 ^(102 103 ^(106 107) ) 104 105)
241: // stream has 7 real + 6 nav nodes
242: // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
243: Tree r0 = new CommonTree(new CommonToken(101));
244: Tree r1 = new CommonTree(new CommonToken(102));
245: r0.addChild(r1);
246: r1.addChild(new CommonTree(new CommonToken(103)));
247: Tree r2 = new CommonTree(new CommonToken(106));
248: r2.addChild(new CommonTree(new CommonToken(107)));
249: r1.addChild(r2);
250: r0.addChild(new CommonTree(new CommonToken(104)));
251: r0.addChild(new CommonTree(new CommonToken(105)));
252:
253: CommonTreeNodeStream stream = new CommonTreeNodeStream(r0);
254: int m = stream.mark(); // MARK at start
255: stream.consume(); // consume 101
256: stream.consume(); // consume DN
257: int m2 = stream.mark(); // MARK on 102
258: stream.consume(); // consume 102
259: stream.consume(); // consume DN
260: stream.consume(); // consume 103
261: stream.consume(); // consume 106
262: stream.rewind(m2); // REWIND to 102
263: assertEquals(102, ((Tree) stream.LT(1)).getType());
264: stream.consume();
265: assertEquals(Token.DOWN, ((Tree) stream.LT(1)).getType());
266: stream.consume();
267: // stop at 103 and rewind to start
268: stream.rewind(m); // REWIND to 101
269: assertEquals(101, ((Tree) stream.LT(1)).getType());
270: stream.consume();
271: assertEquals(Token.DOWN, ((Tree) stream.LT(1)).getType());
272: stream.consume();
273: assertEquals(102, ((Tree) stream.LT(1)).getType());
274: stream.consume();
275: assertEquals(Token.DOWN, ((Tree) stream.LT(1)).getType());
276: }
277:
278: public void testSeek() throws Exception {
279: // ^(101 ^(102 103 ^(106 107) ) 104 105)
280: // stream has 7 real + 6 nav nodes
281: // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
282: Tree r0 = new CommonTree(new CommonToken(101));
283: Tree r1 = new CommonTree(new CommonToken(102));
284: r0.addChild(r1);
285: r1.addChild(new CommonTree(new CommonToken(103)));
286: Tree r2 = new CommonTree(new CommonToken(106));
287: r2.addChild(new CommonTree(new CommonToken(107)));
288: r1.addChild(r2);
289: r0.addChild(new CommonTree(new CommonToken(104)));
290: r0.addChild(new CommonTree(new CommonToken(105)));
291:
292: CommonTreeNodeStream stream = new CommonTreeNodeStream(r0);
293: stream.consume(); // consume 101
294: stream.consume(); // consume DN
295: stream.consume(); // consume 102
296: stream.seek(7); // seek to 107
297: assertEquals(107, ((Tree) stream.LT(1)).getType());
298: stream.consume(); // consume 107
299: stream.consume(); // consume UP
300: stream.consume(); // consume UP
301: assertEquals(104, ((Tree) stream.LT(1)).getType());
302: }
303:
304: public void testSeekFromStart() throws Exception {
305: // ^(101 ^(102 103 ^(106 107) ) 104 105)
306: // stream has 7 real + 6 nav nodes
307: // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
308: Tree r0 = new CommonTree(new CommonToken(101));
309: Tree r1 = new CommonTree(new CommonToken(102));
310: r0.addChild(r1);
311: r1.addChild(new CommonTree(new CommonToken(103)));
312: Tree r2 = new CommonTree(new CommonToken(106));
313: r2.addChild(new CommonTree(new CommonToken(107)));
314: r1.addChild(r2);
315: r0.addChild(new CommonTree(new CommonToken(104)));
316: r0.addChild(new CommonTree(new CommonToken(105)));
317:
318: CommonTreeNodeStream stream = new CommonTreeNodeStream(r0);
319: stream.seek(7); // seek to 107
320: assertEquals(107, ((Tree) stream.LT(1)).getType());
321: stream.consume(); // consume 107
322: stream.consume(); // consume UP
323: stream.consume(); // consume UP
324: assertEquals(104, ((Tree) stream.LT(1)).getType());
325: }
326:
327: public String toNodesOnlyString(TreeNodeStream nodes) {
328: StringBuffer buf = new StringBuffer();
329: for (int i = 0; i < nodes.size(); i++) {
330: Object t = nodes.LT(i + 1);
331: int type = nodes.getTreeAdaptor().getType(t);
332: if (!(type == Token.DOWN || type == Token.UP)) {
333: buf.append(" ");
334: buf.append(type);
335: }
336: }
337: return buf.toString();
338: }
339: }
|