antlr-3.4/tool/src/test/java/org/antlr/test/TestTreeNodeStream.java

/*
 * [The "BSD license"]
 *  Copyright (c) 2010 Terence Parr
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions
 *  are met:
 *  1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *  2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *  3. The name of the author may not be used to endorse or promote products
 *      derived from this software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 *  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 *  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.antlr.test;

import org.antlr.runtime.CommonToken;
import org.antlr.runtime.Token;
import org.antlr.runtime.tree.*;
import org.junit.Test;

/** Test the tree node stream. */
public class TestTreeNodeStream extends BaseTest {

	/** Build new stream; let's us override to test other streams. */
	public TreeNodeStream newStream(Object t) {
		return new CommonTreeNodeStream(t);
	}

    public String toTokenTypeString(TreeNodeStream stream) {
        return ((CommonTreeNodeStream)stream).toTokenTypeString();
    }

	@Test public void testSingleNode() throws Exception {
		Tree t = new CommonTree(new CommonToken(101));

		TreeNodeStream stream = newStream(t);
		String expecting = " 101";
		String found = toNodesOnlyString(stream);
		assertEquals(expecting, found);

		expecting = " 101";
		found = toTokenTypeString(stream);
		assertEquals(expecting, found);
	}

	@Test public void test4Nodes() throws Exception {
		// ^(101 ^(102 103) 104)
		Tree t = new CommonTree(new CommonToken(101));
		t.addChild(new CommonTree(new CommonToken(102)));
		t.getChild(0).addChild(new CommonTree(new CommonToken(103)));
		t.addChild(new CommonTree(new CommonToken(104)));

		TreeNodeStream stream = newStream(t);
		String expecting = " 101 102 103 104";
		String found = toNodesOnlyString(stream);
		assertEquals(expecting, found);

		expecting = " 101 2 102 2 103 3 104 3";
		found = toTokenTypeString(stream);
		assertEquals(expecting, found);
	}

	@Test public void testList() throws Exception {
		Tree root = new CommonTree((Token)null);

		Tree t = new CommonTree(new CommonToken(101));
		t.addChild(new CommonTree(new CommonToken(102)));
		t.getChild(0).addChild(new CommonTree(new CommonToken(103)));
		t.addChild(new CommonTree(new CommonToken(104)));

		Tree u = new CommonTree(new CommonToken(105));

		root.addChild(t);
		root.addChild(u);

		TreeNodeStream stream = newStream(root);
		String expecting = " 101 102 103 104 105";
		String found = toNodesOnlyString(stream);
		assertEquals(expecting, found);

		expecting = " 101 2 102 2 103 3 104 3 105";
		found = toTokenTypeString(stream);
		assertEquals(expecting, found);
	}

	@Test public void testFlatList() throws Exception {
		Tree root = new CommonTree((Token)null);

		root.addChild(new CommonTree(new CommonToken(101)));
		root.addChild(new CommonTree(new CommonToken(102)));
		root.addChild(new CommonTree(new CommonToken(103)));

		TreeNodeStream stream = newStream(root);
		String expecting = " 101 102 103";
		String found = toNodesOnlyString(stream);
		assertEquals(expecting, found);

		expecting = " 101 102 103";
		found = toTokenTypeString(stream);
		assertEquals(expecting, found);
	}

	@Test public void testListWithOneNode() throws Exception {
		Tree root = new CommonTree((Token)null);

		root.addChild(new CommonTree(new CommonToken(101)));

		TreeNodeStream stream = newStream(root);
		String expecting = " 101";
		String found = toNodesOnlyString(stream);
		assertEquals(expecting, found);

		expecting = " 101";
		found = toTokenTypeString(stream);
		assertEquals(expecting, found);
	}

	@Test public void testAoverB() throws Exception {
		Tree t = new CommonTree(new CommonToken(101));
		t.addChild(new CommonTree(new CommonToken(102)));

		TreeNodeStream stream = newStream(t);
		String expecting = " 101 102";
		String found = toNodesOnlyString(stream);
		assertEquals(expecting, found);

		expecting = " 101 2 102 3";
		found = toTokenTypeString(stream);
		assertEquals(expecting, found);
	}

