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