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