[mirror_edk2.git] / Tools / CodeTools / Source / Pccts / h / ast.c

/* Abstract syntax tree manipulation functions\r
 *\r
 * SOFTWARE RIGHTS\r
 *\r
 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool\r
 * Set (PCCTS) -- PCCTS is in the public domain.  An individual or\r
 * company may do whatever they wish with source code distributed with\r
 * PCCTS or the code generated by PCCTS, including the incorporation of\r
 * PCCTS, or its output, into commerical software.\r
 *\r
 * We encourage users to develop software with PCCTS.  However, we do ask\r
 * that credit is given to us for developing PCCTS.  By "credit",\r
 * we mean that if you incorporate our source code into one of your\r
 * programs (commercial product, research project, or otherwise) that you\r
 * acknowledge this fact somewhere in the documentation, research report,\r
 * etc...  If you like PCCTS and have developed a nice tool with the\r
 * output, please mention that you developed it using PCCTS.  In\r
 * addition, we ask that this header remain intact in our source code.\r
 * As long as these guidelines are kept, we expect to continue enhancing\r
 * this system and expect to make other tools available as they are\r
 * completed. \r
 *\r
 * ANTLR 1.33\r
 * Terence Parr\r
 * Parr Research Corporation\r
 * with Purdue University and AHPCRC, University of Minnesota\r
 * 1989-2000\r
 */\r
\r
#include "pcctscfg.h"\r
\r
#ifdef PCCTS_USE_STDARG\r
#include "pccts_stdarg.h"\r
#else\r
#include <varargs.h>\r
#endif\r
\r
/* ensure that tree manipulation variables are current after a rule\r
 * reference\r
 */\r
\r
void\r
#ifdef __USE_PROTOS\r
zzlink(AST **_root, AST **_sibling, AST **_tail)\r
#else\r
zzlink(_root, _sibling, _tail)\r
AST **_root, **_sibling, **_tail;\r
#endif\r
{\r
	if ( *_sibling == NULL ) return;\r
	if ( *_root == NULL ) *_root = *_sibling;\r
	else if ( *_root != *_sibling ) (*_root)->down = *_sibling;\r
	if ( *_tail==NULL ) *_tail = *_sibling;\r
	while ( (*_tail)->right != NULL ) *_tail = (*_tail)->right;\r
}\r
\r
AST *\r
#ifdef __USE_PROTOS\r
zzastnew(void)\r
#else\r
zzastnew()\r
#endif\r
{\r
	AST *p = (AST *) calloc(1, sizeof(AST));\r
	if ( p == NULL ) fprintf(stderr,"%s(%d): cannot allocate AST node\n",__FILE__,__LINE__);\r
	return p;\r
}\r
\r
/* add a child node to the current sibling list */\r
void\r
#ifdef __USE_PROTOS\r
zzsubchild(AST **_root, AST **_sibling, AST **_tail)\r
#else\r
zzsubchild(_root, _sibling, _tail)\r
AST **_root, **_sibling, **_tail;\r
#endif\r
{\r
	AST *n;\r
	zzNON_GUESS_MODE {\r
	n = zzastnew();\r
#ifdef DEMAND_LOOK\r
	zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0));\r
#else\r
	zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1));\r
#endif\r
	zzastPush( n );\r
	if ( *_tail != NULL ) (*_tail)->right = n;\r
	else {\r
		*_sibling = n;\r
		if ( *_root != NULL ) (*_root)->down = *_sibling;\r
	}\r
	*_tail = n;\r
	if ( *_root == NULL ) *_root = *_sibling;\r
	}\r
}\r
\r
/* make a new AST node.  Make the newly-created\r
 * node the root for the current sibling list.  If a root node already\r
 * exists, make the newly-created node the root of the current root.\r
 */\r
