OSX/libsecurity_codesigning/antlr2/src/BaseAST.cpp

   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
  15 ANTLR_USING_NAMESPACE(std)
  16 #ifdef ANTLR_CXX_SUPPORTS_NAMESPACE
  17 namespace antlr {
  18 #endif
  19
  20 size_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
  37 void 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  */
  60 bool 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  */
  93 bool 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  */
 123 bool 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  */
 143 bool 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  */
 164 ANTLR_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  */
 180 ANTLR_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
 191 ANTLR_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
 214 ANTLR_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  */
 240 bool 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
 248 void 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
 271 ANTLR_API RefAST nullAST;
 272
 273 #if defined(_MSC_VER) && !defined(__ICL) // Microsoft Visual C++
 274 extern ANTLR_API AST* const nullASTptr = 0;
 275 #else
 276 ANTLR_API AST* const nullASTptr = 0;
 277 #endif
 278
 279 #ifdef ANTLR_CXX_SUPPORTS_NAMESPACE
 280 }
 281 #endif