X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_input.c;h=164a269f3b1d7283e8612a0f5c804e4745be5a06;hb=63fb8a7f484648c3caa25351c8c94ac2395ec563;hp=a1cf268b36a4ae223b72ba45f7044858d57311ec;hpb=fc5018d1bb09fa71ed67427de44b60b278cc2439;p=platform%2Fupstream%2Fisl.git diff --git a/isl_input.c b/isl_input.c index a1cf268..164a269 100644 --- a/isl_input.c +++ b/isl_input.c @@ -1,13 +1,15 @@ /* * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2010 INRIA Saclay + * Copyright 2012 Ecole Normale Superieure * - * Use of this software is governed by the GNU LGPLv2.1 license + * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, K.U.Leuven, Departement * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France + * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France */ #include @@ -17,20 +19,18 @@ #include #include #include -#include -#include +#include #include #include "isl_polynomial_private.h" #include #include +#include +#include +#include struct variable { char *name; int pos; - isl_vec *def; - /* non-zero if variable represents a min (-1) or a max (1) */ - int sign; - isl_mat *list; struct variable *next; }; @@ -56,8 +56,6 @@ static void variable_free(struct variable *var) { while (var) { struct variable *next = var->next; - isl_mat_free(var->list); - isl_vec_free(var->def); free(var->name); free(var); var = next; @@ -84,8 +82,6 @@ static void vars_drop(struct vars *v, int n) var = v->v; while (--n >= 0) { struct variable *next = var->next; - isl_mat_free(var->list); - isl_vec_free(var->def); free(var->name); free(var); var = next; @@ -103,7 +99,6 @@ static struct variable *variable_new(struct vars *v, const char *name, int len, var->name = strdup(name); var->name[len] = '\0'; var->pos = pos; - var->def = NULL; var->next = v->v; return var; error: @@ -145,26 +140,6 @@ static int vars_add_anon(struct vars *v) return 0; } -static __isl_give isl_basic_map *set_name(__isl_take isl_basic_map *bmap, - enum isl_dim_type type, unsigned pos, char *name) -{ - char *prime; - - if (!bmap) - return NULL; - if (!name) - return bmap; - - prime = strchr(name, '\''); - if (prime) - *prime = '\0'; - bmap = isl_basic_map_set_dim_name(bmap, type, pos, name); - if (prime) - *prime = '\''; - - return bmap; -} - /* Obtain next token, with some preprocessing. * In particular, evaluate expressions of the form x^y, * with x and y values. @@ -194,6 +169,86 @@ error: return NULL; } +/* Read an isl_val from "s". + * + * The following token sequences are recognized + * + * "infty" -> infty + * "-" "infty" -> -infty + * "NaN" -> NaN + * n "/" d -> n/d + * v -> v + * + * where n, d and v are integer constants. + */ +__isl_give isl_val *isl_stream_read_val(struct isl_stream *s) +{ + struct isl_token *tok = NULL; + struct isl_token *tok2 = NULL; + isl_val *val; + + tok = next_token(s); + if (!tok) { + isl_stream_error(s, NULL, "unexpected EOF"); + goto error; + } + if (tok->type == ISL_TOKEN_INFTY) { + isl_token_free(tok); + return isl_val_infty(s->ctx); + } + if (tok->type == '-' && + isl_stream_eat_if_available(s, ISL_TOKEN_INFTY)) { + isl_token_free(tok); + return isl_val_neginfty(s->ctx); + } + if (tok->type == ISL_TOKEN_NAN) { + isl_token_free(tok); + return isl_val_nan(s->ctx); + } + if (tok->type != ISL_TOKEN_VALUE) { + isl_stream_error(s, tok, "expecting value"); + goto error; + } + + if (isl_stream_eat_if_available(s, '/')) { + tok2 = next_token(s); + if (!tok2) { + isl_stream_error(s, NULL, "unexpected EOF"); + goto error; + } + if (tok2->type != ISL_TOKEN_VALUE) { + isl_stream_error(s, tok2, "expecting value"); + goto error; + } + val = isl_val_rat_from_isl_int(s->ctx, tok->u.v, tok2->u.v); + val = isl_val_normalize(val); + } else { + val = isl_val_int_from_isl_int(s->ctx, tok->u.v); + } + + isl_token_free(tok); + isl_token_free(tok2); + return val; +error: + isl_token_free(tok); + isl_token_free(tok2); + return NULL; +} + +/* Read an isl_val from "str". + */ +struct isl_val *isl_val_read_from_str(struct isl_ctx *ctx, + const char *str) +{ + isl_val *val; + struct isl_stream *s = isl_stream_new_str(ctx, str); + if (!s) + return NULL; + val = isl_stream_read_val(s); + isl_stream_free(s); + return val; +} + static int accept_cst_factor(struct isl_stream *s, isl_int *f) { struct isl_token *tok; @@ -224,12 +279,11 @@ error: * We introduce an integer division q = [aff/d] and the result * is set to aff - d q. */ -static __isl_give isl_vec *affine_mod(struct isl_stream *s, - struct vars *v, __isl_take isl_vec *aff) +static __isl_give isl_pw_aff *affine_mod(struct isl_stream *s, + struct vars *v, __isl_take isl_pw_aff *aff) { struct isl_token *tok; - struct variable *var; - isl_vec *mod; + isl_pw_aff *q; tok = next_token(s); if (!tok || tok->type != ISL_TOKEN_VALUE) { @@ -237,125 +291,190 @@ static __isl_give isl_vec *affine_mod(struct isl_stream *s, goto error; } - if (vars_add_anon(v) < 0) - goto error; + q = isl_pw_aff_copy(aff); + q = isl_pw_aff_scale_down(q, tok->u.v); + q = isl_pw_aff_floor(q); + q = isl_pw_aff_scale(q, tok->u.v); - var = v->v; + aff = isl_pw_aff_sub(aff, q); + + isl_token_free(tok); + return aff; +error: + isl_pw_aff_free(aff); + isl_token_free(tok); + return NULL; +} + +static __isl_give isl_pw_aff *accept_affine(struct isl_stream *s, + __isl_take isl_space *dim, struct vars *v); +static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s, + __isl_take isl_space *dim, struct vars *v); - var->def = isl_vec_alloc(s->ctx, 2 + v->n); - if (!var->def) +static __isl_give isl_pw_aff *accept_minmax(struct isl_stream *s, + __isl_take isl_space *dim, struct vars *v) +{ + struct isl_token *tok; + isl_pw_aff_list *list = NULL; + int min; + + tok = isl_stream_next_token(s); + if (!tok) + goto error; + min = tok->type == ISL_TOKEN_MIN; + isl_token_free(tok); + + if (isl_stream_eat(s, '(')) goto error; - isl_seq_cpy(var->def->el + 1, aff->el, aff->size); - isl_int_set_si(var->def->el[1 + aff->size], 0); - isl_int_set(var->def->el[0], tok->u.v); - mod = isl_vec_alloc(v->ctx, 1 + v->n); - if (!mod) + list = accept_affine_list(s, isl_space_copy(dim), v); + if (!list) goto error; - isl_seq_cpy(mod->el, aff->el, aff->size); - isl_int_neg(mod->el[aff->size], tok->u.v); + if (isl_stream_eat(s, ')')) + goto error; - isl_vec_free(aff); - isl_token_free(tok); - return mod; + isl_space_free(dim); + return min ? isl_pw_aff_list_min(list) : isl_pw_aff_list_max(list); error: - isl_vec_free(aff); - isl_token_free(tok); + isl_space_free(dim); + isl_pw_aff_list_free(list); return NULL; } -static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v); -static int read_div_definition(struct isl_stream *s, struct vars *v); -static int read_minmax_definition(struct isl_stream *s, struct vars *v); +static __isl_give isl_pw_aff *accept_div(struct isl_stream *s, + __isl_take isl_space *dim, struct vars *v) +{ + struct isl_token *tok; + int f = 0; + int c = 0; + isl_pw_aff *pwaff = NULL; + + if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOORD)) + f = 1; + else if (isl_stream_eat_if_available(s, ISL_TOKEN_CEILD)) + c = 1; + if (f || c) { + if (isl_stream_eat(s, '(')) + goto error; + } else { + if (isl_stream_eat(s, '[')) + goto error; + } + + pwaff = accept_affine(s, isl_space_copy(dim), v); + + if (f || c) { + if (isl_stream_eat(s, ',')) + goto error; + + tok = next_token(s); + if (!tok) + goto error; + if (tok->type != ISL_TOKEN_VALUE) { + isl_stream_error(s, tok, "expected denominator"); + isl_stream_push_token(s, tok); + goto error; + } + isl_pw_aff_scale_down(pwaff, tok->u.v); + isl_token_free(tok); + } + + if (c) + pwaff = isl_pw_aff_ceil(pwaff); + else + pwaff = isl_pw_aff_floor(pwaff); + + if (f || c) { + if (isl_stream_eat(s, ')')) + goto error; + } else { + if (isl_stream_eat(s, ']')) + goto error; + } + + isl_space_free(dim); + return pwaff; +error: + isl_space_free(dim); + isl_pw_aff_free(pwaff); + return NULL; +} -static __isl_give isl_vec *accept_affine_factor(struct isl_stream *s, - struct vars *v) +static __isl_give isl_pw_aff *accept_affine_factor(struct isl_stream *s, + __isl_take isl_space *dim, struct vars *v) { struct isl_token *tok = NULL; - isl_vec *aff = NULL; + isl_pw_aff *res = NULL; tok = next_token(s); if (!tok) { isl_stream_error(s, NULL, "unexpected EOF"); goto error; } - if (tok->type == ISL_TOKEN_IDENT) { + + if (tok->type == ISL_TOKEN_AFF) { + res = isl_pw_aff_copy(tok->u.pwaff); + isl_token_free(tok); + } else if (tok->type == ISL_TOKEN_IDENT) { int n = v->n; int pos = vars_pos(v, tok->u.s, -1); + isl_aff *aff; + if (pos < 0) goto error; if (pos >= n) { + vars_drop(v, v->n - n); isl_stream_error(s, tok, "unknown identifier"); goto error; } - aff = isl_vec_alloc(v->ctx, 1 + v->n); + aff = isl_aff_zero_on_domain(isl_local_space_from_space(isl_space_copy(dim))); if (!aff) goto error; - isl_seq_clr(aff->el, aff->size); - isl_int_set_si(aff->el[1 + pos], 1); + isl_int_set_si(aff->v->el[2 + pos], 1); + res = isl_pw_aff_from_aff(aff); isl_token_free(tok); } else if (tok->type == ISL_TOKEN_VALUE) { if (isl_stream_eat_if_available(s, '*')) { - aff = accept_affine_factor(s, v); - aff = isl_vec_scale(aff, tok->u.v); + res = accept_affine_factor(s, isl_space_copy(dim), v); + res = isl_pw_aff_scale(res, tok->u.v); } else { - aff = isl_vec_alloc(v->ctx, 1 + v->n); - if (!aff) - goto error; - isl_seq_clr(aff->el, aff->size); - isl_int_set(aff->el[0], tok->u.v); + isl_local_space *ls; + isl_aff *aff; + ls = isl_local_space_from_space(isl_space_copy(dim)); + aff = isl_aff_zero_on_domain(ls); + aff = isl_aff_add_constant(aff, tok->u.v); + res = isl_pw_aff_from_aff(aff); } isl_token_free(tok); } else if (tok->type == '(') { isl_token_free(tok); tok = NULL; - aff = accept_affine(s, v); - if (!aff) + res = accept_affine(s, isl_space_copy(dim), v); + if (!res) goto error; if (isl_stream_eat(s, ')')) goto error; } else if (tok->type == '[' || tok->type == ISL_TOKEN_FLOORD || tok->type == ISL_TOKEN_CEILD) { - int ceil = tok->type == ISL_TOKEN_CEILD; - struct variable *var; - if (vars_add_anon(v) < 0) - goto error; - var = v->v; - aff = isl_vec_alloc(v->ctx, 1 + v->n); - if (!aff) - goto error; - isl_seq_clr(aff->el, aff->size); - isl_int_set_si(aff->el[1 + v->n - 1], ceil ? -1 : 1); isl_stream_push_token(s, tok); tok = NULL; - if (read_div_definition(s, v) < 0) - goto error; - if (ceil) - isl_seq_neg(var->def->el + 1, var->def->el + 1, - var->def->size - 1); - aff = isl_vec_zero_extend(aff, 1 + v->n); + res = accept_div(s, isl_space_copy(dim), v); } else if (tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX) { - if (vars_add_anon(v) < 0) - goto error; - aff = isl_vec_alloc(v->ctx, 1 + v->n); - if (!aff) - goto error; - isl_seq_clr(aff->el, aff->size); - isl_int_set_si(aff->el[1 + v->n - 1], 1); isl_stream_push_token(s, tok); tok = NULL; - if (read_minmax_definition(s, v) < 0) - goto error; - aff = isl_vec_zero_extend(aff, 1 + v->n); + res = accept_minmax(s, isl_space_copy(dim), v); } else { isl_stream_error(s, tok, "expecting factor"); goto error; } - if (isl_stream_eat_if_available(s, '%')) - return affine_mod(s, v, aff); + if (isl_stream_eat_if_available(s, '%') || + isl_stream_eat_if_available(s, ISL_TOKEN_MOD)) { + isl_space_free(dim); + return affine_mod(s, v, res); + } if (isl_stream_eat_if_available(s, '*')) { isl_int f; isl_int_init(f); @@ -364,28 +483,55 @@ static __isl_give isl_vec *accept_affine_factor(struct isl_stream *s, isl_int_clear(f); goto error2; } - aff = isl_vec_scale(aff, f); + res = isl_pw_aff_scale(res, f); + isl_int_clear(f); + } + if (isl_stream_eat_if_available(s, '/')) { + isl_int f; + isl_int_init(f); + isl_int_set_si(f, 1); + if (accept_cst_factor(s, &f) < 0) { + isl_int_clear(f); + goto error2; + } + res = isl_pw_aff_scale_down(res, f); isl_int_clear(f); } - return aff; + isl_space_free(dim); + return res; error: isl_token_free(tok); error2: - isl_vec_free(aff); + isl_pw_aff_free(res); + isl_space_free(dim); return NULL; } -static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v) +static __isl_give isl_pw_aff *add_cst(__isl_take isl_pw_aff *pwaff, isl_int v) +{ + isl_aff *aff; + isl_space *space; + + space = isl_pw_aff_get_domain_space(pwaff); + aff = isl_aff_zero_on_domain(isl_local_space_from_space(space)); + aff = isl_aff_add_constant(aff, v); + + return isl_pw_aff_add(pwaff, isl_pw_aff_from_aff(aff)); +} + +static __isl_give isl_pw_aff *accept_affine(struct isl_stream *s, + __isl_take isl_space *dim, struct vars *v) { struct isl_token *tok = NULL; - struct isl_vec *aff; + isl_local_space *ls; + isl_pw_aff *res; int sign = 1; - aff = isl_vec_alloc(v->ctx, 1 + v->n); - if (!aff) - return NULL; - isl_seq_clr(aff->el, aff->size); + ls = isl_local_space_from_space(isl_space_copy(dim)); + res = isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls)); + if (!res) + goto error; for (;;) { tok = next_token(s); @@ -402,16 +548,17 @@ static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v) tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX || tok->type == ISL_TOKEN_FLOORD || tok->type == ISL_TOKEN_CEILD || - tok->type == ISL_TOKEN_IDENT) { - isl_vec *aff2; + tok->type == ISL_TOKEN_IDENT || + tok->type == ISL_TOKEN_AFF) { + isl_pw_aff *term; isl_stream_push_token(s, tok); tok = NULL; - aff2 = accept_affine_factor(s, v); + term = accept_affine_factor(s, isl_space_copy(dim), v); if (sign < 0) - aff2 = isl_vec_scale(aff2, s->ctx->negone); - aff = isl_vec_zero_extend(aff, 1 + v->n); - aff = isl_vec_add(aff, aff2); - if (!aff) + res = isl_pw_aff_sub(res, term); + else + res = isl_pw_aff_add(res, term); + if (!res) goto error; sign = 1; } else if (tok->type == ISL_TOKEN_VALUE) { @@ -419,21 +566,22 @@ static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v) isl_int_neg(tok->u.v, tok->u.v); if (isl_stream_eat_if_available(s, '*') || isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) { - isl_vec *aff2; - aff2 = accept_affine_factor(s, v); - aff2 = isl_vec_scale(aff2, tok->u.v); - aff = isl_vec_zero_extend(aff, 1 + v->n); - aff = isl_vec_add(aff, aff2); - if (!aff) + isl_pw_aff *term; + term = accept_affine_factor(s, + isl_space_copy(dim), v); + term = isl_pw_aff_scale(term, tok->u.v); + res = isl_pw_aff_add(res, term); + if (!res) goto error; } else { - isl_int_add(aff->el[0], aff->el[0], tok->u.v); + res = add_cst(res, tok->u.v); } sign = 1; } else { isl_stream_error(s, tok, "unexpected isl_token"); isl_stream_push_token(s, tok); - isl_vec_free(aff); + isl_pw_aff_free(res); + isl_space_free(dim); return NULL; } isl_token_free(tok); @@ -455,311 +603,204 @@ static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v) } } - return aff; + isl_space_free(dim); + return res; error: + isl_space_free(dim); isl_token_free(tok); - isl_vec_free(aff); + isl_pw_aff_free(res); return NULL; } -/* Add any variables in the variable list "v" that are not already in "bmap" - * as existentially quantified variables in "bmap". - */ -static __isl_give isl_basic_map *add_divs(__isl_take isl_basic_map *bmap, - struct vars *v) +static int is_comparator(struct isl_token *tok) { - int i; - int extra; - struct variable *var; - - extra = v->n - isl_basic_map_total_dim(bmap); - - if (extra == 0) - return bmap; - - bmap = isl_basic_map_extend_dim(bmap, isl_basic_map_get_dim(bmap), - extra, 0, 2 * extra); - - for (i = 0; i < extra; ++i) - if (isl_basic_map_alloc_div(bmap) < 0) - goto error; - - for (i = 0, var = v->v; i < extra; ++i, var = var->next) { - int k = bmap->n_div - 1 - i; - - isl_seq_cpy(bmap->div[k], var->def->el, var->def->size); - isl_seq_clr(bmap->div[k] + var->def->size, - 2 + v->n - var->def->size); + if (!tok) + return 0; - if (isl_basic_map_add_div_constraints(bmap, k) < 0) - goto error; + switch (tok->type) { + case ISL_TOKEN_LT: + case ISL_TOKEN_GT: + case ISL_TOKEN_LE: + case ISL_TOKEN_GE: + case ISL_TOKEN_NE: + case '=': + return 1; + default: + return 0; } - - return bmap; -error: - isl_basic_map_free(bmap); - return NULL; } -static __isl_give isl_basic_map *read_var_def(struct isl_stream *s, - __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v) +static struct isl_map *read_disjuncts(struct isl_stream *s, + struct vars *v, __isl_take isl_map *map, int rational); +static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s, + __isl_take isl_space *dim, struct vars *v, int rational); + +/* Accept a ternary operator, given the first argument. + */ +static __isl_give isl_pw_aff *accept_ternary(struct isl_stream *s, + __isl_take isl_map *cond, struct vars *v, int rational) { - isl_dim *dim; - isl_basic_map *def = NULL; - struct isl_vec *vec; - int k; - int n; + isl_space *dim; + isl_pw_aff *pwaff1 = NULL, *pwaff2 = NULL, *pa_cond; + + if (!cond) + return NULL; - if (vars_add_anon(v) < 0) + if (isl_stream_eat(s, '?')) goto error; - n = v->n; - vec = accept_affine(s, v); - if (!vec) + dim = isl_space_wrap(isl_map_get_space(cond)); + pwaff1 = accept_extended_affine(s, dim, v, rational); + if (!pwaff1) goto error; - dim = isl_basic_map_get_dim(bmap); - def = isl_basic_map_universe(dim); - def = add_divs(def, v); - def = isl_basic_map_extend_constraints(def, 1, 0); - k = isl_basic_map_alloc_equality(def); - if (k >= 0) { - isl_seq_cpy(def->eq[k], vec->el, vec->size); - isl_int_set_si(def->eq[k][1 + n - 1], -1); - } - isl_vec_free(vec); - if (k < 0) + if (isl_stream_eat(s, ':')) goto error; - vars_drop(v, v->n - n); + dim = isl_pw_aff_get_domain_space(pwaff1); + pwaff2 = accept_extended_affine(s, dim, v, rational); + if (!pwaff1) + goto error; - def = isl_basic_map_simplify(def); - def = isl_basic_map_finalize(def); - bmap = isl_basic_map_intersect(bmap, def); - return bmap; + pa_cond = isl_set_indicator_function(isl_map_wrap(cond)); + return isl_pw_aff_cond(pa_cond, pwaff1, pwaff2); error: - isl_basic_map_free(bmap); - isl_basic_map_free(def); + isl_map_free(cond); + isl_pw_aff_free(pwaff1); + isl_pw_aff_free(pwaff2); return NULL; } -static __isl_give isl_basic_map *read_var_list(struct isl_stream *s, - __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v) +/* Accept an affine expression that may involve ternary operators. + * We first read an affine expression. + * If it is not followed by a comparison operator, we simply return it. + * Otherwise, we assume the affine epxression is part of the first + * argument of a ternary operator and try to parse that. + */ +static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s, + __isl_take isl_space *dim, struct vars *v, int rational) { - int i = 0; + isl_space *space; + isl_map *cond; + isl_pw_aff *pwaff; struct isl_token *tok; + int line = -1, col = -1; + int is_comp; - while ((tok = next_token(s)) != NULL) { - int new_name = 0; - - if (tok->type == ISL_TOKEN_IDENT) { - int n = v->n; - int p = vars_pos(v, tok->u.s, -1); - if (p < 0) - goto error; - new_name = p >= n; - } - - if (new_name) { - bmap = isl_basic_map_add(bmap, type, 1); - bmap = set_name(bmap, type, i, v->v->name); - isl_token_free(tok); - } else if (tok->type == ISL_TOKEN_IDENT || - tok->type == ISL_TOKEN_VALUE || - tok->type == '-' || - tok->type == '(') { - if (type == isl_dim_param) { - isl_stream_error(s, tok, - "expecting unique identifier"); - goto error; - } - isl_stream_push_token(s, tok); - tok = NULL; - bmap = isl_basic_map_add(bmap, type, 1); - bmap = read_var_def(s, bmap, type, v); - } else - break; - - tok = isl_stream_next_token(s); - if (tok && tok->type == ']' && - isl_stream_next_token_is(s, '[')) { - isl_token_free(tok); - tok = isl_stream_next_token(s); - } else if (!tok || tok->type != ',') - break; - - isl_token_free(tok); - i++; - } - if (tok) + tok = isl_stream_next_token(s); + if (tok) { + line = tok->line; + col = tok->col; isl_stream_push_token(s, tok); - - return bmap; -error: - isl_token_free(tok); - isl_basic_map_free(bmap); - return NULL; -} - -static __isl_give isl_mat *accept_affine_list(struct isl_stream *s, - struct vars *v) -{ - struct isl_vec *vec; - struct isl_mat *mat; - struct isl_token *tok = NULL; - - vec = accept_affine(s, v); - mat = isl_mat_from_row_vec(vec); - if (!mat) - return NULL; - - for (;;) { - tok = isl_stream_next_token(s); - if (!tok) { - isl_stream_error(s, NULL, "unexpected EOF"); - goto error; - } - if (tok->type != ',') { - isl_stream_push_token(s, tok); - break; - } - isl_token_free(tok); - - vec = accept_affine(s, v); - mat = isl_mat_add_zero_cols(mat, 1 + v->n - isl_mat_cols(mat)); - mat = isl_mat_vec_concat(mat, vec); - if (!mat) - return NULL; } - return mat; -error: - isl_mat_free(mat); - return NULL; -} + pwaff = accept_affine(s, dim, v); + if (rational) + pwaff = isl_pw_aff_set_rational(pwaff); + if (!pwaff) + return NULL; -static int read_minmax_definition(struct isl_stream *s, struct vars *v) -{ - struct isl_token *tok; - struct variable *var; + tok = isl_stream_next_token(s); + if (!tok) + return isl_pw_aff_free(pwaff); - var = v->v; + is_comp = is_comparator(tok); + isl_stream_push_token(s, tok); + if (!is_comp) + return pwaff; - tok = isl_stream_next_token(s); + tok = isl_token_new(s->ctx, line, col, 0); if (!tok) - return -1; - var->sign = tok->type == ISL_TOKEN_MIN ? -1 : 1; - isl_token_free(tok); + return isl_pw_aff_free(pwaff); + tok->type = ISL_TOKEN_AFF; + tok->u.pwaff = pwaff; - if (isl_stream_eat(s, '(')) - return -1; + space = isl_pw_aff_get_domain_space(pwaff); + cond = isl_map_universe(isl_space_unwrap(space)); - var->list = accept_affine_list(s, v); - if (!var->list) - return -1; + isl_stream_push_token(s, tok); - if (isl_stream_eat(s, ')')) - return -1; + cond = read_disjuncts(s, v, cond, rational); - return 0; + return accept_ternary(s, cond, v, rational); } -static int read_div_definition(struct isl_stream *s, struct vars *v) +static __isl_give isl_map *read_var_def(struct isl_stream *s, + __isl_take isl_map *map, enum isl_dim_type type, struct vars *v, + int rational) { - struct isl_token *tok; - int seen_paren = 0; - struct isl_vec *aff; - struct variable *var; - int fc = 0; - - if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOORD) || - isl_stream_eat_if_available(s, ISL_TOKEN_CEILD)) { - fc = 1; - if (isl_stream_eat(s, '(')) - return -1; - } else { - if (isl_stream_eat(s, '[')) - return -1; - if (isl_stream_eat_if_available(s, '(')) - seen_paren = 1; - } - - var = v->v; - - aff = accept_affine(s, v); - if (!aff) - return -1; + isl_pw_aff *def; + int pos; + isl_map *def_map; - var->def = isl_vec_alloc(s->ctx, 2 + v->n); - if (!var->def) { - isl_vec_free(aff); - return -1; + if (type == isl_dim_param) + pos = isl_map_dim(map, isl_dim_param); + else { + pos = isl_map_dim(map, isl_dim_in); + if (type == isl_dim_out) + pos += isl_map_dim(map, isl_dim_out); + type = isl_dim_in; } + --pos; - isl_seq_cpy(var->def->el + 1, aff->el, aff->size); + def = accept_extended_affine(s, isl_space_wrap(isl_map_get_space(map)), + v, rational); + def_map = isl_map_from_pw_aff(def); + def_map = isl_map_equate(def_map, type, pos, isl_dim_out, 0); + def_map = isl_set_unwrap(isl_map_domain(def_map)); - isl_vec_free(aff); + map = isl_map_intersect(map, def_map); - if (fc) { - if (isl_stream_eat(s, ',')) - return -1; - } else { - if (seen_paren && isl_stream_eat(s, ')')) - return -1; - if (isl_stream_eat(s, '/')) - return -1; - } - - tok = next_token(s); - if (!tok) - return -1; - if (tok->type != ISL_TOKEN_VALUE) { - isl_stream_error(s, tok, "expected denominator"); - isl_stream_push_token(s, tok); - return -1; - } - isl_int_set(var->def->el[0], tok->u.v); - isl_token_free(tok); - - if (fc) { - if (isl_stream_eat(s, ')')) - return -1; - } else { - if (isl_stream_eat(s, ']')) - return -1; - } - - return 0; + return map; } -static struct isl_basic_map *add_div_definition(struct isl_stream *s, - struct vars *v, struct isl_basic_map *bmap, int pos) +static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s, + __isl_take isl_space *dim, struct vars *v) { - struct variable *var = v->v; - unsigned o_out = isl_basic_map_offset(bmap, isl_dim_out) - 1; + isl_pw_aff *pwaff; + isl_pw_aff_list *list; + struct isl_token *tok = NULL; - if (read_div_definition(s, v) < 0) + pwaff = accept_affine(s, isl_space_copy(dim), v); + list = isl_pw_aff_list_from_pw_aff(pwaff); + if (!list) goto error; - if (isl_basic_map_add_div_constraints_var(bmap, o_out + pos, - var->def->el) < 0) - goto error; + for (;;) { + tok = isl_stream_next_token(s); + if (!tok) { + isl_stream_error(s, NULL, "unexpected EOF"); + goto error; + } + if (tok->type != ',') { + isl_stream_push_token(s, tok); + break; + } + isl_token_free(tok); - return bmap; + pwaff = accept_affine(s, isl_space_copy(dim), v); + list = isl_pw_aff_list_concat(list, + isl_pw_aff_list_from_pw_aff(pwaff)); + if (!list) + goto error; + } + + isl_space_free(dim); + return list; error: - isl_basic_map_free(bmap); + isl_space_free(dim); + isl_pw_aff_list_free(list); return NULL; } -static struct isl_basic_map *read_defined_var_list(struct isl_stream *s, - struct vars *v, struct isl_basic_map *bmap) +static __isl_give isl_map *read_defined_var_list(struct isl_stream *s, + struct vars *v, __isl_take isl_map *map, int rational) { struct isl_token *tok; while ((tok = isl_stream_next_token(s)) != NULL) { int p; int n = v->n; - unsigned n_out = isl_basic_map_dim(bmap, isl_dim_out); if (tok->type != ISL_TOKEN_IDENT) break; @@ -772,16 +813,13 @@ static struct isl_basic_map *read_defined_var_list(struct isl_stream *s, goto error; } - bmap = isl_basic_map_cow(bmap); - bmap = isl_basic_map_add(bmap, isl_dim_out, 1); - bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim), - 0, 0, 2); + map = isl_map_add_dims(map, isl_dim_out, 1); isl_token_free(tok); tok = isl_stream_next_token(s); if (tok && tok->type == '=') { isl_token_free(tok); - bmap = add_div_definition(s, v, bmap, n_out); + map = read_var_def(s, map, isl_dim_out, v, rational); tok = isl_stream_next_token(s); } @@ -793,10 +831,10 @@ static struct isl_basic_map *read_defined_var_list(struct isl_stream *s, if (tok) isl_stream_push_token(s, tok); - return bmap; + return map; error: isl_token_free(tok); - isl_basic_map_free(bmap); + isl_map_free(map); return NULL; } @@ -824,197 +862,380 @@ static int next_is_tuple(struct isl_stream *s) return is_tuple; } -static __isl_give isl_basic_map *read_tuple(struct isl_stream *s, - __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v); +/* Allocate an initial tuple with zero dimensions and an anonymous, + * unstructured space. + * A tuple is represented as an isl_multi_pw_aff. + * The range space is the space of the tuple. + * The domain space is an anonymous space + * with a dimension for each variable in the set of variables in "v". + * If a given dimension is not defined in terms of earlier dimensions in + * the input, then the corresponding isl_pw_aff is set equal to one time + * the variable corresponding to the dimension being defined. + */ +static __isl_give isl_multi_pw_aff *tuple_alloc(struct vars *v) +{ + return isl_multi_pw_aff_alloc(isl_space_alloc(v->ctx, 0, v->n, 0)); +} -static __isl_give isl_basic_map *read_nested_tuple(struct isl_stream *s, - __isl_take isl_basic_map *bmap, struct vars *v) +/* Is "pa" an expression in term of earlier dimensions? + * The alternative is that the dimension is defined to be equal to itself, + * meaning that it has a universe domain and an expression that depends + * on itself. "i" is the position of the expression in a sequence + * of "n" expressions. The final dimensions of "pa" correspond to + * these "n" expressions. + */ +static int pw_aff_is_expr(__isl_keep isl_pw_aff *pa, int i, int n) { - bmap = read_tuple(s, bmap, isl_dim_in, v); - if (isl_stream_eat(s, ISL_TOKEN_TO)) - goto error; - bmap = read_tuple(s, bmap, isl_dim_out, v); - bmap = isl_basic_map_from_range(isl_basic_map_wrap(bmap)); - return bmap; + isl_aff *aff; + + if (!pa) + return -1; + if (pa->n != 1) + return 1; + if (!isl_set_plain_is_universe(pa->p[0].set)) + return 1; + + aff = pa->p[0].aff; + if (isl_int_is_zero(aff->v->el[aff->v->size - n + i])) + return 1; + return 0; +} + +/* Does the tuple contain any dimensions that are defined + * in terms of earlier dimensions? + */ +static int tuple_has_expr(__isl_keep isl_multi_pw_aff *tuple) +{ + int i, n; + int has_expr = 0; + isl_pw_aff *pa; + + if (!tuple) + return -1; + n = isl_multi_pw_aff_dim(tuple, isl_dim_out); + for (i = 0; i < n; ++i) { + pa = isl_multi_pw_aff_get_pw_aff(tuple, i); + has_expr = pw_aff_is_expr(pa, i, n); + isl_pw_aff_free(pa); + if (has_expr < 0 || has_expr) + break; + } + + return has_expr; +} + +/* Add a dimension to the given tuple. + * The dimension is initially undefined, so it is encoded + * as one times itself. + */ +static __isl_give isl_multi_pw_aff *tuple_add_dim( + __isl_take isl_multi_pw_aff *tuple, struct vars *v) +{ + isl_space *space; + isl_aff *aff; + isl_pw_aff *pa; + + tuple = isl_multi_pw_aff_add_dims(tuple, isl_dim_in, 1); + space = isl_multi_pw_aff_get_domain_space(tuple); + aff = isl_aff_zero_on_domain(isl_local_space_from_space(space)); + aff = isl_aff_add_coefficient_si(aff, isl_dim_in, v->n, 1); + pa = isl_pw_aff_from_aff(aff); + tuple = isl_multi_pw_aff_flat_range_product(tuple, + isl_multi_pw_aff_from_pw_aff(pa)); + + return tuple; +} + +/* Set the name of dimension "pos" in "tuple" to "name". + * During printing, we add primes if the same name appears more than once + * to distinguish the occurrences. Here, we remove those primes from "name" + * before setting the name of the dimension. + */ +static __isl_give isl_multi_pw_aff *tuple_set_dim_name( + __isl_take isl_multi_pw_aff *tuple, int pos, char *name) +{ + char *prime; + + if (!name) + return tuple; + + prime = strchr(name, '\''); + if (prime) + *prime = '\0'; + tuple = isl_multi_pw_aff_set_dim_name(tuple, isl_dim_set, pos, name); + if (prime) + *prime = '\''; + + return tuple; +} + +/* Read an affine expression from "s" and replace the definition + * of dimension "pos" in "tuple" by this expression. + * + * accept_extended_affine requires a wrapped space as input. + * The domain space of "tuple", on the other hand is an anonymous space, + * so we have to adjust the space of the isl_pw_aff before adding it + * to "tuple". + */ +static __isl_give isl_multi_pw_aff *read_tuple_var_def(struct isl_stream *s, + __isl_take isl_multi_pw_aff *tuple, int pos, struct vars *v, + int rational) +{ + isl_space *space; + isl_pw_aff *def; + + space = isl_space_wrap(isl_space_alloc(s->ctx, 0, v->n, 0)); + def = accept_extended_affine(s, space, v, rational); + space = isl_space_set_alloc(s->ctx, 0, v->n); + def = isl_pw_aff_reset_domain_space(def, space); + tuple = isl_multi_pw_aff_set_pw_aff(tuple, pos, def); + + return tuple; +} + +/* Read a list of variables and/or affine expressions and return the list + * as an isl_multi_pw_aff. + * The elements in the list are separated by either "," or "][". + * If "comma" is set then only "," is allowed. + */ +static __isl_give isl_multi_pw_aff *read_tuple_var_list(struct isl_stream *s, + struct vars *v, int rational, int comma) +{ + int i = 0; + struct isl_token *tok; + isl_multi_pw_aff *res; + + res = tuple_alloc(v); + + if (isl_stream_next_token_is(s, ']')) + return res; + + while ((tok = next_token(s)) != NULL) { + int new_name = 0; + + res = tuple_add_dim(res, v); + + if (tok->type == ISL_TOKEN_IDENT) { + int n = v->n; + int p = vars_pos(v, tok->u.s, -1); + if (p < 0) + goto error; + new_name = p >= n; + } + + if (tok->type == '*') { + if (vars_add_anon(v) < 0) + goto error; + isl_token_free(tok); + } else if (new_name) { + res = tuple_set_dim_name(res, i, v->v->name); + isl_token_free(tok); + if (isl_stream_eat_if_available(s, '=')) + res = read_tuple_var_def(s, res, i, v, + rational); + } else { + isl_stream_push_token(s, tok); + tok = NULL; + if (vars_add_anon(v) < 0) + goto error; + res = read_tuple_var_def(s, res, i, v, rational); + } + + tok = isl_stream_next_token(s); + if (!comma && tok && tok->type == ']' && + isl_stream_next_token_is(s, '[')) { + isl_token_free(tok); + tok = isl_stream_next_token(s); + } else if (!tok || tok->type != ',') + break; + + isl_token_free(tok); + i++; + } + if (tok) + isl_stream_push_token(s, tok); + + return res; error: - isl_basic_map_free(bmap); - return NULL; + isl_token_free(tok); + return isl_multi_pw_aff_free(res); } -static __isl_give isl_basic_map *read_tuple(struct isl_stream *s, - __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v) +/* Read a tuple and represent it as an isl_multi_pw_aff. See tuple_alloc. + */ +static __isl_give isl_multi_pw_aff *read_tuple(struct isl_stream *s, + struct vars *v, int rational, int comma) { struct isl_token *tok; char *name = NULL; + isl_multi_pw_aff *res = NULL; tok = isl_stream_next_token(s); - if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) { + if (!tok) + goto error; + if (tok->type == ISL_TOKEN_IDENT || tok->is_keyword) { name = strdup(tok->u.s); + isl_token_free(tok); if (!name) goto error; - isl_token_free(tok); - tok = isl_stream_next_token(s); - } - if (!tok || tok->type != '[') { - isl_stream_error(s, tok, "expecting '['"); + } else + isl_stream_push_token(s, tok); + if (isl_stream_eat(s, '[')) goto error; - } - isl_token_free(tok); - if (type != isl_dim_param && next_is_tuple(s)) { - isl_dim *dim = isl_basic_map_get_dim(bmap); - int nparam = isl_dim_size(dim, isl_dim_param); - int n_in = isl_dim_size(dim, isl_dim_in); - isl_basic_map *nested; - if (type == isl_dim_out) - dim = isl_dim_move(dim, isl_dim_param, nparam, - isl_dim_in, 0, n_in); - nested = isl_basic_map_alloc_dim(dim, 0, 0, 0); - nested = read_nested_tuple(s, nested, v); - if (type == isl_dim_in) { - nested = isl_basic_map_reverse(nested); - bmap = isl_basic_map_intersect(nested, bmap); - } else { - isl_basic_set *bset; - dim = isl_dim_range(isl_basic_map_get_dim(nested)); - dim = isl_dim_drop(dim, isl_dim_param, nparam, n_in); - dim = isl_dim_join(isl_basic_map_get_dim(bmap), dim); - bset = isl_basic_map_domain(bmap); - nested = isl_basic_map_reset_dim(nested, dim); - bmap = isl_basic_map_intersect_domain(nested, bset); - } + if (next_is_tuple(s)) { + isl_multi_pw_aff *out; + int n; + res = read_tuple(s, v, rational, comma); + if (isl_stream_eat(s, ISL_TOKEN_TO)) + goto error; + out = read_tuple(s, v, rational, comma); + n = isl_multi_pw_aff_dim(out, isl_dim_out); + res = isl_multi_pw_aff_add_dims(res, isl_dim_in, n); + res = isl_multi_pw_aff_range_product(res, out); } else - bmap = read_var_list(s, bmap, type, v); - tok = isl_stream_next_token(s); - if (!tok || tok->type != ']') { - isl_stream_error(s, tok, "expecting ']'"); + res = read_tuple_var_list(s, v, rational, comma); + if (isl_stream_eat(s, ']')) goto error; - } - isl_token_free(tok); if (name) { - bmap = isl_basic_map_set_tuple_name(bmap, type, name); + res = isl_multi_pw_aff_set_tuple_name(res, isl_dim_out, name); free(name); } - return bmap; + return res; error: - if (tok) - isl_token_free(tok); - isl_basic_map_free(bmap); - return NULL; + free(name); + return isl_multi_pw_aff_free(res); } -static __isl_give isl_basic_map *construct_constraint( - __isl_take isl_basic_map *bmap, enum isl_token_type type, - isl_int *left, isl_int *right) +/* Read a tuple from "s" and add it to "map". + * The tuple is initially represented as an isl_multi_pw_aff. + * We first create the appropriate space in "map" based on the range + * space of this isl_multi_pw_aff. Then, we add equalities based + * on the affine expressions. These live in an anonymous space, + * however, so we first need to reset the space to that of "map". + */ +static __isl_give isl_map *read_map_tuple(struct isl_stream *s, + __isl_take isl_map *map, enum isl_dim_type type, struct vars *v, + int rational, int comma) { - int k; - unsigned len; - struct isl_ctx *ctx; + int i, n; + isl_multi_pw_aff *tuple; + isl_space *space = NULL; - if (!bmap) - return NULL; - len = 1 + isl_basic_map_total_dim(bmap); - ctx = bmap->ctx; + tuple = read_tuple(s, v, rational, comma); + if (!tuple) + goto error; - k = isl_basic_map_alloc_inequality(bmap); - if (k < 0) + n = isl_multi_pw_aff_dim(tuple, isl_dim_out); + space = isl_space_range(isl_multi_pw_aff_get_space(tuple)); + if (!space) goto error; - if (type == ISL_TOKEN_LE) - isl_seq_combine(bmap->ineq[k], ctx->negone, left, - ctx->one, right, - len); - else if (type == ISL_TOKEN_GE) - isl_seq_combine(bmap->ineq[k], ctx->one, left, - ctx->negone, right, - len); - else if (type == ISL_TOKEN_LT) { - isl_seq_combine(bmap->ineq[k], ctx->negone, left, - ctx->one, right, - len); - isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1); - } else if (type == ISL_TOKEN_GT) { - isl_seq_combine(bmap->ineq[k], ctx->one, left, - ctx->negone, right, - len); - isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1); + + if (type == isl_dim_param) { + if (isl_space_has_tuple_name(space, isl_dim_set) || + isl_space_is_wrapping(space)) { + isl_die(s->ctx, isl_error_invalid, + "parameter tuples cannot be named or nested", + goto error); + } + map = isl_map_add_dims(map, type, n); + for (i = 0; i < n; ++i) { + isl_id *id; + if (!isl_space_has_dim_name(space, isl_dim_set, i)) + isl_die(s->ctx, isl_error_invalid, + "parameters must be named", + goto error); + id = isl_space_get_dim_id(space, isl_dim_set, i); + map = isl_map_set_dim_id(map, isl_dim_param, i, id); + } + } else if (type == isl_dim_in) { + isl_set *set; + + set = isl_set_universe(isl_space_copy(space)); + if (rational) + set = isl_set_set_rational(set); + set = isl_set_intersect_params(set, isl_map_params(map)); + map = isl_map_from_domain(set); } else { - isl_seq_combine(bmap->ineq[k], ctx->one, left, - ctx->negone, right, - len); - isl_basic_map_inequality_to_equality(bmap, k); + isl_set *set; + + set = isl_set_universe(isl_space_copy(space)); + if (rational) + set = isl_set_set_rational(set); + map = isl_map_from_domain_and_range(isl_map_domain(map), set); } - return bmap; + for (i = 0; i < n; ++i) { + isl_pw_aff *pa; + isl_space *space; + isl_aff *aff; + isl_set *set; + isl_map *map_i; + + pa = isl_multi_pw_aff_get_pw_aff(tuple, i); + space = isl_pw_aff_get_domain_space(pa); + aff = isl_aff_zero_on_domain(isl_local_space_from_space(space)); + aff = isl_aff_add_coefficient_si(aff, + isl_dim_in, v->n - n + i, -1); + pa = isl_pw_aff_add(pa, isl_pw_aff_from_aff(aff)); + if (rational) + pa = isl_pw_aff_set_rational(pa); + set = isl_pw_aff_zero_set(pa); + map_i = isl_map_from_range(set); + map_i = isl_map_reset_space(map_i, isl_map_get_space(map)); + map = isl_map_intersect(map, map_i); + } + + isl_space_free(space); + isl_multi_pw_aff_free(tuple); + return map; error: - isl_basic_map_free(bmap); + isl_space_free(space); + isl_multi_pw_aff_free(tuple); + isl_map_free(map); return NULL; } -static int is_comparator(struct isl_token *tok) -{ - if (!tok) - return 0; - - switch (tok->type) { - case ISL_TOKEN_LT: - case ISL_TOKEN_GT: - case ISL_TOKEN_LE: - case ISL_TOKEN_GE: - case '=': - return 1; - default: - return 0; - } -} - -/* Add any variables in the variable list "v" that are not already in "bmap" - * as output variables in "bmap". - */ -static __isl_give isl_basic_map *add_lifted_divs(__isl_take isl_basic_map *bmap, - struct vars *v) +static __isl_give isl_set *construct_constraints( + __isl_take isl_set *set, int type, + __isl_keep isl_pw_aff_list *left, __isl_keep isl_pw_aff_list *right, + int rational) { - int i; - int extra; - struct variable *var; - - extra = v->n - isl_basic_map_total_dim(bmap); - - if (extra == 0) - return bmap; + isl_set *cond; - bmap = isl_basic_map_add(bmap, isl_dim_out, extra); - bmap = isl_basic_map_extend_dim(bmap, isl_basic_map_get_dim(bmap), - 0, 0, 2 * extra); - - for (i = 0, var = v->v; i < extra; ++i, var = var->next) { - if (!var->def) - continue; - var->def = isl_vec_zero_extend(var->def, 2 + v->n); - if (!var->def) - goto error; - if (isl_basic_map_add_div_constraints_var(bmap, var->pos, - var->def->el) < 0) - goto error; + left = isl_pw_aff_list_copy(left); + right = isl_pw_aff_list_copy(right); + if (rational) { + left = isl_pw_aff_list_set_rational(left); + right = isl_pw_aff_list_set_rational(right); } + if (type == ISL_TOKEN_LE) + cond = isl_pw_aff_list_le_set(left, right); + else if (type == ISL_TOKEN_GE) + cond = isl_pw_aff_list_ge_set(left, right); + else if (type == ISL_TOKEN_LT) + cond = isl_pw_aff_list_lt_set(left, right); + else if (type == ISL_TOKEN_GT) + cond = isl_pw_aff_list_gt_set(left, right); + else if (type == ISL_TOKEN_NE) + cond = isl_pw_aff_list_ne_set(left, right); + else + cond = isl_pw_aff_list_eq_set(left, right); - return bmap; -error: - isl_basic_map_free(bmap); - return NULL; + return isl_set_intersect(set, cond); } -static struct isl_basic_map *add_constraint(struct isl_stream *s, - struct vars *v, struct isl_basic_map *bmap) +static __isl_give isl_map *add_constraint(struct isl_stream *s, + struct vars *v, __isl_take isl_map *map, int rational) { - int i, j; struct isl_token *tok = NULL; - struct isl_mat *aff1 = NULL, *aff2 = NULL; - - bmap = isl_basic_map_cow(bmap); + isl_pw_aff_list *list1 = NULL, *list2 = NULL; + isl_set *set; - aff1 = accept_affine_list(s, v); - if (!aff1) + set = isl_map_wrap(map); + list1 = accept_affine_list(s, isl_set_get_space(set), v); + if (!list1) goto error; tok = isl_stream_next_token(s); if (!is_comparator(tok)) { @@ -1025,23 +1246,15 @@ static struct isl_basic_map *add_constraint(struct isl_stream *s, goto error; } for (;;) { - aff2 = accept_affine_list(s, v); - if (!aff2) + list2 = accept_affine_list(s, isl_set_get_space(set), v); + if (!list2) goto error; - aff1 = isl_mat_add_zero_cols(aff1, aff2->n_col - aff1->n_col); - if (!aff1) - goto error; - bmap = add_lifted_divs(bmap, v); - bmap = isl_basic_map_extend_constraints(bmap, 0, - aff1->n_row * aff2->n_row); - for (i = 0; i < aff1->n_row; ++i) - for (j = 0; j < aff2->n_row; ++j) - bmap = construct_constraint(bmap, tok->type, - aff1->row[i], aff2->row[j]); + set = construct_constraints(set, tok->type, list1, list2, + rational); isl_token_free(tok); - isl_mat_free(aff1); - aff1 = aff2; + isl_pw_aff_list_free(list1); + list1 = list2; tok = isl_stream_next_token(s); if (!is_comparator(tok)) { @@ -1050,352 +1263,213 @@ static struct isl_basic_map *add_constraint(struct isl_stream *s, break; } } - isl_mat_free(aff1); + isl_pw_aff_list_free(list1); - return bmap; + return isl_set_unwrap(set); error: if (tok) isl_token_free(tok); - isl_mat_free(aff1); - isl_mat_free(aff2); - isl_basic_map_free(bmap); + isl_pw_aff_list_free(list1); + isl_pw_aff_list_free(list2); + isl_set_free(set); return NULL; } -/* Return first variable, starting at n, representing a min or max, - * or NULL if there is no such variable. - */ -static struct variable *first_minmax(struct vars *v, int n) -{ - struct variable *first = NULL; - struct variable *var; - - for (var = v->v; var && var->pos >= n; var = var->next) - if (var->list) - first = var; - - return first; -} - -/* Check whether the variable at the given position only occurs in - * inequalities and only with the given sign. - */ -static int all_coefficients_of_sign(__isl_keep isl_map *map, int pos, int sign) +static __isl_give isl_map *read_exists(struct isl_stream *s, + struct vars *v, __isl_take isl_map *map, int rational) { - int i, j; - - if (!map) - return -1; - - for (i = 0; i < map->n; ++i) { - isl_basic_map *bmap = map->p[i]; - - for (j = 0; j < bmap->n_eq; ++j) - if (!isl_int_is_zero(bmap->eq[j][1 + pos])) - return 0; - for (j = 0; j < bmap->n_ineq; ++j) { - int s = isl_int_sgn(bmap->ineq[j][1 + pos]); - if (s == 0) - continue; - if (s != sign) - return 0; - } - } - - return 1; -} + int n = v->n; + int seen_paren = isl_stream_eat_if_available(s, '('); -/* Given a variable m which represents a min or a max of n expressions - * b_i, add the constraints - * - * m <= b_i - * - * in case of a min (var->sign < 0) and m >= b_i in case of a max. - */ -static __isl_give isl_map *bound_minmax(__isl_take isl_map *map, - struct variable *var) -{ - int i, k; - isl_basic_map *bound; - int total; + map = isl_map_from_domain(isl_map_wrap(map)); + map = read_defined_var_list(s, v, map, rational); - total = isl_map_dim(map, isl_dim_all); - bound = isl_basic_map_alloc_dim(isl_map_get_dim(map), - 0, 0, var->list->n_row); + if (isl_stream_eat(s, ':')) + goto error; - for (i = 0; i < var->list->n_row; ++i) { - k = isl_basic_map_alloc_inequality(bound); - if (k < 0) - goto error; - if (var->sign < 0) - isl_seq_cpy(bound->ineq[k], var->list->row[i], - var->list->n_col); - else - isl_seq_neg(bound->ineq[k], var->list->row[i], - var->list->n_col); - isl_int_set_si(bound->ineq[k][1 + var->pos], var->sign); - isl_seq_clr(bound->ineq[k] + var->list->n_col, - 1 + total - var->list->n_col); - } + map = read_disjuncts(s, v, map, rational); + map = isl_set_unwrap(isl_map_domain(map)); - map = isl_map_intersect(map, isl_map_from_basic_map(bound)); + vars_drop(v, v->n - n); + if (seen_paren && isl_stream_eat(s, ')')) + goto error; return map; error: - isl_basic_map_free(bound); isl_map_free(map); return NULL; } -/* Given a variable m which represents a min (or max) of n expressions - * b_i, add constraints that assigns the minimal upper bound to m, i.e., - * divide the space into cells where one - * of the upper bounds is smaller than all the others and assign - * this upper bound to m. - * - * In particular, if there are n bounds b_i, then the input map - * is split into n pieces, each with the extra constraints +/* Parse an expression between parentheses and push the result + * back on the stream. * - * m = b_i - * b_i <= b_j for j > i - * b_i < b_j for j < i + * The parsed expression may be either an affine expression + * or a condition. The first type is pushed onto the stream + * as an isl_pw_aff, while the second is pushed as an isl_map. * - * in case of a min (var->sign < 0) and similarly in case of a max. - * - * Note: this function is very similar to set_minimum in isl_tab_pip.c - * Perhaps we should try to merge the two. - */ -static __isl_give isl_map *set_minmax(__isl_take isl_map *map, - struct variable *var) -{ - int i, j, k; - isl_basic_map *bmap = NULL; - isl_ctx *ctx; - isl_map *split = NULL; - int total; - - ctx = isl_map_get_ctx(map); - total = isl_map_dim(map, isl_dim_all); - split = isl_map_alloc_dim(isl_map_get_dim(map), - var->list->n_row, ISL_SET_DISJOINT); - - for (i = 0; i < var->list->n_row; ++i) { - bmap = isl_basic_map_alloc_dim(isl_map_get_dim(map), 0, - 1, var->list->n_row - 1); - k = isl_basic_map_alloc_equality(bmap); - if (k < 0) - goto error; - isl_seq_cpy(bmap->eq[k], var->list->row[i], var->list->n_col); - isl_int_set_si(bmap->eq[k][1 + var->pos], -1); - for (j = 0; j < var->list->n_row; ++j) { - if (j == i) - continue; - k = isl_basic_map_alloc_inequality(bmap); - if (k < 0) - goto error; - if (var->sign < 0) - isl_seq_combine(bmap->ineq[k], - ctx->one, var->list->row[j], - ctx->negone, var->list->row[i], - var->list->n_col); - else - isl_seq_combine(bmap->ineq[k], - ctx->negone, var->list->row[j], - ctx->one, var->list->row[i], - var->list->n_col); - isl_seq_clr(bmap->ineq[k] + var->list->n_col, - 1 + total - var->list->n_col); - if (j < i) - isl_int_sub_ui(bmap->ineq[k][0], - bmap->ineq[k][0], 1); - } - bmap = isl_basic_map_finalize(bmap); - split = isl_map_add_basic_map(split, bmap); - } - - map = isl_map_intersect(map, split); - - return map; -error: - isl_basic_map_free(bmap); - isl_map_free(split); - isl_map_free(map); - return NULL; -} - -/* Plug in the definitions of all min and max expressions. - * If a min expression only appears in inequalities and only - * with a positive coefficient, then we can simply bound - * the variable representing the min by its defining terms - * and similarly for a max expression. - * Otherwise, we have to assign the different terms to the - * variable under the condition that the assigned term is smaller - * than the other terms. + * If the initial token indicates the start of a condition, + * we parse it as such. + * Otherwise, we first parse an affine expression and push + * that onto the stream. If the affine expression covers the + * entire expression between parentheses, we return. + * Otherwise, we assume that the affine expression is the + * start of a condition and continue parsing. */ -static __isl_give isl_map *add_minmax(__isl_take isl_map *map, - struct vars *v, int n) -{ - struct variable *var; - - while (n < v->n) { - var = first_minmax(v, n); - if (!var) - break; - if (all_coefficients_of_sign(map, var->pos, -var->sign)) - map = bound_minmax(map, var); - else - map = set_minmax(map, var); - n = var->pos + 1; - } - - return map; -} - -static isl_map *read_constraint(struct isl_stream *s, - struct vars *v, __isl_take isl_basic_map *bmap) +static int resolve_paren_expr(struct isl_stream *s, + struct vars *v, __isl_take isl_map *map, int rational) { - int n = v->n; - isl_map *map; - unsigned total; + struct isl_token *tok, *tok2; + int line, col; + isl_pw_aff *pwaff; - if (!bmap) - return NULL; + tok = isl_stream_next_token(s); + if (!tok || tok->type != '(') + goto error; - bmap = isl_basic_set_unwrap(isl_basic_set_lift(isl_basic_map_wrap(bmap))); - total = isl_basic_map_total_dim(bmap); - while (v->n < total) - if (vars_add_anon(v) < 0) + if (isl_stream_next_token_is(s, '(')) + if (resolve_paren_expr(s, v, isl_map_copy(map), rational)) goto error; - bmap = add_constraint(s, v, bmap); - bmap = isl_basic_map_simplify(bmap); - bmap = isl_basic_map_finalize(bmap); - - map = isl_map_from_basic_map(bmap); - - map = add_minmax(map, v, n); - - map = isl_set_unwrap(isl_map_domain(map)); + if (isl_stream_next_token_is(s, ISL_TOKEN_EXISTS) || + isl_stream_next_token_is(s, ISL_TOKEN_NOT) || + isl_stream_next_token_is(s, ISL_TOKEN_TRUE) || + isl_stream_next_token_is(s, ISL_TOKEN_FALSE) || + isl_stream_next_token_is(s, ISL_TOKEN_MAP)) { + map = read_disjuncts(s, v, map, rational); + if (isl_stream_eat(s, ')')) + goto error; + tok->type = ISL_TOKEN_MAP; + tok->u.map = map; + isl_stream_push_token(s, tok); + return 0; + } - vars_drop(v, v->n - n); + tok2 = isl_stream_next_token(s); + if (!tok2) + goto error; + line = tok2->line; + col = tok2->col; + isl_stream_push_token(s, tok2); - return map; -error: - isl_basic_map_free(bmap); - return NULL; -} + pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v); + if (!pwaff) + goto error; -static struct isl_map *read_disjuncts(struct isl_stream *s, - struct vars *v, __isl_take isl_basic_map *bmap); + tok2 = isl_token_new(s->ctx, line, col, 0); + if (!tok2) + goto error2; + tok2->type = ISL_TOKEN_AFF; + tok2->u.pwaff = pwaff; -static __isl_give isl_map *read_exists(struct isl_stream *s, - struct vars *v, __isl_take isl_basic_map *bmap) -{ - int n = v->n; - int seen_paren = isl_stream_eat_if_available(s, '('); - isl_map *map = NULL; + if (isl_stream_eat_if_available(s, ')')) { + isl_stream_push_token(s, tok2); + isl_token_free(tok); + isl_map_free(map); + return 0; + } - bmap = isl_basic_map_from_domain(isl_basic_map_wrap(bmap)); - bmap = read_defined_var_list(s, v, bmap); + isl_stream_push_token(s, tok2); - if (isl_stream_eat(s, ':')) + map = read_disjuncts(s, v, map, rational); + if (isl_stream_eat(s, ')')) goto error; - map = read_disjuncts(s, v, bmap); - map = isl_set_unwrap(isl_map_domain(map)); - bmap = NULL; - - vars_drop(v, v->n - n); - if (seen_paren && isl_stream_eat(s, ')')) - goto error; + tok->type = ISL_TOKEN_MAP; + tok->u.map = map; + isl_stream_push_token(s, tok); - return map; + return 0; +error2: + isl_pw_aff_free(pwaff); error: - isl_basic_map_free(bmap); + isl_token_free(tok); isl_map_free(map); - return NULL; + return -1; } static __isl_give isl_map *read_conjunct(struct isl_stream *s, - struct vars *v, __isl_take isl_basic_map *bmap) + struct vars *v, __isl_take isl_map *map, int rational) { - isl_map *map; + if (isl_stream_next_token_is(s, '(')) + if (resolve_paren_expr(s, v, isl_map_copy(map), rational)) + goto error; - if (isl_stream_eat_if_available(s, '(')) { - map = read_disjuncts(s, v, bmap); - if (isl_stream_eat(s, ')')) + if (isl_stream_next_token_is(s, ISL_TOKEN_MAP)) { + struct isl_token *tok; + tok = isl_stream_next_token(s); + if (!tok) goto error; + isl_map_free(map); + map = isl_map_copy(tok->u.map); + isl_token_free(tok); return map; } if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS)) - return read_exists(s, v, bmap); + return read_exists(s, v, map, rational); if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE)) - return isl_map_from_basic_map(bmap); + return map; if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) { - isl_dim *dim = isl_basic_map_get_dim(bmap); - isl_basic_map_free(bmap); + isl_space *dim = isl_map_get_space(map); + isl_map_free(map); return isl_map_empty(dim); } - return read_constraint(s, v, bmap); + return add_constraint(s, v, map, rational); error: isl_map_free(map); return NULL; } static __isl_give isl_map *read_conjuncts(struct isl_stream *s, - struct vars *v, __isl_take isl_basic_map *bmap) + struct vars *v, __isl_take isl_map *map, int rational) { - isl_map *map; + isl_map *res; int negate; negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT); - map = read_conjunct(s, v, isl_basic_map_copy(bmap)); - if (negate) { - isl_map *t; - t = isl_map_from_basic_map(isl_basic_map_copy(bmap)); - map = isl_map_subtract(t, map); - } + res = read_conjunct(s, v, isl_map_copy(map), rational); + if (negate) + res = isl_map_subtract(isl_map_copy(map), res); - while (isl_stream_eat_if_available(s, ISL_TOKEN_AND)) { - isl_map *map_i; + while (res && isl_stream_eat_if_available(s, ISL_TOKEN_AND)) { + isl_map *res_i; negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT); - map_i = read_conjunct(s, v, isl_basic_map_copy(bmap)); + res_i = read_conjunct(s, v, isl_map_copy(map), rational); if (negate) - map = isl_map_subtract(map, map_i); + res = isl_map_subtract(res, res_i); else - map = isl_map_intersect(map, map_i); + res = isl_map_intersect(res, res_i); } - isl_basic_map_free(bmap); - return map; + isl_map_free(map); + return res; } static struct isl_map *read_disjuncts(struct isl_stream *s, - struct vars *v, __isl_take isl_basic_map *bmap) + struct vars *v, __isl_take isl_map *map, int rational) { - struct isl_map *map; + isl_map *res; if (isl_stream_next_token_is(s, '}')) { - isl_dim *dim = isl_basic_map_get_dim(bmap); - isl_basic_map_free(bmap); + isl_space *dim = isl_map_get_space(map); + isl_map_free(map); return isl_map_universe(dim); } - map = read_conjuncts(s, v, isl_basic_map_copy(bmap)); + res = read_conjuncts(s, v, isl_map_copy(map), rational); while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) { - isl_map *map_i; + isl_map *res_i; - map_i = read_conjuncts(s, v, isl_basic_map_copy(bmap)); - map = isl_map_union(map, map_i); + res_i = read_conjuncts(s, v, isl_map_copy(map), rational); + res = isl_map_union(res, res_i); } - isl_basic_map_free(bmap); - return map; + isl_map_free(map); + return res; } static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos) @@ -1491,8 +1565,7 @@ error: return NULL; } -static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s, - int nparam) +static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s) { int i; struct isl_token *tok; @@ -1501,9 +1574,7 @@ static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s, int on_new_line; unsigned in = 0, out, local = 0; struct isl_basic_map *bmap = NULL; - - if (nparam < 0) - nparam = 0; + int nparam = 0; tok = isl_stream_next_token(s); if (!tok) { @@ -1610,7 +1681,7 @@ error: return NULL; } -static struct isl_map *map_read_polylib(struct isl_stream *s, int nparam) +static struct isl_map *map_read_polylib(struct isl_stream *s) { struct isl_token *tok; struct isl_token *tok2; @@ -1626,7 +1697,7 @@ static struct isl_map *map_read_polylib(struct isl_stream *s, int nparam) if (tok2 && tok2->type == ISL_TOKEN_VALUE) { isl_stream_push_token(s, tok2); isl_stream_push_token(s, tok); - return isl_map_from_basic_map(basic_map_read_polylib(s, nparam)); + return isl_map_from_basic_map(basic_map_read_polylib(s)); } if (tok2) { isl_stream_error(s, tok2, "unexpected token"); @@ -1639,11 +1710,11 @@ static struct isl_map *map_read_polylib(struct isl_stream *s, int nparam) isl_assert(s->ctx, n >= 1, return NULL); - map = isl_map_from_basic_map(basic_map_read_polylib(s, nparam)); + map = isl_map_from_basic_map(basic_map_read_polylib(s)); for (i = 1; map && i < n; ++i) map = isl_map_union(map, - isl_map_from_basic_map(basic_map_read_polylib(s, nparam))); + isl_map_from_basic_map(basic_map_read_polylib(s))); return map; } @@ -1673,38 +1744,13 @@ static int optional_power(struct isl_stream *s) return pow; } -static __isl_give isl_div *read_div(struct isl_stream *s, - __isl_take isl_dim *dim, struct vars *v) -{ - int n; - isl_basic_map *bmap; - - n = v->n; - bmap = isl_basic_map_universe(dim); - - if (vars_add_anon(v) < 0) - goto error; - if (read_div_definition(s, v) < 0) - goto error; - bmap = add_divs(bmap, v); - bmap = isl_basic_map_order_divs(bmap); - if (!bmap) - goto error; - vars_drop(v, v->n - n); - - return isl_basic_map_div(bmap, bmap->n_div - 1); -error: - isl_basic_map_free(bmap); - return NULL; -} - -static __isl_give isl_qpolynomial *read_term(struct isl_stream *s, - __isl_keep isl_basic_map *bmap, struct vars *v); +static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s, + __isl_keep isl_map *map, struct vars *v); -static __isl_give isl_qpolynomial *read_factor(struct isl_stream *s, - __isl_keep isl_basic_map *bmap, struct vars *v) +static __isl_give isl_pw_qpolynomial *read_factor(struct isl_stream *s, + __isl_keep isl_map *map, struct vars *v) { - struct isl_qpolynomial *qp; + isl_pw_qpolynomial *pwqp; struct isl_token *tok; tok = next_token(s); @@ -1716,15 +1762,17 @@ static __isl_give isl_qpolynomial *read_factor(struct isl_stream *s, int pow; isl_token_free(tok); - qp = read_term(s, bmap, v); - if (!qp) + pwqp = read_term(s, map, v); + if (!pwqp) return NULL; if (isl_stream_eat(s, ')')) goto error; pow = optional_power(s); - qp = isl_qpolynomial_pow(qp, pow); + pwqp = isl_pw_qpolynomial_pow(pwqp, pow); } else if (tok->type == ISL_TOKEN_VALUE) { struct isl_token *tok2; + isl_qpolynomial *qp; + tok2 = isl_stream_next_token(s); if (tok2 && tok2->type == '/') { isl_token_free(tok2); @@ -1735,25 +1783,31 @@ static __isl_give isl_qpolynomial *read_factor(struct isl_stream *s, isl_token_free(tok2); return NULL; } - qp = isl_qpolynomial_rat_cst(isl_basic_map_get_dim(bmap), + qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map), tok->u.v, tok2->u.v); isl_token_free(tok2); } else { isl_stream_push_token(s, tok2); - qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap), + qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map), tok->u.v); } isl_token_free(tok); + pwqp = isl_pw_qpolynomial_from_qpolynomial(qp); } else if (tok->type == ISL_TOKEN_INFTY) { + isl_qpolynomial *qp; isl_token_free(tok); - qp = isl_qpolynomial_infty(isl_basic_map_get_dim(bmap)); + qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map)); + pwqp = isl_pw_qpolynomial_from_qpolynomial(qp); } else if (tok->type == ISL_TOKEN_NAN) { + isl_qpolynomial *qp; isl_token_free(tok); - qp = isl_qpolynomial_nan(isl_basic_map_get_dim(bmap)); + qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map)); + pwqp = isl_pw_qpolynomial_from_qpolynomial(qp); } else if (tok->type == ISL_TOKEN_IDENT) { int n = v->n; int pos = vars_pos(v, tok->u.s, -1); int pow; + isl_qpolynomial *qp; if (pos < 0) { isl_token_free(tok); return NULL; @@ -1766,23 +1820,21 @@ static __isl_give isl_qpolynomial *read_factor(struct isl_stream *s, } isl_token_free(tok); pow = optional_power(s); - qp = isl_qpolynomial_var_pow(isl_basic_map_get_dim(bmap), pos, pow); + qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow); + pwqp = isl_pw_qpolynomial_from_qpolynomial(qp); } else if (tok->type == '[') { - isl_div *div; + isl_pw_aff *pwaff; int pow; isl_stream_push_token(s, tok); - div = read_div(s, isl_basic_map_get_dim(bmap), v); + pwaff = accept_div(s, isl_map_get_space(map), v); pow = optional_power(s); - qp = isl_qpolynomial_div_pow(div, pow); + pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff); + pwqp = isl_pw_qpolynomial_pow(pwqp, pow); } else if (tok->type == '-') { - struct isl_qpolynomial *qp2; - isl_token_free(tok); - qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap), - s->ctx->negone); - qp2 = read_factor(s, bmap, v); - qp = isl_qpolynomial_mul(qp, qp2); + pwqp = read_factor(s, map, v); + pwqp = isl_pw_qpolynomial_neg(pwqp); } else { isl_stream_error(s, tok, "unexpected isl_token"); isl_stream_push_token(s, tok); @@ -1791,101 +1843,94 @@ static __isl_give isl_qpolynomial *read_factor(struct isl_stream *s, if (isl_stream_eat_if_available(s, '*') || isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) { - struct isl_qpolynomial *qp2; + isl_pw_qpolynomial *pwqp2; - qp2 = read_factor(s, bmap, v); - qp = isl_qpolynomial_mul(qp, qp2); + pwqp2 = read_factor(s, map, v); + pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2); } - return qp; + return pwqp; error: - isl_qpolynomial_free(qp); + isl_pw_qpolynomial_free(pwqp); return NULL; } -static __isl_give isl_qpolynomial *read_term(struct isl_stream *s, - __isl_keep isl_basic_map *bmap, struct vars *v) +static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s, + __isl_keep isl_map *map, struct vars *v) { struct isl_token *tok; - struct isl_qpolynomial *qp; + isl_pw_qpolynomial *pwqp; - qp = read_factor(s, bmap, v); + pwqp = read_factor(s, map, v); for (;;) { tok = next_token(s); if (!tok) - return qp; + return pwqp; if (tok->type == '+') { - struct isl_qpolynomial *qp2; + isl_pw_qpolynomial *pwqp2; isl_token_free(tok); - qp2 = read_factor(s, bmap, v); - qp = isl_qpolynomial_add(qp, qp2); + pwqp2 = read_factor(s, map, v); + pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2); } else if (tok->type == '-') { - struct isl_qpolynomial *qp2; + isl_pw_qpolynomial *pwqp2; isl_token_free(tok); - qp2 = read_factor(s, bmap, v); - qp = isl_qpolynomial_sub(qp, qp2); + pwqp2 = read_factor(s, map, v); + pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2); } else if (tok->type == ISL_TOKEN_VALUE && isl_int_is_neg(tok->u.v)) { - struct isl_qpolynomial *qp2; + isl_pw_qpolynomial *pwqp2; isl_stream_push_token(s, tok); - qp2 = read_factor(s, bmap, v); - qp = isl_qpolynomial_add(qp, qp2); + pwqp2 = read_factor(s, map, v); + pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2); } else { isl_stream_push_token(s, tok); break; } } - return qp; + return pwqp; } static __isl_give isl_map *read_optional_disjuncts(struct isl_stream *s, - __isl_take isl_basic_map *bmap, struct vars *v) + __isl_take isl_map *map, struct vars *v, int rational) { struct isl_token *tok; - struct isl_map *map; tok = isl_stream_next_token(s); if (!tok) { isl_stream_error(s, NULL, "unexpected EOF"); goto error; } - map = isl_map_from_basic_map(isl_basic_map_copy(bmap)); if (tok->type == ':' || (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) { isl_token_free(tok); - map = isl_map_intersect(map, - read_disjuncts(s, v, isl_basic_map_copy(bmap))); + map = read_disjuncts(s, v, map, rational); } else isl_stream_push_token(s, tok); - isl_basic_map_free(bmap); - return map; error: - isl_basic_map_free(bmap); + isl_map_free(map); return NULL; } static struct isl_obj obj_read_poly(struct isl_stream *s, - __isl_take isl_basic_map *bmap, struct vars *v, int n) + __isl_take isl_map *map, struct vars *v, int n) { struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL }; - struct isl_pw_qpolynomial *pwqp; - struct isl_qpolynomial *qp; - struct isl_map *map; + isl_pw_qpolynomial *pwqp; struct isl_set *set; - qp = read_term(s, bmap, v); - map = read_optional_disjuncts(s, bmap, v); + pwqp = read_term(s, map, v); + map = read_optional_disjuncts(s, map, v, 0); set = isl_map_range(map); - pwqp = isl_pw_qpolynomial_alloc(set, qp); + pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set); vars_drop(v, v->n - n); @@ -1894,45 +1939,42 @@ static struct isl_obj obj_read_poly(struct isl_stream *s, } static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s, - __isl_take isl_basic_map *bmap, struct vars *v, int n) + __isl_take isl_set *set, struct vars *v, int n) { struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL }; - isl_qpolynomial *qp; - isl_qpolynomial_fold *fold = NULL; - isl_pw_qpolynomial_fold *pwf; - isl_map *map; - isl_set *set; + isl_pw_qpolynomial *pwqp; + isl_pw_qpolynomial_fold *pwf = NULL; if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX)) - return obj_read_poly(s, bmap, v, n); + return obj_read_poly(s, set, v, n); if (isl_stream_eat(s, '(')) goto error; - qp = read_term(s, bmap, v); - fold = isl_qpolynomial_fold_alloc(isl_fold_max, qp); + pwqp = read_term(s, set, v); + pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, pwqp); while (isl_stream_eat_if_available(s, ',')) { - isl_qpolynomial_fold *fold_i; - qp = read_term(s, bmap, v); - fold_i = isl_qpolynomial_fold_alloc(isl_fold_max, qp); - fold = isl_qpolynomial_fold_fold(fold, fold_i); + isl_pw_qpolynomial_fold *pwf_i; + pwqp = read_term(s, set, v); + pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, + pwqp); + pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i); } if (isl_stream_eat(s, ')')) goto error; - map = read_optional_disjuncts(s, bmap, v); - set = isl_map_range(map); - pwf = isl_pw_qpolynomial_fold_alloc(isl_fold_max, set, fold); + set = read_optional_disjuncts(s, set, v, 0); + pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set); vars_drop(v, v->n - n); obj.v = pwf; return obj; error: - isl_basic_map_free(bmap); - isl_qpolynomial_fold_free(fold); + isl_set_free(set); + isl_pw_qpolynomial_fold_free(pwf); obj.type = isl_obj_none; return obj; } @@ -1956,47 +1998,55 @@ static int is_rational(struct isl_stream *s) } static struct isl_obj obj_read_body(struct isl_stream *s, - __isl_take isl_basic_map *bmap, struct vars *v) + __isl_take isl_map *map, struct vars *v) { - struct isl_map *map = NULL; struct isl_token *tok; struct isl_obj obj = { isl_obj_set, NULL }; int n = v->n; + int rational; - if (is_rational(s)) - bmap = isl_basic_map_set_rational(bmap); + rational = is_rational(s); + if (rational) + map = isl_map_set_rational(map); + + if (isl_stream_next_token_is(s, ':')) { + obj.type = isl_obj_set; + obj.v = read_optional_disjuncts(s, map, v, rational); + return obj; + } if (!next_is_tuple(s)) - return obj_read_poly_or_fold(s, bmap, v, n); + return obj_read_poly_or_fold(s, map, v, n); - bmap = read_tuple(s, bmap, isl_dim_in, v); - if (!bmap) + map = read_map_tuple(s, map, isl_dim_in, v, rational, 0); + if (!map) goto error; tok = isl_stream_next_token(s); - if (tok && tok->type == ISL_TOKEN_TO) { + if (!tok) + goto error; + if (tok->type == ISL_TOKEN_TO) { obj.type = isl_obj_map; isl_token_free(tok); if (!next_is_tuple(s)) { - bmap = isl_basic_map_reverse(bmap); - return obj_read_poly_or_fold(s, bmap, v, n); + isl_set *set = isl_map_domain(map); + return obj_read_poly_or_fold(s, set, v, n); } - bmap = read_tuple(s, bmap, isl_dim_out, v); - if (!bmap) + map = read_map_tuple(s, map, isl_dim_out, v, rational, 0); + if (!map) goto error; } else { - bmap = isl_basic_map_reverse(bmap); - if (tok) - isl_stream_push_token(s, tok); + map = isl_map_domain(map); + isl_stream_push_token(s, tok); } - map = read_optional_disjuncts(s, bmap, v); + map = read_optional_disjuncts(s, map, v, rational); vars_drop(v, v->n - n); obj.v = map; return obj; error: - isl_basic_map_free(bmap); + isl_map_free(map); obj.type = isl_obj_none; return obj; } @@ -2048,21 +2098,21 @@ static struct isl_obj obj_add(struct isl_ctx *ctx, obj2.type == isl_obj_pw_qpolynomial_fold) obj2 = to_union(ctx, obj2); isl_assert(ctx, obj1.type == obj2.type, goto error); - if (obj1.type == isl_obj_map && !isl_map_has_equal_dim(obj1.v, obj2.v)) { + if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) { obj1 = to_union(ctx, obj1); obj2 = to_union(ctx, obj2); } - if (obj1.type == isl_obj_set && !isl_set_has_equal_dim(obj1.v, obj2.v)) { + if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) { obj1 = to_union(ctx, obj1); obj2 = to_union(ctx, obj2); } if (obj1.type == isl_obj_pw_qpolynomial && - !isl_pw_qpolynomial_has_equal_dim(obj1.v, obj2.v)) { + !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) { obj1 = to_union(ctx, obj1); obj2 = to_union(ctx, obj2); } if (obj1.type == isl_obj_pw_qpolynomial_fold && - !isl_pw_qpolynomial_fold_has_equal_dim(obj1.v, obj2.v)) { + !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) { obj1 = to_union(ctx, obj1); obj2 = to_union(ctx, obj2); } @@ -2076,9 +2126,9 @@ error: return obj1; } -static struct isl_obj obj_read(struct isl_stream *s, int nparam) +static struct isl_obj obj_read(struct isl_stream *s) { - isl_basic_map *bmap = NULL; + isl_map *map = NULL; struct isl_token *tok; struct vars *v = NULL; struct isl_obj obj = { isl_obj_set, NULL }; @@ -2104,12 +2154,15 @@ static struct isl_obj obj_read(struct isl_stream *s, int nparam) } isl_stream_push_token(s, tok2); isl_stream_push_token(s, tok); - map = map_read_polylib(s, nparam); + map = map_read_polylib(s); if (!map) goto error; - if (isl_map_dim(map, isl_dim_in) > 0) + if (isl_map_may_be_set(map)) + obj.v = isl_map_range(map); + else { obj.type = isl_obj_map; - obj.v = map; + obj.v = map; + } return obj; } v = vars_new(s->ctx); @@ -2117,14 +2170,12 @@ static struct isl_obj obj_read(struct isl_stream *s, int nparam) isl_stream_push_token(s, tok); goto error; } - bmap = isl_basic_map_alloc(s->ctx, 0, 0, 0, 0, 0, 0); + map = isl_map_universe(isl_space_params_alloc(s->ctx, 0)); if (tok->type == '[') { isl_stream_push_token(s, tok); - bmap = read_tuple(s, bmap, isl_dim_param, v); - if (!bmap) + map = read_map_tuple(s, map, isl_dim_param, v, 0, 0); + if (!map) goto error; - if (nparam >= 0) - isl_assert(s->ctx, nparam == v->n, goto error); tok = isl_stream_next_token(s); if (!tok || tok->type != ISL_TOKEN_TO) { isl_stream_error(s, tok, "expecting '->'"); @@ -2134,8 +2185,7 @@ static struct isl_obj obj_read(struct isl_stream *s, int nparam) } isl_token_free(tok); tok = isl_stream_next_token(s); - } else if (nparam > 0) - bmap = isl_basic_map_add(bmap, isl_dim_param, nparam); + } if (!tok || tok->type != '{') { isl_stream_error(s, tok, "expecting '{'"); if (tok) @@ -2151,14 +2201,12 @@ static struct isl_obj obj_read(struct isl_stream *s, int nparam) isl_token_free(tok); if (isl_stream_eat(s, '=')) goto error; - bmap = read_tuple(s, bmap, isl_dim_param, v); - if (!bmap) + map = read_map_tuple(s, map, isl_dim_param, v, 0, 1); + if (!map) goto error; - if (nparam >= 0) - isl_assert(s->ctx, nparam == v->n, goto error); } else if (tok->type == '}') { obj.type = isl_obj_union_set; - obj.v = isl_union_set_empty(isl_basic_map_get_dim(bmap)); + obj.v = isl_union_set_empty(isl_map_get_space(map)); isl_token_free(tok); goto done; } else @@ -2167,7 +2215,7 @@ static struct isl_obj obj_read(struct isl_stream *s, int nparam) for (;;) { struct isl_obj o; tok = NULL; - o = obj_read_body(s, isl_basic_map_copy(bmap), v); + o = obj_read_body(s, isl_map_copy(map), v); if (o.type == isl_obj_none || !o.v) goto error; if (!obj.v) @@ -2197,11 +2245,11 @@ static struct isl_obj obj_read(struct isl_stream *s, int nparam) } done: vars_free(v); - isl_basic_map_free(bmap); + isl_map_free(map); return obj; error: - isl_basic_map_free(bmap); + isl_map_free(map); obj.type->free(obj.v); if (v) vars_free(v); @@ -2211,17 +2259,20 @@ error: struct isl_obj isl_stream_read_obj(struct isl_stream *s) { - return obj_read(s, -1); + return obj_read(s); } -__isl_give isl_map *isl_stream_read_map(struct isl_stream *s, int nparam) +__isl_give isl_map *isl_stream_read_map(struct isl_stream *s) { struct isl_obj obj; - obj = obj_read(s, nparam); + obj = obj_read(s); if (obj.v) isl_assert(s->ctx, obj.type == isl_obj_map || obj.type == isl_obj_set, goto error); + + if (obj.type == isl_obj_set) + obj.v = isl_map_from_range(obj.v); return obj.v; error: @@ -2229,13 +2280,18 @@ error: return NULL; } -__isl_give isl_set *isl_stream_read_set(struct isl_stream *s, int nparam) +__isl_give isl_set *isl_stream_read_set(struct isl_stream *s) { struct isl_obj obj; - obj = obj_read(s, nparam); - if (obj.v) + obj = obj_read(s); + if (obj.v) { + if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) { + obj.v = isl_map_range(obj.v); + obj.type = isl_obj_set; + } isl_assert(s->ctx, obj.type == isl_obj_set, goto error); + } return obj.v; error: @@ -2247,7 +2303,7 @@ __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s) { struct isl_obj obj; - obj = obj_read(s, -1); + obj = obj_read(s); if (obj.type == isl_obj_map) { obj.type = isl_obj_union_map; obj.v = isl_union_map_from_map(obj.v); @@ -2256,9 +2312,11 @@ __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s) obj.type = isl_obj_union_set; obj.v = isl_union_set_from_set(obj.v); } - if (obj.v) - isl_assert(s->ctx, obj.type == isl_obj_union_map || - obj.type == isl_obj_union_set, goto error); + if (obj.v && obj.type == isl_obj_union_set && + isl_union_set_is_empty(obj.v)) + obj.type = isl_obj_union_map; + if (obj.v && obj.type != isl_obj_union_map) + isl_die(s->ctx, isl_error_invalid, "invalid input", goto error); return obj.v; error: @@ -2270,7 +2328,7 @@ __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s) { struct isl_obj obj; - obj = obj_read(s, -1); + obj = obj_read(s); if (obj.type == isl_obj_set) { obj.type = isl_obj_union_set; obj.v = isl_union_set_from_set(obj.v); @@ -2284,13 +2342,13 @@ error: return NULL; } -static struct isl_basic_map *basic_map_read(struct isl_stream *s, int nparam) +static __isl_give isl_basic_map *basic_map_read(struct isl_stream *s) { struct isl_obj obj; struct isl_map *map; struct isl_basic_map *bmap; - obj = obj_read(s, nparam); + obj = obj_read(s); map = obj.v; if (!map) return NULL; @@ -2310,108 +2368,115 @@ error: return NULL; } +static __isl_give isl_basic_set *basic_set_read(struct isl_stream *s) +{ + isl_basic_map *bmap; + bmap = basic_map_read(s); + if (!bmap) + return NULL; + if (!isl_basic_map_may_be_set(bmap)) + isl_die(s->ctx, isl_error_invalid, + "input is not a set", goto error); + return isl_basic_map_range(bmap); +error: + isl_basic_map_free(bmap); + return NULL; +} + __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx, - FILE *input, int nparam) + FILE *input) { struct isl_basic_map *bmap; struct isl_stream *s = isl_stream_new_file(ctx, input); if (!s) return NULL; - bmap = basic_map_read(s, nparam); + bmap = basic_map_read(s); isl_stream_free(s); return bmap; } __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx, - FILE *input, int nparam) + FILE *input) { - struct isl_basic_map *bmap; - bmap = isl_basic_map_read_from_file(ctx, input, nparam); - if (!bmap) + isl_basic_set *bset; + struct isl_stream *s = isl_stream_new_file(ctx, input); + if (!s) return NULL; - isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error); - return (struct isl_basic_set *)bmap; -error: - isl_basic_map_free(bmap); - return NULL; + bset = basic_set_read(s); + isl_stream_free(s); + return bset; } struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx, - const char *str, int nparam) + const char *str) { struct isl_basic_map *bmap; struct isl_stream *s = isl_stream_new_str(ctx, str); if (!s) return NULL; - bmap = basic_map_read(s, nparam); + bmap = basic_map_read(s); isl_stream_free(s); return bmap; } struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx, - const char *str, int nparam) + const char *str) { - struct isl_basic_map *bmap; - bmap = isl_basic_map_read_from_str(ctx, str, nparam); - if (!bmap) + isl_basic_set *bset; + struct isl_stream *s = isl_stream_new_str(ctx, str); + if (!s) return NULL; - isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error); - return (struct isl_basic_set *)bmap; -error: - isl_basic_map_free(bmap); - return NULL; + bset = basic_set_read(s); + isl_stream_free(s); + return bset; } __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx, - FILE *input, int nparam) + FILE *input) { struct isl_map *map; struct isl_stream *s = isl_stream_new_file(ctx, input); if (!s) return NULL; - map = isl_stream_read_map(s, nparam); + map = isl_stream_read_map(s); isl_stream_free(s); return map; } __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx, - const char *str, int nparam) + const char *str) { struct isl_map *map; struct isl_stream *s = isl_stream_new_str(ctx, str); if (!s) return NULL; - map = isl_stream_read_map(s, nparam); + map = isl_stream_read_map(s); isl_stream_free(s); return map; } __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx, - FILE *input, int nparam) + FILE *input) { - struct isl_map *map; - map = isl_map_read_from_file(ctx, input, nparam); - if (!map) + isl_set *set; + struct isl_stream *s = isl_stream_new_file(ctx, input); + if (!s) return NULL; - isl_assert(ctx, isl_map_n_in(map) == 0, goto error); - return (struct isl_set *)map; -error: - isl_map_free(map); - return NULL; + set = isl_stream_read_set(s); + isl_stream_free(s); + return set; } struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx, - const char *str, int nparam) + const char *str) { - struct isl_map *map; - map = isl_map_read_from_str(ctx, str, nparam); - if (!map) + isl_set *set; + struct isl_stream *s = isl_stream_new_str(ctx, str); + if (!s) return NULL; - isl_assert(ctx, isl_map_n_in(map) == 0, goto error); - return (struct isl_set *)map; -error: - isl_map_free(map); - return NULL; + set = isl_stream_read_set(s); + isl_stream_free(s); + return set; } __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx, @@ -2518,7 +2583,7 @@ __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial( { struct isl_obj obj; - obj = obj_read(s, -1); + obj = obj_read(s); if (obj.v) isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial, goto error); @@ -2552,3 +2617,430 @@ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx, isl_stream_free(s); return pwqp; } + +/* Is the next token an identifer not in "v"? + */ +static int next_is_fresh_ident(struct isl_stream *s, struct vars *v) +{ + int n = v->n; + int fresh; + struct isl_token *tok; + + tok = isl_stream_next_token(s); + if (!tok) + return 0; + fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n; + isl_stream_push_token(s, tok); + + vars_drop(v, v->n - n); + + return fresh; +} + +/* First read the domain of the affine expression, which may be + * a parameter space or a set. + * The tricky part is that we don't know if the domain is a set or not, + * so when we are trying to read the domain, we may actually be reading + * the affine expression itself (defined on a parameter domains) + * If the tuple we are reading is named, we assume it's the domain. + * Also, if inside the tuple, the first thing we find is a nested tuple + * or a new identifier, we again assume it's the domain. + * Otherwise, we assume we are reading an affine expression. + */ +static __isl_give isl_set *read_aff_domain(struct isl_stream *s, + __isl_take isl_set *dom, struct vars *v) +{ + struct isl_token *tok; + + tok = isl_stream_next_token(s); + if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) { + isl_stream_push_token(s, tok); + return read_map_tuple(s, dom, isl_dim_set, v, 1, 0); + } + if (!tok || tok->type != '[') { + isl_stream_error(s, tok, "expecting '['"); + goto error; + } + if (next_is_tuple(s) || next_is_fresh_ident(s, v)) { + isl_stream_push_token(s, tok); + dom = read_map_tuple(s, dom, isl_dim_set, v, 1, 0); + } else + isl_stream_push_token(s, tok); + + return dom; +error: + if (tok) + isl_stream_push_token(s, tok); + isl_set_free(dom); + return NULL; +} + +/* Read an affine expression from "s". + */ +__isl_give isl_aff *isl_stream_read_aff(struct isl_stream *s) +{ + isl_aff *aff; + isl_multi_aff *ma; + + ma = isl_stream_read_multi_aff(s); + if (!ma) + return NULL; + if (isl_multi_aff_dim(ma, isl_dim_out) != 1) + isl_die(s->ctx, isl_error_invalid, + "expecting single affine expression", + goto error); + + aff = isl_multi_aff_get_aff(ma, 0); + isl_multi_aff_free(ma); + return aff; +error: + isl_multi_aff_free(ma); + return NULL; +} + +/* Read a piecewise affine expression from "s" with domain (space) "dom". + */ +static __isl_give isl_pw_aff *read_pw_aff_with_dom(struct isl_stream *s, + __isl_take isl_set *dom, struct vars *v) +{ + isl_pw_aff *pwaff = NULL; + + if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO)) + goto error; + + if (isl_stream_eat(s, '[')) + goto error; + + pwaff = accept_affine(s, isl_set_get_space(dom), v); + + if (isl_stream_eat(s, ']')) + goto error; + + dom = read_optional_disjuncts(s, dom, v, 0); + pwaff = isl_pw_aff_intersect_domain(pwaff, dom); + + return pwaff; +error: + isl_set_free(dom); + isl_pw_aff_free(pwaff); + return NULL; +} + +__isl_give isl_pw_aff *isl_stream_read_pw_aff(struct isl_stream *s) +{ + struct vars *v; + isl_set *dom = NULL; + isl_set *aff_dom; + isl_pw_aff *pa = NULL; + int n; + + v = vars_new(s->ctx); + if (!v) + return NULL; + + dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0)); + if (next_is_tuple(s)) { + dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0); + if (isl_stream_eat(s, ISL_TOKEN_TO)) + goto error; + } + if (isl_stream_eat(s, '{')) + goto error; + + n = v->n; + aff_dom = read_aff_domain(s, isl_set_copy(dom), v); + pa = read_pw_aff_with_dom(s, aff_dom, v); + vars_drop(v, v->n - n); + + while (isl_stream_eat_if_available(s, ';')) { + isl_pw_aff *pa_i; + + n = v->n; + aff_dom = read_aff_domain(s, isl_set_copy(dom), v); + pa_i = read_pw_aff_with_dom(s, aff_dom, v); + vars_drop(v, v->n - n); + + pa = isl_pw_aff_union_add(pa, pa_i); + } + + if (isl_stream_eat(s, '}')) + goto error; + + vars_free(v); + isl_set_free(dom); + return pa; +error: + vars_free(v); + isl_set_free(dom); + isl_pw_aff_free(pa); + return NULL; +} + +__isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str) +{ + isl_aff *aff; + struct isl_stream *s = isl_stream_new_str(ctx, str); + if (!s) + return NULL; + aff = isl_stream_read_aff(s); + isl_stream_free(s); + return aff; +} + +__isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str) +{ + isl_pw_aff *pa; + struct isl_stream *s = isl_stream_new_str(ctx, str); + if (!s) + return NULL; + pa = isl_stream_read_pw_aff(s); + isl_stream_free(s); + return pa; +} + +/* Read an isl_pw_multi_aff from "s". + * We currently read a generic object and if it turns out to be a set or + * a map, we convert that to an isl_pw_multi_aff. + * It would be more efficient if we were to construct the isl_pw_multi_aff + * directly. + */ +__isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(struct isl_stream *s) +{ + struct isl_obj obj; + + obj = obj_read(s); + if (!obj.v) + return NULL; + + if (obj.type == isl_obj_map) + return isl_pw_multi_aff_from_map(obj.v); + if (obj.type == isl_obj_set) + return isl_pw_multi_aff_from_set(obj.v); + + obj.type->free(obj.v); + isl_die(s->ctx, isl_error_invalid, "unexpected object type", + return NULL); +} + +__isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx, + const char *str) +{ + isl_pw_multi_aff *pma; + struct isl_stream *s = isl_stream_new_str(ctx, str); + if (!s) + return NULL; + pma = isl_stream_read_pw_multi_aff(s); + isl_stream_free(s); + return pma; +} + +/* Read an isl_union_pw_multi_aff from "s". + * We currently read a generic object and if it turns out to be a set or + * a map, we convert that to an isl_union_pw_multi_aff. + * It would be more efficient if we were to construct + * the isl_union_pw_multi_aff directly. + */ +__isl_give isl_union_pw_multi_aff *isl_stream_read_union_pw_multi_aff( + struct isl_stream *s) +{ + struct isl_obj obj; + + obj = obj_read(s); + if (!obj.v) + return NULL; + + if (obj.type == isl_obj_map || obj.type == isl_obj_set) + obj = to_union(s->ctx, obj); + if (obj.type == isl_obj_union_map) + return isl_union_pw_multi_aff_from_union_map(obj.v); + if (obj.type == isl_obj_union_set) + return isl_union_pw_multi_aff_from_union_set(obj.v); + + obj.type->free(obj.v); + isl_die(s->ctx, isl_error_invalid, "unexpected object type", + return NULL); +} + +/* Read an isl_union_pw_multi_aff from "str". + */ +__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_read_from_str( + isl_ctx *ctx, const char *str) +{ + isl_union_pw_multi_aff *upma; + struct isl_stream *s = isl_stream_new_str(ctx, str); + if (!s) + return NULL; + upma = isl_stream_read_union_pw_multi_aff(s); + isl_stream_free(s); + return upma; +} + +/* Assuming "pa" represents a single affine expression defined on a universe + * domain, extract this affine expression. + */ +static __isl_give isl_aff *aff_from_pw_aff(__isl_take isl_pw_aff *pa) +{ + isl_aff *aff; + + if (!pa) + return NULL; + if (pa->n != 1) + isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid, + "expecting single affine expression", + goto error); + if (!isl_set_plain_is_universe(pa->p[0].set)) + isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid, + "expecting universe domain", + goto error); + + aff = isl_aff_copy(pa->p[0].aff); + isl_pw_aff_free(pa); + return aff; +error: + isl_pw_aff_free(pa); + return NULL; +} + +/* Read a multi-affine expression from "s". + * If the multi-affine expression has a domain, then then tuple + * representing this domain cannot involve any affine expressions. + * The tuple representing the actual expressions needs to consist + * of only affine expressions. Moreover, these expressions can + * only depend on parameters and input dimensions and not on other + * output dimensions. + */ +__isl_give isl_multi_aff *isl_stream_read_multi_aff(struct isl_stream *s) +{ + struct vars *v; + isl_set *dom = NULL; + isl_multi_pw_aff *tuple = NULL; + int dim, i, n; + isl_space *space, *dom_space; + isl_multi_aff *ma = NULL; + + v = vars_new(s->ctx); + if (!v) + return NULL; + + dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0)); + if (next_is_tuple(s)) { + dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0); + if (isl_stream_eat(s, ISL_TOKEN_TO)) + goto error; + } + if (!isl_set_plain_is_universe(dom)) + isl_die(s->ctx, isl_error_invalid, + "expecting universe parameter domain", goto error); + if (isl_stream_eat(s, '{')) + goto error; + + tuple = read_tuple(s, v, 0, 0); + if (!tuple) + goto error; + if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) { + isl_set *set; + isl_space *space; + int has_expr; + + has_expr = tuple_has_expr(tuple); + if (has_expr < 0) + goto error; + if (has_expr) + isl_die(s->ctx, isl_error_invalid, + "expecting universe domain", goto error); + space = isl_space_range(isl_multi_pw_aff_get_space(tuple)); + set = isl_set_universe(space); + dom = isl_set_intersect_params(set, dom); + isl_multi_pw_aff_free(tuple); + tuple = read_tuple(s, v, 0, 0); + if (!tuple) + goto error; + } + + if (isl_stream_eat(s, '}')) + goto error; + + n = isl_multi_pw_aff_dim(tuple, isl_dim_out); + dim = isl_set_dim(dom, isl_dim_all); + dom_space = isl_set_get_space(dom); + space = isl_space_range(isl_multi_pw_aff_get_space(tuple)); + space = isl_space_align_params(space, isl_space_copy(dom_space)); + if (!isl_space_is_params(dom_space)) + space = isl_space_map_from_domain_and_range( + isl_space_copy(dom_space), space); + isl_space_free(dom_space); + ma = isl_multi_aff_alloc(space); + + for (i = 0; i < n; ++i) { + isl_pw_aff *pa; + isl_aff *aff; + pa = isl_multi_pw_aff_get_pw_aff(tuple, i); + aff = aff_from_pw_aff(pa); + if (!aff) + goto error; + if (isl_aff_involves_dims(aff, isl_dim_in, dim, i + 1)) { + isl_aff_free(aff); + isl_die(s->ctx, isl_error_invalid, + "not an affine expression", goto error); + } + aff = isl_aff_drop_dims(aff, isl_dim_in, dim, n); + space = isl_multi_aff_get_domain_space(ma); + aff = isl_aff_reset_domain_space(aff, space); + ma = isl_multi_aff_set_aff(ma, i, aff); + } + + isl_multi_pw_aff_free(tuple); + vars_free(v); + isl_set_free(dom); + return ma; +error: + isl_multi_pw_aff_free(tuple); + vars_free(v); + isl_set_free(dom); + isl_multi_aff_free(ma); + return NULL; +} + +__isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx, + const char *str) +{ + isl_multi_aff *maff; + struct isl_stream *s = isl_stream_new_str(ctx, str); + if (!s) + return NULL; + maff = isl_stream_read_multi_aff(s); + isl_stream_free(s); + return maff; +} + +__isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial( + struct isl_stream *s) +{ + struct isl_obj obj; + + obj = obj_read(s); + if (obj.type == isl_obj_pw_qpolynomial) { + obj.type = isl_obj_union_pw_qpolynomial; + obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v); + } + if (obj.v) + isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial, + goto error); + + return obj.v; +error: + obj.type->free(obj.v); + return NULL; +} + +__isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str( + isl_ctx *ctx, const char *str) +{ + isl_union_pw_qpolynomial *upwqp; + struct isl_stream *s = isl_stream_new_str(ctx, str); + if (!s) + return NULL; + upwqp = isl_stream_read_union_pw_qpolynomial(s); + isl_stream_free(s); + return upwqp; +}