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$
 */

#include "antlr/config.hpp"

#include <iostream>

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

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
Revision:	1782
Committed:	Wed Aug 22 02:28:28 2012 UTC (13 years, 2 months ago) by gezelter
File size:	6657 byte(s)
Log Message:	MERGE OpenMD development branch 1465:1781 into trunk
#	User	Rev	Content
1	tim	770	/* 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	gezelter	1442	* $Id$
6	tim	770	*/
7
8	gezelter	1558	#include "antlr/config.hpp"
9
10	tim	770	#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	gezelter	1782	#if defined(_MSC_VER) && !defined(__ICL)
274			// Microsoft Visual C++
275	tim	770	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