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