src/antlr/BaseAST.cpp

/* ANTLR Translator Generator
 * Project led by Terence Parr at http://www.jGuru.com
 * Software rights: http://www.antlr.org/license.html
 *
 * $Id: BaseAST.cpp,v 1.1 2005-12-02 15:38:02 tim Exp $
 */

#include <iostream>

#include "antlr/config.hpp"
#include "antlr/AST.hpp"
#include "antlr/BaseAST.hpp"

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

const char* const BaseAST::TYPE_NAME = "BaseAST";

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