brintos / llvm-project-archived public Read only

1/*2 * Copyright 2008-2009 Katholieke Universiteit Leuven3 * Copyright 2010      INRIA Saclay4 * Copyright 2012-2013 Ecole Normale Superieure5 * Copyright 2019,2022 Cerebras Systems6 *7 * Use of this software is governed by the MIT license8 *9 * Written by Sven Verdoolaege, K.U.Leuven, Departement10 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium11 * 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, France14 * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA15 */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 36struct variable {37	char    	    	*name;38	int	     		 pos;39	struct variable		*next;40};41 42struct vars {43	struct isl_ctx	*ctx;44	int		 n;45	struct variable	*v;46};47 48static 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 60static void variable_free(struct variable *var)61{62	while (var) {63		struct variable *next = var->next;64		free(var->name);65		free(var);66		var = next;67	}68}69 70static void vars_free(struct vars *v)71{72	if (!v)73		return;74	variable_free(v->v);75	free(v);76}77 78static 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(var->name);91		free(var);92		var = next;93	}94	v->v = var;95}96 97static 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(name);105	var->name[len] = '\0';106	var->pos = pos;107	var->next = v->v;108	return var;109error:110	variable_free(v->v);111	return NULL;112}113 114static 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);121	for (q = v->v; q; q = q->next) {122		if (strncmp(q->name, s, 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, s, len, v->n);130		if (!v->v)131			return -1;132		v->n++;133	}134	return pos;135}136 137static int vars_add_anon(struct vars *v)138{139	v->v = variable_new(v, "", 0, 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 */152static 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, '^'))160		return tok;161	tok2 = isl_stream_next_token(s);162	if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {163		isl_stream_error(s, tok2, "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(tok2);170	return tok;171error:172	isl_token_free(tok);173	isl_token_free(tok2);174	return NULL;175}176 177/* Read an isl_val from "s".178 *179 * The following token sequences are recognized180 *181 *	"infty"		->	infty182 *	"-" "infty"	->	-infty183 *	"NaN"		->	NaN184 *	n "/" d		->	n/d185 *	"-" n "/" d	->	-n/d186 *	v		->	v187 *	"-" v		->	-v188 *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, '-'))199		sign = -1;200	tok = next_token(s);201	if (!tok) {202		isl_stream_error(s, NULL, "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(s->ctx);209		else210			return isl_val_neginfty(s->ctx);211	}212	if (sign > 0 && tok->type == ISL_TOKEN_NAN) {213		isl_token_free(tok);214		return isl_val_nan(s->ctx);215	}216	if (tok->type != ISL_TOKEN_VALUE) {217		isl_stream_error(s, tok, "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, '/')) {225		tok2 = next_token(s);226		if (!tok2) {227			isl_stream_error(s, NULL, "unexpected EOF");228			goto error;229		}230		if (tok2->type != ISL_TOKEN_VALUE) {231			isl_stream_error(s, tok2, "expecting value");232			goto error;233		}234		val = isl_val_rat_from_isl_int(s->ctx, tok->u.v, tok2->u.v);235		val = isl_val_normalize(val);236	} else {237		val = isl_val_int_from_isl_int(s->ctx, tok->u.v);238	}239 240	isl_token_free(tok);241	isl_token_free(tok2);242	return val;243error:244	isl_token_free(tok);245	isl_token_free(tok2);246	return NULL;247}248 249#undef TYPE_BASE250#define TYPE_BASE	val251#include "isl_read_from_str_templ.c"252 253static 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, '-'))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, "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, '*'))270		return accept_cst_factor(s, f);271 272	return isl_stat_ok;273error:274	isl_token_free(tok);275	return isl_stat_error;276}277 278/* Given an affine expression aff, return an affine expression279 * for aff % d, with d the next token on the stream, which is280 * assumed to be a constant.281 *282 * We introduce an integer division q = [aff/d] and the result283 * is set to aff - d q.284 */285static __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, "expecting constant value");294		goto error;295	}296 297	q = isl_pw_aff_copy(aff);298	q = isl_pw_aff_scale_down(q, tok->u.v);299	q = isl_pw_aff_floor(q);300	q = isl_pw_aff_scale(q, tok->u.v);301 302	aff = isl_pw_aff_sub(aff, q);303 304	isl_token_free(tok);305	return aff;306error:307	isl_pw_aff_free(aff);308	isl_token_free(tok);309	return NULL;310}311 312static __isl_give isl_pw_aff *accept_affine(__isl_keep isl_stream *s,313	__isl_take isl_space *space, struct vars *v);314static __isl_give isl_pw_aff_list *accept_affine_list(__isl_keep isl_stream *s,315	__isl_take isl_space *space, struct vars *v);316 317static __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, '('))331		goto error;332 333	list = accept_affine_list(s, isl_space_copy(space), v);334	if (!list)335		goto error;336 337	if (isl_stream_eat(s, ')'))338		goto error;339 340	isl_space_free(space);341	return min ? isl_pw_aff_list_min(list) : isl_pw_aff_list_max(list);342error: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 */350static __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, "expecting denominator");358		isl_token_free(tok);359		return isl_pw_aff_free(pa);360	}361 362	pa = isl_pw_aff_scale_down(pa,  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 */372static 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, '-'))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 */394static struct isl_token *next_signed_value(__isl_keep isl_stream *s, char *msg)395{396	return next_signed_value_fn(s, &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 */403static 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				    &isl_stream_next_token_on_same_line, msg);408}409 410/* Is "tok" the start of an integer division?411 */412static 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 form432 *433 *	[<affine expression>]434 *	floor(<affine expression>)435 *	ceil(<affine expression>)436 *	floord(<affine expression>,<denominator>)437 *	ceild(<affine expression>,<denominator>)438 */439static __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, ISL_TOKEN_FLOORD))448		extra = f = 1;449	else if (isl_stream_eat_if_available(s, ISL_TOKEN_CEILD))450		extra = c = 1;451	else if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOOR))452		f = 1;453	else if (isl_stream_eat_if_available(s, ISL_TOKEN_CEIL))454		c = 1;455	if (f || c) {456		if (isl_stream_eat(s, '('))457			goto error;458	} else {459		if (isl_stream_eat(s, '['))460			goto error;461	}462 463	pwaff = accept_affine(s, isl_space_copy(space), v);464 465	if (extra) {466		if (isl_stream_eat(s, ','))467			goto error;468 469		pwaff = pw_aff_div_by_cst(s, pwaff);470	}471 472	if (c)473		pwaff = isl_pw_aff_ceil(pwaff);474	else475		pwaff = isl_pw_aff_floor(pwaff);476 477	if (f || c) {478		if (isl_stream_eat(s, ')'))479			goto error;480	} else {481		if (isl_stream_eat(s, ']'))482			goto error;483	}484 485	isl_space_free(space);486	return pwaff;487error:488	isl_space_free(space);489	isl_pw_aff_free(pwaff);490	return NULL;491}492 493static __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, "unexpected EOF");502		goto error;503	}504 505	if (tok->type == ISL_TOKEN_AFF) {506		res = isl_pw_aff_copy(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, tok->u.s, -1);511		isl_aff *aff;512 513		if (pos < 0)514			goto error;515		if (pos >= n) {516			vars_drop(v, v->n - n);517			isl_stream_error(s, tok, "unknown identifier");518			goto error;519		}520 521		aff = isl_aff_zero_on_domain(isl_local_space_from_space(isl_space_copy(space)));522		if (!aff)523			goto error;524		aff->v = isl_vec_set_element_si(aff->v, 2 + pos, 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, '*') ||531		    isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {532			if (isl_stream_eat_if_available(s, '-'))533				isl_int_neg(tok->u.v, tok->u.v);534			res = accept_affine_factor(s, isl_space_copy(space), v);535			res = isl_pw_aff_scale(res, tok->u.v);536		} else {537			isl_local_space *ls;538			isl_aff *aff;539			ls = isl_local_space_from_space(isl_space_copy(space));540			aff = isl_aff_zero_on_domain(ls);541			aff = isl_aff_add_constant(aff, 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, isl_space_copy(space), v);549		if (!res)550			goto error;551		if (isl_stream_eat(s, ')'))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, 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, isl_space_copy(space), v);561	} else {562		isl_stream_error(s, tok, "expecting factor");563		goto error;564	}565	if (isl_stream_eat_if_available(s, '%') ||566	    isl_stream_eat_if_available(s, ISL_TOKEN_MOD)) {567		isl_space_free(space);568		return affine_mod(s, v, res);569	}570	if (isl_stream_eat_if_available(s, '*')) {571		isl_int f;572		isl_int_init(f);573		isl_int_set_si(f, 1);574		if (accept_cst_factor(s, &f) < 0) {575			isl_int_clear(f);576			goto error2;577		}578		res = isl_pw_aff_scale(res, f);579		isl_int_clear(f);580	}581	if (isl_stream_eat_if_available(s, '/'))582		res = pw_aff_div_by_cst(s, res);583	if (isl_stream_eat_if_available(s, ISL_TOKEN_INT_DIV))584		res = isl_pw_aff_floor(pw_aff_div_by_cst(s, res));585 586	isl_space_free(space);587	return res;588error:589	isl_token_free(tok);590error2:591	isl_pw_aff_free(res);592	isl_space_free(space);593	return NULL;594}595 596/* Return a piecewise affine expression defined on the specified domain597 * that represents NaN.598 */599static __isl_give isl_pw_aff *nan_on_domain(__isl_keep isl_space *space)600{601	return isl_pw_aff_nan_on_domain_space(isl_space_copy(space));602}603 604static __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(isl_space_copy(space));614	res = isl_pw_aff_from_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, "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						    isl_space_copy(space), v);643			if (op * sign < 0)644				res = isl_pw_aff_sub(res, term);645			else646				res = isl_pw_aff_add(res, term);647			if (!res)648				goto error;649		} else if (tok->type == ISL_TOKEN_NAN) {650			res = isl_pw_aff_add(res, nan_on_domain(space));651		} else {652			isl_stream_error(s, tok, "unexpected isl_token");653			isl_stream_push_token(s, tok);654			isl_pw_aff_free(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;677error:678	isl_space_free(space);679	isl_token_free(tok);680	isl_pw_aff_free(res);681	return NULL;682}683 684/* Is "type" the type of a comparison operator between lists685 * of affine expressions?686 */687static 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 700static int is_comparator(struct isl_token *tok)701{702	if (!tok)703		return 0;704	if (is_list_comparator_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 720static __isl_give isl_map *read_formula(__isl_keep isl_stream *s,721	struct vars *v, __isl_take isl_map *map, int rational);722static __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 */727static __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, '?'))737		goto error;738 739	space = isl_space_wrap(isl_map_get_space(cond));740	pwaff1 = accept_extended_affine(s, space, v, rational);741	if (!pwaff1)742		goto error;743 744	if (isl_stream_eat(s, ':'))745		goto error;746 747	space = isl_pw_aff_get_domain_space(pwaff1);748	pwaff2 = accept_extended_affine(s, space, v, rational);749	if (!pwaff2)750		goto error;751 752	pa_cond = isl_set_indicator_function(isl_map_wrap(cond));753	return isl_pw_aff_cond(pa_cond, pwaff1, pwaff2);754error:755	isl_map_free(cond);756	isl_pw_aff_free(pwaff1);757	isl_pw_aff_free(pwaff2);758	return NULL;759}760 761/* Set *line and *col to those of the next token, if any.762 */763static 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 given777 * line and column.778 */779static 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(s->ctx, line, col, 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;792error:793	isl_pw_aff_free(pa);794	return isl_stat_error;795}796 797/* Is the next token a comparison operator?798 */799static 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 first818 * argument of a ternary operator and try to parse that.819 */820static __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, &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(isl_space_unwrap(space));839 840	if (push_aff(s, line, col, pwaff) < 0)841		cond = isl_map_free(cond);842	if (!cond)843		return NULL;844 845	cond = read_formula(s, v, cond, rational);846 847	return accept_ternary(s, cond, v, rational);848}849 850static __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, isl_dim_param);860	else {861		pos = isl_map_dim(map, isl_dim_in);862		if (type == isl_dim_out) {863			isl_size n_out = isl_map_dim(map, 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, isl_space_wrap(isl_map_get_space(map)),875					v, rational);876	def_map = isl_map_from_pw_aff(def);877	def_map = isl_map_equate(def_map, type, pos, isl_dim_out, 0);878	def_map = isl_set_unwrap(isl_map_domain(def_map));879 880	map = isl_map_intersect(map, def_map);881 882	return map;883}884 885static __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, isl_space_copy(space), v);893	list = isl_pw_aff_list_from_pw_aff(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, "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, isl_space_copy(space), v);910		list = isl_pw_aff_list_concat(list,911				isl_pw_aff_list_from_pw_aff(pwaff));912		if (!list)913			goto error;914	}915 916	isl_space_free(space);917	return list;918error:919	isl_space_free(space);920	isl_pw_aff_list_free(list);921	return NULL;922}923 924static __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, tok->u.s, -1);937		if (p < 0)938			goto error;939		if (p < n) {940			isl_stream_error(s, tok, "expecting unique identifier");941			goto error;942		}943 944		map = isl_map_add_dims(map, isl_dim_out, 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, 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;963error:964	isl_token_free(tok);965	isl_map_free(map);966	return NULL;967}968 969static 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, '[');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 */995static int next_is_end_tuple_element(__isl_keep isl_stream *s)996{997	return isl_stream_next_token_is(s, ',') ||998	    isl_stream_next_token_is(s, ']');999}1000 1001/* Is the next token one that necessarily forms the start of a condition?1002 */1003static int next_is_condition_start(__isl_keep isl_stream *s)1004{1005	return isl_stream_next_token_is(s, ISL_TOKEN_EXISTS) ||1006	    isl_stream_next_token_is(s, ISL_TOKEN_NOT) ||1007	    isl_stream_next_token_is(s, ISL_TOKEN_TRUE) ||1008	    isl_stream_next_token_is(s, ISL_TOKEN_FALSE) ||1009	    isl_stream_next_token_is(s, 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 depends1015 * on itself.  "i" is the position of the expression in a sequence1016 * of "n" expressions.  The final dimensions of "pa" correspond to1017 * these "n" expressions.1018 */1019static 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(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 defined1037 * in terms of earlier dimensions?1038 */1039static 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(tuple, 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(tuple, i);1051		has_expr = pw_aff_is_expr(pa, i, n);1052		isl_pw_aff_free(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 once1062 * to distinguish the occurrences.  Here, we remove those primes from "name"1063 * before setting the name of the dimension.1064 */1065static __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(name, '\'');1074	if (prime)1075		*prime = '\0';1076	space = isl_space_set_dim_name(space, 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 */1086static __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, isl_dim_out);1092	if (pos < 0)1093		return isl_space_free(space);1094	return space_set_dim_name(space, 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 */1100static __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(isl_local_space_from_space(space));1106	aff = isl_aff_add_coefficient_si(aff, isl_dim_in, v->n - 1, 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 construct1114 *1115 *	D[..., i] -> i.1116 */1117static __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(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 form1129 *1130 *	D[..., i] -> i : C1131 *1132 * with D also the domains space of "lower' and "C" some constraints.1133 *1134 * Return the expression1135 *1136 *	D[..., i] -> i : C and i >= lower1137 */1138static __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(isl_pw_aff_copy(range_pa), lower);1144	return isl_pw_aff_intersect_domain(range_pa, 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 form1150 *1151 *	D[..., i] -> i : C1152 *1153 * with D also the domains space of "upper' and "C" some constraints.1154 *1155 * Return the expression1156 *1157 *	D[..., i] -> i : C and i <= upper1158 */1159static __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(isl_pw_aff_copy(range_pa), upper);1165	return isl_pw_aff_intersect_domain(range_pa, range);1166}1167 1168/* Construct a piecewise affine expression corresponding1169 * 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 expression1173 *1174 *	D[..., i] -> i,1175 *1176 * impose lower bound "pa" and return1177 *1178 *	D[..., i] -> i : i >= pa1179 */1180static __isl_give isl_pw_aff *construct_lower(__isl_take isl_pw_aff *pa,1181	struct vars *v)1182{1183	return set_lower(init_range(pa, v), pa);1184}1185 1186/* Construct a piecewise affine expression corresponding1187 * 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 expression1191 *1192 *	D[..., i] -> i,1193 *1194 * impose lower bound "pa" and return1195 *1196 *	D[..., i] -> i : i <= pa1197 */1198static __isl_give isl_pw_aff *construct_upper(__isl_take isl_pw_aff *pa,1199	struct vars *v)1200{1201	return set_upper(init_range(pa, v), pa);1202}1203 1204/* Construct a piecewise affine expression corresponding1205 * 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 expression1209 *1210 *	D[..., i] -> i,1211 *1212 * impose lower bound "pa" and upper bound "pa2" and return1213 *1214 *	D[..., i] -> i : pa <= i <= pa21215 */1216static __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(set_lower(init_range(pa, v), pa), pa2);1220}1221 1222static 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 expression1232 * then consider the two expressions as endpoints of a range of values and1233 * return a piecewise affine expression that takes values in that range.1234 * Note that an affine expression followed by a comparison operator1235 * 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 bound1238 * and return a piecewise affine expression that takes values in that range.1239 */1240static __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(pa);1248	map = isl_map_universe(isl_space_from_domain(dom_space));1249 1250	if (isl_stream_next_token_is(s, '('))1251		if (resolve_paren_expr(s, v, 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, &col);1263		space = isl_space_wrap(isl_map_get_space(map));1264		pa2 = accept_affine(s, space, v);1265		if (rational)1266			pa2 = isl_pw_aff_set_rational(pa2);1267		if (!next_is_comparator(s)) {1268			isl_map_free(map);1269			pa2 = isl_pw_aff_domain_factor_domain(pa2);1270			return construct_range(pa, pa2, v);1271		}1272		if (push_aff(s, line, col, pa2) < 0)1273			goto error;1274	}1275 1276	map = read_formula(s, v, map, rational);1277	pa = isl_pw_aff_intersect_domain(pa, isl_map_domain(map));1278 1279	return pa;1280error:1281	isl_map_free(map);1282	isl_pw_aff_free(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 form1289 *1290 *	aff1 : condition1; aff2 : conditions2; ...1291 *1292 * or one of1293 *1294 *	aff :1295 *	aff1 : aff21296 *	: aff1297 *	:1298 *1299 * or simply1300 *1301 *	aff1302 *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 be1306 * ":" or ": aff2", depending on whether anything follows the colon1307 * inside the tuple element.1308 * The first is considered to represent an arbitrary value.1309 * The second is considered to represent a range of values1310 * 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/or1314 * around the entire piecewise affine expression.1315 * We therefore remove the opening parenthesis (if any) from the stream1316 * in case the closing parenthesis follows the colon, but if the closing1317 * parenthesis is the first thing in the stream after the parsed affine1318 * expression, we push the parsed expression onto the stream and parse1319 * again in case the parentheses enclose some subexpression of "aff1".1320 */1321static __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, ':')) {1328		if (next_is_end_tuple_element(s))1329			return identity_tuple_el_on_space(space, v);1330		else1331			return construct_upper(accept_affine(s, space, v), v);1332	}1333 1334	res_space = isl_space_from_domain(isl_space_copy(space));1335	res_space = isl_space_add_dims(res_space, isl_dim_out, 1);1336	res = isl_pw_aff_empty(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, &col);1343		seen_paren = isl_stream_eat_if_available(s, '(');1344		if (seen_paren)1345			pa = accept_piecewise_affine(s, isl_space_copy(space),1346							v, rational);1347		else1348			pa = accept_extended_affine(s, isl_space_copy(space),1349							v, rational);1350		if (seen_paren && isl_stream_eat_if_available(s, ')')) {1351			seen_paren = 0;1352			if (push_aff(s, line, col, pa) < 0)1353				goto error;1354			pa = accept_extended_affine(s, isl_space_copy(space),1355							v, rational);1356		}1357		if (pa && isl_stream_eat_if_available(s, ':'))1358			pa = update_piecewise_affine_colon(pa, s, v, rational);1359 1360		res = isl_pw_aff_union_add(res, pa);1361 1362		if (!res || (seen_paren && isl_stream_eat(s, ')')))1363			goto error;1364	} while (isl_stream_eat_if_available(s, ';'));1365 1366	isl_space_free(space);1367 1368	return res;1369error:1370	isl_space_free(space);1371	return isl_pw_aff_free(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_aff1378 * to have an anonymous space.  We therefore adjust the space1379 * of the isl_pw_aff before returning it.1380 */1381static __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(isl_space_alloc(s->ctx, 0, v->n, 0));1388 1389	def = accept_piecewise_affine(s, space, v, rational);1390	def = isl_pw_aff_domain_factor_domain(def);1391 1392	return def;1393}1394 1395/* Read a list of tuple elements by calling "read_el" on each of them and1396 * return a space with the same number of set dimensions derived from1397 * 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 */1401static __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, ']'))1414		return space;1415 1416	for (;;) {1417		struct isl_token *tok;1418 1419		space = isl_space_add_dims(space, isl_dim_set, 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, '[')) {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 */1445static __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(tok->u.s);1461		isl_token_free(tok);1462		if (!name)1463			goto error;1464	} else1465		isl_stream_push_token(s, tok);1466	if (isl_stream_eat(s, '['))1467		goto error;1468	if (next_is_tuple(s)) {1469		isl_space *out;1470		res = read_tuple_space(s, v, isl_space_copy(space),1471					rational, comma, read_el, user);1472		if (isl_stream_eat(s, ISL_TOKEN_TO))1473			goto error;1474		out = read_tuple_space(s, v, isl_space_copy(space),1475					rational, comma, read_el, user);1476		res = isl_space_product(res, out);1477	} else1478		res = read_tuple_list(s, v, isl_space_copy(space),1479					rational, comma, read_el, user);1480	if (!res || isl_stream_eat(s, ']'))1481		goto error;1482 1483	if (name) {1484		res = isl_space_set_tuple_name(res, isl_dim_set, name);1485		free(name);1486	}1487 1488	isl_space_free(space);1489	return res;1490error:1491	free(name);1492	isl_space_free(res);1493	isl_space_free(space);1494	return NULL;1495}1496 1497/* Construct an isl_pw_aff defined on a space with v->n variables1498 * that is equal to the last of those variables.1499 */1500static __isl_give isl_pw_aff *identity_tuple_el(struct vars *v)1501{1502	isl_space *space;1503 1504	space = isl_space_set_alloc(v->ctx, 0, 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 defined1510 * over a space containing all variables in "v" defined so far.1511 * The isl_pw_aff expresses the new variable in terms of earlier variables1512 * if a definition is provided.  Otherwise, it is represented as being1513 * equal to itself.1514 * Add the isl_pw_aff to *list.1515 * If the new variable was named, then adjust "space" accordingly and1516 * return the updated space.1517 */1518static __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, "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, tok->u.s, -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, v->v->name);1547		isl_token_free(tok);1548		if (isl_stream_eat_if_available(s, '='))1549			pa = read_tuple_var_def(s, v, rational);1550		else1551			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, pa);1561	if (!*list)1562		return isl_space_free(space);1563 1564	return space;1565error: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 space1573 * 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 in1576 * the input, then the corresponding isl_pw_aff is set equal to one time1577 * 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 representing1581 * the variables defined so far.  We need to adjust the earlier1582 * elements to have as many variables in the domain as the final1583 * element in the list.1584 */1585static __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(v->ctx, 0);1594	list = isl_pw_aff_list_alloc(s->ctx, 0);1595	space = read_tuple_space(s, v, space, rational, comma,1596				&read_tuple_pw_aff_el, &list);1597	n = isl_space_dim(space, 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, i);1604		pa = isl_pw_aff_add_dims(pa, isl_dim_in, n - (i + 1));1605		list = isl_pw_aff_list_set_pw_aff(list, i, pa);1606	}1607 1608	space = isl_space_from_range(space);1609	space = isl_space_add_dims(space, isl_dim_in, 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 range1615 * space of this isl_multi_pw_aff.  Then, we add equalities based1616 * 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 */1619static __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(tuple, isl_dim_out);1629	if (!map || n < 0)1630		goto error;1631	ctx = isl_multi_pw_aff_get_ctx(tuple);1632	space = isl_space_range(isl_multi_pw_aff_get_space(tuple));1633	if (!space)1634		goto error;1635 1636	if (type == isl_dim_param) {1637		if (isl_space_has_tuple_name(space, 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, isl_dim_set, i))1647				isl_die(ctx, isl_error_invalid,1648					"parameters must be named",1649					goto error);1650			id = isl_space_get_dim_id(space, isl_dim_set, i);1651			map = isl_map_set_dim_id(map, isl_dim_param, i, id);1652		}1653	} else if (type == isl_dim_in) {1654		isl_set *set;1655 1656		set = isl_set_universe(isl_space_copy(space));1657		if (rational)1658			set = isl_set_set_rational(set);1659		set = isl_set_intersect_params(set, isl_map_params(map));1660		map = isl_map_from_domain(set);1661	} else {1662		isl_set *set;1663 1664		set = isl_set_universe(isl_space_copy(space));1665		if (rational)1666			set = isl_set_set_rational(set);1667		map = isl_map_from_domain_and_range(isl_map_domain(map), 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(tuple, i);1678		space = isl_pw_aff_get_domain_space(pa);1679		aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));1680		aff = isl_aff_add_coefficient_si(aff,1681						isl_dim_in, v->n - n + i, -1);1682		pa = isl_pw_aff_add(pa, isl_pw_aff_from_aff(aff));1683		if (rational)1684			pa = isl_pw_aff_set_rational(pa);1685		set = isl_pw_aff_zero_set(pa);1686		map_i = isl_map_from_range(set);1687		map_i = isl_map_reset_space(map_i, isl_map_get_space(map));1688		map = isl_map_intersect(map, map_i);1689	}1690 1691	isl_space_free(space);1692	isl_multi_pw_aff_free(tuple);1693	return map;1694error:1695	isl_space_free(space);1696	isl_multi_pw_aff_free(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 and1703 * then added to "map".1704 */1705static __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) and1719 * check that it does not involve any constraints.1720 * "v" contains a description of the identifiers parsed so far1721 * (of which there should not be any at this point) and is extended1722 * by this function.1723 */1724static __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(isl_space_params_alloc(s->ctx, 0));1730	if (next_is_tuple(s)) {1731		dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);1732		if (isl_stream_eat(s, ISL_TOKEN_TO))1733			return isl_set_free(dom);1734	}1735	if (!isl_set_plain_is_universe(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 far1746 * (of which there should not be any at this point) and is extended1747 * by this function.1748 */1749static __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" accordingly1764 * if the variable has a name.1765 */1766static __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, "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, tok->u.s, -1);1780		if (p < 0)1781			goto error;1782		if (p < n) {1783			isl_stream_error(s, tok, "expecting fresh identifier");1784			goto error;1785		}1786		space = space_set_last_dim_name(space, 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, "expecting identifier or '*'");1792		goto error;1793	}1794 1795	isl_token_free(tok);1796	return space;1797error: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 tuples1803 * read from "s".1804 * "v" contains a description of the identifiers parsed so far and is extended1805 * by this function.1806 */1807static __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, isl_space_copy(params), 1, 1,1813				&read_tuple_id, NULL);1814	if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {1815		ran = read_tuple_space(s, v, isl_space_copy(params), 1, 1,1816					&read_tuple_id, NULL);1817		space = isl_space_unwrap(isl_space_product(space, ran));1818	}1819	isl_space_free(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(s->ctx);1838	if (!v)1839		return NULL;1840	space = read_params(s, v);1841 1842	if (isl_stream_eat(s, '{'))1843		goto error;1844 1845	if (!isl_stream_eat_if_available(s, ':'))1846		space = read_space_tuples(s, v, space);1847 1848	if (isl_stream_eat(s, '}'))1849		goto error;1850 1851	vars_free(v);1852	return space;1853error:1854	vars_free(v);1855	isl_space_free(space);1856	return NULL;1857}1858 1859#undef TYPE_BASE1860#define TYPE_BASE	space1861#include "isl_read_from_str_templ.c"1862 1863/* Given two equal-length lists of piecewise affine expression with the space1864 * of "set" as domain, construct a set in the same space that expresses1865 * that "left" and "right" satisfy the comparison "type".1866 *1867 * A space is constructed of the same dimension as the number of elements1868 * in the two lists.  The comparison is then expressed in a map from1869 * this space to itself and wrapped into a set.  Finally the two lists1870 * 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 and1874 * 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 */1878static __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(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, isl_dim_out, n);1892	mpa1 = isl_multi_pw_aff_from_pw_aff_list(isl_space_copy(space), left);1893	mpa2 = isl_multi_pw_aff_from_pw_aff_list(isl_space_copy(space), right);1894	mpa1 = isl_multi_pw_aff_range_product(mpa1, mpa2);1895 1896	space = isl_space_range(space);1897	switch (type) {1898	case ISL_TOKEN_LEX_LT:1899		set = isl_map_wrap(isl_map_lex_lt(space));1900		break;1901	case ISL_TOKEN_LEX_GT:1902		set = isl_map_wrap(isl_map_lex_gt(space));1903		break;1904	case ISL_TOKEN_LEX_LE:1905		set = isl_map_wrap(isl_map_lex_le(space));1906		break;1907	case ISL_TOKEN_LEX_GE:1908		set = isl_map_wrap(isl_map_lex_ge(space));1909		break;1910	default:1911		isl_multi_pw_aff_free(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, mpa1);1917	return set;1918error:1919	isl_pw_aff_list_free(left);1920	isl_pw_aff_list_free(right);1921	return NULL;1922}1923 1924/* Construct constraints of the form1925 *1926 *	a op b1927 *1928 * where a is an element in "left", op is an operator of type "type" and1929 * b is an element in "right", add the constraints to "set" and return1930 * the result.1931 * "rational" is set if the constraints should be treated as1932 * a rational constraints.1933 *1934 * If "type" is the type of a comparison operator between lists1935 * of affine expressions, then a single (compound) constraint1936 * is constructed by list_cmp instead.1937 */1938static __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(left);1946	right = isl_pw_aff_list_copy(right);1947	if (rational) {1948		left = isl_pw_aff_list_set_rational(left);1949		right = isl_pw_aff_list_set_rational(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(left, right);1955	else if (type == ISL_TOKEN_GE)1956		cond = isl_pw_aff_list_ge_set(left, right);1957	else if (type == ISL_TOKEN_LT)1958		cond = isl_pw_aff_list_lt_set(left, right);1959	else if (type == ISL_TOKEN_GT)1960		cond = isl_pw_aff_list_gt_set(left, right);1961	else if (type == ISL_TOKEN_NE)1962		cond = isl_pw_aff_list_ne_set(left, right);1963	else1964		cond = isl_pw_aff_list_eq_set(left, right);1965 1966	return isl_set_intersect(set, 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 as1972 * a rational constraint.1973 * The constraint read from "s" may be applied to multiple pairs1974 * of affine expressions and may be chained.1975 * In particular, a list of affine expressions is read, followed1976 * by a comparison operator and another list of affine expressions.1977 * The comparison operator is then applied to each pair of elements1978 * 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 lists1981 * are required to have the same length.1982 * If the next token is another comparison operator, then another1983 * list of affine expressions is read and the process repeats.1984 *1985 * The processing is performed on a wrapped copy of "map" because1986 * an affine expression cannot have a binary relation as domain.1987 */1988static __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, 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, "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, isl_set_get_space(set), v);2012		n1 = isl_pw_aff_list_n_pw_aff(list1);2013		n2 = isl_pw_aff_list_n_pw_aff(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					"list arguments not of same size");2019			goto error;2020		}2021 2022		set = construct_constraints(set, type, list1, list2, rational);2023		isl_pw_aff_list_free(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(list1);2033 2034	return isl_set_unwrap(set);2035error:2036	isl_pw_aff_list_free(list1);2037	isl_pw_aff_list_free(list2);2038	isl_set_free(set);2039	return NULL;2040}2041 2042static __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, '(');2047 2048	map = isl_map_from_domain(isl_map_wrap(map));2049	map = read_defined_var_list(s, v, map, rational);2050 2051	if (isl_stream_eat(s, ':'))2052		goto error;2053 2054	map = read_formula(s, v, map, rational);2055	map = isl_set_unwrap(isl_map_domain(map));2056 2057	vars_drop(v, v->n - n);2058	if (seen_paren && isl_stream_eat(s, ')'))2059		goto error;2060 2061	return map;2062error:2063	isl_map_free(map);2064	return NULL;2065}2066 2067/* Parse an expression between parentheses and push the result2068 * back on the stream.2069 *2070 * The parsed expression may be either an affine expression2071 * or a condition.  The first type is pushed onto the stream2072 * 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 push2077 * that onto the stream.  If the affine expression covers the2078 * entire expression between parentheses, we return.2079 * Otherwise, we assume that the affine expression is the2080 * start of a condition and continue parsing.2081 */2082static 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, '('))2095		if (resolve_paren_expr(s, v, 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, ')'))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, tok2);2114 2115	pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v);2116	if (!pwaff)2117		goto error;2118 2119	has_paren = isl_stream_eat_if_available(s, ')');2120 2121	if (push_aff(s, line, col, 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, ')'))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;2139error:2140	isl_token_free(tok);2141	isl_map_free(map);2142	return -1;2143}2144 2145static __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, '('))2149		if (resolve_paren_expr(s, v, isl_map_copy(map), rational))2150			goto error;2151 2152	if (isl_stream_next_token_is(s, 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(tok->u.map);2159		isl_token_free(tok);2160		return map;2161	}2162 2163	if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))2164		return read_exists(s, v, map, rational);2165 2166	if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))2167		return map;2168 2169	if (isl_stream_eat_if_available(s, 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);2176error:2177	isl_map_free(map);2178	return NULL;2179}2180 2181static __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, ISL_TOKEN_NOT);2188	res = read_conjunct(s, v, isl_map_copy(map), rational);2189	if (negate)2190		res = isl_map_subtract(isl_map_copy(map), res);2191 2192	while (res && isl_stream_eat_if_available(s, ISL_TOKEN_AND)) {2193		isl_map *res_i;2194 2195		negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);2196		res_i = read_conjunct(s, v, isl_map_copy(map), rational);2197		if (negate)2198			res = isl_map_subtract(res, res_i);2199		else2200			res = isl_map_intersect(res, res_i);2201	}2202 2203	isl_map_free(map);2204	return res;2205}2206 2207static __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, '}'))2213		return map;2214 2215	res = read_conjuncts(s, v, isl_map_copy(map), rational);2216	while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {2217		isl_map *res_i;2218 2219		res_i = read_conjuncts(s, v, isl_map_copy(map), rational);2220		res = isl_map_union(res, res_i);2221	}2222 2223	isl_map_free(map);2224	return res;2225}2226 2227/* Read a first order formula from "s", add the corresponding2228 * constraints to "map" and return the result.2229 *2230 * In particular, read a formula of the form2231 *2232 *	a2233 *2234 * or2235 *2236 *	a implies b2237 *2238 * where a and b are disjunctions.2239 *2240 * In the first case, map is replaced by2241 *2242 *	map \cap { [..] : a }2243 *2244 * In the second case, it is replaced by2245 *2246 *	(map \setminus { [..] : a}) \cup (map \cap { [..] : b })2247 */2248static __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, isl_map_copy(map), rational);2254 2255	if (isl_stream_eat_if_available(s, ISL_TOKEN_IMPLIES)) {2256		isl_map *res2;2257 2258		res = isl_map_subtract(isl_map_copy(map), res);2259		res2 = read_disjuncts(s, v, map, rational);2260		res = isl_map_union(res, res2);2261	} else2262		isl_map_free(map);2263 2264	return res;2265}2266 2267static 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, isl_dim_param);2272	n_in = isl_basic_map_dim(bmap, isl_dim_in);2273	n_out = isl_basic_map_dim(bmap, isl_dim_out);2274	n_div = isl_basic_map_dim(bmap, 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 2296static __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, "expecting coefficient");2312		isl_token_free(tok);2313		goto error;2314	}2315	if (!tok->on_new_line) {2316		isl_stream_error(s, tok, "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, 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					"expecting coefficient on same line");2342		if (!tok)2343			goto error;2344		pos = polylib_pos_to_isl_pos(bmap, 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;2353error:2354	isl_basic_map_free(bmap);2355	return NULL;2356}2357 2358static __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, "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, "unexpected EOF");2379		return NULL;2380	}2381	if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {2382		isl_token_free(tok2);2383		isl_token_free(tok);2384		isl_stream_error(s, NULL,2385				 "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(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				    "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				    "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				    "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				    "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				    "dimensions don't match");2439			goto error;2440		}2441	} else2442		out = n_col - 2 - nparam;2443	bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, 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(bmap->div[k], 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, "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;2470error:2471	isl_basic_map_free(bmap);2472	return NULL;2473}2474 2475static __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, "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, tok2);2490		isl_stream_push_token(s, tok);2491		return isl_map_from_basic_map(basic_map_read_polylib(s));2492	}2493	if (tok2) {2494		isl_stream_error(s, tok2, "unexpected token");2495		isl_stream_push_token(s, 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(basic_map_read_polylib(s));2505 2506	for (i = 1; map && i < n; ++i)2507		map = isl_map_union(map,2508			isl_map_from_basic_map(basic_map_read_polylib(s)));2509 2510	return map;2511}2512 2513static 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, "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 2538static __isl_give isl_pw_qpolynomial *read_term(__isl_keep isl_stream *s,2539	__isl_keep isl_map *map, struct vars *v);2540 2541static __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, "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, ')'))2560			goto error;2561		pow = optional_power(s);2562		pwqp = isl_pw_qpolynomial_pow(pwqp, 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(tok2);2570			tok2 = next_token(s);2571			if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {2572				isl_stream_error(s, tok2, "expected denominator");2573				isl_token_free(tok);2574				isl_token_free(tok2);2575				return NULL;2576			}2577			qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map),2578						    tok->u.v, tok2->u.v);2579			isl_token_free(tok2);2580		} else {2581			isl_stream_push_token(s, tok2);2582			qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map),2583						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(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(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, tok->u.s, -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, v->n - n);2608			isl_stream_error(s, tok, "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(isl_map_get_space(map), pos, 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, 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, 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, "unexpected isl_token");2631		isl_stream_push_token(s, tok);2632		return NULL;2633	}2634 2635	if (isl_stream_eat_if_available(s, '*') ||2636	    isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {2637		isl_pw_qpolynomial *pwqp2;2638 2639		pwqp2 = read_factor(s, map, v);2640		pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2);2641	}2642 2643	return pwqp;2644error:2645	isl_pw_qpolynomial_free(pwqp);2646	return NULL;2647}2648 2649static __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(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(pwqp, pwqp2);2674		} else {2675			isl_stream_push_token(s, tok);2676			break;2677		}2678	}2679 2680	return pwqp;2681}2682 2683static __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, "unexpected EOF");2691		goto error;2692	}2693	if (tok->type == ':' ||2694	    (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {2695		isl_token_free(tok);2696		map = read_formula(s, v, map, rational);2697	} else2698		isl_stream_push_token(s, tok);2699 2700	return map;2701error:2702	isl_map_free(map);2703	return NULL;2704}2705 2706static 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, 0);2715	set = isl_map_range(map);2716 2717	pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set);2718 2719	vars_drop(v, v->n - n);2720 2721	obj.v = pwqp;2722	return obj;2723}2724 2725static 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, ISL_TOKEN_MAX);2735	min = !max && isl_stream_eat_if_available(s, ISL_TOKEN_MIN);2736	if (!min && !max)2737		return obj_read_poly(s, set, v, n);2738	fold = max ? isl_fold_max : isl_fold_min;2739 2740	if (isl_stream_eat(s, '('))2741		goto error;2742 2743	pwqp = read_term(s, set, v);2744	pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(fold, pwqp);2745 2746	while (isl_stream_eat_if_available(s, ',')) {2747		isl_pw_qpolynomial_fold *pwf_i;2748		pwqp = read_term(s, set, v);2749		pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(fold, pwqp);2750		pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i);2751	}2752 2753	if (isl_stream_eat(s, ')'))2754		goto error;2755 2756	set = read_optional_formula(s, set, v, 0);2757	pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set);2758 2759	vars_drop(v, v->n - n);2760 2761	obj.v = pwf;2762	return obj;2763error:2764	isl_set_free(set);2765	isl_pw_qpolynomial_fold_free(pwf);2766	obj.type = isl_obj_none;2767	return obj;2768}2769 2770static 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, ':')) {2778		isl_token_free(tok);2779		isl_stream_eat(s, ':');2780		return 1;2781	}2782 2783	isl_stream_push_token(s, tok);2784 2785	return 0;2786}2787 2788static 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, ':')) {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, map, v, n);2808 2809	map = read_map_tuple(s, map, isl_dim_in, v, rational, 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(map);2820			return obj_read_poly_or_fold(s, set, v, n);2821		}2822		map = read_map_tuple(s, map, isl_dim_out, v, rational, 0);2823		if (!map)2824			goto error;2825	} else {2826		map = isl_map_domain(map);2827		isl_stream_push_token(s, tok);2828	}2829 2830	map = read_optional_formula(s, map, v, rational);2831 2832	vars_drop(v, v->n - n);2833 2834	obj.v = map;2835	return obj;2836error:2837	isl_map_free(map);2838	obj.type = isl_obj_none;2839	return obj;2840}2841 2842static 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(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(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(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(obj.v);2855		obj.type = isl_obj_union_pw_qpolynomial_fold;2856	} else2857		isl_assert(ctx, 0, goto error);2858	return obj;2859error:2860	obj.type->free(obj.v);2861	obj.type = isl_obj_none;2862	return obj;2863}2864 2865static 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(s->ctx, obj1);2872	if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)2873		obj2 = to_union(s->ctx, obj2);2874	if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)2875		obj1 = to_union(s->ctx, obj1);2876	if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)2877		obj2 = to_union(s->ctx, obj2);2878	if (obj1.type == isl_obj_pw_qpolynomial &&2879	    obj2.type == isl_obj_union_pw_qpolynomial)2880		obj1 = to_union(s->ctx, obj1);2881	if (obj1.type == isl_obj_union_pw_qpolynomial &&2882	    obj2.type == isl_obj_pw_qpolynomial)2883		obj2 = to_union(s->ctx, obj2);2884	if (obj1.type == isl_obj_pw_qpolynomial_fold &&2885	    obj2.type == isl_obj_union_pw_qpolynomial_fold)2886		obj1 = to_union(s->ctx, obj1);2887	if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&2888	    obj2.type == isl_obj_pw_qpolynomial_fold)2889		obj2 = to_union(s->ctx, obj2);2890	if (obj1.type != obj2.type) {2891		isl_stream_error(s, NULL,2892				"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(obj1.v, obj2.v)) {2899		obj1 = to_union(s->ctx, obj1);2900		obj2 = to_union(s->ctx, obj2);2901	}2902	if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) {2903		obj1 = to_union(s->ctx, obj1);2904		obj2 = to_union(s->ctx, obj2);2905	}2906	if (obj1.type == isl_obj_pw_qpolynomial &&2907	    !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) {2908		obj1 = to_union(s->ctx, obj1);2909		obj2 = to_union(s->ctx, obj2);2910	}2911	if (obj1.type == isl_obj_pw_qpolynomial_fold &&2912	    !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) {2913		obj1 = to_union(s->ctx, obj1);2914		obj2 = to_union(s->ctx, obj2);2915	}2916	obj1.v = obj1.type->add(obj1.v, obj2.v);2917	return obj1;2918error: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 string2927 * or as an identifier) followed by ":"?2928 */2929static 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(s->ctx, tok);2944	res = !strcmp(name, "domain") && isl_stream_next_token_is(s, ':');2945	free(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 thing2955 * we expect in the stream is a domain key, i.e., "domain" followed2956 * by ":".  If the schedule was printed in YAML flow style, then2957 * we additionally expect a "{" to open the outer mapping.2958 */2959static 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 */2980static 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 */2995static 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, '}')) {3001		obj.type = isl_obj_union_set;3002		obj.v = isl_union_set_empty(isl_map_get_space(map));3003		return obj;3004	}3005 3006	for (;;) {3007		struct isl_obj o;3008		o = obj_read_body(s, isl_map_copy(map), v);3009		if (!obj.v)3010			obj = o;3011		else3012			obj = obj_add(s, obj, o);3013		if (obj.type == isl_obj_none || !obj.v)3014			return obj;3015		if (!isl_stream_eat_if_available(s, ';'))3016			break;3017		if (isl_stream_next_token_is(s, '}'))3018			break;3019	}3020 3021	return obj;3022}3023 3024static 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, "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, tok2);3048			obj.type = isl_obj_val;3049			obj.v = isl_val_int_from_isl_int(s->ctx, tok->u.v);3050			isl_token_free(tok);3051			return obj;3052		}3053		isl_stream_push_token(s, 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(s->ctx);3067	if (!v) {3068		isl_stream_push_token(s, tok);3069		goto error;3070	}3071	map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));3072	if (tok->type == '[') {3073		isl_stream_push_token(s, tok);3074		map = read_map_tuple(s, map, isl_dim_param, v, 0, 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, "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, "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(tok->u.s, "Sym")) {3099		isl_token_free(tok);3100		if (isl_stream_eat(s, '='))3101			goto error;3102		map = read_map_tuple(s, map, isl_dim_param, v, 0, 1);3103		if (!map)3104			goto error;3105	} else3106		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, "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;3126error: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 3135struct 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(obj.v);3151 3152	return obj.v;3153error: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(obj.v)) {3165			obj.v = isl_map_range(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;3172error: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(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(obj.v);3189	}3190	if (obj.v && obj.type == isl_obj_union_set &&3191	    isl_union_set_is_empty(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;3197error: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 set3204 * (in which case it is converted to a union set) or a union set.3205 */3206static __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(obj.v);3212	}3213	if (obj.v)3214		isl_assert(ctx, obj.type == isl_obj_union_set, goto error);3215 3216	return obj.v;3217error: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 extract3224 * 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(s->ctx, obj);3232}3233 3234static __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(isl_map_get_space(map));3256	else3257		bmap = isl_basic_map_copy(map->p[0]);3258 3259	isl_map_free(map);3260 3261	return bmap;3262error: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);3279error: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, 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, 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_BASE3309#define TYPE_BASE	basic_map3310#include "isl_read_from_str_templ.c"3311 3312#undef TYPE_BASE3313#define TYPE_BASE	basic_set3314#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, 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_BASE3329#define TYPE_BASE	map3330#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, 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_BASE3345#define TYPE_BASE	set3346#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, 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_BASE3361#define TYPE_BASE	union_map3362#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, 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_BASE3377#define TYPE_BASE	union_set3378#include "isl_read_from_str_templ.c"3379 3380static __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, "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(s->ctx, size);3397 3398	for (j = 0; j < size; ++j) {3399		tok = next_signed_value(s, "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;3407error:3408	isl_token_free(tok);3409	isl_vec_free(vec);3410	return NULL;3411}3412 3413static __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, 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;3440error:3441	obj.type->free(obj.v);3442	return NULL;3443}3444 3445#undef TYPE_BASE3446#define TYPE_BASE	pw_qpolynomial3447#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, 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 and3463 * 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;3475error:3476	obj.type->free(obj.v);3477	return NULL;3478}3479 3480#undef TYPE_BASE3481#define TYPE_BASE	pw_qpolynomial_fold3482#include "isl_read_from_str_templ.c"3483 3484/* Is the next token an identifier not in "v"?3485 */3486static 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, tok->u.s, -1) >= n;3496	isl_stream_push_token(s, tok);3497 3498	vars_drop(v, v->n - n);3499 3500	return fresh;3501}3502 3503/* First read the domain of the affine expression, which may be3504 * 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 reading3507 * 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 tuple3510 * or a new identifier, we again assume it's the domain.3511 * Finally, if the tuple is empty, then it must be the domain3512 * since it does not contain an affine expression.3513 * Otherwise, we assume we are reading an affine expression.3514 */3515static __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, dom, isl_dim_set, v, 0, 0);3525	}3526	if (!tok || tok->type != '[') {3527		isl_stream_error(s, tok, "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, 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, dom, isl_dim_set, v, 0, 0);3537	} else3538		isl_stream_push_token(s, tok);3539 3540	return dom;3541error:3542	if (tok)3543		isl_stream_push_token(s, tok);3544	isl_set_free(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(ma, 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(ma, 0);3566	isl_multi_aff_free(ma);3567	return aff;3568error:3569	isl_multi_aff_free(ma);3570	return NULL;3571}3572 3573/* Read a piecewise affine expression from "s" with domain (space) "dom".3574 */3575static __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(dom) && isl_stream_eat(s, ISL_TOKEN_TO))3581		goto error;3582 3583	if (isl_stream_eat(s, '['))3584		goto error;3585 3586	pwaff = accept_affine(s, isl_set_get_space(dom), v);3587 3588	if (isl_stream_eat(s, ']'))3589		goto error;3590 3591	dom = read_optional_formula(s, dom, v, 0);3592	pwaff = isl_pw_aff_intersect_domain(pwaff, dom);3593 3594	return pwaff;3595error:3596	isl_set_free(dom);3597	isl_pw_aff_free(pwaff);3598	return NULL;3599}3600 3601/* Read an affine expression, together with optional constraints3602 * on the domain from "s".  "dom" represents the initial constraints3603 * on the parameter domain.3604 * "v" contains a description of the identifiers parsed so far.3605 */3606static __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, aff_dom, v);3616	vars_drop(v, v->n - n);3617 3618	return pa;3619}3620 3621#undef BASE3622#define BASE	aff3623#include "isl_stream_read_pw_with_params_templ.c"3624 3625#undef TYPE_BASE3626#define TYPE_BASE	aff3627#include "isl_read_from_str_templ.c"3628 3629#undef TYPE_BASE3630#define TYPE_BASE	pw_aff3631#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 tuple3635 * returned by read_tuple, check that it does not involve any3636 * output/set dimensions (appearing at the "n" positions starting at "first"),3637 * remove those from the domain and replace the domain space3638 * with "domain_space".3639 *3640 * In particular, the result of read_tuple is of the form3641 * [input, output] -> [output], with anonymous domain.3642 * The function read_tuple accepts tuples where some output or3643 * set dimensions are defined in terms of other output or set dimensions3644 * 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 themselves3646 * (i.e., that are not defined).3647 * These cases are not allowed here.3648 */3649static __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(pa, isl_dim_in, first, pos + 1);3655	if (involves < 0) {3656		pa =  isl_pw_aff_free(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(pa, isl_dim_in, first, n);3663	pa = isl_pw_aff_reset_domain_space(pa, 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 dimensions3671 * at position "first".3672 *3673 * The entry is not allowed to depend on any (other) output dimensions.3674 */3675static __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(mpa);3683	pa = separate_tuple_entry(tuple_el, pos, first, n, space);3684	return isl_multi_pw_aff_set_pw_aff(mpa, pos, pa);3685}3686 3687#undef BASE3688#define BASE pw_aff3689 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 conditions3697 * on the domains should be specified inside the tuple since each3698 * 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 domain3701 * 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 and3706 * read in the next tuple.  This tuple (or the first tuple if it was3707 * not followed by a "->") is then converted into an isl_multi_pw_aff3708 * 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 */3714static __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, 0, 0);3724	if (!tuple)3725		goto error;3726	if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {3727		isl_map *map = map_from_tuple(tuple, dom, isl_dim_in, v, 0);3728		dom = isl_map_domain(map);3729		n_dom = v->n;3730		tuple = read_tuple(s, v, 0, 0);3731		if (!tuple)3732			goto error;3733	}3734	mpa = isl_multi_pw_aff_from_tuple(isl_set_get_space(dom), tuple);3735	if (!mpa)3736		dom = isl_set_free(dom);3737 3738	vars_drop(v, v->n - n_dom);3739	dom = read_optional_formula(s, dom, v, 0);3740 3741	vars_drop(v, v->n - n);3742 3743	mpa = isl_multi_pw_aff_intersect_domain(mpa, dom);3744 3745	return mpa;3746error:3747	isl_set_free(dom);3748	return NULL;3749}3750 3751/* Read a tuple of affine expressions, together with optional constraints3752 * on the domain from "s".  "dom" represents the initial constraints3753 * on the domain.3754 *3755 * Read a tuple of piecewise affine expressions with optional constraints and3756 * convert the result to an isl_pw_multi_aff on the shared domain.3757 */3758static __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 sequence3771 * of zero or more tuples of affine expressions with optional conditions and3772 * add them up.3773 */3774static __isl_give isl_union_pw_multi_aff *3775isl_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(isl_set_get_space(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, '}'))3787			break;3788 3789		pma = read_conditional_multi_aff(s, isl_set_copy(dom), v);3790		upma2 = isl_union_pw_multi_aff_from_pw_multi_aff(pma);3791		upma = isl_union_pw_multi_aff_union_add(upma, upma2);3792		if (!upma)3793			return NULL;3794	} while (isl_stream_eat_if_available(s, ';'));3795 3796	return upma;3797}3798 3799#undef BASE3800#define BASE	multi_aff3801#include "isl_stream_read_pw_with_params_templ.c"3802 3803#undef TYPE_BASE3804#define TYPE_BASE	pw_multi_aff3805#include "isl_stream_read_with_params_templ.c"3806#include "isl_read_from_str_templ.c"3807 3808#undef TYPE_BASE3809#define TYPE_BASE	union_pw_multi_aff3810#include "isl_stream_read_with_params_templ.c"3811#include "isl_read_from_str_templ.c"3812 3813#undef BASE3814#define BASE val3815 3816#include <isl_multi_read_no_explicit_domain_templ.c>3817 3818#undef BASE3819#define BASE id3820 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 dimensions3826 * at position "first".3827 *3828 * The entry is not allowed to depend on any (other) output dimensions.3829 */3830static __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(ma);3839	pa = separate_tuple_entry(tuple_el, pos, first, n, space);3840	aff = isl_pw_aff_as_aff(pa);3841	return isl_multi_aff_set_aff(ma, pos, aff);3842}3843 3844#undef BASE3845#define BASE aff3846 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 tuple3851 * representing this domain cannot involve any affine expressions.3852 * The tuple representing the actual expressions needs to consist3853 * 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(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, '{'))3870		goto error;3871 3872	tuple = read_tuple(s, v, 0, 0);3873	if (!tuple)3874		goto error;3875	if (isl_stream_eat_if_available(s, 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(isl_multi_pw_aff_get_space(tuple));3886		dom_space = isl_space_align_params(space, dom_space);3887		isl_multi_pw_aff_free(tuple);3888		tuple = read_tuple(s, v, 0, 0);3889		if (!tuple)3890			goto error;3891	}3892 3893	if (isl_stream_eat(s, '}'))3894		goto error;3895 3896	ma = isl_multi_aff_from_tuple(dom_space, tuple);3897 3898	vars_free(v);3899	return ma;3900error:3901	isl_multi_pw_aff_free(tuple);3902	vars_free(v);3903	isl_space_free(dom_space);3904	isl_multi_aff_free(ma);3905	return NULL;3906}3907 3908#undef TYPE_BASE3909#define TYPE_BASE	multi_aff3910#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 */3915static __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, isl_set_copy(dom), v);3919}3920 3921#undef TYPE_BASE3922#define TYPE_BASE	multi_pw_aff3923#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 */3928static __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, isl_set_copy(dom), v);3938	pa = read_pw_aff_with_dom(s, aff_dom, v);3939	vars_drop(v, v->n - n);3940 3941	upa = isl_union_pw_aff_from_pw_aff(pa);3942 3943	while (isl_stream_eat_if_available(s, ';')) {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, isl_set_copy(dom), v);3949		pa_i = read_pw_aff_with_dom(s, aff_dom, v);3950		vars_drop(v, v->n - n);3951 3952		upa_i = isl_union_pw_aff_from_pw_aff(pa_i);3953		upa = isl_union_pw_aff_union_add(upa, upa_i);3954	}3955 3956	isl_set_free(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 */3963static __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, isl_set_copy(dom), v);3967}3968 3969#undef TYPE_BASE3970#define TYPE_BASE	union_pw_aff3971#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 inside3975 * isl_stream_read_multi_union_pw_aff.3976 *3977 * Read a '{', the union piecewise affine expression body and a '}' and3978 * add the isl_union_pw_aff to *list.3979 */3980static __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(isl_space_params(isl_space_copy(space)));3988	if (isl_stream_eat(s, '{'))3989		goto error;3990	upa = read_union_pw_aff_with_dom(s, dom, v);3991	*list = isl_union_pw_aff_list_add(*list, upa);3992	if (isl_stream_eat(s, '}'))3993		return isl_space_free(space);3994	if (!*list)3995		return isl_space_free(space);3996	return space;3997error:3998	isl_set_free(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 */4006static 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, tok3);4025	}4026	if (tok2)4027		isl_stream_push_token(s, 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 not4035 * followed by a '{' or a nested tuple?4036 */4037static 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, 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 and4061 * 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 form4066 *4067 *	[{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]4068 *4069 * Read the tuple, collecting the individual isl_union_pw_aff4070 * elements in a list and construct the result from the tuple space and4071 * the list.4072 */4073static __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(s->ctx, 0);4080	space = read_tuple_space(s, v, space, 1, 0,4081				&read_union_pw_aff_el, &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 extract4093 * an isl_union_set from that.4094 */4095static __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, '{') < 0)4103		goto error;4104	obj = obj_read_disjuncts(s, v, map);4105	if (isl_stream_eat(s, '}') < 0)4106		goto error;4107	isl_map_free(map);4108 4109	return extract_union_set(s->ctx, obj);4110error: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 as4123 *4124 *	([...] : ...)4125 *4126 * and are especially useful for setting the explicit domain4127 * of a zero-dimensional isl_multi_union_pw_aff.4128 * The core isl_multi_union_pw_aff body ([...]) is read by4129 * read_multi_union_pw_aff_body_core.4130 */4131static __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, '('))4137		return read_multi_union_pw_aff_body_core(s, v, space);4138 4139	if (isl_stream_eat(s, '(') < 0)4140		goto error;4141	mupa = read_multi_union_pw_aff_body_core(s, v, isl_space_copy(space));4142	if (isl_stream_eat_if_available(s, ':')) {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, dom);4147	} else {4148		isl_space_free(space);4149	}4150	if (isl_stream_eat(s, ')') < 0)4151		return isl_multi_union_pw_aff_free(mupa);4152 4153	return mupa;4154error: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 form4162 *4163 *	[{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]4164 *4165 * or4166 *4167 *	[..] -> [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]4168 *4169 * Additionally, a shared domain may be specified as4170 *4171 *	([..] : ...)4172 *4173 * or4174 *4175 *	[..] -> ([..] : ...)4176 *4177 * The first case is handled by the caller, the second case4178 * 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 */4184static __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, '['))4194			return NULL;4195		if (isl_stream_eat(s, ']'))4196			return NULL;4197		space = isl_space_set_alloc(s->ctx, 0, 0);4198		return isl_multi_union_pw_aff_zero(space);4199	}4200 4201	v = vars_new(s->ctx);4202	if (!v)4203		return NULL;4204 4205	dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));4206	if (next_is_param_tuple(s)) {4207		dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);4208		if (isl_stream_eat(s, ISL_TOKEN_TO))4209			goto error;4210	}4211	space = isl_set_get_space(dom);4212	isl_set_free(dom);4213	mupa = read_multi_union_pw_aff_body(s, v, space);4214 4215	vars_free(v);4216 4217	return mupa;4218error:4219	vars_free(v);4220	isl_set_free(dom);4221	isl_multi_union_pw_aff_free(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 as4229 *4230 *	([...] : ...)4231 *4232 * and are especially useful for setting the explicit domain4233 * of a zero-dimensional isl_multi_union_pw_aff.4234 * The core isl_multi_union_pw_aff ([...]) is read by4235 * 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, '('))4243		return read_multi_union_pw_aff_core(s);4244 4245	if (isl_stream_eat(s, '(') < 0)4246		return NULL;4247	mupa = read_multi_union_pw_aff_core(s);4248	if (isl_stream_eat_if_available(s, ':')) {4249		isl_union_set *dom;4250 4251		dom = isl_stream_read_union_set(s);4252		mupa = isl_multi_union_pw_aff_intersect_domain(mupa, dom);4253	}4254	if (isl_stream_eat(s, ')') < 0)4255		return isl_multi_union_pw_aff_free(mupa);4256	return mupa;4257}4258 4259#undef TYPE_BASE4260#define TYPE_BASE	multi_union_pw_aff4261#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(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;4278error:4279	obj.type->free(obj.v);4280	return NULL;4281}4282 4283#undef TYPE_BASE4284#define TYPE_BASE	union_pw_qpolynomial4285#include "isl_read_from_str_templ.c"4286