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.tree.CommonTree; 31 import org.antlr.runtime.tree.CommonTreeAdaptor; 32 import org.antlr.runtime.tree.TreeAdaptor; 33 import org.antlr.runtime.tree.TreeWizard; 34 import org.junit.Test; 35 36 import java.util.ArrayList; 37 import java.util.HashMap; 38 import java.util.List; 39 import java.util.Map; 40 41 42 public class TestTreeWizard extends BaseTest { 43 protected static final String[] tokens = 44 new String[] {"", "", "", "", "", "A", "B", "C", "D", "E", "ID", "VAR"}; 45 protected static final TreeAdaptor adaptor = new CommonTreeAdaptor(); 46 testSingleNode()47 @Test public void testSingleNode() throws Exception { 48 TreeWizard wiz = new TreeWizard(adaptor, tokens); 49 CommonTree t = (CommonTree)wiz.create("ID"); 50 String found = t.toStringTree(); 51 String expecting = "ID"; 52 assertEquals(expecting, found); 53 } 54 testSingleNodeWithArg()55 @Test public void testSingleNodeWithArg() throws Exception { 56 TreeWizard wiz = new TreeWizard(adaptor, tokens); 57 CommonTree t = (CommonTree)wiz.create("ID[foo]"); 58 String found = t.toStringTree(); 59 String expecting = "foo"; 60 assertEquals(expecting, found); 61 } 62 testSingleNodeTree()63 @Test public void testSingleNodeTree() throws Exception { 64 TreeWizard wiz = new TreeWizard(adaptor, tokens); 65 CommonTree t = (CommonTree)wiz.create("(A)"); 66 String found = t.toStringTree(); 67 String expecting = "A"; 68 assertEquals(expecting, found); 69 } 70 testSingleLevelTree()71 @Test public void testSingleLevelTree() throws Exception { 72 TreeWizard wiz = new TreeWizard(adaptor, tokens); 73 CommonTree t = (CommonTree)wiz.create("(A B C D)"); 74 String found = t.toStringTree(); 75 String expecting = "(A B C D)"; 76 assertEquals(expecting, found); 77 } 78 testListTree()79 @Test public void testListTree() throws Exception { 80 TreeWizard wiz = new TreeWizard(adaptor, tokens); 81 CommonTree t = (CommonTree)wiz.create("(nil A B C)"); 82 String found = t.toStringTree(); 83 String expecting = "A B C"; 84 assertEquals(expecting, found); 85 } 86 testInvalidListTree()87 @Test public void testInvalidListTree() throws Exception { 88 TreeWizard wiz = new TreeWizard(adaptor, tokens); 89 CommonTree t = (CommonTree)wiz.create("A B C"); 90 assertTrue(t==null); 91 } 92 testDoubleLevelTree()93 @Test public void testDoubleLevelTree() throws Exception { 94 TreeWizard wiz = new TreeWizard(adaptor, tokens); 95 CommonTree t = (CommonTree)wiz.create("(A (B C) (B D) E)"); 96 String found = t.toStringTree(); 97 String expecting = "(A (B C) (B D) E)"; 98 assertEquals(expecting, found); 99 } 100 testSingleNodeIndex()101 @Test public void testSingleNodeIndex() throws Exception { 102 TreeWizard wiz = new TreeWizard(adaptor, tokens); 103 CommonTree t = (CommonTree)wiz.create("ID"); 104 Map m = wiz.index(t); 105 String found = m.toString(); 106 String expecting = "{10=[ID]}"; 107 assertEquals(expecting, found); 108 } 109 testNoRepeatsIndex()110 @Test public void testNoRepeatsIndex() throws Exception { 111 TreeWizard wiz = new TreeWizard(adaptor, tokens); 112 CommonTree t = (CommonTree)wiz.create("(A B C D)"); 113 Map m = wiz.index(t); 114 String found = sortMapToString(m); 115 String expecting = "{5=[A], 6=[B], 7=[C], 8=[D]}"; 116 assertEquals(expecting, found); 117 } 118 testRepeatsIndex()119 @Test public void testRepeatsIndex() throws Exception { 120 TreeWizard wiz = new TreeWizard(adaptor, tokens); 121 CommonTree t = (CommonTree)wiz.create("(A B (A C B) B D D)"); 122 Map m = wiz.index(t); 123 String found = sortMapToString(m); 124 String expecting = "{5=[A, A], 6=[B, B, B], 7=[C], 8=[D, D]}"; 125 assertEquals(expecting, found); 126 } 127 testNoRepeatsVisit()128 @Test public void testNoRepeatsVisit() throws Exception { 129 TreeWizard wiz = new TreeWizard(adaptor, tokens); 130 CommonTree t = (CommonTree)wiz.create("(A B C D)"); 131 final List elements = new ArrayList(); 132 wiz.visit(t, wiz.getTokenType("B"), new TreeWizard.Visitor() { 133 public void visit(Object t) { 134 elements.add(t); 135 } 136 }); 137 String found = elements.toString(); 138 String expecting = "[B]"; 139 assertEquals(expecting, found); 140 } 141 testNoRepeatsVisit2()142 @Test public void testNoRepeatsVisit2() throws Exception { 143 TreeWizard wiz = new TreeWizard(adaptor, tokens); 144 CommonTree t = (CommonTree)wiz.create("(A B (A C B) B D D)"); 145 final List elements = new ArrayList(); 146 wiz.visit(t, wiz.getTokenType("C"), 147 new TreeWizard.Visitor() { 148 public void visit(Object t) { 149 elements.add(t); 150 } 151 }); 152 String found = elements.toString(); 153 String expecting = "[C]"; 154 assertEquals(expecting, found); 155 } 156 testRepeatsVisit()157 @Test public void testRepeatsVisit() throws Exception { 158 TreeWizard wiz = new TreeWizard(adaptor, tokens); 159 CommonTree t = (CommonTree)wiz.create("(A B (A C B) B D D)"); 160 final List elements = new ArrayList(); 161 wiz.visit(t, wiz.getTokenType("B"), 162 new TreeWizard.Visitor() { 163 public void visit(Object t) { 164 elements.add(t); 165 } 166 }); 167 String found = elements.toString(); 168 String expecting = "[B, B, B]"; 169 assertEquals(expecting, found); 170 } 171 testRepeatsVisit2()172 @Test public void testRepeatsVisit2() throws Exception { 173 TreeWizard wiz = new TreeWizard(adaptor, tokens); 174 CommonTree t = (CommonTree)wiz.create("(A B (A C B) B D D)"); 175 final List elements = new ArrayList(); 176 wiz.visit(t, wiz.getTokenType("A"), 177 new TreeWizard.Visitor() { 178 public void visit(Object t) { 179 elements.add(t); 180 } 181 }); 182 String found = elements.toString(); 183 String expecting = "[A, A]"; 184 assertEquals(expecting, found); 185 } 186 testRepeatsVisitWithContext()187 @Test public void testRepeatsVisitWithContext() throws Exception { 188 TreeWizard wiz = new TreeWizard(adaptor, tokens); 189 CommonTree t = (CommonTree)wiz.create("(A B (A C B) B D D)"); 190 final List elements = new ArrayList(); 191 wiz.visit(t, wiz.getTokenType("B"), 192 new TreeWizard.ContextVisitor() { 193 public void visit(Object t, Object parent, int childIndex, Map labels) { 194 elements.add(adaptor.getText(t)+"@"+ 195 (parent!=null?adaptor.getText(parent):"nil")+ 196 "["+childIndex+"]"); 197 } 198 }); 199 String found = elements.toString(); 200 String expecting = "[B@A[0], B@A[1], B@A[2]]"; 201 assertEquals(expecting, found); 202 } 203 testRepeatsVisitWithNullParentAndContext()204 @Test public void testRepeatsVisitWithNullParentAndContext() throws Exception { 205 TreeWizard wiz = new TreeWizard(adaptor, tokens); 206 CommonTree t = (CommonTree)wiz.create("(A B (A C B) B D D)"); 207 final List elements = new ArrayList(); 208 wiz.visit(t, wiz.getTokenType("A"), 209 new TreeWizard.ContextVisitor() { 210 public void visit(Object t, Object parent, int childIndex, Map labels) { 211 elements.add(adaptor.getText(t)+"@"+ 212 (parent!=null?adaptor.getText(parent):"nil")+ 213 "["+childIndex+"]"); 214 } 215 }); 216 String found = elements.toString(); 217 String expecting = "[A@nil[0], A@A[1]]"; 218 assertEquals(expecting, found); 219 } 220 testVisitPattern()221 @Test public void testVisitPattern() throws Exception { 222 TreeWizard wiz = new TreeWizard(adaptor, tokens); 223 CommonTree t = (CommonTree)wiz.create("(A B C (A B) D)"); 224 final List elements = new ArrayList(); 225 wiz.visit(t, "(A B)", 226 new TreeWizard.Visitor() { 227 public void visit(Object t) { 228 elements.add(t); 229 } 230 }); 231 String found = elements.toString(); 232 String expecting = "[A]"; // shouldn't match overall root, just (A B) 233 assertEquals(expecting, found); 234 } 235 testVisitPatternMultiple()236 @Test public void testVisitPatternMultiple() throws Exception { 237 TreeWizard wiz = new TreeWizard(adaptor, tokens); 238 CommonTree t = (CommonTree)wiz.create("(A B C (A B) (D (A B)))"); 239 final List elements = new ArrayList(); 240 wiz.visit(t, "(A B)", 241 new TreeWizard.ContextVisitor() { 242 public void visit(Object t, Object parent, int childIndex, Map labels) { 243 elements.add(adaptor.getText(t)+"@"+ 244 (parent!=null?adaptor.getText(parent):"nil")+ 245 "["+childIndex+"]"); 246 } 247 }); 248 String found = elements.toString(); 249 String expecting = "[A@A[2], A@D[0]]"; // shouldn't match overall root, just (A B) 250 assertEquals(expecting, found); 251 } 252 testVisitPatternMultipleWithLabels()253 @Test public void testVisitPatternMultipleWithLabels() throws Exception { 254 TreeWizard wiz = new TreeWizard(adaptor, tokens); 255 CommonTree t = (CommonTree)wiz.create("(A B C (A[foo] B[bar]) (D (A[big] B[dog])))"); 256 final List elements = new ArrayList(); 257 wiz.visit(t, "(%a:A %b:B)", 258 new TreeWizard.ContextVisitor() { 259 public void visit(Object t, Object parent, int childIndex, Map labels) { 260 elements.add(adaptor.getText(t)+"@"+ 261 (parent!=null?adaptor.getText(parent):"nil")+ 262 "["+childIndex+"]"+labels.get("a")+"&"+labels.get("b")); 263 } 264 }); 265 String found = elements.toString(); 266 String expecting = "[foo@A[2]foo&bar, big@D[0]big&dog]"; 267 assertEquals(expecting, found); 268 } 269 testParse()270 @Test public void testParse() throws Exception { 271 TreeWizard wiz = new TreeWizard(adaptor, tokens); 272 CommonTree t = (CommonTree)wiz.create("(A B C)"); 273 boolean valid = wiz.parse(t, "(A B C)"); 274 assertTrue(valid); 275 } 276 testParseSingleNode()277 @Test public void testParseSingleNode() throws Exception { 278 TreeWizard wiz = new TreeWizard(adaptor, tokens); 279 CommonTree t = (CommonTree)wiz.create("A"); 280 boolean valid = wiz.parse(t, "A"); 281 assertTrue(valid); 282 } 283 testParseFlatTree()284 @Test public void testParseFlatTree() throws Exception { 285 TreeWizard wiz = new TreeWizard(adaptor, tokens); 286 CommonTree t = (CommonTree)wiz.create("(nil A B C)"); 287 boolean valid = wiz.parse(t, "(nil A B C)"); 288 assertTrue(valid); 289 } 290 testWildcard()291 @Test public void testWildcard() throws Exception { 292 TreeWizard wiz = new TreeWizard(adaptor, tokens); 293 CommonTree t = (CommonTree)wiz.create("(A B C)"); 294 boolean valid = wiz.parse(t, "(A . .)"); 295 assertTrue(valid); 296 } 297 testParseWithText()298 @Test public void testParseWithText() throws Exception { 299 TreeWizard wiz = new TreeWizard(adaptor, tokens); 300 CommonTree t = (CommonTree)wiz.create("(A B[foo] C[bar])"); 301 // C pattern has no text arg so despite [bar] in t, no need 302 // to match text--check structure only. 303 boolean valid = wiz.parse(t, "(A B[foo] C)"); 304 assertTrue(valid); 305 } 306 testParseWithText2()307 @Test public void testParseWithText2() throws Exception { 308 TreeWizard wiz = new TreeWizard(adaptor, tokens); 309 CommonTree t = (CommonTree)wiz.create("(A B[T__32] (C (D E[a])))"); 310 // C pattern has no text arg so despite [bar] in t, no need 311 // to match text--check structure only. 312 boolean valid = wiz.parse(t, "(A B[foo] C)"); 313 assertEquals("(A T__32 (C (D a)))", t.toStringTree()); 314 } 315 testParseWithTextFails()316 @Test public void testParseWithTextFails() throws Exception { 317 TreeWizard wiz = new TreeWizard(adaptor, tokens); 318 CommonTree t = (CommonTree)wiz.create("(A B C)"); 319 boolean valid = wiz.parse(t, "(A[foo] B C)"); 320 assertTrue(!valid); // fails 321 } 322 testParseLabels()323 @Test public void testParseLabels() throws Exception { 324 TreeWizard wiz = new TreeWizard(adaptor, tokens); 325 CommonTree t = (CommonTree)wiz.create("(A B C)"); 326 Map labels = new HashMap(); 327 boolean valid = wiz.parse(t, "(%a:A %b:B %c:C)", labels); 328 assertTrue(valid); 329 assertEquals("A", labels.get("a").toString()); 330 assertEquals("B", labels.get("b").toString()); 331 assertEquals("C", labels.get("c").toString()); 332 } 333 testParseWithWildcardLabels()334 @Test public void testParseWithWildcardLabels() throws Exception { 335 TreeWizard wiz = new TreeWizard(adaptor, tokens); 336 CommonTree t = (CommonTree)wiz.create("(A B C)"); 337 Map labels = new HashMap(); 338 boolean valid = wiz.parse(t, "(A %b:. %c:.)", labels); 339 assertTrue(valid); 340 assertEquals("B", labels.get("b").toString()); 341 assertEquals("C", labels.get("c").toString()); 342 } 343 testParseLabelsAndTestText()344 @Test public void testParseLabelsAndTestText() throws Exception { 345 TreeWizard wiz = new TreeWizard(adaptor, tokens); 346 CommonTree t = (CommonTree)wiz.create("(A B[foo] C)"); 347 Map labels = new HashMap(); 348 boolean valid = wiz.parse(t, "(%a:A %b:B[foo] %c:C)", labels); 349 assertTrue(valid); 350 assertEquals("A", labels.get("a").toString()); 351 assertEquals("foo", labels.get("b").toString()); 352 assertEquals("C", labels.get("c").toString()); 353 } 354 testParseLabelsInNestedTree()355 @Test public void testParseLabelsInNestedTree() throws Exception { 356 TreeWizard wiz = new TreeWizard(adaptor, tokens); 357 CommonTree t = (CommonTree)wiz.create("(A (B C) (D E))"); 358 Map labels = new HashMap(); 359 boolean valid = wiz.parse(t, "(%a:A (%b:B %c:C) (%d:D %e:E) )", labels); 360 assertTrue(valid); 361 assertEquals("A", labels.get("a").toString()); 362 assertEquals("B", labels.get("b").toString()); 363 assertEquals("C", labels.get("c").toString()); 364 assertEquals("D", labels.get("d").toString()); 365 assertEquals("E", labels.get("e").toString()); 366 } 367 testEquals()368 @Test public void testEquals() throws Exception { 369 TreeWizard wiz = new TreeWizard(adaptor, tokens); 370 CommonTree t1 = (CommonTree)wiz.create("(A B C)"); 371 CommonTree t2 = (CommonTree)wiz.create("(A B C)"); 372 boolean same = TreeWizard.equals(t1, t2, adaptor); 373 assertTrue(same); 374 } 375 testEqualsWithText()376 @Test public void testEqualsWithText() throws Exception { 377 TreeWizard wiz = new TreeWizard(adaptor, tokens); 378 CommonTree t1 = (CommonTree)wiz.create("(A B[foo] C)"); 379 CommonTree t2 = (CommonTree)wiz.create("(A B[foo] C)"); 380 boolean same = TreeWizard.equals(t1, t2, adaptor); 381 assertTrue(same); 382 } 383 testEqualsWithMismatchedText()384 @Test public void testEqualsWithMismatchedText() throws Exception { 385 TreeWizard wiz = new TreeWizard(adaptor, tokens); 386 CommonTree t1 = (CommonTree)wiz.create("(A B[foo] C)"); 387 CommonTree t2 = (CommonTree)wiz.create("(A B C)"); 388 boolean same = TreeWizard.equals(t1, t2, adaptor); 389 assertTrue(!same); 390 } 391 testFindPattern()392 @Test public void testFindPattern() throws Exception { 393 TreeWizard wiz = new TreeWizard(adaptor, tokens); 394 CommonTree t = (CommonTree)wiz.create("(A B C (A[foo] B[bar]) (D (A[big] B[dog])))"); 395 final List subtrees = wiz.find(t, "(A B)"); 396 List elements = subtrees; 397 String found = elements.toString(); 398 String expecting = "[foo, big]"; 399 assertEquals(expecting, found); 400 } 401 402 }