13447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/* 23447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein [The "BSD license"] 33447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Copyright (c) 2005-2009 Terence Parr 43447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein All rights reserved. 53447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 63447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Redistribution and use in source and binary forms, with or without 73447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein modification, are permitted provided that the following conditions 83447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein are met: 93447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1. Redistributions of source code must retain the above copyright 103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein notice, this list of conditions and the following disclaimer. 113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2. Redistributions in binary form must reproduce the above copyright 123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein notice, this list of conditions and the following disclaimer in the 133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein documentation and/or other materials provided with the distribution. 143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3. The name of the author may not be used to endorse or promote products 153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein derived from this software without specific prior written permission. 163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpackage org.antlr.runtime.tree; 303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/** Do a depth first walk of a tree, applying pre() and post() actions 323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * as we discover and finish nodes. 333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpublic class TreeVisitor { 353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected TreeAdaptor adaptor; 363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public TreeVisitor(TreeAdaptor adaptor) { 383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this.adaptor = adaptor; 393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public TreeVisitor() { this(new CommonTreeAdaptor()); } 413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Visit every node in tree t and trigger an action for each node 433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * before/after having visited all of its children. 443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Execute both actions even if t has no children. 453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * If a child visit yields a new child, it can update its 463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * parent's child list or just return the new child. The 473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * child update code works even if the child visit alters its parent 483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * and returns the new tree. 493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Return result of applying post action to this node. 513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Object visit(Object t, TreeVisitorAction action) { 533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // System.out.println("visit "+((Tree)t).toStringTree()); 543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein boolean isNil = adaptor.isNil(t); 553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( action!=null && !isNil ) { 563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein t = action.pre(t); // if rewritten, walk children of new t 573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i=0; i<adaptor.getChildCount(t); i++) { 593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Object child = adaptor.getChild(t, i); 603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Object visitResult = visit(child, action); 613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Object childAfterVisit = adaptor.getChild(t, i); 623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( visitResult != childAfterVisit ) { // result & child differ? 633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein adaptor.setChild(t, i, visitResult); 643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( action!=null && !isNil ) t = action.post(t); 673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return t; 683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein} 70