1 /* 2 [The "BSD licence"] 3 Copyright (c) 2005-2007 Kunle Odutola 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 13 the documentation and/or other materials provided with the 14 distribution. 15 3. The name of the author may not be used to endorse or promote products 16 derived from this software without specific prior WRITTEN permission. 17 4. Unless explicitly state otherwise, any contribution intentionally 18 submitted for inclusion in this work to the copyright owner or licensor 19 shall be under the terms and conditions of this license, without any 20 additional terms or conditions. 21 22 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 23 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 24 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 25 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 26 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 27 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 31 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34 35 namespace Antlr.Runtime.Tests 36 { 37 using System; 38 using StringBuilder = System.Text.StringBuilder; 39 40 using IToken = Antlr.Runtime.IToken; 41 using CommonToken = Antlr.Runtime.CommonToken; 42 using ITree = Antlr.Runtime.Tree.ITree; 43 using ITreeAdaptor = Antlr.Runtime.Tree.ITreeAdaptor; 44 using CommonTree = Antlr.Runtime.Tree.CommonTree; 45 using CommonTreeAdaptor = Antlr.Runtime.Tree.CommonTreeAdaptor; 46 47 using MbUnit.Framework; 48 49 [TestFixture] 50 public class ITreeFixture : TestFixtureBase 51 { 52 #region CommonTree Tests 53 54 [Test] 55 public void testSingleNode() 56 { 57 CommonTree t = new CommonTree(new CommonToken(101)); 58 Assert.IsNull(t.Parent); 59 Assert.AreEqual(-1, t.ChildIndex); 60 } 61 62 [Test] 63 public void test4Nodes() 64 { 65 // ^(101 ^(102 103) 104) 66 CommonTree r0 = new CommonTree(new CommonToken(101)); 67 r0.AddChild(new CommonTree(new CommonToken(102))); 68 r0.GetChild(0).AddChild(new CommonTree(new CommonToken(103))); 69 r0.AddChild(new CommonTree(new CommonToken(104))); 70 71 Assert.IsNull(r0.Parent); 72 Assert.AreEqual(-1, r0.ChildIndex); 73 } 74 75 [Test] 76 public void testList() 77 { 78 // ^(nil 101 102 103) 79 CommonTree r0 = new CommonTree((IToken)null); 80 CommonTree c0, c1, c2; 81 r0.AddChild(c0 = new CommonTree(new CommonToken(101))); 82 r0.AddChild(c1 = new CommonTree(new CommonToken(102))); 83 r0.AddChild(c2 = new CommonTree(new CommonToken(103))); 84 85 Assert.IsNull(r0.Parent); 86 Assert.AreEqual(-1, r0.ChildIndex); 87 Assert.AreEqual(r0, c0.Parent); 88 Assert.AreEqual(0, c0.ChildIndex); 89 Assert.AreEqual(r0, c1.Parent); 90 Assert.AreEqual(1, c1.ChildIndex); 91 Assert.AreEqual(r0, c2.Parent); 92 Assert.AreEqual(2, c2.ChildIndex); 93 } 94 95 [Test] 96 public void testList2() 97 { 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((IToken)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 Assert.IsNull(root.Parent); 112 Assert.AreEqual(-1, root.ChildIndex); 113 // check children of root all point at root 114 Assert.AreEqual(root, c0.Parent); 115 Assert.AreEqual(0, c0.ChildIndex); 116 Assert.AreEqual(root, c0.Parent); 117 Assert.AreEqual(1, c1.ChildIndex); 118 Assert.AreEqual(root, c0.Parent); 119 Assert.AreEqual(2, c2.ChildIndex); 120 } 121 122 [Test] 123 public void testAddListToExistChildren() 124 { 125 // Add child ^(nil 101 102 103) to root ^(5 6) 126 // should add 101 102 103 to end of 5's child list 127 CommonTree root = new CommonTree(new CommonToken(5)); 128 root.AddChild(new CommonTree(new CommonToken(6))); 129 130 // child tree 131 CommonTree r0 = new CommonTree((IToken)null); 132 CommonTree c0, c1, c2; 133 r0.AddChild(c0 = new CommonTree(new CommonToken(101))); 134 r0.AddChild(c1 = new CommonTree(new CommonToken(102))); 135 r0.AddChild(c2 = new CommonTree(new CommonToken(103))); 136 137 root.AddChild(r0); 138 139 Assert.IsNull(root.Parent); 140 Assert.AreEqual(-1, root.ChildIndex); 141 // check children of root all point at root 142 Assert.AreEqual(root, c0.Parent); 143 Assert.AreEqual(1, c0.ChildIndex); 144 Assert.AreEqual(root, c0.Parent); 145 Assert.AreEqual(2, c1.ChildIndex); 146 Assert.AreEqual(root, c0.Parent); 147 Assert.AreEqual(3, c2.ChildIndex); 148 } 149 150 [Test] 151 public void testDupTree() 152 { 153 // ^(101 ^(102 103 ^(106 107) ) 104 105) 154 CommonTree r0 = new CommonTree(new CommonToken(101)); 155 CommonTree r1 = new CommonTree(new CommonToken(102)); 156 r0.AddChild(r1); 157 r1.AddChild(new CommonTree(new CommonToken(103))); 158 ITree r2 = new CommonTree(new CommonToken(106)); 159 r2.AddChild(new CommonTree(new CommonToken(107))); 160 r1.AddChild(r2); 161 r0.AddChild(new CommonTree(new CommonToken(104))); 162 r0.AddChild(new CommonTree(new CommonToken(105))); 163 164 CommonTree dup = (CommonTree)(new CommonTreeAdaptor()).DupTree(r0); 165 166 Assert.IsNull(dup.Parent); 167 Assert.AreEqual(-1, dup.ChildIndex); 168 dup.SanityCheckParentAndChildIndexes(); 169 } 170 171 [Test] 172 public void testBecomeRoot() 173 { 174 // 5 becomes new root of ^(nil 101 102 103) 175 CommonTree newRoot = new CommonTree(new CommonToken(5)); 176 177 CommonTree oldRoot = new CommonTree((IToken)null); 178 oldRoot.AddChild(new CommonTree(new CommonToken(101))); 179 oldRoot.AddChild(new CommonTree(new CommonToken(102))); 180 oldRoot.AddChild(new CommonTree(new CommonToken(103))); 181 182 ITreeAdaptor adaptor = new CommonTreeAdaptor(); 183 adaptor.BecomeRoot(newRoot, oldRoot); 184 newRoot.SanityCheckParentAndChildIndexes(); 185 } 186 187 [Test] 188 public void testBecomeRoot2() 189 { 190 // 5 becomes new root of ^(101 102 103) 191 CommonTree newRoot = new CommonTree(new CommonToken(5)); 192 193 CommonTree oldRoot = new CommonTree(new CommonToken(101)); 194 oldRoot.AddChild(new CommonTree(new CommonToken(102))); 195 oldRoot.AddChild(new CommonTree(new CommonToken(103))); 196 197 ITreeAdaptor adaptor = new CommonTreeAdaptor(); 198 adaptor.BecomeRoot(newRoot, oldRoot); 199 newRoot.SanityCheckParentAndChildIndexes(); 200 } 201 202 [Test] 203 public void testBecomeRoot3() 204 { 205 // ^(nil 5) becomes new root of ^(nil 101 102 103) 206 CommonTree newRoot = new CommonTree((IToken)null); 207 newRoot.AddChild(new CommonTree(new CommonToken(5))); 208 209 CommonTree oldRoot = new CommonTree((IToken)null); 210 oldRoot.AddChild(new CommonTree(new CommonToken(101))); 211 oldRoot.AddChild(new CommonTree(new CommonToken(102))); 212 oldRoot.AddChild(new CommonTree(new CommonToken(103))); 213 214 ITreeAdaptor adaptor = new CommonTreeAdaptor(); 215 adaptor.BecomeRoot(newRoot, oldRoot); 216 newRoot.SanityCheckParentAndChildIndexes(); 217 } 218 219 [Test] 220 public void testBecomeRoot5() 221 { 222 // ^(nil 5) becomes new root of ^(101 102 103) 223 CommonTree newRoot = new CommonTree((IToken)null); 224 newRoot.AddChild(new CommonTree(new CommonToken(5))); 225 226 CommonTree oldRoot = new CommonTree(new CommonToken(101)); 227 oldRoot.AddChild(new CommonTree(new CommonToken(102))); 228 oldRoot.AddChild(new CommonTree(new CommonToken(103))); 229 230 ITreeAdaptor adaptor = new CommonTreeAdaptor(); 231 adaptor.BecomeRoot(newRoot, oldRoot); 232 newRoot.SanityCheckParentAndChildIndexes(); 233 } 234 235 [Test] 236 public void testBecomeRoot6() 237 { 238 // emulates construction of ^(5 6) 239 ITreeAdaptor adaptor = new CommonTreeAdaptor(); 240 CommonTree root_0 = (CommonTree)adaptor.Nil(); 241 CommonTree root_1 = (CommonTree)adaptor.Nil(); 242 root_1 = (CommonTree)adaptor.BecomeRoot(new CommonTree(new CommonToken(5)), root_1); 243 244 adaptor.AddChild(root_1, new CommonTree(new CommonToken(6))); 245 246 adaptor.AddChild(root_0, root_1); 247 248 root_0.SanityCheckParentAndChildIndexes(); 249 } 250 251 // Test replaceChildren 252 253 [Test] 254 public void testReplaceWithNoChildren() 255 { 256 CommonTree t = new CommonTree(new CommonToken(101)); 257 CommonTree newChild = new CommonTree(new CommonToken(5)); 258 bool error = false; 259 try 260 { 261 t.ReplaceChildren(0, 0, newChild); 262 } 263 catch (Exception) 264 { 265 error = true; 266 } 267 Assert.IsTrue(error); 268 } 269 270 [Test] 271 public void testReplaceWithOneChildren() 272 { 273 // assume token type 99 and use text 274 CommonTree t = new CommonTree(new CommonToken(99, "a")); 275 CommonTree c0 = new CommonTree(new CommonToken(99, "b")); 276 t.AddChild(c0); 277 278 CommonTree newChild = new CommonTree(new CommonToken(99, "c")); 279 t.ReplaceChildren(0, 0, newChild); 280 String expected = "(a c)"; 281 Assert.AreEqual(expected, t.ToStringTree()); 282 t.SanityCheckParentAndChildIndexes(); 283 } 284 285 [Test] 286 public void testReplaceInMiddle() 287 { 288 CommonTree t = new CommonTree(new CommonToken(99, "a")); 289 t.AddChild(new CommonTree(new CommonToken(99, "b"))); 290 t.AddChild(new CommonTree(new CommonToken(99, "c"))); // index 1 291 t.AddChild(new CommonTree(new CommonToken(99, "d"))); 292 293 CommonTree newChild = new CommonTree(new CommonToken(99, "x")); 294 t.ReplaceChildren(1, 1, newChild); 295 String expected = "(a b x d)"; 296 Assert.AreEqual(expected, t.ToStringTree()); 297 t.SanityCheckParentAndChildIndexes(); 298 } 299 300 [Test] 301 public void testReplaceAtLeft() 302 { 303 CommonTree t = new CommonTree(new CommonToken(99, "a")); 304 t.AddChild(new CommonTree(new CommonToken(99, "b"))); // index 0 305 t.AddChild(new CommonTree(new CommonToken(99, "c"))); 306 t.AddChild(new CommonTree(new CommonToken(99, "d"))); 307 308 CommonTree newChild = new CommonTree(new CommonToken(99, "x")); 309 t.ReplaceChildren(0, 0, newChild); 310 String expected = "(a x c d)"; 311 Assert.AreEqual(expected, t.ToStringTree()); 312 t.SanityCheckParentAndChildIndexes(); 313 } 314 315 [Test] 316 public void testReplaceAtRight() 317 { 318 CommonTree t = new CommonTree(new CommonToken(99, "a")); 319 t.AddChild(new CommonTree(new CommonToken(99, "b"))); 320 t.AddChild(new CommonTree(new CommonToken(99, "c"))); 321 t.AddChild(new CommonTree(new CommonToken(99, "d"))); // index 2 322 323 CommonTree newChild = new CommonTree(new CommonToken(99, "x")); 324 t.ReplaceChildren(2, 2, newChild); 325 String expected = "(a b c x)"; 326 Assert.AreEqual(expected, t.ToStringTree()); 327 t.SanityCheckParentAndChildIndexes(); 328 } 329 330 [Test] 331 public void testReplaceOneWithTwoAtLeft() 332 { 333 ITreeAdaptor adaptor = new CommonTreeAdaptor(); 334 CommonTree t = new CommonTree(new CommonToken(99, "a")); 335 t.AddChild(new CommonTree(new CommonToken(99, "b"))); 336 t.AddChild(new CommonTree(new CommonToken(99, "c"))); 337 t.AddChild(new CommonTree(new CommonToken(99, "d"))); 338 339 CommonTree newChildren = (CommonTree)adaptor.Nil(); 340 newChildren.AddChild(new CommonTree(new CommonToken(99, "x"))); 341 newChildren.AddChild(new CommonTree(new CommonToken(99, "y"))); 342 343 t.ReplaceChildren(0, 0, newChildren); 344 String expected = "(a x y c d)"; 345 Assert.AreEqual(expected, t.ToStringTree()); 346 t.SanityCheckParentAndChildIndexes(); 347 } 348 349 [Test] 350 public void testReplaceOneWithTwoAtRight() 351 { 352 ITreeAdaptor adaptor = new CommonTreeAdaptor(); 353 CommonTree t = new CommonTree(new CommonToken(99, "a")); 354 t.AddChild(new CommonTree(new CommonToken(99, "b"))); 355 t.AddChild(new CommonTree(new CommonToken(99, "c"))); 356 t.AddChild(new CommonTree(new CommonToken(99, "d"))); 357 358 CommonTree newChildren = (CommonTree)adaptor.Nil(); 359 newChildren.AddChild(new CommonTree(new CommonToken(99, "x"))); 360 newChildren.AddChild(new CommonTree(new CommonToken(99, "y"))); 361 362 t.ReplaceChildren(2, 2, newChildren); 363 String expected = "(a b c x y)"; 364 Assert.AreEqual(expected, t.ToStringTree()); 365 t.SanityCheckParentAndChildIndexes(); 366 } 367 368 [Test] 369 public void testReplaceOneWithTwoInMiddle() 370 { 371 ITreeAdaptor adaptor = new CommonTreeAdaptor(); 372 CommonTree t = new CommonTree(new CommonToken(99, "a")); 373 t.AddChild(new CommonTree(new CommonToken(99, "b"))); 374 t.AddChild(new CommonTree(new CommonToken(99, "c"))); 375 t.AddChild(new CommonTree(new CommonToken(99, "d"))); 376 377 CommonTree newChildren = (CommonTree)adaptor.Nil(); 378 newChildren.AddChild(new CommonTree(new CommonToken(99, "x"))); 379 newChildren.AddChild(new CommonTree(new CommonToken(99, "y"))); 380 381 t.ReplaceChildren(1, 1, newChildren); 382 String expected = "(a b x y d)"; 383 Assert.AreEqual(expected, t.ToStringTree()); 384 t.SanityCheckParentAndChildIndexes(); 385 } 386 387 [Test] 388 public void testReplaceTwoWithOneAtLeft() 389 { 390 CommonTree t = new CommonTree(new CommonToken(99, "a")); 391 t.AddChild(new CommonTree(new CommonToken(99, "b"))); 392 t.AddChild(new CommonTree(new CommonToken(99, "c"))); 393 t.AddChild(new CommonTree(new CommonToken(99, "d"))); 394 395 CommonTree newChild = new CommonTree(new CommonToken(99, "x")); 396 397 t.ReplaceChildren(0, 1, newChild); 398 String expected = "(a x d)"; 399 Assert.AreEqual(expected, t.ToStringTree()); 400 t.SanityCheckParentAndChildIndexes(); 401 } 402 403 [Test] 404 public void testReplaceTwoWithOneAtRight() 405 { 406 CommonTree t = new CommonTree(new CommonToken(99, "a")); 407 t.AddChild(new CommonTree(new CommonToken(99, "b"))); 408 t.AddChild(new CommonTree(new CommonToken(99, "c"))); 409 t.AddChild(new CommonTree(new CommonToken(99, "d"))); 410 411 CommonTree newChild = new CommonTree(new CommonToken(99, "x")); 412 413 t.ReplaceChildren(1, 2, newChild); 414 String expected = "(a b x)"; 415 Assert.AreEqual(expected, t.ToStringTree()); 416 t.SanityCheckParentAndChildIndexes(); 417 } 418 419 [Test] 420 public void testReplaceAllWithOne() 421 { 422 CommonTree t = new CommonTree(new CommonToken(99, "a")); 423 t.AddChild(new CommonTree(new CommonToken(99, "b"))); 424 t.AddChild(new CommonTree(new CommonToken(99, "c"))); 425 t.AddChild(new CommonTree(new CommonToken(99, "d"))); 426 427 CommonTree newChild = new CommonTree(new CommonToken(99, "x")); 428 429 t.ReplaceChildren(0, 2, newChild); 430 String expected = "(a x)"; 431 Assert.AreEqual(expected, t.ToStringTree()); 432 t.SanityCheckParentAndChildIndexes(); 433 } 434 435 [Test] 436 public void testReplaceAllWithTwo() 437 { 438 ITreeAdaptor adaptor = new CommonTreeAdaptor(); 439 CommonTree t = new CommonTree(new CommonToken(99, "a")); 440 t.AddChild(new CommonTree(new CommonToken(99, "b"))); 441 t.AddChild(new CommonTree(new CommonToken(99, "c"))); 442 t.AddChild(new CommonTree(new CommonToken(99, "d"))); 443 444 CommonTree newChildren = (CommonTree)adaptor.Nil(); 445 newChildren.AddChild(new CommonTree(new CommonToken(99, "x"))); 446 newChildren.AddChild(new CommonTree(new CommonToken(99, "y"))); 447 448 t.ReplaceChildren(0, 2, newChildren); 449 String expected = "(a x y)"; 450 Assert.AreEqual(expected, t.ToStringTree()); 451 t.SanityCheckParentAndChildIndexes(); 452 } 453 454 #endregion 455 } 456 }
