summaryrefslogtreecommitdiffstats
path: root/lib/antlr/src/BaseAST.cpp
blob: b5d1814f5245f2534cdba57232f20d5189169d34 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
/* ANTLR Translator Generator
 * Project led by Terence Parr at http://www.jGuru.com
 * Software rights: http://www.antlr.org/license.html
 *
 * $Id$
 */

#include "antlr/config.h"

#include <iostream>

#include "antlr/AST.h"
#include "antlr/BaseAST.h"

ANTLR_USING_NAMESPACE(std)
#ifdef ANTLR_CXX_SUPPORTS_NAMESPACE
namespace antlr {
#endif

size_t BaseAST::getNumberOfChildren() const
{
	RefBaseAST t = this->down;
	size_t n = 0;
	if( t )
	{
		n = 1;
		while( t->right )
		{
			t = t->right;
			n++;
		}
		return n;
	}
	return n;
}

void BaseAST::doWorkForFindAll(
		ANTLR_USE_NAMESPACE(std)vector<RefAST>& v,
		RefAST target,bool partialMatch)
{
	// Start walking sibling lists, looking for matches.
	for (RefAST sibling=this;
			sibling;
			sibling=sibling->getNextSibling())
	{
		if ( (partialMatch && sibling->equalsTreePartial(target)) ||
				(!partialMatch && sibling->equalsTree(target)) ) {
			v.push_back(sibling);
		}
		// regardless of match or not, check any children for matches
		if ( sibling->getFirstChild() ) {
			RefBaseAST(sibling->getFirstChild())->doWorkForFindAll(v, target, partialMatch);
		}
	}
}

/** Is t an exact structural and equals() match of this tree.  The
 *  'this' reference is considered the start of a sibling list.
 */
bool BaseAST::equalsList(RefAST t) const
{
	// the empty tree is not a match of any non-null tree.
	if (!t)
		return false;

	// Otherwise, start walking sibling lists.  First mismatch, return false.
	RefAST sibling=this;
	for (;sibling && t;
			sibling=sibling->getNextSibling(), t=t->getNextSibling()) {
		// as a quick optimization, check roots first.
		if (!sibling->equals(t))
			return false;
		// if roots match, do full list match test on children.
		if (sibling->getFirstChild()) {
			if (!sibling->getFirstChild()->equalsList(t->getFirstChild()))
				return false;
		}
		// sibling has no kids, make sure t doesn't either
		else if (t->getFirstChild())
			return false;
	}

	if (!sibling && !t)
		return true;

	// one sibling list has more than the other
	return false;
}

/** Is 'sub' a subtree of this list?
 *  The siblings of the root are NOT ignored.
 */
bool BaseAST::equalsListPartial(RefAST sub) const
{
	// the empty tree is always a subset of any tree.
	if (!sub)
		return true;

	// Otherwise, start walking sibling lists.  First mismatch, return false.
	RefAST sibling=this;
	for (;sibling && sub;
			sibling=sibling->getNextSibling(), sub=sub->getNextSibling()) {
		// as a quick optimization, check roots first.
		if (!sibling->equals(sub))
			return false;
		// if roots match, do partial list match test on children.
		if (sibling->getFirstChild())
			if (!sibling->getFirstChild()->equalsListPartial(sub->getFirstChild()))
				return false;
	}

	if (!sibling && sub)
		// nothing left to match in this tree, but subtree has more
		return false;

	// either both are null or sibling has more, but subtree doesn't
	return true;
}

/** Is tree rooted at 'this' equal to 't'?  The siblings
 *  of 'this' are ignored.
 */
bool BaseAST::equalsTree(RefAST t) const
{
	// check roots first
	if (!equals(t))
		return false;
	// if roots match, do full list match test on children.
	if (getFirstChild()) {
		if (!getFirstChild()->equalsList(t->getFirstChild()))
			return false;
	}
	// sibling has no kids, make sure t doesn't either
	else if (t->getFirstChild())
		return false;

	return true;
}

/** Is 'sub' a subtree of the tree rooted at 'this'?  The siblings
 *  of 'this' are ignored.
 */
bool BaseAST::equalsTreePartial(RefAST sub) const
{
	// the empty tree is always a subset of any tree.
	if (!sub)
		return true;

	// check roots first
	if (!equals(sub))
		return false;
	// if roots match, do full list partial match test on children.
	if (getFirstChild())
		if (!getFirstChild()->equalsListPartial(sub->getFirstChild()))
			return false;

	return true;
}

/** Walk the tree looking for all exact subtree matches.  Return
 *  an ASTEnumerator that lets the caller walk the list
 *  of subtree roots found herein.
 */
ANTLR_USE_NAMESPACE(std)vector<RefAST> BaseAST::findAll(RefAST target)
{
	ANTLR_USE_NAMESPACE(std)vector<RefAST> roots;

	// the empty tree cannot result in an enumeration
	if (target) {
		doWorkForFindAll(roots,target,false); // find all matches recursively
	}

	return roots;
}

/** Walk the tree looking for all subtrees.  Return
 *  an ASTEnumerator that lets the caller walk the list
 *  of subtree roots found herein.
 */
ANTLR_USE_NAMESPACE(std)vector<RefAST> BaseAST::findAllPartial(RefAST target)
{
	ANTLR_USE_NAMESPACE(std)vector<RefAST> roots;

	// the empty tree cannot result in an enumeration
	if (target)
		doWorkForFindAll(roots,target,true); // find all matches recursively

	return roots;
}

ANTLR_USE_NAMESPACE(std)string BaseAST::toStringList() const
{
	ANTLR_USE_NAMESPACE(std)string ts="";

	if (getFirstChild())
	{
		ts+=" ( ";
		ts+=toString();
		ts+=getFirstChild()->toStringList();
		ts+=" )";
	}
	else
	{
		ts+=" ";
		ts+=toString();
	}

	if (getNextSibling())
		ts+=getNextSibling()->toStringList();

	return ts;
}

ANTLR_USE_NAMESPACE(std)string BaseAST::toStringTree() const
{
	ANTLR_USE_NAMESPACE(std)string ts = "";

	if (getFirstChild())
	{
		ts+=" ( ";
		ts+=toString();
		ts+=getFirstChild()->toStringList();
		ts+=" )";
	}
	else
	{
		ts+=" ";
		ts+=toString();
	}
	return ts;
}

#ifdef ANTLR_SUPPORT_XML
/* This whole XML output stuff needs a little bit more thought
 * I'd like to store extra XML data in the node. e.g. for custom ast's
 * with for instance symboltable references. This
 * should be more pluggable..
 * @returns boolean value indicating wether a closetag should be produced.
 */
bool BaseAST::attributesToStream( ANTLR_USE_NAMESPACE(std)ostream& out ) const
{
	out << "text=\"" << this->getText()
		<< "\" type=\"" << this->getType() << "\"";

	return false;
}

void BaseAST::toStream( ANTLR_USE_NAMESPACE(std)ostream& out ) const
{
	for( RefAST node = this; node != 0; node = node->getNextSibling() )
	{
		out << "<" << this->typeName() << " ";

		// Write out attributes and if there is extra data...
		bool need_close_tag = node->attributesToStream( out );

		if( need_close_tag )
		{
			// got children so write them...
			if( node->getFirstChild() != 0 )
				node->getFirstChild()->toStream( out );

			// and a closing tag..
			out << "</" << node->typeName() << ">" << endl;
		}
	}
}
#endif

// this is nasty, but it makes the code generation easier
ANTLR_API RefAST nullAST;

#if defined(_MSC_VER) && !defined(__ICL) // Microsoft Visual C++
extern ANTLR_API AST* const nullASTptr = 0;
#else
ANTLR_API AST* const nullASTptr = 0;
#endif

#ifdef ANTLR_CXX_SUPPORTS_NAMESPACE
}
#endif