1/*
2 * Copyright 2012-2013 Ecole Normale Superieure
3 * Copyright 2022      Cerebras Systems
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d���Ulm, 75230 Paris, France
9 * and Cerebras Systems, 1237 E Arques Ave, Sunnyvale, CA, USA
10 */
11
12#include <string.h>
13
14#include <isl/id.h>
15#include <isl/stream.h>
16#include <isl/val.h>
17#include <isl_ast_private.h>
18
19#undef EL_BASE
20#define EL_BASE ast_expr
21
22#include <isl_list_templ.c>
23
24#undef EL_BASE
25#define EL_BASE ast_node
26
27#include <isl_list_templ.c>
28
29isl_ctx *isl_ast_print_options_get_ctx(
30	__isl_keep isl_ast_print_options *options)
31{
32	return options ? options->ctx : NULL;
33}
34
35__isl_give isl_ast_print_options *isl_ast_print_options_alloc(isl_ctx *ctx)
36{
37	isl_ast_print_options *options;
38
39	options = isl_calloc_type(ctx, isl_ast_print_options);
40	if (!options)
41		return NULL;
42
43	options->ctx = ctx;
44	isl_ctx_ref(ctx);
45	options->ref = 1;
46
47	return options;
48}
49
50__isl_give isl_ast_print_options *isl_ast_print_options_dup(
51	__isl_keep isl_ast_print_options *options)
52{
53	isl_ctx *ctx;
54	isl_ast_print_options *dup;
55
56	if (!options)
57		return NULL;
58
59	ctx = isl_ast_print_options_get_ctx(options);
60	dup = isl_ast_print_options_alloc(ctx);
61	if (!dup)
62		return NULL;
63
64	dup->print_for = options->print_for;
65	dup->print_for_user = options->print_for_user;
66	dup->print_user = options->print_user;
67	dup->print_user_user = options->print_user_user;
68
69	return dup;
70}
71
72__isl_give isl_ast_print_options *isl_ast_print_options_cow(
73	__isl_take isl_ast_print_options *options)
74{
75	if (!options)
76		return NULL;
77
78	if (options->ref == 1)
79		return options;
80	options->ref--;
81	return isl_ast_print_options_dup(options);
82}
83
84__isl_give isl_ast_print_options *isl_ast_print_options_copy(
85	__isl_keep isl_ast_print_options *options)
86{
87	if (!options)
88		return NULL;
89
90	options->ref++;
91	return options;
92}
93
94__isl_null isl_ast_print_options *isl_ast_print_options_free(
95	__isl_take isl_ast_print_options *options)
96{
97	if (!options)
98		return NULL;
99
100	if (--options->ref > 0)
101		return NULL;
102
103	isl_ctx_deref(options->ctx);
104
105	free(options);
106	return NULL;
107}
108
109/* Set the print_user callback of "options" to "print_user".
110 *
111 * If this callback is set, then it is used to print user nodes in the AST.
112 * Otherwise, the expression associated to the user node is printed.
113 */
114__isl_give isl_ast_print_options *isl_ast_print_options_set_print_user(
115	__isl_take isl_ast_print_options *options,
116	__isl_give isl_printer *(*print_user)(__isl_take isl_printer *p,
117		__isl_take isl_ast_print_options *options,
118		__isl_keep isl_ast_node *node, void *user),
119	void *user)
120{
121	options = isl_ast_print_options_cow(options);
122	if (!options)
123		return NULL;
124
125	options->print_user = print_user;
126	options->print_user_user = user;
127
128	return options;
129}
130
131/* Set the print_for callback of "options" to "print_for".
132 *
133 * If this callback is set, then it used to print for nodes in the AST.
134 */
135__isl_give isl_ast_print_options *isl_ast_print_options_set_print_for(
136	__isl_take isl_ast_print_options *options,
137	__isl_give isl_printer *(*print_for)(__isl_take isl_printer *p,
138		__isl_take isl_ast_print_options *options,
139		__isl_keep isl_ast_node *node, void *user),
140	void *user)
141{
142	options = isl_ast_print_options_cow(options);
143	if (!options)
144		return NULL;
145
146	options->print_for = print_for;
147	options->print_for_user = user;
148
149	return options;
150}
151
152/* Create a new operation expression of operation type "op",
153 * with arguments "args".
154 */
155static __isl_give isl_ast_expr *alloc_op(enum isl_ast_expr_op_type op,
156	__isl_take isl_ast_expr_list *args)
157{
158	isl_ctx *ctx;
159	isl_ast_expr *expr;
160
161	if (!args)
162		return NULL;
163
164	ctx = isl_ast_expr_list_get_ctx(args);
165	expr = isl_calloc_type(ctx, isl_ast_expr);
166	if (!expr)
167		goto error;
168
169	expr->ctx = ctx;
170	isl_ctx_ref(ctx);
171	expr->ref = 1;
172	expr->type = isl_ast_expr_op;
173	expr->u.op.op = op;
174	expr->u.op.args = args;
175
176	return expr;
177error:
178	isl_ast_expr_list_free(args);
179	return NULL;
180}
181
182/* Create a new operation expression of operation type "op",
183 * which will end up having "n_arg" arguments.
184 * The caller still needs to add those arguments.
185 */
186__isl_give isl_ast_expr *isl_ast_expr_alloc_op(isl_ctx *ctx,
187	enum isl_ast_expr_op_type op, int n_arg)
188{
189	isl_ast_expr_list *args;
190
191	args = isl_ast_expr_list_alloc(ctx, n_arg);
192	return alloc_op(op, args);
193}
194
195__isl_give isl_ast_expr *isl_ast_expr_copy(__isl_keep isl_ast_expr *expr)
196{
197	if (!expr)
198		return NULL;
199
200	expr->ref++;
201	return expr;
202}
203
204__isl_give isl_ast_expr *isl_ast_expr_dup(__isl_keep isl_ast_expr *expr)
205{
206	isl_ast_expr *dup;
207
208	if (!expr)
209		return NULL;
210
211	switch (expr->type) {
212	case isl_ast_expr_int:
213		dup = isl_ast_expr_from_val(isl_val_copy(expr->u.v));
214		break;
215	case isl_ast_expr_id:
216		dup = isl_ast_expr_from_id(isl_id_copy(expr->u.id));
217		break;
218	case isl_ast_expr_op:
219		dup = alloc_op(expr->u.op.op,
220				isl_ast_expr_list_copy(expr->u.op.args));
221		break;
222	case isl_ast_expr_error:
223		dup = NULL;
224	}
225
226	if (!dup)
227		return NULL;
228
229	return dup;
230}
231
232__isl_give isl_ast_expr *isl_ast_expr_cow(__isl_take isl_ast_expr *expr)
233{
234	if (!expr)
235		return NULL;
236
237	if (expr->ref == 1)
238		return expr;
239	expr->ref--;
240	return isl_ast_expr_dup(expr);
241}
242
243__isl_null isl_ast_expr *isl_ast_expr_free(__isl_take isl_ast_expr *expr)
244{
245	if (!expr)
246		return NULL;
247
248	if (--expr->ref > 0)
249		return NULL;
250
251	isl_ctx_deref(expr->ctx);
252
253	switch (expr->type) {
254	case isl_ast_expr_int:
255		isl_val_free(expr->u.v);
256		break;
257	case isl_ast_expr_id:
258		isl_id_free(expr->u.id);
259		break;
260	case isl_ast_expr_op:
261		isl_ast_expr_list_free(expr->u.op.args);
262		break;
263	case isl_ast_expr_error:
264		break;
265	}
266
267	free(expr);
268	return NULL;
269}
270
271isl_ctx *isl_ast_expr_get_ctx(__isl_keep isl_ast_expr *expr)
272{
273	return expr ? expr->ctx : NULL;
274}
275
276enum isl_ast_expr_type isl_ast_expr_get_type(__isl_keep isl_ast_expr *expr)
277{
278	return expr ? expr->type : isl_ast_expr_error;
279}
280
281/* Return the integer value represented by "expr".
282 */
283__isl_give isl_val *isl_ast_expr_int_get_val(__isl_keep isl_ast_expr *expr)
284{
285	if (!expr)
286		return NULL;
287	if (expr->type != isl_ast_expr_int)
288		isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
289			"expression not an int", return NULL);
290	return isl_val_copy(expr->u.v);
291}
292
293/* This is an alternative name for the function above.
294 */
295__isl_give isl_val *isl_ast_expr_get_val(__isl_keep isl_ast_expr *expr)
296{
297	return isl_ast_expr_int_get_val(expr);
298}
299
300__isl_give isl_id *isl_ast_expr_id_get_id(__isl_keep isl_ast_expr *expr)
301{
302	if (!expr)
303		return NULL;
304	if (expr->type != isl_ast_expr_id)
305		isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
306			"expression not an identifier", return NULL);
307
308	return isl_id_copy(expr->u.id);
309}
310
311/* This is an alternative name for the function above.
312 */
313__isl_give isl_id *isl_ast_expr_get_id(__isl_keep isl_ast_expr *expr)
314{
315	return isl_ast_expr_id_get_id(expr);
316}
317
318/* Check that "expr" is of type isl_ast_expr_op.
319 */
320static isl_stat isl_ast_expr_check_op(__isl_keep isl_ast_expr *expr)
321{
322	if (!expr)
323		return isl_stat_error;
324	if (expr->type != isl_ast_expr_op)
325		isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
326			"expression not an operation", return isl_stat_error);
327	return isl_stat_ok;
328}
329
330/* Return the type of operation represented by "expr".
331 */
332enum isl_ast_expr_op_type isl_ast_expr_op_get_type(
333	__isl_keep isl_ast_expr *expr)
334{
335	if (isl_ast_expr_check_op(expr) < 0)
336		return isl_ast_expr_op_error;
337	return expr->u.op.op;
338}
339
340/* This is an alternative name for the function above.
341 */
342enum isl_ast_expr_op_type isl_ast_expr_get_op_type(
343	__isl_keep isl_ast_expr *expr)
344{
345	return isl_ast_expr_op_get_type(expr);
346}
347
348/* Return the number of arguments of the operation represented by "expr".
349 */
350isl_size isl_ast_expr_op_get_n_arg(__isl_keep isl_ast_expr *expr)
351{
352	if (isl_ast_expr_check_op(expr) < 0)
353		return isl_size_error;
354	return isl_ast_expr_list_size(expr->u.op.args);
355}
356
357/* This is an alternative name for the function above.
358 */
359isl_size isl_ast_expr_get_op_n_arg(__isl_keep isl_ast_expr *expr)
360{
361	return isl_ast_expr_op_get_n_arg(expr);
362}
363
364/* Return the argument at position "pos" of the operation represented by "expr".
365 */
366__isl_give isl_ast_expr *isl_ast_expr_op_get_arg(__isl_keep isl_ast_expr *expr,
367	int pos)
368{
369	if (isl_ast_expr_check_op(expr) < 0)
370		return NULL;
371
372	return isl_ast_expr_list_get_at(expr->u.op.args, pos);
373}
374
375/* This is an alternative name for the function above.
376 */
377__isl_give isl_ast_expr *isl_ast_expr_get_op_arg(__isl_keep isl_ast_expr *expr,
378	int pos)
379{
380	return isl_ast_expr_op_get_arg(expr, pos);
381}
382
383/* Return a copy of the arguments of the operation represented by "expr".
384 */
385static __isl_give isl_ast_expr_list *isl_ast_expr_op_get_args(
386	__isl_keep isl_ast_expr *expr)
387{
388	if (isl_ast_expr_check_op(expr) < 0)
389		return NULL;
390	return isl_ast_expr_list_copy(expr->u.op.args);
391}
392
393/* Return the arguments of the operation expression "expr".
394 * This may be either a copy or the arguments themselves
395 * if there is only one reference to "expr".
396 * This allows the arguments to be modified inplace
397 * if both "expr" and its arguments have only a single reference.
398 * The caller is not allowed to modify "expr" between this call and
399 * the subsequent call to isl_ast_expr_op_restore_args.
400 * The only exception is that isl_ast_expr_free can be called instead.
401 */
402static __isl_give isl_ast_expr_list *isl_ast_expr_op_take_args(
403	__isl_keep isl_ast_expr *expr)
404{
405	isl_ast_expr_list *args;
406
407	if (isl_ast_expr_check_op(expr) < 0)
408		return NULL;
409	if (expr->ref != 1)
410		return isl_ast_expr_op_get_args(expr);
411	args = expr->u.op.args;
412	expr->u.op.args = NULL;
413	return args;
414}
415
416/* Set the arguments of the operation expression "expr" to "args",
417 * where the arguments of "args" may be missing
418 * due to a preceding call to isl_ast_expr_op_take_args.
419 * However, in this case, "expr" only has a single reference and
420 * then the call to isl_ast_expr_cow has no effect.
421 */
422static __isl_give isl_ast_expr *isl_ast_expr_op_restore_args(
423	__isl_take isl_ast_expr *expr, __isl_take isl_ast_expr_list *args)
424{
425	if (isl_ast_expr_check_op(expr) < 0 || !args)
426		goto error;
427	if (expr->u.op.args == args) {
428		isl_ast_expr_list_free(args);
429		return expr;
430	}
431
432	expr = isl_ast_expr_cow(expr);
433	if (!expr)
434		goto error;
435
436	isl_ast_expr_list_free(expr->u.op.args);
437	expr->u.op.args = args;
438
439	return expr;
440error:
441	isl_ast_expr_free(expr);
442	isl_ast_expr_list_free(args);
443	return NULL;
444}
445
446/* Add "arg" to the arguments of the operation expression "expr".
447 */
448__isl_give isl_ast_expr *isl_ast_expr_op_add_arg(__isl_take isl_ast_expr *expr,
449	__isl_take isl_ast_expr *arg)
450{
451	isl_ast_expr_list *args;
452
453	args = isl_ast_expr_op_take_args(expr);
454	args = isl_ast_expr_list_add(args, arg);
455	expr = isl_ast_expr_op_restore_args(expr, args);
456
457	return expr;
458}
459
460/* Replace the argument at position "pos" of "expr" by "arg".
461 */
462__isl_give isl_ast_expr *isl_ast_expr_set_op_arg(__isl_take isl_ast_expr *expr,
463	int pos, __isl_take isl_ast_expr *arg)
464{
465	isl_ast_expr_list *args;
466
467	args = isl_ast_expr_op_take_args(expr);
468	args = isl_ast_expr_list_set_at(args, pos, arg);
469	expr = isl_ast_expr_op_restore_args(expr, args);
470
471	return expr;
472}
473
474/* Are the lists of AST expressions "list1" and "list2" the same?
475 */
476static isl_bool isl_ast_expr_list_is_equal(__isl_keep isl_ast_expr_list *list1,
477	__isl_keep isl_ast_expr_list *list2)
478{
479	int i;
480	isl_size n1, n2;
481
482	if (!list1 || !list2)
483		return isl_bool_error;
484	if (list1 == list2)
485		return isl_bool_true;
486
487	n1 = isl_ast_expr_list_size(list1);
488	n2 = isl_ast_expr_list_size(list2);
489	if (n1 < 0 || n2 < 0)
490		return isl_bool_error;
491	if (n1 != n2)
492		return isl_bool_false;
493	for (i = 0; i < n1; ++i) {
494		isl_ast_expr *expr1, *expr2;
495		isl_bool equal;
496
497		expr1 = isl_ast_expr_list_get_at(list1, i);
498		expr2 = isl_ast_expr_list_get_at(list2, i);
499		equal = isl_ast_expr_is_equal(expr1, expr2);
500		isl_ast_expr_free(expr1);
501		isl_ast_expr_free(expr2);
502		if (equal < 0 || !equal)
503			return equal;
504	}
505
506	return isl_bool_true;
507}
508
509/* Is "expr1" equal to "expr2"?
510 */
511isl_bool isl_ast_expr_is_equal(__isl_keep isl_ast_expr *expr1,
512	__isl_keep isl_ast_expr *expr2)
513{
514	if (!expr1 || !expr2)
515		return isl_bool_error;
516
517	if (expr1 == expr2)
518		return isl_bool_true;
519	if (expr1->type != expr2->type)
520		return isl_bool_false;
521	switch (expr1->type) {
522	case isl_ast_expr_int:
523		return isl_val_eq(expr1->u.v, expr2->u.v);
524	case isl_ast_expr_id:
525		return isl_bool_ok(expr1->u.id == expr2->u.id);
526	case isl_ast_expr_op:
527		if (expr1->u.op.op != expr2->u.op.op)
528			return isl_bool_false;
529		return isl_ast_expr_list_is_equal(expr1->u.op.args,
530						expr2->u.op.args);
531	case isl_ast_expr_error:
532		return isl_bool_error;
533	}
534
535	isl_die(isl_ast_expr_get_ctx(expr1), isl_error_internal,
536		"unhandled case", return isl_bool_error);
537}
538
539/* Create a new id expression representing "id".
540 */
541__isl_give isl_ast_expr *isl_ast_expr_from_id(__isl_take isl_id *id)
542{
543	isl_ctx *ctx;
544	isl_ast_expr *expr;
545
546	if (!id)
547		return NULL;
548
549	ctx = isl_id_get_ctx(id);
550	expr = isl_calloc_type(ctx, isl_ast_expr);
551	if (!expr)
552		goto error;
553
554	expr->ctx = ctx;
555	isl_ctx_ref(ctx);
556	expr->ref = 1;
557	expr->type = isl_ast_expr_id;
558	expr->u.id = id;
559
560	return expr;
561error:
562	isl_id_free(id);
563	return NULL;
564}
565
566/* Create a new integer expression representing "i".
567 */
568__isl_give isl_ast_expr *isl_ast_expr_alloc_int_si(isl_ctx *ctx, int i)
569{
570	isl_ast_expr *expr;
571
572	expr = isl_calloc_type(ctx, isl_ast_expr);
573	if (!expr)
574		return NULL;
575
576	expr->ctx = ctx;
577	isl_ctx_ref(ctx);
578	expr->ref = 1;
579	expr->type = isl_ast_expr_int;
580	expr->u.v = isl_val_int_from_si(ctx, i);
581	if (!expr->u.v)
582		return isl_ast_expr_free(expr);
583
584	return expr;
585}
586
587/* Create a new integer expression representing "v".
588 */
589__isl_give isl_ast_expr *isl_ast_expr_from_val(__isl_take isl_val *v)
590{
591	isl_ctx *ctx;
592	isl_ast_expr *expr;
593
594	if (!v)
595		return NULL;
596	if (!isl_val_is_int(v))
597		isl_die(isl_val_get_ctx(v), isl_error_invalid,
598			"expecting integer value", goto error);
599
600	ctx = isl_val_get_ctx(v);
601	expr = isl_calloc_type(ctx, isl_ast_expr);
602	if (!expr)
603		goto error;
604
605	expr->ctx = ctx;
606	isl_ctx_ref(ctx);
607	expr->ref = 1;
608	expr->type = isl_ast_expr_int;
609	expr->u.v = v;
610
611	return expr;
612error:
613	isl_val_free(v);
614	return NULL;
615}
616
617/* Create an expression representing the unary operation "type" applied to
618 * "arg".
619 */
620__isl_give isl_ast_expr *isl_ast_expr_alloc_unary(
621	enum isl_ast_expr_op_type type, __isl_take isl_ast_expr *arg)
622{
623	isl_ctx *ctx;
624	isl_ast_expr *expr = NULL;
625	isl_ast_expr_list *args;
626
627	if (!arg)
628		return NULL;
629
630	ctx = isl_ast_expr_get_ctx(arg);
631	expr = isl_ast_expr_alloc_op(ctx, type, 1);
632
633	args = isl_ast_expr_op_take_args(expr);
634	args = isl_ast_expr_list_add(args, arg);
635	expr = isl_ast_expr_op_restore_args(expr, args);
636
637	return expr;
638}
639
640/* Create an expression representing the negation of "arg".
641 */
642__isl_give isl_ast_expr *isl_ast_expr_neg(__isl_take isl_ast_expr *arg)
643{
644	return isl_ast_expr_alloc_unary(isl_ast_expr_op_minus, arg);
645}
646
647/* Create an expression representing the address of "expr".
648 */
649__isl_give isl_ast_expr *isl_ast_expr_address_of(__isl_take isl_ast_expr *expr)
650{
651	if (!expr)
652		return NULL;
653
654	if (isl_ast_expr_get_type(expr) != isl_ast_expr_op ||
655	    isl_ast_expr_get_op_type(expr) != isl_ast_expr_op_access)
656		isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
657			"can only take address of access expressions",
658			return isl_ast_expr_free(expr));
659
660	return isl_ast_expr_alloc_unary(isl_ast_expr_op_address_of, expr);
661}
662
663/* Create an expression representing the binary operation "type"
664 * applied to "expr1" and "expr2".
665 */
666__isl_give isl_ast_expr *isl_ast_expr_alloc_binary(
667	enum isl_ast_expr_op_type type,
668	__isl_take isl_ast_expr *expr1, __isl_take isl_ast_expr *expr2)
669{
670	isl_ctx *ctx;
671	isl_ast_expr *expr = NULL;
672	isl_ast_expr_list *args;
673
674	if (!expr1 || !expr2)
675		goto error;
676
677	ctx = isl_ast_expr_get_ctx(expr1);
678	expr = isl_ast_expr_alloc_op(ctx, type, 2);
679
680	args = isl_ast_expr_op_take_args(expr);
681	args = isl_ast_expr_list_add(args, expr1);
682	args = isl_ast_expr_list_add(args, expr2);
683	expr = isl_ast_expr_op_restore_args(expr, args);
684
685	return expr;
686error:
687	isl_ast_expr_free(expr1);
688	isl_ast_expr_free(expr2);
689	return NULL;
690}
691
692/* Create an expression representing the sum of "expr1" and "expr2".
693 */
694__isl_give isl_ast_expr *isl_ast_expr_add(__isl_take isl_ast_expr *expr1,
695	__isl_take isl_ast_expr *expr2)
696{
697	return isl_ast_expr_alloc_binary(isl_ast_expr_op_add, expr1, expr2);
698}
699
700/* Create an expression representing the difference of "expr1" and "expr2".
701 */
702__isl_give isl_ast_expr *isl_ast_expr_sub(__isl_take isl_ast_expr *expr1,
703	__isl_take isl_ast_expr *expr2)
704{
705	return isl_ast_expr_alloc_binary(isl_ast_expr_op_sub, expr1, expr2);
706}
707
708/* Create an expression representing the product of "expr1" and "expr2".
709 */
710__isl_give isl_ast_expr *isl_ast_expr_mul(__isl_take isl_ast_expr *expr1,
711	__isl_take isl_ast_expr *expr2)
712{
713	return isl_ast_expr_alloc_binary(isl_ast_expr_op_mul, expr1, expr2);
714}
715
716/* Create an expression representing the quotient of "expr1" and "expr2".
717 */
718__isl_give isl_ast_expr *isl_ast_expr_div(__isl_take isl_ast_expr *expr1,
719	__isl_take isl_ast_expr *expr2)
720{
721	return isl_ast_expr_alloc_binary(isl_ast_expr_op_div, expr1, expr2);
722}
723
724/* Create an expression representing the quotient of the integer
725 * division of "expr1" by "expr2", where "expr1" is known to be
726 * non-negative.
727 */
728__isl_give isl_ast_expr *isl_ast_expr_pdiv_q(__isl_take isl_ast_expr *expr1,
729	__isl_take isl_ast_expr *expr2)
730{
731	return isl_ast_expr_alloc_binary(isl_ast_expr_op_pdiv_q, expr1, expr2);
732}
733
734/* Create an expression representing the remainder of the integer
735 * division of "expr1" by "expr2", where "expr1" is known to be
736 * non-negative.
737 */
738__isl_give isl_ast_expr *isl_ast_expr_pdiv_r(__isl_take isl_ast_expr *expr1,
739	__isl_take isl_ast_expr *expr2)
740{
741	return isl_ast_expr_alloc_binary(isl_ast_expr_op_pdiv_r, expr1, expr2);
742}
743
744/* Create an expression representing the conjunction of "expr1" and "expr2".
745 */
746__isl_give isl_ast_expr *isl_ast_expr_and(__isl_take isl_ast_expr *expr1,
747	__isl_take isl_ast_expr *expr2)
748{
749	return isl_ast_expr_alloc_binary(isl_ast_expr_op_and, expr1, expr2);
750}
751
752/* Create an expression representing the conjunction of "expr1" and "expr2",
753 * where "expr2" is evaluated only if "expr1" is evaluated to true.
754 */
755__isl_give isl_ast_expr *isl_ast_expr_and_then(__isl_take isl_ast_expr *expr1,
756	__isl_take isl_ast_expr *expr2)
757{
758	return isl_ast_expr_alloc_binary(isl_ast_expr_op_and_then, expr1, expr2);
759}
760
761/* Create an expression representing the disjunction of "expr1" and "expr2".
762 */
763__isl_give isl_ast_expr *isl_ast_expr_or(__isl_take isl_ast_expr *expr1,
764	__isl_take isl_ast_expr *expr2)
765{
766	return isl_ast_expr_alloc_binary(isl_ast_expr_op_or, expr1, expr2);
767}
768
769/* Create an expression representing the disjunction of "expr1" and "expr2",
770 * where "expr2" is evaluated only if "expr1" is evaluated to false.
771 */
772__isl_give isl_ast_expr *isl_ast_expr_or_else(__isl_take isl_ast_expr *expr1,
773	__isl_take isl_ast_expr *expr2)
774{
775	return isl_ast_expr_alloc_binary(isl_ast_expr_op_or_else, expr1, expr2);
776}
777
778/* Create an expression representing "expr1" less than or equal to "expr2".
779 */
780__isl_give isl_ast_expr *isl_ast_expr_le(__isl_take isl_ast_expr *expr1,
781	__isl_take isl_ast_expr *expr2)
782{
783	return isl_ast_expr_alloc_binary(isl_ast_expr_op_le, expr1, expr2);
784}
785
786/* Create an expression representing "expr1" less than "expr2".
787 */
788__isl_give isl_ast_expr *isl_ast_expr_lt(__isl_take isl_ast_expr *expr1,
789	__isl_take isl_ast_expr *expr2)
790{
791	return isl_ast_expr_alloc_binary(isl_ast_expr_op_lt, expr1, expr2);
792}
793
794/* Create an expression representing "expr1" greater than or equal to "expr2".
795 */
796__isl_give isl_ast_expr *isl_ast_expr_ge(__isl_take isl_ast_expr *expr1,
797	__isl_take isl_ast_expr *expr2)
798{
799	return isl_ast_expr_alloc_binary(isl_ast_expr_op_ge, expr1, expr2);
800}
801
802/* Create an expression representing "expr1" greater than "expr2".
803 */
804__isl_give isl_ast_expr *isl_ast_expr_gt(__isl_take isl_ast_expr *expr1,
805	__isl_take isl_ast_expr *expr2)
806{
807	return isl_ast_expr_alloc_binary(isl_ast_expr_op_gt, expr1, expr2);
808}
809
810/* Create an expression representing "expr1" equal to "expr2".
811 */
812__isl_give isl_ast_expr *isl_ast_expr_eq(__isl_take isl_ast_expr *expr1,
813	__isl_take isl_ast_expr *expr2)
814{
815	return isl_ast_expr_alloc_binary(isl_ast_expr_op_eq, expr1, expr2);
816}
817
818/* Create an expression of type "type" with as arguments "arg0" followed
819 * by "arguments".
820 */
821static __isl_give isl_ast_expr *ast_expr_with_arguments(
822	enum isl_ast_expr_op_type type, __isl_take isl_ast_expr *arg0,
823	__isl_take isl_ast_expr_list *arguments)
824{
825	arguments = isl_ast_expr_list_insert(arguments, 0, arg0);
826	return alloc_op(type, arguments);
827}
828
829/* Create an expression representing an access to "array" with index
830 * expressions "indices".
831 */
832__isl_give isl_ast_expr *isl_ast_expr_access(__isl_take isl_ast_expr *array,
833	__isl_take isl_ast_expr_list *indices)
834{
835	return ast_expr_with_arguments(isl_ast_expr_op_access, array, indices);
836}
837
838/* Create an expression representing a call to "function" with argument
839 * expressions "arguments".
840 */
841__isl_give isl_ast_expr *isl_ast_expr_call(__isl_take isl_ast_expr *function,
842	__isl_take isl_ast_expr_list *arguments)
843{
844	return ast_expr_with_arguments(isl_ast_expr_op_call, function, arguments);
845}
846
847/* Wrapper around isl_ast_expr_substitute_ids for use
848 * as an isl_ast_expr_list_map callback.
849 */
850static __isl_give isl_ast_expr *substitute_ids(__isl_take isl_ast_expr *expr,
851	void *user)
852{
853	isl_id_to_ast_expr *id2expr = user;
854
855	return isl_ast_expr_substitute_ids(expr,
856					    isl_id_to_ast_expr_copy(id2expr));
857}
858
859/* For each subexpression of "expr" of type isl_ast_expr_id,
860 * if it appears in "id2expr", then replace it by the corresponding
861 * expression.
862 */
863__isl_give isl_ast_expr *isl_ast_expr_substitute_ids(
864	__isl_take isl_ast_expr *expr, __isl_take isl_id_to_ast_expr *id2expr)
865{
866	isl_maybe_isl_ast_expr m;
867	isl_ast_expr_list *args;
868
869	if (!expr || !id2expr)
870		goto error;
871
872	switch (expr->type) {
873	case isl_ast_expr_int:
874		break;
875	case isl_ast_expr_id:
876		m = isl_id_to_ast_expr_try_get(id2expr, expr->u.id);
877		if (m.valid < 0)
878			goto error;
879		if (!m.valid)
880			break;
881		isl_ast_expr_free(expr);
882		expr = m.value;
883		break;
884	case isl_ast_expr_op:
885		args = isl_ast_expr_op_take_args(expr);
886		args = isl_ast_expr_list_map(args, &substitute_ids, id2expr);
887		expr = isl_ast_expr_op_restore_args(expr, args);
888		break;
889	case isl_ast_expr_error:
890		expr = isl_ast_expr_free(expr);
891		break;
892	}
893
894	isl_id_to_ast_expr_free(id2expr);
895	return expr;
896error:
897	isl_ast_expr_free(expr);
898	isl_id_to_ast_expr_free(id2expr);
899	return NULL;
900}
901
902isl_ctx *isl_ast_node_get_ctx(__isl_keep isl_ast_node *node)
903{
904	return node ? node->ctx : NULL;
905}
906
907enum isl_ast_node_type isl_ast_node_get_type(__isl_keep isl_ast_node *node)
908{
909	return node ? node->type : isl_ast_node_error;
910}
911
912__isl_give isl_ast_node *isl_ast_node_alloc(isl_ctx *ctx,
913	enum isl_ast_node_type type)
914{
915	isl_ast_node *node;
916
917	node = isl_calloc_type(ctx, isl_ast_node);
918	if (!node)
919		return NULL;
920
921	node->ctx = ctx;
922	isl_ctx_ref(ctx);
923	node->ref = 1;
924	node->type = type;
925
926	return node;
927}
928
929/* Create an if node with the given guard.
930 *
931 * The then body needs to be filled in later.
932 */
933__isl_give isl_ast_node *isl_ast_node_alloc_if(__isl_take isl_ast_expr *guard)
934{
935	isl_ast_node *node;
936
937	if (!guard)
938		return NULL;
939
940	node = isl_ast_node_alloc(isl_ast_expr_get_ctx(guard), isl_ast_node_if);
941	if (!node)
942		goto error;
943	node->u.i.guard = guard;
944
945	return node;
946error:
947	isl_ast_expr_free(guard);
948	return NULL;
949}
950
951/* Create a for node with the given iterator.
952 *
953 * The remaining fields need to be filled in later.
954 */
955__isl_give isl_ast_node *isl_ast_node_alloc_for(__isl_take isl_id *id)
956{
957	isl_ast_node *node;
958	isl_ctx *ctx;
959
960	if (!id)
961		return NULL;
962
963	ctx = isl_id_get_ctx(id);
964	node = isl_ast_node_alloc(ctx, isl_ast_node_for);
965	if (!node)
966		goto error;
967
968	node->u.f.iterator = isl_ast_expr_from_id(id);
969	if (!node->u.f.iterator)
970		return isl_ast_node_free(node);
971
972	return node;
973error:
974	isl_id_free(id);
975	return NULL;
976}
977
978/* Create a mark node, marking "node" with "id".
979 */
980__isl_give isl_ast_node *isl_ast_node_alloc_mark(__isl_take isl_id *id,
981	__isl_take isl_ast_node *node)
982{
983	isl_ctx *ctx;
984	isl_ast_node *mark;
985
986	if (!id || !node)
987		goto error;
988
989	ctx = isl_id_get_ctx(id);
990	mark = isl_ast_node_alloc(ctx, isl_ast_node_mark);
991	if (!mark)
992		goto error;
993
994	mark->u.m.mark = id;
995	mark->u.m.node = node;
996
997	return mark;
998error:
999	isl_id_free(id);
1000	isl_ast_node_free(node);
1001	return NULL;
1002}
1003
1004/* Create a user node evaluating "expr".
1005 */
1006__isl_give isl_ast_node *isl_ast_node_user_from_expr(
1007	__isl_take isl_ast_expr *expr)
1008{
1009	isl_ctx *ctx;
1010	isl_ast_node *node;
1011
1012	if (!expr)
1013		return NULL;
1014
1015	ctx = isl_ast_expr_get_ctx(expr);
1016	node = isl_ast_node_alloc(ctx, isl_ast_node_user);
1017	if (!node)
1018		goto error;
1019
1020	node->u.e.expr = expr;
1021
1022	return node;
1023error:
1024	isl_ast_expr_free(expr);
1025	return NULL;
1026}
1027
1028/* This is an alternative name for the function above.
1029 */
1030__isl_give isl_ast_node *isl_ast_node_alloc_user(__isl_take isl_ast_expr *expr)
1031{
1032	return isl_ast_node_user_from_expr(expr);
1033}
1034
1035/* Create a block node with the given children.
1036 */
1037__isl_give isl_ast_node *isl_ast_node_block_from_children(
1038	__isl_take isl_ast_node_list *list)
1039{
1040	isl_ast_node *node;
1041	isl_ctx *ctx;
1042
1043	if (!list)
1044		return NULL;
1045
1046	ctx = isl_ast_node_list_get_ctx(list);
1047	node = isl_ast_node_alloc(ctx, isl_ast_node_block);
1048	if (!node)
1049		goto error;
1050
1051	node->u.b.children = list;
1052
1053	return node;
1054error:
1055	isl_ast_node_list_free(list);
1056	return NULL;
1057}
1058
1059/* This is an alternative name for the function above.
1060 */
1061__isl_give isl_ast_node *isl_ast_node_alloc_block(
1062	__isl_take isl_ast_node_list *list)
1063{
1064	return isl_ast_node_block_from_children(list);
1065}
1066
1067/* Represent the given list of nodes as a single node, either by
1068 * extract the node from a single element list or by creating
1069 * a block node with the list of nodes as children.
1070 */
1071__isl_give isl_ast_node *isl_ast_node_from_ast_node_list(
1072	__isl_take isl_ast_node_list *list)
1073{
1074	isl_size n;
1075	isl_ast_node *node;
1076
1077	n = isl_ast_node_list_n_ast_node(list);
1078	if (n < 0)
1079		goto error;
1080	if (n != 1)
1081		return isl_ast_node_alloc_block(list);
1082
1083	node = isl_ast_node_list_get_ast_node(list, 0);
1084	isl_ast_node_list_free(list);
1085
1086	return node;
1087error:
1088	isl_ast_node_list_free(list);
1089	return NULL;
1090}
1091
1092__isl_give isl_ast_node *isl_ast_node_copy(__isl_keep isl_ast_node *node)
1093{
1094	if (!node)
1095		return NULL;
1096
1097	node->ref++;
1098	return node;
1099}
1100
1101/* Return a fresh copy of "node".
1102 *
1103 * In the case of a degenerate for node, take into account
1104 * that "cond" and "inc" are NULL.
1105 */
1106__isl_give isl_ast_node *isl_ast_node_dup(__isl_keep isl_ast_node *node)
1107{
1108	isl_ast_node *dup;
1109
1110	if (!node)
1111		return NULL;
1112
1113	dup = isl_ast_node_alloc(isl_ast_node_get_ctx(node), node->type);
1114	if (!dup)
1115		return NULL;
1116
1117	switch (node->type) {
1118	case isl_ast_node_if:
1119		dup->u.i.guard = isl_ast_expr_copy(node->u.i.guard);
1120		dup->u.i.then = isl_ast_node_copy(node->u.i.then);
1121		dup->u.i.else_node = isl_ast_node_copy(node->u.i.else_node);
1122		if (!dup->u.i.guard  || !dup->u.i.then ||
1123		    (node->u.i.else_node && !dup->u.i.else_node))
1124			return isl_ast_node_free(dup);
1125		break;
1126	case isl_ast_node_for:
1127		dup->u.f.degenerate = node->u.f.degenerate;
1128		dup->u.f.iterator = isl_ast_expr_copy(node->u.f.iterator);
1129		dup->u.f.init = isl_ast_expr_copy(node->u.f.init);
1130		dup->u.f.body = isl_ast_node_copy(node->u.f.body);
1131		if (!dup->u.f.iterator || !dup->u.f.init || !dup->u.f.body)
1132			return isl_ast_node_free(dup);
1133		if (node->u.f.degenerate)
1134			break;
1135		dup->u.f.cond = isl_ast_expr_copy(node->u.f.cond);
1136		dup->u.f.inc = isl_ast_expr_copy(node->u.f.inc);
1137		if (!dup->u.f.cond || !dup->u.f.inc)
1138			return isl_ast_node_free(dup);
1139		break;
1140	case isl_ast_node_block:
1141		dup->u.b.children = isl_ast_node_list_copy(node->u.b.children);
1142		if (!dup->u.b.children)
1143			return isl_ast_node_free(dup);
1144		break;
1145	case isl_ast_node_mark:
1146		dup->u.m.mark = isl_id_copy(node->u.m.mark);
1147		dup->u.m.node = isl_ast_node_copy(node->u.m.node);
1148		if (!dup->u.m.mark || !dup->u.m.node)
1149			return isl_ast_node_free(dup);
1150		break;
1151	case isl_ast_node_user:
1152		dup->u.e.expr = isl_ast_expr_copy(node->u.e.expr);
1153		if (!dup->u.e.expr)
1154			return isl_ast_node_free(dup);
1155		break;
1156	case isl_ast_node_error:
1157		break;
1158	}
1159
1160	if (!node->annotation)
1161		return dup;
1162	dup->annotation = isl_id_copy(node->annotation);
1163	if (!dup->annotation)
1164		return isl_ast_node_free(dup);
1165
1166	return dup;
1167}
1168
1169__isl_give isl_ast_node *isl_ast_node_cow(__isl_take isl_ast_node *node)
1170{
1171	if (!node)
1172		return NULL;
1173
1174	if (node->ref == 1)
1175		return node;
1176	node->ref--;
1177	return isl_ast_node_dup(node);
1178}
1179
1180__isl_null isl_ast_node *isl_ast_node_free(__isl_take isl_ast_node *node)
1181{
1182	if (!node)
1183		return NULL;
1184
1185	if (--node->ref > 0)
1186		return NULL;
1187
1188	switch (node->type) {
1189	case isl_ast_node_if:
1190		isl_ast_expr_free(node->u.i.guard);
1191		isl_ast_node_free(node->u.i.then);
1192		isl_ast_node_free(node->u.i.else_node);
1193		break;
1194	case isl_ast_node_for:
1195		isl_ast_expr_free(node->u.f.iterator);
1196		isl_ast_expr_free(node->u.f.init);
1197		isl_ast_expr_free(node->u.f.cond);
1198		isl_ast_expr_free(node->u.f.inc);
1199		isl_ast_node_free(node->u.f.body);
1200		break;
1201	case isl_ast_node_block:
1202		isl_ast_node_list_free(node->u.b.children);
1203		break;
1204	case isl_ast_node_mark:
1205		isl_id_free(node->u.m.mark);
1206		isl_ast_node_free(node->u.m.node);
1207		break;
1208	case isl_ast_node_user:
1209		isl_ast_expr_free(node->u.e.expr);
1210		break;
1211	case isl_ast_node_error:
1212		break;
1213	}
1214
1215	isl_id_free(node->annotation);
1216	isl_ctx_deref(node->ctx);
1217	free(node);
1218
1219	return NULL;
1220}
1221
1222/* Check that "node" is of type "type", printing "msg" if not.
1223 */
1224static isl_stat isl_ast_node_check_type(__isl_keep isl_ast_node *node,
1225	enum isl_ast_node_type type, const char *msg)
1226{
1227	if (!node)
1228		return isl_stat_error;
1229	if (node->type != type)
1230		isl_die(isl_ast_node_get_ctx(node), isl_error_invalid, msg,
1231			return isl_stat_error);
1232	return isl_stat_ok;
1233}
1234
1235/* Check that "node" is of type isl_ast_node_block.
1236 */
1237static isl_stat isl_ast_node_check_block(__isl_keep isl_ast_node *node)
1238{
1239	return isl_ast_node_check_type(node, isl_ast_node_block,
1240					"not a block node");
1241}
1242
1243/* Check that "node" is of type isl_ast_node_if.
1244 */
1245static isl_stat isl_ast_node_check_if(__isl_keep isl_ast_node *node)
1246{
1247	return isl_ast_node_check_type(node, isl_ast_node_if, "not an if node");
1248}
1249
1250/* Check that "node" is of type isl_ast_node_for.
1251 */
1252static isl_stat isl_ast_node_check_for(__isl_keep isl_ast_node *node)
1253{
1254	return isl_ast_node_check_type(node, isl_ast_node_for,
1255					"not a for node");
1256}
1257
1258/* Check that "node" is of type isl_ast_node_mark.
1259 */
1260static isl_stat isl_ast_node_check_mark(__isl_keep isl_ast_node *node)
1261{
1262	return isl_ast_node_check_type(node, isl_ast_node_mark,
1263					"not a mark node");
1264}
1265
1266/* Check that "node" is of type isl_ast_node_user.
1267 */
1268static isl_stat isl_ast_node_check_user(__isl_keep isl_ast_node *node)
1269{
1270	return isl_ast_node_check_type(node, isl_ast_node_user,
1271					"not a user node");
1272}
1273
1274#undef NODE_TYPE
1275#define NODE_TYPE	for
1276#undef FIELD_NAME
1277#define FIELD_NAME	init
1278#undef FIELD_TYPE
1279#define FIELD_TYPE	isl_ast_expr
1280#undef FIELD
1281#define FIELD		u.f.init
1282#include "isl_ast_node_set_field_templ.c"
1283
1284#undef NODE_TYPE
1285#define NODE_TYPE	for
1286#undef FIELD_NAME
1287#define FIELD_NAME	cond
1288#undef FIELD_TYPE
1289#define FIELD_TYPE	isl_ast_expr
1290#undef FIELD
1291#define FIELD		u.f.cond
1292#include "isl_ast_node_set_field_templ.c"
1293
1294#undef NODE_TYPE
1295#define NODE_TYPE	for
1296#undef FIELD_NAME
1297#define FIELD_NAME	inc
1298#undef FIELD_TYPE
1299#define FIELD_TYPE	isl_ast_expr
1300#undef FIELD
1301#define FIELD		u.f.inc
1302#include "isl_ast_node_set_field_templ.c"
1303
1304#undef NODE_TYPE
1305#define NODE_TYPE	for
1306#undef FIELD_NAME
1307#define FIELD_NAME	body
1308#undef FIELD_TYPE
1309#define FIELD_TYPE	isl_ast_node
1310#undef FIELD
1311#define FIELD		u.f.body
1312#include "isl_ast_node_set_field_templ.c"
1313
1314/* Return the body of the for-node "node",
1315 * This may be either a copy or the body itself
1316 * if there is only one reference to "node".
1317 * This allows the body to be modified inplace
1318 * if both "node" and its body have only a single reference.
1319 * The caller is not allowed to modify "node" between this call and
1320 * the subsequent call to isl_ast_node_for_restore_body.
1321 * The only exception is that isl_ast_node_free can be called instead.
1322 */
1323static __isl_give isl_ast_node *isl_ast_node_for_take_body(
1324	__isl_keep isl_ast_node *node)
1325{
1326	isl_ast_node *body;
1327
1328	if (isl_ast_node_check_for(node) < 0)
1329		return NULL;
1330	if (node->ref != 1)
1331		return isl_ast_node_for_get_body(node);
1332	body = node->u.f.body;
1333	node->u.f.body = NULL;
1334	return body;
1335}
1336
1337/* Set the body of the for-node "node" to "body",
1338 * where the body of "node" may be missing
1339 * due to a preceding call to isl_ast_node_for_take_body.
1340 * However, in this case, "node" only has a single reference.
1341 */
1342static __isl_give isl_ast_node *isl_ast_node_for_restore_body(
1343	__isl_take isl_ast_node *node, __isl_take isl_ast_node *body)
1344{
1345	return isl_ast_node_for_set_body(node, body);
1346}
1347
1348__isl_give isl_ast_node *isl_ast_node_for_get_body(
1349	__isl_keep isl_ast_node *node)
1350{
1351	if (isl_ast_node_check_for(node) < 0)
1352		return NULL;
1353	return isl_ast_node_copy(node->u.f.body);
1354}
1355
1356/* Mark the given for node as being degenerate.
1357 */
1358__isl_give isl_ast_node *isl_ast_node_for_mark_degenerate(
1359	__isl_take isl_ast_node *node)
1360{
1361	node = isl_ast_node_cow(node);
1362	if (!node)
1363		return NULL;
1364	node->u.f.degenerate = 1;
1365	return node;
1366}
1367
1368isl_bool isl_ast_node_for_is_degenerate(__isl_keep isl_ast_node *node)
1369{
1370	if (isl_ast_node_check_for(node) < 0)
1371		return isl_bool_error;
1372	return isl_bool_ok(node->u.f.degenerate);
1373}
1374
1375__isl_give isl_ast_expr *isl_ast_node_for_get_iterator(
1376	__isl_keep isl_ast_node *node)
1377{
1378	if (isl_ast_node_check_for(node) < 0)
1379		return NULL;
1380	return isl_ast_expr_copy(node->u.f.iterator);
1381}
1382
1383__isl_give isl_ast_expr *isl_ast_node_for_get_init(
1384	__isl_keep isl_ast_node *node)
1385{
1386	if (isl_ast_node_check_for(node) < 0)
1387		return NULL;
1388	return isl_ast_expr_copy(node->u.f.init);
1389}
1390
1391/* Return the condition expression of the given for node.
1392 *
1393 * If the for node is degenerate, then the condition is not explicitly
1394 * stored in the node.  Instead, it is constructed as
1395 *
1396 *	iterator <= init
1397 */
1398__isl_give isl_ast_expr *isl_ast_node_for_get_cond(
1399	__isl_keep isl_ast_node *node)
1400{
1401	if (isl_ast_node_check_for(node) < 0)
1402		return NULL;
1403	if (!node->u.f.degenerate)
1404		return isl_ast_expr_copy(node->u.f.cond);
1405
1406	return isl_ast_expr_alloc_binary(isl_ast_expr_op_le,
1407				isl_ast_expr_copy(node->u.f.iterator),
1408				isl_ast_expr_copy(node->u.f.init));
1409}
1410
1411/* Return the increment of the given for node.
1412 *
1413 * If the for node is degenerate, then the increment is not explicitly
1414 * stored in the node.  We simply return "1".
1415 */
1416__isl_give isl_ast_expr *isl_ast_node_for_get_inc(
1417	__isl_keep isl_ast_node *node)
1418{
1419	if (isl_ast_node_check_for(node) < 0)
1420		return NULL;
1421	if (!node->u.f.degenerate)
1422		return isl_ast_expr_copy(node->u.f.inc);
1423	return isl_ast_expr_alloc_int_si(isl_ast_node_get_ctx(node), 1);
1424}
1425
1426#undef NODE_TYPE
1427#define NODE_TYPE	if
1428#undef FIELD_NAME
1429#define FIELD_NAME	then
1430#undef FIELD_TYPE
1431#define FIELD_TYPE	isl_ast_node
1432#undef FIELD
1433#define FIELD		u.i.then
1434#include "isl_ast_node_set_field_templ.c"
1435
1436/* Return the then-branch of the if-node "node",
1437 * This may be either a copy or the branch itself
1438 * if there is only one reference to "node".
1439 * This allows the branch to be modified inplace
1440 * if both "node" and its then-branch have only a single reference.
1441 * The caller is not allowed to modify "node" between this call and
1442 * the subsequent call to isl_ast_node_if_restore_then_node.
1443 * The only exception is that isl_ast_node_free can be called instead.
1444 */
1445static __isl_give isl_ast_node *isl_ast_node_if_take_then_node(
1446	__isl_keep isl_ast_node *node)
1447{
1448	isl_ast_node *then_node;
1449
1450	if (isl_ast_node_check_if(node) < 0)
1451		return NULL;
1452	if (node->ref != 1)
1453		return isl_ast_node_if_get_then_node(node);
1454	then_node = node->u.i.then;
1455	node->u.i.then = NULL;
1456	return then_node;
1457}
1458
1459/* Set the then-branch of the if-node "node" to "child",
1460 * where the then-branch of "node" may be missing
1461 * due to a preceding call to isl_ast_node_if_take_then_node.
1462 * However, in this case, "node" only has a single reference.
1463 */
1464static __isl_give isl_ast_node *isl_ast_node_if_restore_then_node(
1465	__isl_take isl_ast_node *node, __isl_take isl_ast_node *child)
1466{
1467	return isl_ast_node_if_set_then(node, child);
1468}
1469
1470/* Return the then-node of the given if-node.
1471 */
1472__isl_give isl_ast_node *isl_ast_node_if_get_then_node(
1473	__isl_keep isl_ast_node *node)
1474{
1475	if (isl_ast_node_check_if(node) < 0)
1476		return NULL;
1477	return isl_ast_node_copy(node->u.i.then);
1478}
1479
1480/* This is an alternative name for the function above.
1481 */
1482__isl_give isl_ast_node *isl_ast_node_if_get_then(
1483	__isl_keep isl_ast_node *node)
1484{
1485	return isl_ast_node_if_get_then_node(node);
1486}
1487
1488/* Does the given if-node have an else-node?
1489 */
1490isl_bool isl_ast_node_if_has_else_node(__isl_keep isl_ast_node *node)
1491{
1492	if (isl_ast_node_check_if(node) < 0)
1493		return isl_bool_error;
1494	return isl_bool_ok(node->u.i.else_node != NULL);
1495}
1496
1497/* This is an alternative name for the function above.
1498 */
1499isl_bool isl_ast_node_if_has_else(__isl_keep isl_ast_node *node)
1500{
1501	return isl_ast_node_if_has_else_node(node);
1502}
1503
1504/* Return the else-node of the given if-node,
1505 * assuming there is one.
1506 */
1507__isl_give isl_ast_node *isl_ast_node_if_get_else_node(
1508	__isl_keep isl_ast_node *node)
1509{
1510	if (isl_ast_node_check_if(node) < 0)
1511		return NULL;
1512	return isl_ast_node_copy(node->u.i.else_node);
1513}
1514
1515/* This is an alternative name for the function above.
1516 */
1517__isl_give isl_ast_node *isl_ast_node_if_get_else(
1518	__isl_keep isl_ast_node *node)
1519{
1520	return isl_ast_node_if_get_else_node(node);
1521}
1522
1523#undef NODE_TYPE
1524#define NODE_TYPE	if
1525#undef FIELD_NAME
1526#define FIELD_NAME	else_node
1527#undef FIELD_TYPE
1528#define FIELD_TYPE	isl_ast_node
1529#undef FIELD
1530#define FIELD		u.i.else_node
1531static
1532#include "isl_ast_node_set_field_templ.c"
1533
1534/* Return the else-branch of the if-node "node",
1535 * This may be either a copy or the branch itself
1536 * if there is only one reference to "node".
1537 * This allows the branch to be modified inplace
1538 * if both "node" and its else-branch have only a single reference.
1539 * The caller is not allowed to modify "node" between this call and
1540 * the subsequent call to isl_ast_node_if_restore_else_node.
1541 * The only exception is that isl_ast_node_free can be called instead.
1542 */
1543static __isl_give isl_ast_node *isl_ast_node_if_take_else_node(
1544	__isl_keep isl_ast_node *node)
1545{
1546	isl_ast_node *else_node;
1547
1548	if (isl_ast_node_check_if(node) < 0)
1549		return NULL;
1550	if (node->ref != 1)
1551		return isl_ast_node_if_get_else_node(node);
1552	else_node = node->u.i.else_node;
1553	node->u.i.else_node = NULL;
1554	return else_node;
1555}
1556
1557/* Set the else-branch of the if-node "node" to "child",
1558 * where the else-branch of "node" may be missing
1559 * due to a preceding call to isl_ast_node_if_take_else_node.
1560 * However, in this case, "node" only has a single reference.
1561 */
1562static __isl_give isl_ast_node *isl_ast_node_if_restore_else_node(
1563	__isl_take isl_ast_node *node, __isl_take isl_ast_node *child)
1564{
1565	return isl_ast_node_if_set_else_node(node, child);
1566}
1567
1568__isl_give isl_ast_expr *isl_ast_node_if_get_cond(
1569	__isl_keep isl_ast_node *node)
1570{
1571	if (isl_ast_node_check_if(node) < 0)
1572		return NULL;
1573	return isl_ast_expr_copy(node->u.i.guard);
1574}
1575
1576__isl_give isl_ast_node_list *isl_ast_node_block_get_children(
1577	__isl_keep isl_ast_node *node)
1578{
1579	if (isl_ast_node_check_block(node) < 0)
1580		return NULL;
1581	return isl_ast_node_list_copy(node->u.b.children);
1582}
1583
1584#undef NODE_TYPE
1585#define NODE_TYPE	block
1586#undef FIELD_NAME
1587#define FIELD_NAME	children
1588#undef FIELD_TYPE
1589#define FIELD_TYPE	isl_ast_node_list
1590#undef FIELD
1591#define FIELD		u.b.children
1592static
1593#include "isl_ast_node_set_field_templ.c"
1594
1595/* Return the children of the block-node "node",
1596 * This may be either a copy or the children themselves
1597 * if there is only one reference to "node".
1598 * This allows the children to be modified inplace
1599 * if both "node" and its children have only a single reference.
1600 * The caller is not allowed to modify "node" between this call and
1601 * the subsequent call to isl_ast_node_block_restore_children.
1602 * The only exception is that isl_ast_node_free can be called instead.
1603 */
1604static __isl_give isl_ast_node_list *isl_ast_node_block_take_children(
1605	__isl_keep isl_ast_node *node)
1606{
1607	isl_ast_node_list *children;
1608
1609	if (isl_ast_node_check_block(node) < 0)
1610		return NULL;
1611	if (node->ref != 1)
1612		return isl_ast_node_block_get_children(node);
1613	children = node->u.b.children;
1614	node->u.b.children = NULL;
1615	return children;
1616}
1617
1618/* Set the children of the block-node "node" to "children",
1619 * where the children of "node" may be missing
1620 * due to a preceding call to isl_ast_node_block_take_children.
1621 * However, in this case, "node" only has a single reference.
1622 */
1623static __isl_give isl_ast_node *isl_ast_node_block_restore_children(
1624	__isl_take isl_ast_node *node, __isl_take isl_ast_node_list *children)
1625{
1626	return isl_ast_node_block_set_children(node, children);
1627}
1628
1629__isl_give isl_ast_expr *isl_ast_node_user_get_expr(
1630	__isl_keep isl_ast_node *node)
1631{
1632	if (isl_ast_node_check_user(node) < 0)
1633		return NULL;
1634
1635	return isl_ast_expr_copy(node->u.e.expr);
1636}
1637
1638/* Return the mark identifier of the mark node "node".
1639 */
1640__isl_give isl_id *isl_ast_node_mark_get_id(__isl_keep isl_ast_node *node)
1641{
1642	if (isl_ast_node_check_mark(node) < 0)
1643		return NULL;
1644
1645	return isl_id_copy(node->u.m.mark);
1646}
1647
1648/* Return the node marked by mark node "node".
1649 */
1650__isl_give isl_ast_node *isl_ast_node_mark_get_node(
1651	__isl_keep isl_ast_node *node)
1652{
1653	if (isl_ast_node_check_mark(node) < 0)
1654		return NULL;
1655
1656	return isl_ast_node_copy(node->u.m.node);
1657}
1658
1659#undef NODE_TYPE
1660#define NODE_TYPE	mark
1661#undef FIELD_NAME
1662#define FIELD_NAME	node
1663#undef FIELD_TYPE
1664#define FIELD_TYPE	isl_ast_node
1665#undef FIELD
1666#define FIELD		u.m.node
1667static
1668#include "isl_ast_node_set_field_templ.c"
1669
1670/* Return the child of the mark-node "node",
1671 * This may be either a copy or the child itself
1672 * if there is only one reference to "node".
1673 * This allows the child to be modified inplace
1674 * if both "node" and its child have only a single reference.
1675 * The caller is not allowed to modify "node" between this call and
1676 * the subsequent call to isl_ast_node_mark_restore_node.
1677 * The only exception is that isl_ast_node_free can be called instead.
1678 */
1679static __isl_give isl_ast_node *isl_ast_node_mark_take_node(
1680	__isl_keep isl_ast_node *node)
1681{
1682	isl_ast_node *child;
1683
1684	if (isl_ast_node_check_mark(node) < 0)
1685		return NULL;
1686	if (node->ref != 1)
1687		return isl_ast_node_mark_get_node(node);
1688	child = node->u.m.node;
1689	node->u.m.node = NULL;
1690	return child;
1691}
1692
1693/* Set the child of the mark-node "node" to "child",
1694 * where the child of "node" may be missing
1695 * due to a preceding call to isl_ast_node_mark_take_node.
1696 * However, in this case, "node" only has a single reference.
1697 */
1698static __isl_give isl_ast_node *isl_ast_node_mark_restore_node(
1699	__isl_take isl_ast_node *node, __isl_take isl_ast_node *child)
1700{
1701	return isl_ast_node_mark_set_node(node, child);
1702}
1703
1704__isl_give isl_id *isl_ast_node_get_annotation(__isl_keep isl_ast_node *node)
1705{
1706	return node ? isl_id_copy(node->annotation) : NULL;
1707}
1708
1709/* Check that "node" is of any type.
1710 * That is, simply check that it is a valid node.
1711 */
1712static isl_stat isl_ast_node_check_any(__isl_keep isl_ast_node *node)
1713{
1714	return isl_stat_non_null(node);
1715}
1716
1717#undef NODE_TYPE
1718#define NODE_TYPE	any
1719#undef FIELD_NAME
1720#define FIELD_NAME	annotation
1721#undef FIELD_TYPE
1722#define FIELD_TYPE	isl_id
1723#undef FIELD
1724#define FIELD		annotation
1725static
1726#include "isl_ast_node_set_field_templ.c"
1727
1728/* Replace node->annotation by "annotation".
1729 */
1730__isl_give isl_ast_node *isl_ast_node_set_annotation(
1731	__isl_take isl_ast_node *node, __isl_take isl_id *annotation)
1732{
1733	return isl_ast_node_any_set_annotation(node, annotation);
1734}
1735
1736static __isl_give isl_ast_node *traverse(__isl_take isl_ast_node *node,
1737	__isl_give isl_ast_node *(*enter)(__isl_take isl_ast_node *node,
1738		int *more, void *user),
1739	__isl_give isl_ast_node *(*leave)(__isl_take isl_ast_node *node,
1740		void *user),
1741	void *user);
1742
1743/* Traverse the elements of "list" and all their descendants
1744 * in depth first preorder.  Call "enter" whenever a node is entered and "leave"
1745 * whenever a node is left.
1746 *
1747 * Return the updated node.
1748 */
1749static __isl_give isl_ast_node_list *traverse_list(
1750	__isl_take isl_ast_node_list *list,
1751	__isl_give isl_ast_node *(*enter)(__isl_take isl_ast_node *node,
1752		int *more, void *user),
1753	__isl_give isl_ast_node *(*leave)(__isl_take isl_ast_node *node,
1754		void *user),
1755	void *user)
1756{
1757	int i;
1758	isl_size n;
1759
1760	n = isl_ast_node_list_size(list);
1761	if (n < 0)
1762		return isl_ast_node_list_free(list);
1763
1764	for (i = 0; i < n; ++i) {
1765		isl_ast_node *node;
1766
1767		node = isl_ast_node_list_get_at(list, i);
1768		node = traverse(node, enter, leave, user);
1769		list = isl_ast_node_list_set_at(list, i, node);
1770	}
1771
1772	return list;
1773}
1774
1775/* Traverse the descendants of "node" (including the node itself)
1776 * in depth first preorder.  Call "enter" whenever a node is entered and "leave"
1777 * whenever a node is left.
1778 *
1779 * If "enter" sets the "more" argument to zero, then the subtree rooted
1780 * at the given node is skipped.
1781 *
1782 * Return the updated node.
1783 */
1784static __isl_give isl_ast_node *traverse(__isl_take isl_ast_node *node,
1785	__isl_give isl_ast_node *(*enter)(__isl_take isl_ast_node *node,
1786		int *more, void *user),
1787	__isl_give isl_ast_node *(*leave)(__isl_take isl_ast_node *node,
1788		void *user),
1789	void *user)
1790{
1791	int more;
1792	isl_bool has_else;
1793	isl_ast_node *child;
1794	isl_ast_node_list *children;
1795
1796	node = enter(node, &more, user);
1797	if (!node)
1798		return NULL;
1799	if (!more)
1800		return node;
1801
1802	switch (node->type) {
1803	case isl_ast_node_for:
1804		child = isl_ast_node_for_take_body(node);
1805		child = traverse(child, enter, leave, user);
1806		node = isl_ast_node_for_restore_body(node, child);
1807		return leave(node, user);
1808	case isl_ast_node_if:
1809		child = isl_ast_node_if_take_then_node(node);
1810		child = traverse(child, enter, leave, user);
1811		node = isl_ast_node_if_restore_then_node(node, child);
1812		has_else = isl_ast_node_if_has_else_node(node);
1813		if (has_else < 0)
1814			return isl_ast_node_free(node);
1815		if (!has_else)
1816			return leave(node, user);
1817		child = isl_ast_node_if_take_else_node(node);
1818		child = traverse(child, enter, leave, user);
1819		node = isl_ast_node_if_restore_else_node(node, child);
1820		return leave(node, user);
1821	case isl_ast_node_block:
1822		children = isl_ast_node_block_take_children(node);
1823		children = traverse_list(children, enter, leave, user);
1824		node = isl_ast_node_block_restore_children(node, children);
1825		return leave(node, user);
1826	case isl_ast_node_mark:
1827		child = isl_ast_node_mark_take_node(node);
1828		child = traverse(child, enter, leave, user);
1829		node = isl_ast_node_mark_restore_node(node, child);
1830		return leave(node, user);
1831	case isl_ast_node_user:
1832		return leave(node, user);
1833	case isl_ast_node_error:
1834		return isl_ast_node_free(node);
1835	}
1836
1837	return node;
1838}
1839
1840/* Internal data structure storing the arguments of
1841 * isl_ast_node_foreach_descendant_top_down.
1842 */
1843struct isl_ast_node_preorder_data {
1844	isl_bool (*fn)(__isl_keep isl_ast_node *node, void *user);
1845	void *user;
1846};
1847
1848/* Enter "node" and set *more to continue traversing its descendants.
1849 *
1850 * In the case of a depth first preorder traversal, call data->fn and
1851 * let it decide whether to continue.
1852 */
1853static __isl_give isl_ast_node *preorder_enter(__isl_take isl_ast_node *node,
1854	int *more, void *user)
1855{
1856	struct isl_ast_node_preorder_data *data = user;
1857	isl_bool m;
1858
1859	if (!node)
1860		return NULL;
1861	m = data->fn(node, data->user);
1862	if (m < 0)
1863		return isl_ast_node_free(node);
1864	*more = m;
1865	return node;
1866}
1867
1868/* Leave "node".
1869 *
1870 * In the case of a depth first preorder traversal, nothing needs to be done.
1871 */
1872static __isl_give isl_ast_node *preorder_leave(__isl_take isl_ast_node *node,
1873	void *user)
1874{
1875	return node;
1876}
1877
1878/* Traverse the descendants of "node" (including the node itself)
1879 * in depth first preorder.
1880 *
1881 * If "fn" returns isl_bool_error on any of the nodes, then the traversal
1882 * is aborted.
1883 * If "fn" returns isl_bool_false on any of the nodes, then the subtree rooted
1884 * at that node is skipped.
1885 *
1886 * Return isl_stat_ok on success and isl_stat_error on failure.
1887 */
1888isl_stat isl_ast_node_foreach_descendant_top_down(
1889	__isl_keep isl_ast_node *node,
1890	isl_bool (*fn)(__isl_keep isl_ast_node *node, void *user), void *user)
1891{
1892	struct isl_ast_node_preorder_data data = { fn, user };
1893
1894	node = isl_ast_node_copy(node);
1895	node = traverse(node, &preorder_enter, &preorder_leave, &data);
1896	isl_ast_node_free(node);
1897
1898	return isl_stat_non_null(node);
1899}
1900
1901/* Internal data structure storing the arguments of
1902 * isl_ast_node_map_descendant_bottom_up.
1903 */
1904struct isl_ast_node_postorder_data {
1905	__isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
1906		void *user);
1907	void *user;
1908};
1909
1910/* Enter "node" and set *more to continue traversing its descendants.
1911 *
1912 * In the case of a depth-first post-order traversal,
1913 * nothing needs to be done and traversal always continues.
1914 */
1915static __isl_give isl_ast_node *postorder_enter(__isl_take isl_ast_node *node,
1916	int *more, void *user)
1917{
1918	*more = 1;
1919	return node;
1920}
1921
1922/* Leave "node".
1923 *
1924 * In the case of a depth-first post-order traversal, call data->fn.
1925 */
1926static __isl_give isl_ast_node *postorder_leave(__isl_take isl_ast_node *node,
1927	void *user)
1928{
1929	struct isl_ast_node_postorder_data *data = user;
1930
1931	if (!node)
1932		return NULL;
1933
1934	node = data->fn(node, data->user);
1935	return node;
1936}
1937
1938/* Traverse the descendants of "node" (including the node itself)
1939 * in depth-first post-order, where the user callback is allowed to modify the
1940 * visited node.
1941 *
1942 * Return the updated node.
1943 */
1944__isl_give isl_ast_node *isl_ast_node_map_descendant_bottom_up(
1945	__isl_take isl_ast_node *node,
1946	__isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
1947		void *user), void *user)
1948{
1949	struct isl_ast_node_postorder_data data = { fn, user };
1950
1951	return traverse(node, &postorder_enter, &postorder_leave, &data);
1952}
1953
1954/* Textual C representation of the various operators.
1955 */
1956static char *op_str_c[] = {
1957	[isl_ast_expr_op_and] = "&&",
1958	[isl_ast_expr_op_and_then] = "&&",
1959	[isl_ast_expr_op_or] = "||",
1960	[isl_ast_expr_op_or_else] = "||",
1961	[isl_ast_expr_op_max] = "max",
1962	[isl_ast_expr_op_min] = "min",
1963	[isl_ast_expr_op_minus] = "-",
1964	[isl_ast_expr_op_add] = "+",
1965	[isl_ast_expr_op_sub] = "-",
1966	[isl_ast_expr_op_mul] = "*",
1967	[isl_ast_expr_op_fdiv_q] = "floord",
1968	[isl_ast_expr_op_pdiv_q] = "/",
1969	[isl_ast_expr_op_pdiv_r] = "%",
1970	[isl_ast_expr_op_zdiv_r] = "%",
1971	[isl_ast_expr_op_div] = "/",
1972	[isl_ast_expr_op_eq] = "==",
1973	[isl_ast_expr_op_le] = "<=",
1974	[isl_ast_expr_op_ge] = ">=",
1975	[isl_ast_expr_op_lt] = "<",
1976	[isl_ast_expr_op_gt] = ">",
1977	[isl_ast_expr_op_member] = ".",
1978	[isl_ast_expr_op_address_of] = "&"
1979};
1980
1981/* Precedence in C of the various operators.
1982 * Based on http://en.wikipedia.org/wiki/Operators_in_C_and_C++
1983 * Lowest value means highest precedence.
1984 */
1985static int op_prec[] = {
1986	[isl_ast_expr_op_and] = 13,
1987	[isl_ast_expr_op_and_then] = 13,
1988	[isl_ast_expr_op_or] = 14,
1989	[isl_ast_expr_op_or_else] = 14,
1990	[isl_ast_expr_op_max] = 2,
1991	[isl_ast_expr_op_min] = 2,
1992	[isl_ast_expr_op_minus] = 3,
1993	[isl_ast_expr_op_add] = 6,
1994	[isl_ast_expr_op_sub] = 6,
1995	[isl_ast_expr_op_mul] = 5,
1996	[isl_ast_expr_op_div] = 5,
1997	[isl_ast_expr_op_fdiv_q] = 2,
1998	[isl_ast_expr_op_pdiv_q] = 5,
1999	[isl_ast_expr_op_pdiv_r] = 5,
2000	[isl_ast_expr_op_zdiv_r] = 5,
2001	[isl_ast_expr_op_cond] = 15,
2002	[isl_ast_expr_op_select] = 15,
2003	[isl_ast_expr_op_eq] = 9,
2004	[isl_ast_expr_op_le] = 8,
2005	[isl_ast_expr_op_ge] = 8,
2006	[isl_ast_expr_op_lt] = 8,
2007	[isl_ast_expr_op_gt] = 8,
2008	[isl_ast_expr_op_call] = 2,
2009	[isl_ast_expr_op_access] = 2,
2010	[isl_ast_expr_op_member] = 2,
2011	[isl_ast_expr_op_address_of] = 3
2012};
2013
2014/* Is the operator left-to-right associative?
2015 */
2016static int op_left[] = {
2017	[isl_ast_expr_op_and] = 1,
2018	[isl_ast_expr_op_and_then] = 1,
2019	[isl_ast_expr_op_or] = 1,
2020	[isl_ast_expr_op_or_else] = 1,
2021	[isl_ast_expr_op_max] = 1,
2022	[isl_ast_expr_op_min] = 1,
2023	[isl_ast_expr_op_minus] = 0,
2024	[isl_ast_expr_op_add] = 1,
2025	[isl_ast_expr_op_sub] = 1,
2026	[isl_ast_expr_op_mul] = 1,
2027	[isl_ast_expr_op_div] = 1,
2028	[isl_ast_expr_op_fdiv_q] = 1,
2029	[isl_ast_expr_op_pdiv_q] = 1,
2030	[isl_ast_expr_op_pdiv_r] = 1,
2031	[isl_ast_expr_op_zdiv_r] = 1,
2032	[isl_ast_expr_op_cond] = 0,
2033	[isl_ast_expr_op_select] = 0,
2034	[isl_ast_expr_op_eq] = 1,
2035	[isl_ast_expr_op_le] = 1,
2036	[isl_ast_expr_op_ge] = 1,
2037	[isl_ast_expr_op_lt] = 1,
2038	[isl_ast_expr_op_gt] = 1,
2039	[isl_ast_expr_op_call] = 1,
2040	[isl_ast_expr_op_access] = 1,
2041	[isl_ast_expr_op_member] = 1,
2042	[isl_ast_expr_op_address_of] = 0
2043};
2044
2045static int is_and(enum isl_ast_expr_op_type op)
2046{
2047	return op == isl_ast_expr_op_and || op == isl_ast_expr_op_and_then;
2048}
2049
2050static int is_or(enum isl_ast_expr_op_type op)
2051{
2052	return op == isl_ast_expr_op_or || op == isl_ast_expr_op_or_else;
2053}
2054
2055static int is_add_sub(enum isl_ast_expr_op_type op)
2056{
2057	return op == isl_ast_expr_op_add || op == isl_ast_expr_op_sub;
2058}
2059
2060static int is_div_mod(enum isl_ast_expr_op_type op)
2061{
2062	return op == isl_ast_expr_op_div ||
2063	       op == isl_ast_expr_op_pdiv_r ||
2064	       op == isl_ast_expr_op_zdiv_r;
2065}
2066
2067static __isl_give isl_printer *print_ast_expr_c(__isl_take isl_printer *p,
2068	__isl_keep isl_ast_expr *expr);
2069
2070/* Do we need/want parentheses around "expr" as a subexpression of
2071 * an "op" operation?  If "left" is set, then "expr" is the left-most
2072 * operand.
2073 *
2074 * We only need parentheses if "expr" represents an operation.
2075 *
2076 * If op has a higher precedence than expr->u.op.op, then we need
2077 * parentheses.
2078 * If op and expr->u.op.op have the same precedence, but the operations
2079 * are performed in an order that is different from the associativity,
2080 * then we need parentheses.
2081 *
2082 * An and inside an or technically does not require parentheses,
2083 * but some compilers complain about that, so we add them anyway.
2084 *
2085 * Computations such as "a / b * c" and "a % b + c" can be somewhat
2086 * difficult to read, so we add parentheses for those as well.
2087 */
2088static int sub_expr_need_parens(enum isl_ast_expr_op_type op,
2089	__isl_keep isl_ast_expr *expr, int left)
2090{
2091	if (expr->type != isl_ast_expr_op)
2092		return 0;
2093
2094	if (op_prec[expr->u.op.op] > op_prec[op])
2095		return 1;
2096	if (op_prec[expr->u.op.op] == op_prec[op] && left != op_left[op])
2097		return 1;
2098
2099	if (is_or(op) && is_and(expr->u.op.op))
2100		return 1;
2101	if (op == isl_ast_expr_op_mul && expr->u.op.op != isl_ast_expr_op_mul &&
2102	    op_prec[expr->u.op.op] == op_prec[op])
2103		return 1;
2104	if (is_add_sub(op) && is_div_mod(expr->u.op.op))
2105		return 1;
2106
2107	return 0;
2108}
2109
2110/* Print the subexpression at position "pos" of operation expression "expr"
2111 * in C format.
2112 * If "left" is set, then "expr" is the left-most operand.
2113 */
2114static __isl_give isl_printer *print_sub_expr_c(__isl_take isl_printer *p,
2115	__isl_keep isl_ast_expr *expr, int pos, int left)
2116{
2117	int need_parens;
2118	isl_ast_expr *arg;
2119
2120	if (!expr)
2121		return isl_printer_free(p);
2122
2123	arg = isl_ast_expr_list_get_at(expr->u.op.args, pos);
2124	need_parens = sub_expr_need_parens(expr->u.op.op, arg, left);
2125
2126	if (need_parens)
2127		p = isl_printer_print_str(p, "(");
2128	p = print_ast_expr_c(p, arg);
2129	if (need_parens)
2130		p = isl_printer_print_str(p, ")");
2131
2132	isl_ast_expr_free(arg);
2133
2134	return p;
2135}
2136
2137#define isl_ast_expr_op_last	isl_ast_expr_op_address_of
2138
2139/* Data structure that holds the user-specified textual
2140 * representations for the operators in C format.
2141 * The entries are either NULL or copies of strings.
2142 * A NULL entry means that the default name should be used.
2143 */
2144struct isl_ast_expr_op_names {
2145	char *op_str[isl_ast_expr_op_last + 1];
2146};
2147
2148/* Create an empty struct isl_ast_expr_op_names.
2149 */
2150static void *create_names(isl_ctx *ctx)
2151{
2152	return isl_calloc_type(ctx, struct isl_ast_expr_op_names);
2153}
2154
2155/* Free a struct isl_ast_expr_op_names along with all memory
2156 * owned by the struct.
2157 */
2158static void free_names(void *user)
2159{
2160	int i;
2161	struct isl_ast_expr_op_names *names = user;
2162
2163	if (!user)
2164		return;
2165
2166	for (i = 0; i <= isl_ast_expr_op_last; ++i)
2167		free(names->op_str[i]);
2168	free(user);
2169}
2170
2171/* Create an identifier that is used to store
2172 * an isl_ast_expr_op_names note.
2173 */
2174static __isl_give isl_id *names_id(isl_ctx *ctx)
2175{
2176	return isl_id_alloc(ctx, "isl_ast_expr_op_type_names", NULL);
2177}
2178
2179/* Ensure that "p" has a note identified by "id".
2180 * If there is no such note yet, then it is created by "note_create" and
2181 * scheduled do be freed by "note_free".
2182 */
2183static __isl_give isl_printer *alloc_note(__isl_take isl_printer *p,
2184	__isl_keep isl_id *id, void *(*note_create)(isl_ctx *),
2185	void (*note_free)(void *))
2186{
2187	isl_ctx *ctx;
2188	isl_id *note_id;
2189	isl_bool has_note;
2190	void *note;
2191
2192	has_note = isl_printer_has_note(p, id);
2193	if (has_note < 0)
2194		return isl_printer_free(p);
2195	if (has_note)
2196		return p;
2197
2198	ctx = isl_printer_get_ctx(p);
2199	note = note_create(ctx);
2200	if (!note)
2201		return isl_printer_free(p);
2202	note_id = isl_id_alloc(ctx, NULL, note);
2203	if (!note_id)
2204		note_free(note);
2205	else
2206		note_id = isl_id_set_free_user(note_id, note_free);
2207
2208	p = isl_printer_set_note(p, isl_id_copy(id), note_id);
2209
2210	return p;
2211}
2212
2213/* Ensure that "p" has an isl_ast_expr_op_names note identified by "id".
2214 */
2215static __isl_give isl_printer *alloc_names(__isl_take isl_printer *p,
2216	__isl_keep isl_id *id)
2217{
2218	return alloc_note(p, id, &create_names, &free_names);
2219}
2220
2221/* Retrieve the note identified by "id" from "p".
2222 * The note is assumed to exist.
2223 */
2224static void *get_note(__isl_keep isl_printer *p, __isl_keep isl_id *id)
2225{
2226	void *note;
2227
2228	id = isl_printer_get_note(p, isl_id_copy(id));
2229	note = isl_id_get_user(id);
2230	isl_id_free(id);
2231
2232	return note;
2233}
2234
2235/* Use "name" to print operations of type "type" to "p".
2236 *
2237 * Store the name in an isl_ast_expr_op_names note attached to "p", such that
2238 * it can be retrieved by get_op_str.
2239 */
2240__isl_give isl_printer *isl_ast_expr_op_type_set_print_name(
2241	__isl_take isl_printer *p, enum isl_ast_expr_op_type type,
2242	__isl_keep const char *name)
2243{
2244	isl_id *id;
2245	struct isl_ast_expr_op_names *names;
2246
2247	if (!p)
2248		return NULL;
2249	if (type > isl_ast_expr_op_last)
2250		isl_die(isl_printer_get_ctx(p), isl_error_invalid,
2251			"invalid type", return isl_printer_free(p));
2252
2253	id = names_id(isl_printer_get_ctx(p));
2254	p = alloc_names(p, id);
2255	names = get_note(p, id);
2256	isl_id_free(id);
2257	if (!names)
2258		return isl_printer_free(p);
2259	free(names->op_str[type]);
2260	names->op_str[type] = strdup(name);
2261
2262	return p;
2263}
2264
2265/* This is an alternative name for the function above.
2266 */
2267__isl_give isl_printer *isl_ast_op_type_set_print_name(
2268	__isl_take isl_printer *p, enum isl_ast_expr_op_type type,
2269	__isl_keep const char *name)
2270{
2271	return isl_ast_expr_op_type_set_print_name(p, type, name);
2272}
2273
2274/* Return the textual representation of "type" in C format.
2275 *
2276 * If there is a user-specified name in an isl_ast_expr_op_names note
2277 * associated to "p", then return that.
2278 * Otherwise, return the default name in op_str_c.
2279 */
2280static const char *get_op_str_c(__isl_keep isl_printer *p,
2281	enum isl_ast_expr_op_type type)
2282{
2283	isl_id *id;
2284	isl_bool has_names;
2285	struct isl_ast_expr_op_names *names = NULL;
2286
2287	id = names_id(isl_printer_get_ctx(p));
2288	has_names = isl_printer_has_note(p, id);
2289	if (has_names >= 0 && has_names)
2290		names = get_note(p, id);
2291	isl_id_free(id);
2292	if (names && names->op_str[type])
2293		return names->op_str[type];
2294	return op_str_c[type];
2295}
2296
2297/* Print the expression at position "pos" in "list" in C format.
2298 */
2299static __isl_give isl_printer *print_at_c(__isl_take isl_printer *p,
2300	__isl_keep isl_ast_expr_list *list, int pos)
2301{
2302	isl_ast_expr *expr;
2303
2304	expr = isl_ast_expr_list_get_at(list, pos);
2305	p = print_ast_expr_c(p, expr);
2306	isl_ast_expr_free(expr);
2307
2308	return p;
2309}
2310
2311/* Print a min or max reduction "expr" in C format.
2312 */
2313static __isl_give isl_printer *print_min_max_c(__isl_take isl_printer *p,
2314	__isl_keep isl_ast_expr *expr)
2315{
2316	int i = 0;
2317	isl_size n;
2318
2319	n = isl_ast_expr_list_size(expr->u.op.args);
2320	if (n < 0)
2321		return isl_printer_free(p);
2322
2323	for (i = 1; i < n; ++i) {
2324		p = isl_printer_print_str(p, get_op_str_c(p, expr->u.op.op));
2325		p = isl_printer_print_str(p, "(");
2326	}
2327	p = print_at_c(p, expr->u.op.args, 0);
2328	for (i = 1; i < n; ++i) {
2329		p = isl_printer_print_str(p, ", ");
2330		p = print_at_c(p, expr->u.op.args, i);
2331		p = isl_printer_print_str(p, ")");
2332	}
2333
2334	return p;
2335}
2336
2337/* Print a function call "expr" in C format.
2338 *
2339 * The first argument represents the function to be called.
2340 */
2341static __isl_give isl_printer *print_call_c(__isl_take isl_printer *p,
2342	__isl_keep isl_ast_expr *expr)
2343{
2344	int i = 0;
2345	isl_size n;
2346
2347	n = isl_ast_expr_list_size(expr->u.op.args);
2348	if (n < 0)
2349		return isl_printer_free(p);
2350
2351	p = print_at_c(p, expr->u.op.args, 0);
2352	p = isl_printer_print_str(p, "(");
2353	for (i = 1; i < n; ++i) {
2354		if (i != 1)
2355			p = isl_printer_print_str(p, ", ");
2356		p = print_at_c(p, expr->u.op.args, i);
2357	}
2358	p = isl_printer_print_str(p, ")");
2359
2360	return p;
2361}
2362
2363/* Print an array access "expr" in C format.
2364 *
2365 * The first argument represents the array being accessed.
2366 */
2367static __isl_give isl_printer *print_access_c(__isl_take isl_printer *p,
2368	__isl_keep isl_ast_expr *expr)
2369{
2370	int i = 0;
2371	isl_size n;
2372
2373	n = isl_ast_expr_list_size(expr->u.op.args);
2374	if (n < 0)
2375		return isl_printer_free(p);
2376
2377	p = print_at_c(p, expr->u.op.args, 0);
2378	for (i = 1; i < n; ++i) {
2379		p = isl_printer_print_str(p, "[");
2380		p = print_at_c(p, expr->u.op.args, i);
2381		p = isl_printer_print_str(p, "]");
2382	}
2383
2384	return p;
2385}
2386
2387/* Print "expr" to "p" in C format.
2388 */
2389static __isl_give isl_printer *print_ast_expr_c(__isl_take isl_printer *p,
2390	__isl_keep isl_ast_expr *expr)
2391{
2392	isl_size n;
2393
2394	if (!p)
2395		return NULL;
2396	if (!expr)
2397		return isl_printer_free(p);
2398
2399	switch (expr->type) {
2400	case isl_ast_expr_op:
2401		if (expr->u.op.op == isl_ast_expr_op_call) {
2402			p = print_call_c(p, expr);
2403			break;
2404		}
2405		if (expr->u.op.op == isl_ast_expr_op_access) {
2406			p = print_access_c(p, expr);
2407			break;
2408		}
2409		n = isl_ast_expr_list_size(expr->u.op.args);
2410		if (n < 0)
2411			return isl_printer_free(p);
2412		if (n == 1) {
2413			p = isl_printer_print_str(p,
2414						get_op_str_c(p, expr->u.op.op));
2415			p = print_sub_expr_c(p, expr, 0, 0);
2416			break;
2417		}
2418		if (expr->u.op.op == isl_ast_expr_op_fdiv_q) {
2419			const char *name;
2420
2421			name = get_op_str_c(p, isl_ast_expr_op_fdiv_q);
2422			p = isl_printer_print_str(p, name);
2423			p = isl_printer_print_str(p, "(");
2424			p = print_at_c(p, expr->u.op.args, 0);
2425			p = isl_printer_print_str(p, ", ");
2426			p = print_at_c(p, expr->u.op.args, 1);
2427			p = isl_printer_print_str(p, ")");
2428			break;
2429		}
2430		if (expr->u.op.op == isl_ast_expr_op_max ||
2431		    expr->u.op.op == isl_ast_expr_op_min) {
2432			p = print_min_max_c(p, expr);
2433			break;
2434		}
2435		if (expr->u.op.op == isl_ast_expr_op_cond ||
2436		    expr->u.op.op == isl_ast_expr_op_select) {
2437			p = print_at_c(p, expr->u.op.args, 0);
2438			p = isl_printer_print_str(p, " ? ");
2439			p = print_at_c(p, expr->u.op.args, 1);
2440			p = isl_printer_print_str(p, " : ");
2441			p = print_at_c(p, expr->u.op.args, 2);
2442			break;
2443		}
2444		if (n != 2)
2445			isl_die(isl_printer_get_ctx(p), isl_error_internal,
2446				"operation should have two arguments",
2447				return isl_printer_free(p));
2448		p = print_sub_expr_c(p, expr, 0, 1);
2449		if (expr->u.op.op != isl_ast_expr_op_member)
2450			p = isl_printer_print_str(p, " ");
2451		p = isl_printer_print_str(p, get_op_str_c(p, expr->u.op.op));
2452		if (expr->u.op.op != isl_ast_expr_op_member)
2453			p = isl_printer_print_str(p, " ");
2454		p = print_sub_expr_c(p, expr, 1, 0);
2455		break;
2456	case isl_ast_expr_id:
2457		p = isl_printer_print_str(p, isl_id_get_name(expr->u.id));
2458		break;
2459	case isl_ast_expr_int:
2460		p = isl_printer_print_val(p, expr->u.v);
2461		break;
2462	case isl_ast_expr_error:
2463		break;
2464	}
2465
2466	return p;
2467}
2468
2469/* Textual representation of the isl_ast_expr_op_type elements
2470 * for use in a YAML representation of an isl_ast_expr.
2471 */
2472static char *op_str[] = {
2473	[isl_ast_expr_op_and] = "and",
2474	[isl_ast_expr_op_and_then] = "and_then",
2475	[isl_ast_expr_op_or] = "or",
2476	[isl_ast_expr_op_or_else] = "or_else",
2477	[isl_ast_expr_op_max] = "max",
2478	[isl_ast_expr_op_min] = "min",
2479	[isl_ast_expr_op_minus] = "minus",
2480	[isl_ast_expr_op_add] = "add",
2481	[isl_ast_expr_op_sub] = "sub",
2482	[isl_ast_expr_op_mul] = "mul",
2483	[isl_ast_expr_op_div] = "div",
2484	[isl_ast_expr_op_fdiv_q] = "fdiv_q",
2485	[isl_ast_expr_op_pdiv_q] = "pdiv_q",
2486	[isl_ast_expr_op_pdiv_r] = "pdiv_r",
2487	[isl_ast_expr_op_zdiv_r] = "zdiv_r",
2488	[isl_ast_expr_op_cond] = "cond",
2489	[isl_ast_expr_op_select] = "select",
2490	[isl_ast_expr_op_eq] = "eq",
2491	[isl_ast_expr_op_le] = "le",
2492	[isl_ast_expr_op_lt] = "lt",
2493	[isl_ast_expr_op_ge] = "ge",
2494	[isl_ast_expr_op_gt] = "gt",
2495	[isl_ast_expr_op_call] = "call",
2496	[isl_ast_expr_op_access] = "access",
2497	[isl_ast_expr_op_member] = "member",
2498	[isl_ast_expr_op_address_of] = "address_of"
2499};
2500
2501static __isl_give isl_printer *print_ast_expr_isl(__isl_take isl_printer *p,
2502	__isl_keep isl_ast_expr *expr);
2503
2504/* Print the arguments of "expr" to "p" in isl format.
2505 *
2506 * If there are no arguments, then nothing needs to be printed.
2507 * Otherwise add an "args" key to the current mapping with as value
2508 * the list of arguments of "expr".
2509 */
2510static __isl_give isl_printer *print_arguments(__isl_take isl_printer *p,
2511	__isl_keep isl_ast_expr *expr)
2512{
2513	int i;
2514	isl_size n;
2515
2516	n = isl_ast_expr_get_op_n_arg(expr);
2517	if (n < 0)
2518		return isl_printer_free(p);
2519	if (n == 0)
2520		return p;
2521
2522	p = isl_printer_print_str(p, "args");
2523	p = isl_printer_yaml_next(p);
2524	p = isl_printer_yaml_start_sequence(p);
2525	for (i = 0; i < n; ++i) {
2526		isl_ast_expr *arg;
2527
2528		arg = isl_ast_expr_get_op_arg(expr, i);
2529		p = print_ast_expr_isl(p, arg);
2530		isl_ast_expr_free(arg);
2531		p = isl_printer_yaml_next(p);
2532	}
2533	p = isl_printer_yaml_end_sequence(p);
2534
2535	return p;
2536}
2537
2538/* Textual representations of the YAML keys for an isl_ast_expr object.
2539 */
2540static char *expr_str[] = {
2541	[isl_ast_expr_op] = "op",
2542	[isl_ast_expr_id] = "id",
2543	[isl_ast_expr_int] = "val",
2544};
2545
2546/* Print "expr" to "p" in isl format.
2547 *
2548 * In particular, print the isl_ast_expr as a YAML document.
2549 */
2550static __isl_give isl_printer *print_ast_expr_isl(__isl_take isl_printer *p,
2551	__isl_keep isl_ast_expr *expr)
2552{
2553	enum isl_ast_expr_type type;
2554	enum isl_ast_expr_op_type op;
2555	isl_id *id;
2556	isl_val *v;
2557
2558	if (!expr)
2559		return isl_printer_free(p);
2560
2561	p = isl_printer_yaml_start_mapping(p);
2562	type = isl_ast_expr_get_type(expr);
2563	switch (type) {
2564	case isl_ast_expr_error:
2565		return isl_printer_free(p);
2566	case isl_ast_expr_op:
2567		op = isl_ast_expr_get_op_type(expr);
2568		if (op == isl_ast_expr_op_error)
2569			return isl_printer_free(p);
2570		p = isl_printer_print_str(p, expr_str[type]);
2571		p = isl_printer_yaml_next(p);
2572		p = isl_printer_print_str(p, op_str[op]);
2573		p = isl_printer_yaml_next(p);
2574		p = print_arguments(p, expr);
2575		break;
2576	case isl_ast_expr_id:
2577		p = isl_printer_print_str(p, expr_str[type]);
2578		p = isl_printer_yaml_next(p);
2579		id = isl_ast_expr_get_id(expr);
2580		p = isl_printer_print_id(p, id);
2581		isl_id_free(id);
2582		break;
2583	case isl_ast_expr_int:
2584		p = isl_printer_print_str(p, expr_str[type]);
2585		p = isl_printer_yaml_next(p);
2586		v = isl_ast_expr_get_val(expr);
2587		p = isl_printer_print_val(p, v);
2588		isl_val_free(v);
2589		break;
2590	}
2591	p = isl_printer_yaml_end_mapping(p);
2592
2593	return p;
2594}
2595
2596/* Print "expr" to "p".
2597 *
2598 * Only an isl and a C format are supported.
2599 */
2600__isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p,
2601	__isl_keep isl_ast_expr *expr)
2602{
2603	int format;
2604
2605	if (!p)
2606		return NULL;
2607
2608	format = isl_printer_get_output_format(p);
2609	switch (format) {
2610	case ISL_FORMAT_ISL:
2611		p = print_ast_expr_isl(p, expr);
2612		break;
2613	case ISL_FORMAT_C:
2614		p = print_ast_expr_c(p, expr);
2615		break;
2616	default:
2617		isl_die(isl_printer_get_ctx(p), isl_error_unsupported,
2618			"output format not supported for ast_expr",
2619			return isl_printer_free(p));
2620	}
2621
2622	return p;
2623}
2624
2625#undef KEY
2626#define KEY		enum isl_ast_expr_op_type
2627#undef KEY_ERROR
2628#define KEY_ERROR	isl_ast_expr_op_error
2629#undef KEY_END
2630#define KEY_END		(isl_ast_expr_op_address_of + 1)
2631#undef KEY_STR
2632#define KEY_STR		op_str
2633#undef KEY_EXTRACT
2634#define KEY_EXTRACT	extract_op_type
2635#undef KEY_GET
2636#define KEY_GET		get_op_type
2637#include "extract_key.c"
2638
2639/* Return the next token, which is assumed to be a key in a YAML mapping,
2640 * from "s" as a string.
2641 */
2642static __isl_give char *next_key(__isl_keep isl_stream *s)
2643{
2644	struct isl_token *tok;
2645	char *str;
2646	isl_ctx *ctx;
2647
2648	if (!s)
2649		return NULL;
2650	tok = isl_stream_next_token(s);
2651	if (!tok) {
2652		isl_stream_error(s, NULL, "unexpected EOF");
2653		return NULL;
2654	}
2655	ctx = isl_stream_get_ctx(s);
2656	str = isl_token_get_str(ctx, tok);
2657	isl_token_free(tok);
2658	return str;
2659}
2660
2661/* Remove the next token, which is assumed to be the key "expected"
2662 * in a YAML mapping, from "s" and move to the corresponding value.
2663 */
2664static isl_stat eat_key(__isl_keep isl_stream *s, const char *expected)
2665{
2666	char *str;
2667	int ok;
2668
2669	str = next_key(s);
2670	if (!str)
2671		return isl_stat_error;
2672	ok = !strcmp(str, expected);
2673	free(str);
2674
2675	if (!ok) {
2676		isl_stream_error(s, NULL, "expecting different key");
2677		return isl_stat_error;
2678	}
2679
2680	if (isl_stream_yaml_next(s) < 0)
2681		return isl_stat_error;
2682
2683	return isl_stat_ok;
2684}
2685
2686#undef EL_BASE
2687#define EL_BASE ast_expr
2688
2689#include <isl_list_read_yaml_templ.c>
2690
2691/* Read an isl_ast_expr object of type isl_ast_expr_op from "s",
2692 * where the "op" key has already been read by the caller.
2693 *
2694 * Read the operation type and the arguments and
2695 * return the corresponding isl_ast_expr object.
2696 */
2697static __isl_give isl_ast_expr *read_op(__isl_keep isl_stream *s)
2698{
2699	enum isl_ast_expr_op_type op;
2700	isl_ast_expr_list *list;
2701
2702	op = get_op_type(s);
2703	if (op < 0)
2704		return NULL;
2705	if (isl_stream_yaml_next(s) < 0)
2706		return NULL;
2707	if (eat_key(s, "args") < 0)
2708		return NULL;
2709
2710	list = isl_stream_yaml_read_ast_expr_list(s);
2711
2712	return alloc_op(op, list);
2713}
2714
2715/* Read an isl_ast_expr object of type isl_ast_expr_id from "s",
2716 * where the "id" key has already been read by the caller.
2717 */
2718static __isl_give isl_ast_expr *read_id(__isl_keep isl_stream *s)
2719{
2720	return isl_ast_expr_from_id(isl_stream_read_id(s));
2721}
2722
2723/* Read an isl_ast_expr object of type isl_ast_expr_int from "s",
2724 * where the "val" key has already been read by the caller.
2725 */
2726static __isl_give isl_ast_expr *read_int(__isl_keep isl_stream *s)
2727{
2728	return isl_ast_expr_from_val(isl_stream_read_val(s));
2729}
2730
2731#undef KEY
2732#define KEY		enum isl_ast_expr_type
2733#undef KEY_ERROR
2734#define KEY_ERROR	isl_ast_expr_error
2735#undef KEY_END
2736#define KEY_END		(isl_ast_expr_int + 1)
2737#undef KEY_STR
2738#define KEY_STR		expr_str
2739#undef KEY_EXTRACT
2740#define KEY_EXTRACT	extract_expr_type
2741#undef KEY_GET
2742#define KEY_GET		get_expr_type
2743#include "extract_key.c"
2744
2745/* Read an isl_ast_expr object from "s".
2746 *
2747 * The keys in the YAML mapping are assumed to appear
2748 * in the same order as the one in which they are printed
2749 * by print_ast_expr_isl.
2750 * In particular, the isl_ast_expr_op type, which is the only one
2751 * with more than one element, is identified by the "op" key and
2752 * not by the "args" key.
2753 */
2754__isl_give isl_ast_expr *isl_stream_read_ast_expr(__isl_keep isl_stream *s)
2755{
2756	enum isl_ast_expr_type type;
2757	isl_bool more;
2758	isl_ast_expr *expr;
2759
2760	if (isl_stream_yaml_read_start_mapping(s))
2761		return NULL;
2762	more = isl_stream_yaml_next(s);
2763	if (more < 0)
2764		return NULL;
2765	if (!more) {
2766		isl_stream_error(s, NULL, "missing key");
2767		return NULL;
2768	}
2769
2770	type = get_expr_type(s);
2771	if (type < 0)
2772		return NULL;
2773	if (isl_stream_yaml_next(s) < 0)
2774		return NULL;
2775	switch (type) {
2776	case isl_ast_expr_op:
2777		expr = read_op(s);
2778		break;
2779	case isl_ast_expr_id:
2780		expr = read_id(s);
2781		break;
2782	case isl_ast_expr_int:
2783		expr = read_int(s);
2784		break;
2785	case isl_ast_expr_error:
2786		return NULL;
2787	}
2788
2789	if (isl_stream_yaml_read_end_mapping(s) < 0)
2790		return isl_ast_expr_free(expr);
2791
2792	return expr;
2793}
2794
2795static __isl_give isl_printer *print_ast_node_isl(__isl_take isl_printer *p,
2796	__isl_keep isl_ast_node *node);
2797
2798/* Print a YAML sequence containing the entries in "list" to "p".
2799 */
2800static __isl_give isl_printer *print_ast_node_list(__isl_take isl_printer *p,
2801	__isl_keep isl_ast_node_list *list)
2802{
2803	int i;
2804	isl_size n;
2805
2806	n = isl_ast_node_list_n_ast_node(list);
2807	if (n < 0)
2808		return isl_printer_free(p);
2809
2810	p = isl_printer_yaml_start_sequence(p);
2811	for (i = 0; i < n; ++i) {
2812		isl_ast_node *node;
2813
2814		node = isl_ast_node_list_get_ast_node(list, i);
2815		p = print_ast_node_isl(p, node);
2816		isl_ast_node_free(node);
2817		p = isl_printer_yaml_next(p);
2818	}
2819	p = isl_printer_yaml_end_sequence(p);
2820
2821	return p;
2822}
2823
2824/* Print "node" to "p" in "isl format".
2825 *
2826 * In particular, print the isl_ast_node as a YAML document.
2827 */
2828static __isl_give isl_printer *print_ast_node_isl(__isl_take isl_printer *p,
2829	__isl_keep isl_ast_node *node)
2830{
2831	switch (node->type) {
2832	case isl_ast_node_for:
2833		p = isl_printer_yaml_start_mapping(p);
2834		p = isl_printer_print_str(p, "iterator");
2835		p = isl_printer_yaml_next(p);
2836		p = isl_printer_print_ast_expr(p, node->u.f.iterator);
2837		p = isl_printer_yaml_next(p);
2838		if (node->u.f.degenerate) {
2839			p = isl_printer_print_str(p, "value");
2840			p = isl_printer_yaml_next(p);
2841			p = isl_printer_print_ast_expr(p, node->u.f.init);
2842			p = isl_printer_yaml_next(p);
2843		} else {
2844			p = isl_printer_print_str(p, "init");
2845			p = isl_printer_yaml_next(p);
2846			p = isl_printer_print_ast_expr(p, node->u.f.init);
2847			p = isl_printer_yaml_next(p);
2848			p = isl_printer_print_str(p, "cond");
2849			p = isl_printer_yaml_next(p);
2850			p = isl_printer_print_ast_expr(p, node->u.f.cond);
2851			p = isl_printer_yaml_next(p);
2852			p = isl_printer_print_str(p, "inc");
2853			p = isl_printer_yaml_next(p);
2854			p = isl_printer_print_ast_expr(p, node->u.f.inc);
2855			p = isl_printer_yaml_next(p);
2856		}
2857		if (node->u.f.body) {
2858			p = isl_printer_print_str(p, "body");
2859			p = isl_printer_yaml_next(p);
2860			p = isl_printer_print_ast_node(p, node->u.f.body);
2861			p = isl_printer_yaml_next(p);
2862		}
2863		p = isl_printer_yaml_end_mapping(p);
2864		break;
2865	case isl_ast_node_mark:
2866		p = isl_printer_yaml_start_mapping(p);
2867		p = isl_printer_print_str(p, "mark");
2868		p = isl_printer_yaml_next(p);
2869		p = isl_printer_print_id(p, node->u.m.mark);
2870		p = isl_printer_yaml_next(p);
2871		p = isl_printer_print_str(p, "node");
2872		p = isl_printer_yaml_next(p);
2873		p = isl_printer_print_ast_node(p, node->u.m.node);
2874		p = isl_printer_yaml_end_mapping(p);
2875		break;
2876	case isl_ast_node_user:
2877		p = isl_printer_yaml_start_mapping(p);
2878		p = isl_printer_print_str(p, "user");
2879		p = isl_printer_yaml_next(p);
2880		p = isl_printer_print_ast_expr(p, node->u.e.expr);
2881		p = isl_printer_yaml_end_mapping(p);
2882		break;
2883	case isl_ast_node_if:
2884		p = isl_printer_yaml_start_mapping(p);
2885		p = isl_printer_print_str(p, "guard");
2886		p = isl_printer_yaml_next(p);
2887		p = isl_printer_print_ast_expr(p, node->u.i.guard);
2888		p = isl_printer_yaml_next(p);
2889		if (node->u.i.then) {
2890			p = isl_printer_print_str(p, "then");
2891			p = isl_printer_yaml_next(p);
2892			p = isl_printer_print_ast_node(p, node->u.i.then);
2893			p = isl_printer_yaml_next(p);
2894		}
2895		if (node->u.i.else_node) {
2896			p = isl_printer_print_str(p, "else");
2897			p = isl_printer_yaml_next(p);
2898			p = isl_printer_print_ast_node(p, node->u.i.else_node);
2899		}
2900		p = isl_printer_yaml_end_mapping(p);
2901		break;
2902	case isl_ast_node_block:
2903		p = print_ast_node_list(p, node->u.b.children);
2904		break;
2905	case isl_ast_node_error:
2906		break;
2907	}
2908	return p;
2909}
2910
2911/* Do we need to print a block around the body "node" of a for or if node?
2912 *
2913 * If the node is a block, then we need to print a block.
2914 * Also if the node is a degenerate for then we will print it as
2915 * an assignment followed by the body of the for loop, so we need a block
2916 * as well.
2917 * If the node is an if node with an else, then we print a block
2918 * to avoid spurious dangling else warnings emitted by some compilers.
2919 * If the node is a mark, then in principle, we would have to check
2920 * the child of the mark node.  However, even if the child would not
2921 * require us to print a block, for readability it is probably best
2922 * to print a block anyway.
2923 * If the ast_always_print_block option has been set, then we print a block.
2924 */
2925static int need_block(__isl_keep isl_ast_node *node)
2926{
2927	isl_ctx *ctx;
2928
2929	if (node->type == isl_ast_node_block)
2930		return 1;
2931	if (node->type == isl_ast_node_for && node->u.f.degenerate)
2932		return 1;
2933	if (node->type == isl_ast_node_if && node->u.i.else_node)
2934		return 1;
2935	if (node->type == isl_ast_node_mark)
2936		return 1;
2937
2938	ctx = isl_ast_node_get_ctx(node);
2939	return isl_options_get_ast_always_print_block(ctx);
2940}
2941
2942static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
2943	__isl_keep isl_ast_node *node,
2944	__isl_keep isl_ast_print_options *options, int in_block, int in_list);
2945static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
2946	__isl_keep isl_ast_node *node,
2947	__isl_keep isl_ast_print_options *options, int new_line,
2948	int force_block);
2949
2950/* Print the body "node" of a for or if node.
2951 * If "else_node" is set, then it is printed as well.
2952 * If "force_block" is set, then print out the body as a block.
2953 *
2954 * We first check if we need to print out a block.
2955 * We always print out a block if there is an else node to make
2956 * sure that the else node is matched to the correct if node.
2957 * For consistency, the corresponding else node is also printed as a block.
2958 *
2959 * If the else node is itself an if, then we print it as
2960 *
2961 *	} else if (..) {
2962 *	}
2963 *
2964 * Otherwise the else node is printed as
2965 *
2966 *	} else {
2967 *	  node
2968 *	}
2969 */
2970static __isl_give isl_printer *print_body_c(__isl_take isl_printer *p,
2971	__isl_keep isl_ast_node *node, __isl_keep isl_ast_node *else_node,
2972	__isl_keep isl_ast_print_options *options, int force_block)
2973{
2974	if (!node)
2975		return isl_printer_free(p);
2976
2977	if (!force_block && !else_node && !need_block(node)) {
2978		p = isl_printer_end_line(p);
2979		p = isl_printer_indent(p, 2);
2980		p = isl_ast_node_print(node, p,
2981					isl_ast_print_options_copy(options));
2982		p = isl_printer_indent(p, -2);
2983		return p;
2984	}
2985
2986	p = isl_printer_print_str(p, " {");
2987	p = isl_printer_end_line(p);
2988	p = isl_printer_indent(p, 2);
2989	p = print_ast_node_c(p, node, options, 1, 0);
2990	p = isl_printer_indent(p, -2);
2991	p = isl_printer_start_line(p);
2992	p = isl_printer_print_str(p, "}");
2993	if (else_node) {
2994		if (else_node->type == isl_ast_node_if) {
2995			p = isl_printer_print_str(p, " else ");
2996			p = print_if_c(p, else_node, options, 0, 1);
2997		} else {
2998			p = isl_printer_print_str(p, " else");
2999			p = print_body_c(p, else_node, NULL, options, 1);
3000		}
3001	} else
3002		p = isl_printer_end_line(p);
3003
3004	return p;
3005}
3006
3007/* Print the start of a compound statement.
3008 */
3009static __isl_give isl_printer *start_block(__isl_take isl_printer *p)
3010{
3011	p = isl_printer_start_line(p);
3012	p = isl_printer_print_str(p, "{");
3013	p = isl_printer_end_line(p);
3014	p = isl_printer_indent(p, 2);
3015
3016	return p;
3017}
3018
3019/* Print the end of a compound statement.
3020 */
3021static __isl_give isl_printer *end_block(__isl_take isl_printer *p)
3022{
3023	p = isl_printer_indent(p, -2);
3024	p = isl_printer_start_line(p);
3025	p = isl_printer_print_str(p, "}");
3026	p = isl_printer_end_line(p);
3027
3028	return p;
3029}
3030
3031/* Print the for node "node".
3032 *
3033 * If the for node is degenerate, it is printed as
3034 *
3035 *	type iterator = init;
3036 *	body
3037 *
3038 * Otherwise, it is printed as
3039 *
3040 *	for (type iterator = init; cond; iterator += inc)
3041 *		body
3042 *
3043 * "in_block" is set if we are currently inside a block.
3044 * "in_list" is set if the current node is not alone in the block.
3045 * If we are not in a block or if the current not is not alone in the block
3046 * then we print a block around a degenerate for loop such that the variable
3047 * declaration will not conflict with any potential other declaration
3048 * of the same variable.
3049 */
3050static __isl_give isl_printer *print_for_c(__isl_take isl_printer *p,
3051	__isl_keep isl_ast_node *node,
3052	__isl_keep isl_ast_print_options *options, int in_block, int in_list)
3053{
3054	isl_id *id;
3055	const char *name;
3056	const char *type;
3057
3058	type = isl_options_get_ast_iterator_type(isl_printer_get_ctx(p));
3059	if (!node->u.f.degenerate) {
3060		id = isl_ast_expr_get_id(node->u.f.iterator);
3061		name = isl_id_get_name(id);
3062		isl_id_free(id);
3063		p = isl_printer_start_line(p);
3064		p = isl_printer_print_str(p, "for (");
3065		p = isl_printer_print_str(p, type);
3066		p = isl_printer_print_str(p, " ");
3067		p = isl_printer_print_str(p, name);
3068		p = isl_printer_print_str(p, " = ");
3069		p = isl_printer_print_ast_expr(p, node->u.f.init);
3070		p = isl_printer_print_str(p, "; ");
3071		p = isl_printer_print_ast_expr(p, node->u.f.cond);
3072		p = isl_printer_print_str(p, "; ");
3073		p = isl_printer_print_str(p, name);
3074		p = isl_printer_print_str(p, " += ");
3075		p = isl_printer_print_ast_expr(p, node->u.f.inc);
3076		p = isl_printer_print_str(p, ")");
3077		p = print_body_c(p, node->u.f.body, NULL, options, 0);
3078	} else {
3079		id = isl_ast_expr_get_id(node->u.f.iterator);
3080		name = isl_id_get_name(id);
3081		isl_id_free(id);
3082		if (!in_block || in_list)
3083			p = start_block(p);
3084		p = isl_printer_start_line(p);
3085		p = isl_printer_print_str(p, type);
3086		p = isl_printer_print_str(p, " ");
3087		p = isl_printer_print_str(p, name);
3088		p = isl_printer_print_str(p, " = ");
3089		p = isl_printer_print_ast_expr(p, node->u.f.init);
3090		p = isl_printer_print_str(p, ";");
3091		p = isl_printer_end_line(p);
3092		p = print_ast_node_c(p, node->u.f.body, options, 1, 0);
3093		if (!in_block || in_list)
3094			p = end_block(p);
3095	}
3096
3097	return p;
3098}
3099
3100/* Print the if node "node".
3101 * If "new_line" is set then the if node should be printed on a new line.
3102 * If "force_block" is set, then print out the body as a block.
3103 */
3104static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
3105	__isl_keep isl_ast_node *node,
3106	__isl_keep isl_ast_print_options *options, int new_line,
3107	int force_block)
3108{
3109	if (new_line)
3110		p = isl_printer_start_line(p);
3111	p = isl_printer_print_str(p, "if (");
3112	p = isl_printer_print_ast_expr(p, node->u.i.guard);
3113	p = isl_printer_print_str(p, ")");
3114	p = print_body_c(p, node->u.i.then, node->u.i.else_node, options,
3115			force_block);
3116
3117	return p;
3118}
3119
3120/* Print the "node" to "p".
3121 *
3122 * "in_block" is set if we are currently inside a block.
3123 * If so, we do not print a block around the children of a block node.
3124 * We do this to avoid an extra block around the body of a degenerate
3125 * for node.
3126 *
3127 * "in_list" is set if the current node is not alone in the block.
3128 */
3129static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
3130	__isl_keep isl_ast_node *node,
3131	__isl_keep isl_ast_print_options *options, int in_block, int in_list)
3132{
3133	switch (node->type) {
3134	case isl_ast_node_for:
3135		if (options->print_for)
3136			return options->print_for(p,
3137					isl_ast_print_options_copy(options),
3138					node, options->print_for_user);
3139		p = print_for_c(p, node, options, in_block, in_list);
3140		break;
3141	case isl_ast_node_if:
3142		p = print_if_c(p, node, options, 1, 0);
3143		break;
3144	case isl_ast_node_block:
3145		if (!in_block)
3146			p = start_block(p);
3147		p = isl_ast_node_list_print(node->u.b.children, p, options);
3148		if (!in_block)
3149			p = end_block(p);
3150		break;
3151	case isl_ast_node_mark:
3152		p = isl_printer_start_line(p);
3153		p = isl_printer_print_str(p, "// ");
3154		p = isl_printer_print_str(p, isl_id_get_name(node->u.m.mark));
3155		p = isl_printer_end_line(p);
3156		p = print_ast_node_c(p, node->u.m.node, options, 0, in_list);
3157		break;
3158	case isl_ast_node_user:
3159		if (options->print_user)
3160			return options->print_user(p,
3161					isl_ast_print_options_copy(options),
3162					node, options->print_user_user);
3163		p = isl_printer_start_line(p);
3164		p = isl_printer_print_ast_expr(p, node->u.e.expr);
3165		p = isl_printer_print_str(p, ";");
3166		p = isl_printer_end_line(p);
3167		break;
3168	case isl_ast_node_error:
3169		break;
3170	}
3171	return p;
3172}
3173
3174/* Print the for node "node" to "p".
3175 */
3176__isl_give isl_printer *isl_ast_node_for_print(__isl_keep isl_ast_node *node,
3177	__isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
3178{
3179	if (isl_ast_node_check_for(node) < 0 || !options)
3180		goto error;
3181	p = print_for_c(p, node, options, 0, 0);
3182	isl_ast_print_options_free(options);
3183	return p;
3184error:
3185	isl_ast_print_options_free(options);
3186	isl_printer_free(p);
3187	return NULL;
3188}
3189
3190/* Print the if node "node" to "p".
3191 */
3192__isl_give isl_printer *isl_ast_node_if_print(__isl_keep isl_ast_node *node,
3193	__isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
3194{
3195	if (isl_ast_node_check_if(node) < 0 || !options)
3196		goto error;
3197	p = print_if_c(p, node, options, 1, 0);
3198	isl_ast_print_options_free(options);
3199	return p;
3200error:
3201	isl_ast_print_options_free(options);
3202	isl_printer_free(p);
3203	return NULL;
3204}
3205
3206/* Print "node" to "p".
3207 *
3208 * "node" is assumed to be either the outermost node in an AST or
3209 * a node that is known not to be a block.
3210 * If "node" is a block (and is therefore outermost) and
3211 * if the ast_print_outermost_block options is not set,
3212 * then act as if the printing occurs inside a block, such
3213 * that no "extra" block will get printed.
3214 */
3215__isl_give isl_printer *isl_ast_node_print(__isl_keep isl_ast_node *node,
3216	__isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
3217{
3218	int in_block = 0;
3219
3220	if (!options || !node)
3221		goto error;
3222	if (node->type == isl_ast_node_block) {
3223		isl_ctx *ctx;
3224
3225		ctx = isl_ast_node_get_ctx(node);
3226		in_block = !isl_options_get_ast_print_outermost_block(ctx);
3227	}
3228	p = print_ast_node_c(p, node, options, in_block, 0);
3229	isl_ast_print_options_free(options);
3230	return p;
3231error:
3232	isl_ast_print_options_free(options);
3233	isl_printer_free(p);
3234	return NULL;
3235}
3236
3237/* Print "node" to "p".
3238 */
3239__isl_give isl_printer *isl_printer_print_ast_node(__isl_take isl_printer *p,
3240	__isl_keep isl_ast_node *node)
3241{
3242	int format;
3243	isl_ast_print_options *options;
3244
3245	if (!p)
3246		return NULL;
3247
3248	format = isl_printer_get_output_format(p);
3249	switch (format) {
3250	case ISL_FORMAT_ISL:
3251		p = print_ast_node_isl(p, node);
3252		break;
3253	case ISL_FORMAT_C:
3254		options = isl_ast_print_options_alloc(isl_printer_get_ctx(p));
3255		p = isl_ast_node_print(node, p, options);
3256		break;
3257	default:
3258		isl_die(isl_printer_get_ctx(p), isl_error_unsupported,
3259			"output format not supported for ast_node",
3260			return isl_printer_free(p));
3261	}
3262
3263	return p;
3264}
3265
3266/* Print the list of nodes "list" to "p".
3267 */
3268__isl_give isl_printer *isl_ast_node_list_print(
3269	__isl_keep isl_ast_node_list *list, __isl_take isl_printer *p,
3270	__isl_keep isl_ast_print_options *options)
3271{
3272	int i;
3273
3274	if (!p || !list || !options)
3275		return isl_printer_free(p);
3276
3277	for (i = 0; i < list->n; ++i)
3278		p = print_ast_node_c(p, list->p[i], options, 1, 1);
3279
3280	return p;
3281}
3282
3283/* Is the next token on "s" the start of a YAML sequence
3284 * (rather than a YAML mapping)?
3285 *
3286 * A YAML sequence starts with either a '[' or a '-', depending on the format.
3287 */
3288static isl_bool next_is_sequence(__isl_keep isl_stream *s)
3289{
3290	struct isl_token *tok;
3291	int type;
3292	int seq;
3293
3294	tok = isl_stream_next_token(s);
3295	if (!tok)
3296		return isl_bool_error;
3297	type = isl_token_get_type(tok);
3298	seq = type == '[' || type == '-';
3299	isl_stream_push_token(s, tok);
3300
3301	return isl_bool_ok(seq);
3302}
3303
3304#undef EL_BASE
3305#define EL_BASE ast_node
3306
3307#include <isl_list_read_yaml_templ.c>
3308
3309/* Read an isl_ast_node object of type isl_ast_node_block from "s".
3310 */
3311static __isl_give isl_ast_node *read_block(__isl_keep isl_stream *s)
3312{
3313	isl_ast_node_list *children;
3314
3315	children = isl_stream_yaml_read_ast_node_list(s);
3316	return isl_ast_node_block_from_children(children);
3317}
3318
3319/* Textual representation of the first YAML key used
3320 * while printing an isl_ast_node of a given type.
3321 *
3322 * An isl_ast_node of type isl_ast_node_block is not printed
3323 * as a YAML mapping and is therefore assigned a dummy key.
3324 */
3325static char *node_first_str[] = {
3326	[isl_ast_node_for] = "iterator",
3327	[isl_ast_node_mark] = "mark",
3328	[isl_ast_node_user] = "user",
3329	[isl_ast_node_if] = "guard",
3330	[isl_ast_node_block] = "",
3331};
3332
3333#undef KEY
3334#define KEY		enum isl_ast_node_type
3335#undef KEY_ERROR
3336#define KEY_ERROR	isl_ast_node_error
3337#undef KEY_END
3338#define KEY_END		(isl_ast_node_user + 1)
3339#undef KEY_STR
3340#define KEY_STR		node_first_str
3341#undef KEY_EXTRACT
3342#define KEY_EXTRACT	extract_node_type
3343#undef KEY_GET
3344#define KEY_GET		get_node_type
3345#include "extract_key.c"
3346
3347static __isl_give isl_ast_node *read_body(__isl_keep isl_stream *s,
3348	__isl_take isl_ast_node *node)
3349{
3350	if (eat_key(s, "body") < 0)
3351		return isl_ast_node_free(node);
3352	node = isl_ast_node_for_set_body(node, isl_stream_read_ast_node(s));
3353	if (isl_stream_yaml_next(s) < 0)
3354		return isl_ast_node_free(node);
3355	return node;
3356}
3357
3358/* Read an isl_ast_node object of type isl_ast_node_for from "s",
3359 * where the initial "iterator" key has already been read by the caller.
3360 *
3361 * If the initial value is printed as the value of the key "value",
3362 * then the for-loop is degenerate and can at most have
3363 * a further "body" element.
3364 * Otherwise, the for-loop also has "cond" and "inc" elements.
3365 */
3366static __isl_give isl_ast_node *read_for(__isl_keep isl_stream *s)
3367{
3368	isl_id *id;
3369	isl_ast_expr *expr;
3370	isl_ast_node *node;
3371	char *key;
3372	isl_bool more;
3373	int is_value, is_init;
3374
3375	expr = isl_stream_read_ast_expr(s);
3376	id = isl_ast_expr_id_get_id(expr);
3377	isl_ast_expr_free(expr);
3378	if (!id)
3379		return NULL;
3380	if (isl_stream_yaml_next(s) < 0)
3381		id = isl_id_free(id);
3382
3383	node = isl_ast_node_alloc_for(id);
3384
3385	key = next_key(s);
3386	if (!key)
3387		return isl_ast_node_free(node);
3388	is_value = !strcmp(key, "value");
3389	is_init = !strcmp(key, "init");
3390	free(key);
3391	if (!is_value && !is_init)
3392		isl_die(isl_stream_get_ctx(s), isl_error_invalid,
3393			"unexpected key", return isl_ast_node_free(node));
3394	if (isl_stream_yaml_next(s) < 0)
3395		return isl_ast_node_free(node);
3396	node = isl_ast_node_for_set_init(node, isl_stream_read_ast_expr(s));
3397	if ((more = isl_stream_yaml_next(s)) < 0)
3398		return isl_ast_node_free(node);
3399	if (is_value) {
3400		node = isl_ast_node_for_mark_degenerate(node);
3401		if (more)
3402			node = read_body(s, node);
3403		return node;
3404	}
3405
3406	if (eat_key(s, "cond") < 0)
3407		return isl_ast_node_free(node);
3408	node = isl_ast_node_for_set_cond(node, isl_stream_read_ast_expr(s));
3409	if (isl_stream_yaml_next(s) < 0)
3410		return isl_ast_node_free(node);
3411	if (eat_key(s, "inc") < 0)
3412		return isl_ast_node_free(node);
3413	node = isl_ast_node_for_set_inc(node, isl_stream_read_ast_expr(s));
3414	if ((more = isl_stream_yaml_next(s)) < 0)
3415		return isl_ast_node_free(node);
3416
3417	if (more)
3418		node = read_body(s, node);
3419
3420	return node;
3421}
3422
3423/* Read an isl_ast_node object of type isl_ast_node_mark from "s",
3424 * where the initial "mark" key has already been read by the caller.
3425 */
3426static __isl_give isl_ast_node *read_mark(__isl_keep isl_stream *s)
3427{
3428	isl_id *id;
3429	isl_ast_node *node;
3430
3431	id = isl_stream_read_id(s);
3432	if (!id)
3433		return NULL;
3434	if (isl_stream_yaml_next(s) < 0)
3435		goto error;
3436	if (eat_key(s, "node") < 0)
3437		goto error;
3438	node = isl_stream_read_ast_node(s);
3439	node = isl_ast_node_alloc_mark(id, node);
3440	if (isl_stream_yaml_next(s) < 0)
3441		return isl_ast_node_free(node);
3442	return node;
3443error:
3444	isl_id_free(id);
3445	return NULL;
3446}
3447
3448/* Read an isl_ast_node object of type isl_ast_node_user from "s",
3449 * where the "user" key has already been read by the caller.
3450 */
3451static __isl_give isl_ast_node *read_user(__isl_keep isl_stream *s)
3452{
3453	isl_ast_node *node;
3454
3455	node = isl_ast_node_alloc_user(isl_stream_read_ast_expr(s));
3456	if (isl_stream_yaml_next(s) < 0)
3457		return isl_ast_node_free(node);
3458	return node;
3459}
3460
3461/* Read an isl_ast_node object of type isl_ast_node_if from "s",
3462 * where the initial "guard" key has already been read by the caller.
3463 */
3464static __isl_give isl_ast_node *read_if(__isl_keep isl_stream *s)
3465{
3466	isl_bool more;
3467	isl_ast_node *node;
3468
3469	node = isl_ast_node_alloc_if(isl_stream_read_ast_expr(s));
3470	if ((more = isl_stream_yaml_next(s)) < 0)
3471		return isl_ast_node_free(node);
3472	if (!more)
3473		return node;
3474
3475	if (eat_key(s, "then") < 0)
3476		return isl_ast_node_free(node);
3477	node = isl_ast_node_if_set_then(node, isl_stream_read_ast_node(s));
3478	if ((more = isl_stream_yaml_next(s)) < 0)
3479		return isl_ast_node_free(node);
3480	if (!more)
3481		return node;
3482
3483	if (eat_key(s, "else") < 0)
3484		return isl_ast_node_free(node);
3485	node = isl_ast_node_if_set_else_node(node, isl_stream_read_ast_node(s));
3486	if (isl_stream_yaml_next(s) < 0)
3487		return isl_ast_node_free(node);
3488
3489	return node;
3490}
3491
3492/* Read an isl_ast_node object from "s".
3493 *
3494 * A block node is printed as a YAML sequence by print_ast_node_isl.
3495 * Every other node type is printed as a YAML mapping.
3496 *
3497 * First check if the next element is a sequence and if so,
3498 * read a block node.
3499 * Otherwise, read a node based on the first mapping key
3500 * that is used to print a node type.
3501 * Note that the keys in the YAML mapping are assumed to appear
3502 * in the same order as the one in which they are printed
3503 * by print_ast_node_isl.
3504 */
3505__isl_give isl_ast_node *isl_stream_read_ast_node(__isl_keep isl_stream *s)
3506{
3507	enum isl_ast_node_type type;
3508	isl_bool more;
3509	isl_bool seq;
3510	isl_ast_node *node;
3511
3512	seq = next_is_sequence(s);
3513	if (seq < 0)
3514		return NULL;
3515	if (seq)
3516		return read_block(s);
3517
3518	if (isl_stream_yaml_read_start_mapping(s))
3519		return NULL;
3520	more = isl_stream_yaml_next(s);
3521	if (more < 0)
3522		return NULL;
3523	if (!more) {
3524		isl_stream_error(s, NULL, "missing key");
3525		return NULL;
3526	}
3527
3528	type = get_node_type(s);
3529	if (type < 0)
3530		return NULL;
3531	if (isl_stream_yaml_next(s) < 0)
3532		return NULL;
3533
3534	switch (type) {
3535	case isl_ast_node_block:
3536		isl_die(isl_stream_get_ctx(s), isl_error_internal,
3537			"block cannot be detected as mapping",
3538			return NULL);
3539	case isl_ast_node_for:
3540		node = read_for(s);
3541		break;
3542	case isl_ast_node_mark:
3543		node = read_mark(s);
3544		break;
3545	case isl_ast_node_user:
3546		node = read_user(s);
3547		break;
3548	case isl_ast_node_if:
3549		node = read_if(s);
3550		break;
3551	case isl_ast_node_error:
3552		return NULL;
3553	}
3554
3555	if (isl_stream_yaml_read_end_mapping(s) < 0)
3556		return isl_ast_node_free(node);
3557
3558	return node;
3559}
3560
3561#define ISL_AST_MACRO_FDIV_Q	(1 << 0)
3562#define ISL_AST_MACRO_MIN	(1 << 1)
3563#define ISL_AST_MACRO_MAX	(1 << 2)
3564#define ISL_AST_MACRO_ALL	(ISL_AST_MACRO_FDIV_Q | \
3565				 ISL_AST_MACRO_MIN | \
3566				 ISL_AST_MACRO_MAX)
3567
3568static int ast_expr_required_macros(__isl_keep isl_ast_expr *expr, int macros);
3569
3570/* Wrapper around ast_expr_required_macros for use
3571 * as an isl_ast_expr_list_foreach callback.
3572 */
3573static isl_stat entry_required_macros(__isl_take isl_ast_expr *expr, void *user)
3574{
3575	int *macros = user;
3576
3577	*macros = ast_expr_required_macros(expr, *macros);
3578	isl_ast_expr_free(expr);
3579
3580	return isl_stat_ok;
3581}
3582
3583/* If "expr" contains an isl_ast_expr_op_min, isl_ast_expr_op_max or
3584 * isl_ast_expr_op_fdiv_q then set the corresponding bit in "macros".
3585 */
3586static int ast_expr_required_macros(__isl_keep isl_ast_expr *expr, int macros)
3587{
3588	if (macros == ISL_AST_MACRO_ALL)
3589		return macros;
3590
3591	if (expr->type != isl_ast_expr_op)
3592		return macros;
3593
3594	if (expr->u.op.op == isl_ast_expr_op_min)
3595		macros |= ISL_AST_MACRO_MIN;
3596	if (expr->u.op.op == isl_ast_expr_op_max)
3597		macros |= ISL_AST_MACRO_MAX;
3598	if (expr->u.op.op == isl_ast_expr_op_fdiv_q)
3599		macros |= ISL_AST_MACRO_FDIV_Q;
3600
3601	isl_ast_expr_list_foreach(expr->u.op.args,
3602				&entry_required_macros, &macros);
3603
3604	return macros;
3605}
3606
3607static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
3608	int macros);
3609
3610/* If "node" contains an isl_ast_expr_op_min, isl_ast_expr_op_max or
3611 * isl_ast_expr_op_fdiv_q then set the corresponding bit in "macros".
3612 */
3613static int ast_node_required_macros(__isl_keep isl_ast_node *node, int macros)
3614{
3615	if (macros == ISL_AST_MACRO_ALL)
3616		return macros;
3617
3618	switch (node->type) {
3619	case isl_ast_node_for:
3620		macros = ast_expr_required_macros(node->u.f.init, macros);
3621		if (!node->u.f.degenerate) {
3622			macros = ast_expr_required_macros(node->u.f.cond,
3623								macros);
3624			macros = ast_expr_required_macros(node->u.f.inc,
3625								macros);
3626		}
3627		macros = ast_node_required_macros(node->u.f.body, macros);
3628		break;
3629	case isl_ast_node_if:
3630		macros = ast_expr_required_macros(node->u.i.guard, macros);
3631		macros = ast_node_required_macros(node->u.i.then, macros);
3632		if (node->u.i.else_node)
3633			macros = ast_node_required_macros(node->u.i.else_node,
3634								macros);
3635		break;
3636	case isl_ast_node_block:
3637		macros = ast_node_list_required_macros(node->u.b.children,
3638							macros);
3639		break;
3640	case isl_ast_node_mark:
3641		macros = ast_node_required_macros(node->u.m.node, macros);
3642		break;
3643	case isl_ast_node_user:
3644		macros = ast_expr_required_macros(node->u.e.expr, macros);
3645		break;
3646	case isl_ast_node_error:
3647		break;
3648	}
3649
3650	return macros;
3651}
3652
3653/* If "list" contains an isl_ast_expr_op_min, isl_ast_expr_op_max or
3654 * isl_ast_expr_op_fdiv_q then set the corresponding bit in "macros".
3655 */
3656static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
3657	int macros)
3658{
3659	int i;
3660
3661	for (i = 0; i < list->n; ++i)
3662		macros = ast_node_required_macros(list->p[i], macros);
3663
3664	return macros;
3665}
3666
3667/* Data structure for keeping track of whether a macro definition
3668 * for a given type has already been printed.
3669 * The value is zero if no definition has been printed and non-zero otherwise.
3670 */
3671struct isl_ast_expr_op_printed {
3672	char printed[isl_ast_expr_op_last + 1];
3673};
3674
3675/* Create an empty struct isl_ast_expr_op_printed.
3676 */
3677static void *create_printed(isl_ctx *ctx)
3678{
3679	return isl_calloc_type(ctx, struct isl_ast_expr_op_printed);
3680}
3681
3682/* Free a struct isl_ast_expr_op_printed.
3683 */
3684static void free_printed(void *user)
3685{
3686	free(user);
3687}
3688
3689/* Ensure that "p" has an isl_ast_expr_op_printed note identified by "id".
3690 */
3691static __isl_give isl_printer *alloc_printed(__isl_take isl_printer *p,
3692	__isl_keep isl_id *id)
3693{
3694	return alloc_note(p, id, &create_printed, &free_printed);
3695}
3696
3697/* Create an identifier that is used to store
3698 * an isl_ast_expr_op_printed note.
3699 */
3700static __isl_give isl_id *printed_id(isl_ctx *ctx)
3701{
3702	return isl_id_alloc(ctx, "isl_ast_expr_op_type_printed", NULL);
3703}
3704
3705/* Did the user specify that a macro definition should only be
3706 * printed once and has a macro definition for "type" already
3707 * been printed to "p"?
3708 * If definitions should only be printed once, but a definition
3709 * for "p" has not yet been printed, then mark it as having been
3710 * printed so that it will not printed again.
3711 * The actual printing is taken care of by the caller.
3712 */
3713static isl_bool already_printed_once(__isl_keep isl_printer *p,
3714	enum isl_ast_expr_op_type type)
3715{
3716	isl_ctx *ctx;
3717	isl_id *id;
3718	struct isl_ast_expr_op_printed *printed;
3719
3720	if (!p)
3721		return isl_bool_error;
3722
3723	ctx = isl_printer_get_ctx(p);
3724	if (!isl_options_get_ast_print_macro_once(ctx))
3725		return isl_bool_false;
3726
3727	if (type > isl_ast_expr_op_last)
3728		isl_die(isl_printer_get_ctx(p), isl_error_invalid,
3729			"invalid type", return isl_bool_error);
3730
3731	id = printed_id(isl_printer_get_ctx(p));
3732	p = alloc_printed(p, id);
3733	printed = get_note(p, id);
3734	isl_id_free(id);
3735	if (!printed)
3736		return isl_bool_error;
3737
3738	if (printed->printed[type])
3739		return isl_bool_true;
3740
3741	printed->printed[type] = 1;
3742	return isl_bool_false;
3743}
3744
3745/* Print a macro definition for the operator "type".
3746 *
3747 * If the user has specified that a macro definition should
3748 * only be printed once to any given printer and if the macro definition
3749 * has already been printed to "p", then do not print the definition.
3750 */
3751__isl_give isl_printer *isl_ast_expr_op_type_print_macro(
3752	enum isl_ast_expr_op_type type, __isl_take isl_printer *p)
3753{
3754	isl_bool skip;
3755
3756	skip = already_printed_once(p, type);
3757	if (skip < 0)
3758		return isl_printer_free(p);
3759	if (skip)
3760		return p;
3761
3762	switch (type) {
3763	case isl_ast_expr_op_min:
3764		p = isl_printer_start_line(p);
3765		p = isl_printer_print_str(p, "#define ");
3766		p = isl_printer_print_str(p, get_op_str_c(p, type));
3767		p = isl_printer_print_str(p,
3768			"(x,y)    ((x) < (y) ? (x) : (y))");
3769		p = isl_printer_end_line(p);
3770		break;
3771	case isl_ast_expr_op_max:
3772		p = isl_printer_start_line(p);
3773		p = isl_printer_print_str(p, "#define ");
3774		p = isl_printer_print_str(p, get_op_str_c(p, type));
3775		p = isl_printer_print_str(p,
3776			"(x,y)    ((x) > (y) ? (x) : (y))");
3777		p = isl_printer_end_line(p);
3778		break;
3779	case isl_ast_expr_op_fdiv_q:
3780		p = isl_printer_start_line(p);
3781		p = isl_printer_print_str(p, "#define ");
3782		p = isl_printer_print_str(p, get_op_str_c(p, type));
3783		p = isl_printer_print_str(p,
3784			"(n,d) "
3785			"(((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))");
3786		p = isl_printer_end_line(p);
3787		break;
3788	default:
3789		break;
3790	}
3791
3792	return p;
3793}
3794
3795/* This is an alternative name for the function above.
3796 */
3797__isl_give isl_printer *isl_ast_op_type_print_macro(
3798	enum isl_ast_expr_op_type type, __isl_take isl_printer *p)
3799{
3800	return isl_ast_expr_op_type_print_macro(type, p);
3801}
3802
3803/* Call "fn" for each type of operation represented in the "macros"
3804 * bit vector.
3805 */
3806static isl_stat foreach_ast_expr_op_type(int macros,
3807	isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user)
3808{
3809	if (macros & ISL_AST_MACRO_MIN && fn(isl_ast_expr_op_min, user) < 0)
3810		return isl_stat_error;
3811	if (macros & ISL_AST_MACRO_MAX && fn(isl_ast_expr_op_max, user) < 0)
3812		return isl_stat_error;
3813	if (macros & ISL_AST_MACRO_FDIV_Q &&
3814	    fn(isl_ast_expr_op_fdiv_q, user) < 0)
3815		return isl_stat_error;
3816
3817	return isl_stat_ok;
3818}
3819
3820/* Call "fn" for each type of operation that appears in "expr"
3821 * and that requires a macro definition.
3822 */
3823isl_stat isl_ast_expr_foreach_ast_expr_op_type(__isl_keep isl_ast_expr *expr,
3824	isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user)
3825{
3826	int macros;
3827
3828	if (!expr)
3829		return isl_stat_error;
3830
3831	macros = ast_expr_required_macros(expr, 0);
3832	return foreach_ast_expr_op_type(macros, fn, user);
3833}
3834
3835/* This is an alternative name for the function above.
3836 */
3837isl_stat isl_ast_expr_foreach_ast_op_type(__isl_keep isl_ast_expr *expr,
3838	isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user)
3839{
3840	return isl_ast_expr_foreach_ast_expr_op_type(expr, fn, user);
3841}
3842
3843/* Call "fn" for each type of operation that appears in "node"
3844 * and that requires a macro definition.
3845 */
3846isl_stat isl_ast_node_foreach_ast_expr_op_type(__isl_keep isl_ast_node *node,
3847	isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user)
3848{
3849	int macros;
3850
3851	if (!node)
3852		return isl_stat_error;
3853
3854	macros = ast_node_required_macros(node, 0);
3855	return foreach_ast_expr_op_type(macros, fn, user);
3856}
3857
3858/* This is an alternative name for the function above.
3859 */
3860isl_stat isl_ast_node_foreach_ast_op_type(__isl_keep isl_ast_node *node,
3861	isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user)
3862{
3863	return isl_ast_node_foreach_ast_expr_op_type(node, fn, user);
3864}
3865
3866static isl_stat ast_op_type_print_macro(enum isl_ast_expr_op_type type,
3867	void *user)
3868{
3869	isl_printer **p = user;
3870
3871	*p = isl_ast_expr_op_type_print_macro(type, *p);
3872
3873	return isl_stat_ok;
3874}
3875
3876/* Print macro definitions for all the macros used in the result
3877 * of printing "expr".
3878 */
3879__isl_give isl_printer *isl_ast_expr_print_macros(
3880	__isl_keep isl_ast_expr *expr, __isl_take isl_printer *p)
3881{
3882	if (isl_ast_expr_foreach_ast_expr_op_type(expr,
3883					    &ast_op_type_print_macro, &p) < 0)
3884		return isl_printer_free(p);
3885	return p;
3886}
3887
3888/* Print macro definitions for all the macros used in the result
3889 * of printing "node".
3890 */
3891__isl_give isl_printer *isl_ast_node_print_macros(
3892	__isl_keep isl_ast_node *node, __isl_take isl_printer *p)
3893{
3894	if (isl_ast_node_foreach_ast_expr_op_type(node,
3895					    &ast_op_type_print_macro, &p) < 0)
3896		return isl_printer_free(p);
3897	return p;
3898}
3899
3900/* Return a string containing C code representing this isl_ast_expr.
3901 */
3902__isl_give char *isl_ast_expr_to_C_str(__isl_keep isl_ast_expr *expr)
3903{
3904	isl_printer *p;
3905	char *str;
3906
3907	if (!expr)
3908		return NULL;
3909
3910	p = isl_printer_to_str(isl_ast_expr_get_ctx(expr));
3911	p = isl_printer_set_output_format(p, ISL_FORMAT_C);
3912	p = isl_printer_print_ast_expr(p, expr);
3913
3914	str = isl_printer_get_str(p);
3915
3916	isl_printer_free(p);
3917
3918	return str;
3919}
3920
3921/* Return a string containing C code representing this isl_ast_node.
3922 */
3923__isl_give char *isl_ast_node_to_C_str(__isl_keep isl_ast_node *node)
3924{
3925	isl_printer *p;
3926	char *str;
3927
3928	if (!node)
3929		return NULL;
3930
3931	p = isl_printer_to_str(isl_ast_node_get_ctx(node));
3932	p = isl_printer_set_output_format(p, ISL_FORMAT_C);
3933	p = isl_printer_print_ast_node(p, node);
3934
3935	str = isl_printer_get_str(p);
3936
3937	isl_printer_free(p);
3938
3939	return str;
3940}
3941