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
29	isl_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(ctx: options->ctx);
104
105	free(ptr: 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	*/
155	static __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(list: 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;
177	error:
178	isl_ast_expr_list_free(list: 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: 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(v: isl_val_copy(v: expr->u.v));
214	break;
215	case isl_ast_expr_id:
216	dup = isl_ast_expr_from_id(id: isl_id_copy(id: expr->u.id));
217	break;
218	case isl_ast_expr_op:
219	dup = alloc_op(op: expr->u.op.op,
220	args: isl_ast_expr_list_copy(list: 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(ctx: expr->ctx);
252
253	switch (expr->type) {
254	case isl_ast_expr_int:
255	isl_val_free(v: expr->u.v);
256	break;
257	case isl_ast_expr_id:
258	isl_id_free(id: expr->u.id);
259	break;
260	case isl_ast_expr_op:
261	isl_ast_expr_list_free(list: expr->u.op.args);
262	break;
263	case isl_ast_expr_error:
264	break;
265	}
266
267	free(ptr: expr);
268	return NULL;
269	}
270
271	isl_ctx *isl_ast_expr_get_ctx(__isl_keep isl_ast_expr *expr)
272	{
273	return expr ? expr->ctx : NULL;
274	}
275
276	enum 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(v: 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(id: 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	*/
320	static 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	*/
332	enum 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	*/
342	enum 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	*/
350	isl_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(list: expr->u.op.args);
355	}
356
357	/* This is an alternative name for the function above.
358	*/
359	isl_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(list: expr->u.op.args, index: 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	*/
385	static __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(list: 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	*/
402	static __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	*/
422	static __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(list: 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(list: expr->u.op.args);
437	expr->u.op.args = args;
438
439	return expr;
440	error:
441	isl_ast_expr_free(expr);
442	isl_ast_expr_list_free(list: 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(list: args, el: 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(list: args, index: pos, el: 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	*/
476	static 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(list: list1);
488	n2 = isl_ast_expr_list_size(list: 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(list: list1, index: i);
498	expr2 = isl_ast_expr_list_get_at(list: list2, index: i);
499	equal = isl_ast_expr_is_equal(expr1, expr2);
500	isl_ast_expr_free(expr: expr1);
501	isl_ast_expr_free(expr: 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	*/
511	isl_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(v1: expr1->u.v, v2: expr2->u.v);
524	case isl_ast_expr_id:
525	return isl_bool_ok(b: 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(list1: expr1->u.op.args,
530	list2: 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;
561	error:
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(val: 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;
612	error:
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(expr: arg);
631	expr = isl_ast_expr_alloc_op(ctx, op: type, n_arg: 1);
632
633	args = isl_ast_expr_op_take_args(expr);
634	args = isl_ast_expr_list_add(list: args, el: 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(type: 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(type: isl_ast_expr_op_address_of, arg: 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(expr: expr1);
678	expr = isl_ast_expr_alloc_op(ctx, op: type, n_arg: 2);
679
680	args = isl_ast_expr_op_take_args(expr);
681	args = isl_ast_expr_list_add(list: args, el: expr1);
682	args = isl_ast_expr_list_add(list: args, el: expr2);
683	expr = isl_ast_expr_op_restore_args(expr, args);
684
685	return expr;
686	error:
687	isl_ast_expr_free(expr: expr1);
688	isl_ast_expr_free(expr: 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(type: 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(type: 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(type: 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(type: 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(type: 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(type: 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(type: 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(type: 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(type: 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(type: 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(type: 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(type: 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(type: 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(type: 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(type: 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	*/
821	static __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(list: arguments, pos: 0, el: arg0);
826	return alloc_op(op: type, args: 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(type: isl_ast_expr_op_access, arg0: array, arguments: 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(type: isl_ast_expr_op_call, arg0: function, arguments);
845	}
846
847	/* Wrapper around isl_ast_expr_substitute_ids for use
848	* as an isl_ast_expr_list_map callback.
849	*/
850	static __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	id2expr: isl_id_to_ast_expr_copy(hmap: 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(hmap: id2expr, key: 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(list: args, fn: &substitute_ids, user: 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(hmap: id2expr);
895	return expr;
896	error:
897	isl_ast_expr_free(expr);
898	isl_id_to_ast_expr_free(hmap: id2expr);
899	return NULL;
900	}
901
902	isl_ctx *isl_ast_node_get_ctx(__isl_keep isl_ast_node *node)
903	{
904	return node ? node->ctx : NULL;
905	}
906
907	enum 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(ctx: isl_ast_expr_get_ctx(expr: guard), type: isl_ast_node_if);
941	if (!node)
942	goto error;
943	node->u.i.guard = guard;
944
945	return node;
946	error:
947	isl_ast_expr_free(expr: 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, type: 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;
973	error:
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, type: 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;
998	error:
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, type: isl_ast_node_user);
1017	if (!node)
1018	goto error;
1019
1020	node->u.e.expr = expr;
1021
1022	return node;
1023	error:
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, type: isl_ast_node_block);
1048	if (!node)
1049	goto error;
1050
1051	node->u.b.children = list;
1052
1053	return node;
1054	error:
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, index: 0);
1084	isl_ast_node_list_free(list);
1085
1086	return node;
1087	error:
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(ctx: isl_ast_node_get_ctx(node), type: 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(expr: node->u.i.guard);
1120	dup->u.i.then = isl_ast_node_copy(node: node->u.i.then);
1121	dup->u.i.else_node = isl_ast_node_copy(node: 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(node: 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(expr: node->u.f.iterator);
1129	dup->u.f.init = isl_ast_expr_copy(expr: node->u.f.init);
1130	dup->u.f.body = isl_ast_node_copy(node: node->u.f.body);
1131	if (!dup->u.f.iterator || !dup->u.f.init || !dup->u.f.body)
1132	return isl_ast_node_free(node: dup);
1133	if (node->u.f.degenerate)
1134	break;
1135	dup->u.f.cond = isl_ast_expr_copy(expr: node->u.f.cond);
1136	dup->u.f.inc = isl_ast_expr_copy(expr: node->u.f.inc);
1137	if (!dup->u.f.cond || !dup->u.f.inc)
1138	return isl_ast_node_free(node: dup);
1139	break;
1140	case isl_ast_node_block:
1141	dup->u.b.children = isl_ast_node_list_copy(list: node->u.b.children);
1142	if (!dup->u.b.children)
1143	return isl_ast_node_free(node: dup);
1144	break;
1145	case isl_ast_node_mark:
1146	dup->u.m.mark = isl_id_copy(id: node->u.m.mark);
1147	dup->u.m.node = isl_ast_node_copy(node: node->u.m.node);
1148	if (!dup->u.m.mark || !dup->u.m.node)
1149	return isl_ast_node_free(node: dup);
1150	break;
1151	case isl_ast_node_user:
1152	dup->u.e.expr = isl_ast_expr_copy(expr: node->u.e.expr);
1153	if (!dup->u.e.expr)
1154	return isl_ast_node_free(node: 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(id: node->annotation);
1163	if (!dup->annotation)
1164	return isl_ast_node_free(node: 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(expr: node->u.i.guard);
1191	isl_ast_node_free(node: node->u.i.then);
1192	isl_ast_node_free(node: node->u.i.else_node);
1193	break;
1194	case isl_ast_node_for:
1195	isl_ast_expr_free(expr: node->u.f.iterator);
1196	isl_ast_expr_free(expr: node->u.f.init);
1197	isl_ast_expr_free(expr: node->u.f.cond);
1198	isl_ast_expr_free(expr: node->u.f.inc);
1199	isl_ast_node_free(node: node->u.f.body);
1200	break;
1201	case isl_ast_node_block:
1202	isl_ast_node_list_free(list: node->u.b.children);
1203	break;
1204	case isl_ast_node_mark:
1205	isl_id_free(id: node->u.m.mark);
1206	isl_ast_node_free(node: node->u.m.node);
1207	break;
1208	case isl_ast_node_user:
1209	isl_ast_expr_free(expr: node->u.e.expr);
1210	break;
1211	case isl_ast_node_error:
1212	break;
1213	}
1214
1215	isl_id_free(id: node->annotation);
1216	isl_ctx_deref(ctx: node->ctx);
1217	free(ptr: node);
1218
1219	return NULL;
1220	}
1221
1222	/* Check that "node" is of type "type", printing "msg" if not.
1223	*/
1224	static 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	*/
1237	static isl_stat isl_ast_node_check_block(__isl_keep isl_ast_node *node)
1238	{
1239	return isl_ast_node_check_type(node, type: isl_ast_node_block,
1240	msg: "not a block node");
1241	}
1242
1243	/* Check that "node" is of type isl_ast_node_if.
1244	*/
1245	static isl_stat isl_ast_node_check_if(__isl_keep isl_ast_node *node)
1246	{
1247	return isl_ast_node_check_type(node, type: isl_ast_node_if, msg: "not an if node");
1248	}
1249
1250	/* Check that "node" is of type isl_ast_node_for.
1251	*/
1252	static isl_stat isl_ast_node_check_for(__isl_keep isl_ast_node *node)
1253	{
1254	return isl_ast_node_check_type(node, type: isl_ast_node_for,
1255	msg: "not a for node");
1256	}
1257
1258	/* Check that "node" is of type isl_ast_node_mark.
1259	*/
1260	static isl_stat isl_ast_node_check_mark(__isl_keep isl_ast_node *node)
1261	{
1262	return isl_ast_node_check_type(node, type: isl_ast_node_mark,
1263	msg: "not a mark node");
1264	}
1265
1266	/* Check that "node" is of type isl_ast_node_user.
1267	*/
1268	static isl_stat isl_ast_node_check_user(__isl_keep isl_ast_node *node)
1269	{
1270	return isl_ast_node_check_type(node, type: isl_ast_node_user,
1271	msg: "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	*/
1323	static __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	*/
1342	static __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, field: 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: 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
1368	isl_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(b: 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(expr: 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(expr: 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(expr: node->u.f.cond);
1405
1406	return isl_ast_expr_alloc_binary(type: isl_ast_expr_op_le,
1407	expr1: isl_ast_expr_copy(expr: node->u.f.iterator),
1408	expr2: isl_ast_expr_copy(expr: 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(expr: node->u.f.inc);
1423	return isl_ast_expr_alloc_int_si(ctx: isl_ast_node_get_ctx(node), i: 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	*/
1445	static __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	*/
1464	static __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, field: 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: 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	*/
1490	isl_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(b: node->u.i.else_node != NULL);
1495	}
1496
1497	/* This is an alternative name for the function above.
1498	*/
1499	isl_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: 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
1531	static
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	*/
1543	static __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	*/
1562	static __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, field: 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(expr: 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(list: 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
1592	static
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	*/
1604	static __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	*/
1623	static __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, field: 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(expr: 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(id: 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: 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
1667	static
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	*/
1679	static __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	*/
1698	static __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, field: 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(id: 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	*/
1712	static isl_stat isl_ast_node_check_any(__isl_keep isl_ast_node *node)
1713	{
1714	return isl_stat_non_null(obj: 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
1725	static
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, field: annotation);
1734	}
1735
1736	static __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	*/
1749	static __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, index: i);
1768	node = traverse(node, enter, leave, user);
1769	list = isl_ast_node_list_set_at(list, index: i, el: 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	*/
1784	static __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(node: child, enter, leave, user);
1806	node = isl_ast_node_for_restore_body(node, body: 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(node: 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(node: 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(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(node: 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	*/
1843	struct 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	*/
1853	static __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	*/
1872	static __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	*/
1888	isl_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, enter: &preorder_enter, leave: &preorder_leave, user: &data);
1896	isl_ast_node_free(node);
1897
1898	return isl_stat_non_null(obj: node);
1899	}
1900
1901	/* Internal data structure storing the arguments of
1902	* isl_ast_node_map_descendant_bottom_up.
1903	*/
1904	struct 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	*/
1915	static __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	*/
1926	static __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, enter: &postorder_enter, leave: &postorder_leave, user: &data);
1952	}
1953
1954	/* Textual C representation of the various operators.
1955	*/
1956	static 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	*/
1985	static 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	*/
2016	static 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
2045	static 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
2050	static 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
2055	static 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
2060	static 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
2067	static __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	*/
2088	static 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(op: 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(op: 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	*/
2114	static __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(printer: p);
2122
2123	arg = isl_ast_expr_list_get_at(list: expr->u.op.args, index: pos);
2124	need_parens = sub_expr_need_parens(op: expr->u.op.op, expr: arg, left);
2125
2126	if (need_parens)
2127	p = isl_printer_print_str(p, s: "(");
2128	p = print_ast_expr_c(p, expr: arg);
2129	if (need_parens)
2130	p = isl_printer_print_str(p, s: ")");
2131
2132	isl_ast_expr_free(expr: 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	*/
2144	struct 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	*/
2150	static 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	*/
2158	static 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(ptr: names->op_str[i]);
2168	free(ptr: user);
2169	}
2170
2171	/* Create an identifier that is used to store
2172	* an isl_ast_expr_op_names note.
2173	*/
2174	static __isl_give isl_id *names_id(isl_ctx *ctx)
2175	{
2176	return isl_id_alloc(ctx, name: "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	*/
2183	static __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(printer: p);
2195	if (has_note)
2196	return p;
2197
2198	ctx = isl_printer_get_ctx(printer: p);
2199	note = note_create(ctx);
2200	if (!note)
2201	return isl_printer_free(printer: p);
2202	note_id = isl_id_alloc(ctx, NULL, user: note);
2203	if (!note_id)
2204	note_free(note);
2205	else
2206	note_id = isl_id_set_free_user(id: note_id, free_user: note_free);
2207
2208	p = isl_printer_set_note(p, id: isl_id_copy(id), note: note_id);
2209
2210	return p;
2211	}
2212
2213	/* Ensure that "p" has an isl_ast_expr_op_names note identified by "id".
2214	*/
2215	static __isl_give isl_printer *alloc_names(__isl_take isl_printer *p,
2216	__isl_keep isl_id *id)
2217	{
2218	return alloc_note(p, id, note_create: &create_names, note_free: &free_names);
2219	}
2220
2221	/* Retrieve the note identified by "id" from "p".
2222	* The note is assumed to exist.
2223	*/
2224	static 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, id: 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(ctx: isl_printer_get_ctx(printer: 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(printer: p);
2259	free(ptr: names->op_str[type]);
2260	names->op_str[type] = strdup(s: 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	*/
2280	static 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(ctx: isl_printer_get_ctx(printer: 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	*/
2299	static __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, index: 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	*/
2313	static __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(list: expr->u.op.args);
2320	if (n < 0)
2321	return isl_printer_free(printer: p);
2322
2323	for (i = 1; i < n; ++i) {
2324	p = isl_printer_print_str(p, s: get_op_str_c(p, type: expr->u.op.op));
2325	p = isl_printer_print_str(p, s: "(");
2326	}
2327	p = print_at_c(p, list: expr->u.op.args, pos: 0);
2328	for (i = 1; i < n; ++i) {
2329	p = isl_printer_print_str(p, s: ", ");
2330	p = print_at_c(p, list: expr->u.op.args, pos: i);
2331	p = isl_printer_print_str(p, s: ")");
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	*/
2341	static __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(list: expr->u.op.args);
2348	if (n < 0)
2349	return isl_printer_free(printer: p);
2350
2351	p = print_at_c(p, list: expr->u.op.args, pos: 0);
2352	p = isl_printer_print_str(p, s: "(");
2353	for (i = 1; i < n; ++i) {
2354	if (i != 1)
2355	p = isl_printer_print_str(p, s: ", ");
2356	p = print_at_c(p, list: expr->u.op.args, pos: i);
2357	}
2358	p = isl_printer_print_str(p, s: ")");
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	*/
2367	static __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(list: expr->u.op.args);
2374	if (n < 0)
2375	return isl_printer_free(printer: p);
2376
2377	p = print_at_c(p, list: expr->u.op.args, pos: 0);
2378	for (i = 1; i < n; ++i) {
2379	p = isl_printer_print_str(p, s: "[");
2380	p = print_at_c(p, list: expr->u.op.args, pos: i);
2381	p = isl_printer_print_str(p, s: "]");
2382	}
2383
2384	return p;
2385	}
2386
2387	/* Print "expr" to "p" in C format.
2388	*/
2389	static __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(printer: 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(list: expr->u.op.args);
2410	if (n < 0)
2411	return isl_printer_free(printer: p);
2412	if (n == 1) {
2413	p = isl_printer_print_str(p,
2414	s: get_op_str_c(p, type: expr->u.op.op));
2415	p = print_sub_expr_c(p, expr, pos: 0, left: 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, type: isl_ast_expr_op_fdiv_q);
2422	p = isl_printer_print_str(p, s: name);
2423	p = isl_printer_print_str(p, s: "(");
2424	p = print_at_c(p, list: expr->u.op.args, pos: 0);
2425	p = isl_printer_print_str(p, s: ", ");
2426	p = print_at_c(p, list: expr->u.op.args, pos: 1);
2427	p = isl_printer_print_str(p, s: ")");
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, list: expr->u.op.args, pos: 0);
2438	p = isl_printer_print_str(p, s: " ? ");
2439	p = print_at_c(p, list: expr->u.op.args, pos: 1);
2440	p = isl_printer_print_str(p, s: " : ");
2441	p = print_at_c(p, list: expr->u.op.args, pos: 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, pos: 0, left: 1);
2449	if (expr->u.op.op != isl_ast_expr_op_member)
2450	p = isl_printer_print_str(p, s: " ");
2451	p = isl_printer_print_str(p, s: get_op_str_c(p, type: expr->u.op.op));
2452	if (expr->u.op.op != isl_ast_expr_op_member)
2453	p = isl_printer_print_str(p, s: " ");
2454	p = print_sub_expr_c(p, expr, pos: 1, left: 0);
2455	break;
2456	case isl_ast_expr_id:
2457	p = isl_printer_print_str(p, s: isl_id_get_name(id: expr->u.id));
2458	break;
2459	case isl_ast_expr_int:
2460	p = isl_printer_print_val(p, v: 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	*/
2472	static 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
2501	static __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	*/
2510	static __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(printer: p);
2519	if (n == 0)
2520	return p;
2521
2522	p = isl_printer_print_str(p, s: "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, pos: i);
2529	p = print_ast_expr_isl(p, expr: arg);
2530	isl_ast_expr_free(expr: 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	*/
2540	static 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	*/
2550	static __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(printer: 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(printer: 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(printer: p);
2570	p = isl_printer_print_str(p, s: expr_str[type]);
2571	p = isl_printer_yaml_next(p);
2572	p = isl_printer_print_str(p, s: 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, s: 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, s: 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	*/
2642	static __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, msg: "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	*/
2664	static 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(s1: str, s2: expected);
2673	free(ptr: str);
2674
2675	if (!ok) {
2676	isl_stream_error(s, NULL, msg: "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	*/
2697	static __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, expected: "args") < 0)
2708	return NULL;
2709
2710	list = isl_stream_yaml_read_ast_expr_list(s);
2711
2712	return alloc_op(op, args: 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	*/
2718	static __isl_give isl_ast_expr *read_id(__isl_keep isl_stream *s)
2719	{
2720	return isl_ast_expr_from_id(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	*/
2726	static __isl_give isl_ast_expr *read_int(__isl_keep isl_stream *s)
2727	{
2728	return isl_ast_expr_from_val(v: 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, msg: "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
2795	static __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	*/
2800	static __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(printer: 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, index: 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	*/
2828	static __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, s: "iterator");
2835	p = isl_printer_yaml_next(p);
2836	p = isl_printer_print_ast_expr(p, expr: node->u.f.iterator);
2837	p = isl_printer_yaml_next(p);
2838	if (node->u.f.degenerate) {
2839	p = isl_printer_print_str(p, s: "value");
2840	p = isl_printer_yaml_next(p);
2841	p = isl_printer_print_ast_expr(p, expr: node->u.f.init);
2842	p = isl_printer_yaml_next(p);
2843	} else {
2844	p = isl_printer_print_str(p, s: "init");
2845	p = isl_printer_yaml_next(p);
2846	p = isl_printer_print_ast_expr(p, expr: node->u.f.init);
2847	p = isl_printer_yaml_next(p);
2848	p = isl_printer_print_str(p, s: "cond");
2849	p = isl_printer_yaml_next(p);
2850	p = isl_printer_print_ast_expr(p, expr: node->u.f.cond);
2851	p = isl_printer_yaml_next(p);
2852	p = isl_printer_print_str(p, s: "inc");
2853	p = isl_printer_yaml_next(p);
2854	p = isl_printer_print_ast_expr(p, expr: 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, s: "body");
2859	p = isl_printer_yaml_next(p);
2860	p = isl_printer_print_ast_node(p, node: 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, s: "mark");
2868	p = isl_printer_yaml_next(p);
2869	p = isl_printer_print_id(p, id: node->u.m.mark);
2870	p = isl_printer_yaml_next(p);
2871	p = isl_printer_print_str(p, s: "node");
2872	p = isl_printer_yaml_next(p);
2873	p = isl_printer_print_ast_node(p, node: 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, s: "user");
2879	p = isl_printer_yaml_next(p);
2880	p = isl_printer_print_ast_expr(p, expr: 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, s: "guard");
2886	p = isl_printer_yaml_next(p);
2887	p = isl_printer_print_ast_expr(p, expr: node->u.i.guard);
2888	p = isl_printer_yaml_next(p);
2889	if (node->u.i.then) {
2890	p = isl_printer_print_str(p, s: "then");
2891	p = isl_printer_yaml_next(p);
2892	p = isl_printer_print_ast_node(p, node: 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, s: "else");
2897	p = isl_printer_yaml_next(p);
2898	p = isl_printer_print_ast_node(p, node: 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, list: 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	*/
2925	static 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
2942	static __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);
2945	static __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	*/
2970	static __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(printer: p);
2976
2977	if (!force_block && !else_node && !need_block(node)) {
2978	p = isl_printer_end_line(p);
2979	p = isl_printer_indent(p, indent: 2);
2980	p = isl_ast_node_print(node, p,
2981	options: isl_ast_print_options_copy(options));
2982	p = isl_printer_indent(p, indent: -2);
2983	return p;
2984	}
2985
2986	p = isl_printer_print_str(p, s: " {");
2987	p = isl_printer_end_line(p);
2988	p = isl_printer_indent(p, indent: 2);
2989	p = print_ast_node_c(p, node, options, in_block: 1, in_list: 0);
2990	p = isl_printer_indent(p, indent: -2);
2991	p = isl_printer_start_line(p);
2992	p = isl_printer_print_str(p, s: "}");
2993	if (else_node) {
2994	if (else_node->type == isl_ast_node_if) {
2995	p = isl_printer_print_str(p, s: " else ");
2996	p = print_if_c(p, node: else_node, options, new_line: 0, force_block: 1);
2997	} else {
2998	p = isl_printer_print_str(p, s: " else");
2999	p = print_body_c(p, node: else_node, NULL, options, force_block: 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	*/
3009	static __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, s: "{");
3013	p = isl_printer_end_line(p);
3014	p = isl_printer_indent(p, indent: 2);
3015
3016	return p;
3017	}
3018
3019	/* Print the end of a compound statement.
3020	*/
3021	static __isl_give isl_printer *end_block(__isl_take isl_printer *p)
3022	{
3023	p = isl_printer_indent(p, indent: -2);
3024	p = isl_printer_start_line(p);
3025	p = isl_printer_print_str(p, s: "}");
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	*/
3050	static __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(ctx: isl_printer_get_ctx(printer: p));
3059	if (!node->u.f.degenerate) {
3060	id = isl_ast_expr_get_id(expr: 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, s: "for (");
3065	p = isl_printer_print_str(p, s: type);
3066	p = isl_printer_print_str(p, s: " ");
3067	p = isl_printer_print_str(p, s: name);
3068	p = isl_printer_print_str(p, s: " = ");
3069	p = isl_printer_print_ast_expr(p, expr: node->u.f.init);
3070	p = isl_printer_print_str(p, s: "; ");
3071	p = isl_printer_print_ast_expr(p, expr: node->u.f.cond);
3072	p = isl_printer_print_str(p, s: "; ");
3073	p = isl_printer_print_str(p, s: name);
3074	p = isl_printer_print_str(p, s: " += ");
3075	p = isl_printer_print_ast_expr(p, expr: node->u.f.inc);
3076	p = isl_printer_print_str(p, s: ")");
3077	p = print_body_c(p, node: node->u.f.body, NULL, options, force_block: 0);
3078	} else {
3079	id = isl_ast_expr_get_id(expr: 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, s: type);
3086	p = isl_printer_print_str(p, s: " ");
3087	p = isl_printer_print_str(p, s: name);
3088	p = isl_printer_print_str(p, s: " = ");
3089	p = isl_printer_print_ast_expr(p, expr: node->u.f.init);
3090	p = isl_printer_print_str(p, s: ";");
3091	p = isl_printer_end_line(p);
3092	p = print_ast_node_c(p, node: node->u.f.body, options, in_block: 1, in_list: 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	*/
3104	static __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, s: "if (");
3112	p = isl_printer_print_ast_expr(p, expr: node->u.i.guard);
3113	p = isl_printer_print_str(p, s: ")");
3114	p = print_body_c(p, node: node->u.i.then, else_node: 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	*/
3129	static __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, new_line: 1, force_block: 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(list: 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, s: "// ");
3154	p = isl_printer_print_str(p, s: isl_id_get_name(id: node->u.m.mark));
3155	p = isl_printer_end_line(p);
3156	p = print_ast_node_c(p, node: node->u.m.node, options, in_block: 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, expr: node->u.e.expr);
3165	p = isl_printer_print_str(p, s: ";");
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, in_block: 0, in_list: 0);
3182	isl_ast_print_options_free(options);
3183	return p;
3184	error:
3185	isl_ast_print_options_free(options);
3186	isl_printer_free(printer: 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, new_line: 1, force_block: 0);
3198	isl_ast_print_options_free(options);
3199	return p;
3200	error:
3201	isl_ast_print_options_free(options);
3202	isl_printer_free(printer: 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, in_list: 0);
3229	isl_ast_print_options_free(options);
3230	return p;
3231	error:
3232	isl_ast_print_options_free(options);
3233	isl_printer_free(printer: 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(ctx: isl_printer_get_ctx(printer: 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(printer: p);
3276
3277	for (i = 0; i < list->n; ++i)
3278	p = print_ast_node_c(p, node: list->p[i], options, in_block: 1, in_list: 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	*/
3288	static 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(b: 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	*/
3311	static __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(list: 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	*/
3325	static 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
3347	static __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, expected: "body") < 0)
3351	return isl_ast_node_free(node);
3352	node = isl_ast_node_for_set_body(node, field: 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	*/
3366	static __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(s1: key, s2: "value");
3389	is_init = !strcmp(s1: key, s2: "init");
3390	free(ptr: 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, field: 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, expected: "cond") < 0)
3407	return isl_ast_node_free(node);
3408	node = isl_ast_node_for_set_cond(node, field: 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, expected: "inc") < 0)
3412	return isl_ast_node_free(node);
3413	node = isl_ast_node_for_set_inc(node, field: 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	*/
3426	static __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, expected: "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;
3443	error:
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	*/
3451	static __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(expr: 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	*/
3464	static __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(guard: 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, expected: "then") < 0)
3476	return isl_ast_node_free(node);
3477	node = isl_ast_node_if_set_then(node, field: 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, expected: "else") < 0)
3484	return isl_ast_node_free(node);
3485	node = isl_ast_node_if_set_else_node(node, field: 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, msg: "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
3568	static 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	*/
3573	static 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: *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	*/
3586	static 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(list: expr->u.op.args,
3602	fn: &entry_required_macros, user: &macros);
3603
3604	return macros;
3605	}
3606
3607	static 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	*/
3613	static 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(expr: node->u.f.init, macros);
3621	if (!node->u.f.degenerate) {
3622	macros = ast_expr_required_macros(expr: node->u.f.cond,
3623	macros);
3624	macros = ast_expr_required_macros(expr: node->u.f.inc,
3625	macros);
3626	}
3627	macros = ast_node_required_macros(node: node->u.f.body, macros);
3628	break;
3629	case isl_ast_node_if:
3630	macros = ast_expr_required_macros(expr: node->u.i.guard, macros);
3631	macros = ast_node_required_macros(node: node->u.i.then, macros);
3632	if (node->u.i.else_node)
3633	macros = ast_node_required_macros(node: node->u.i.else_node,
3634	macros);
3635	break;
3636	case isl_ast_node_block:
3637	macros = ast_node_list_required_macros(list: node->u.b.children,
3638	macros);
3639	break;
3640	case isl_ast_node_mark:
3641	macros = ast_node_required_macros(node: node->u.m.node, macros);
3642	break;
3643	case isl_ast_node_user:
3644	macros = ast_expr_required_macros(expr: 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	*/
3656	static 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(node: 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	*/
3671	struct 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	*/
3677	static 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	*/
3684	static void free_printed(void *user)
3685	{
3686	free(ptr: user);
3687	}
3688
3689	/* Ensure that "p" has an isl_ast_expr_op_printed note identified by "id".
3690	*/
3691	static __isl_give isl_printer *alloc_printed(__isl_take isl_printer *p,
3692	__isl_keep isl_id *id)
3693	{
3694	return alloc_note(p, id, note_create: &create_printed, note_free: &free_printed);
3695	}
3696
3697	/* Create an identifier that is used to store
3698	* an isl_ast_expr_op_printed note.
3699	*/
3700	static __isl_give isl_id *printed_id(isl_ctx *ctx)
3701	{
3702	return isl_id_alloc(ctx, name: "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	*/
3713	static 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(printer: 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(ctx: isl_printer_get_ctx(printer: 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(printer: 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, s: "#define ");
3766	p = isl_printer_print_str(p, s: get_op_str_c(p, type));
3767	p = isl_printer_print_str(p,
3768	s: "(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, s: "#define ");
3774	p = isl_printer_print_str(p, s: get_op_str_c(p, type));
3775	p = isl_printer_print_str(p,
3776	s: "(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, s: "#define ");
3782	p = isl_printer_print_str(p, s: get_op_str_c(p, type));
3783	p = isl_printer_print_str(p,
3784	s: "(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	*/
3806	static 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	*/
3823	isl_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, macros: 0);
3832	return foreach_ast_expr_op_type(macros, fn, user);
3833	}
3834
3835	/* This is an alternative name for the function above.
3836	*/
3837	isl_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	*/
3846	isl_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, macros: 0);
3855	return foreach_ast_expr_op_type(macros, fn, user);
3856	}
3857
3858	/* This is an alternative name for the function above.
3859	*/
3860	isl_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
3866	static 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: *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	fn: &ast_op_type_print_macro, user: &p) < 0)
3884	return isl_printer_free(printer: 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	fn: &ast_op_type_print_macro, user: &p) < 0)
3896	return isl_printer_free(printer: 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(ctx: 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(printer: p);
3915
3916	isl_printer_free(printer: 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(ctx: 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(printer: p);
3936
3937	isl_printer_free(printer: p);
3938
3939	return str;
3940	}
3941