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
#	User	Rev	Content
1	tim	2469	/* 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