1 /* 2 * [The "BSD license"] 3 * Copyright (c) 2010 Terence Parr 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. The name of the author may not be used to endorse or promote products 15 * derived from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 package org.antlr.test; 29 30 import org.antlr.runtime.CommonToken; 31 import org.antlr.runtime.Token; 32 import org.antlr.runtime.tree.*; 33 import org.junit.Test; 34 35 import static org.junit.Assert.*; 36 37 /** Test the tree node stream. */ 38 public class TestTreeNodeStream extends BaseTest { 39 40 /** Build new stream; let's us override to test other streams. */ newStream(Object t)41 public TreeNodeStream newStream(Object t) { 42 return new CommonTreeNodeStream(t); 43 } 44 toTokenTypeString(TreeNodeStream stream)45 public String toTokenTypeString(TreeNodeStream stream) { 46 return ((CommonTreeNodeStream)stream).toTokenTypeString(); 47 } 48 testSingleNode()49 @Test public void testSingleNode() throws Exception { 50 Tree t = new CommonTree(new CommonToken(101)); 51 52 TreeNodeStream stream = newStream(t); 53 String expecting = " 101"; 54 String found = toNodesOnlyString(stream); 55 assertEquals(expecting, found); 56 57 expecting = " 101"; 58 found = toTokenTypeString(stream); 59 assertEquals(expecting, found); 60 } 61 test4Nodes()62 @Test public void test4Nodes() throws Exception { 63 // ^(101 ^(102 103) 104) 64 Tree t = new CommonTree(new CommonToken(101)); 65 t.addChild(new CommonTree(new CommonToken(102))); 66 t.getChild(0).addChild(new CommonTree(new CommonToken(103))); 67 t.addChild(new CommonTree(new CommonToken(104))); 68 69 TreeNodeStream stream = newStream(t); 70 String expecting = " 101 102 103 104"; 71 String found = toNodesOnlyString(stream); 72 assertEquals(expecting, found); 73 74 expecting = " 101 2 102 2 103 3 104 3"; 75 found = toTokenTypeString(stream); 76 assertEquals(expecting, found); 77 } 78 testList()79 @Test public void testList() throws Exception { 80 Tree root = new CommonTree((Token)null); 81 82 Tree t = new CommonTree(new CommonToken(101)); 83 t.addChild(new CommonTree(new CommonToken(102))); 84 t.getChild(0).addChild(new CommonTree(new CommonToken(103))); 85 t.addChild(new CommonTree(new CommonToken(104))); 86 87 Tree u = new CommonTree(new CommonToken(105)); 88 89 root.addChild(t); 90 root.addChild(u); 91 92 TreeNodeStream stream = newStream(root); 93 String expecting = " 101 102 103 104 105"; 94 String found = toNodesOnlyString(stream); 95 assertEquals(expecting, found); 96 97 expecting = " 101 2 102 2 103 3 104 3 105"; 98 found = toTokenTypeString(stream); 99 assertEquals(expecting, found); 100 } 101 testFlatList()102 @Test public void testFlatList() throws Exception { 103 Tree root = new CommonTree((Token)null); 104 105 root.addChild(new CommonTree(new CommonToken(101))); 106 root.addChild(new CommonTree(new CommonToken(102))); 107 root.addChild(new CommonTree(new CommonToken(103))); 108 109 TreeNodeStream stream = newStream(root); 110 String expecting = " 101 102 103"; 111 String found = toNodesOnlyString(stream); 112 assertEquals(expecting, found); 113 114 expecting = " 101 102 103"; 115 found = toTokenTypeString(stream); 116 assertEquals(expecting, found); 117 } 118 testListWithOneNode()119 @Test public void testListWithOneNode() throws Exception { 120 Tree root = new CommonTree((Token)null); 121 122 root.addChild(new CommonTree(new CommonToken(101))); 123 124 TreeNodeStream stream = newStream(root); 125 String expecting = " 101"; 126 String found = toNodesOnlyString(stream); 127 assertEquals(expecting, found); 128 129 expecting = " 101"; 130 found = toTokenTypeString(stream); 131 assertEquals(expecting, found); 132 } 133 testAoverB()134 @Test public void testAoverB() throws Exception { 135 Tree t = new CommonTree(new CommonToken(101)); 136 t.addChild(new CommonTree(new CommonToken(102))); 137 138 TreeNodeStream stream = newStream(t); 139 String expecting = " 101 102"; 140 String found = toNodesOnlyString(stream); 141 assertEquals(expecting, found); 142 143 expecting = " 101 2 102 3"; 144 found = toTokenTypeString(stream); 145 assertEquals(expecting, found); 146 } 147 testLT()148 @Test public void testLT() throws Exception { 149 // ^(101 ^(102 103) 104) 150 Tree t = new CommonTree(new CommonToken(101)); 151 t.addChild(new CommonTree(new CommonToken(102))); 152 t.getChild(0).addChild(new CommonTree(new CommonToken(103))); 153 t.addChild(new CommonTree(new CommonToken(104))); 154 155 TreeNodeStream stream = newStream(t); 156 assertEquals(101, ((Tree)stream.LT(1)).getType()); 157 assertEquals(Token.DOWN, ((Tree)stream.LT(2)).getType()); 158 assertEquals(102, ((Tree)stream.LT(3)).getType()); 159 assertEquals(Token.DOWN, ((Tree)stream.LT(4)).getType()); 160 assertEquals(103, ((Tree)stream.LT(5)).getType()); 161 assertEquals(Token.UP, ((Tree)stream.LT(6)).getType()); 162 assertEquals(104, ((Tree)stream.LT(7)).getType()); 163 assertEquals(Token.UP, ((Tree)stream.LT(8)).getType()); 164 assertEquals(Token.EOF, ((Tree)stream.LT(9)).getType()); 165 // check way ahead 166 assertEquals(Token.EOF, ((Tree)stream.LT(100)).getType()); 167 } 168 testMarkRewindEntire()169 @Test public void testMarkRewindEntire() throws Exception { 170 // ^(101 ^(102 103 ^(106 107) ) 104 105) 171 // stream has 7 real + 6 nav nodes 172 // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF 173 Tree r0 = new CommonTree(new CommonToken(101)); 174 Tree r1 = new CommonTree(new CommonToken(102)); 175 r0.addChild(r1); 176 r1.addChild(new CommonTree(new CommonToken(103))); 177 Tree r2 = new CommonTree(new CommonToken(106)); 178 r2.addChild(new CommonTree(new CommonToken(107))); 179 r1.addChild(r2); 180 r0.addChild(new CommonTree(new CommonToken(104))); 181 r0.addChild(new CommonTree(new CommonToken(105))); 182 183 TreeNodeStream stream = newStream(r0); 184 int m = stream.mark(); // MARK 185 for (int k=1; k<=13; k++) { // consume til end 186 stream.LT(1); 187 stream.consume(); 188 } 189 assertEquals(Token.EOF, ((Tree)stream.LT(1)).getType()); 190 stream.rewind(m); // REWIND 191 192 // consume til end again :) 193 for (int k=1; k<=13; k++) { // consume til end 194 stream.LT(1); 195 stream.consume(); 196 } 197 assertEquals(Token.EOF, ((Tree)stream.LT(1)).getType()); 198 } 199 testMarkRewindInMiddle()200 @Test public void testMarkRewindInMiddle() throws Exception { 201 // ^(101 ^(102 103 ^(106 107) ) 104 105) 202 // stream has 7 real + 6 nav nodes 203 // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF 204 Tree r0 = new CommonTree(new CommonToken(101)); 205 Tree r1 = new CommonTree(new CommonToken(102)); 206 r0.addChild(r1); 207 r1.addChild(new CommonTree(new CommonToken(103))); 208 Tree r2 = new CommonTree(new CommonToken(106)); 209 r2.addChild(new CommonTree(new CommonToken(107))); 210 r1.addChild(r2); 211 r0.addChild(new CommonTree(new CommonToken(104))); 212 r0.addChild(new CommonTree(new CommonToken(105))); 213 214 TreeNodeStream stream = newStream(r0); 215 for (int k=1; k<=7; k++) { // consume til middle 216 //System.out.println(((Tree)stream.LT(1)).getType()); 217 stream.consume(); 218 } 219 assertEquals(107, ((Tree)stream.LT(1)).getType()); 220 stream.mark(); // MARK 221 stream.consume(); // consume 107 222 stream.consume(); // consume UP 223 stream.consume(); // consume UP 224 stream.consume(); // consume 104 225 stream.rewind(); // REWIND 226 stream.mark(); // keep saving nodes though 227 228 assertEquals(107, ((Tree)stream.LT(1)).getType()); 229 stream.consume(); 230 assertEquals(Token.UP, ((Tree)stream.LT(1)).getType()); 231 stream.consume(); 232 assertEquals(Token.UP, ((Tree)stream.LT(1)).getType()); 233 stream.consume(); 234 assertEquals(104, ((Tree)stream.LT(1)).getType()); 235 stream.consume(); 236 // now we're past rewind position 237 assertEquals(105, ((Tree)stream.LT(1)).getType()); 238 stream.consume(); 239 assertEquals(Token.UP, ((Tree)stream.LT(1)).getType()); 240 stream.consume(); 241 assertEquals(Token.EOF, ((Tree)stream.LT(1)).getType()); 242 assertEquals(Token.UP, ((Tree)stream.LT(-1)).getType()); 243 } 244 testMarkRewindNested()245 @Test public void testMarkRewindNested() throws Exception { 246 // ^(101 ^(102 103 ^(106 107) ) 104 105) 247 // stream has 7 real + 6 nav nodes 248 // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF 249 Tree r0 = new CommonTree(new CommonToken(101)); 250 Tree r1 = new CommonTree(new CommonToken(102)); 251 r0.addChild(r1); 252 r1.addChild(new CommonTree(new CommonToken(103))); 253 Tree r2 = new CommonTree(new CommonToken(106)); 254 r2.addChild(new CommonTree(new CommonToken(107))); 255 r1.addChild(r2); 256 r0.addChild(new CommonTree(new CommonToken(104))); 257 r0.addChild(new CommonTree(new CommonToken(105))); 258 259 TreeNodeStream stream = newStream(r0); 260 int m = stream.mark(); // MARK at start 261 stream.consume(); // consume 101 262 stream.consume(); // consume DN 263 int m2 = stream.mark(); // MARK on 102 264 stream.consume(); // consume 102 265 stream.consume(); // consume DN 266 stream.consume(); // consume 103 267 stream.consume(); // consume 106 268 stream.rewind(m2); // REWIND to 102 269 assertEquals(102, ((Tree)stream.LT(1)).getType()); 270 stream.consume(); 271 assertEquals(Token.DOWN, ((Tree)stream.LT(1)).getType()); 272 stream.consume(); 273 // stop at 103 and rewind to start 274 stream.rewind(m); // REWIND to 101 275 assertEquals(101, ((Tree)stream.LT(1)).getType()); 276 stream.consume(); 277 assertEquals(Token.DOWN, ((Tree)stream.LT(1)).getType()); 278 stream.consume(); 279 assertEquals(102, ((Tree)stream.LT(1)).getType()); 280 stream.consume(); 281 assertEquals(Token.DOWN, ((Tree)stream.LT(1)).getType()); 282 } 283 testSeekFromStart()284 @Test public void testSeekFromStart() throws Exception { 285 // ^(101 ^(102 103 ^(106 107) ) 104 105) 286 // stream has 7 real + 6 nav nodes 287 // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF 288 Tree r0 = new CommonTree(new CommonToken(101)); 289 Tree r1 = new CommonTree(new CommonToken(102)); 290 r0.addChild(r1); 291 r1.addChild(new CommonTree(new CommonToken(103))); 292 Tree r2 = new CommonTree(new CommonToken(106)); 293 r2.addChild(new CommonTree(new CommonToken(107))); 294 r1.addChild(r2); 295 r0.addChild(new CommonTree(new CommonToken(104))); 296 r0.addChild(new CommonTree(new CommonToken(105))); 297 298 TreeNodeStream stream = newStream(r0); 299 stream.seek(7); // seek to 107 300 assertEquals(107, ((Tree)stream.LT(1)).getType()); 301 stream.consume(); // consume 107 302 stream.consume(); // consume UP 303 stream.consume(); // consume UP 304 assertEquals(104, ((Tree)stream.LT(1)).getType()); 305 } 306 testReset()307 @Test public void testReset() throws Exception { 308 // ^(101 ^(102 103 ^(106 107) ) 104 105) 309 // stream has 7 real + 6 nav nodes 310 // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF 311 Tree r0 = new CommonTree(new CommonToken(101)); 312 Tree r1 = new CommonTree(new CommonToken(102)); 313 r0.addChild(r1); 314 r1.addChild(new CommonTree(new CommonToken(103))); 315 Tree r2 = new CommonTree(new CommonToken(106)); 316 r2.addChild(new CommonTree(new CommonToken(107))); 317 r1.addChild(r2); 318 r0.addChild(new CommonTree(new CommonToken(104))); 319 r0.addChild(new CommonTree(new CommonToken(105))); 320 321 TreeNodeStream stream = newStream(r0); 322 String v = toNodesOnlyString(stream); // scan all 323 stream.reset(); 324 String v2 = toNodesOnlyString(stream); // scan all 325 assertEquals(v, v2); 326 } 327 testDeepTree()328 @Test public void testDeepTree() throws Exception { 329 // ^(10 100 101 ^(20 ^(30 40 (50 (60 70)))) (80 90))) 330 // stream has 8 real + 10 nav nodes 331 int n = 9; 332 CommonTree[] nodes = new CommonTree[n]; 333 for (int i=0; i< n; i++) { 334 nodes[i] = new CommonTree(new CommonToken((i+1)*10)); 335 } 336 Tree g = nodes[0]; 337 Tree rules = nodes[1]; 338 Tree rule1 = nodes[2]; 339 Tree id = nodes[3]; 340 Tree block = nodes[4]; 341 Tree alt = nodes[5]; 342 Tree s = nodes[6]; 343 Tree rule2 = nodes[7]; 344 Tree id2 = nodes[8]; 345 g.addChild(new CommonTree(new CommonToken(100))); 346 g.addChild(new CommonTree(new CommonToken(101))); 347 g.addChild(rules); 348 rules.addChild(rule1); 349 rule1.addChild(id); 350 rule1.addChild(block); 351 block.addChild(alt); 352 alt.addChild(s); 353 rules.addChild(rule2); 354 rule2.addChild(id2); 355 356 TreeNodeStream stream = newStream(g); 357 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"; 358 String found = toTokenTypeString(stream); 359 assertEquals(expecting, found); 360 } 361 toNodesOnlyString(TreeNodeStream nodes)362 public String toNodesOnlyString(TreeNodeStream nodes) { 363 TreeAdaptor adaptor = nodes.getTreeAdaptor(); 364 StringBuilder buf = new StringBuilder(); 365 Object o = nodes.LT(1); 366 int type = adaptor.getType(o); 367 while ( o!=null && type!=Token.EOF ) { 368 if ( !(type==Token.DOWN||type==Token.UP) ) { 369 buf.append(" "); 370 buf.append(type); 371 } 372 nodes.consume(); 373 o = nodes.LT(1); 374 type = adaptor.getType(o); 375 } 376 return buf.toString(); 377 } 378 } 379