void\r
#ifdef __USE_PROTOS\r
zzsubroot(AST **_root, AST **_sibling, AST **_tail)\r
#else\r
zzsubroot(_root, _sibling, _tail)\r
AST **_root, **_sibling, **_tail;\r
#endif\r
{\r
	AST *n;\r
	zzNON_GUESS_MODE {\r
	n = zzastnew();\r
#ifdef DEMAND_LOOK\r
	zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0));\r
#else\r
	zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1));\r
#endif\r
	zzastPush( n );\r
	if ( *_root != NULL )\r
		if ( (*_root)->down == *_sibling ) *_sibling = *_tail = *_root;\r
	*_root = n;\r
	(*_root)->down = *_sibling;\r
	}\r
}\r
\r
/* Apply function to root then each sibling\r
 * example: print tree in child-sibling LISP-format (AST has token field)\r
 *\r
 *	void show(tree)\r
 *	AST *tree;\r
 *	{\r
 *		if ( tree == NULL ) return;\r
 *		printf(" %s", zztokens[tree->token]);\r
 *	}\r
 *\r
 *	void before() { printf(" ("); }\r
 *	void after()  { printf(" )"); }\r
 *\r
 *	LISPdump() { zzpre_ast(tree, show, before, after); }\r
 *\r
 */\r
void\r
#ifdef __USE_PROTOS\r
zzpre_ast(\r
	  AST *tree,\r
	  void (*func)(AST *),   /* apply this to each tree node */\r
	  void (*before)(AST *), /* apply this to root of subtree before preordering it */\r
	  void (*after)(AST *))  /* apply this to root of subtree after preordering it */\r
#else\r
zzpre_ast(tree, func, before, after)\r
AST *tree;\r
void (*func)(),   /* apply this to each tree node */\r
	 (*before)(), /* apply this to root of subtree before preordering it */\r
	 (*after)();  /* apply this to root of subtree after preordering it */\r
#endif\r
{\r
	while ( tree!= NULL )\r
	{\r
		if ( tree->down != NULL ) (*before)(tree);\r
		(*func)(tree);\r
		zzpre_ast(tree->down, func, before, after);\r
		if ( tree->down != NULL ) (*after)(tree);\r
		tree = tree->right;\r
	}\r
}\r
\r
/* free all AST nodes in tree; apply func to each before freeing */\r
\r
#if 0\r
////void\r
////#ifdef __USE_PROTOS\r
////zzfree_ast(AST *tree)\r
////#else\r
////zzfree_ast(tree)\r
////AST *tree;\r
////#endif\r
////{\r
////	if ( tree == NULL ) return;\r
////	zzfree_ast( tree->down );\r
////	zzfree_ast( tree->right );\r
////	zztfree( tree );\r
////}\r
#endif\r
\r
/*\r
   MR19 Optimize freeing of the following structure to limit recursion\r
   SAKAI Kiyotaka (ksakai@isr.co.jp)\r
*/\r
\r
/*\r
         NULL o\r
             / \\r
           NULL o\r
               / \\r
            NULL NULL\r
*/\r
\r
/*\r
   MR21 Another refinement to replace recursion with iteration\r
   NAKAJIMA Mutsuki (muc@isr.co.jp).\r
*/\r
\r
void\r
#ifdef __USE_PROTOS\r
zzfree_ast(AST *tree)\r
#else\r
zzfree_ast(tree)\r
AST *tree;\r
#endif\r
{\r
\r
    AST *otree;\r
\r
    if (tree == NULL) return;\r
\r
    while (tree->down == NULL || tree->right == NULL) {\r
\r
        if (tree->down == NULL && tree->right == NULL) {\r
            zztfree(tree);\r
            return;\r
        }\r
\r
        otree = tree;\r
        if (tree->down == NULL) {\r
            tree = tree->right;\r
        } else {\r
            tree = tree->down;\r
        }\r
        zztfree( otree );\r
    }\r
\r
    while (tree != NULL) {\r
        zzfree_ast(tree->down);\r
        otree = tree;\r
        tree = otree->right;\r
        zztfree(otree);\r
    }\r
}\r
\r
/* build a tree (root child1 child2 ... NULL)\r
 * If root is NULL, simply make the children siblings and return ptr\r
 * to 1st sibling (child1).  If root is not single node, return NULL.\r
 *\r
 * Siblings that are actually siblins lists themselves are handled\r
 * correctly.  For example #( NULL, #( NULL, A, B, C), D) results\r
 * in the tree ( NULL A B C D ).\r
 *\r
 * Requires at least two parameters with the last one being NULL.  If\r
 * both are NULL, return NULL.\r
 */\r
