1/* ANTLR Translator Generator 2 * Project led by Terence Parr at http://www.jGuru.com 3 * Software rights: http://www.antlr.org/license.html 4 * 5 * $Id: //depot/code/org.antlr/release/antlr-2.7.7/lib/cpp/src/BaseAST.cpp#2 $ 6 */ 7 8#include "antlr/config.hpp" 9 10//#include <iostream> 11 12#include "antlr/AST.hpp" 13#include "antlr/BaseAST.hpp" 14 15ANTLR_USING_NAMESPACE(std) 16#ifdef ANTLR_CXX_SUPPORTS_NAMESPACE 17namespace antlr { 18#endif 19 20size_t BaseAST::getNumberOfChildren() const 21{ 22 RefBaseAST t = this->down; 23 size_t n = 0; 24 if( t ) 25 { 26 n = 1; 27 while( t->right ) 28 { 29 t = t->right; 30 n++; 31 } 32 return n; 33 } 34 return n; 35} 36 37void BaseAST::doWorkForFindAll( 38 ANTLR_USE_NAMESPACE(std)vector<RefAST>& v, 39 RefAST target,bool partialMatch) 40{ 41 // Start walking sibling lists, looking for matches. 42 for (RefAST sibling=this; 43 sibling; 44 sibling=sibling->getNextSibling()) 45 { 46 if ( (partialMatch && sibling->equalsTreePartial(target)) || 47 (!partialMatch && sibling->equalsTree(target)) ) { 48 v.push_back(sibling); 49 } 50 // regardless of match or not, check any children for matches 51 if ( sibling->getFirstChild() ) { 52 RefBaseAST(sibling->getFirstChild())->doWorkForFindAll(v, target, partialMatch); 53 } 54 } 55} 56 57/** Is t an exact structural and equals() match of this tree. The 58 * 'this' reference is considered the start of a sibling list. 59 */ 60bool BaseAST::equalsList(RefAST t) const 61{ 62 // the empty tree is not a match of any non-null tree. 63 if (!t) 64 return false; 65 66 // Otherwise, start walking sibling lists. First mismatch, return false. 67 RefAST sibling=this; 68 for (;sibling && t; 69 sibling=sibling->getNextSibling(), t=t->getNextSibling()) { 70 // as a quick optimization, check roots first. 71 if (!sibling->equals(t)) 72 return false; 73 // if roots match, do full list match test on children. 74 if (sibling->getFirstChild()) { 75 if (!sibling->getFirstChild()->equalsList(t->getFirstChild())) 76 return false; 77 } 78 // sibling has no kids, make sure t doesn't either 79 else if (t->getFirstChild()) 80 return false; 81 } 82 83 if (!sibling && !t) 84 return true; 85 86 // one sibling list has more than the other 87 return false; 88} 89 90/** Is 'sub' a subtree of this list? 91 * The siblings of the root are NOT ignored. 92 */ 93bool BaseAST::equalsListPartial(RefAST sub) const 94{ 95 // the empty tree is always a subset of any tree. 96 if (!sub) 97 return true; 98 99 // Otherwise, start walking sibling lists. First mismatch, return false. 100 RefAST sibling=this; 101 for (;sibling && sub; 102 sibling=sibling->getNextSibling(), sub=sub->getNextSibling()) { 103 // as a quick optimization, check roots first. 104 if (!sibling->equals(sub)) 105 return false; 106 // if roots match, do partial list match test on children. 107 if (sibling->getFirstChild()) 108 if (!sibling->getFirstChild()->equalsListPartial(sub->getFirstChild())) 109 return false; 110 } 111 112 if (!sibling && sub) 113 // nothing left to match in this tree, but subtree has more 114 return false; 115 116 // either both are null or sibling has more, but subtree doesn't 117 return true; 118} 119 120/** Is tree rooted at 'this' equal to 't'? The siblings 121 * of 'this' are ignored. 122 */ 123bool BaseAST::equalsTree(RefAST t) const 124{ 125 // check roots first 126 if (!equals(t)) 127 return false; 128 // if roots match, do full list match test on children. 129 if (getFirstChild()) { 130 if (!getFirstChild()->equalsList(t->getFirstChild())) 131 return false; 132 } 133 // sibling has no kids, make sure t doesn't either 134 else if (t->getFirstChild()) 135 return false; 136 137 return true; 138} 139 140/** Is 'sub' a subtree of the tree rooted at 'this'? The siblings 141 * of 'this' are ignored. 142 */ 143bool BaseAST::equalsTreePartial(RefAST sub) const 144{ 145 // the empty tree is always a subset of any tree. 146 if (!sub) 147 return true; 148 149 // check roots first 150 if (!equals(sub)) 151 return false; 152 // if roots match, do full list partial match test on children. 153 if (getFirstChild()) 154 if (!getFirstChild()->equalsListPartial(sub->getFirstChild())) 155 return false; 156 157 return true; 158} 159 160/** Walk the tree looking for all exact subtree matches. Return 161 * an ASTEnumerator that lets the caller walk the list 162 * of subtree roots found herein. 163 */ 164ANTLR_USE_NAMESPACE(std)vector<RefAST> BaseAST::findAll(RefAST target) 165{ 166 ANTLR_USE_NAMESPACE(std)vector<RefAST> roots; 167 168 // the empty tree cannot result in an enumeration 169 if (target) { 170 doWorkForFindAll(roots,target,false); // find all matches recursively 171 } 172 173 return roots; 174} 175 176/** Walk the tree looking for all subtrees. Return 177 * an ASTEnumerator that lets the caller walk the list 178 * of subtree roots found herein. 179 */ 180ANTLR_USE_NAMESPACE(std)vector<RefAST> BaseAST::findAllPartial(RefAST target) 181{ 182 ANTLR_USE_NAMESPACE(std)vector<RefAST> roots; 183 184 // the empty tree cannot result in an enumeration 185 if (target) 186 doWorkForFindAll(roots,target,true); // find all matches recursively 187 188 return roots; 189} 190 191ANTLR_USE_NAMESPACE(std)string BaseAST::toStringList() const 192{ 193 ANTLR_USE_NAMESPACE(std)string ts=""; 194 195 if (getFirstChild()) 196 { 197 ts+=" ( "; 198 ts+=toString(); 199 ts+=getFirstChild()->toStringList(); 200 ts+=" )"; 201 } 202 else 203 { 204 ts+=" "; 205 ts+=toString(); 206 } 207 208 if (getNextSibling()) 209 ts+=getNextSibling()->toStringList(); 210 211 return ts; 212} 213 214ANTLR_USE_NAMESPACE(std)string BaseAST::toStringTree() const 215{ 216 ANTLR_USE_NAMESPACE(std)string ts = ""; 217 218 if (getFirstChild()) 219 { 220 ts+=" ( "; 221 ts+=toString(); 222 ts+=getFirstChild()->toStringList(); 223 ts+=" )"; 224 } 225 else 226 { 227 ts+=" "; 228 ts+=toString(); 229 } 230 return ts; 231} 232 233#ifdef ANTLR_SUPPORT_XML 234/* This whole XML output stuff needs a little bit more thought 235 * I'd like to store extra XML data in the node. e.g. for custom ast's 236 * with for instance symboltable references. This 237 * should be more pluggable.. 238 * @returns boolean value indicating wether a closetag should be produced. 239 */ 240bool BaseAST::attributesToStream( ANTLR_USE_NAMESPACE(std)ostream& out ) const 241{ 242 out << "text=\"" << this->getText() 243 << "\" type=\"" << this->getType() << "\""; 244 245 return false; 246} 247 248void BaseAST::toStream( ANTLR_USE_NAMESPACE(std)ostream& out ) const 249{ 250 for( RefAST node = this; node != 0; node = node->getNextSibling() ) 251 { 252 out << "<" << this->typeName() << " "; 253 254 // Write out attributes and if there is extra data... 255 bool need_close_tag = node->attributesToStream( out ); 256 257 if( need_close_tag ) 258 { 259 // got children so write them... 260 if( node->getFirstChild() != 0 ) 261 node->getFirstChild()->toStream( out ); 262 263 // and a closing tag.. 264 out << "</" << node->typeName() << ">" << endl; 265 } 266 } 267} 268#endif 269 270// this is nasty, but it makes the code generation easier 271ANTLR_API RefAST nullAST; 272 273#if defined(_MSC_VER) && !defined(__ICL) // Microsoft Visual C++ 274extern ANTLR_API AST* const nullASTptr = 0; 275#else 276ANTLR_API AST* const nullASTptr = 0; 277#endif 278 279#ifdef ANTLR_CXX_SUPPORTS_NAMESPACE 280} 281#endif 282