	@Test public void testLT() throws Exception {
		// ^(101 ^(102 103) 104)
		Tree t = new CommonTree(new CommonToken(101));
		t.addChild(new CommonTree(new CommonToken(102)));
		t.getChild(0).addChild(new CommonTree(new CommonToken(103)));
		t.addChild(new CommonTree(new CommonToken(104)));

		TreeNodeStream stream = newStream(t);
		assertEquals(101, ((Tree)stream.LT(1)).getType());
		assertEquals(Token.DOWN, ((Tree)stream.LT(2)).getType());
		assertEquals(102, ((Tree)stream.LT(3)).getType());
		assertEquals(Token.DOWN, ((Tree)stream.LT(4)).getType());
		assertEquals(103, ((Tree)stream.LT(5)).getType());
		assertEquals(Token.UP, ((Tree)stream.LT(6)).getType());
		assertEquals(104, ((Tree)stream.LT(7)).getType());
		assertEquals(Token.UP, ((Tree)stream.LT(8)).getType());
		assertEquals(Token.EOF, ((Tree)stream.LT(9)).getType());
		// check way ahead
		assertEquals(Token.EOF, ((Tree)stream.LT(100)).getType());
	}

	@Test public void testMarkRewindEntire() throws Exception {
		// ^(101 ^(102 103 ^(106 107) ) 104 105)
		// stream has 7 real + 6 nav nodes
		// Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
		Tree r0 = new CommonTree(new CommonToken(101));
		Tree r1 = new CommonTree(new CommonToken(102));
		r0.addChild(r1);
		r1.addChild(new CommonTree(new CommonToken(103)));
		Tree r2 = new CommonTree(new CommonToken(106));
		r2.addChild(new CommonTree(new CommonToken(107)));
		r1.addChild(r2);
		r0.addChild(new CommonTree(new CommonToken(104)));
		r0.addChild(new CommonTree(new CommonToken(105)));

		TreeNodeStream stream = newStream(r0);
		int m = stream.mark(); // MARK
		for (int k=1; k<=13; k++) { // consume til end
			stream.LT(1);
			stream.consume();
		}
		assertEquals(Token.EOF, ((Tree)stream.LT(1)).getType());
		stream.rewind(m);      // REWIND

		// consume til end again :)
		for (int k=1; k<=13; k++) { // consume til end
			stream.LT(1);
			stream.consume();
		}
		assertEquals(Token.EOF, ((Tree)stream.LT(1)).getType());
	}

	@Test public void testMarkRewindInMiddle() throws Exception {
		// ^(101 ^(102 103 ^(106 107) ) 104 105)
		// stream has 7 real + 6 nav nodes
		// Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
		Tree r0 = new CommonTree(new CommonToken(101));
		Tree r1 = new CommonTree(new CommonToken(102));
		r0.addChild(r1);
		r1.addChild(new CommonTree(new CommonToken(103)));
		Tree r2 = new CommonTree(new CommonToken(106));
		r2.addChild(new CommonTree(new CommonToken(107)));
		r1.addChild(r2);
		r0.addChild(new CommonTree(new CommonToken(104)));
		r0.addChild(new CommonTree(new CommonToken(105)));

		TreeNodeStream stream = newStream(r0);
		for (int k=1; k<=7; k++) { // consume til middle
			//System.out.println(((Tree)stream.LT(1)).getType());
			stream.consume();
		}
		assertEquals(107, ((Tree)stream.LT(1)).getType());
		stream.mark(); // MARK
		stream.consume(); // consume 107
		stream.consume(); // consume UP
		stream.consume(); // consume UP
		stream.consume(); // consume 104
		stream.rewind(); // REWIND
        stream.mark();   // keep saving nodes though

		assertEquals(107, ((Tree)stream.LT(1)).getType());
		stream.consume();
		assertEquals(Token.UP, ((Tree)stream.LT(1)).getType());
		stream.consume();
		assertEquals(Token.UP, ((Tree)stream.LT(1)).getType());
		stream.consume();
		assertEquals(104, ((Tree)stream.LT(1)).getType());
		stream.consume();
		// now we're past rewind position
		assertEquals(105, ((Tree)stream.LT(1)).getType());
		stream.consume();
		assertEquals(Token.UP, ((Tree)stream.LT(1)).getType());
		stream.consume();
		assertEquals(Token.EOF, ((Tree)stream.LT(1)).getType());
		assertEquals(Token.UP, ((Tree)stream.LT(-1)).getType());
	}

	@Test public void testMarkRewindNested() throws Exception {
		// ^(101 ^(102 103 ^(106 107) ) 104 105)
		// stream has 7 real + 6 nav nodes
		// Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
		Tree r0 = new CommonTree(new CommonToken(101));
		Tree r1 = new CommonTree(new CommonToken(102));
		r0.addChild(r1);
		r1.addChild(new CommonTree(new CommonToken(103)));
		Tree r2 = new CommonTree(new CommonToken(106));
		r2.addChild(new CommonTree(new CommonToken(107)));
		r1.addChild(r2);
		r0.addChild(new CommonTree(new CommonToken(104)));
		r0.addChild(new CommonTree(new CommonToken(105)));

		TreeNodeStream stream = newStream(r0);
		int m = stream.mark(); // MARK at start
		stream.consume(); // consume 101
		stream.consume(); // consume DN
		int m2 = stream.mark(); // MARK on 102
		stream.consume(); // consume 102
		stream.consume(); // consume DN
		stream.consume(); // consume 103
		stream.consume(); // consume 106
		stream.rewind(m2);      // REWIND to 102
		assertEquals(102, ((Tree)stream.LT(1)).getType());
		stream.consume();
		assertEquals(Token.DOWN, ((Tree)stream.LT(1)).getType());
		stream.consume();
		// stop at 103 and rewind to start
		stream.rewind(m); // REWIND to 101
		assertEquals(101, ((Tree)stream.LT(1)).getType());
		stream.consume();
		assertEquals(Token.DOWN, ((Tree)stream.LT(1)).getType());
		stream.consume();
		assertEquals(102, ((Tree)stream.LT(1)).getType());
		stream.consume();
		assertEquals(Token.DOWN, ((Tree)stream.LT(1)).getType());
	}