#ifdef PCCTS_USE_STDARG\r
AST *zztmake(AST *rt, ...)\r
#else\r
AST *zztmake(va_alist)\r
va_dcl\r
#endif\r
{\r
	va_list ap;\r
	register AST *child, *sibling=NULL, *tail=NULL /* MR20 */, *w;\r
	AST *root;\r
\r
#ifdef PCCTS_USE_STDARG\r
	va_start(ap, rt);\r
	root = rt;\r
#else\r
	va_start(ap);\r
	root = va_arg(ap, AST *);\r
#endif\r
\r
	if ( root != NULL )\r
		if ( root->down != NULL ) return NULL;\r
	child = va_arg(ap, AST *);\r
	while ( child != NULL )\r
	{\r
		for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */\r
		if ( sibling == NULL ) {sibling = child; tail = w;}\r
		else {tail->right = child; tail = w;}\r
		child = va_arg(ap, AST *);\r
	}\r
	if ( root==NULL ) root = sibling;\r
	else root->down = sibling;\r
	va_end(ap);\r
	return root;\r
}\r
\r
/* tree duplicate */\r
AST *\r
#ifdef __USE_PROTOS\r
zzdup_ast(AST *t)\r
#else\r
zzdup_ast(t)\r
AST *t;\r
#endif\r
{\r
	AST *u;\r
	\r
	if ( t == NULL ) return NULL;\r
	u = zzastnew();\r
	*u = *t;\r
#ifdef zzAST_DOUBLE\r
	u->up = NULL;		/* set by calling invocation */\r
	u->left = NULL;\r
#endif\r
	u->right = zzdup_ast(t->right);\r
	u->down = zzdup_ast(t->down);\r
#ifdef zzAST_DOUBLE\r
	if ( u->right!=NULL ) u->right->left = u;\r
	if ( u->down!=NULL ) u->down->up = u;\r
#endif\r
	return u;\r
}\r
\r
void\r
#ifdef __USE_PROTOS\r
zztfree(AST *t)\r
#else\r
zztfree(t)\r
AST *t;\r
#endif\r
{\r
#ifdef zzd_ast\r
	zzd_ast( t );\r
#endif\r
	free( t );\r
}\r
\r
#ifdef zzAST_DOUBLE\r
/*\r
 * Set the 'up', and 'left' pointers of all nodes in 't'.\r
 * Initial call is double_link(your_tree, NULL, NULL).\r
 */\r
