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