	@Test public void testSeekFromStart() throws Exception {
		// ^(101 ^(102 103 ^(106 107) ) 104 105)
		// stream has 7 real + 6 nav nodes
		// Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
		Tree r0 = new CommonTree(new CommonToken(101));
		Tree r1 = new CommonTree(new CommonToken(102));
		r0.addChild(r1);
		r1.addChild(new CommonTree(new CommonToken(103)));
		Tree r2 = new CommonTree(new CommonToken(106));
		r2.addChild(new CommonTree(new CommonToken(107)));
		r1.addChild(r2);
		r0.addChild(new CommonTree(new CommonToken(104)));
		r0.addChild(new CommonTree(new CommonToken(105)));

		TreeNodeStream stream = newStream(r0);
		stream.seek(7);   // seek to 107
		assertEquals(107, ((Tree)stream.LT(1)).getType());
		stream.consume(); // consume 107
		stream.consume(); // consume UP
		stream.consume(); // consume UP
		assertEquals(104, ((Tree)stream.LT(1)).getType());
	}

    @Test public void testReset() throws Exception {
        // ^(101 ^(102 103 ^(106 107) ) 104 105)
        // stream has 7 real + 6 nav nodes
        // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF
        Tree r0 = new CommonTree(new CommonToken(101));
        Tree r1 = new CommonTree(new CommonToken(102));
        r0.addChild(r1);
        r1.addChild(new CommonTree(new CommonToken(103)));
        Tree r2 = new CommonTree(new CommonToken(106));
        r2.addChild(new CommonTree(new CommonToken(107)));
        r1.addChild(r2);
        r0.addChild(new CommonTree(new CommonToken(104)));
        r0.addChild(new CommonTree(new CommonToken(105)));

        TreeNodeStream stream = newStream(r0);
        String v = toNodesOnlyString(stream); // scan all
        stream.reset();
        String v2 = toNodesOnlyString(stream); // scan all
        assertEquals(v, v2);
    }

	@Test public void testDeepTree() throws Exception {
		// ^(10 100 101 ^(20 ^(30 40 (50 (60 70)))) (80 90)))
		// stream has 8 real + 10 nav nodes
		int n = 9;
		CommonTree[] nodes = new CommonTree[n];
		for (int i=0; i< n; i++) {
			nodes[i] = new CommonTree(new CommonToken((i+1)*10));
		}
		Tree g = nodes[0];
		Tree rules = nodes[1];
		Tree rule1 = nodes[2];
		Tree id = nodes[3];
		Tree block = nodes[4];
		Tree alt = nodes[5];
		Tree s = nodes[6];
		Tree rule2 = nodes[7];
		Tree id2 = nodes[8];
		g.addChild(new CommonTree(new CommonToken(100)));
		g.addChild(new CommonTree(new CommonToken(101)));
		g.addChild(rules);
		rules.addChild(rule1);
		rule1.addChild(id);
		rule1.addChild(block);
		block.addChild(alt);
		alt.addChild(s);
		rules.addChild(rule2);
		rule2.addChild(id2);

		TreeNodeStream stream = newStream(g);
		String expecting = " 10 2 100 101 20 2 30 2 40 50 2 60 2 70 3 3 3 80 2 90 3 3 3";
		String found = toTokenTypeString(stream);
		assertEquals(expecting, found);
	}

	public String toNodesOnlyString(TreeNodeStream nodes) {
        TreeAdaptor adaptor = nodes.getTreeAdaptor();
		StringBuffer buf = new StringBuffer();
        Object o = nodes.LT(1);
        int type = adaptor.getType(o);
        while ( o!=null && type!=Token.EOF ) {
			if ( !(type==Token.DOWN||type==Token.UP) ) {
				buf.append(" ");
				buf.append(type);
			}
            nodes.consume();
            o = nodes.LT(1);
            type = adaptor.getType(o);
		}
		return buf.toString();
	}
}