1	/*
2	* Copyright 2008-2009 Katholieke Universiteit Leuven
3	* Copyright 2010 INRIA Saclay
4	* Copyright 2012-2013 Ecole Normale Superieure
5	* Copyright 2019,2022 Cerebras Systems
6	*
7	* Use of this software is governed by the MIT license
8	*
9	* Written by Sven Verdoolaege, K.U.Leuven, Departement
10	* Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
11	* and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
12	* ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
13	* and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14	* and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA
15	*/
16
17	#include <ctype.h>
18	#include <stdio.h>
19	#include <string.h>
20	#include <isl_ctx_private.h>
21	#include <isl_map_private.h>
22	#include <isl_id_private.h>
23	#include <isl/set.h>
24	#include <isl_seq.h>
25	#include <isl_stream_private.h>
26	#include <isl/obj.h>
27	#include "isl_polynomial_private.h"
28	#include <isl/union_set.h>
29	#include <isl/union_map.h>
30	#include <isl_mat_private.h>
31	#include <isl_aff_private.h>
32	#include <isl_vec_private.h>
33	#include <isl/list.h>
34	#include <isl_val_private.h>
35
36	struct variable {
37	char *name;
38	int pos;
39	struct variable *next;
40	};
41
42	struct vars {
43	struct isl_ctx *ctx;
44	int n;
45	struct variable *v;
46	};
47
48	static struct vars *vars_new(struct isl_ctx *ctx)
49	{
50	struct vars *v;
51	v = isl_alloc_type(ctx, struct vars);
52	if (!v)
53	return NULL;
54	v->ctx = ctx;
55	v->n = 0;
56	v->v = NULL;
57	return v;
58	}
59
60	static void variable_free(struct variable *var)
61	{
62	while (var) {
63	struct variable *next = var->next;
64	free(ptr: var->name);
65	free(ptr: var);
66	var = next;
67	}
68	}
69
70	static void vars_free(struct vars *v)
71	{
72	if (!v)
73	return;
74	variable_free(var: v->v);
75	free(ptr: v);
76	}
77
78	static void vars_drop(struct vars *v, int n)
79	{
80	struct variable *var;
81
82	if (!v || !v->v)
83	return;
84
85	v->n -= n;
86
87	var = v->v;
88	while (--n >= 0) {
89	struct variable *next = var->next;
90	free(ptr: var->name);
91	free(ptr: var);
92	var = next;
93	}
94	v->v = var;
95	}
96
97	static struct variable *variable_new(struct vars *v, const char *name, int len,
98	int pos)
99	{
100	struct variable *var;
101	var = isl_calloc_type(v->ctx, struct variable);
102	if (!var)
103	goto error;
104	var->name = strdup(s: name);
105	var->name[len] = '\0';
106	var->pos = pos;
107	var->next = v->v;
108	return var;
109	error:
110	variable_free(var: v->v);
111	return NULL;
112	}
113
114	static int vars_pos(struct vars *v, const char *s, int len)
115	{
116	int pos;
117	struct variable *q;
118
119	if (len == -1)
120	len = strlen(s: s);
121	for (q = v->v; q; q = q->next) {
122	if (strncmp(s1: q->name, s2: s, n: len) == 0 && q->name[len] == '\0')
123	break;
124	}
125	if (q)
126	pos = q->pos;
127	else {
128	pos = v->n;
129	v->v = variable_new(v, name: s, len, pos: v->n);
130	if (!v->v)
131	return -1;
132	v->n++;
133	}
134	return pos;
135	}
136
137	static int vars_add_anon(struct vars *v)
138	{
139	v->v = variable_new(v, name: "", len: 0, pos: v->n);
140
141	if (!v->v)
142	return -1;
143	v->n++;
144
145	return 0;
146	}
147
148	/* Obtain next token, with some preprocessing.
149	* In particular, evaluate expressions of the form x^y,
150	* with x and y values.
151	*/
152	static struct isl_token *next_token(__isl_keep isl_stream *s)
153	{
154	struct isl_token *tok, *tok2;
155
156	tok = isl_stream_next_token(s);
157	if (!tok || tok->type != ISL_TOKEN_VALUE)
158	return tok;
159	if (!isl_stream_eat_if_available(s, type: '^'))
160	return tok;
161	tok2 = isl_stream_next_token(s);
162	if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
163	isl_stream_error(s, tok: tok2, msg: "expecting constant value");
164	goto error;
165	}
166
167	isl_int_pow_ui(tok->u.v, tok->u.v, isl_int_get_ui(tok2->u.v));
168
169	isl_token_free(tok: tok2);
170	return tok;
171	error:
172	isl_token_free(tok);
173	isl_token_free(tok: tok2);
174	return NULL;
175	}
176
177	/* Read an isl_val from "s".
178	*
179	* The following token sequences are recognized
180	*
181	* "infty" -> infty
182	* "-" "infty" -> -infty
183	* "NaN" -> NaN
184	* n "/" d -> n/d
185	* "-" n "/" d -> -n/d
186	* v -> v
187	* "-" v -> -v
188	*
189	* where n, d and v are integer constants.
190	*/
191	__isl_give isl_val *isl_stream_read_val(__isl_keep isl_stream *s)
192	{
193	struct isl_token *tok = NULL;
194	struct isl_token *tok2 = NULL;
195	int sign = 1;
196	isl_val *val;
197
198	if (isl_stream_eat_if_available(s, type: '-'))
199	sign = -1;
200	tok = next_token(s);
201	if (!tok) {
202	isl_stream_error(s, NULL, msg: "unexpected EOF");
203	goto error;
204	}
205	if (tok->type == ISL_TOKEN_INFTY) {
206	isl_token_free(tok);
207	if (sign > 0)
208	return isl_val_infty(ctx: s->ctx);
209	else
210	return isl_val_neginfty(ctx: s->ctx);
211	}
212	if (sign > 0 && tok->type == ISL_TOKEN_NAN) {
213	isl_token_free(tok);
214	return isl_val_nan(ctx: s->ctx);
215	}
216	if (tok->type != ISL_TOKEN_VALUE) {
217	isl_stream_error(s, tok, msg: "expecting value");
218	goto error;
219	}
220
221	if (sign < 0)
222	isl_int_neg(tok->u.v, tok->u.v);
223
224	if (isl_stream_eat_if_available(s, type: '/')) {
225	tok2 = next_token(s);
226	if (!tok2) {
227	isl_stream_error(s, NULL, msg: "unexpected EOF");
228	goto error;
229	}
230	if (tok2->type != ISL_TOKEN_VALUE) {
231	isl_stream_error(s, tok: tok2, msg: "expecting value");
232	goto error;
233	}
234	val = isl_val_rat_from_isl_int(ctx: s->ctx, n: tok->u.v, d: tok2->u.v);
235	val = isl_val_normalize(v: val);
236	} else {
237	val = isl_val_int_from_isl_int(ctx: s->ctx, n: tok->u.v);
238	}
239
240	isl_token_free(tok);
241	isl_token_free(tok: tok2);
242	return val;
243	error:
244	isl_token_free(tok);
245	isl_token_free(tok: tok2);
246	return NULL;
247	}
248
249	#undef TYPE_BASE
250	#define TYPE_BASE val
251	#include "isl_read_from_str_templ.c"
252
253	static isl_stat accept_cst_factor(__isl_keep isl_stream *s, isl_int *f)
254	{
255	struct isl_token *tok;
256
257	if (isl_stream_eat_if_available(s, type: '-'))
258	isl_int_neg(*f, *f);
259	tok = next_token(s);
260	if (!tok || tok->type != ISL_TOKEN_VALUE) {
261	isl_stream_error(s, tok, msg: "expecting constant value");
262	goto error;
263	}
264
265	isl_int_mul(*f, *f, tok->u.v);
266
267	isl_token_free(tok);
268
269	if (isl_stream_eat_if_available(s, type: '*'))
270	return accept_cst_factor(s, f);
271
272	return isl_stat_ok;
273	error:
274	isl_token_free(tok);
275	return isl_stat_error;
276	}
277
278	/* Given an affine expression aff, return an affine expression
279	* for aff % d, with d the next token on the stream, which is
280	* assumed to be a constant.
281	*
282	* We introduce an integer division q = [aff/d] and the result
283	* is set to aff - d q.
284	*/
285	static __isl_give isl_pw_aff *affine_mod(__isl_keep isl_stream *s,
286	struct vars *v, __isl_take isl_pw_aff *aff)
287	{
288	struct isl_token *tok;
289	isl_pw_aff *q;
290
291	tok = next_token(s);
292	if (!tok || tok->type != ISL_TOKEN_VALUE) {
293	isl_stream_error(s, tok, msg: "expecting constant value");
294	goto error;
295	}
296
297	q = isl_pw_aff_copy(pwaff: aff);
298	q = isl_pw_aff_scale_down(pwaff: q, f: tok->u.v);
299	q = isl_pw_aff_floor(pwaff: q);
300	q = isl_pw_aff_scale(pwaff: q, f: tok->u.v);
301
302	aff = isl_pw_aff_sub(pwaff1: aff, pwaff2: q);
303
304	isl_token_free(tok);
305	return aff;
306	error:
307	isl_pw_aff_free(pwaff: aff);
308	isl_token_free(tok);
309	return NULL;
310	}
311
312	static __isl_give isl_pw_aff *accept_affine(__isl_keep isl_stream *s,
313	__isl_take isl_space *space, struct vars *v);
314	static __isl_give isl_pw_aff_list *accept_affine_list(__isl_keep isl_stream *s,
315	__isl_take isl_space *space, struct vars *v);
316
317	static __isl_give isl_pw_aff *accept_minmax(__isl_keep isl_stream *s,
318	__isl_take isl_space *space, struct vars *v)
319	{
320	struct isl_token *tok;
321	isl_pw_aff_list *list = NULL;
322	int min;
323
324	tok = isl_stream_next_token(s);
325	if (!tok)
326	goto error;
327	min = tok->type == ISL_TOKEN_MIN;
328	isl_token_free(tok);
329
330	if (isl_stream_eat(s, type: '('))
331	goto error;
332
333	list = accept_affine_list(s, space: isl_space_copy(space), v);
334	if (!list)
335	goto error;
336
337	if (isl_stream_eat(s, type: ')'))
338	goto error;
339
340	isl_space_free(space);
341	return min ? isl_pw_aff_list_min(list) : isl_pw_aff_list_max(list);
342	error:
343	isl_space_free(space);
344	isl_pw_aff_list_free(list);
345	return NULL;
346	}
347
348	/* Divide "pa" by an integer constant read from the stream.
349	*/
350	static __isl_give isl_pw_aff *pw_aff_div_by_cst(__isl_keep isl_stream *s,
351	__isl_take isl_pw_aff *pa)
352	{
353	struct isl_token *tok;
354
355	tok = next_token(s);
356	if (!tok || tok->type != ISL_TOKEN_VALUE) {
357	isl_stream_error(s, tok, msg: "expecting denominator");
358	isl_token_free(tok);
359	return isl_pw_aff_free(pwaff: pa);
360	}
361
362	pa = isl_pw_aff_scale_down(pwaff: pa, f: tok->u.v);
363
364	isl_token_free(tok);
365
366	return pa;
367	}
368
369	/* Return the (signed) value that is next on the stream,
370	* using "next" to read the next token and printing "msg" in case of an error.
371	*/
372	static struct isl_token *next_signed_value_fn(__isl_keep isl_stream *s,
373	struct isl_token *(*next)(__isl_keep isl_stream *s), char *msg)
374	{
375	struct isl_token *tok;
376	int sign = 1;
377
378	if (isl_stream_eat_if_available(s, type: '-'))
379	sign = -1;
380	tok = next(s);
381	if (!tok || tok->type != ISL_TOKEN_VALUE) {
382	isl_stream_error(s, tok, msg);
383	isl_token_free(tok);
384	return NULL;
385	}
386	if (sign < 0)
387	isl_int_neg(tok->u.v, tok->u.v);
388	return tok;
389	}
390
391	/* Return the (signed) value that is next on the stream,
392	* printing "msg" in case of an error.
393	*/
394	static struct isl_token *next_signed_value(__isl_keep isl_stream *s, char *msg)
395	{
396	return next_signed_value_fn(s, next: &isl_stream_next_token, msg);
397	}
398
399	/* Return the (signed) value that is next on the stream,
400	* provided it is on the same line,
401	* printing "msg" in case of an error.
402	*/
403	static struct isl_token *next_signed_value_on_same_line(
404	__isl_keep isl_stream *s, char *msg)
405	{
406	return next_signed_value_fn(s,
407	next: &isl_stream_next_token_on_same_line, msg);
408	}
409
410	/* Is "tok" the start of an integer division?
411	*/
412	static int is_start_of_div(struct isl_token *tok)
413	{
414	if (!tok)
415	return 0;
416	if (tok->type == '[')
417	return 1;
418	if (tok->type == ISL_TOKEN_FLOOR)
419	return 1;
420	if (tok->type == ISL_TOKEN_CEIL)
421	return 1;
422	if (tok->type == ISL_TOKEN_FLOORD)
423	return 1;
424	if (tok->type == ISL_TOKEN_CEILD)
425	return 1;
426	return 0;
427	}
428
429	/* Read an integer division from "s" and return it as an isl_pw_aff.
430	*
431	* The integer division can be of the form
432	*
433	* [<affine expression>]
434	* floor(<affine expression>)
435	* ceil(<affine expression>)
436	* floord(<affine expression>,<denominator>)
437	* ceild(<affine expression>,<denominator>)
438	*/
439	static __isl_give isl_pw_aff *accept_div(__isl_keep isl_stream *s,
440	__isl_take isl_space *space, struct vars *v)
441	{
442	int f = 0;
443	int c = 0;
444	int extra = 0;
445	isl_pw_aff *pwaff = NULL;
446
447	if (isl_stream_eat_if_available(s, type: ISL_TOKEN_FLOORD))
448	extra = f = 1;
449	else if (isl_stream_eat_if_available(s, type: ISL_TOKEN_CEILD))
450	extra = c = 1;
451	else if (isl_stream_eat_if_available(s, type: ISL_TOKEN_FLOOR))
452	f = 1;
453	else if (isl_stream_eat_if_available(s, type: ISL_TOKEN_CEIL))
454	c = 1;
455	if (f || c) {
456	if (isl_stream_eat(s, type: '('))
457	goto error;
458	} else {
459	if (isl_stream_eat(s, type: '['))
460	goto error;
461	}
462
463	pwaff = accept_affine(s, space: isl_space_copy(space), v);
464
465	if (extra) {
466	if (isl_stream_eat(s, type: ','))
467	goto error;
468
469	pwaff = pw_aff_div_by_cst(s, pa: pwaff);
470	}
471
472	if (c)
473	pwaff = isl_pw_aff_ceil(pwaff);
474	else
475	pwaff = isl_pw_aff_floor(pwaff);
476
477	if (f || c) {
478	if (isl_stream_eat(s, type: ')'))
479	goto error;
480	} else {
481	if (isl_stream_eat(s, type: ']'))
482	goto error;
483	}
484
485	isl_space_free(space);
486	return pwaff;
487	error:
488	isl_space_free(space);
489	isl_pw_aff_free(pwaff);
490	return NULL;
491	}
492
493	static __isl_give isl_pw_aff *accept_affine_factor(__isl_keep isl_stream *s,
494	__isl_take isl_space *space, struct vars *v)
495	{
496	struct isl_token *tok = NULL;
497	isl_pw_aff *res = NULL;
498
499	tok = next_token(s);
500	if (!tok) {
501	isl_stream_error(s, NULL, msg: "unexpected EOF");
502	goto error;
503	}
504
505	if (tok->type == ISL_TOKEN_AFF) {
506	res = isl_pw_aff_copy(pwaff: tok->u.pwaff);
507	isl_token_free(tok);
508	} else if (tok->type == ISL_TOKEN_IDENT) {
509	int n = v->n;
510	int pos = vars_pos(v, s: tok->u.s, len: -1);
511	isl_aff *aff;
512
513	if (pos < 0)
514	goto error;
515	if (pos >= n) {
516	vars_drop(v, n: v->n - n);
517	isl_stream_error(s, tok, msg: "unknown identifier");
518	goto error;
519	}
520
521	aff = isl_aff_zero_on_domain(ls: isl_local_space_from_space(space: isl_space_copy(space)));
522	if (!aff)
523	goto error;
524	aff->v = isl_vec_set_element_si(vec: aff->v, pos: 2 + pos, v: 1);
525	if (!aff->v)
526	aff = isl_aff_free(aff);
527	res = isl_pw_aff_from_aff(aff);
528	isl_token_free(tok);
529	} else if (tok->type == ISL_TOKEN_VALUE) {
530	if (isl_stream_eat_if_available(s, type: '*') ||
531	isl_stream_next_token_is(s, type: ISL_TOKEN_IDENT)) {
532	if (isl_stream_eat_if_available(s, type: '-'))
533	isl_int_neg(tok->u.v, tok->u.v);
534	res = accept_affine_factor(s, space: isl_space_copy(space), v);
535	res = isl_pw_aff_scale(pwaff: res, f: tok->u.v);
536	} else {
537	isl_local_space *ls;
538	isl_aff *aff;
539	ls = isl_local_space_from_space(space: isl_space_copy(space));
540	aff = isl_aff_zero_on_domain(ls);
541	aff = isl_aff_add_constant(aff, v: tok->u.v);
542	res = isl_pw_aff_from_aff(aff);
543	}
544	isl_token_free(tok);
545	} else if (tok->type == '(') {
546	isl_token_free(tok);
547	tok = NULL;
548	res = accept_affine(s, space: isl_space_copy(space), v);
549	if (!res)
550	goto error;
551	if (isl_stream_eat(s, type: ')'))
552	goto error;
553	} else if (is_start_of_div(tok)) {
554	isl_stream_push_token(s, tok);
555	tok = NULL;
556	res = accept_div(s, space: isl_space_copy(space), v);
557	} else if (tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX) {
558	isl_stream_push_token(s, tok);
559	tok = NULL;
560	res = accept_minmax(s, space: isl_space_copy(space), v);
561	} else {
562	isl_stream_error(s, tok, msg: "expecting factor");
563	goto error;
564	}
565	if (isl_stream_eat_if_available(s, type: '%') ||
566	isl_stream_eat_if_available(s, type: ISL_TOKEN_MOD)) {
567	isl_space_free(space);
568	return affine_mod(s, v, aff: res);
569	}
570	if (isl_stream_eat_if_available(s, type: '*')) {
571	isl_int f;
572	isl_int_init(f);
573	isl_int_set_si(f, 1);
574	if (accept_cst_factor(s, f: &f) < 0) {
575	isl_int_clear(f);
576	goto error2;
577	}
578	res = isl_pw_aff_scale(pwaff: res, f);
579	isl_int_clear(f);
580	}
581	if (isl_stream_eat_if_available(s, type: '/'))
582	res = pw_aff_div_by_cst(s, pa: res);
583	if (isl_stream_eat_if_available(s, type: ISL_TOKEN_INT_DIV))
584	res = isl_pw_aff_floor(pwaff: pw_aff_div_by_cst(s, pa: res));
585
586	isl_space_free(space);
587	return res;
588	error:
589	isl_token_free(tok);
590	error2:
591	isl_pw_aff_free(pwaff: res);
592	isl_space_free(space);
593	return NULL;
594	}
595
596	/* Return a piecewise affine expression defined on the specified domain
597	* that represents NaN.
598	*/
599	static __isl_give isl_pw_aff *nan_on_domain(__isl_keep isl_space *space)
600	{
601	return isl_pw_aff_nan_on_domain_space(space: isl_space_copy(space));
602	}
603
604	static __isl_give isl_pw_aff *accept_affine(__isl_keep isl_stream *s,
605	__isl_take isl_space *space, struct vars *v)
606	{
607	struct isl_token *tok = NULL;
608	isl_local_space *ls;
609	isl_pw_aff *res;
610	int op = 1;
611	int sign = 1;
612
613	ls = isl_local_space_from_space(space: isl_space_copy(space));
614	res = isl_pw_aff_from_aff(aff: isl_aff_zero_on_domain(ls));
615	if (!res)
616	goto error;
617
618	for (;;) {
619	tok = next_token(s);
620	if (!tok) {
621	isl_stream_error(s, NULL, msg: "unexpected EOF");
622	goto error;
623	}
624	if (tok->type == '-') {
625	sign = -sign;
626	isl_token_free(tok);
627	continue;
628	}
629	if (tok->type == '(' || is_start_of_div(tok) ||
630	tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX ||
631	tok->type == ISL_TOKEN_IDENT ||
632	tok->type == ISL_TOKEN_VALUE ||
633	tok->type == ISL_TOKEN_AFF) {
634	isl_pw_aff *term;
635	if (tok->type == ISL_TOKEN_VALUE && sign < 0) {
636	isl_int_neg(tok->u.v, tok->u.v);
637	sign = 1;
638	}
639	isl_stream_push_token(s, tok);
640	tok = NULL;
641	term = accept_affine_factor(s,
642	space: isl_space_copy(space), v);
643	if (op * sign < 0)
644	res = isl_pw_aff_sub(pwaff1: res, pwaff2: term);
645	else
646	res = isl_pw_aff_add(pwaff1: res, pwaff2: term);
647	if (!res)
648	goto error;
649	} else if (tok->type == ISL_TOKEN_NAN) {
650	res = isl_pw_aff_add(pwaff1: res, pwaff2: nan_on_domain(space));
651	} else {
652	isl_stream_error(s, tok, msg: "unexpected isl_token");
653	isl_stream_push_token(s, tok);
654	isl_pw_aff_free(pwaff: res);
655	isl_space_free(space);
656	return NULL;
657	}
658	isl_token_free(tok);
659
660	tok = next_token(s);
661	sign = 1;
662	if (tok && tok->type == '-') {
663	op = -1;
664	isl_token_free(tok);
665	} else if (tok && tok->type == '+') {
666	op = 1;
667	isl_token_free(tok);
668	} else {
669	if (tok)
670	isl_stream_push_token(s, tok);
671	break;
672	}
673	}
674
675	isl_space_free(space);
676	return res;
677	error:
678	isl_space_free(space);
679	isl_token_free(tok);
680	isl_pw_aff_free(pwaff: res);
681	return NULL;
682	}
683
684	/* Is "type" the type of a comparison operator between lists
685	* of affine expressions?
686	*/
687	static int is_list_comparator_type(int type)
688	{
689	switch (type) {
690	case ISL_TOKEN_LEX_LT:
691	case ISL_TOKEN_LEX_GT:
692	case ISL_TOKEN_LEX_LE:
693	case ISL_TOKEN_LEX_GE:
694	return 1;
695	default:
696	return 0;
697	}
698	}
699
700	static int is_comparator(struct isl_token *tok)
701	{
702	if (!tok)
703	return 0;
704	if (is_list_comparator_type(type: tok->type))
705	return 1;
706
707	switch (tok->type) {
708	case ISL_TOKEN_LT:
709	case ISL_TOKEN_GT:
710	case ISL_TOKEN_LE:
711	case ISL_TOKEN_GE:
712	case ISL_TOKEN_NE:
713	case '=':
714	return 1;
715	default:
716	return 0;
717	}
718	}
719
720	static __isl_give isl_map *read_formula(__isl_keep isl_stream *s,
721	struct vars *v, __isl_take isl_map *map, int rational);
722	static __isl_give isl_pw_aff *accept_extended_affine(__isl_keep isl_stream *s,
723	__isl_take isl_space *space, struct vars *v, int rational);
724
725	/* Accept a ternary operator, given the first argument.
726	*/
727	static __isl_give isl_pw_aff *accept_ternary(__isl_keep isl_stream *s,
728	__isl_take isl_map *cond, struct vars *v, int rational)
729	{
730	isl_space *space;
731	isl_pw_aff *pwaff1 = NULL, *pwaff2 = NULL, *pa_cond;
732
733	if (!cond)
734	return NULL;
735
736	if (isl_stream_eat(s, type: '?'))
737	goto error;
738
739	space = isl_space_wrap(space: isl_map_get_space(map: cond));
740	pwaff1 = accept_extended_affine(s, space, v, rational);
741	if (!pwaff1)
742	goto error;
743
744	if (isl_stream_eat(s, type: ':'))
745	goto error;
746
747	space = isl_pw_aff_get_domain_space(pwaff: pwaff1);
748	pwaff2 = accept_extended_affine(s, space, v, rational);
749	if (!pwaff2)
750	goto error;
751
752	pa_cond = isl_set_indicator_function(set: isl_map_wrap(map: cond));
753	return isl_pw_aff_cond(cond: pa_cond, pwaff_true: pwaff1, pwaff_false: pwaff2);
754	error:
755	isl_map_free(map: cond);
756	isl_pw_aff_free(pwaff: pwaff1);
757	isl_pw_aff_free(pwaff: pwaff2);
758	return NULL;
759	}
760
761	/* Set *line and *col to those of the next token, if any.
762	*/
763	static void set_current_line_col(__isl_keep isl_stream *s, int *line, int *col)
764	{
765	struct isl_token *tok;
766
767	tok = isl_stream_next_token(s);
768	if (!tok)
769	return;
770
771	*line = tok->line;
772	*col = tok->col;
773	isl_stream_push_token(s, tok);
774	}
775
776	/* Push a token encapsulating "pa" onto "s", with the given
777	* line and column.
778	*/
779	static isl_stat push_aff(__isl_keep isl_stream *s, int line, int col,
780	__isl_take isl_pw_aff *pa)
781	{
782	struct isl_token *tok;
783
784	tok = isl_token_new(ctx: s->ctx, line, col, on_new_line: 0);
785	if (!tok)
786	goto error;
787	tok->type = ISL_TOKEN_AFF;
788	tok->u.pwaff = pa;
789	isl_stream_push_token(s, tok);
790
791	return isl_stat_ok;
792	error:
793	isl_pw_aff_free(pwaff: pa);
794	return isl_stat_error;
795	}
796
797	/* Is the next token a comparison operator?
798	*/
799	static int next_is_comparator(__isl_keep isl_stream *s)
800	{
801	int is_comp;
802	struct isl_token *tok;
803
804	tok = isl_stream_next_token(s);
805	if (!tok)
806	return 0;
807
808	is_comp = is_comparator(tok);
809	isl_stream_push_token(s, tok);
810
811	return is_comp;
812	}
813
814	/* Accept an affine expression that may involve ternary operators.
815	* We first read an affine expression.
816	* If it is not followed by a comparison operator, we simply return it.
817	* Otherwise, we assume the affine expression is part of the first
818	* argument of a ternary operator and try to parse that.
819	*/
820	static __isl_give isl_pw_aff *accept_extended_affine(__isl_keep isl_stream *s,
821	__isl_take isl_space *space, struct vars *v, int rational)
822	{
823	isl_map *cond;
824	isl_pw_aff *pwaff;
825	int line = -1, col = -1;
826
827	set_current_line_col(s, line: &line, col: &col);
828
829	pwaff = accept_affine(s, space, v);
830	if (rational)
831	pwaff = isl_pw_aff_set_rational(pwaff);
832	if (!pwaff)
833	return NULL;
834	if (!next_is_comparator(s))
835	return pwaff;
836
837	space = isl_pw_aff_get_domain_space(pwaff);
838	cond = isl_map_universe(space: isl_space_unwrap(space));
839
840	if (push_aff(s, line, col, pa: pwaff) < 0)
841	cond = isl_map_free(map: cond);
842	if (!cond)
843	return NULL;
844
845	cond = read_formula(s, v, map: cond, rational);
846
847	return accept_ternary(s, cond, v, rational);
848	}
849
850	static __isl_give isl_map *read_var_def(__isl_keep isl_stream *s,
851	__isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
852	int rational)
853	{
854	isl_pw_aff *def;
855	isl_size pos;
856	isl_map *def_map;
857
858	if (type == isl_dim_param)
859	pos = isl_map_dim(map, type: isl_dim_param);
860	else {
861	pos = isl_map_dim(map, type: isl_dim_in);
862	if (type == isl_dim_out) {
863	isl_size n_out = isl_map_dim(map, type: isl_dim_out);
864	if (pos < 0 || n_out < 0)
865	return isl_map_free(map);
866	pos += n_out;
867	}
868	type = isl_dim_in;
869	}
870	if (pos < 0)
871	return isl_map_free(map);
872	--pos;
873
874	def = accept_extended_affine(s, space: isl_space_wrap(space: isl_map_get_space(map)),
875	v, rational);
876	def_map = isl_map_from_pw_aff(pwaff: def);
877	def_map = isl_map_equate(map: def_map, type1: type, pos1: pos, type2: isl_dim_out, pos2: 0);
878	def_map = isl_set_unwrap(set: isl_map_domain(bmap: def_map));
879
880	map = isl_map_intersect(map1: map, map2: def_map);
881
882	return map;
883	}
884
885	static __isl_give isl_pw_aff_list *accept_affine_list(__isl_keep isl_stream *s,
886	__isl_take isl_space *space, struct vars *v)
887	{
888	isl_pw_aff *pwaff;
889	isl_pw_aff_list *list;
890	struct isl_token *tok = NULL;
891
892	pwaff = accept_affine(s, space: isl_space_copy(space), v);
893	list = isl_pw_aff_list_from_pw_aff(el: pwaff);
894	if (!list)
895	goto error;
896
897	for (;;) {
898	tok = isl_stream_next_token(s);
899	if (!tok) {
900	isl_stream_error(s, NULL, msg: "unexpected EOF");
901	goto error;
902	}
903	if (tok->type != ',') {
904	isl_stream_push_token(s, tok);
905	break;
906	}
907	isl_token_free(tok);
908
909	pwaff = accept_affine(s, space: isl_space_copy(space), v);
910	list = isl_pw_aff_list_concat(list1: list,
911	list2: isl_pw_aff_list_from_pw_aff(el: pwaff));
912	if (!list)
913	goto error;
914	}
915
916	isl_space_free(space);
917	return list;
918	error:
919	isl_space_free(space);
920	isl_pw_aff_list_free(list);
921	return NULL;
922	}
923
924	static __isl_give isl_map *read_defined_var_list(__isl_keep isl_stream *s,
925	struct vars *v, __isl_take isl_map *map, int rational)
926	{
927	struct isl_token *tok;
928
929	while ((tok = isl_stream_next_token(s)) != NULL) {
930	int p;
931	int n = v->n;
932
933	if (tok->type != ISL_TOKEN_IDENT)
934	break;
935
936	p = vars_pos(v, s: tok->u.s, len: -1);
937	if (p < 0)
938	goto error;
939	if (p < n) {
940	isl_stream_error(s, tok, msg: "expecting unique identifier");
941	goto error;
942	}
943
944	map = isl_map_add_dims(map, type: isl_dim_out, n: 1);
945
946	isl_token_free(tok);
947	tok = isl_stream_next_token(s);
948	if (tok && tok->type == '=') {
949	isl_token_free(tok);
950	map = read_var_def(s, map, type: isl_dim_out, v, rational);
951	tok = isl_stream_next_token(s);
952	}
953
954	if (!tok || tok->type != ',')
955	break;
956
957	isl_token_free(tok);
958	}
959	if (tok)
960	isl_stream_push_token(s, tok);
961
962	return map;
963	error:
964	isl_token_free(tok);
965	isl_map_free(map);
966	return NULL;
967	}
968
969	static int next_is_tuple(__isl_keep isl_stream *s)
970	{
971	struct isl_token *tok;
972	int is_tuple;
973
974	tok = isl_stream_next_token(s);
975	if (!tok)
976	return 0;
977	if (tok->type == '[') {
978	isl_stream_push_token(s, tok);
979	return 1;
980	}
981	if (tok->type != ISL_TOKEN_IDENT && !tok->is_keyword) {
982	isl_stream_push_token(s, tok);
983	return 0;
984	}
985
986	is_tuple = isl_stream_next_token_is(s, type: '[');
987
988	isl_stream_push_token(s, tok);
989
990	return is_tuple;
991	}
992
993	/* Does the next token mark the end of a tuple element?
994	*/
995	static int next_is_end_tuple_element(__isl_keep isl_stream *s)
996	{
997	return isl_stream_next_token_is(s, type: ',') ||
998	isl_stream_next_token_is(s, type: ']');
999	}
1000
1001	/* Is the next token one that necessarily forms the start of a condition?
1002	*/
1003	static int next_is_condition_start(__isl_keep isl_stream *s)
1004	{
1005	return isl_stream_next_token_is(s, type: ISL_TOKEN_EXISTS) ||
1006	isl_stream_next_token_is(s, type: ISL_TOKEN_NOT) ||
1007	isl_stream_next_token_is(s, type: ISL_TOKEN_TRUE) ||
1008	isl_stream_next_token_is(s, type: ISL_TOKEN_FALSE) ||
1009	isl_stream_next_token_is(s, type: ISL_TOKEN_MAP);
1010	}
1011
1012	/* Is "pa" an expression in term of earlier dimensions?
1013	* The alternative is that the dimension is defined to be equal to itself,
1014	* meaning that it has a universe domain and an expression that depends
1015	* on itself. "i" is the position of the expression in a sequence
1016	* of "n" expressions. The final dimensions of "pa" correspond to
1017	* these "n" expressions.
1018	*/
1019	static isl_bool pw_aff_is_expr(__isl_keep isl_pw_aff *pa, int i, int n)
1020	{
1021	isl_aff *aff;
1022
1023	if (!pa)
1024	return isl_bool_error;
1025	if (pa->n != 1)
1026	return isl_bool_true;
1027	if (!isl_set_plain_is_universe(set: pa->p[0].set))
1028	return isl_bool_true;
1029
1030	aff = pa->p[0].aff;
1031	if (isl_int_is_zero(aff->v->el[aff->v->size - n + i]))
1032	return isl_bool_true;
1033	return isl_bool_false;
1034	}
1035
1036	/* Does the tuple contain any dimensions that are defined
1037	* in terms of earlier dimensions?
1038	*/
1039	static isl_bool tuple_has_expr(__isl_keep isl_multi_pw_aff *tuple)
1040	{
1041	int i;
1042	isl_size n;
1043	isl_bool has_expr = isl_bool_false;
1044	isl_pw_aff *pa;
1045
1046	n = isl_multi_pw_aff_dim(multi: tuple, type: isl_dim_out);
1047	if (n < 0)
1048	return isl_bool_error;
1049	for (i = 0; i < n; ++i) {
1050	pa = isl_multi_pw_aff_get_pw_aff(multi: tuple, pos: i);
1051	has_expr = pw_aff_is_expr(pa, i, n);
1052	isl_pw_aff_free(pwaff: pa);
1053	if (has_expr < 0 || has_expr)
1054	break;
1055	}
1056
1057	return has_expr;
1058	}
1059
1060	/* Set the name of dimension "pos" in "space" to "name".
1061	* During printing, we add primes if the same name appears more than once
1062	* to distinguish the occurrences. Here, we remove those primes from "name"
1063	* before setting the name of the dimension.
1064	*/
1065	static __isl_give isl_space *space_set_dim_name(__isl_take isl_space *space,
1066	int pos, char *name)
1067	{
1068	char *prime;
1069
1070	if (!name)
1071	return space;
1072
1073	prime = strchr(s: name, c: '\'');
1074	if (prime)
1075	*prime = '\0';
1076	space = isl_space_set_dim_name(space, type: isl_dim_out, pos, name);
1077	if (prime)
1078	*prime = '\'';
1079
1080	return space;
1081	}
1082
1083	/* Set the name of the last (output) dimension of "space" to "name",
1084	* ignoring any primes in "name".
1085	*/
1086	static __isl_give isl_space *space_set_last_dim_name(
1087	__isl_take isl_space *space, char *name)
1088	{
1089	isl_size pos;
1090
1091	pos = isl_space_dim(space, type: isl_dim_out);
1092	if (pos < 0)
1093	return isl_space_free(space);
1094	return space_set_dim_name(space, pos: pos - 1, name);
1095	}
1096
1097	/* Construct an isl_pw_aff defined on a "space" (with v->n variables)
1098	* that is equal to the last of those variables.
1099	*/
1100	static __isl_give isl_pw_aff *identity_tuple_el_on_space(
1101	__isl_take isl_space *space, struct vars *v)
1102	{
1103	isl_aff *aff;
1104
1105	aff = isl_aff_zero_on_domain(ls: isl_local_space_from_space(space));
1106	aff = isl_aff_add_coefficient_si(aff, type: isl_dim_in, pos: v->n - 1, v: 1);
1107	return isl_pw_aff_from_aff(aff);
1108	}
1109
1110	/* Construct an isl_pw_aff defined on the domain space of "pa"
1111	* that is equal to the last variable in "v".
1112	*
1113	* That is, if D is the domain space of "pa", then construct
1114	*
1115	* D[..., i] -> i.
1116	*/
1117	static __isl_give isl_pw_aff *init_range(__isl_keep isl_pw_aff *pa,
1118	struct vars *v)
1119	{
1120	isl_space *space;
1121
1122	space = isl_pw_aff_get_domain_space(pwaff: pa);
1123	return identity_tuple_el_on_space(space, v);
1124	}
1125
1126	/* Impose the lower bound "lower" on the variable represented by "range_pa".
1127	*
1128	* In particular, "range_pa" is of the form
1129	*
1130	* D[..., i] -> i : C
1131	*
1132	* with D also the domains space of "lower' and "C" some constraints.
1133	*
1134	* Return the expression
1135	*
1136	* D[..., i] -> i : C and i >= lower
1137	*/
1138	static __isl_give isl_pw_aff *set_lower(__isl_take isl_pw_aff *range_pa,
1139	__isl_take isl_pw_aff *lower)
1140	{
1141	isl_set *range;
1142
1143	range = isl_pw_aff_ge_set(pwaff1: isl_pw_aff_copy(pwaff: range_pa), pwaff2: lower);
1144	return isl_pw_aff_intersect_domain(pa: range_pa, set: range);
1145	}
1146
1147	/* Impose the upper bound "upper" on the variable represented by "range_pa".
1148	*
1149	* In particular, "range_pa" is of the form
1150	*
1151	* D[..., i] -> i : C
1152	*
1153	* with D also the domains space of "upper' and "C" some constraints.
1154	*
1155	* Return the expression
1156	*
1157	* D[..., i] -> i : C and i <= upper
1158	*/
1159	static __isl_give isl_pw_aff *set_upper(__isl_take isl_pw_aff *range_pa,
1160	__isl_take isl_pw_aff *upper)
1161	{
1162	isl_set *range;
1163
1164	range = isl_pw_aff_le_set(pwaff1: isl_pw_aff_copy(pwaff: range_pa), pwaff2: upper);
1165	return isl_pw_aff_intersect_domain(pa: range_pa, set: range);
1166	}
1167
1168	/* Construct a piecewise affine expression corresponding
1169	* to the last variable in "v" that is greater than or equal to "pa".
1170	*
1171	* In particular, if D is the domain space of "pa",
1172	* then construct the expression
1173	*
1174	* D[..., i] -> i,
1175	*
1176	* impose lower bound "pa" and return
1177	*
1178	* D[..., i] -> i : i >= pa
1179	*/
1180	static __isl_give isl_pw_aff *construct_lower(__isl_take isl_pw_aff *pa,
1181	struct vars *v)
1182	{
1183	return set_lower(range_pa: init_range(pa, v), lower: pa);
1184	}
1185
1186	/* Construct a piecewise affine expression corresponding
1187	* to the last variable in "v" that is smaller than or equal to "pa".
1188	*
1189	* In particular, if D is the domain space of "pa",
1190	* then construct the expression
1191	*
1192	* D[..., i] -> i,
1193	*
1194	* impose lower bound "pa" and return
1195	*
1196	* D[..., i] -> i : i <= pa
1197	*/
1198	static __isl_give isl_pw_aff *construct_upper(__isl_take isl_pw_aff *pa,
1199	struct vars *v)
1200	{
1201	return set_upper(range_pa: init_range(pa, v), upper: pa);
1202	}
1203
1204	/* Construct a piecewise affine expression corresponding
1205	* to the last variable in "v" that ranges between "pa" and "pa2".
1206	*
1207	* In particular, if D is the domain space of "pa" (and "pa2"),
1208	* then construct the expression
1209	*
1210	* D[..., i] -> i,
1211	*
1212	* impose lower bound "pa" and upper bound "pa2" and return
1213	*
1214	* D[..., i] -> i : pa <= i <= pa2
1215	*/
1216	static __isl_give isl_pw_aff *construct_range(__isl_take isl_pw_aff *pa,
1217	__isl_take isl_pw_aff *pa2, struct vars *v)
1218	{
1219	return set_upper(range_pa: set_lower(range_pa: init_range(pa, v), lower: pa), upper: pa2);
1220	}
1221
1222	static int resolve_paren_expr(__isl_keep isl_stream *s,
1223	struct vars *v, __isl_take isl_map *map, int rational);
1224
1225	/* Given that the (piecewise) affine expression "pa"
1226	* has just been parsed, followed by a colon,
1227	* continue parsing as part of a piecewise affine expression.
1228	*
1229	* In particular, check if the colon is followed by a condition.
1230	* If so, parse the conditions(a) on "pa" and include them in the domain.
1231	* Otherwise, if the colon is followed by another (piecewise) affine expression
1232	* then consider the two expressions as endpoints of a range of values and
1233	* return a piecewise affine expression that takes values in that range.
1234	* Note that an affine expression followed by a comparison operator
1235	* is considered to be part of a condition.
1236	* If the colon is not followed by anything (inside the tuple element),
1237	* then consider "pa" as a lower bound on a range of values without upper bound
1238	* and return a piecewise affine expression that takes values in that range.
1239	*/
1240	static __isl_give isl_pw_aff *update_piecewise_affine_colon(
1241	__isl_take isl_pw_aff *pa, __isl_keep isl_stream *s,
1242	struct vars *v, int rational)
1243	{
1244	isl_space *dom_space;
1245	isl_map *map;
1246
1247	dom_space = isl_pw_aff_get_domain_space(pwaff: pa);
1248	map = isl_map_universe(space: isl_space_from_domain(space: dom_space));
1249
1250	if (isl_stream_next_token_is(s, type: '('))
1251	if (resolve_paren_expr(s, v, map: isl_map_copy(map), rational))
1252	goto error;
1253	if (next_is_end_tuple_element(s)) {
1254	isl_map_free(map);
1255	return construct_lower(pa, v);
1256	}
1257	if (!next_is_condition_start(s)) {
1258	int line = -1, col = -1;
1259	isl_space *space;
1260	isl_pw_aff *pa2;
1261
1262	set_current_line_col(s, line: &line, col: &col);
1263	space = isl_space_wrap(space: isl_map_get_space(map));
1264	pa2 = accept_affine(s, space, v);
1265	if (rational)
1266	pa2 = isl_pw_aff_set_rational(pwaff: pa2);
1267	if (!next_is_comparator(s)) {
1268	isl_map_free(map);
1269	pa2 = isl_pw_aff_domain_factor_domain(pa: pa2);
1270	return construct_range(pa, pa2, v);
1271	}
1272	if (push_aff(s, line, col, pa: pa2) < 0)
1273	goto error;
1274	}
1275
1276	map = read_formula(s, v, map, rational);
1277	pa = isl_pw_aff_intersect_domain(pa, set: isl_map_domain(bmap: map));
1278
1279	return pa;
1280	error:
1281	isl_map_free(map);
1282	isl_pw_aff_free(pwaff: pa);
1283	return NULL;
1284	}
1285
1286	/* Accept a piecewise affine expression.
1287	*
1288	* At the outer level, the piecewise affine expression may be of the form
1289	*
1290	* aff1 : condition1; aff2 : conditions2; ...
1291	*
1292	* or one of
1293	*
1294	* aff :
1295	* aff1 : aff2
1296	* : aff
1297	* :
1298	*
1299	* or simply
1300	*
1301	* aff
1302	*
1303	* each of the affine expressions may in turn include ternary operators.
1304	*
1305	* If the first token is a colon, then the expression must be
1306	* ":" or ": aff2", depending on whether anything follows the colon
1307	* inside the tuple element.
1308	* The first is considered to represent an arbitrary value.
1309	* The second is considered to represent a range of values
1310	* with the given upper bound and no lower bound.
1311	*
1312	* There may be parentheses around some subexpression of "aff1"
1313	* around "aff1" itself, around "aff1 : condition1" and/or
1314	* around the entire piecewise affine expression.
1315	* We therefore remove the opening parenthesis (if any) from the stream
1316	* in case the closing parenthesis follows the colon, but if the closing
1317	* parenthesis is the first thing in the stream after the parsed affine
1318	* expression, we push the parsed expression onto the stream and parse
1319	* again in case the parentheses enclose some subexpression of "aff1".
1320	*/
1321	static __isl_give isl_pw_aff *accept_piecewise_affine(__isl_keep isl_stream *s,
1322	__isl_take isl_space *space, struct vars *v, int rational)
1323	{
1324	isl_pw_aff *res;
1325	isl_space *res_space;
1326
1327	if (isl_stream_eat_if_available(s, type: ':')) {
1328	if (next_is_end_tuple_element(s))
1329	return identity_tuple_el_on_space(space, v);
1330	else
1331	return construct_upper(pa: accept_affine(s, space, v), v);
1332	}
1333
1334	res_space = isl_space_from_domain(space: isl_space_copy(space));
1335	res_space = isl_space_add_dims(space: res_space, type: isl_dim_out, n: 1);
1336	res = isl_pw_aff_empty(space: res_space);
1337	do {
1338	isl_pw_aff *pa;
1339	int seen_paren;
1340	int line = -1, col = -1;
1341
1342	set_current_line_col(s, line: &line, col: &col);
1343	seen_paren = isl_stream_eat_if_available(s, type: '(');
1344	if (seen_paren)
1345	pa = accept_piecewise_affine(s, space: isl_space_copy(space),
1346	v, rational);
1347	else
1348	pa = accept_extended_affine(s, space: isl_space_copy(space),
1349	v, rational);
1350	if (seen_paren && isl_stream_eat_if_available(s, type: ')')) {
1351	seen_paren = 0;
1352	if (push_aff(s, line, col, pa) < 0)
1353	goto error;
1354	pa = accept_extended_affine(s, space: isl_space_copy(space),
1355	v, rational);
1356	}
1357	if (pa && isl_stream_eat_if_available(s, type: ':'))
1358	pa = update_piecewise_affine_colon(pa, s, v, rational);
1359
1360	res = isl_pw_aff_union_add(pwaff1: res, pwaff2: pa);
1361
1362	if (!res || (seen_paren && isl_stream_eat(s, type: ')')))
1363	goto error;
1364	} while (isl_stream_eat_if_available(s, type: ';'));
1365
1366	isl_space_free(space);
1367
1368	return res;
1369	error:
1370	isl_space_free(space);
1371	return isl_pw_aff_free(pwaff: res);
1372	}
1373
1374	/* Read an affine expression from "s" for use in read_tuple.
1375	*
1376	* accept_extended_affine requires a wrapped space as input.
1377	* read_tuple on the other hand expects each isl_pw_aff
1378	* to have an anonymous space. We therefore adjust the space
1379	* of the isl_pw_aff before returning it.
1380	*/
1381	static __isl_give isl_pw_aff *read_tuple_var_def(__isl_keep isl_stream *s,
1382	struct vars *v, int rational)
1383	{
1384	isl_space *space;
1385	isl_pw_aff *def;
1386
1387	space = isl_space_wrap(space: isl_space_alloc(ctx: s->ctx, nparam: 0, n_in: v->n, n_out: 0));
1388
1389	def = accept_piecewise_affine(s, space, v, rational);
1390	def = isl_pw_aff_domain_factor_domain(pa: def);
1391
1392	return def;
1393	}
1394
1395	/* Read a list of tuple elements by calling "read_el" on each of them and
1396	* return a space with the same number of set dimensions derived from
1397	* the parameter space "space" and possibly updated by "read_el".
1398	* The elements in the list are separated by either "," or "][".
1399	* If "comma" is set then only "," is allowed.
1400	*/
1401	static __isl_give isl_space *read_tuple_list(__isl_keep isl_stream *s,
1402	struct vars *v, __isl_take isl_space *space, int rational, int comma,
1403	__isl_give isl_space *(*read_el)(__isl_keep isl_stream *s,
1404	struct vars *v, __isl_take isl_space *space, int rational,
1405	void *user),
1406	void *user)
1407	{
1408	if (!space)
1409	return NULL;
1410
1411	space = isl_space_set_from_params(space);
1412
1413	if (isl_stream_next_token_is(s, type: ']'))
1414	return space;
1415
1416	for (;;) {
1417	struct isl_token *tok;
1418
1419	space = isl_space_add_dims(space, type: isl_dim_set, n: 1);
1420
1421	space = read_el(s, v, space, rational, user);
1422	if (!space)
1423	return NULL;
1424
1425	tok = isl_stream_next_token(s);
1426	if (!comma && tok && tok->type == ']' &&
1427	isl_stream_next_token_is(s, type: '[')) {
1428	isl_token_free(tok);
1429	tok = isl_stream_next_token(s);
1430	} else if (!tok || tok->type != ',') {
1431	if (tok)
1432	isl_stream_push_token(s, tok);
1433	break;
1434	}
1435
1436	isl_token_free(tok);
1437	}
1438
1439	return space;
1440	}
1441
1442	/* Read a tuple space from "s" derived from the parameter space "space".
1443	* Call "read_el" on each element in the tuples.
1444	*/
1445	static __isl_give isl_space *read_tuple_space(__isl_keep isl_stream *s,
1446	struct vars *v, __isl_take isl_space *space, int rational, int comma,
1447	__isl_give isl_space *(*read_el)(__isl_keep isl_stream *s,
1448	struct vars *v, __isl_take isl_space *space, int rational,
1449	void *user),
1450	void *user)
1451	{
1452	struct isl_token *tok;
1453	char *name = NULL;
1454	isl_space *res = NULL;
1455
1456	tok = isl_stream_next_token(s);
1457	if (!tok)
1458	goto error;
1459	if (tok->type == ISL_TOKEN_IDENT || tok->is_keyword) {
1460	name = strdup(s: tok->u.s);
1461	isl_token_free(tok);
1462	if (!name)
1463	goto error;
1464	} else
1465	isl_stream_push_token(s, tok);
1466	if (isl_stream_eat(s, type: '['))
1467	goto error;
1468	if (next_is_tuple(s)) {
1469	isl_space *out;
1470	res = read_tuple_space(s, v, space: isl_space_copy(space),
1471	rational, comma, read_el, user);
1472	if (isl_stream_eat(s, type: ISL_TOKEN_TO))
1473	goto error;
1474	out = read_tuple_space(s, v, space: isl_space_copy(space),
1475	rational, comma, read_el, user);
1476	res = isl_space_product(left: res, right: out);
1477	} else
1478	res = read_tuple_list(s, v, space: isl_space_copy(space),
1479	rational, comma, read_el, user);
1480	if (!res || isl_stream_eat(s, type: ']'))
1481	goto error;
1482
1483	if (name) {
1484	res = isl_space_set_tuple_name(space: res, type: isl_dim_set, s: name);
1485	free(ptr: name);
1486	}
1487
1488	isl_space_free(space);
1489	return res;
1490	error:
1491	free(ptr: name);
1492	isl_space_free(space: res);
1493	isl_space_free(space);
1494	return NULL;
1495	}
1496
1497	/* Construct an isl_pw_aff defined on a space with v->n variables
1498	* that is equal to the last of those variables.
1499	*/
1500	static __isl_give isl_pw_aff *identity_tuple_el(struct vars *v)
1501	{
1502	isl_space *space;
1503
1504	space = isl_space_set_alloc(ctx: v->ctx, nparam: 0, dim: v->n);
1505	return identity_tuple_el_on_space(space, v);
1506	}
1507
1508	/* This function is called for each element in a tuple inside read_tuple.
1509	* Add a new variable to "v" and construct a corresponding isl_pw_aff defined
1510	* over a space containing all variables in "v" defined so far.
1511	* The isl_pw_aff expresses the new variable in terms of earlier variables
1512	* if a definition is provided. Otherwise, it is represented as being
1513	* equal to itself.
1514	* Add the isl_pw_aff to *list.
1515	* If the new variable was named, then adjust "space" accordingly and
1516	* return the updated space.
1517	*/
1518	static __isl_give isl_space *read_tuple_pw_aff_el(__isl_keep isl_stream *s,
1519	struct vars *v, __isl_take isl_space *space, int rational, void *user)
1520	{
1521	isl_pw_aff_list **list = (isl_pw_aff_list **) user;
1522	isl_pw_aff *pa;
1523	struct isl_token *tok;
1524	int new_name = 0;
1525
1526	tok = next_token(s);
1527	if (!tok) {
1528	isl_stream_error(s, NULL, msg: "unexpected EOF");
1529	return isl_space_free(space);
1530	}
1531
1532	if (tok->type == ISL_TOKEN_IDENT) {
1533	int n = v->n;
1534	int p = vars_pos(v, s: tok->u.s, len: -1);
1535	if (p < 0)
1536	goto error;
1537	new_name = p >= n;
1538	}
1539
1540	if (tok->type == '*') {
1541	if (vars_add_anon(v) < 0)
1542	goto error;
1543	isl_token_free(tok);
1544	pa = identity_tuple_el(v);
1545	} else if (new_name) {
1546	space = space_set_last_dim_name(space, name: v->v->name);
1547	isl_token_free(tok);
1548	if (isl_stream_eat_if_available(s, type: '='))
1549	pa = read_tuple_var_def(s, v, rational);
1550	else
1551	pa = identity_tuple_el(v);
1552	} else {
1553	isl_stream_push_token(s, tok);
1554	tok = NULL;
1555	if (vars_add_anon(v) < 0)
1556	goto error;
1557	pa = read_tuple_var_def(s, v, rational);
1558	}
1559
1560	*list = isl_pw_aff_list_add(list: *list, el: pa);
1561	if (!*list)
1562	return isl_space_free(space);
1563
1564	return space;
1565	error:
1566	isl_token_free(tok);
1567	return isl_space_free(space);
1568	}
1569
1570	/* Read a tuple and represent it as an isl_multi_pw_aff.
1571	* The range space of the isl_multi_pw_aff is the space of the tuple.
1572	* The domain space is an anonymous space
1573	* with a dimension for each variable in the set of variables in "v",
1574	* including the variables in the range.
1575	* If a given dimension is not defined in terms of earlier dimensions in
1576	* the input, then the corresponding isl_pw_aff is set equal to one time
1577	* the variable corresponding to the dimension being defined.
1578	*
1579	* The elements in the tuple are collected in a list by read_tuple_pw_aff_el.
1580	* Each element in this list is defined over a space representing
1581	* the variables defined so far. We need to adjust the earlier
1582	* elements to have as many variables in the domain as the final
1583	* element in the list.
1584	*/
1585	static __isl_give isl_multi_pw_aff *read_tuple(__isl_keep isl_stream *s,
1586	struct vars *v, int rational, int comma)
1587	{
1588	int i;
1589	isl_size n;
1590	isl_space *space;
1591	isl_pw_aff_list *list;
1592
1593	space = isl_space_params_alloc(ctx: v->ctx, nparam: 0);
1594	list = isl_pw_aff_list_alloc(ctx: s->ctx, n: 0);
1595	space = read_tuple_space(s, v, space, rational, comma,
1596	read_el: &read_tuple_pw_aff_el, user: &list);
1597	n = isl_space_dim(space, type: isl_dim_set);
1598	if (n < 0)
1599	space = isl_space_free(space);
1600	for (i = 0; i + 1 < n; ++i) {
1601	isl_pw_aff *pa;
1602
1603	pa = isl_pw_aff_list_get_pw_aff(list, index: i);
1604	pa = isl_pw_aff_add_dims(pwaff: pa, type: isl_dim_in, n: n - (i + 1));
1605	list = isl_pw_aff_list_set_pw_aff(list, index: i, el: pa);
1606	}
1607
1608	space = isl_space_from_range(space);
1609	space = isl_space_add_dims(space, type: isl_dim_in, n: v->n);
1610	return isl_multi_pw_aff_from_pw_aff_list(space, list);
1611	}
1612
1613	/* Add the tuple represented by the isl_multi_pw_aff "tuple" to "map".
1614	* We first create the appropriate space in "map" based on the range
1615	* space of this isl_multi_pw_aff. Then, we add equalities based
1616	* on the affine expressions. These live in an anonymous space,
1617	* however, so we first need to reset the space to that of "map".
1618	*/
1619	static __isl_give isl_map *map_from_tuple(__isl_take isl_multi_pw_aff *tuple,
1620	__isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
1621	int rational)
1622	{
1623	int i;
1624	isl_size n;
1625	isl_ctx *ctx;
1626	isl_space *space = NULL;
1627
1628	n = isl_multi_pw_aff_dim(multi: tuple, type: isl_dim_out);
1629	if (!map || n < 0)
1630	goto error;
1631	ctx = isl_multi_pw_aff_get_ctx(multi: tuple);
1632	space = isl_space_range(space: isl_multi_pw_aff_get_space(multi: tuple));
1633	if (!space)
1634	goto error;
1635
1636	if (type == isl_dim_param) {
1637	if (isl_space_has_tuple_name(space, type: isl_dim_set) ||
1638	isl_space_is_wrapping(space)) {
1639	isl_die(ctx, isl_error_invalid,
1640	"parameter tuples cannot be named or nested",
1641	goto error);
1642	}
1643	map = isl_map_add_dims(map, type, n);
1644	for (i = 0; i < n; ++i) {
1645	isl_id *id;
1646	if (!isl_space_has_dim_name(space, type: isl_dim_set, pos: i))
1647	isl_die(ctx, isl_error_invalid,
1648	"parameters must be named",
1649	goto error);
1650	id = isl_space_get_dim_id(space, type: isl_dim_set, pos: i);
1651	map = isl_map_set_dim_id(map, type: isl_dim_param, pos: i, id);
1652	}
1653	} else if (type == isl_dim_in) {
1654	isl_set *set;
1655
1656	set = isl_set_universe(space: isl_space_copy(space));
1657	if (rational)
1658	set = isl_set_set_rational(set);
1659	set = isl_set_intersect_params(set, params: isl_map_params(map));
1660	map = isl_map_from_domain(set);
1661	} else {
1662	isl_set *set;
1663
1664	set = isl_set_universe(space: isl_space_copy(space));
1665	if (rational)
1666	set = isl_set_set_rational(set);
1667	map = isl_map_from_domain_and_range(domain: isl_map_domain(bmap: map), range: set);
1668	}
1669
1670	for (i = 0; i < n; ++i) {
1671	isl_pw_aff *pa;
1672	isl_space *space;
1673	isl_aff *aff;
1674	isl_set *set;
1675	isl_map *map_i;
1676
1677	pa = isl_multi_pw_aff_get_pw_aff(multi: tuple, pos: i);
1678	space = isl_pw_aff_get_domain_space(pwaff: pa);
1679	aff = isl_aff_zero_on_domain(ls: isl_local_space_from_space(space));
1680	aff = isl_aff_add_coefficient_si(aff,
1681	type: isl_dim_in, pos: v->n - n + i, v: -1);
1682	pa = isl_pw_aff_add(pwaff1: pa, pwaff2: isl_pw_aff_from_aff(aff));
1683	if (rational)
1684	pa = isl_pw_aff_set_rational(pwaff: pa);
1685	set = isl_pw_aff_zero_set(pwaff: pa);
1686	map_i = isl_map_from_range(set);
1687	map_i = isl_map_reset_space(map: map_i, space: isl_map_get_space(map));
1688	map = isl_map_intersect(map1: map, map2: map_i);
1689	}
1690
1691	isl_space_free(space);
1692	isl_multi_pw_aff_free(multi: tuple);
1693	return map;
1694	error:
1695	isl_space_free(space);
1696	isl_multi_pw_aff_free(multi: tuple);
1697	isl_map_free(map);
1698	return NULL;
1699	}
1700
1701	/* Read a tuple from "s" and add it to "map".
1702	* The tuple is initially represented as an isl_multi_pw_aff and
1703	* then added to "map".
1704	*/
1705	static __isl_give isl_map *read_map_tuple(__isl_keep isl_stream *s,
1706	__isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
1707	int rational, int comma)
1708	{
1709	isl_multi_pw_aff *tuple;
1710
1711	tuple = read_tuple(s, v, rational, comma);
1712	if (!tuple)
1713	return isl_map_free(map);
1714
1715	return map_from_tuple(tuple, map, type, v, rational);
1716	}
1717
1718	/* Read the parameter domain of an expression from "s" (if any) and
1719	* check that it does not involve any constraints.
1720	* "v" contains a description of the identifiers parsed so far
1721	* (of which there should not be any at this point) and is extended
1722	* by this function.
1723	*/
1724	static __isl_give isl_set *read_universe_params(__isl_keep isl_stream *s,
1725	struct vars *v)
1726	{
1727	isl_set *dom;
1728
1729	dom = isl_set_universe(space: isl_space_params_alloc(ctx: s->ctx, nparam: 0));
1730	if (next_is_tuple(s)) {
1731	dom = read_map_tuple(s, map: dom, type: isl_dim_param, v, rational: 1, comma: 0);
1732	if (isl_stream_eat(s, type: ISL_TOKEN_TO))
1733	return isl_set_free(set: dom);
1734	}
1735	if (!isl_set_plain_is_universe(set: dom))
1736	isl_die(s->ctx, isl_error_invalid,
1737	"expecting universe parameter domain",
1738	return isl_set_free(dom));
1739
1740	return dom;
1741	}
1742
1743	/* Read the parameter domain of an expression from "s" (if any),
1744	* check that it does not involve any constraints and return its space.
1745	* "v" contains a description of the identifiers parsed so far
1746	* (of which there should not be any at this point) and is extended
1747	* by this function.
1748	*/
1749	static __isl_give isl_space *read_params(__isl_keep isl_stream *s,
1750	struct vars *v)
1751	{
1752	isl_space *space;
1753	isl_set *set;
1754
1755	set = read_universe_params(s, v);
1756	space = isl_set_get_space(set);
1757	isl_set_free(set);
1758
1759	return space;
1760	}
1761
1762	/* This function is called for each element in a tuple inside read_space_tuples.
1763	* Add a new variable to "v" and adjust "space" accordingly
1764	* if the variable has a name.
1765	*/
1766	static __isl_give isl_space *read_tuple_id(__isl_keep isl_stream *s,
1767	struct vars *v, __isl_take isl_space *space, int rational, void *user)
1768	{
1769	struct isl_token *tok;
1770
1771	tok = next_token(s);
1772	if (!tok) {
1773	isl_stream_error(s, NULL, msg: "unexpected EOF");
1774	return isl_space_free(space);
1775	}
1776
1777	if (tok->type == ISL_TOKEN_IDENT) {
1778	int n = v->n;
1779	int p = vars_pos(v, s: tok->u.s, len: -1);
1780	if (p < 0)
1781	goto error;
1782	if (p < n) {
1783	isl_stream_error(s, tok, msg: "expecting fresh identifier");
1784	goto error;
1785	}
1786	space = space_set_last_dim_name(space, name: v->v->name);
1787	} else if (tok->type == '*') {
1788	if (vars_add_anon(v) < 0)
1789	goto error;
1790	} else {
1791	isl_stream_error(s, tok, msg: "expecting identifier or '*'");
1792	goto error;
1793	}
1794
1795	isl_token_free(tok);
1796	return space;
1797	error:
1798	isl_token_free(tok);
1799	return isl_space_free(space);
1800	}
1801
1802	/* Given a parameter space "params", extend it with one or two tuples
1803	* read from "s".
1804	* "v" contains a description of the identifiers parsed so far and is extended
1805	* by this function.
1806	*/
1807	static __isl_give isl_space *read_space_tuples(__isl_keep isl_stream *s,
1808	struct vars *v, __isl_take isl_space *params)
1809	{
1810	isl_space *space, *ran;
1811
1812	space = read_tuple_space(s, v, space: isl_space_copy(space: params), rational: 1, comma: 1,
1813	read_el: &read_tuple_id, NULL);
1814	if (isl_stream_eat_if_available(s, type: ISL_TOKEN_TO)) {
1815	ran = read_tuple_space(s, v, space: isl_space_copy(space: params), rational: 1, comma: 1,
1816	read_el: &read_tuple_id, NULL);
1817	space = isl_space_unwrap(space: isl_space_product(left: space, right: ran));
1818	}
1819	isl_space_free(space: params);
1820
1821	return space;
1822	}
1823
1824	/* Read an isl_space object from "s".
1825	*
1826	* First read the parameters (if any).
1827	*
1828	* Then check if the description is of the special form "{ : }",
1829	* in which case it represents a parameter space.
1830	* Otherwise, it has one or two tuples.
1831	*/
1832	__isl_give isl_space *isl_stream_read_space(__isl_keep isl_stream *s)
1833	{
1834	struct vars *v;
1835	isl_space *space;
1836
1837	v = vars_new(ctx: s->ctx);
1838	if (!v)
1839	return NULL;
1840	space = read_params(s, v);
1841
1842	if (isl_stream_eat(s, type: '{'))
1843	goto error;
1844
1845	if (!isl_stream_eat_if_available(s, type: ':'))
1846	space = read_space_tuples(s, v, params: space);
1847
1848	if (isl_stream_eat(s, type: '}'))
1849	goto error;
1850
1851	vars_free(v);
1852	return space;
1853	error:
1854	vars_free(v);
1855	isl_space_free(space);
1856	return NULL;
1857	}
1858
1859	#undef TYPE_BASE
1860	#define TYPE_BASE space
1861	#include "isl_read_from_str_templ.c"
1862
1863	/* Given two equal-length lists of piecewise affine expression with the space
1864	* of "set" as domain, construct a set in the same space that expresses
1865	* that "left" and "right" satisfy the comparison "type".
1866	*
1867	* A space is constructed of the same dimension as the number of elements
1868	* in the two lists. The comparison is then expressed in a map from
1869	* this space to itself and wrapped into a set. Finally the two lists
1870	* of piecewise affine expressions are plugged into this set.
1871	*
1872	* Let S be the space of "set" and T the constructed space.
1873	* The lists are first changed into two isl_multi_pw_affs in S -> T and
1874	* then combined into an isl_multi_pw_aff in S -> [T -> T],
1875	* while the comparison is first expressed in T -> T, then [T -> T]
1876	* and finally in S.
1877	*/
1878	static __isl_give isl_set *list_cmp(__isl_keep isl_set *set, int type,
1879	__isl_take isl_pw_aff_list *left, __isl_take isl_pw_aff_list *right)
1880	{
1881	isl_space *space;
1882	isl_size n;
1883	isl_multi_pw_aff *mpa1, *mpa2;
1884
1885	n = isl_pw_aff_list_n_pw_aff(list: left);
1886	if (!set || n < 0 || !right)
1887	goto error;
1888
1889	space = isl_set_get_space(set);
1890	space = isl_space_from_domain(space);
1891	space = isl_space_add_dims(space, type: isl_dim_out, n);
1892	mpa1 = isl_multi_pw_aff_from_pw_aff_list(space: isl_space_copy(space), list: left);
1893	mpa2 = isl_multi_pw_aff_from_pw_aff_list(space: isl_space_copy(space), list: right);
1894	mpa1 = isl_multi_pw_aff_range_product(multi1: mpa1, multi2: mpa2);
1895
1896	space = isl_space_range(space);
1897	switch (type) {
1898	case ISL_TOKEN_LEX_LT:
1899	set = isl_map_wrap(map: isl_map_lex_lt(set_space: space));
1900	break;
1901	case ISL_TOKEN_LEX_GT:
1902	set = isl_map_wrap(map: isl_map_lex_gt(set_space: space));
1903	break;
1904	case ISL_TOKEN_LEX_LE:
1905	set = isl_map_wrap(map: isl_map_lex_le(set_space: space));
1906	break;
1907	case ISL_TOKEN_LEX_GE:
1908	set = isl_map_wrap(map: isl_map_lex_ge(set_space: space));
1909	break;
1910	default:
1911	isl_multi_pw_aff_free(multi: mpa1);
1912	isl_space_free(space);
1913	isl_die(isl_set_get_ctx(set), isl_error_internal,
1914	"unhandled list comparison type", return NULL);
1915	}
1916	set = isl_set_preimage_multi_pw_aff(set, mpa: mpa1);
1917	return set;
1918	error:
1919	isl_pw_aff_list_free(list: left);
1920	isl_pw_aff_list_free(list: right);
1921	return NULL;
1922	}
1923
1924	/* Construct constraints of the form
1925	*
1926	* a op b
1927	*
1928	* where a is an element in "left", op is an operator of type "type" and
1929	* b is an element in "right", add the constraints to "set" and return
1930	* the result.
1931	* "rational" is set if the constraints should be treated as
1932	* a rational constraints.
1933	*
1934	* If "type" is the type of a comparison operator between lists
1935	* of affine expressions, then a single (compound) constraint
1936	* is constructed by list_cmp instead.
1937	*/
1938	static __isl_give isl_set *construct_constraints(
1939	__isl_take isl_set *set, int type,
1940	__isl_keep isl_pw_aff_list *left, __isl_keep isl_pw_aff_list *right,
1941	int rational)
1942	{
1943	isl_set *cond;
1944
1945	left = isl_pw_aff_list_copy(list: left);
1946	right = isl_pw_aff_list_copy(list: right);
1947	if (rational) {
1948	left = isl_pw_aff_list_set_rational(list: left);
1949	right = isl_pw_aff_list_set_rational(list: right);
1950	}
1951	if (is_list_comparator_type(type))
1952	cond = list_cmp(set, type, left, right);
1953	else if (type == ISL_TOKEN_LE)
1954	cond = isl_pw_aff_list_le_set(list1: left, list2: right);
1955	else if (type == ISL_TOKEN_GE)
1956	cond = isl_pw_aff_list_ge_set(list1: left, list2: right);
1957	else if (type == ISL_TOKEN_LT)
1958	cond = isl_pw_aff_list_lt_set(list1: left, list2: right);
1959	else if (type == ISL_TOKEN_GT)
1960	cond = isl_pw_aff_list_gt_set(list1: left, list2: right);
1961	else if (type == ISL_TOKEN_NE)
1962	cond = isl_pw_aff_list_ne_set(list1: left, list2: right);
1963	else
1964	cond = isl_pw_aff_list_eq_set(list1: left, list2: right);
1965
1966	return isl_set_intersect(set1: set, set2: cond);
1967	}
1968
1969	/* Read a constraint from "s", add it to "map" and return the result.
1970	* "v" contains a description of the identifiers parsed so far.
1971	* "rational" is set if the constraint should be treated as
1972	* a rational constraint.
1973	* The constraint read from "s" may be applied to multiple pairs
1974	* of affine expressions and may be chained.
1975	* In particular, a list of affine expressions is read, followed
1976	* by a comparison operator and another list of affine expressions.
1977	* The comparison operator is then applied to each pair of elements
1978	* in the two lists and the results are added to "map".
1979	* However, if the operator expects two lists of affine expressions,
1980	* then it is applied directly to those lists and the two lists
1981	* are required to have the same length.
1982	* If the next token is another comparison operator, then another
1983	* list of affine expressions is read and the process repeats.
1984	*
1985	* The processing is performed on a wrapped copy of "map" because
1986	* an affine expression cannot have a binary relation as domain.
1987	*/
1988	static __isl_give isl_map *add_constraint(__isl_keep isl_stream *s,
1989	struct vars *v, __isl_take isl_map *map, int rational)
1990	{
1991	struct isl_token *tok;
1992	int type;
1993	isl_pw_aff_list *list1 = NULL, *list2 = NULL;
1994	isl_size n1, n2;
1995	isl_set *set;
1996
1997	set = isl_map_wrap(map);
1998	list1 = accept_affine_list(s, space: isl_set_get_space(set), v);
1999	if (!list1)
2000	goto error;
2001	tok = isl_stream_next_token(s);
2002	if (!is_comparator(tok)) {
2003	isl_stream_error(s, tok, msg: "missing operator");
2004	if (tok)
2005	isl_stream_push_token(s, tok);
2006	goto error;
2007	}
2008	type = tok->type;
2009	isl_token_free(tok);
2010	for (;;) {
2011	list2 = accept_affine_list(s, space: isl_set_get_space(set), v);
2012	n1 = isl_pw_aff_list_n_pw_aff(list: list1);
2013	n2 = isl_pw_aff_list_n_pw_aff(list: list2);
2014	if (n1 < 0 || n2 < 0)
2015	goto error;
2016	if (is_list_comparator_type(type) && n1 != n2) {
2017	isl_stream_error(s, NULL,
2018	msg: "list arguments not of same size");
2019	goto error;
2020	}
2021
2022	set = construct_constraints(set, type, left: list1, right: list2, rational);
2023	isl_pw_aff_list_free(list: list1);
2024	list1 = list2;
2025
2026	if (!next_is_comparator(s))
2027	break;
2028	tok = isl_stream_next_token(s);
2029	type = tok->type;
2030	isl_token_free(tok);
2031	}
2032	isl_pw_aff_list_free(list: list1);
2033
2034	return isl_set_unwrap(set);
2035	error:
2036	isl_pw_aff_list_free(list: list1);
2037	isl_pw_aff_list_free(list: list2);
2038	isl_set_free(set);
2039	return NULL;
2040	}
2041
2042	static __isl_give isl_map *read_exists(__isl_keep isl_stream *s,
2043	struct vars *v, __isl_take isl_map *map, int rational)
2044	{
2045	int n = v->n;
2046	int seen_paren = isl_stream_eat_if_available(s, type: '(');
2047
2048	map = isl_map_from_domain(set: isl_map_wrap(map));
2049	map = read_defined_var_list(s, v, map, rational);
2050
2051	if (isl_stream_eat(s, type: ':'))
2052	goto error;
2053
2054	map = read_formula(s, v, map, rational);
2055	map = isl_set_unwrap(set: isl_map_domain(bmap: map));
2056
2057	vars_drop(v, n: v->n - n);
2058	if (seen_paren && isl_stream_eat(s, type: ')'))
2059	goto error;
2060
2061	return map;
2062	error:
2063	isl_map_free(map);
2064	return NULL;
2065	}
2066
2067	/* Parse an expression between parentheses and push the result
2068	* back on the stream.
2069	*
2070	* The parsed expression may be either an affine expression
2071	* or a condition. The first type is pushed onto the stream
2072	* as an isl_pw_aff, while the second is pushed as an isl_map.
2073	*
2074	* If the initial token indicates the start of a condition,
2075	* we parse it as such.
2076	* Otherwise, we first parse an affine expression and push
2077	* that onto the stream. If the affine expression covers the
2078	* entire expression between parentheses, we return.
2079	* Otherwise, we assume that the affine expression is the
2080	* start of a condition and continue parsing.
2081	*/
2082	static int resolve_paren_expr(__isl_keep isl_stream *s,
2083	struct vars *v, __isl_take isl_map *map, int rational)
2084	{
2085	struct isl_token *tok, *tok2;
2086	int has_paren;
2087	int line, col;
2088	isl_pw_aff *pwaff;
2089
2090	tok = isl_stream_next_token(s);
2091	if (!tok || tok->type != '(')
2092	goto error;
2093
2094	if (isl_stream_next_token_is(s, type: '('))
2095	if (resolve_paren_expr(s, v, map: isl_map_copy(map), rational))
2096	goto error;
2097
2098	if (next_is_condition_start(s)) {
2099	map = read_formula(s, v, map, rational);
2100	if (isl_stream_eat(s, type: ')'))
2101	goto error;
2102	tok->type = ISL_TOKEN_MAP;
2103	tok->u.map = map;
2104	isl_stream_push_token(s, tok);
2105	return 0;
2106	}
2107
2108	tok2 = isl_stream_next_token(s);
2109	if (!tok2)
2110	goto error;
2111	line = tok2->line;
2112	col = tok2->col;
2113	isl_stream_push_token(s, tok: tok2);
2114
2115	pwaff = accept_affine(s, space: isl_space_wrap(space: isl_map_get_space(map)), v);
2116	if (!pwaff)
2117	goto error;
2118
2119	has_paren = isl_stream_eat_if_available(s, type: ')');
2120
2121	if (push_aff(s, line, col, pa: pwaff) < 0)
2122	goto error;
2123
2124	if (has_paren) {
2125	isl_token_free(tok);
2126	isl_map_free(map);
2127	return 0;
2128	}
2129
2130	map = read_formula(s, v, map, rational);
2131	if (isl_stream_eat(s, type: ')'))
2132	goto error;
2133
2134	tok->type = ISL_TOKEN_MAP;
2135	tok->u.map = map;
2136	isl_stream_push_token(s, tok);
2137
2138	return 0;
2139	error:
2140	isl_token_free(tok);
2141	isl_map_free(map);
2142	return -1;
2143	}
2144
2145	static __isl_give isl_map *read_conjunct(__isl_keep isl_stream *s,
2146	struct vars *v, __isl_take isl_map *map, int rational)
2147	{
2148	if (isl_stream_next_token_is(s, type: '('))
2149	if (resolve_paren_expr(s, v, map: isl_map_copy(map), rational))
2150	goto error;
2151
2152	if (isl_stream_next_token_is(s, type: ISL_TOKEN_MAP)) {
2153	struct isl_token *tok;
2154	tok = isl_stream_next_token(s);
2155	if (!tok)
2156	goto error;
2157	isl_map_free(map);
2158	map = isl_map_copy(map: tok->u.map);
2159	isl_token_free(tok);
2160	return map;
2161	}
2162
2163	if (isl_stream_eat_if_available(s, type: ISL_TOKEN_EXISTS))
2164	return read_exists(s, v, map, rational);
2165
2166	if (isl_stream_eat_if_available(s, type: ISL_TOKEN_TRUE))
2167	return map;
2168
2169	if (isl_stream_eat_if_available(s, type: ISL_TOKEN_FALSE)) {
2170	isl_space *space = isl_map_get_space(map);
2171	isl_map_free(map);
2172	return isl_map_empty(space);
2173	}
2174
2175	return add_constraint(s, v, map, rational);
2176	error:
2177	isl_map_free(map);
2178	return NULL;
2179	}
2180
2181	static __isl_give isl_map *read_conjuncts(__isl_keep isl_stream *s,
2182	struct vars *v, __isl_take isl_map *map, int rational)
2183	{
2184	isl_map *res;
2185	int negate;
2186
2187	negate = isl_stream_eat_if_available(s, type: ISL_TOKEN_NOT);
2188	res = read_conjunct(s, v, map: isl_map_copy(map), rational);
2189	if (negate)
2190	res = isl_map_subtract(map1: isl_map_copy(map), map2: res);
2191
2192	while (res && isl_stream_eat_if_available(s, type: ISL_TOKEN_AND)) {
2193	isl_map *res_i;
2194
2195	negate = isl_stream_eat_if_available(s, type: ISL_TOKEN_NOT);
2196	res_i = read_conjunct(s, v, map: isl_map_copy(map), rational);
2197	if (negate)
2198	res = isl_map_subtract(map1: res, map2: res_i);
2199	else
2200	res = isl_map_intersect(map1: res, map2: res_i);
2201	}
2202
2203	isl_map_free(map);
2204	return res;
2205	}
2206
2207	static __isl_give isl_map *read_disjuncts(__isl_keep isl_stream *s,
2208	struct vars *v, __isl_take isl_map *map, int rational)
2209	{
2210	isl_map *res;
2211
2212	if (isl_stream_next_token_is(s, type: '}'))
2213	return map;
2214
2215	res = read_conjuncts(s, v, map: isl_map_copy(map), rational);
2216	while (isl_stream_eat_if_available(s, type: ISL_TOKEN_OR)) {
2217	isl_map *res_i;
2218
2219	res_i = read_conjuncts(s, v, map: isl_map_copy(map), rational);
2220	res = isl_map_union(map1: res, map2: res_i);
2221	}
2222
2223	isl_map_free(map);
2224	return res;
2225	}
2226
2227	/* Read a first order formula from "s", add the corresponding
2228	* constraints to "map" and return the result.
2229	*
2230	* In particular, read a formula of the form
2231	*
2232	* a
2233	*
2234	* or
2235	*
2236	* a implies b
2237	*
2238	* where a and b are disjunctions.
2239	*
2240	* In the first case, map is replaced by
2241	*
2242	* map \cap { [..] : a }
2243	*
2244	* In the second case, it is replaced by
2245	*
2246	* (map \setminus { [..] : a}) \cup (map \cap { [..] : b })
2247	*/
2248	static __isl_give isl_map *read_formula(__isl_keep isl_stream *s,
2249	struct vars *v, __isl_take isl_map *map, int rational)
2250	{
2251	isl_map *res;
2252
2253	res = read_disjuncts(s, v, map: isl_map_copy(map), rational);
2254
2255	if (isl_stream_eat_if_available(s, type: ISL_TOKEN_IMPLIES)) {
2256	isl_map *res2;
2257
2258	res = isl_map_subtract(map1: isl_map_copy(map), map2: res);
2259	res2 = read_disjuncts(s, v, map, rational);
2260	res = isl_map_union(map1: res, map2: res2);
2261	} else
2262	isl_map_free(map);
2263
2264	return res;
2265	}
2266
2267	static isl_size polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
2268	{
2269	isl_size n_out, n_in, n_param, n_div;
2270
2271	n_param = isl_basic_map_dim(bmap, type: isl_dim_param);
2272	n_in = isl_basic_map_dim(bmap, type: isl_dim_in);
2273	n_out = isl_basic_map_dim(bmap, type: isl_dim_out);
2274	n_div = isl_basic_map_dim(bmap, type: isl_dim_div);
2275	if (n_param < 0 || n_in < 0 || n_out < 0 || n_div < 0)
2276	return isl_size_error;
2277
2278	if (pos < n_out)
2279	return 1 + n_param + n_in + pos;
2280	pos -= n_out;
2281
2282	if (pos < n_in)
2283	return 1 + n_param + pos;
2284	pos -= n_in;
2285
2286	if (pos < n_div)
2287	return 1 + n_param + n_in + n_out + pos;
2288	pos -= n_div;
2289
2290	if (pos < n_param)
2291	return 1 + pos;
2292
2293	return 0;
2294	}
2295
2296	static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
2297	__isl_keep isl_stream *s, __isl_take isl_basic_map *bmap)
2298	{
2299	int j;
2300	struct isl_token *tok;
2301	int type;
2302	int k;
2303	isl_int *c;
2304	isl_size total;
2305
2306	if (!bmap)
2307	return NULL;
2308
2309	tok = isl_stream_next_token(s);
2310	if (!tok || tok->type != ISL_TOKEN_VALUE) {
2311	isl_stream_error(s, tok, msg: "expecting coefficient");
2312	isl_token_free(tok);
2313	goto error;
2314	}
2315	if (!tok->on_new_line) {
2316	isl_stream_error(s, tok, msg: "coefficient should appear on new line");
2317	isl_token_free(tok);
2318	goto error;
2319	}
2320
2321	type = isl_int_get_si(tok->u.v);
2322	isl_token_free(tok);
2323
2324	isl_assert(s->ctx, type == 0 || type == 1, goto error);
2325	if (type == 0) {
2326	k = isl_basic_map_alloc_equality(bmap);
2327	c = bmap->eq[k];
2328	} else {
2329	k = isl_basic_map_alloc_inequality(bmap);
2330	c = bmap->ineq[k];
2331	}
2332	if (k < 0)
2333	goto error;
2334
2335	total = isl_basic_map_dim(bmap, type: isl_dim_all);
2336	if (total < 0)
2337	return isl_basic_map_free(bmap);
2338	for (j = 0; j < 1 + total; ++j) {
2339	isl_size pos;
2340	tok = next_signed_value_on_same_line(s,
2341	msg: "expecting coefficient on same line");
2342	if (!tok)
2343	goto error;
2344	pos = polylib_pos_to_isl_pos(bmap, pos: j);
2345	if (pos >= 0)
2346	isl_int_set(c[pos], tok->u.v);
2347	isl_token_free(tok);
2348	if (pos < 0)
2349	return isl_basic_map_free(bmap);
2350	}
2351
2352	return bmap;
2353	error:
2354	isl_basic_map_free(bmap);
2355	return NULL;
2356	}
2357
2358	static __isl_give isl_basic_map *basic_map_read_polylib(
2359	__isl_keep isl_stream *s)
2360	{
2361	int i;
2362	struct isl_token *tok;
2363	struct isl_token *tok2;
2364	int n_row, n_col;
2365	int on_new_line;
2366	unsigned in = 0, out, local = 0;
2367	struct isl_basic_map *bmap = NULL;
2368	int nparam = 0;
2369
2370	tok = isl_stream_next_token(s);
2371	if (!tok) {
2372	isl_stream_error(s, NULL, msg: "unexpected EOF");
2373	return NULL;
2374	}
2375	tok2 = isl_stream_next_token(s);
2376	if (!tok2) {
2377	isl_token_free(tok);
2378	isl_stream_error(s, NULL, msg: "unexpected EOF");
2379	return NULL;
2380	}
2381	if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
2382	isl_token_free(tok: tok2);
2383	isl_token_free(tok);
2384	isl_stream_error(s, NULL,
2385	msg: "expecting constraint matrix dimensions");
2386	return NULL;
2387	}
2388	n_row = isl_int_get_si(tok->u.v);
2389	n_col = isl_int_get_si(tok2->u.v);
2390	on_new_line = tok2->on_new_line;
2391	isl_token_free(tok: tok2);
2392	isl_token_free(tok);
2393	isl_assert(s->ctx, !on_new_line, return NULL);
2394	isl_assert(s->ctx, n_row >= 0, return NULL);
2395	isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
2396	tok = isl_stream_next_token_on_same_line(s);
2397	if (tok) {
2398	if (tok->type != ISL_TOKEN_VALUE) {
2399	isl_stream_error(s, tok,
2400	msg: "expecting number of output dimensions");
2401	isl_token_free(tok);
2402	goto error;
2403	}
2404	out = isl_int_get_si(tok->u.v);
2405	isl_token_free(tok);
2406
2407	tok = isl_stream_next_token_on_same_line(s);
2408	if (!tok || tok->type != ISL_TOKEN_VALUE) {
2409	isl_stream_error(s, tok,
2410	msg: "expecting number of input dimensions");
2411	isl_token_free(tok);
2412	goto error;
2413	}
2414	in = isl_int_get_si(tok->u.v);
2415	isl_token_free(tok);
2416
2417	tok = isl_stream_next_token_on_same_line(s);
2418	if (!tok || tok->type != ISL_TOKEN_VALUE) {
2419	isl_stream_error(s, tok,
2420	msg: "expecting number of existentials");
2421	isl_token_free(tok);
2422	goto error;
2423	}
2424	local = isl_int_get_si(tok->u.v);
2425	isl_token_free(tok);
2426
2427	tok = isl_stream_next_token_on_same_line(s);
2428	if (!tok || tok->type != ISL_TOKEN_VALUE) {
2429	isl_stream_error(s, tok,
2430	msg: "expecting number of parameters");
2431	isl_token_free(tok);
2432	goto error;
2433	}
2434	nparam = isl_int_get_si(tok->u.v);
2435	isl_token_free(tok);
2436	if (n_col != 1 + out + in + local + nparam + 1) {
2437	isl_stream_error(s, NULL,
2438	msg: "dimensions don't match");
2439	goto error;
2440	}
2441	} else
2442	out = n_col - 2 - nparam;
2443	bmap = isl_basic_map_alloc(ctx: s->ctx, nparam, in, out, extra: local, n_eq: n_row, n_ineq: n_row);
2444	if (!bmap)
2445	return NULL;
2446
2447	for (i = 0; i < local; ++i) {
2448	int k = isl_basic_map_alloc_div(bmap);
2449	if (k < 0)
2450	goto error;
2451	isl_seq_clr(p: bmap->div[k], len: 1 + 1 + nparam + in + out + local);
2452	}
2453
2454	for (i = 0; i < n_row; ++i)
2455	bmap = basic_map_read_polylib_constraint(s, bmap);
2456
2457	if (!bmap)
2458	return NULL;
2459
2460	tok = isl_stream_next_token_on_same_line(s);
2461	if (tok) {
2462	isl_stream_error(s, tok, msg: "unexpected extra token on line");
2463	isl_token_free(tok);
2464	goto error;
2465	}
2466
2467	bmap = isl_basic_map_simplify(bmap);
2468	bmap = isl_basic_map_finalize(bmap);
2469	return bmap;
2470	error:
2471	isl_basic_map_free(bmap);
2472	return NULL;
2473	}
2474
2475	static __isl_give isl_map *map_read_polylib(__isl_keep isl_stream *s)
2476	{
2477	struct isl_token *tok;
2478	struct isl_token *tok2;
2479	int i, n;
2480	struct isl_map *map;
2481
2482	tok = isl_stream_next_token(s);
2483	if (!tok) {
2484	isl_stream_error(s, NULL, msg: "unexpected EOF");
2485	return NULL;
2486	}
2487	tok2 = isl_stream_next_token_on_same_line(s);
2488	if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
2489	isl_stream_push_token(s, tok: tok2);
2490	isl_stream_push_token(s, tok);
2491	return isl_map_from_basic_map(bmap: basic_map_read_polylib(s));
2492	}
2493	if (tok2) {
2494	isl_stream_error(s, tok: tok2, msg: "unexpected token");
2495	isl_stream_push_token(s, tok: tok2);
2496	isl_stream_push_token(s, tok);
2497	return NULL;
2498	}
2499	n = isl_int_get_si(tok->u.v);
2500	isl_token_free(tok);
2501
2502	isl_assert(s->ctx, n >= 1, return NULL);
2503
2504	map = isl_map_from_basic_map(bmap: basic_map_read_polylib(s));
2505
2506	for (i = 1; map && i < n; ++i)
2507	map = isl_map_union(map1: map,
2508	map2: isl_map_from_basic_map(bmap: basic_map_read_polylib(s)));
2509
2510	return map;
2511	}
2512
2513	static int optional_power(__isl_keep isl_stream *s)
2514	{
2515	int pow;
2516	struct isl_token *tok;
2517
2518	tok = isl_stream_next_token(s);
2519	if (!tok)
2520	return 1;
2521	if (tok->type != '^') {
2522	isl_stream_push_token(s, tok);
2523	return 1;
2524	}
2525	isl_token_free(tok);
2526	tok = isl_stream_next_token(s);
2527	if (!tok || tok->type != ISL_TOKEN_VALUE) {
2528	isl_stream_error(s, tok, msg: "expecting exponent");
2529	if (tok)
2530	isl_stream_push_token(s, tok);
2531	return 1;
2532	}
2533	pow = isl_int_get_si(tok->u.v);
2534	isl_token_free(tok);
2535	return pow;
2536	}
2537
2538	static __isl_give isl_pw_qpolynomial *read_term(__isl_keep isl_stream *s,
2539	__isl_keep isl_map *map, struct vars *v);
2540
2541	static __isl_give isl_pw_qpolynomial *read_factor(__isl_keep isl_stream *s,
2542	__isl_keep isl_map *map, struct vars *v)
2543	{
2544	isl_pw_qpolynomial *pwqp;
2545	struct isl_token *tok;
2546
2547	tok = next_token(s);
2548	if (!tok) {
2549	isl_stream_error(s, NULL, msg: "unexpected EOF");
2550	return NULL;
2551	}
2552	if (tok->type == '(') {
2553	int pow;
2554
2555	isl_token_free(tok);
2556	pwqp = read_term(s, map, v);
2557	if (!pwqp)
2558	return NULL;
2559	if (isl_stream_eat(s, type: ')'))
2560	goto error;
2561	pow = optional_power(s);
2562	pwqp = isl_pw_qpolynomial_pow(pwqp, exponent: pow);
2563	} else if (tok->type == ISL_TOKEN_VALUE) {
2564	struct isl_token *tok2;
2565	isl_qpolynomial *qp;
2566
2567	tok2 = isl_stream_next_token(s);
2568	if (tok2 && tok2->type == '/') {
2569	isl_token_free(tok: tok2);
2570	tok2 = next_token(s);
2571	if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
2572	isl_stream_error(s, tok: tok2, msg: "expected denominator");
2573	isl_token_free(tok);
2574	isl_token_free(tok: tok2);
2575	return NULL;
2576	}
2577	qp = isl_qpolynomial_rat_cst_on_domain(domain: isl_map_get_space(map),
2578	n: tok->u.v, d: tok2->u.v);
2579	isl_token_free(tok: tok2);
2580	} else {
2581	isl_stream_push_token(s, tok: tok2);
2582	qp = isl_qpolynomial_cst_on_domain(domain: isl_map_get_space(map),
2583	v: tok->u.v);
2584	}
2585	isl_token_free(tok);
2586	pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2587	} else if (tok->type == ISL_TOKEN_INFTY) {
2588	isl_qpolynomial *qp;
2589	isl_token_free(tok);
2590	qp = isl_qpolynomial_infty_on_domain(domain: isl_map_get_space(map));
2591	pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2592	} else if (tok->type == ISL_TOKEN_NAN) {
2593	isl_qpolynomial *qp;
2594	isl_token_free(tok);
2595	qp = isl_qpolynomial_nan_on_domain(domain: isl_map_get_space(map));
2596	pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2597	} else if (tok->type == ISL_TOKEN_IDENT) {
2598	int n = v->n;
2599	int pos = vars_pos(v, s: tok->u.s, len: -1);
2600	int pow;
2601	isl_qpolynomial *qp;
2602	if (pos < 0) {
2603	isl_token_free(tok);
2604	return NULL;
2605	}
2606	if (pos >= n) {
2607	vars_drop(v, n: v->n - n);
2608	isl_stream_error(s, tok, msg: "unknown identifier");
2609	isl_token_free(tok);
2610	return NULL;
2611	}
2612	isl_token_free(tok);
2613	pow = optional_power(s);
2614	qp = isl_qpolynomial_var_pow_on_domain(domain: isl_map_get_space(map), pos, power: pow);
2615	pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2616	} else if (is_start_of_div(tok)) {
2617	isl_pw_aff *pwaff;
2618	int pow;
2619
2620	isl_stream_push_token(s, tok);
2621	pwaff = accept_div(s, space: isl_map_get_space(map), v);
2622	pow = optional_power(s);
2623	pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff);
2624	pwqp = isl_pw_qpolynomial_pow(pwqp, exponent: pow);
2625	} else if (tok->type == '-') {
2626	isl_token_free(tok);
2627	pwqp = read_factor(s, map, v);
2628	pwqp = isl_pw_qpolynomial_neg(pwqp);
2629	} else {
2630	isl_stream_error(s, tok, msg: "unexpected isl_token");
2631	isl_stream_push_token(s, tok);
2632	return NULL;
2633	}
2634
2635	if (isl_stream_eat_if_available(s, type: '*') ||
2636	isl_stream_next_token_is(s, type: ISL_TOKEN_IDENT)) {
2637	isl_pw_qpolynomial *pwqp2;
2638
2639	pwqp2 = read_factor(s, map, v);
2640	pwqp = isl_pw_qpolynomial_mul(pwqp1: pwqp, pwqp2);
2641	}
2642
2643	return pwqp;
2644	error:
2645	isl_pw_qpolynomial_free(pwqp);
2646	return NULL;
2647	}
2648
2649	static __isl_give isl_pw_qpolynomial *read_term(__isl_keep isl_stream *s,
2650	__isl_keep isl_map *map, struct vars *v)
2651	{
2652	struct isl_token *tok;
2653	isl_pw_qpolynomial *pwqp;
2654
2655	pwqp = read_factor(s, map, v);
2656
2657	for (;;) {
2658	tok = next_token(s);
2659	if (!tok)
2660	return pwqp;
2661
2662	if (tok->type == '+') {
2663	isl_pw_qpolynomial *pwqp2;
2664
2665	isl_token_free(tok);
2666	pwqp2 = read_factor(s, map, v);
2667	pwqp = isl_pw_qpolynomial_add(pwqp1: pwqp, pwqp2);
2668	} else if (tok->type == '-') {
2669	isl_pw_qpolynomial *pwqp2;
2670
2671	isl_token_free(tok);
2672	pwqp2 = read_factor(s, map, v);
2673	pwqp = isl_pw_qpolynomial_sub(pwqp1: pwqp, pwqp2);
2674	} else {
2675	isl_stream_push_token(s, tok);
2676	break;
2677	}
2678	}
2679
2680	return pwqp;
2681	}
2682
2683	static __isl_give isl_map *read_optional_formula(__isl_keep isl_stream *s,
2684	__isl_take isl_map *map, struct vars *v, int rational)
2685	{
2686	struct isl_token *tok;
2687
2688	tok = isl_stream_next_token(s);
2689	if (!tok) {
2690	isl_stream_error(s, NULL, msg: "unexpected EOF");
2691	goto error;
2692	}
2693	if (tok->type == ':' ||
2694	(tok->type == ISL_TOKEN_OR && !strcmp(s1: tok->u.s, s2: "|"))) {
2695	isl_token_free(tok);
2696	map = read_formula(s, v, map, rational);
2697	} else
2698	isl_stream_push_token(s, tok);
2699
2700	return map;
2701	error:
2702	isl_map_free(map);
2703	return NULL;
2704	}
2705
2706	static struct isl_obj obj_read_poly(__isl_keep isl_stream *s,
2707	__isl_take isl_map *map, struct vars *v, int n)
2708	{
2709	struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
2710	isl_pw_qpolynomial *pwqp;
2711	struct isl_set *set;
2712
2713	pwqp = read_term(s, map, v);
2714	map = read_optional_formula(s, map, v, rational: 0);
2715	set = isl_map_range(map);
2716
2717	pwqp = isl_pw_qpolynomial_intersect_domain(pwpq: pwqp, set);
2718
2719	vars_drop(v, n: v->n - n);
2720
2721	obj.v = pwqp;
2722	return obj;
2723	}
2724
2725	static struct isl_obj obj_read_poly_or_fold(__isl_keep isl_stream *s,
2726	__isl_take isl_set *set, struct vars *v, int n)
2727	{
2728	int min, max;
2729	struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
2730	isl_pw_qpolynomial *pwqp;
2731	isl_pw_qpolynomial_fold *pwf = NULL;
2732	enum isl_fold fold;
2733
2734	max = isl_stream_eat_if_available(s, type: ISL_TOKEN_MAX);
2735	min = !max && isl_stream_eat_if_available(s, type: ISL_TOKEN_MIN);
2736	if (!min && !max)
2737	return obj_read_poly(s, map: set, v, n);
2738	fold = max ? isl_fold_max : isl_fold_min;
2739
2740	if (isl_stream_eat(s, type: '('))
2741	goto error;
2742
2743	pwqp = read_term(s, map: set, v);
2744	pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type: fold, pwqp);
2745
2746	while (isl_stream_eat_if_available(s, type: ',')) {
2747	isl_pw_qpolynomial_fold *pwf_i;
2748	pwqp = read_term(s, map: set, v);
2749	pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type: fold, pwqp);
2750	pwf = isl_pw_qpolynomial_fold_fold(pwf1: pwf, pwf2: pwf_i);
2751	}
2752
2753	if (isl_stream_eat(s, type: ')'))
2754	goto error;
2755
2756	set = read_optional_formula(s, map: set, v, rational: 0);
2757	pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set);
2758
2759	vars_drop(v, n: v->n - n);
2760
2761	obj.v = pwf;
2762	return obj;
2763	error:
2764	isl_set_free(set);
2765	isl_pw_qpolynomial_fold_free(pwf);
2766	obj.type = isl_obj_none;
2767	return obj;
2768	}
2769
2770	static int is_rational(__isl_keep isl_stream *s)
2771	{
2772	struct isl_token *tok;
2773
2774	tok = isl_stream_next_token(s);
2775	if (!tok)
2776	return 0;
2777	if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, type: ':')) {
2778	isl_token_free(tok);
2779	isl_stream_eat(s, type: ':');
2780	return 1;
2781	}
2782
2783	isl_stream_push_token(s, tok);
2784
2785	return 0;
2786	}
2787
2788	static struct isl_obj obj_read_body(__isl_keep isl_stream *s,
2789	__isl_take isl_map *map, struct vars *v)
2790	{
2791	struct isl_token *tok;
2792	struct isl_obj obj = { isl_obj_set, NULL };
2793	int n = v->n;
2794	int rational;
2795
2796	rational = is_rational(s);
2797	if (rational)
2798	map = isl_map_set_rational(map);
2799
2800	if (isl_stream_next_token_is(s, type: ':')) {
2801	obj.type = isl_obj_set;
2802	obj.v = read_optional_formula(s, map, v, rational);
2803	return obj;
2804	}
2805
2806	if (!next_is_tuple(s))
2807	return obj_read_poly_or_fold(s, set: map, v, n);
2808
2809	map = read_map_tuple(s, map, type: isl_dim_in, v, rational, comma: 0);
2810	if (!map)
2811	goto error;
2812	tok = isl_stream_next_token(s);
2813	if (!tok)
2814	goto error;
2815	if (tok->type == ISL_TOKEN_TO) {
2816	obj.type = isl_obj_map;
2817	isl_token_free(tok);
2818	if (!next_is_tuple(s)) {
2819	isl_set *set = isl_map_domain(bmap: map);
2820	return obj_read_poly_or_fold(s, set, v, n);
2821	}
2822	map = read_map_tuple(s, map, type: isl_dim_out, v, rational, comma: 0);
2823	if (!map)
2824	goto error;
2825	} else {
2826	map = isl_map_domain(bmap: map);
2827	isl_stream_push_token(s, tok);
2828	}
2829
2830	map = read_optional_formula(s, map, v, rational);
2831
2832	vars_drop(v, n: v->n - n);
2833
2834	obj.v = map;
2835	return obj;
2836	error:
2837	isl_map_free(map);
2838	obj.type = isl_obj_none;
2839	return obj;
2840	}
2841
2842	static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
2843	{
2844	if (obj.type == isl_obj_map) {
2845	obj.v = isl_union_map_from_map(map: obj.v);
2846	obj.type = isl_obj_union_map;
2847	} else if (obj.type == isl_obj_set) {
2848	obj.v = isl_union_set_from_set(set: obj.v);
2849	obj.type = isl_obj_union_set;
2850	} else if (obj.type == isl_obj_pw_qpolynomial) {
2851	obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(pwqp: obj.v);
2852	obj.type = isl_obj_union_pw_qpolynomial;
2853	} else if (obj.type == isl_obj_pw_qpolynomial_fold) {
2854	obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(pwf: obj.v);
2855	obj.type = isl_obj_union_pw_qpolynomial_fold;
2856	} else
2857	isl_assert(ctx, 0, goto error);
2858	return obj;
2859	error:
2860	obj.type->free(obj.v);
2861	obj.type = isl_obj_none;
2862	return obj;
2863	}
2864
2865	static struct isl_obj obj_add(__isl_keep isl_stream *s,
2866	struct isl_obj obj1, struct isl_obj obj2)
2867	{
2868	if (obj2.type == isl_obj_none || !obj2.v)
2869	goto error;
2870	if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
2871	obj1 = to_union(ctx: s->ctx, obj: obj1);
2872	if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
2873	obj2 = to_union(ctx: s->ctx, obj: obj2);
2874	if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
2875	obj1 = to_union(ctx: s->ctx, obj: obj1);
2876	if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
2877	obj2 = to_union(ctx: s->ctx, obj: obj2);
2878	if (obj1.type == isl_obj_pw_qpolynomial &&
2879	obj2.type == isl_obj_union_pw_qpolynomial)
2880	obj1 = to_union(ctx: s->ctx, obj: obj1);
2881	if (obj1.type == isl_obj_union_pw_qpolynomial &&
2882	obj2.type == isl_obj_pw_qpolynomial)
2883	obj2 = to_union(ctx: s->ctx, obj: obj2);
2884	if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2885	obj2.type == isl_obj_union_pw_qpolynomial_fold)
2886	obj1 = to_union(ctx: s->ctx, obj: obj1);
2887	if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
2888	obj2.type == isl_obj_pw_qpolynomial_fold)
2889	obj2 = to_union(ctx: s->ctx, obj: obj2);
2890	if (obj1.type != obj2.type) {
2891	isl_stream_error(s, NULL,
2892	msg: "attempt to combine incompatible objects");
2893	goto error;
2894	}
2895	if (!obj1.type->add)
2896	isl_die(s->ctx, isl_error_internal,
2897	"combination not supported on object type", goto error);
2898	if (obj1.type == isl_obj_map && !isl_map_has_equal_space(map1: obj1.v, map2: obj2.v)) {
2899	obj1 = to_union(ctx: s->ctx, obj: obj1);
2900	obj2 = to_union(ctx: s->ctx, obj: obj2);
2901	}
2902	if (obj1.type == isl_obj_set && !isl_set_has_equal_space(set1: obj1.v, set2: obj2.v)) {
2903	obj1 = to_union(ctx: s->ctx, obj: obj1);
2904	obj2 = to_union(ctx: s->ctx, obj: obj2);
2905	}
2906	if (obj1.type == isl_obj_pw_qpolynomial &&
2907	!isl_pw_qpolynomial_has_equal_space(pwqp1: obj1.v, pwqp2: obj2.v)) {
2908	obj1 = to_union(ctx: s->ctx, obj: obj1);
2909	obj2 = to_union(ctx: s->ctx, obj: obj2);
2910	}
2911	if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2912	!isl_pw_qpolynomial_fold_has_equal_space(pwf1: obj1.v, pwf2: obj2.v)) {
2913	obj1 = to_union(ctx: s->ctx, obj: obj1);
2914	obj2 = to_union(ctx: s->ctx, obj: obj2);
2915	}
2916	obj1.v = obj1.type->add(obj1.v, obj2.v);
2917	return obj1;
2918	error:
2919	obj1.type->free(obj1.v);
2920	obj2.type->free(obj2.v);
2921	obj1.type = isl_obj_none;
2922	obj1.v = NULL;
2923	return obj1;
2924	}
2925
2926	/* Are the first two tokens on "s", "domain" (either as a string
2927	* or as an identifier) followed by ":"?
2928	*/
2929	static int next_is_domain_colon(__isl_keep isl_stream *s)
2930	{
2931	struct isl_token *tok;
2932	char *name;
2933	int res;
2934
2935	tok = isl_stream_next_token(s);
2936	if (!tok)
2937	return 0;
2938	if (tok->type != ISL_TOKEN_IDENT && tok->type != ISL_TOKEN_STRING) {
2939	isl_stream_push_token(s, tok);
2940	return 0;
2941	}
2942
2943	name = isl_token_get_str(ctx: s->ctx, tok);
2944	res = !strcmp(s1: name, s2: "domain") && isl_stream_next_token_is(s, type: ':');
2945	free(ptr: name);
2946
2947	isl_stream_push_token(s, tok);
2948
2949	return res;
2950	}
2951
2952	/* Do the first tokens on "s" look like a schedule?
2953	*
2954	* The root of a schedule is always a domain node, so the first thing
2955	* we expect in the stream is a domain key, i.e., "domain" followed
2956	* by ":". If the schedule was printed in YAML flow style, then
2957	* we additionally expect a "{" to open the outer mapping.
2958	*/
2959	static int next_is_schedule(__isl_keep isl_stream *s)
2960	{
2961	struct isl_token *tok;
2962	int is_schedule;
2963
2964	tok = isl_stream_next_token(s);
2965	if (!tok)
2966	return 0;
2967	if (tok->type != '{') {
2968	isl_stream_push_token(s, tok);
2969	return next_is_domain_colon(s);
2970	}
2971
2972	is_schedule = next_is_domain_colon(s);
2973	isl_stream_push_token(s, tok);
2974
2975	return is_schedule;
2976	}
2977
2978	/* Read an isl_schedule from "s" and store it in an isl_obj.
2979	*/
2980	static struct isl_obj schedule_read(__isl_keep isl_stream *s)
2981	{
2982	struct isl_obj obj;
2983
2984	obj.type = isl_obj_schedule;
2985	obj.v = isl_stream_read_schedule(s);
2986
2987	return obj;
2988	}
2989
2990	/* Read a disjunction of object bodies from "s".
2991	* That is, read the inside of the braces, but not the braces themselves.
2992	* "v" contains a description of the identifiers parsed so far.
2993	* "map" contains information about the parameters.
2994	*/
2995	static struct isl_obj obj_read_disjuncts(__isl_keep isl_stream *s,
2996	struct vars *v, __isl_keep isl_map *map)
2997	{
2998	struct isl_obj obj = { isl_obj_set, NULL };
2999
3000	if (isl_stream_next_token_is(s, type: '}')) {
3001	obj.type = isl_obj_union_set;
3002	obj.v = isl_union_set_empty(space: isl_map_get_space(map));
3003	return obj;
3004	}
3005
3006	for (;;) {
3007	struct isl_obj o;
3008	o = obj_read_body(s, map: isl_map_copy(map), v);
3009	if (!obj.v)
3010	obj = o;
3011	else
3012	obj = obj_add(s, obj1: obj, obj2: o);
3013	if (obj.type == isl_obj_none || !obj.v)
3014	return obj;
3015	if (!isl_stream_eat_if_available(s, type: ';'))
3016	break;
3017	if (isl_stream_next_token_is(s, type: '}'))
3018	break;
3019	}
3020
3021	return obj;
3022	}
3023
3024	static struct isl_obj obj_read(__isl_keep isl_stream *s)
3025	{
3026	isl_map *map = NULL;
3027	struct isl_token *tok;
3028	struct vars *v = NULL;
3029	struct isl_obj obj = { isl_obj_set, NULL };
3030
3031	if (next_is_schedule(s))
3032	return schedule_read(s);
3033
3034	tok = next_token(s);
3035	if (!tok) {
3036	isl_stream_error(s, NULL, msg: "unexpected EOF");
3037	goto error;
3038	}
3039	if (tok->type == ISL_TOKEN_VALUE) {
3040	struct isl_token *tok2;
3041	struct isl_map *map;
3042
3043	tok2 = isl_stream_next_token(s);
3044	if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
3045	isl_int_is_neg(tok2->u.v)) {
3046	if (tok2)
3047	isl_stream_push_token(s, tok: tok2);
3048	obj.type = isl_obj_val;
3049	obj.v = isl_val_int_from_isl_int(ctx: s->ctx, n: tok->u.v);
3050	isl_token_free(tok);
3051	return obj;
3052	}
3053	isl_stream_push_token(s, tok: tok2);
3054	isl_stream_push_token(s, tok);
3055	map = map_read_polylib(s);
3056	if (!map)
3057	goto error;
3058	if (isl_map_may_be_set(map))
3059	obj.v = isl_map_range(map);
3060	else {
3061	obj.type = isl_obj_map;
3062	obj.v = map;
3063	}
3064	return obj;
3065	}
3066	v = vars_new(ctx: s->ctx);
3067	if (!v) {
3068	isl_stream_push_token(s, tok);
3069	goto error;
3070	}
3071	map = isl_map_universe(space: isl_space_params_alloc(ctx: s->ctx, nparam: 0));
3072	if (tok->type == '[') {
3073	isl_stream_push_token(s, tok);
3074	map = read_map_tuple(s, map, type: isl_dim_param, v, rational: 0, comma: 0);
3075	if (!map)
3076	goto error;
3077	tok = isl_stream_next_token(s);
3078	if (!tok || tok->type != ISL_TOKEN_TO) {
3079	isl_stream_error(s, tok, msg: "expecting '->'");
3080	if (tok)
3081	isl_stream_push_token(s, tok);
3082	goto error;
3083	}
3084	isl_token_free(tok);
3085	tok = isl_stream_next_token(s);
3086	}
3087	if (!tok || tok->type != '{') {
3088	isl_stream_error(s, tok, msg: "expecting '{'");
3089	if (tok)
3090	isl_stream_push_token(s, tok);
3091	goto error;
3092	}
3093	isl_token_free(tok);
3094
3095	tok = isl_stream_next_token(s);
3096	if (!tok)
3097	;
3098	else if (tok->type == ISL_TOKEN_IDENT && !strcmp(s1: tok->u.s, s2: "Sym")) {
3099	isl_token_free(tok);
3100	if (isl_stream_eat(s, type: '='))
3101	goto error;
3102	map = read_map_tuple(s, map, type: isl_dim_param, v, rational: 0, comma: 1);
3103	if (!map)
3104	goto error;
3105	} else
3106	isl_stream_push_token(s, tok);
3107
3108	obj = obj_read_disjuncts(s, v, map);
3109	if (obj.type == isl_obj_none || !obj.v)
3110	goto error;
3111
3112	tok = isl_stream_next_token(s);
3113	if (tok && tok->type == '}') {
3114	isl_token_free(tok);
3115	} else {
3116	isl_stream_error(s, tok, msg: "unexpected isl_token");
3117	if (tok)
3118	isl_token_free(tok);
3119	goto error;
3120	}
3121
3122	vars_free(v);
3123	isl_map_free(map);
3124
3125	return obj;
3126	error:
3127	isl_map_free(map);
3128	obj.type->free(obj.v);
3129	if (v)
3130	vars_free(v);
3131	obj.v = NULL;
3132	return obj;
3133	}
3134
3135	struct isl_obj isl_stream_read_obj(__isl_keep isl_stream *s)
3136	{
3137	return obj_read(s);
3138	}
3139
3140	__isl_give isl_map *isl_stream_read_map(__isl_keep isl_stream *s)
3141	{
3142	struct isl_obj obj;
3143
3144	obj = obj_read(s);
3145	if (obj.v)
3146	isl_assert(s->ctx, obj.type == isl_obj_map ||
3147	obj.type == isl_obj_set, goto error);
3148
3149	if (obj.type == isl_obj_set)
3150	obj.v = isl_map_from_range(set: obj.v);
3151
3152	return obj.v;
3153	error:
3154	obj.type->free(obj.v);
3155	return NULL;
3156	}
3157
3158	__isl_give isl_set *isl_stream_read_set(__isl_keep isl_stream *s)
3159	{
3160	struct isl_obj obj;
3161
3162	obj = obj_read(s);
3163	if (obj.v) {
3164	if (obj.type == isl_obj_map && isl_map_may_be_set(map: obj.v)) {
3165	obj.v = isl_map_range(map: obj.v);
3166	obj.type = isl_obj_set;
3167	}
3168	isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
3169	}
3170
3171	return obj.v;
3172	error:
3173	obj.type->free(obj.v);
3174	return NULL;
3175	}
3176
3177	__isl_give isl_union_map *isl_stream_read_union_map(__isl_keep isl_stream *s)
3178	{
3179	struct isl_obj obj;
3180
3181	obj = obj_read(s);
3182	if (obj.type == isl_obj_map) {
3183	obj.type = isl_obj_union_map;
3184	obj.v = isl_union_map_from_map(map: obj.v);
3185	}
3186	if (obj.type == isl_obj_set) {
3187	obj.type = isl_obj_union_set;
3188	obj.v = isl_union_set_from_set(set: obj.v);
3189	}
3190	if (obj.v && obj.type == isl_obj_union_set &&
3191	isl_union_set_is_empty(uset: obj.v))
3192	obj.type = isl_obj_union_map;
3193	if (obj.v && obj.type != isl_obj_union_map)
3194	isl_die(s->ctx, isl_error_invalid, "invalid input", goto error);
3195
3196	return obj.v;
3197	error:
3198	obj.type->free(obj.v);
3199	return NULL;
3200	}
3201
3202	/* Extract an isl_union_set from "obj".
3203	* This only works if the object was detected as either a set
3204	* (in which case it is converted to a union set) or a union set.
3205	*/
3206	static __isl_give isl_union_set *extract_union_set(isl_ctx *ctx,
3207	struct isl_obj obj)
3208	{
3209	if (obj.type == isl_obj_set) {
3210	obj.type = isl_obj_union_set;
3211	obj.v = isl_union_set_from_set(set: obj.v);
3212	}
3213	if (obj.v)
3214	isl_assert(ctx, obj.type == isl_obj_union_set, goto error);
3215
3216	return obj.v;
3217	error:
3218	obj.type->free(obj.v);
3219	return NULL;
3220	}
3221
3222	/* Read an isl_union_set from "s".
3223	* First read a generic object and then try and extract
3224	* an isl_union_set from that.
3225	*/
3226	__isl_give isl_union_set *isl_stream_read_union_set(__isl_keep isl_stream *s)
3227	{
3228	struct isl_obj obj;
3229
3230	obj = obj_read(s);
3231	return extract_union_set(ctx: s->ctx, obj);
3232	}
3233
3234	static __isl_give isl_basic_map *isl_stream_read_basic_map(
3235	__isl_keep isl_stream *s)
3236	{
3237	struct isl_obj obj;
3238	struct isl_map *map;
3239	struct isl_basic_map *bmap;
3240
3241	obj = obj_read(s);
3242	if (obj.v && (obj.type != isl_obj_map && obj.type != isl_obj_set))
3243	isl_die(s->ctx, isl_error_invalid, "not a (basic) set or map",
3244	goto error);
3245	map = obj.v;
3246	if (!map)
3247	return NULL;
3248
3249	if (map->n > 1)
3250	isl_die(s->ctx, isl_error_invalid,
3251	"set or map description involves "
3252	"more than one disjunct", goto error);
3253
3254	if (map->n == 0)
3255	bmap = isl_basic_map_empty(space: isl_map_get_space(map));
3256	else
3257	bmap = isl_basic_map_copy(bmap: map->p[0]);
3258
3259	isl_map_free(map);
3260
3261	return bmap;
3262	error:
3263	obj.type->free(obj.v);
3264	return NULL;
3265	}
3266
3267	/* Read an isl_basic_set object from "s".
3268	*/
3269	__isl_give isl_basic_set *isl_stream_read_basic_set(__isl_keep isl_stream *s)
3270	{
3271	isl_basic_map *bmap;
3272	bmap = isl_stream_read_basic_map(s);
3273	if (!bmap)
3274	return NULL;
3275	if (!isl_basic_map_may_be_set(bmap))
3276	isl_die(s->ctx, isl_error_invalid,
3277	"input is not a set", goto error);
3278	return isl_basic_map_range(bmap);
3279	error:
3280	isl_basic_map_free(bmap);
3281	return NULL;
3282	}
3283
3284	__isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
3285	FILE *input)
3286	{
3287	struct isl_basic_map *bmap;
3288	isl_stream *s = isl_stream_new_file(ctx, file: input);
3289	if (!s)
3290	return NULL;
3291	bmap = isl_stream_read_basic_map(s);
3292	isl_stream_free(s);
3293	return bmap;
3294	}
3295
3296	__isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
3297	FILE *input)
3298	{
3299	isl_basic_set *bset;
3300	isl_stream *s = isl_stream_new_file(ctx, file: input);
3301	if (!s)
3302	return NULL;
3303	bset = isl_stream_read_basic_set(s);
3304	isl_stream_free(s);
3305	return bset;
3306	}
3307
3308	#undef TYPE_BASE
3309	#define TYPE_BASE basic_map
3310	#include "isl_read_from_str_templ.c"
3311
3312	#undef TYPE_BASE
3313	#define TYPE_BASE basic_set
3314	#include "isl_read_from_str_templ.c"
3315
3316	__isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
3317	FILE *input)
3318	{
3319	struct isl_map *map;
3320	isl_stream *s = isl_stream_new_file(ctx, file: input);
3321	if (!s)
3322	return NULL;
3323	map = isl_stream_read_map(s);
3324	isl_stream_free(s);
3325	return map;
3326	}
3327
3328	#undef TYPE_BASE
3329	#define TYPE_BASE map
3330	#include "isl_read_from_str_templ.c"
3331
3332	__isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
3333	FILE *input)
3334	{
3335	isl_set *set;
3336	isl_stream *s = isl_stream_new_file(ctx, file: input);
3337	if (!s)
3338	return NULL;
3339	set = isl_stream_read_set(s);
3340	isl_stream_free(s);
3341	return set;
3342	}
3343
3344	#undef TYPE_BASE
3345	#define TYPE_BASE set
3346	#include "isl_read_from_str_templ.c"
3347
3348	__isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
3349	FILE *input)
3350	{
3351	isl_union_map *umap;
3352	isl_stream *s = isl_stream_new_file(ctx, file: input);
3353	if (!s)
3354	return NULL;
3355	umap = isl_stream_read_union_map(s);
3356	isl_stream_free(s);
3357	return umap;
3358	}
3359
3360	#undef TYPE_BASE
3361	#define TYPE_BASE union_map
3362	#include "isl_read_from_str_templ.c"
3363
3364	__isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
3365	FILE *input)
3366	{
3367	isl_union_set *uset;
3368	isl_stream *s = isl_stream_new_file(ctx, file: input);
3369	if (!s)
3370	return NULL;
3371	uset = isl_stream_read_union_set(s);
3372	isl_stream_free(s);
3373	return uset;
3374	}
3375
3376	#undef TYPE_BASE
3377	#define TYPE_BASE union_set
3378	#include "isl_read_from_str_templ.c"
3379
3380	static __isl_give isl_vec *isl_vec_read_polylib(__isl_keep isl_stream *s)
3381	{
3382	struct isl_vec *vec = NULL;
3383	struct isl_token *tok;
3384	unsigned size;
3385	int j;
3386
3387	tok = isl_stream_next_token(s);
3388	if (!tok || tok->type != ISL_TOKEN_VALUE) {
3389	isl_stream_error(s, tok, msg: "expecting vector length");
3390	goto error;
3391	}
3392
3393	size = isl_int_get_si(tok->u.v);
3394	isl_token_free(tok);
3395
3396	vec = isl_vec_alloc(ctx: s->ctx, size);
3397
3398	for (j = 0; j < size; ++j) {
3399	tok = next_signed_value(s, msg: "expecting constant value");
3400	if (!tok)
3401	goto error;
3402	isl_int_set(vec->el[j], tok->u.v);
3403	isl_token_free(tok);
3404	}
3405
3406	return vec;
3407	error:
3408	isl_token_free(tok);
3409	isl_vec_free(vec);
3410	return NULL;
3411	}
3412
3413	static __isl_give isl_vec *vec_read(__isl_keep isl_stream *s)
3414	{
3415	return isl_vec_read_polylib(s);
3416	}
3417
3418	__isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
3419	{
3420	isl_vec *v;
3421	isl_stream *s = isl_stream_new_file(ctx, file: input);
3422	if (!s)
3423	return NULL;
3424	v = vec_read(s);
3425	isl_stream_free(s);
3426	return v;
3427	}
3428
3429	__isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
3430	__isl_keep isl_stream *s)
3431	{
3432	struct isl_obj obj;
3433
3434	obj = obj_read(s);
3435	if (obj.v)
3436	isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
3437	goto error);
3438
3439	return obj.v;
3440	error:
3441	obj.type->free(obj.v);
3442	return NULL;
3443	}
3444
3445	#undef TYPE_BASE
3446	#define TYPE_BASE pw_qpolynomial
3447	#include "isl_read_from_str_templ.c"
3448
3449	__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
3450	FILE *input)
3451	{
3452	isl_pw_qpolynomial *pwqp;
3453	isl_stream *s = isl_stream_new_file(ctx, file: input);
3454	if (!s)
3455	return NULL;
3456	pwqp = isl_stream_read_pw_qpolynomial(s);
3457	isl_stream_free(s);
3458	return pwqp;
3459	}
3460
3461	/* Read an isl_pw_qpolynomial_fold from "s".
3462	* First read a generic object and
3463	* then check that it is an isl_pw_qpolynomial_fold.
3464	*/
3465	__isl_give isl_pw_qpolynomial_fold *isl_stream_read_pw_qpolynomial_fold(
3466	__isl_keep isl_stream *s)
3467	{
3468	struct isl_obj obj;
3469
3470	obj = obj_read(s);
3471	if (obj.v && obj.type != isl_obj_pw_qpolynomial_fold)
3472	isl_die(s->ctx, isl_error_invalid, "invalid input", goto error);
3473
3474	return obj.v;
3475	error:
3476	obj.type->free(obj.v);
3477	return NULL;
3478	}
3479
3480	#undef TYPE_BASE
3481	#define TYPE_BASE pw_qpolynomial_fold
3482	#include "isl_read_from_str_templ.c"
3483
3484	/* Is the next token an identifier not in "v"?
3485	*/
3486	static int next_is_fresh_ident(__isl_keep isl_stream *s, struct vars *v)
3487	{
3488	int n = v->n;
3489	int fresh;
3490	struct isl_token *tok;
3491
3492	tok = isl_stream_next_token(s);
3493	if (!tok)
3494	return 0;
3495	fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, s: tok->u.s, len: -1) >= n;
3496	isl_stream_push_token(s, tok);
3497
3498	vars_drop(v, n: v->n - n);
3499
3500	return fresh;
3501	}
3502
3503	/* First read the domain of the affine expression, which may be
3504	* a parameter space or a set.
3505	* The tricky part is that we don't know if the domain is a set or not,
3506	* so when we are trying to read the domain, we may actually be reading
3507	* the affine expression itself (defined on a parameter domains)
3508	* If the tuple we are reading is named, we assume it's the domain.
3509	* Also, if inside the tuple, the first thing we find is a nested tuple
3510	* or a new identifier, we again assume it's the domain.
3511	* Finally, if the tuple is empty, then it must be the domain
3512	* since it does not contain an affine expression.
3513	* Otherwise, we assume we are reading an affine expression.
3514	*/
3515	static __isl_give isl_set *read_aff_domain(__isl_keep isl_stream *s,
3516	__isl_take isl_set *dom, struct vars *v)
3517	{
3518	struct isl_token *tok, *tok2;
3519	int is_empty;
3520
3521	tok = isl_stream_next_token(s);
3522	if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
3523	isl_stream_push_token(s, tok);
3524	return read_map_tuple(s, map: dom, type: isl_dim_set, v, rational: 0, comma: 0);
3525	}
3526	if (!tok || tok->type != '[') {
3527	isl_stream_error(s, tok, msg: "expecting '['");
3528	goto error;
3529	}
3530	tok2 = isl_stream_next_token(s);
3531	is_empty = tok2 && tok2->type == ']';
3532	if (tok2)
3533	isl_stream_push_token(s, tok: tok2);
3534	if (is_empty || next_is_tuple(s) || next_is_fresh_ident(s, v)) {
3535	isl_stream_push_token(s, tok);
3536	dom = read_map_tuple(s, map: dom, type: isl_dim_set, v, rational: 0, comma: 0);
3537	} else
3538	isl_stream_push_token(s, tok);
3539
3540	return dom;
3541	error:
3542	if (tok)
3543	isl_stream_push_token(s, tok);
3544	isl_set_free(set: dom);
3545	return NULL;
3546	}
3547
3548	/* Read an affine expression from "s".
3549	*/
3550	__isl_give isl_aff *isl_stream_read_aff(__isl_keep isl_stream *s)
3551	{
3552	isl_aff *aff;
3553	isl_multi_aff *ma;
3554	isl_size dim;
3555
3556	ma = isl_stream_read_multi_aff(s);
3557	dim = isl_multi_aff_dim(multi: ma, type: isl_dim_out);
3558	if (dim < 0)
3559	goto error;
3560	if (dim != 1)
3561	isl_die(s->ctx, isl_error_invalid,
3562	"expecting single affine expression",
3563	goto error);
3564
3565	aff = isl_multi_aff_get_aff(multi: ma, pos: 0);
3566	isl_multi_aff_free(multi: ma);
3567	return aff;
3568	error:
3569	isl_multi_aff_free(multi: ma);
3570	return NULL;
3571	}
3572
3573	/* Read a piecewise affine expression from "s" with domain (space) "dom".
3574	*/
3575	static __isl_give isl_pw_aff *read_pw_aff_with_dom(__isl_keep isl_stream *s,
3576	__isl_take isl_set *dom, struct vars *v)
3577	{
3578	isl_pw_aff *pwaff = NULL;
3579
3580	if (!isl_set_is_params(set: dom) && isl_stream_eat(s, type: ISL_TOKEN_TO))
3581	goto error;
3582
3583	if (isl_stream_eat(s, type: '['))
3584	goto error;
3585
3586	pwaff = accept_affine(s, space: isl_set_get_space(set: dom), v);
3587
3588	if (isl_stream_eat(s, type: ']'))
3589	goto error;
3590
3591	dom = read_optional_formula(s, map: dom, v, rational: 0);
3592	pwaff = isl_pw_aff_intersect_domain(pa: pwaff, set: dom);
3593
3594	return pwaff;
3595	error:
3596	isl_set_free(set: dom);
3597	isl_pw_aff_free(pwaff);
3598	return NULL;
3599	}
3600
3601	/* Read an affine expression, together with optional constraints
3602	* on the domain from "s". "dom" represents the initial constraints
3603	* on the parameter domain.
3604	* "v" contains a description of the identifiers parsed so far.
3605	*/
3606	static __isl_give isl_pw_aff *read_conditional_aff(__isl_keep isl_stream *s,
3607	__isl_take isl_set *dom, struct vars *v)
3608	{
3609	isl_set *aff_dom;
3610	isl_pw_aff *pa;
3611	int n;
3612
3613	n = v->n;
3614	aff_dom = read_aff_domain(s, dom, v);
3615	pa = read_pw_aff_with_dom(s, dom: aff_dom, v);
3616	vars_drop(v, n: v->n - n);
3617
3618	return pa;
3619	}
3620
3621	#undef BASE
3622	#define BASE aff
3623	#include "isl_stream_read_pw_with_params_templ.c"
3624
3625	#undef TYPE_BASE
3626	#define TYPE_BASE aff
3627	#include "isl_read_from_str_templ.c"
3628
3629	#undef TYPE_BASE
3630	#define TYPE_BASE pw_aff
3631	#include "isl_stream_read_with_params_templ.c"
3632	#include "isl_read_from_str_templ.c"
3633
3634	/* Given that "pa" is the element at position "pos" of a tuple
3635	* returned by read_tuple, check that it does not involve any
3636	* output/set dimensions (appearing at the "n" positions starting at "first"),
3637	* remove those from the domain and replace the domain space
3638	* with "domain_space".
3639	*
3640	* In particular, the result of read_tuple is of the form
3641	* [input, output] -> [output], with anonymous domain.
3642	* The function read_tuple accepts tuples where some output or
3643	* set dimensions are defined in terms of other output or set dimensions
3644	* since this function is also used to read maps. As a special case,
3645	* read_tuple also accepts dimensions that are defined in terms of themselves
3646	* (i.e., that are not defined).
3647	* These cases are not allowed here.
3648	*/
3649	static __isl_give isl_pw_aff *separate_tuple_entry(__isl_take isl_pw_aff *pa,
3650	int pos, unsigned first, unsigned n, __isl_take isl_space *domain_space)
3651	{
3652	isl_bool involves;
3653
3654	involves = isl_pw_aff_involves_dims(pwaff: pa, type: isl_dim_in, first, n: pos + 1);
3655	if (involves < 0) {
3656	pa = isl_pw_aff_free(pwaff: pa);
3657	} else if (involves) {
3658	isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
3659	"not an affine expression",
3660	pa = isl_pw_aff_free(pa));
3661	}
3662	pa = isl_pw_aff_drop_dims(pwaff: pa, type: isl_dim_in, first, n);
3663	pa = isl_pw_aff_reset_domain_space(pwaff: pa, space: domain_space);
3664
3665	return pa;
3666	}
3667
3668	/* Set entry "pos" of "mpa" to the corresponding entry in "tuple",
3669	* as obtained from read_tuple().
3670	* The "n" output dimensions also appear among the input dimensions
3671	* at position "first".
3672	*
3673	* The entry is not allowed to depend on any (other) output dimensions.
3674	*/
3675	static __isl_give isl_multi_pw_aff *isl_multi_pw_aff_set_tuple_entry(
3676	__isl_take isl_multi_pw_aff *mpa, __isl_take isl_pw_aff *tuple_el,
3677	int pos, unsigned first, unsigned n)
3678	{
3679	isl_space *space;
3680	isl_pw_aff *pa;
3681
3682	space = isl_multi_pw_aff_get_domain_space(multi: mpa);
3683	pa = separate_tuple_entry(pa: tuple_el, pos, first, n, domain_space: space);
3684	return isl_multi_pw_aff_set_pw_aff(multi: mpa, pos, el: pa);
3685	}
3686
3687	#undef BASE
3688	#define BASE pw_aff
3689
3690	#include <isl_multi_from_tuple_templ.c>
3691
3692	/* Read a tuple of piecewise affine expressions,
3693	* including optional constraints on the domain from "s".
3694	* "dom" represents the initial constraints on the domain.
3695	*
3696	* The input format is similar to that of a map, except that any conditions
3697	* on the domains should be specified inside the tuple since each
3698	* piecewise affine expression may have a different domain.
3699	* However, additional, shared conditions can also be specified.
3700	* This is especially useful for setting the explicit domain
3701	* of a zero-dimensional isl_multi_pw_aff.
3702	*
3703	* The isl_multi_pw_aff may live in either a set or a map space.
3704	* First read the first tuple and check if it is followed by a "->".
3705	* If so, convert the tuple into the domain of the isl_multi_pw_aff and
3706	* read in the next tuple. This tuple (or the first tuple if it was
3707	* not followed by a "->") is then converted into an isl_multi_pw_aff
3708	* through a call to isl_multi_pw_aff_from_tuple.
3709	* The domain of the result is intersected with the domain.
3710	*
3711	* Note that the last tuple may introduce new identifiers,
3712	* but these cannot be referenced in the description of the domain.
3713	*/
3714	static __isl_give isl_multi_pw_aff *read_conditional_multi_pw_aff(
3715	__isl_keep isl_stream *s, __isl_take isl_set *dom, struct vars *v)
3716	{
3717	isl_multi_pw_aff *tuple;
3718	isl_multi_pw_aff *mpa;
3719	int n = v->n;
3720	int n_dom;
3721
3722	n_dom = v->n;
3723	tuple = read_tuple(s, v, rational: 0, comma: 0);
3724	if (!tuple)
3725	goto error;
3726	if (isl_stream_eat_if_available(s, type: ISL_TOKEN_TO)) {
3727	isl_map *map = map_from_tuple(tuple, map: dom, type: isl_dim_in, v, rational: 0);
3728	dom = isl_map_domain(bmap: map);
3729	n_dom = v->n;
3730	tuple = read_tuple(s, v, rational: 0, comma: 0);
3731	if (!tuple)
3732	goto error;
3733	}
3734	mpa = isl_multi_pw_aff_from_tuple(dom_space: isl_set_get_space(set: dom), tuple);
3735	if (!mpa)
3736	dom = isl_set_free(set: dom);
3737
3738	vars_drop(v, n: v->n - n_dom);
3739	dom = read_optional_formula(s, map: dom, v, rational: 0);
3740
3741	vars_drop(v, n: v->n - n);
3742
3743	mpa = isl_multi_pw_aff_intersect_domain(mpa, domain: dom);
3744
3745	return mpa;
3746	error:
3747	isl_set_free(set: dom);
3748	return NULL;
3749	}
3750
3751	/* Read a tuple of affine expressions, together with optional constraints
3752	* on the domain from "s". "dom" represents the initial constraints
3753	* on the domain.
3754	*
3755	* Read a tuple of piecewise affine expressions with optional constraints and
3756	* convert the result to an isl_pw_multi_aff on the shared domain.
3757	*/
3758	static __isl_give isl_pw_multi_aff *read_conditional_multi_aff(
3759	__isl_keep isl_stream *s, __isl_take isl_set *dom, struct vars *v)
3760	{
3761	isl_multi_pw_aff *mpa;
3762
3763	mpa = read_conditional_multi_pw_aff(s, dom, v);
3764	return isl_pw_multi_aff_from_multi_pw_aff(mpa);
3765	}
3766
3767	/* Read an isl_union_pw_multi_aff from "s" with parameter domain "dom".
3768	* "v" contains a description of the identifiers parsed so far.
3769	*
3770	* In particular, read a sequence
3771	* of zero or more tuples of affine expressions with optional conditions and
3772	* add them up.
3773	*/
3774	static __isl_give isl_union_pw_multi_aff *
3775	isl_stream_read_with_params_union_pw_multi_aff(__isl_keep isl_stream *s,
3776	__isl_keep isl_set *dom, struct vars *v)
3777	{
3778	isl_union_pw_multi_aff *upma;
3779
3780	upma = isl_union_pw_multi_aff_empty(space: isl_set_get_space(set: dom));
3781
3782	do {
3783	isl_pw_multi_aff *pma;
3784	isl_union_pw_multi_aff *upma2;
3785
3786	if (isl_stream_next_token_is(s, type: '}'))
3787	break;
3788
3789	pma = read_conditional_multi_aff(s, dom: isl_set_copy(set: dom), v);
3790	upma2 = isl_union_pw_multi_aff_from_pw_multi_aff(pma);
3791	upma = isl_union_pw_multi_aff_union_add(upma1: upma, upma2);
3792	if (!upma)
3793	return NULL;
3794	} while (isl_stream_eat_if_available(s, type: ';'));
3795
3796	return upma;
3797	}
3798
3799	#undef BASE
3800	#define BASE multi_aff
3801	#include "isl_stream_read_pw_with_params_templ.c"
3802
3803	#undef TYPE_BASE
3804	#define TYPE_BASE pw_multi_aff
3805	#include "isl_stream_read_with_params_templ.c"
3806	#include "isl_read_from_str_templ.c"
3807
3808	#undef TYPE_BASE
3809	#define TYPE_BASE union_pw_multi_aff
3810	#include "isl_stream_read_with_params_templ.c"
3811	#include "isl_read_from_str_templ.c"
3812
3813	#undef BASE
3814	#define BASE val
3815
3816	#include <isl_multi_read_no_explicit_domain_templ.c>
3817
3818	#undef BASE
3819	#define BASE id
3820
3821	#include <isl_multi_read_no_explicit_domain_templ.c>
3822
3823	/* Set entry "pos" of "ma" to the corresponding entry in "tuple",
3824	* as obtained from read_tuple().
3825	* The "n" output dimensions also appear among the input dimensions
3826	* at position "first".
3827	*
3828	* The entry is not allowed to depend on any (other) output dimensions.
3829	*/
3830	static __isl_give isl_multi_aff *isl_multi_aff_set_tuple_entry(
3831	__isl_take isl_multi_aff *ma, __isl_take isl_pw_aff *tuple_el,
3832	int pos, unsigned first, unsigned n)
3833	{
3834	isl_space *space;
3835	isl_pw_aff *pa;
3836	isl_aff *aff;
3837
3838	space = isl_multi_aff_get_domain_space(multi: ma);
3839	pa = separate_tuple_entry(pa: tuple_el, pos, first, n, domain_space: space);
3840	aff = isl_pw_aff_as_aff(pa);
3841	return isl_multi_aff_set_aff(multi: ma, pos, el: aff);
3842	}
3843
3844	#undef BASE
3845	#define BASE aff
3846
3847	#include <isl_multi_from_tuple_templ.c>
3848
3849	/* Read a multi-affine expression from "s".
3850	* If the multi-affine expression has a domain, then the tuple
3851	* representing this domain cannot involve any affine expressions.
3852	* The tuple representing the actual expressions needs to consist
3853	* of only affine expressions.
3854	*/
3855	__isl_give isl_multi_aff *isl_stream_read_multi_aff(__isl_keep isl_stream *s)
3856	{
3857	struct vars *v;
3858	isl_multi_pw_aff *tuple = NULL;
3859	isl_space *dom_space = NULL;
3860	isl_multi_aff *ma = NULL;
3861
3862	v = vars_new(ctx: s->ctx);
3863	if (!v)
3864	return NULL;
3865
3866	dom_space = read_params(s, v);
3867	if (!dom_space)
3868	goto error;
3869	if (isl_stream_eat(s, type: '{'))
3870	goto error;
3871
3872	tuple = read_tuple(s, v, rational: 0, comma: 0);
3873	if (!tuple)
3874	goto error;
3875	if (isl_stream_eat_if_available(s, type: ISL_TOKEN_TO)) {
3876	isl_space *space;
3877	isl_bool has_expr;
3878
3879	has_expr = tuple_has_expr(tuple);
3880	if (has_expr < 0)
3881	goto error;
3882	if (has_expr)
3883	isl_die(s->ctx, isl_error_invalid,
3884	"expecting universe domain", goto error);
3885	space = isl_space_range(space: isl_multi_pw_aff_get_space(multi: tuple));
3886	dom_space = isl_space_align_params(space1: space, space2: dom_space);
3887	isl_multi_pw_aff_free(multi: tuple);
3888	tuple = read_tuple(s, v, rational: 0, comma: 0);
3889	if (!tuple)
3890	goto error;
3891	}
3892
3893	if (isl_stream_eat(s, type: '}'))
3894	goto error;
3895
3896	ma = isl_multi_aff_from_tuple(dom_space, tuple);
3897
3898	vars_free(v);
3899	return ma;
3900	error:
3901	isl_multi_pw_aff_free(multi: tuple);
3902	vars_free(v);
3903	isl_space_free(space: dom_space);
3904	isl_multi_aff_free(multi: ma);
3905	return NULL;
3906	}
3907
3908	#undef TYPE_BASE
3909	#define TYPE_BASE multi_aff
3910	#include "isl_read_from_str_templ.c"
3911
3912	/* Read an isl_multi_pw_aff from "s" with parameter domain "dom"..
3913	* "v" contains a description of the identifiers parsed so far.
3914	*/
3915	static __isl_give isl_multi_pw_aff *isl_stream_read_with_params_multi_pw_aff(
3916	__isl_keep isl_stream *s, __isl_keep isl_set *dom, struct vars *v)
3917	{
3918	return read_conditional_multi_pw_aff(s, dom: isl_set_copy(set: dom), v);
3919	}
3920
3921	#undef TYPE_BASE
3922	#define TYPE_BASE multi_pw_aff
3923	#include "isl_stream_read_with_params_templ.c"
3924	#include "isl_read_from_str_templ.c"
3925
3926	/* Read the body of an isl_union_pw_aff from "s" with parameter domain "dom".
3927	*/
3928	static __isl_give isl_union_pw_aff *read_union_pw_aff_with_dom(
3929	__isl_keep isl_stream *s, __isl_take isl_set *dom, struct vars *v)
3930	{
3931	isl_pw_aff *pa;
3932	isl_union_pw_aff *upa = NULL;
3933	isl_set *aff_dom;
3934	int n;
3935
3936	n = v->n;
3937	aff_dom = read_aff_domain(s, dom: isl_set_copy(set: dom), v);
3938	pa = read_pw_aff_with_dom(s, dom: aff_dom, v);
3939	vars_drop(v, n: v->n - n);
3940
3941	upa = isl_union_pw_aff_from_pw_aff(pa);
3942
3943	while (isl_stream_eat_if_available(s, type: ';')) {
3944	isl_pw_aff *pa_i;
3945	isl_union_pw_aff *upa_i;
3946
3947	n = v->n;
3948	aff_dom = read_aff_domain(s, dom: isl_set_copy(set: dom), v);
3949	pa_i = read_pw_aff_with_dom(s, dom: aff_dom, v);
3950	vars_drop(v, n: v->n - n);
3951
3952	upa_i = isl_union_pw_aff_from_pw_aff(pa: pa_i);
3953	upa = isl_union_pw_aff_union_add(upa1: upa, upa2: upa_i);
3954	}
3955
3956	isl_set_free(set: dom);
3957	return upa;
3958	}
3959
3960	/* Read an isl_union_pw_aff from "s" with parameter domain "dom".
3961	* "v" contains a description of the identifiers parsed so far.
3962	*/
3963	static __isl_give isl_union_pw_aff *isl_stream_read_with_params_union_pw_aff(
3964	__isl_keep isl_stream *s, __isl_keep isl_set *dom, struct vars *v)
3965	{
3966	return read_union_pw_aff_with_dom(s, dom: isl_set_copy(set: dom), v);
3967	}
3968
3969	#undef TYPE_BASE
3970	#define TYPE_BASE union_pw_aff
3971	#include "isl_stream_read_with_params_templ.c"
3972	#include "isl_read_from_str_templ.c"
3973
3974	/* This function is called for each element in a tuple inside
3975	* isl_stream_read_multi_union_pw_aff.
3976	*
3977	* Read a '{', the union piecewise affine expression body and a '}' and
3978	* add the isl_union_pw_aff to *list.
3979	*/
3980	static __isl_give isl_space *read_union_pw_aff_el(__isl_keep isl_stream *s,
3981	struct vars *v, __isl_take isl_space *space, int rational, void *user)
3982	{
3983	isl_set *dom;
3984	isl_union_pw_aff *upa;
3985	isl_union_pw_aff_list **list = (isl_union_pw_aff_list **) user;
3986
3987	dom = isl_set_universe(space: isl_space_params(space: isl_space_copy(space)));
3988	if (isl_stream_eat(s, type: '{'))
3989	goto error;
3990	upa = read_union_pw_aff_with_dom(s, dom, v);
3991	*list = isl_union_pw_aff_list_add(list: *list, el: upa);
3992	if (isl_stream_eat(s, type: '}'))
3993	return isl_space_free(space);
3994	if (!*list)
3995	return isl_space_free(space);
3996	return space;
3997	error:
3998	isl_set_free(set: dom);
3999	return isl_space_free(space);
4000	}
4001
4002	/* Do the next tokens in "s" correspond to an empty tuple?
4003	* In particular, does the stream start with a '[', followed by a ']',
4004	* not followed by a "->"?
4005	*/
4006	static int next_is_empty_tuple(__isl_keep isl_stream *s)
4007	{
4008	struct isl_token *tok, *tok2, *tok3;
4009	int is_empty_tuple = 0;
4010
4011	tok = isl_stream_next_token(s);
4012	if (!tok)
4013	return 0;
4014	if (tok->type != '[') {
4015	isl_stream_push_token(s, tok);
4016	return 0;
4017	}
4018
4019	tok2 = isl_stream_next_token(s);
4020	if (tok2 && tok2->type == ']') {
4021	tok3 = isl_stream_next_token(s);
4022	is_empty_tuple = !tok || tok->type != ISL_TOKEN_TO;
4023	if (tok3)
4024	isl_stream_push_token(s, tok: tok3);
4025	}
4026	if (tok2)
4027	isl_stream_push_token(s, tok: tok2);
4028	isl_stream_push_token(s, tok);
4029
4030	return is_empty_tuple;
4031	}
4032
4033	/* Do the next tokens in "s" correspond to a tuple of parameters?
4034	* In particular, does the stream start with a '[' that is not
4035	* followed by a '{' or a nested tuple?
4036	*/
4037	static int next_is_param_tuple(__isl_keep isl_stream *s)
4038	{
4039	struct isl_token *tok, *tok2;
4040	int is_tuple;
4041
4042	tok = isl_stream_next_token(s);
4043	if (!tok)
4044	return 0;
4045	if (tok->type != '[' || next_is_tuple(s)) {
4046	isl_stream_push_token(s, tok);
4047	return 0;
4048	}
4049
4050	tok2 = isl_stream_next_token(s);
4051	is_tuple = tok2 && tok2->type != '{';
4052	if (tok2)
4053	isl_stream_push_token(s, tok: tok2);
4054	isl_stream_push_token(s, tok);
4055
4056	return is_tuple;
4057	}
4058
4059	/* Read the core of a body of an isl_multi_union_pw_aff from "s",
4060	* i.e., everything except the parameter specification and
4061	* without shared domain constraints.
4062	* "v" contains a description of the identifiers parsed so far.
4063	* The parameters, if any, are specified by "space".
4064	*
4065	* The body is of the form
4066	*
4067	* [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4068	*
4069	* Read the tuple, collecting the individual isl_union_pw_aff
4070	* elements in a list and construct the result from the tuple space and
4071	* the list.
4072	*/
4073	static __isl_give isl_multi_union_pw_aff *read_multi_union_pw_aff_body_core(
4074	__isl_keep isl_stream *s, struct vars *v, __isl_take isl_space *space)
4075	{
4076	isl_union_pw_aff_list *list;
4077	isl_multi_union_pw_aff *mupa;
4078
4079	list = isl_union_pw_aff_list_alloc(ctx: s->ctx, n: 0);
4080	space = read_tuple_space(s, v, space, rational: 1, comma: 0,
4081	read_el: &read_union_pw_aff_el, user: &list);
4082	mupa = isl_multi_union_pw_aff_from_union_pw_aff_list(space, list);
4083
4084	return mupa;
4085	}
4086
4087	/* Read the body of an isl_union_set from "s",
4088	* i.e., everything except the parameter specification.
4089	* "v" contains a description of the identifiers parsed so far.
4090	* The parameters, if any, are specified by "space".
4091	*
4092	* First read a generic disjunction of object bodies and then try and extract
4093	* an isl_union_set from that.
4094	*/
4095	static __isl_give isl_union_set *read_union_set_body(__isl_keep isl_stream *s,
4096	struct vars *v, __isl_take isl_space *space)
4097	{
4098	struct isl_obj obj = { isl_obj_set, NULL };
4099	isl_map *map;
4100
4101	map = isl_set_universe(space);
4102	if (isl_stream_eat(s, type: '{') < 0)
4103	goto error;
4104	obj = obj_read_disjuncts(s, v, map);
4105	if (isl_stream_eat(s, type: '}') < 0)
4106	goto error;
4107	isl_map_free(map);
4108
4109	return extract_union_set(ctx: s->ctx, obj);
4110	error:
4111	obj.type->free(obj.v);
4112	isl_map_free(map);
4113	return NULL;
4114	}
4115
4116	/* Read the body of an isl_multi_union_pw_aff from "s",
4117	* i.e., everything except the parameter specification.
4118	* "v" contains a description of the identifiers parsed so far.
4119	* The parameters, if any, are specified by "space".
4120	*
4121	* In particular, handle the special case with shared domain constraints.
4122	* These are specified as
4123	*
4124	* ([...] : ...)
4125	*
4126	* and are especially useful for setting the explicit domain
4127	* of a zero-dimensional isl_multi_union_pw_aff.
4128	* The core isl_multi_union_pw_aff body ([...]) is read by
4129	* read_multi_union_pw_aff_body_core.
4130	*/
4131	static __isl_give isl_multi_union_pw_aff *read_multi_union_pw_aff_body(
4132	__isl_keep isl_stream *s, struct vars *v, __isl_take isl_space *space)
4133	{
4134	isl_multi_union_pw_aff *mupa;
4135
4136	if (!isl_stream_next_token_is(s, type: '('))
4137	return read_multi_union_pw_aff_body_core(s, v, space);
4138
4139	if (isl_stream_eat(s, type: '(') < 0)
4140	goto error;
4141	mupa = read_multi_union_pw_aff_body_core(s, v, space: isl_space_copy(space));
4142	if (isl_stream_eat_if_available(s, type: ':')) {
4143	isl_union_set *dom;
4144
4145	dom = read_union_set_body(s, v, space);
4146	mupa = isl_multi_union_pw_aff_intersect_domain(mupa, uset: dom);
4147	} else {
4148	isl_space_free(space);
4149	}
4150	if (isl_stream_eat(s, type: ')') < 0)
4151	return isl_multi_union_pw_aff_free(multi: mupa);
4152
4153	return mupa;
4154	error:
4155	isl_space_free(space);
4156	return NULL;
4157	}
4158
4159	/* Read an isl_multi_union_pw_aff from "s".
4160	*
4161	* The input has the form
4162	*
4163	* [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4164	*
4165	* or
4166	*
4167	* [..] -> [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4168	*
4169	* Additionally, a shared domain may be specified as
4170	*
4171	* ([..] : ...)
4172	*
4173	* or
4174	*
4175	* [..] -> ([..] : ...)
4176	*
4177	* The first case is handled by the caller, the second case
4178	* is handled by read_multi_union_pw_aff_body.
4179	*
4180	* We first check for the special case of an empty tuple "[]".
4181	* Then we check if there are any parameters.
4182	* Finally, read the tuple and construct the result.
4183	*/
4184	static __isl_give isl_multi_union_pw_aff *read_multi_union_pw_aff_core(
4185	__isl_keep isl_stream *s)
4186	{
4187	struct vars *v;
4188	isl_set *dom = NULL;
4189	isl_space *space;
4190	isl_multi_union_pw_aff *mupa = NULL;
4191
4192	if (next_is_empty_tuple(s)) {
4193	if (isl_stream_eat(s, type: '['))
4194	return NULL;
4195	if (isl_stream_eat(s, type: ']'))
4196	return NULL;
4197	space = isl_space_set_alloc(ctx: s->ctx, nparam: 0, dim: 0);
4198	return isl_multi_union_pw_aff_zero(space);
4199	}
4200
4201	v = vars_new(ctx: s->ctx);
4202	if (!v)
4203	return NULL;
4204
4205	dom = isl_set_universe(space: isl_space_params_alloc(ctx: s->ctx, nparam: 0));
4206	if (next_is_param_tuple(s)) {
4207	dom = read_map_tuple(s, map: dom, type: isl_dim_param, v, rational: 1, comma: 0);
4208	if (isl_stream_eat(s, type: ISL_TOKEN_TO))
4209	goto error;
4210	}
4211	space = isl_set_get_space(set: dom);
4212	isl_set_free(set: dom);
4213	mupa = read_multi_union_pw_aff_body(s, v, space);
4214
4215	vars_free(v);
4216
4217	return mupa;
4218	error:
4219	vars_free(v);
4220	isl_set_free(set: dom);
4221	isl_multi_union_pw_aff_free(multi: mupa);
4222	return NULL;
4223	}
4224
4225	/* Read an isl_multi_union_pw_aff from "s".
4226	*
4227	* In particular, handle the special case with shared domain constraints.
4228	* These are specified as
4229	*
4230	* ([...] : ...)
4231	*
4232	* and are especially useful for setting the explicit domain
4233	* of a zero-dimensional isl_multi_union_pw_aff.
4234	* The core isl_multi_union_pw_aff ([...]) is read by
4235	* read_multi_union_pw_aff_core.
4236	*/
4237	__isl_give isl_multi_union_pw_aff *isl_stream_read_multi_union_pw_aff(
4238	__isl_keep isl_stream *s)
4239	{
4240	isl_multi_union_pw_aff *mupa;
4241
4242	if (!isl_stream_next_token_is(s, type: '('))
4243	return read_multi_union_pw_aff_core(s);
4244
4245	if (isl_stream_eat(s, type: '(') < 0)
4246	return NULL;
4247	mupa = read_multi_union_pw_aff_core(s);
4248	if (isl_stream_eat_if_available(s, type: ':')) {
4249	isl_union_set *dom;
4250
4251	dom = isl_stream_read_union_set(s);
4252	mupa = isl_multi_union_pw_aff_intersect_domain(mupa, uset: dom);
4253	}
4254	if (isl_stream_eat(s, type: ')') < 0)
4255	return isl_multi_union_pw_aff_free(multi: mupa);
4256	return mupa;
4257	}
4258
4259	#undef TYPE_BASE
4260	#define TYPE_BASE multi_union_pw_aff
4261	#include "isl_read_from_str_templ.c"
4262
4263	__isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial(
4264	__isl_keep isl_stream *s)
4265	{
4266	struct isl_obj obj;
4267
4268	obj = obj_read(s);
4269	if (obj.type == isl_obj_pw_qpolynomial) {
4270	obj.type = isl_obj_union_pw_qpolynomial;
4271	obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(pwqp: obj.v);
4272	}
4273	if (obj.v)
4274	isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial,
4275	goto error);
4276
4277	return obj.v;
4278	error:
4279	obj.type->free(obj.v);
4280	return NULL;
4281	}
4282
4283	#undef TYPE_BASE
4284	#define TYPE_BASE union_pw_qpolynomial
4285	#include "isl_read_from_str_templ.c"
4286