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.CommonTree; 33import org.antlr.runtime.tree.CommonTreeAdaptor; 34import org.antlr.runtime.tree.Tree; 35import org.antlr.runtime.tree.TreeAdaptor; 36import org.junit.Test; 37 38public class TestTrees extends BaseTest { 39 TreeAdaptor adaptor = new CommonTreeAdaptor(); 40 protected boolean debug = false; 41 42 static class V extends CommonTree { 43 public int x; 44 public V(Token t) { this.token = t;} 45 public V(int ttype, int x) { this.x=x; token=new CommonToken(ttype); } 46 public V(int ttype, Token t, int x) { token=t; this.x=x;} 47 public String toString() { return (token!=null?token.getText():"")+"<V>";} 48 } 49 50 @Test public void testSingleNode() throws Exception { 51 CommonTree t = new CommonTree(new CommonToken(101)); 52 assertNull(t.parent); 53 assertEquals(-1, t.childIndex); 54 } 55 56 @Test public void testTwoChildrenOfNilRoot() throws Exception { 57 CommonTree root_0 = (CommonTree)adaptor.nil(); 58 CommonTree t = new V(101, 2); 59 CommonTree u = new V(new CommonToken(102,"102")); 60 adaptor.addChild(root_0, t); 61 adaptor.addChild(root_0, u); 62 assertNull(root_0.parent); 63 assertEquals(-1, root_0.childIndex); 64 assertEquals(0, t.childIndex); 65 assertEquals(1, u.childIndex); 66 } 67 68 @Test public void test4Nodes() throws Exception { 69 // ^(101 ^(102 103) 104) 70 CommonTree r0 = new CommonTree(new CommonToken(101)); 71 r0.addChild(new CommonTree(new CommonToken(102))); 72 r0.getChild(0).addChild(new CommonTree(new CommonToken(103))); 73 r0.addChild(new CommonTree(new CommonToken(104))); 74 75 assertNull(r0.parent); 76 assertEquals(-1, r0.childIndex); 77 } 78 79 @Test public void testList() throws Exception { 80 // ^(nil 101 102 103) 81 CommonTree r0 = new CommonTree((Token)null); 82 CommonTree c0, c1, c2; 83 r0.addChild(c0=new CommonTree(new CommonToken(101))); 84 r0.addChild(c1=new CommonTree(new CommonToken(102))); 85 r0.addChild(c2=new CommonTree(new CommonToken(103))); 86 87 assertNull(r0.parent); 88 assertEquals(-1, r0.childIndex); 89 assertEquals(r0, c0.parent); 90 assertEquals(0, c0.childIndex); 91 assertEquals(r0, c1.parent); 92 assertEquals(1, c1.childIndex); 93 assertEquals(r0, c2.parent); 94 assertEquals(2, c2.childIndex); 95 } 96 97 @Test public void testList2() throws Exception { 98 // Add child ^(nil 101 102 103) to root 5 99 // should pull 101 102 103 directly to become 5's child list 100 CommonTree root = new CommonTree(new CommonToken(5)); 101 102 // child tree 103 CommonTree r0 = new CommonTree((Token)null); 104 CommonTree c0, c1, c2; 105 r0.addChild(c0=new CommonTree(new CommonToken(101))); 106 r0.addChild(c1=new CommonTree(new CommonToken(102))); 107 r0.addChild(c2=new CommonTree(new CommonToken(103))); 108 109 root.addChild(r0); 110 111 assertNull(root.parent); 112 assertEquals(-1, root.childIndex); 113 // check children of root all point at root 114 assertEquals(root, c0.parent); 115 assertEquals(0, c0.childIndex); 116 assertEquals(root, c0.parent); 117 assertEquals(1, c1.childIndex); 118 assertEquals(root, c0.parent); 119 assertEquals(2, c2.childIndex); 120 } 121 122 @Test public void testAddListToExistChildren() throws Exception { 123 // Add child ^(nil 101 102 103) to root ^(5 6) 124 // should add 101 102 103 to end of 5's child list 125 CommonTree root = new CommonTree(new CommonToken(5)); 126 root.addChild(new CommonTree(new CommonToken(6))); 127 128 // child tree 129 CommonTree r0 = new CommonTree((Token)null); 130 CommonTree c0, c1, c2; 131 r0.addChild(c0=new CommonTree(new CommonToken(101))); 132 r0.addChild(c1=new CommonTree(new CommonToken(102))); 133 r0.addChild(c2=new CommonTree(new CommonToken(103))); 134 135 root.addChild(r0); 136 137 assertNull(root.parent); 138 assertEquals(-1, root.childIndex); 139 // check children of root all point at root 140 assertEquals(root, c0.parent); 141 assertEquals(1, c0.childIndex); 142 assertEquals(root, c0.parent); 143 assertEquals(2, c1.childIndex); 144 assertEquals(root, c0.parent); 145 assertEquals(3, c2.childIndex); 146 } 147 148 @Test public void testDupTree() throws Exception { 149 // ^(101 ^(102 103 ^(106 107) ) 104 105) 150 CommonTree r0 = new CommonTree(new CommonToken(101)); 151 CommonTree r1 = new CommonTree(new CommonToken(102)); 152 r0.addChild(r1); 153 r1.addChild(new CommonTree(new CommonToken(103))); 154 Tree r2 = new CommonTree(new CommonToken(106)); 155 r2.addChild(new CommonTree(new CommonToken(107))); 156 r1.addChild(r2); 157 r0.addChild(new CommonTree(new CommonToken(104))); 158 r0.addChild(new CommonTree(new CommonToken(105))); 159 160 CommonTree dup = (CommonTree)(new CommonTreeAdaptor()).dupTree(r0); 161 162 assertNull(dup.parent); 163 assertEquals(-1, dup.childIndex); 164 dup.sanityCheckParentAndChildIndexes(); 165 } 166 167 @Test public void testBecomeRoot() throws Exception { 168 // 5 becomes new root of ^(nil 101 102 103) 169 CommonTree newRoot = new CommonTree(new CommonToken(5)); 170 171 CommonTree oldRoot = new CommonTree((Token)null); 172 oldRoot.addChild(new CommonTree(new CommonToken(101))); 173 oldRoot.addChild(new CommonTree(new CommonToken(102))); 174 oldRoot.addChild(new CommonTree(new CommonToken(103))); 175 176 TreeAdaptor adaptor = new CommonTreeAdaptor(); 177 adaptor.becomeRoot(newRoot, oldRoot); 178 newRoot.sanityCheckParentAndChildIndexes(); 179 } 180 181 @Test public void testBecomeRoot2() throws Exception { 182 // 5 becomes new root of ^(101 102 103) 183 CommonTree newRoot = new CommonTree(new CommonToken(5)); 184 185 CommonTree oldRoot = new CommonTree(new CommonToken(101)); 186 oldRoot.addChild(new CommonTree(new CommonToken(102))); 187 oldRoot.addChild(new CommonTree(new CommonToken(103))); 188 189 TreeAdaptor adaptor = new CommonTreeAdaptor(); 190 adaptor.becomeRoot(newRoot, oldRoot); 191 newRoot.sanityCheckParentAndChildIndexes(); 192 } 193 194 @Test public void testBecomeRoot3() throws Exception { 195 // ^(nil 5) becomes new root of ^(nil 101 102 103) 196 CommonTree newRoot = new CommonTree((Token)null); 197 newRoot.addChild(new CommonTree(new CommonToken(5))); 198 199 CommonTree oldRoot = new CommonTree((Token)null); 200 oldRoot.addChild(new CommonTree(new CommonToken(101))); 201 oldRoot.addChild(new CommonTree(new CommonToken(102))); 202 oldRoot.addChild(new CommonTree(new CommonToken(103))); 203 204 TreeAdaptor adaptor = new CommonTreeAdaptor(); 205 adaptor.becomeRoot(newRoot, oldRoot); 206 newRoot.sanityCheckParentAndChildIndexes(); 207 } 208 209 @Test public void testBecomeRoot5() throws Exception { 210 // ^(nil 5) becomes new root of ^(101 102 103) 211 CommonTree newRoot = new CommonTree((Token)null); 212 newRoot.addChild(new CommonTree(new CommonToken(5))); 213 214 CommonTree oldRoot = new CommonTree(new CommonToken(101)); 215 oldRoot.addChild(new CommonTree(new CommonToken(102))); 216 oldRoot.addChild(new CommonTree(new CommonToken(103))); 217 218 TreeAdaptor adaptor = new CommonTreeAdaptor(); 219 adaptor.becomeRoot(newRoot, oldRoot); 220 newRoot.sanityCheckParentAndChildIndexes(); 221 } 222 223 @Test public void testBecomeRoot6() throws Exception { 224 // emulates construction of ^(5 6) 225 CommonTree root_0 = (CommonTree)adaptor.nil(); 226 CommonTree root_1 = (CommonTree)adaptor.nil(); 227 root_1 = (CommonTree)adaptor.becomeRoot(new CommonTree(new CommonToken(5)), root_1); 228 229 adaptor.addChild(root_1, new CommonTree(new CommonToken(6))); 230 231 adaptor.addChild(root_0, root_1); 232 233 root_0.sanityCheckParentAndChildIndexes(); 234 } 235 236 // Test replaceChildren 237 238 @Test public void testReplaceWithNoChildren() throws Exception { 239 CommonTree t = new CommonTree(new CommonToken(101)); 240 CommonTree newChild = new CommonTree(new CommonToken(5)); 241 boolean error = false; 242 try { 243 t.replaceChildren(0, 0, newChild); 244 } 245 catch (IllegalArgumentException iae) { 246 error = true; 247 } 248 assertTrue(error); 249 } 250 251 @Test public void testReplaceWithOneChildren() throws Exception { 252 // assume token type 99 and use text 253 CommonTree t = new CommonTree(new CommonToken(99,"a")); 254 CommonTree c0 = new CommonTree(new CommonToken(99, "b")); 255 t.addChild(c0); 256 257 CommonTree newChild = new CommonTree(new CommonToken(99, "c")); 258 t.replaceChildren(0, 0, newChild); 259 String expecting = "(a c)"; 260 assertEquals(expecting, t.toStringTree()); 261 t.sanityCheckParentAndChildIndexes(); 262 } 263 264 @Test public void testReplaceInMiddle() throws Exception { 265 CommonTree t = new CommonTree(new CommonToken(99, "a")); 266 t.addChild(new CommonTree(new CommonToken(99, "b"))); 267 t.addChild(new CommonTree(new CommonToken(99, "c"))); // index 1 268 t.addChild(new CommonTree(new CommonToken(99, "d"))); 269 270 CommonTree newChild = new CommonTree(new CommonToken(99,"x")); 271 t.replaceChildren(1, 1, newChild); 272 String expecting = "(a b x d)"; 273 assertEquals(expecting, t.toStringTree()); 274 t.sanityCheckParentAndChildIndexes(); 275 } 276 277 @Test public void testReplaceAtLeft() throws Exception { 278 CommonTree t = new CommonTree(new CommonToken(99, "a")); 279 t.addChild(new CommonTree(new CommonToken(99, "b"))); // index 0 280 t.addChild(new CommonTree(new CommonToken(99, "c"))); 281 t.addChild(new CommonTree(new CommonToken(99, "d"))); 282 283 CommonTree newChild = new CommonTree(new CommonToken(99,"x")); 284 t.replaceChildren(0, 0, newChild); 285 String expecting = "(a x c d)"; 286 assertEquals(expecting, t.toStringTree()); 287 t.sanityCheckParentAndChildIndexes(); 288 } 289 290 @Test public void testReplaceAtRight() throws Exception { 291 CommonTree t = new CommonTree(new CommonToken(99, "a")); 292 t.addChild(new CommonTree(new CommonToken(99, "b"))); 293 t.addChild(new CommonTree(new CommonToken(99, "c"))); 294 t.addChild(new CommonTree(new CommonToken(99, "d"))); // index 2 295 296 CommonTree newChild = new CommonTree(new CommonToken(99,"x")); 297 t.replaceChildren(2, 2, newChild); 298 String expecting = "(a b c x)"; 299 assertEquals(expecting, t.toStringTree()); 300 t.sanityCheckParentAndChildIndexes(); 301 } 302 303 @Test public void testReplaceOneWithTwoAtLeft() throws Exception { 304 CommonTree t = new CommonTree(new CommonToken(99, "a")); 305 t.addChild(new CommonTree(new CommonToken(99, "b"))); 306 t.addChild(new CommonTree(new CommonToken(99, "c"))); 307 t.addChild(new CommonTree(new CommonToken(99, "d"))); 308 309 CommonTree newChildren = (CommonTree)adaptor.nil(); 310 newChildren.addChild(new CommonTree(new CommonToken(99,"x"))); 311 newChildren.addChild(new CommonTree(new CommonToken(99,"y"))); 312 313 t.replaceChildren(0, 0, newChildren); 314 String expecting = "(a x y c d)"; 315 assertEquals(expecting, t.toStringTree()); 316 t.sanityCheckParentAndChildIndexes(); 317 } 318 319 @Test public void testReplaceOneWithTwoAtRight() throws Exception { 320 CommonTree t = new CommonTree(new CommonToken(99, "a")); 321 t.addChild(new CommonTree(new CommonToken(99, "b"))); 322 t.addChild(new CommonTree(new CommonToken(99, "c"))); 323 t.addChild(new CommonTree(new CommonToken(99, "d"))); 324 325 CommonTree newChildren = (CommonTree)adaptor.nil(); 326 newChildren.addChild(new CommonTree(new CommonToken(99,"x"))); 327 newChildren.addChild(new CommonTree(new CommonToken(99,"y"))); 328 329 t.replaceChildren(2, 2, newChildren); 330 String expecting = "(a b c x y)"; 331 assertEquals(expecting, t.toStringTree()); 332 t.sanityCheckParentAndChildIndexes(); 333 } 334 335 @Test public void testReplaceOneWithTwoInMiddle() throws Exception { 336 CommonTree t = new CommonTree(new CommonToken(99, "a")); 337 t.addChild(new CommonTree(new CommonToken(99, "b"))); 338 t.addChild(new CommonTree(new CommonToken(99, "c"))); 339 t.addChild(new CommonTree(new CommonToken(99, "d"))); 340 341 CommonTree newChildren = (CommonTree)adaptor.nil(); 342 newChildren.addChild(new CommonTree(new CommonToken(99,"x"))); 343 newChildren.addChild(new CommonTree(new CommonToken(99,"y"))); 344 345 t.replaceChildren(1, 1, newChildren); 346 String expecting = "(a b x y d)"; 347 assertEquals(expecting, t.toStringTree()); 348 t.sanityCheckParentAndChildIndexes(); 349 } 350 351 @Test public void testReplaceTwoWithOneAtLeft() throws Exception { 352 CommonTree t = new CommonTree(new CommonToken(99, "a")); 353 t.addChild(new CommonTree(new CommonToken(99, "b"))); 354 t.addChild(new CommonTree(new CommonToken(99, "c"))); 355 t.addChild(new CommonTree(new CommonToken(99, "d"))); 356 357 CommonTree newChild = new CommonTree(new CommonToken(99,"x")); 358 359 t.replaceChildren(0, 1, newChild); 360 String expecting = "(a x d)"; 361 assertEquals(expecting, t.toStringTree()); 362 t.sanityCheckParentAndChildIndexes(); 363 } 364 365 @Test public void testReplaceTwoWithOneAtRight() throws Exception { 366 CommonTree t = new CommonTree(new CommonToken(99, "a")); 367 t.addChild(new CommonTree(new CommonToken(99, "b"))); 368 t.addChild(new CommonTree(new CommonToken(99, "c"))); 369 t.addChild(new CommonTree(new CommonToken(99, "d"))); 370 371 CommonTree newChild = new CommonTree(new CommonToken(99,"x")); 372 373 t.replaceChildren(1, 2, newChild); 374 String expecting = "(a b x)"; 375 assertEquals(expecting, t.toStringTree()); 376 t.sanityCheckParentAndChildIndexes(); 377 } 378 379 @Test public void testReplaceAllWithOne() throws Exception { 380 CommonTree t = new CommonTree(new CommonToken(99, "a")); 381 t.addChild(new CommonTree(new CommonToken(99, "b"))); 382 t.addChild(new CommonTree(new CommonToken(99, "c"))); 383 t.addChild(new CommonTree(new CommonToken(99, "d"))); 384 385 CommonTree newChild = new CommonTree(new CommonToken(99,"x")); 386 387 t.replaceChildren(0, 2, newChild); 388 String expecting = "(a x)"; 389 assertEquals(expecting, t.toStringTree()); 390 t.sanityCheckParentAndChildIndexes(); 391 } 392 393 @Test public void testReplaceAllWithTwo() throws Exception { 394 CommonTree t = new CommonTree(new CommonToken(99, "a")); 395 t.addChild(new CommonTree(new CommonToken(99, "b"))); 396 t.addChild(new CommonTree(new CommonToken(99, "c"))); 397 t.addChild(new CommonTree(new CommonToken(99, "d"))); 398 399 CommonTree newChildren = (CommonTree)adaptor.nil(); 400 newChildren.addChild(new CommonTree(new CommonToken(99,"x"))); 401 newChildren.addChild(new CommonTree(new CommonToken(99,"y"))); 402 403 t.replaceChildren(0, 2, newChildren); 404 String expecting = "(a x y)"; 405 assertEquals(expecting, t.toStringTree()); 406 t.sanityCheckParentAndChildIndexes(); 407 } 408} 409