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 */ 28package org.antlr.test; 29 30import org.antlr.runtime.CommonToken; 31import org.antlr.runtime.Token; 32import org.antlr.runtime.tree.*; 33import org.junit.Test; 34 35/** Test the tree node stream. */ 36public class TestTreeNodeStream extends BaseTest { 37 38 /** Build new stream; let's us override to test other streams. */ 39 public TreeNodeStream newStream(Object t) { 40 return new CommonTreeNodeStream(t); 41 } 42 43 public String toTokenTypeString(TreeNodeStream stream) { 44 return ((CommonTreeNodeStream)stream).toTokenTypeString(); 45 } 46 47 @Test public void testSingleNode() throws Exception { 48 Tree t = new CommonTree(new CommonToken(101)); 49 50 TreeNodeStream stream = newStream(t); 51 String expecting = " 101"; 52 String found = toNodesOnlyString(stream); 53 assertEquals(expecting, found); 54 55 expecting = " 101"; 56 found = toTokenTypeString(stream); 57 assertEquals(expecting, found); 58 } 59 60 @Test public void test4Nodes() throws Exception { 61 // ^(101 ^(102 103) 104) 62 Tree t = new CommonTree(new CommonToken(101)); 63 t.addChild(new CommonTree(new CommonToken(102))); 64 t.getChild(0).addChild(new CommonTree(new CommonToken(103))); 65 t.addChild(new CommonTree(new CommonToken(104))); 66 67 TreeNodeStream stream = newStream(t); 68 String expecting = " 101 102 103 104"; 69 String found = toNodesOnlyString(stream); 70 assertEquals(expecting, found); 71 72 expecting = " 101 2 102 2 103 3 104 3"; 73 found = toTokenTypeString(stream); 74 assertEquals(expecting, found); 75 } 76 77 @Test public void testList() throws Exception { 78 Tree root = new CommonTree((Token)null); 79 80 Tree t = new CommonTree(new CommonToken(101)); 81 t.addChild(new CommonTree(new CommonToken(102))); 82 t.getChild(0).addChild(new CommonTree(new CommonToken(103))); 83 t.addChild(new CommonTree(new CommonToken(104))); 84 85 Tree u = new CommonTree(new CommonToken(105)); 86 87 root.addChild(t); 88 root.addChild(u); 89 90 TreeNodeStream stream = newStream(root); 91 String expecting = " 101 102 103 104 105"; 92 String found = toNodesOnlyString(stream); 93 assertEquals(expecting, found); 94 95 expecting = " 101 2 102 2 103 3 104 3 105"; 96 found = toTokenTypeString(stream); 97 assertEquals(expecting, found); 98 } 99 100 @Test public void testFlatList() throws Exception { 101 Tree root = new CommonTree((Token)null); 102 103 root.addChild(new CommonTree(new CommonToken(101))); 104 root.addChild(new CommonTree(new CommonToken(102))); 105 root.addChild(new CommonTree(new CommonToken(103))); 106 107 TreeNodeStream stream = newStream(root); 108 String expecting = " 101 102 103"; 109 String found = toNodesOnlyString(stream); 110 assertEquals(expecting, found); 111 112 expecting = " 101 102 103"; 113 found = toTokenTypeString(stream); 114 assertEquals(expecting, found); 115 } 116 117 @Test public void testListWithOneNode() throws Exception { 118 Tree root = new CommonTree((Token)null); 119 120 root.addChild(new CommonTree(new CommonToken(101))); 121 122 TreeNodeStream stream = newStream(root); 123 String expecting = " 101"; 124 String found = toNodesOnlyString(stream); 125 assertEquals(expecting, found); 126 127 expecting = " 101"; 128 found = toTokenTypeString(stream); 129 assertEquals(expecting, found); 130 } 131 132 @Test public void testAoverB() throws Exception { 133 Tree t = new CommonTree(new CommonToken(101)); 134 t.addChild(new CommonTree(new CommonToken(102))); 135 136 TreeNodeStream stream = newStream(t); 137 String expecting = " 101 102"; 138 String found = toNodesOnlyString(stream); 139 assertEquals(expecting, found); 140 141 expecting = " 101 2 102 3"; 142 found = toTokenTypeString(stream); 143 assertEquals(expecting, found); 144 } 145 146 @Test public void testLT() throws Exception { 147 // ^(101 ^(102 103) 104) 148 Tree t = new CommonTree(new CommonToken(101)); 149 t.addChild(new CommonTree(new CommonToken(102))); 150 t.getChild(0).addChild(new CommonTree(new CommonToken(103))); 151 t.addChild(new CommonTree(new CommonToken(104))); 152 153 TreeNodeStream stream = newStream(t); 154 assertEquals(101, ((Tree)stream.LT(1)).getType()); 155 assertEquals(Token.DOWN, ((Tree)stream.LT(2)).getType()); 156 assertEquals(102, ((Tree)stream.LT(3)).getType()); 157 assertEquals(Token.DOWN, ((Tree)stream.LT(4)).getType()); 158 assertEquals(103, ((Tree)stream.LT(5)).getType()); 159 assertEquals(Token.UP, ((Tree)stream.LT(6)).getType()); 160 assertEquals(104, ((Tree)stream.LT(7)).getType()); 161 assertEquals(Token.UP, ((Tree)stream.LT(8)).getType()); 162 assertEquals(Token.EOF, ((Tree)stream.LT(9)).getType()); 163 // check way ahead 164 assertEquals(Token.EOF, ((Tree)stream.LT(100)).getType()); 165 } 166 167 @Test public void testMarkRewindEntire() throws Exception { 168 // ^(101 ^(102 103 ^(106 107) ) 104 105) 169 // stream has 7 real + 6 nav nodes 170 // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF 171 Tree r0 = new CommonTree(new CommonToken(101)); 172 Tree r1 = new CommonTree(new CommonToken(102)); 173 r0.addChild(r1); 174 r1.addChild(new CommonTree(new CommonToken(103))); 175 Tree r2 = new CommonTree(new CommonToken(106)); 176 r2.addChild(new CommonTree(new CommonToken(107))); 177 r1.addChild(r2); 178 r0.addChild(new CommonTree(new CommonToken(104))); 179 r0.addChild(new CommonTree(new CommonToken(105))); 180 181 TreeNodeStream stream = newStream(r0); 182 int m = stream.mark(); // MARK 183 for (int k=1; k<=13; k++) { // consume til end 184 stream.LT(1); 185 stream.consume(); 186 } 187 assertEquals(Token.EOF, ((Tree)stream.LT(1)).getType()); 188 stream.rewind(m); // REWIND 189 190 // consume til end again :) 191 for (int k=1; k<=13; k++) { // consume til end 192 stream.LT(1); 193 stream.consume(); 194 } 195 assertEquals(Token.EOF, ((Tree)stream.LT(1)).getType()); 196 } 197 198 @Test public void testMarkRewindInMiddle() throws Exception { 199 // ^(101 ^(102 103 ^(106 107) ) 104 105) 200 // stream has 7 real + 6 nav nodes 201 // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF 202 Tree r0 = new CommonTree(new CommonToken(101)); 203 Tree r1 = new CommonTree(new CommonToken(102)); 204 r0.addChild(r1); 205 r1.addChild(new CommonTree(new CommonToken(103))); 206 Tree r2 = new CommonTree(new CommonToken(106)); 207 r2.addChild(new CommonTree(new CommonToken(107))); 208 r1.addChild(r2); 209 r0.addChild(new CommonTree(new CommonToken(104))); 210 r0.addChild(new CommonTree(new CommonToken(105))); 211 212 TreeNodeStream stream = newStream(r0); 213 for (int k=1; k<=7; k++) { // consume til middle 214 //System.out.println(((Tree)stream.LT(1)).getType()); 215 stream.consume(); 216 } 217 assertEquals(107, ((Tree)stream.LT(1)).getType()); 218 stream.mark(); // MARK 219 stream.consume(); // consume 107 220 stream.consume(); // consume UP 221 stream.consume(); // consume UP 222 stream.consume(); // consume 104 223 stream.rewind(); // REWIND 224 stream.mark(); // keep saving nodes though 225 226 assertEquals(107, ((Tree)stream.LT(1)).getType()); 227 stream.consume(); 228 assertEquals(Token.UP, ((Tree)stream.LT(1)).getType()); 229 stream.consume(); 230 assertEquals(Token.UP, ((Tree)stream.LT(1)).getType()); 231 stream.consume(); 232 assertEquals(104, ((Tree)stream.LT(1)).getType()); 233 stream.consume(); 234 // now we're past rewind position 235 assertEquals(105, ((Tree)stream.LT(1)).getType()); 236 stream.consume(); 237 assertEquals(Token.UP, ((Tree)stream.LT(1)).getType()); 238 stream.consume(); 239 assertEquals(Token.EOF, ((Tree)stream.LT(1)).getType()); 240 assertEquals(Token.UP, ((Tree)stream.LT(-1)).getType()); 241 } 242 243 @Test public void testMarkRewindNested() throws Exception { 244 // ^(101 ^(102 103 ^(106 107) ) 104 105) 245 // stream has 7 real + 6 nav nodes 246 // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF 247 Tree r0 = new CommonTree(new CommonToken(101)); 248 Tree r1 = new CommonTree(new CommonToken(102)); 249 r0.addChild(r1); 250 r1.addChild(new CommonTree(new CommonToken(103))); 251 Tree r2 = new CommonTree(new CommonToken(106)); 252 r2.addChild(new CommonTree(new CommonToken(107))); 253 r1.addChild(r2); 254 r0.addChild(new CommonTree(new CommonToken(104))); 255 r0.addChild(new CommonTree(new CommonToken(105))); 256 257 TreeNodeStream stream = newStream(r0); 258 int m = stream.mark(); // MARK at start 259 stream.consume(); // consume 101 260 stream.consume(); // consume DN 261 int m2 = stream.mark(); // MARK on 102 262 stream.consume(); // consume 102 263 stream.consume(); // consume DN 264 stream.consume(); // consume 103 265 stream.consume(); // consume 106 266 stream.rewind(m2); // REWIND to 102 267 assertEquals(102, ((Tree)stream.LT(1)).getType()); 268 stream.consume(); 269 assertEquals(Token.DOWN, ((Tree)stream.LT(1)).getType()); 270 stream.consume(); 271 // stop at 103 and rewind to start 272 stream.rewind(m); // REWIND to 101 273 assertEquals(101, ((Tree)stream.LT(1)).getType()); 274 stream.consume(); 275 assertEquals(Token.DOWN, ((Tree)stream.LT(1)).getType()); 276 stream.consume(); 277 assertEquals(102, ((Tree)stream.LT(1)).getType()); 278 stream.consume(); 279 assertEquals(Token.DOWN, ((Tree)stream.LT(1)).getType()); 280 } 281 282 @Test public void testSeekFromStart() throws Exception { 283 // ^(101 ^(102 103 ^(106 107) ) 104 105) 284 // stream has 7 real + 6 nav nodes 285 // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF 286 Tree r0 = new CommonTree(new CommonToken(101)); 287 Tree r1 = new CommonTree(new CommonToken(102)); 288 r0.addChild(r1); 289 r1.addChild(new CommonTree(new CommonToken(103))); 290 Tree r2 = new CommonTree(new CommonToken(106)); 291 r2.addChild(new CommonTree(new CommonToken(107))); 292 r1.addChild(r2); 293 r0.addChild(new CommonTree(new CommonToken(104))); 294 r0.addChild(new CommonTree(new CommonToken(105))); 295 296 TreeNodeStream stream = newStream(r0); 297 stream.seek(7); // seek to 107 298 assertEquals(107, ((Tree)stream.LT(1)).getType()); 299 stream.consume(); // consume 107 300 stream.consume(); // consume UP 301 stream.consume(); // consume UP 302 assertEquals(104, ((Tree)stream.LT(1)).getType()); 303 } 304 305 @Test public void testReset() throws Exception { 306 // ^(101 ^(102 103 ^(106 107) ) 104 105) 307 // stream has 7 real + 6 nav nodes 308 // Sequence of types: 101 DN 102 DN 103 106 DN 107 UP UP 104 105 UP EOF 309 Tree r0 = new CommonTree(new CommonToken(101)); 310 Tree r1 = new CommonTree(new CommonToken(102)); 311 r0.addChild(r1); 312 r1.addChild(new CommonTree(new CommonToken(103))); 313 Tree r2 = new CommonTree(new CommonToken(106)); 314 r2.addChild(new CommonTree(new CommonToken(107))); 315 r1.addChild(r2); 316 r0.addChild(new CommonTree(new CommonToken(104))); 317 r0.addChild(new CommonTree(new CommonToken(105))); 318 319 TreeNodeStream stream = newStream(r0); 320 String v = toNodesOnlyString(stream); // scan all 321 stream.reset(); 322 String v2 = toNodesOnlyString(stream); // scan all 323 assertEquals(v, v2); 324 } 325 326 @Test public void testDeepTree() throws Exception { 327 // ^(10 100 101 ^(20 ^(30 40 (50 (60 70)))) (80 90))) 328 // stream has 8 real + 10 nav nodes 329 int n = 9; 330 CommonTree[] nodes = new CommonTree[n]; 331 for (int i=0; i< n; i++) { 332 nodes[i] = new CommonTree(new CommonToken((i+1)*10)); 333 } 334 Tree g = nodes[0]; 335 Tree rules = nodes[1]; 336 Tree rule1 = nodes[2]; 337 Tree id = nodes[3]; 338 Tree block = nodes[4]; 339 Tree alt = nodes[5]; 340 Tree s = nodes[6]; 341 Tree rule2 = nodes[7]; 342 Tree id2 = nodes[8]; 343 g.addChild(new CommonTree(new CommonToken(100))); 344 g.addChild(new CommonTree(new CommonToken(101))); 345 g.addChild(rules); 346 rules.addChild(rule1); 347 rule1.addChild(id); 348 rule1.addChild(block); 349 block.addChild(alt); 350 alt.addChild(s); 351 rules.addChild(rule2); 352 rule2.addChild(id2); 353 354 TreeNodeStream stream = newStream(g); 355 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"; 356 String found = toTokenTypeString(stream); 357 assertEquals(expecting, found); 358 } 359 360 public String toNodesOnlyString(TreeNodeStream nodes) { 361 TreeAdaptor adaptor = nodes.getTreeAdaptor(); 362 StringBuffer buf = new StringBuffer(); 363 Object o = nodes.LT(1); 364 int type = adaptor.getType(o); 365 while ( o!=null && type!=Token.EOF ) { 366 if ( !(type==Token.DOWN||type==Token.UP) ) { 367 buf.append(" "); 368 buf.append(type); 369 } 370 nodes.consume(); 371 o = nodes.LT(1); 372 type = adaptor.getType(o); 373 } 374 return buf.toString(); 375 } 376} 377