void\r
#ifdef __USE_PROTOS\r
zzdouble_link(AST *t, AST *left, AST *up)\r
#else\r
zzdouble_link(t, left, up)\r
AST *t, *left, *up;\r
#endif\r
{\r
	if ( t==NULL ) return;\r
	t->left = left;\r
	t->up = up;\r
	zzdouble_link(t->down, NULL, t);\r
	zzdouble_link(t->right, t, up);\r
}\r
#endif\r
Commit	Line	Data
878ddf1f	1	/* Abstract syntax tree manipulation functions\r
	2	*\r
	3	* SOFTWARE RIGHTS\r
	4	*\r
	5	* We reserve no LEGAL rights to the Purdue Compiler Construction Tool\r
	6	* Set (PCCTS) -- PCCTS is in the public domain. An individual or\r
	7	* company may do whatever they wish with source code distributed with\r
	8	* PCCTS or the code generated by PCCTS, including the incorporation of\r
	9	* PCCTS, or its output, into commerical software.\r
	10	*\r
	11	* We encourage users to develop software with PCCTS. However, we do ask\r
	12	* that credit is given to us for developing PCCTS. By "credit",\r
	13	* we mean that if you incorporate our source code into one of your\r
	14	* programs (commercial product, research project, or otherwise) that you\r
	15	* acknowledge this fact somewhere in the documentation, research report,\r
	16	* etc... If you like PCCTS and have developed a nice tool with the\r
	17	* output, please mention that you developed it using PCCTS. In\r
	18	* addition, we ask that this header remain intact in our source code.\r
	19	* As long as these guidelines are kept, we expect to continue enhancing\r
	20	* this system and expect to make other tools available as they are\r
	21	* completed. \r
	22	*\r
	23	* ANTLR 1.33\r
	24	* Terence Parr\r
	25	* Parr Research Corporation\r
	26	* with Purdue University and AHPCRC, University of Minnesota\r
	27	* 1989-2000\r
	28	*/\r
	29	\r
	30	#include "pcctscfg.h"\r
	31	\r
	32	#ifdef PCCTS_USE_STDARG\r
	33	#include "pccts_stdarg.h"\r
	34	#else\r
	35	#include <varargs.h>\r
	36	#endif\r
	37	\r
	38	/* ensure that tree manipulation variables are current after a rule\r
	39	* reference\r
	40	*/\r
	41	\r
	42	void\r
	43	#ifdef __USE_PROTOS\r
	44	zzlink(AST _root, AST _sibling, AST **_tail)\r
	45	#else\r
	46	zzlink(_root, _sibling, _tail)\r
	47	AST _root, _sibling, **_tail;\r
	48	#endif\r
	49	{\r
	50	if ( *_sibling == NULL ) return;\r
	51	if ( _root == NULL ) _root = *_sibling;\r
	52	else if ( _root != _sibling ) (_root)->down = _sibling;\r
	53	if ( _tail==NULL ) _tail = *_sibling;\r
	54	while ( (_tail)->right != NULL ) _tail = (*_tail)->right;\r
	55	}\r
	56	\r
	57	AST *\r
	58	#ifdef __USE_PROTOS\r
	59	zzastnew(void)\r
	60	#else\r
	61	zzastnew()\r
	62	#endif\r
	63	{\r
	64	AST p = (AST ) calloc(1, sizeof(AST));\r
65	if ( p == NULL ) fprintf(stderr,"%s(%d): cannot allocate AST node\n",__FILE__,__LINE__);\r
66	return p;\r
67	}\r
68	\r
69	/* add a child node to the current sibling list */\r
70	void\r
71	#ifdef __USE_PROTOS\r
72	zzsubchild(AST _root, AST _sibling, AST **_tail)\r
73	#else\r
74	zzsubchild(_root, _sibling, _tail)\r
75	AST _root, _sibling, **_tail;\r
76	#endif\r
77	{\r
78	AST *n;\r
79	zzNON_GUESS_MODE {\r
80	n = zzastnew();\r
81	#ifdef DEMAND_LOOK\r
82	zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0));\r
83	#else\r
84	zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1));\r
85	#endif\r
86	zzastPush( n );\r
87	if ( _tail != NULL ) (_tail)->right = n;\r
88	else {\r
89	*_sibling = n;\r
90	if ( _root != NULL ) (_root)->down = *_sibling;\r
91	}\r
92	*_tail = n;\r
93	if ( _root == NULL ) _root = *_sibling;\r
94	}\r
95	}\r
96	\r
97	/* make a new AST node. Make the newly-created\r
98	* node the root for the current sibling list. If a root node already\r
99	* exists, make the newly-created node the root of the current root.\r
100	*/\r
101	void\r
102	#ifdef __USE_PROTOS\r
103	zzsubroot(AST _root, AST _sibling, AST **_tail)\r
104	#else\r
105	zzsubroot(_root, _sibling, _tail)\r
106	AST _root, _sibling, **_tail;\r
107	#endif\r
108	{\r
109	AST *n;\r
110	zzNON_GUESS_MODE {\r
111	n = zzastnew();\r
112	#ifdef DEMAND_LOOK\r
113	zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0));\r
114	#else\r
115	zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1));\r
116	#endif\r
117	zzastPush( n );\r
118	if ( *_root != NULL )\r
119	if ( (_root)->down == _sibling ) _sibling = _tail = *_root;\r
120	*_root = n;\r
121	(_root)->down = _sibling;\r
122	}\r
123	}\r
124	\r
125	/* Apply function to root then each sibling\r
126	* example: print tree in child-sibling LISP-format (AST has token field)\r
127	*\r
128	* void show(tree)\r
129	* AST *tree;\r
130	* {\r
131	* if ( tree == NULL ) return;\r
132	* printf(" %s", zztokens[tree->token]);\r
133	* }\r
134	*\r
135	* void before() { printf(" ("); }\r
136	* void after() { printf(" )"); }\r
137	*\r
138	* LISPdump() { zzpre_ast(tree, show, before, after); }\r
139	*\r
140	*/\r
141	void\r
142	#ifdef __USE_PROTOS\r
143	zzpre_ast(\r
144	AST *tree,\r
145	void (func)(AST ), /* apply this to each tree node */\r
146	void (before)(AST ), /* apply this to root of subtree before preordering it */\r
147	void (after)(AST )) /* apply this to root of subtree after preordering it */\r
148	#else\r
149	zzpre_ast(tree, func, before, after)\r
150	AST *tree;\r
151	void (func)(), / apply this to each tree node */\r
152	(before)(), / apply this to root of subtree before preordering it */\r
153	(after)(); / apply this to root of subtree after preordering it */\r
154	#endif\r
155	{\r
156	while ( tree!= NULL )\r
157	{\r
158	if ( tree->down != NULL ) (*before)(tree);\r
159	(*func)(tree);\r
160	zzpre_ast(tree->down, func, before, after);\r
161	if ( tree->down != NULL ) (*after)(tree);\r
162	tree = tree->right;\r
163	}\r
164	}\r
165	\r
166	/* free all AST nodes in tree; apply func to each before freeing */\r
167	\r
168	#if 0\r
169	////void\r
170	////#ifdef __USE_PROTOS\r
171	////zzfree_ast(AST *tree)\r
172	////#else\r
173	////zzfree_ast(tree)\r
174	////AST *tree;\r
175	////#endif\r
176	////{\r
177	//// if ( tree == NULL ) return;\r
178	//// zzfree_ast( tree->down );\r
179	//// zzfree_ast( tree->right );\r
180	//// zztfree( tree );\r
181	////}\r
182	#endif\r
183	\r
184	/*\r
185	MR19 Optimize freeing of the following structure to limit recursion\r
186	SAKAI Kiyotaka (ksakai@isr.co.jp)\r
187	*/\r
188	\r
189	/*\r
190	NULL o\r
191	/ \\r
192	NULL o\r
193	/ \\r
194	NULL NULL\r
195	*/\r
196	\r
197	/*\r
198	MR21 Another refinement to replace recursion with iteration\r
199	NAKAJIMA Mutsuki (muc@isr.co.jp).\r
200	*/\r
201	\r
202	void\r
203	#ifdef __USE_PROTOS\r
204	zzfree_ast(AST *tree)\r
205	#else\r
206	zzfree_ast(tree)\r
207	AST *tree;\r
208	#endif\r
209	{\r
210	\r
211	AST *otree;\r
212	\r
213	if (tree == NULL) return;\r
214	\r
215	while (tree->down == NULL \|\| tree->right == NULL) {\r
216	\r
217	if (tree->down == NULL && tree->right == NULL) {\r
218	zztfree(tree);\r
219	return;\r
220	}\r
221	\r
222	otree = tree;\r
223	if (tree->down == NULL) {\r
224	tree = tree->right;\r
225	} else {\r
226	tree = tree->down;\r
227	}\r
228	zztfree( otree );\r
229	}\r
230	\r
231	while (tree != NULL) {\r
232	zzfree_ast(tree->down);\r
233	otree = tree;\r
234	tree = otree->right;\r
235	zztfree(otree);\r
236	}\r
237	}\r
238	\r
239	/* build a tree (root child1 child2 ... NULL)\r
240	* If root is NULL, simply make the children siblings and return ptr\r
241	* to 1st sibling (child1). If root is not single node, return NULL.\r
242	*\r
243	* Siblings that are actually siblins lists themselves are handled\r
244	* correctly. For example #( NULL, #( NULL, A, B, C), D) results\r
245	* in the tree ( NULL A B C D ).\r
246	*\r
247	* Requires at least two parameters with the last one being NULL. If\r
248	* both are NULL, return NULL.\r
249	*/\r
250	#ifdef PCCTS_USE_STDARG\r
251	AST zztmake(AST rt, ...)\r
252	#else\r
253	AST *zztmake(va_alist)\r
254	va_dcl\r
255	#endif\r
256	{\r
257	va_list ap;\r
258	register AST child, sibling=NULL, tail=NULL / MR20 /, w;\r
259	AST *root;\r
260	\r
261	#ifdef PCCTS_USE_STDARG\r
262	va_start(ap, rt);\r
263	root = rt;\r
264	#else\r
265	va_start(ap);\r
266	root = va_arg(ap, AST *);\r
267	#endif\r
268	\r
269	if ( root != NULL )\r
270	if ( root->down != NULL ) return NULL;\r
271	child = va_arg(ap, AST *);\r
272	while ( child != NULL )\r
273	{\r
274	for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */\r
275	if ( sibling == NULL ) {sibling = child; tail = w;}\r
276	else {tail->right = child; tail = w;}\r
277	child = va_arg(ap, AST *);\r
278	}\r
279	if ( root==NULL ) root = sibling;\r
280	else root->down = sibling;\r
281	va_end(ap);\r
282	return root;\r
283	}\r
284	\r
285	/* tree duplicate */\r
286	AST *\r
287	#ifdef __USE_PROTOS\r
288	zzdup_ast(AST *t)\r
289	#else\r
290	zzdup_ast(t)\r
291	AST *t;\r
292	#endif\r
293	{\r
294	AST *u;\r
295	\r
296	if ( t == NULL ) return NULL;\r
297	u = zzastnew();\r
298	u = t;\r
299	#ifdef zzAST_DOUBLE\r
300	u->up = NULL; /* set by calling invocation */\r
301	u->left = NULL;\r
302	#endif\r
303	u->right = zzdup_ast(t->right);\r
304	u->down = zzdup_ast(t->down);\r
305	#ifdef zzAST_DOUBLE\r
306	if ( u->right!=NULL ) u->right->left = u;\r
307	if ( u->down!=NULL ) u->down->up = u;\r
308	#endif\r
309	return u;\r
310	}\r
311	\r
312	void\r
313	#ifdef __USE_PROTOS\r
314	zztfree(AST *t)\r
315	#else\r
316	zztfree(t)\r
317	AST *t;\r
318	#endif\r
319	{\r
320	#ifdef zzd_ast\r
321	zzd_ast( t );\r
322	#endif\r
323	free( t );\r
324	}\r
325	\r
326	#ifdef zzAST_DOUBLE\r
327	/*\r
328	* Set the 'up', and 'left' pointers of all nodes in 't'.\r
329	* Initial call is double_link(your_tree, NULL, NULL).\r
330	*/\r
331	void\r
332	#ifdef __USE_PROTOS\r
333	zzdouble_link(AST t, AST left, AST *up)\r
334	#else\r
335	zzdouble_link(t, left, up)\r
336	AST t, left, *up;\r
337	#endif\r
338	{\r
339	if ( t==NULL ) return;\r
340	t->left = left;\r
341	t->up = up;\r
342	zzdouble_link(t->down, NULL, t);\r
343	zzdouble_link(t->right, t, up);\r
344	}\r
345	#endif\r