1/* 2 * Copyright 2008-2009 Katholieke Universiteit Leuven 3 * Copyright 2010 INRIA Saclay 4 * Copyright 2012-2013 Ecole Normale Superieure 5 * Copyright 2019,2022 Cerebras Systems 6 * 7 * Use of this software is governed by the MIT license 8 * 9 * Written by Sven Verdoolaege, K.U.Leuven, Departement 10 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium 11 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, 12 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 13 * and Ecole Normale Superieure, 45 rue d���Ulm, 75230 Paris, France 14 * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA 15 */ 16 17#include <ctype.h> 18#include <stdio.h> 19#include <string.h> 20#include <isl_ctx_private.h> 21#include <isl_map_private.h> 22#include <isl_id_private.h> 23#include <isl/set.h> 24#include <isl_seq.h> 25#include <isl_stream_private.h> 26#include <isl/obj.h> 27#include "isl_polynomial_private.h" 28#include <isl/union_set.h> 29#include <isl/union_map.h> 30#include <isl_mat_private.h> 31#include <isl_aff_private.h> 32#include <isl_vec_private.h> 33#include <isl/list.h> 34#include <isl_val_private.h> 35 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 recognized 180 * 181 * "infty" -> infty 182 * "-" "infty" -> -infty 183 * "NaN" -> NaN 184 * n "/" d -> n/d 185 * "-" n "/" d -> -n/d 186 * v -> v 187 * "-" v -> -v 188 * 189 * where n, d and v are integer constants. 190 */ 191__isl_give isl_val *isl_stream_read_val(__isl_keep isl_stream *s) 192{ 193 struct isl_token *tok = NULL; 194 struct isl_token *tok2 = NULL; 195 int sign = 1; 196 isl_val *val; 197 198 if (isl_stream_eat_if_available(s, '-')) 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 else 210 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_BASE 250#define TYPE_BASE val 251#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 expression 279 * for aff % d, with d the next token on the stream, which is 280 * assumed to be a constant. 281 * 282 * We introduce an integer division q = [aff/d] and the result 283 * is set to aff - d q. 284 */ 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 form 432 * 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 else 475 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 domain 597 * 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 else 646 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 lists 685 * 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 given 777 * 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 first 818 * 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 depends 1015 * on itself. "i" is the position of the expression in a sequence 1016 * of "n" expressions. The final dimensions of "pa" correspond to 1017 * these "n" expressions. 1018 */ 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 defined 1037 * 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 once 1062 * 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 construct 1114 * 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 form 1129 * 1130 * D[..., i] -> i : C 1131 * 1132 * with D also the domains space of "lower' and "C" some constraints. 1133 * 1134 * Return the expression 1135 * 1136 * D[..., i] -> i : C and i >= lower 1137 */ 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 form 1150 * 1151 * D[..., i] -> i : C 1152 * 1153 * with D also the domains space of "upper' and "C" some constraints. 1154 * 1155 * Return the expression 1156 * 1157 * D[..., i] -> i : C and i <= upper 1158 */ 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 corresponding 1169 * to the last variable in "v" that is greater than or equal to "pa". 1170 * 1171 * In particular, if D is the domain space of "pa", 1172 * then construct the expression 1173 * 1174 * D[..., i] -> i, 1175 * 1176 * impose lower bound "pa" and return 1177 * 1178 * D[..., i] -> i : i >= pa 1179 */ 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 corresponding 1187 * to the last variable in "v" that is smaller than or equal to "pa". 1188 * 1189 * In particular, if D is the domain space of "pa", 1190 * then construct the expression 1191 * 1192 * D[..., i] -> i, 1193 * 1194 * impose lower bound "pa" and return 1195 * 1196 * D[..., i] -> i : i <= pa 1197 */ 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 corresponding 1205 * to the last variable in "v" that ranges between "pa" and "pa2". 1206 * 1207 * In particular, if D is the domain space of "pa" (and "pa2"), 1208 * then construct the expression 1209 * 1210 * D[..., i] -> i, 1211 * 1212 * impose lower bound "pa" and upper bound "pa2" and return 1213 * 1214 * D[..., i] -> i : pa <= i <= pa2 1215 */ 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 expression 1232 * then consider the two expressions as endpoints of a range of values and 1233 * return a piecewise affine expression that takes values in that range. 1234 * Note that an affine expression followed by a comparison operator 1235 * is considered to be part of a condition. 1236 * If the colon is not followed by anything (inside the tuple element), 1237 * then consider "pa" as a lower bound on a range of values without upper bound 1238 * and return a piecewise affine expression that takes values in that range. 1239 */ 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 form 1289 * 1290 * aff1 : condition1; aff2 : conditions2; ... 1291 * 1292 * or one of 1293 * 1294 * aff : 1295 * aff1 : aff2 1296 * : aff 1297 * : 1298 * 1299 * or simply 1300 * 1301 * aff 1302 * 1303 * each of the affine expressions may in turn include ternary operators. 1304 * 1305 * If the first token is a colon, then the expression must be 1306 * ":" or ": aff2", depending on whether anything follows the colon 1307 * inside the tuple element. 1308 * The first is considered to represent an arbitrary value. 1309 * The second is considered to represent a range of values 1310 * with the given upper bound and no lower bound. 1311 * 1312 * There may be parentheses around some subexpression of "aff1" 1313 * around "aff1" itself, around "aff1 : condition1" and/or 1314 * around the entire piecewise affine expression. 1315 * We therefore remove the opening parenthesis (if any) from the stream 1316 * in case the closing parenthesis follows the colon, but if the closing 1317 * parenthesis is the first thing in the stream after the parsed affine 1318 * expression, we push the parsed expression onto the stream and parse 1319 * again in case the parentheses enclose some subexpression of "aff1". 1320 */ 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 else 1331 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 else 1348 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_aff 1378 * to have an anonymous space. We therefore adjust the space 1379 * 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 and 1396 * return a space with the same number of set dimensions derived from 1397 * the parameter space "space" and possibly updated by "read_el". 1398 * The elements in the list are separated by either "," or "][". 1399 * If "comma" is set then only "," is allowed. 1400 */ 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 } else 1465 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 } else 1478 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 variables 1498 * 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 defined 1510 * over a space containing all variables in "v" defined so far. 1511 * The isl_pw_aff expresses the new variable in terms of earlier variables 1512 * if a definition is provided. Otherwise, it is represented as being 1513 * equal to itself. 1514 * Add the isl_pw_aff to *list. 1515 * If the new variable was named, then adjust "space" accordingly and 1516 * return the updated space. 1517 */ 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 else 1551 pa = identity_tuple_el(v); 1552 } else { 1553 isl_stream_push_token(s, tok); 1554 tok = NULL; 1555 if (vars_add_anon(v) < 0) 1556 goto error; 1557 pa = read_tuple_var_def(s, v, rational); 1558 } 1559 1560 *list = isl_pw_aff_list_add(*list, 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 space 1573 * with a dimension for each variable in the set of variables in "v", 1574 * including the variables in the range. 1575 * If a given dimension is not defined in terms of earlier dimensions in 1576 * the input, then the corresponding isl_pw_aff is set equal to one time 1577 * the variable corresponding to the dimension being defined. 1578 * 1579 * The elements in the tuple are collected in a list by read_tuple_pw_aff_el. 1580 * Each element in this list is defined over a space representing 1581 * the variables defined so far. We need to adjust the earlier 1582 * elements to have as many variables in the domain as the final 1583 * element in the list. 1584 */ 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 range 1615 * space of this isl_multi_pw_aff. Then, we add equalities based 1616 * on the affine expressions. These live in an anonymous space, 1617 * however, so we first need to reset the space to that of "map". 1618 */ 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 and 1703 * 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 comma) 1708{ 1709 isl_bool rational; 1710 isl_multi_pw_aff *tuple; 1711 1712 rational = isl_map_is_rational(map); 1713 if (rational < 0) 1714 return isl_map_free(map); 1715 tuple = read_tuple(s, v, rational, comma); 1716 if (!tuple) 1717 return isl_map_free(map); 1718 1719 return map_from_tuple(tuple, map, type, v, rational); 1720} 1721 1722/* Read the parameter domain of an expression from "s" (if any) and 1723 * check that it does not involve any constraints. 1724 * "v" contains a description of the identifiers parsed so far 1725 * (of which there should not be any at this point) and is extended 1726 * by this function. 1727 */ 1728static __isl_give isl_set *read_universe_params(__isl_keep isl_stream *s, 1729 struct vars *v) 1730{ 1731 isl_set *dom; 1732 1733 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0)); 1734 if (next_is_tuple(s)) { 1735 dom = read_map_tuple(s, dom, isl_dim_param, v, 0); 1736 if (isl_stream_eat(s, ISL_TOKEN_TO)) 1737 return isl_set_free(dom); 1738 } 1739 if (!isl_set_plain_is_universe(dom)) 1740 isl_die(s->ctx, isl_error_invalid, 1741 "expecting universe parameter domain", 1742 return isl_set_free(dom)); 1743 1744 return dom; 1745} 1746 1747/* Read the parameter domain of an expression from "s" (if any), 1748 * check that it does not involve any constraints and return its space. 1749 * "v" contains a description of the identifiers parsed so far 1750 * (of which there should not be any at this point) and is extended 1751 * by this function. 1752 */ 1753static __isl_give isl_space *read_params(__isl_keep isl_stream *s, 1754 struct vars *v) 1755{ 1756 isl_space *space; 1757 isl_set *set; 1758 1759 set = read_universe_params(s, v); 1760 space = isl_set_get_space(set); 1761 isl_set_free(set); 1762 1763 return space; 1764} 1765 1766/* This function is called for each element in a tuple inside read_space_tuples. 1767 * Add a new variable to "v" and adjust "space" accordingly 1768 * if the variable has a name. 1769 */ 1770static __isl_give isl_space *read_tuple_id(__isl_keep isl_stream *s, 1771 struct vars *v, __isl_take isl_space *space, int rational, void *user) 1772{ 1773 struct isl_token *tok; 1774 1775 tok = next_token(s); 1776 if (!tok) { 1777 isl_stream_error(s, NULL, "unexpected EOF"); 1778 return isl_space_free(space); 1779 } 1780 1781 if (tok->type == ISL_TOKEN_IDENT) { 1782 int n = v->n; 1783 int p = vars_pos(v, tok->u.s, -1); 1784 if (p < 0) 1785 goto error; 1786 if (p < n) { 1787 isl_stream_error(s, tok, "expecting fresh identifier"); 1788 goto error; 1789 } 1790 space = space_set_last_dim_name(space, v->v->name); 1791 } else if (tok->type == '*') { 1792 if (vars_add_anon(v) < 0) 1793 goto error; 1794 } else { 1795 isl_stream_error(s, tok, "expecting identifier or '*'"); 1796 goto error; 1797 } 1798 1799 isl_token_free(tok); 1800 return space; 1801error: 1802 isl_token_free(tok); 1803 return isl_space_free(space); 1804} 1805 1806/* Given a parameter space "params", extend it with one or two tuples 1807 * read from "s". 1808 * "v" contains a description of the identifiers parsed so far and is extended 1809 * by this function. 1810 */ 1811static __isl_give isl_space *read_space_tuples(__isl_keep isl_stream *s, 1812 struct vars *v, __isl_take isl_space *params) 1813{ 1814 isl_space *space, *ran; 1815 1816 space = read_tuple_space(s, v, isl_space_copy(params), 1, 1, 1817 &read_tuple_id, NULL); 1818 if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) { 1819 ran = read_tuple_space(s, v, isl_space_copy(params), 1, 1, 1820 &read_tuple_id, NULL); 1821 space = isl_space_unwrap(isl_space_product(space, ran)); 1822 } 1823 isl_space_free(params); 1824 1825 return space; 1826} 1827 1828/* Read an isl_space object from "s". 1829 * 1830 * First read the parameters (if any). 1831 * 1832 * Then check if the description is of the special form "{ : }", 1833 * in which case it represents a parameter space. 1834 * Otherwise, it has one or two tuples. 1835 */ 1836__isl_give isl_space *isl_stream_read_space(__isl_keep isl_stream *s) 1837{ 1838 struct vars *v; 1839 isl_space *space; 1840 1841 v = vars_new(s->ctx); 1842 if (!v) 1843 return NULL; 1844 space = read_params(s, v); 1845 1846 if (isl_stream_eat(s, '{')) 1847 goto error; 1848 1849 if (!isl_stream_eat_if_available(s, ':')) 1850 space = read_space_tuples(s, v, space); 1851 1852 if (isl_stream_eat(s, '}')) 1853 goto error; 1854 1855 vars_free(v); 1856 return space; 1857error: 1858 vars_free(v); 1859 isl_space_free(space); 1860 return NULL; 1861} 1862 1863#undef TYPE_BASE 1864#define TYPE_BASE space 1865#include "isl_read_from_str_templ.c" 1866 1867/* Given two equal-length lists of piecewise affine expression with the space 1868 * of "set" as domain, construct a set in the same space that expresses 1869 * that "left" and "right" satisfy the comparison "type". 1870 * 1871 * A space is constructed of the same dimension as the number of elements 1872 * in the two lists. The comparison is then expressed in a map from 1873 * this space to itself and wrapped into a set. Finally the two lists 1874 * of piecewise affine expressions are plugged into this set. 1875 * 1876 * Let S be the space of "set" and T the constructed space. 1877 * The lists are first changed into two isl_multi_pw_affs in S -> T and 1878 * then combined into an isl_multi_pw_aff in S -> [T -> T], 1879 * while the comparison is first expressed in T -> T, then [T -> T] 1880 * and finally in S. 1881 */ 1882static __isl_give isl_set *list_cmp(__isl_keep isl_set *set, int type, 1883 __isl_take isl_pw_aff_list *left, __isl_take isl_pw_aff_list *right) 1884{ 1885 isl_space *space; 1886 isl_size n; 1887 isl_multi_pw_aff *mpa1, *mpa2; 1888 1889 n = isl_pw_aff_list_n_pw_aff(left); 1890 if (!set || n < 0 || !right) 1891 goto error; 1892 1893 space = isl_set_get_space(set); 1894 space = isl_space_from_domain(space); 1895 space = isl_space_add_dims(space, isl_dim_out, n); 1896 mpa1 = isl_multi_pw_aff_from_pw_aff_list(isl_space_copy(space), left); 1897 mpa2 = isl_multi_pw_aff_from_pw_aff_list(isl_space_copy(space), right); 1898 mpa1 = isl_multi_pw_aff_range_product(mpa1, mpa2); 1899 1900 space = isl_space_range(space); 1901 switch (type) { 1902 case ISL_TOKEN_LEX_LT: 1903 set = isl_map_wrap(isl_map_lex_lt(space)); 1904 break; 1905 case ISL_TOKEN_LEX_GT: 1906 set = isl_map_wrap(isl_map_lex_gt(space)); 1907 break; 1908 case ISL_TOKEN_LEX_LE: 1909 set = isl_map_wrap(isl_map_lex_le(space)); 1910 break; 1911 case ISL_TOKEN_LEX_GE: 1912 set = isl_map_wrap(isl_map_lex_ge(space)); 1913 break; 1914 default: 1915 isl_multi_pw_aff_free(mpa1); 1916 isl_space_free(space); 1917 isl_die(isl_set_get_ctx(set), isl_error_internal, 1918 "unhandled list comparison type", return NULL); 1919 } 1920 set = isl_set_preimage_multi_pw_aff(set, mpa1); 1921 return set; 1922error: 1923 isl_pw_aff_list_free(left); 1924 isl_pw_aff_list_free(right); 1925 return NULL; 1926} 1927 1928/* Construct constraints of the form 1929 * 1930 * a op b 1931 * 1932 * where a is an element in "left", op is an operator of type "type" and 1933 * b is an element in "right", add the constraints to "set" and return 1934 * the result. 1935 * "rational" is set if the constraints should be treated as 1936 * a rational constraints. 1937 * 1938 * If "type" is the type of a comparison operator between lists 1939 * of affine expressions, then a single (compound) constraint 1940 * is constructed by list_cmp instead. 1941 */ 1942static __isl_give isl_set *construct_constraints( 1943 __isl_take isl_set *set, int type, 1944 __isl_keep isl_pw_aff_list *left, __isl_keep isl_pw_aff_list *right, 1945 int rational) 1946{ 1947 isl_set *cond; 1948 1949 left = isl_pw_aff_list_copy(left); 1950 right = isl_pw_aff_list_copy(right); 1951 if (rational) { 1952 left = isl_pw_aff_list_set_rational(left); 1953 right = isl_pw_aff_list_set_rational(right); 1954 } 1955 if (is_list_comparator_type(type)) 1956 cond = list_cmp(set, type, left, right); 1957 else if (type == ISL_TOKEN_LE) 1958 cond = isl_pw_aff_list_le_set(left, right); 1959 else if (type == ISL_TOKEN_GE) 1960 cond = isl_pw_aff_list_ge_set(left, right); 1961 else if (type == ISL_TOKEN_LT) 1962 cond = isl_pw_aff_list_lt_set(left, right); 1963 else if (type == ISL_TOKEN_GT) 1964 cond = isl_pw_aff_list_gt_set(left, right); 1965 else if (type == ISL_TOKEN_NE) 1966 cond = isl_pw_aff_list_ne_set(left, right); 1967 else 1968 cond = isl_pw_aff_list_eq_set(left, right); 1969 1970 return isl_set_intersect(set, cond); 1971} 1972 1973/* Read a constraint from "s", add it to "map" and return the result. 1974 * "v" contains a description of the identifiers parsed so far. 1975 * "rational" is set if the constraint should be treated as 1976 * a rational constraint. 1977 * The constraint read from "s" may be applied to multiple pairs 1978 * of affine expressions and may be chained. 1979 * In particular, a list of affine expressions is read, followed 1980 * by a comparison operator and another list of affine expressions. 1981 * The comparison operator is then applied to each pair of elements 1982 * in the two lists and the results are added to "map". 1983 * However, if the operator expects two lists of affine expressions, 1984 * then it is applied directly to those lists and the two lists 1985 * are required to have the same length. 1986 * If the next token is another comparison operator, then another 1987 * list of affine expressions is read and the process repeats. 1988 * 1989 * The processing is performed on a wrapped copy of "map" because 1990 * an affine expression cannot have a binary relation as domain. 1991 */ 1992static __isl_give isl_map *add_constraint(__isl_keep isl_stream *s, 1993 struct vars *v, __isl_take isl_map *map, int rational) 1994{ 1995 struct isl_token *tok; 1996 int type; 1997 isl_pw_aff_list *list1 = NULL, *list2 = NULL; 1998 isl_size n1, n2; 1999 isl_set *set; 2000 2001 set = isl_map_wrap(map); 2002 list1 = accept_affine_list(s, isl_set_get_space(set), v); 2003 if (!list1) 2004 goto error; 2005 tok = isl_stream_next_token(s); 2006 if (!is_comparator(tok)) { 2007 isl_stream_error(s, tok, "missing operator"); 2008 if (tok) 2009 isl_stream_push_token(s, tok); 2010 goto error; 2011 } 2012 type = tok->type; 2013 isl_token_free(tok); 2014 for (;;) { 2015 list2 = accept_affine_list(s, isl_set_get_space(set), v); 2016 n1 = isl_pw_aff_list_n_pw_aff(list1); 2017 n2 = isl_pw_aff_list_n_pw_aff(list2); 2018 if (n1 < 0 || n2 < 0) 2019 goto error; 2020 if (is_list_comparator_type(type) && n1 != n2) { 2021 isl_stream_error(s, NULL, 2022 "list arguments not of same size"); 2023 goto error; 2024 } 2025 2026 set = construct_constraints(set, type, list1, list2, rational); 2027 isl_pw_aff_list_free(list1); 2028 list1 = list2; 2029 2030 if (!next_is_comparator(s)) 2031 break; 2032 tok = isl_stream_next_token(s); 2033 type = tok->type; 2034 isl_token_free(tok); 2035 } 2036 isl_pw_aff_list_free(list1); 2037 2038 return isl_set_unwrap(set); 2039error: 2040 isl_pw_aff_list_free(list1); 2041 isl_pw_aff_list_free(list2); 2042 isl_set_free(set); 2043 return NULL; 2044} 2045 2046static __isl_give isl_map *read_exists(__isl_keep isl_stream *s, 2047 struct vars *v, __isl_take isl_map *map, int rational) 2048{ 2049 int n = v->n; 2050 int seen_paren = isl_stream_eat_if_available(s, '('); 2051 2052 map = isl_map_from_domain(isl_map_wrap(map)); 2053 map = read_defined_var_list(s, v, map, rational); 2054 2055 if (isl_stream_eat(s, ':')) 2056 goto error; 2057 2058 map = read_formula(s, v, map, rational); 2059 map = isl_set_unwrap(isl_map_domain(map)); 2060 2061 vars_drop(v, v->n - n); 2062 if (seen_paren && isl_stream_eat(s, ')')) 2063 goto error; 2064 2065 return map; 2066error: 2067 isl_map_free(map); 2068 return NULL; 2069} 2070 2071/* Parse an expression between parentheses and push the result 2072 * back on the stream. 2073 * 2074 * The parsed expression may be either an affine expression 2075 * or a condition. The first type is pushed onto the stream 2076 * as an isl_pw_aff, while the second is pushed as an isl_map. 2077 * 2078 * If the initial token indicates the start of a condition, 2079 * we parse it as such. 2080 * Otherwise, we first parse an affine expression and push 2081 * that onto the stream. If the affine expression covers the 2082 * entire expression between parentheses, we return. 2083 * Otherwise, we assume that the affine expression is the 2084 * start of a condition and continue parsing. 2085 */ 2086static int resolve_paren_expr(__isl_keep isl_stream *s, 2087 struct vars *v, __isl_take isl_map *map, int rational) 2088{ 2089 struct isl_token *tok, *tok2; 2090 int has_paren; 2091 int line, col; 2092 isl_pw_aff *pwaff; 2093 2094 tok = isl_stream_next_token(s); 2095 if (!tok || tok->type != '(') 2096 goto error; 2097 2098 if (isl_stream_next_token_is(s, '(')) 2099 if (resolve_paren_expr(s, v, isl_map_copy(map), rational)) 2100 goto error; 2101 2102 if (next_is_condition_start(s)) { 2103 map = read_formula(s, v, map, rational); 2104 if (isl_stream_eat(s, ')')) 2105 goto error; 2106 tok->type = ISL_TOKEN_MAP; 2107 tok->u.map = map; 2108 isl_stream_push_token(s, tok); 2109 return 0; 2110 } 2111 2112 tok2 = isl_stream_next_token(s); 2113 if (!tok2) 2114 goto error; 2115 line = tok2->line; 2116 col = tok2->col; 2117 isl_stream_push_token(s, tok2); 2118 2119 pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v); 2120 if (!pwaff) 2121 goto error; 2122 2123 has_paren = isl_stream_eat_if_available(s, ')'); 2124 2125 if (push_aff(s, line, col, pwaff) < 0) 2126 goto error; 2127 2128 if (has_paren) { 2129 isl_token_free(tok); 2130 isl_map_free(map); 2131 return 0; 2132 } 2133 2134 map = read_formula(s, v, map, rational); 2135 if (isl_stream_eat(s, ')')) 2136 goto error; 2137 2138 tok->type = ISL_TOKEN_MAP; 2139 tok->u.map = map; 2140 isl_stream_push_token(s, tok); 2141 2142 return 0; 2143error: 2144 isl_token_free(tok); 2145 isl_map_free(map); 2146 return -1; 2147} 2148 2149static __isl_give isl_map *read_conjunct(__isl_keep isl_stream *s, 2150 struct vars *v, __isl_take isl_map *map, int rational) 2151{ 2152 if (isl_stream_next_token_is(s, '(')) 2153 if (resolve_paren_expr(s, v, isl_map_copy(map), rational)) 2154 goto error; 2155 2156 if (isl_stream_next_token_is(s, ISL_TOKEN_MAP)) { 2157 struct isl_token *tok; 2158 tok = isl_stream_next_token(s); 2159 if (!tok) 2160 goto error; 2161 isl_map_free(map); 2162 map = isl_map_copy(tok->u.map); 2163 isl_token_free(tok); 2164 return map; 2165 } 2166 2167 if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS)) 2168 return read_exists(s, v, map, rational); 2169 2170 if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE)) 2171 return map; 2172 2173 if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) { 2174 isl_space *space = isl_map_get_space(map); 2175 isl_map_free(map); 2176 return isl_map_empty(space); 2177 } 2178 2179 return add_constraint(s, v, map, rational); 2180error: 2181 isl_map_free(map); 2182 return NULL; 2183} 2184 2185static __isl_give isl_map *read_conjuncts(__isl_keep isl_stream *s, 2186 struct vars *v, __isl_take isl_map *map, int rational) 2187{ 2188 isl_map *res; 2189 int negate; 2190 2191 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT); 2192 res = read_conjunct(s, v, isl_map_copy(map), rational); 2193 if (negate) 2194 res = isl_map_subtract(isl_map_copy(map), res); 2195 2196 while (res && isl_stream_eat_if_available(s, ISL_TOKEN_AND)) { 2197 isl_map *res_i; 2198 2199 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT); 2200 res_i = read_conjunct(s, v, isl_map_copy(map), rational); 2201 if (negate) 2202 res = isl_map_subtract(res, res_i); 2203 else 2204 res = isl_map_intersect(res, res_i); 2205 } 2206 2207 isl_map_free(map); 2208 return res; 2209} 2210 2211static __isl_give isl_map *read_disjuncts(__isl_keep isl_stream *s, 2212 struct vars *v, __isl_take isl_map *map, int rational) 2213{ 2214 isl_map *res; 2215 2216 if (isl_stream_next_token_is(s, '}')) 2217 return map; 2218 2219 res = read_conjuncts(s, v, isl_map_copy(map), rational); 2220 while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) { 2221 isl_map *res_i; 2222 2223 res_i = read_conjuncts(s, v, isl_map_copy(map), rational); 2224 res = isl_map_union(res, res_i); 2225 } 2226 2227 isl_map_free(map); 2228 return res; 2229} 2230 2231/* Read a first order formula from "s", add the corresponding 2232 * constraints to "map" and return the result. 2233 * 2234 * In particular, read a formula of the form 2235 * 2236 * a 2237 * 2238 * or 2239 * 2240 * a implies b 2241 * 2242 * where a and b are disjunctions. 2243 * 2244 * In the first case, map is replaced by 2245 * 2246 * map \cap { [..] : a } 2247 * 2248 * In the second case, it is replaced by 2249 * 2250 * (map \setminus { [..] : a}) \cup (map \cap { [..] : b }) 2251 */ 2252static __isl_give isl_map *read_formula(__isl_keep isl_stream *s, 2253 struct vars *v, __isl_take isl_map *map, int rational) 2254{ 2255 isl_map *res; 2256 2257 res = read_disjuncts(s, v, isl_map_copy(map), rational); 2258 2259 if (isl_stream_eat_if_available(s, ISL_TOKEN_IMPLIES)) { 2260 isl_map *res2; 2261 2262 res = isl_map_subtract(isl_map_copy(map), res); 2263 res2 = read_disjuncts(s, v, map, rational); 2264 res = isl_map_union(res, res2); 2265 } else 2266 isl_map_free(map); 2267 2268 return res; 2269} 2270 2271static isl_size polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos) 2272{ 2273 isl_size n_out, n_in, n_param, n_div; 2274 2275 n_param = isl_basic_map_dim(bmap, isl_dim_param); 2276 n_in = isl_basic_map_dim(bmap, isl_dim_in); 2277 n_out = isl_basic_map_dim(bmap, isl_dim_out); 2278 n_div = isl_basic_map_dim(bmap, isl_dim_div); 2279 if (n_param < 0 || n_in < 0 || n_out < 0 || n_div < 0) 2280 return isl_size_error; 2281 2282 if (pos < n_out) 2283 return 1 + n_param + n_in + pos; 2284 pos -= n_out; 2285 2286 if (pos < n_in) 2287 return 1 + n_param + pos; 2288 pos -= n_in; 2289 2290 if (pos < n_div) 2291 return 1 + n_param + n_in + n_out + pos; 2292 pos -= n_div; 2293 2294 if (pos < n_param) 2295 return 1 + pos; 2296 2297 return 0; 2298} 2299 2300static __isl_give isl_basic_map *basic_map_read_polylib_constraint( 2301 __isl_keep isl_stream *s, __isl_take isl_basic_map *bmap) 2302{ 2303 int j; 2304 struct isl_token *tok; 2305 int type; 2306 int k; 2307 isl_int *c; 2308 isl_size total; 2309 2310 if (!bmap) 2311 return NULL; 2312 2313 tok = isl_stream_next_token(s); 2314 if (!tok || tok->type != ISL_TOKEN_VALUE) { 2315 isl_stream_error(s, tok, "expecting coefficient"); 2316 isl_token_free(tok); 2317 goto error; 2318 } 2319 if (!tok->on_new_line) { 2320 isl_stream_error(s, tok, "coefficient should appear on new line"); 2321 isl_token_free(tok); 2322 goto error; 2323 } 2324 2325 type = isl_int_get_si(tok->u.v); 2326 isl_token_free(tok); 2327 2328 isl_assert(s->ctx, type == 0 || type == 1, goto error); 2329 if (type == 0) { 2330 k = isl_basic_map_alloc_equality(bmap); 2331 c = bmap->eq[k]; 2332 } else { 2333 k = isl_basic_map_alloc_inequality(bmap); 2334 c = bmap->ineq[k]; 2335 } 2336 if (k < 0) 2337 goto error; 2338 2339 total = isl_basic_map_dim(bmap, isl_dim_all); 2340 if (total < 0) 2341 return isl_basic_map_free(bmap); 2342 for (j = 0; j < 1 + total; ++j) { 2343 isl_size pos; 2344 tok = next_signed_value_on_same_line(s, 2345 "expecting coefficient on same line"); 2346 if (!tok) 2347 goto error; 2348 pos = polylib_pos_to_isl_pos(bmap, j); 2349 if (pos >= 0) 2350 isl_int_set(c[pos], tok->u.v); 2351 isl_token_free(tok); 2352 if (pos < 0) 2353 return isl_basic_map_free(bmap); 2354 } 2355 2356 return bmap; 2357error: 2358 isl_basic_map_free(bmap); 2359 return NULL; 2360} 2361 2362static __isl_give isl_basic_map *basic_map_read_polylib( 2363 __isl_keep isl_stream *s) 2364{ 2365 int i; 2366 struct isl_token *tok; 2367 struct isl_token *tok2; 2368 int n_row, n_col; 2369 int on_new_line; 2370 unsigned in = 0, out, local = 0; 2371 struct isl_basic_map *bmap = NULL; 2372 int nparam = 0; 2373 2374 tok = isl_stream_next_token(s); 2375 if (!tok) { 2376 isl_stream_error(s, NULL, "unexpected EOF"); 2377 return NULL; 2378 } 2379 tok2 = isl_stream_next_token(s); 2380 if (!tok2) { 2381 isl_token_free(tok); 2382 isl_stream_error(s, NULL, "unexpected EOF"); 2383 return NULL; 2384 } 2385 if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) { 2386 isl_token_free(tok2); 2387 isl_token_free(tok); 2388 isl_stream_error(s, NULL, 2389 "expecting constraint matrix dimensions"); 2390 return NULL; 2391 } 2392 n_row = isl_int_get_si(tok->u.v); 2393 n_col = isl_int_get_si(tok2->u.v); 2394 on_new_line = tok2->on_new_line; 2395 isl_token_free(tok2); 2396 isl_token_free(tok); 2397 isl_assert(s->ctx, !on_new_line, return NULL); 2398 isl_assert(s->ctx, n_row >= 0, return NULL); 2399 isl_assert(s->ctx, n_col >= 2 + nparam, return NULL); 2400 tok = isl_stream_next_token_on_same_line(s); 2401 if (tok) { 2402 if (tok->type != ISL_TOKEN_VALUE) { 2403 isl_stream_error(s, tok, 2404 "expecting number of output dimensions"); 2405 isl_token_free(tok); 2406 goto error; 2407 } 2408 out = isl_int_get_si(tok->u.v); 2409 isl_token_free(tok); 2410 2411 tok = isl_stream_next_token_on_same_line(s); 2412 if (!tok || tok->type != ISL_TOKEN_VALUE) { 2413 isl_stream_error(s, tok, 2414 "expecting number of input dimensions"); 2415 isl_token_free(tok); 2416 goto error; 2417 } 2418 in = isl_int_get_si(tok->u.v); 2419 isl_token_free(tok); 2420 2421 tok = isl_stream_next_token_on_same_line(s); 2422 if (!tok || tok->type != ISL_TOKEN_VALUE) { 2423 isl_stream_error(s, tok, 2424 "expecting number of existentials"); 2425 isl_token_free(tok); 2426 goto error; 2427 } 2428 local = isl_int_get_si(tok->u.v); 2429 isl_token_free(tok); 2430 2431 tok = isl_stream_next_token_on_same_line(s); 2432 if (!tok || tok->type != ISL_TOKEN_VALUE) { 2433 isl_stream_error(s, tok, 2434 "expecting number of parameters"); 2435 isl_token_free(tok); 2436 goto error; 2437 } 2438 nparam = isl_int_get_si(tok->u.v); 2439 isl_token_free(tok); 2440 if (n_col != 1 + out + in + local + nparam + 1) { 2441 isl_stream_error(s, NULL, 2442 "dimensions don't match"); 2443 goto error; 2444 } 2445 } else 2446 out = n_col - 2 - nparam; 2447 bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row); 2448 if (!bmap) 2449 return NULL; 2450 2451 for (i = 0; i < local; ++i) { 2452 int k = isl_basic_map_alloc_div(bmap); 2453 if (k < 0) 2454 goto error; 2455 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local); 2456 } 2457 2458 for (i = 0; i < n_row; ++i) 2459 bmap = basic_map_read_polylib_constraint(s, bmap); 2460 2461 if (!bmap) 2462 return NULL; 2463 2464 tok = isl_stream_next_token_on_same_line(s); 2465 if (tok) { 2466 isl_stream_error(s, tok, "unexpected extra token on line"); 2467 isl_token_free(tok); 2468 goto error; 2469 } 2470 2471 bmap = isl_basic_map_simplify(bmap); 2472 bmap = isl_basic_map_finalize(bmap); 2473 return bmap; 2474error: 2475 isl_basic_map_free(bmap); 2476 return NULL; 2477} 2478 2479static __isl_give isl_map *map_read_polylib(__isl_keep isl_stream *s) 2480{ 2481 struct isl_token *tok; 2482 struct isl_token *tok2; 2483 int i, n; 2484 struct isl_map *map; 2485 2486 tok = isl_stream_next_token(s); 2487 if (!tok) { 2488 isl_stream_error(s, NULL, "unexpected EOF"); 2489 return NULL; 2490 } 2491 tok2 = isl_stream_next_token_on_same_line(s); 2492 if (tok2 && tok2->type == ISL_TOKEN_VALUE) { 2493 isl_stream_push_token(s, tok2); 2494 isl_stream_push_token(s, tok); 2495 return isl_map_from_basic_map(basic_map_read_polylib(s)); 2496 } 2497 if (tok2) { 2498 isl_stream_error(s, tok2, "unexpected token"); 2499 isl_stream_push_token(s, tok2); 2500 isl_stream_push_token(s, tok); 2501 return NULL; 2502 } 2503 n = isl_int_get_si(tok->u.v); 2504 isl_token_free(tok); 2505 2506 isl_assert(s->ctx, n >= 1, return NULL); 2507 2508 map = isl_map_from_basic_map(basic_map_read_polylib(s)); 2509 2510 for (i = 1; map && i < n; ++i) 2511 map = isl_map_union(map, 2512 isl_map_from_basic_map(basic_map_read_polylib(s))); 2513 2514 return map; 2515} 2516 2517static int optional_power(__isl_keep isl_stream *s) 2518{ 2519 int pow; 2520 struct isl_token *tok; 2521 2522 tok = isl_stream_next_token(s); 2523 if (!tok) 2524 return 1; 2525 if (tok->type != '^') { 2526 isl_stream_push_token(s, tok); 2527 return 1; 2528 } 2529 isl_token_free(tok); 2530 tok = isl_stream_next_token(s); 2531 if (!tok || tok->type != ISL_TOKEN_VALUE) { 2532 isl_stream_error(s, tok, "expecting exponent"); 2533 if (tok) 2534 isl_stream_push_token(s, tok); 2535 return 1; 2536 } 2537 pow = isl_int_get_si(tok->u.v); 2538 isl_token_free(tok); 2539 return pow; 2540} 2541 2542static __isl_give isl_pw_qpolynomial *read_term(__isl_keep isl_stream *s, 2543 __isl_keep isl_map *map, struct vars *v); 2544 2545static __isl_give isl_pw_qpolynomial *read_factor(__isl_keep isl_stream *s, 2546 __isl_keep isl_map *map, struct vars *v) 2547{ 2548 isl_pw_qpolynomial *pwqp; 2549 struct isl_token *tok; 2550 2551 tok = next_token(s); 2552 if (!tok) { 2553 isl_stream_error(s, NULL, "unexpected EOF"); 2554 return NULL; 2555 } 2556 if (tok->type == '(') { 2557 int pow; 2558 2559 isl_token_free(tok); 2560 pwqp = read_term(s, map, v); 2561 if (!pwqp) 2562 return NULL; 2563 if (isl_stream_eat(s, ')')) 2564 goto error; 2565 pow = optional_power(s); 2566 pwqp = isl_pw_qpolynomial_pow(pwqp, pow); 2567 } else if (tok->type == ISL_TOKEN_VALUE) { 2568 struct isl_token *tok2; 2569 isl_qpolynomial *qp; 2570 2571 tok2 = isl_stream_next_token(s); 2572 if (tok2 && tok2->type == '/') { 2573 isl_token_free(tok2); 2574 tok2 = next_token(s); 2575 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) { 2576 isl_stream_error(s, tok2, "expected denominator"); 2577 isl_token_free(tok); 2578 isl_token_free(tok2); 2579 return NULL; 2580 } 2581 qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map), 2582 tok->u.v, tok2->u.v); 2583 isl_token_free(tok2); 2584 } else { 2585 isl_stream_push_token(s, tok2); 2586 qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map), 2587 tok->u.v); 2588 } 2589 isl_token_free(tok); 2590 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp); 2591 } else if (tok->type == ISL_TOKEN_INFTY) { 2592 isl_qpolynomial *qp; 2593 isl_token_free(tok); 2594 qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map)); 2595 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp); 2596 } else if (tok->type == ISL_TOKEN_NAN) { 2597 isl_qpolynomial *qp; 2598 isl_token_free(tok); 2599 qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map)); 2600 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp); 2601 } else if (tok->type == ISL_TOKEN_IDENT) { 2602 int n = v->n; 2603 int pos = vars_pos(v, tok->u.s, -1); 2604 int pow; 2605 isl_qpolynomial *qp; 2606 if (pos < 0) { 2607 isl_token_free(tok); 2608 return NULL; 2609 } 2610 if (pos >= n) { 2611 vars_drop(v, v->n - n); 2612 isl_stream_error(s, tok, "unknown identifier"); 2613 isl_token_free(tok); 2614 return NULL; 2615 } 2616 isl_token_free(tok); 2617 pow = optional_power(s); 2618 qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow); 2619 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp); 2620 } else if (is_start_of_div(tok)) { 2621 isl_pw_aff *pwaff; 2622 int pow; 2623 2624 isl_stream_push_token(s, tok); 2625 pwaff = accept_div(s, isl_map_get_space(map), v); 2626 pow = optional_power(s); 2627 pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff); 2628 pwqp = isl_pw_qpolynomial_pow(pwqp, pow); 2629 } else if (tok->type == '-') { 2630 isl_token_free(tok); 2631 pwqp = read_factor(s, map, v); 2632 pwqp = isl_pw_qpolynomial_neg(pwqp); 2633 } else { 2634 isl_stream_error(s, tok, "unexpected isl_token"); 2635 isl_stream_push_token(s, tok); 2636 return NULL; 2637 } 2638 2639 if (isl_stream_eat_if_available(s, '*') || 2640 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) { 2641 isl_pw_qpolynomial *pwqp2; 2642 2643 pwqp2 = read_factor(s, map, v); 2644 pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2); 2645 } 2646 2647 return pwqp; 2648error: 2649 isl_pw_qpolynomial_free(pwqp); 2650 return NULL; 2651} 2652 2653static __isl_give isl_pw_qpolynomial *read_term(__isl_keep isl_stream *s, 2654 __isl_keep isl_map *map, struct vars *v) 2655{ 2656 struct isl_token *tok; 2657 isl_pw_qpolynomial *pwqp; 2658 2659 pwqp = read_factor(s, map, v); 2660 2661 for (;;) { 2662 tok = next_token(s); 2663 if (!tok) 2664 return pwqp; 2665 2666 if (tok->type == '+') { 2667 isl_pw_qpolynomial *pwqp2; 2668 2669 isl_token_free(tok); 2670 pwqp2 = read_factor(s, map, v); 2671 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2); 2672 } else if (tok->type == '-') { 2673 isl_pw_qpolynomial *pwqp2; 2674 2675 isl_token_free(tok); 2676 pwqp2 = read_factor(s, map, v); 2677 pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2); 2678 } else { 2679 isl_stream_push_token(s, tok); 2680 break; 2681 } 2682 } 2683 2684 return pwqp; 2685} 2686 2687static __isl_give isl_map *read_optional_formula(__isl_keep isl_stream *s, 2688 __isl_take isl_map *map, struct vars *v, int rational) 2689{ 2690 struct isl_token *tok; 2691 2692 tok = isl_stream_next_token(s); 2693 if (!tok) { 2694 isl_stream_error(s, NULL, "unexpected EOF"); 2695 goto error; 2696 } 2697 if (tok->type == ':' || 2698 (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) { 2699 isl_token_free(tok); 2700 map = read_formula(s, v, map, rational); 2701 } else 2702 isl_stream_push_token(s, tok); 2703 2704 return map; 2705error: 2706 isl_map_free(map); 2707 return NULL; 2708} 2709 2710static struct isl_obj obj_read_poly(__isl_keep isl_stream *s, 2711 __isl_take isl_map *map, struct vars *v, int n) 2712{ 2713 struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL }; 2714 isl_pw_qpolynomial *pwqp; 2715 struct isl_set *set; 2716 2717 pwqp = read_term(s, map, v); 2718 map = read_optional_formula(s, map, v, 0); 2719 set = isl_map_range(map); 2720 2721 pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set); 2722 2723 vars_drop(v, v->n - n); 2724 2725 obj.v = pwqp; 2726 return obj; 2727} 2728 2729static struct isl_obj obj_read_poly_or_fold(__isl_keep isl_stream *s, 2730 __isl_take isl_set *set, struct vars *v, int n) 2731{ 2732 int min, max; 2733 struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL }; 2734 isl_pw_qpolynomial *pwqp; 2735 isl_pw_qpolynomial_fold *pwf = NULL; 2736 enum isl_fold fold; 2737 2738 max = isl_stream_eat_if_available(s, ISL_TOKEN_MAX); 2739 min = !max && isl_stream_eat_if_available(s, ISL_TOKEN_MIN); 2740 if (!min && !max) 2741 return obj_read_poly(s, set, v, n); 2742 fold = max ? isl_fold_max : isl_fold_min; 2743 2744 if (isl_stream_eat(s, '(')) 2745 goto error; 2746 2747 pwqp = read_term(s, set, v); 2748 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(fold, pwqp); 2749 2750 while (isl_stream_eat_if_available(s, ',')) { 2751 isl_pw_qpolynomial_fold *pwf_i; 2752 pwqp = read_term(s, set, v); 2753 pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(fold, pwqp); 2754 pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i); 2755 } 2756 2757 if (isl_stream_eat(s, ')')) 2758 goto error; 2759 2760 set = read_optional_formula(s, set, v, 0); 2761 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set); 2762 2763 vars_drop(v, v->n - n); 2764 2765 obj.v = pwf; 2766 return obj; 2767error: 2768 isl_set_free(set); 2769 isl_pw_qpolynomial_fold_free(pwf); 2770 obj.type = isl_obj_none; 2771 return obj; 2772} 2773 2774static int is_rational(__isl_keep isl_stream *s) 2775{ 2776 struct isl_token *tok; 2777 2778 tok = isl_stream_next_token(s); 2779 if (!tok) 2780 return 0; 2781 if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) { 2782 isl_token_free(tok); 2783 isl_stream_eat(s, ':'); 2784 return 1; 2785 } 2786 2787 isl_stream_push_token(s, tok); 2788 2789 return 0; 2790} 2791 2792static struct isl_obj obj_read_body(__isl_keep isl_stream *s, 2793 __isl_take isl_map *map, struct vars *v) 2794{ 2795 struct isl_token *tok; 2796 struct isl_obj obj = { isl_obj_set, NULL }; 2797 int n = v->n; 2798 int rational; 2799 2800 rational = is_rational(s); 2801 if (rational) 2802 map = isl_map_set_rational(map); 2803 2804 if (isl_stream_next_token_is(s, ':')) { 2805 obj.type = isl_obj_set; 2806 obj.v = read_optional_formula(s, map, v, rational); 2807 return obj; 2808 } 2809 2810 if (!next_is_tuple(s)) 2811 return obj_read_poly_or_fold(s, map, v, n); 2812 2813 map = read_map_tuple(s, map, isl_dim_in, v, 0); 2814 if (!map) 2815 goto error; 2816 tok = isl_stream_next_token(s); 2817 if (!tok) 2818 goto error; 2819 if (tok->type == ISL_TOKEN_TO) { 2820 obj.type = isl_obj_map; 2821 isl_token_free(tok); 2822 if (!next_is_tuple(s)) { 2823 isl_set *set = isl_map_domain(map); 2824 return obj_read_poly_or_fold(s, set, v, n); 2825 } 2826 map = read_map_tuple(s, map, isl_dim_out, v, 0); 2827 if (!map) 2828 goto error; 2829 } else { 2830 map = isl_map_domain(map); 2831 isl_stream_push_token(s, tok); 2832 } 2833 2834 map = read_optional_formula(s, map, v, rational); 2835 2836 vars_drop(v, v->n - n); 2837 2838 obj.v = map; 2839 return obj; 2840error: 2841 isl_map_free(map); 2842 obj.type = isl_obj_none; 2843 return obj; 2844} 2845 2846static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj) 2847{ 2848 if (obj.type == isl_obj_map) { 2849 obj.v = isl_union_map_from_map(obj.v); 2850 obj.type = isl_obj_union_map; 2851 } else if (obj.type == isl_obj_set) { 2852 obj.v = isl_union_set_from_set(obj.v); 2853 obj.type = isl_obj_union_set; 2854 } else if (obj.type == isl_obj_pw_qpolynomial) { 2855 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v); 2856 obj.type = isl_obj_union_pw_qpolynomial; 2857 } else if (obj.type == isl_obj_pw_qpolynomial_fold) { 2858 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v); 2859 obj.type = isl_obj_union_pw_qpolynomial_fold; 2860 } else 2861 isl_assert(ctx, 0, goto error); 2862 return obj; 2863error: 2864 obj.type->free(obj.v); 2865 obj.type = isl_obj_none; 2866 return obj; 2867} 2868 2869static struct isl_obj obj_add(__isl_keep isl_stream *s, 2870 struct isl_obj obj1, struct isl_obj obj2) 2871{ 2872 if (obj2.type == isl_obj_none || !obj2.v) 2873 goto error; 2874 if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set) 2875 obj1 = to_union(s->ctx, obj1); 2876 if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set) 2877 obj2 = to_union(s->ctx, obj2); 2878 if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map) 2879 obj1 = to_union(s->ctx, obj1); 2880 if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map) 2881 obj2 = to_union(s->ctx, obj2); 2882 if (obj1.type == isl_obj_pw_qpolynomial && 2883 obj2.type == isl_obj_union_pw_qpolynomial) 2884 obj1 = to_union(s->ctx, obj1); 2885 if (obj1.type == isl_obj_union_pw_qpolynomial && 2886 obj2.type == isl_obj_pw_qpolynomial) 2887 obj2 = to_union(s->ctx, obj2); 2888 if (obj1.type == isl_obj_pw_qpolynomial_fold && 2889 obj2.type == isl_obj_union_pw_qpolynomial_fold) 2890 obj1 = to_union(s->ctx, obj1); 2891 if (obj1.type == isl_obj_union_pw_qpolynomial_fold && 2892 obj2.type == isl_obj_pw_qpolynomial_fold) 2893 obj2 = to_union(s->ctx, obj2); 2894 if (obj1.type != obj2.type) { 2895 isl_stream_error(s, NULL, 2896 "attempt to combine incompatible objects"); 2897 goto error; 2898 } 2899 if (!obj1.type->add) 2900 isl_die(s->ctx, isl_error_internal, 2901 "combination not supported on object type", goto error); 2902 if (obj1.type == isl_obj_map && !isl_map_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_set && !isl_set_has_equal_space(obj1.v, obj2.v)) { 2907 obj1 = to_union(s->ctx, obj1); 2908 obj2 = to_union(s->ctx, obj2); 2909 } 2910 if (obj1.type == isl_obj_pw_qpolynomial && 2911 !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) { 2912 obj1 = to_union(s->ctx, obj1); 2913 obj2 = to_union(s->ctx, obj2); 2914 } 2915 if (obj1.type == isl_obj_pw_qpolynomial_fold && 2916 !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) { 2917 obj1 = to_union(s->ctx, obj1); 2918 obj2 = to_union(s->ctx, obj2); 2919 } 2920 obj1.v = obj1.type->add(obj1.v, obj2.v); 2921 return obj1; 2922error: 2923 obj1.type->free(obj1.v); 2924 obj2.type->free(obj2.v); 2925 obj1.type = isl_obj_none; 2926 obj1.v = NULL; 2927 return obj1; 2928} 2929 2930/* Are the first two tokens on "s", "domain" (either as a string 2931 * or as an identifier) followed by ":"? 2932 */ 2933static int next_is_domain_colon(__isl_keep isl_stream *s) 2934{ 2935 struct isl_token *tok; 2936 char *name; 2937 int res; 2938 2939 tok = isl_stream_next_token(s); 2940 if (!tok) 2941 return 0; 2942 if (tok->type != ISL_TOKEN_IDENT && tok->type != ISL_TOKEN_STRING) { 2943 isl_stream_push_token(s, tok); 2944 return 0; 2945 } 2946 2947 name = isl_token_get_str(s->ctx, tok); 2948 res = !strcmp(name, "domain") && isl_stream_next_token_is(s, ':'); 2949 free(name); 2950 2951 isl_stream_push_token(s, tok); 2952 2953 return res; 2954} 2955 2956/* Do the first tokens on "s" look like a schedule? 2957 * 2958 * The root of a schedule is always a domain node, so the first thing 2959 * we expect in the stream is a domain key, i.e., "domain" followed 2960 * by ":". If the schedule was printed in YAML flow style, then 2961 * we additionally expect a "{" to open the outer mapping. 2962 */ 2963static int next_is_schedule(__isl_keep isl_stream *s) 2964{ 2965 struct isl_token *tok; 2966 int is_schedule; 2967 2968 tok = isl_stream_next_token(s); 2969 if (!tok) 2970 return 0; 2971 if (tok->type != '{') { 2972 isl_stream_push_token(s, tok); 2973 return next_is_domain_colon(s); 2974 } 2975 2976 is_schedule = next_is_domain_colon(s); 2977 isl_stream_push_token(s, tok); 2978 2979 return is_schedule; 2980} 2981 2982/* Read an isl_schedule from "s" and store it in an isl_obj. 2983 */ 2984static struct isl_obj schedule_read(__isl_keep isl_stream *s) 2985{ 2986 struct isl_obj obj; 2987 2988 obj.type = isl_obj_schedule; 2989 obj.v = isl_stream_read_schedule(s); 2990 2991 return obj; 2992} 2993 2994/* Read a disjunction of object bodies from "s". 2995 * That is, read the inside of the braces, but not the braces themselves. 2996 * "v" contains a description of the identifiers parsed so far. 2997 * "map" contains information about the parameters. 2998 */ 2999static struct isl_obj obj_read_disjuncts(__isl_keep isl_stream *s, 3000 struct vars *v, __isl_keep isl_map *map) 3001{ 3002 struct isl_obj obj = { isl_obj_set, NULL }; 3003 3004 if (isl_stream_next_token_is(s, '}')) { 3005 obj.type = isl_obj_union_set; 3006 obj.v = isl_union_set_empty(isl_map_get_space(map)); 3007 return obj; 3008 } 3009 3010 for (;;) { 3011 struct isl_obj o; 3012 o = obj_read_body(s, isl_map_copy(map), v); 3013 if (!obj.v) 3014 obj = o; 3015 else 3016 obj = obj_add(s, obj, o); 3017 if (obj.type == isl_obj_none || !obj.v) 3018 return obj; 3019 if (!isl_stream_eat_if_available(s, ';')) 3020 break; 3021 if (isl_stream_next_token_is(s, '}')) 3022 break; 3023 } 3024 3025 return obj; 3026} 3027 3028static struct isl_obj obj_read(__isl_keep isl_stream *s) 3029{ 3030 isl_map *map = NULL; 3031 struct isl_token *tok; 3032 struct vars *v = NULL; 3033 struct isl_obj obj = { isl_obj_set, NULL }; 3034 3035 if (next_is_schedule(s)) 3036 return schedule_read(s); 3037 3038 tok = next_token(s); 3039 if (!tok) { 3040 isl_stream_error(s, NULL, "unexpected EOF"); 3041 goto error; 3042 } 3043 if (tok->type == ISL_TOKEN_VALUE) { 3044 struct isl_token *tok2; 3045 struct isl_map *map; 3046 3047 tok2 = isl_stream_next_token(s); 3048 if (!tok2 || tok2->type != ISL_TOKEN_VALUE || 3049 isl_int_is_neg(tok2->u.v)) { 3050 if (tok2) 3051 isl_stream_push_token(s, tok2); 3052 obj.type = isl_obj_val; 3053 obj.v = isl_val_int_from_isl_int(s->ctx, tok->u.v); 3054 isl_token_free(tok); 3055 return obj; 3056 } 3057 isl_stream_push_token(s, tok2); 3058 isl_stream_push_token(s, tok); 3059 map = map_read_polylib(s); 3060 if (!map) 3061 goto error; 3062 if (isl_map_may_be_set(map)) 3063 obj.v = isl_map_range(map); 3064 else { 3065 obj.type = isl_obj_map; 3066 obj.v = map; 3067 } 3068 return obj; 3069 } 3070 v = vars_new(s->ctx); 3071 if (!v) { 3072 isl_stream_push_token(s, tok); 3073 goto error; 3074 } 3075 map = isl_map_universe(isl_space_params_alloc(s->ctx, 0)); 3076 if (tok->type == '[') { 3077 isl_stream_push_token(s, tok); 3078 map = read_map_tuple(s, map, isl_dim_param, v, 0); 3079 if (!map) 3080 goto error; 3081 tok = isl_stream_next_token(s); 3082 if (!tok || tok->type != ISL_TOKEN_TO) { 3083 isl_stream_error(s, tok, "expecting '->'"); 3084 if (tok) 3085 isl_stream_push_token(s, tok); 3086 goto error; 3087 } 3088 isl_token_free(tok); 3089 tok = isl_stream_next_token(s); 3090 } 3091 if (!tok || tok->type != '{') { 3092 isl_stream_error(s, tok, "expecting '{'"); 3093 if (tok) 3094 isl_stream_push_token(s, tok); 3095 goto error; 3096 } 3097 isl_token_free(tok); 3098 3099 tok = isl_stream_next_token(s); 3100 if (!tok) 3101 ; 3102 else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) { 3103 isl_token_free(tok); 3104 if (isl_stream_eat(s, '=')) 3105 goto error; 3106 map = read_map_tuple(s, map, isl_dim_param, v, 1); 3107 if (!map) 3108 goto error; 3109 } else 3110 isl_stream_push_token(s, tok); 3111 3112 obj = obj_read_disjuncts(s, v, map); 3113 if (obj.type == isl_obj_none || !obj.v) 3114 goto error; 3115 3116 tok = isl_stream_next_token(s); 3117 if (tok && tok->type == '}') { 3118 isl_token_free(tok); 3119 } else { 3120 isl_stream_error(s, tok, "unexpected isl_token"); 3121 if (tok) 3122 isl_token_free(tok); 3123 goto error; 3124 } 3125 3126 vars_free(v); 3127 isl_map_free(map); 3128 3129 return obj; 3130error: 3131 isl_map_free(map); 3132 obj.type->free(obj.v); 3133 if (v) 3134 vars_free(v); 3135 obj.v = NULL; 3136 return obj; 3137} 3138 3139struct isl_obj isl_stream_read_obj(__isl_keep isl_stream *s) 3140{ 3141 return obj_read(s); 3142} 3143 3144__isl_give isl_map *isl_stream_read_map(__isl_keep isl_stream *s) 3145{ 3146 struct isl_obj obj; 3147 3148 obj = obj_read(s); 3149 if (obj.v) 3150 isl_assert(s->ctx, obj.type == isl_obj_map || 3151 obj.type == isl_obj_set, goto error); 3152 3153 if (obj.type == isl_obj_set) 3154 obj.v = isl_map_from_range(obj.v); 3155 3156 return obj.v; 3157error: 3158 obj.type->free(obj.v); 3159 return NULL; 3160} 3161 3162__isl_give isl_set *isl_stream_read_set(__isl_keep isl_stream *s) 3163{ 3164 struct isl_obj obj; 3165 3166 obj = obj_read(s); 3167 if (obj.v) { 3168 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) { 3169 obj.v = isl_map_range(obj.v); 3170 obj.type = isl_obj_set; 3171 } 3172 isl_assert(s->ctx, obj.type == isl_obj_set, goto error); 3173 } 3174 3175 return obj.v; 3176error: 3177 obj.type->free(obj.v); 3178 return NULL; 3179} 3180 3181__isl_give isl_union_map *isl_stream_read_union_map(__isl_keep isl_stream *s) 3182{ 3183 struct isl_obj obj; 3184 3185 obj = obj_read(s); 3186 if (obj.type == isl_obj_map) { 3187 obj.type = isl_obj_union_map; 3188 obj.v = isl_union_map_from_map(obj.v); 3189 } 3190 if (obj.type == isl_obj_set) { 3191 obj.type = isl_obj_union_set; 3192 obj.v = isl_union_set_from_set(obj.v); 3193 } 3194 if (obj.v && obj.type == isl_obj_union_set && 3195 isl_union_set_is_empty(obj.v)) 3196 obj.type = isl_obj_union_map; 3197 if (obj.v && obj.type != isl_obj_union_map) 3198 isl_die(s->ctx, isl_error_invalid, "invalid input", goto error); 3199 3200 return obj.v; 3201error: 3202 obj.type->free(obj.v); 3203 return NULL; 3204} 3205 3206/* Extract an isl_union_set from "obj". 3207 * This only works if the object was detected as either a set 3208 * (in which case it is converted to a union set) or a union set. 3209 */ 3210static __isl_give isl_union_set *extract_union_set(isl_ctx *ctx, 3211 struct isl_obj obj) 3212{ 3213 if (obj.type == isl_obj_set) { 3214 obj.type = isl_obj_union_set; 3215 obj.v = isl_union_set_from_set(obj.v); 3216 } 3217 if (obj.v) 3218 isl_assert(ctx, obj.type == isl_obj_union_set, goto error); 3219 3220 return obj.v; 3221error: 3222 obj.type->free(obj.v); 3223 return NULL; 3224} 3225 3226/* Read an isl_union_set from "s". 3227 * First read a generic object and then try and extract 3228 * an isl_union_set from that. 3229 */ 3230__isl_give isl_union_set *isl_stream_read_union_set(__isl_keep isl_stream *s) 3231{ 3232 struct isl_obj obj; 3233 3234 obj = obj_read(s); 3235 return extract_union_set(s->ctx, obj); 3236} 3237 3238static __isl_give isl_basic_map *isl_stream_read_basic_map( 3239 __isl_keep isl_stream *s) 3240{ 3241 struct isl_obj obj; 3242 struct isl_map *map; 3243 struct isl_basic_map *bmap; 3244 3245 obj = obj_read(s); 3246 if (obj.v && (obj.type != isl_obj_map && obj.type != isl_obj_set)) 3247 isl_die(s->ctx, isl_error_invalid, "not a (basic) set or map", 3248 goto error); 3249 map = obj.v; 3250 if (!map) 3251 return NULL; 3252 3253 if (map->n > 1) 3254 isl_die(s->ctx, isl_error_invalid, 3255 "set or map description involves " 3256 "more than one disjunct", goto error); 3257 3258 if (map->n == 0) 3259 bmap = isl_basic_map_empty(isl_map_get_space(map)); 3260 else 3261 bmap = isl_basic_map_copy(map->p[0]); 3262 3263 isl_map_free(map); 3264 3265 return bmap; 3266error: 3267 obj.type->free(obj.v); 3268 return NULL; 3269} 3270 3271/* Read an isl_basic_set object from "s". 3272 */ 3273__isl_give isl_basic_set *isl_stream_read_basic_set(__isl_keep isl_stream *s) 3274{ 3275 isl_basic_map *bmap; 3276 bmap = isl_stream_read_basic_map(s); 3277 if (!bmap) 3278 return NULL; 3279 if (!isl_basic_map_may_be_set(bmap)) 3280 isl_die(s->ctx, isl_error_invalid, 3281 "input is not a set", goto error); 3282 return isl_basic_map_range(bmap); 3283error: 3284 isl_basic_map_free(bmap); 3285 return NULL; 3286} 3287 3288__isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx, 3289 FILE *input) 3290{ 3291 struct isl_basic_map *bmap; 3292 isl_stream *s = isl_stream_new_file(ctx, input); 3293 if (!s) 3294 return NULL; 3295 bmap = isl_stream_read_basic_map(s); 3296 isl_stream_free(s); 3297 return bmap; 3298} 3299 3300__isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx, 3301 FILE *input) 3302{ 3303 isl_basic_set *bset; 3304 isl_stream *s = isl_stream_new_file(ctx, input); 3305 if (!s) 3306 return NULL; 3307 bset = isl_stream_read_basic_set(s); 3308 isl_stream_free(s); 3309 return bset; 3310} 3311 3312#undef TYPE_BASE 3313#define TYPE_BASE basic_map 3314#include "isl_read_from_str_templ.c" 3315 3316#undef TYPE_BASE 3317#define TYPE_BASE basic_set 3318#include "isl_read_from_str_templ.c" 3319 3320__isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx, 3321 FILE *input) 3322{ 3323 struct isl_map *map; 3324 isl_stream *s = isl_stream_new_file(ctx, input); 3325 if (!s) 3326 return NULL; 3327 map = isl_stream_read_map(s); 3328 isl_stream_free(s); 3329 return map; 3330} 3331 3332#undef TYPE_BASE 3333#define TYPE_BASE map 3334#include "isl_read_from_str_templ.c" 3335 3336__isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx, 3337 FILE *input) 3338{ 3339 isl_set *set; 3340 isl_stream *s = isl_stream_new_file(ctx, input); 3341 if (!s) 3342 return NULL; 3343 set = isl_stream_read_set(s); 3344 isl_stream_free(s); 3345 return set; 3346} 3347 3348#undef TYPE_BASE 3349#define TYPE_BASE set 3350#include "isl_read_from_str_templ.c" 3351 3352__isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx, 3353 FILE *input) 3354{ 3355 isl_union_map *umap; 3356 isl_stream *s = isl_stream_new_file(ctx, input); 3357 if (!s) 3358 return NULL; 3359 umap = isl_stream_read_union_map(s); 3360 isl_stream_free(s); 3361 return umap; 3362} 3363 3364#undef TYPE_BASE 3365#define TYPE_BASE union_map 3366#include "isl_read_from_str_templ.c" 3367 3368__isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx, 3369 FILE *input) 3370{ 3371 isl_union_set *uset; 3372 isl_stream *s = isl_stream_new_file(ctx, input); 3373 if (!s) 3374 return NULL; 3375 uset = isl_stream_read_union_set(s); 3376 isl_stream_free(s); 3377 return uset; 3378} 3379 3380#undef TYPE_BASE 3381#define TYPE_BASE union_set 3382#include "isl_read_from_str_templ.c" 3383 3384static __isl_give isl_vec *isl_vec_read_polylib(__isl_keep isl_stream *s) 3385{ 3386 struct isl_vec *vec = NULL; 3387 struct isl_token *tok; 3388 unsigned size; 3389 int j; 3390 3391 tok = isl_stream_next_token(s); 3392 if (!tok || tok->type != ISL_TOKEN_VALUE) { 3393 isl_stream_error(s, tok, "expecting vector length"); 3394 goto error; 3395 } 3396 3397 size = isl_int_get_si(tok->u.v); 3398 isl_token_free(tok); 3399 3400 vec = isl_vec_alloc(s->ctx, size); 3401 3402 for (j = 0; j < size; ++j) { 3403 tok = next_signed_value(s, "expecting constant value"); 3404 if (!tok) 3405 goto error; 3406 isl_int_set(vec->el[j], tok->u.v); 3407 isl_token_free(tok); 3408 } 3409 3410 return vec; 3411error: 3412 isl_token_free(tok); 3413 isl_vec_free(vec); 3414 return NULL; 3415} 3416 3417static __isl_give isl_vec *vec_read(__isl_keep isl_stream *s) 3418{ 3419 return isl_vec_read_polylib(s); 3420} 3421 3422__isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input) 3423{ 3424 isl_vec *v; 3425 isl_stream *s = isl_stream_new_file(ctx, input); 3426 if (!s) 3427 return NULL; 3428 v = vec_read(s); 3429 isl_stream_free(s); 3430 return v; 3431} 3432 3433__isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial( 3434 __isl_keep isl_stream *s) 3435{ 3436 struct isl_obj obj; 3437 3438 obj = obj_read(s); 3439 if (obj.v) 3440 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial, 3441 goto error); 3442 3443 return obj.v; 3444error: 3445 obj.type->free(obj.v); 3446 return NULL; 3447} 3448 3449#undef TYPE_BASE 3450#define TYPE_BASE pw_qpolynomial 3451#include "isl_read_from_str_templ.c" 3452 3453__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx, 3454 FILE *input) 3455{ 3456 isl_pw_qpolynomial *pwqp; 3457 isl_stream *s = isl_stream_new_file(ctx, input); 3458 if (!s) 3459 return NULL; 3460 pwqp = isl_stream_read_pw_qpolynomial(s); 3461 isl_stream_free(s); 3462 return pwqp; 3463} 3464 3465/* Read an isl_pw_qpolynomial_fold from "s". 3466 * First read a generic object and 3467 * then check that it is an isl_pw_qpolynomial_fold. 3468 */ 3469__isl_give isl_pw_qpolynomial_fold *isl_stream_read_pw_qpolynomial_fold( 3470 __isl_keep isl_stream *s) 3471{ 3472 struct isl_obj obj; 3473 3474 obj = obj_read(s); 3475 if (obj.v && obj.type != isl_obj_pw_qpolynomial_fold) 3476 isl_die(s->ctx, isl_error_invalid, "invalid input", goto error); 3477 3478 return obj.v; 3479error: 3480 obj.type->free(obj.v); 3481 return NULL; 3482} 3483 3484#undef TYPE_BASE 3485#define TYPE_BASE pw_qpolynomial_fold 3486#include "isl_read_from_str_templ.c" 3487 3488/* Is the next token an identifier not in "v"? 3489 */ 3490static int next_is_fresh_ident(__isl_keep isl_stream *s, struct vars *v) 3491{ 3492 int n = v->n; 3493 int fresh; 3494 struct isl_token *tok; 3495 3496 tok = isl_stream_next_token(s); 3497 if (!tok) 3498 return 0; 3499 fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n; 3500 isl_stream_push_token(s, tok); 3501 3502 vars_drop(v, v->n - n); 3503 3504 return fresh; 3505} 3506 3507/* First read the domain of the affine expression, which may be 3508 * a parameter space or a set. 3509 * The tricky part is that we don't know if the domain is a set or not, 3510 * so when we are trying to read the domain, we may actually be reading 3511 * the affine expression itself (defined on a parameter domains) 3512 * If the tuple we are reading is named, we assume it's the domain. 3513 * Also, if inside the tuple, the first thing we find is a nested tuple 3514 * or a new identifier, we again assume it's the domain. 3515 * Finally, if the tuple is empty, then it must be the domain 3516 * since it does not contain an affine expression. 3517 * Otherwise, we assume we are reading an affine expression. 3518 */ 3519static __isl_give isl_set *read_aff_domain(__isl_keep isl_stream *s, 3520 __isl_take isl_set *dom, struct vars *v) 3521{ 3522 struct isl_token *tok, *tok2; 3523 int is_empty; 3524 3525 tok = isl_stream_next_token(s); 3526 if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) { 3527 isl_stream_push_token(s, tok); 3528 return read_map_tuple(s, dom, isl_dim_set, v, 0); 3529 } 3530 if (!tok || tok->type != '[') { 3531 isl_stream_error(s, tok, "expecting '['"); 3532 goto error; 3533 } 3534 tok2 = isl_stream_next_token(s); 3535 is_empty = tok2 && tok2->type == ']'; 3536 if (tok2) 3537 isl_stream_push_token(s, tok2); 3538 if (is_empty || next_is_tuple(s) || next_is_fresh_ident(s, v)) { 3539 isl_stream_push_token(s, tok); 3540 dom = read_map_tuple(s, dom, isl_dim_set, v, 0); 3541 } else 3542 isl_stream_push_token(s, tok); 3543 3544 return dom; 3545error: 3546 if (tok) 3547 isl_stream_push_token(s, tok); 3548 isl_set_free(dom); 3549 return NULL; 3550} 3551 3552/* Read an affine expression from "s". 3553 */ 3554__isl_give isl_aff *isl_stream_read_aff(__isl_keep isl_stream *s) 3555{ 3556 isl_aff *aff; 3557 isl_multi_aff *ma; 3558 isl_size dim; 3559 3560 ma = isl_stream_read_multi_aff(s); 3561 dim = isl_multi_aff_dim(ma, isl_dim_out); 3562 if (dim < 0) 3563 goto error; 3564 if (dim != 1) 3565 isl_die(s->ctx, isl_error_invalid, 3566 "expecting single affine expression", 3567 goto error); 3568 3569 aff = isl_multi_aff_get_aff(ma, 0); 3570 isl_multi_aff_free(ma); 3571 return aff; 3572error: 3573 isl_multi_aff_free(ma); 3574 return NULL; 3575} 3576 3577/* Read a piecewise affine expression from "s" with domain (space) "dom". 3578 */ 3579static __isl_give isl_pw_aff *read_pw_aff_with_dom(__isl_keep isl_stream *s, 3580 __isl_take isl_set *dom, struct vars *v) 3581{ 3582 isl_pw_aff *pwaff = NULL; 3583 3584 if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO)) 3585 goto error; 3586 3587 if (isl_stream_eat(s, '[')) 3588 goto error; 3589 3590 pwaff = accept_affine(s, isl_set_get_space(dom), v); 3591 3592 if (isl_stream_eat(s, ']')) 3593 goto error; 3594 3595 dom = read_optional_formula(s, dom, v, 0); 3596 pwaff = isl_pw_aff_intersect_domain(pwaff, dom); 3597 3598 return pwaff; 3599error: 3600 isl_set_free(dom); 3601 isl_pw_aff_free(pwaff); 3602 return NULL; 3603} 3604 3605/* Read an affine expression, together with optional constraints 3606 * on the domain from "s". "dom" represents the initial constraints 3607 * on the parameter domain. 3608 * "v" contains a description of the identifiers parsed so far. 3609 */ 3610static __isl_give isl_pw_aff *read_conditional_aff(__isl_keep isl_stream *s, 3611 __isl_take isl_set *dom, struct vars *v) 3612{ 3613 isl_set *aff_dom; 3614 isl_pw_aff *pa; 3615 int n; 3616 3617 n = v->n; 3618 aff_dom = read_aff_domain(s, dom, v); 3619 pa = read_pw_aff_with_dom(s, aff_dom, v); 3620 vars_drop(v, v->n - n); 3621 3622 return pa; 3623} 3624 3625#undef BASE 3626#define BASE aff 3627#include "isl_stream_read_pw_with_params_templ.c" 3628 3629#undef TYPE_BASE 3630#define TYPE_BASE aff 3631#include "isl_read_from_str_templ.c" 3632 3633#undef TYPE_BASE 3634#define TYPE_BASE pw_aff 3635#include "isl_stream_read_with_params_templ.c" 3636#include "isl_read_from_str_templ.c" 3637 3638/* Given that "pa" is the element at position "pos" of a tuple 3639 * returned by read_tuple, check that it does not involve any 3640 * output/set dimensions (appearing at the "n" positions starting at "first"), 3641 * remove those from the domain and replace the domain space 3642 * with "domain_space". 3643 * 3644 * In particular, the result of read_tuple is of the form 3645 * [input, output] -> [output], with anonymous domain. 3646 * The function read_tuple accepts tuples where some output or 3647 * set dimensions are defined in terms of other output or set dimensions 3648 * since this function is also used to read maps. As a special case, 3649 * read_tuple also accepts dimensions that are defined in terms of themselves 3650 * (i.e., that are not defined). 3651 * These cases are not allowed here. 3652 */ 3653static __isl_give isl_pw_aff *separate_tuple_entry(__isl_take isl_pw_aff *pa, 3654 int pos, unsigned first, unsigned n, __isl_take isl_space *domain_space) 3655{ 3656 isl_bool involves; 3657 3658 involves = isl_pw_aff_involves_dims(pa, isl_dim_in, first, pos + 1); 3659 if (involves < 0) { 3660 pa = isl_pw_aff_free(pa); 3661 } else if (involves) { 3662 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid, 3663 "not an affine expression", 3664 pa = isl_pw_aff_free(pa)); 3665 } 3666 pa = isl_pw_aff_drop_dims(pa, isl_dim_in, first, n); 3667 pa = isl_pw_aff_reset_domain_space(pa, domain_space); 3668 3669 return pa; 3670} 3671 3672/* Set entry "pos" of "mpa" to the corresponding entry in "tuple", 3673 * as obtained from read_tuple(). 3674 * The "n" output dimensions also appear among the input dimensions 3675 * at position "first". 3676 * 3677 * The entry is not allowed to depend on any (other) output dimensions. 3678 */ 3679static __isl_give isl_multi_pw_aff *isl_multi_pw_aff_set_tuple_entry( 3680 __isl_take isl_multi_pw_aff *mpa, __isl_take isl_pw_aff *tuple_el, 3681 int pos, unsigned first, unsigned n) 3682{ 3683 isl_space *space; 3684 isl_pw_aff *pa; 3685 3686 space = isl_multi_pw_aff_get_domain_space(mpa); 3687 pa = separate_tuple_entry(tuple_el, pos, first, n, space); 3688 return isl_multi_pw_aff_set_pw_aff(mpa, pos, pa); 3689} 3690 3691#undef BASE 3692#define BASE pw_aff 3693 3694#include <isl_multi_from_tuple_templ.c> 3695 3696/* Read a tuple of piecewise affine expressions, 3697 * including optional constraints on the domain from "s". 3698 * "dom" represents the initial constraints on the domain. 3699 * 3700 * The input format is similar to that of a map, except that any conditions 3701 * on the domains should be specified inside the tuple since each 3702 * piecewise affine expression may have a different domain. 3703 * However, additional, shared conditions can also be specified. 3704 * This is especially useful for setting the explicit domain 3705 * of a zero-dimensional isl_multi_pw_aff. 3706 * 3707 * The isl_multi_pw_aff may live in either a set or a map space. 3708 * First read the first tuple and check if it is followed by a "->". 3709 * If so, convert the tuple into the domain of the isl_multi_pw_aff and 3710 * read in the next tuple. This tuple (or the first tuple if it was 3711 * not followed by a "->") is then converted into an isl_multi_pw_aff 3712 * through a call to isl_multi_pw_aff_from_tuple. 3713 * The domain of the result is intersected with the domain. 3714 * 3715 * Note that the last tuple may introduce new identifiers, 3716 * but these cannot be referenced in the description of the domain. 3717 */ 3718static __isl_give isl_multi_pw_aff *read_conditional_multi_pw_aff( 3719 __isl_keep isl_stream *s, __isl_take isl_set *dom, struct vars *v) 3720{ 3721 isl_multi_pw_aff *tuple; 3722 isl_multi_pw_aff *mpa; 3723 int n = v->n; 3724 int n_dom; 3725 3726 n_dom = v->n; 3727 tuple = read_tuple(s, v, 0, 0); 3728 if (!tuple) 3729 goto error; 3730 if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) { 3731 isl_map *map = map_from_tuple(tuple, dom, isl_dim_in, v, 0); 3732 dom = isl_map_domain(map); 3733 n_dom = v->n; 3734 tuple = read_tuple(s, v, 0, 0); 3735 if (!tuple) 3736 goto error; 3737 } 3738 mpa = isl_multi_pw_aff_from_tuple(isl_set_get_space(dom), tuple); 3739 if (!mpa) 3740 dom = isl_set_free(dom); 3741 3742 vars_drop(v, v->n - n_dom); 3743 dom = read_optional_formula(s, dom, v, 0); 3744 3745 vars_drop(v, v->n - n); 3746 3747 mpa = isl_multi_pw_aff_intersect_domain(mpa, dom); 3748 3749 return mpa; 3750error: 3751 isl_set_free(dom); 3752 return NULL; 3753} 3754 3755/* Read a tuple of affine expressions, together with optional constraints 3756 * on the domain from "s". "dom" represents the initial constraints 3757 * on the domain. 3758 * 3759 * Read a tuple of piecewise affine expressions with optional constraints and 3760 * convert the result to an isl_pw_multi_aff on the shared domain. 3761 */ 3762static __isl_give isl_pw_multi_aff *read_conditional_multi_aff( 3763 __isl_keep isl_stream *s, __isl_take isl_set *dom, struct vars *v) 3764{ 3765 isl_multi_pw_aff *mpa; 3766 3767 mpa = read_conditional_multi_pw_aff(s, dom, v); 3768 return isl_pw_multi_aff_from_multi_pw_aff(mpa); 3769} 3770 3771/* Read an isl_union_pw_multi_aff from "s" with parameter domain "dom". 3772 * "v" contains a description of the identifiers parsed so far. 3773 * 3774 * In particular, read a sequence 3775 * of zero or more tuples of affine expressions with optional conditions and 3776 * add them up. 3777 */ 3778static __isl_give isl_union_pw_multi_aff * 3779isl_stream_read_with_params_union_pw_multi_aff(__isl_keep isl_stream *s, 3780 __isl_keep isl_set *dom, struct vars *v) 3781{ 3782 isl_union_pw_multi_aff *upma; 3783 3784 upma = isl_union_pw_multi_aff_empty(isl_set_get_space(dom)); 3785 3786 do { 3787 isl_pw_multi_aff *pma; 3788 isl_union_pw_multi_aff *upma2; 3789 3790 if (isl_stream_next_token_is(s, '}')) 3791 break; 3792 3793 pma = read_conditional_multi_aff(s, isl_set_copy(dom), v); 3794 upma2 = isl_union_pw_multi_aff_from_pw_multi_aff(pma); 3795 upma = isl_union_pw_multi_aff_union_add(upma, upma2); 3796 if (!upma) 3797 return NULL; 3798 } while (isl_stream_eat_if_available(s, ';')); 3799 3800 return upma; 3801} 3802 3803#undef BASE 3804#define BASE multi_aff 3805#include "isl_stream_read_pw_with_params_templ.c" 3806 3807#undef TYPE_BASE 3808#define TYPE_BASE pw_multi_aff 3809#include "isl_stream_read_with_params_templ.c" 3810#include "isl_read_from_str_templ.c" 3811 3812#undef TYPE_BASE 3813#define TYPE_BASE union_pw_multi_aff 3814#include "isl_stream_read_with_params_templ.c" 3815#include "isl_read_from_str_templ.c" 3816 3817#undef BASE 3818#define BASE val 3819 3820#include <isl_multi_read_no_explicit_domain_templ.c> 3821 3822#undef BASE 3823#define BASE id 3824 3825#include <isl_multi_read_no_explicit_domain_templ.c> 3826 3827/* Set entry "pos" of "ma" to the corresponding entry in "tuple", 3828 * as obtained from read_tuple(). 3829 * The "n" output dimensions also appear among the input dimensions 3830 * at position "first". 3831 * 3832 * The entry is not allowed to depend on any (other) output dimensions. 3833 */ 3834static __isl_give isl_multi_aff *isl_multi_aff_set_tuple_entry( 3835 __isl_take isl_multi_aff *ma, __isl_take isl_pw_aff *tuple_el, 3836 int pos, unsigned first, unsigned n) 3837{ 3838 isl_space *space; 3839 isl_pw_aff *pa; 3840 isl_aff *aff; 3841 3842 space = isl_multi_aff_get_domain_space(ma); 3843 pa = separate_tuple_entry(tuple_el, pos, first, n, space); 3844 aff = isl_pw_aff_as_aff(pa); 3845 return isl_multi_aff_set_aff(ma, pos, aff); 3846} 3847 3848#undef BASE 3849#define BASE aff 3850 3851#include <isl_multi_from_tuple_templ.c> 3852 3853/* Read a multi-affine expression from "s". 3854 * If the multi-affine expression has a domain, then the tuple 3855 * representing this domain cannot involve any affine expressions. 3856 * The tuple representing the actual expressions needs to consist 3857 * of only affine expressions. 3858 */ 3859__isl_give isl_multi_aff *isl_stream_read_multi_aff(__isl_keep isl_stream *s) 3860{ 3861 struct vars *v; 3862 isl_multi_pw_aff *tuple = NULL; 3863 isl_space *dom_space = NULL; 3864 isl_multi_aff *ma = NULL; 3865 3866 v = vars_new(s->ctx); 3867 if (!v) 3868 return NULL; 3869 3870 dom_space = read_params(s, v); 3871 if (!dom_space) 3872 goto error; 3873 if (isl_stream_eat(s, '{')) 3874 goto error; 3875 3876 tuple = read_tuple(s, v, 0, 0); 3877 if (!tuple) 3878 goto error; 3879 if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) { 3880 isl_space *space; 3881 isl_bool has_expr; 3882 3883 has_expr = tuple_has_expr(tuple); 3884 if (has_expr < 0) 3885 goto error; 3886 if (has_expr) 3887 isl_die(s->ctx, isl_error_invalid, 3888 "expecting universe domain", goto error); 3889 space = isl_space_range(isl_multi_pw_aff_get_space(tuple)); 3890 dom_space = isl_space_align_params(space, dom_space); 3891 isl_multi_pw_aff_free(tuple); 3892 tuple = read_tuple(s, v, 0, 0); 3893 if (!tuple) 3894 goto error; 3895 } 3896 3897 if (isl_stream_eat(s, '}')) 3898 goto error; 3899 3900 ma = isl_multi_aff_from_tuple(dom_space, tuple); 3901 3902 vars_free(v); 3903 return ma; 3904error: 3905 isl_multi_pw_aff_free(tuple); 3906 vars_free(v); 3907 isl_space_free(dom_space); 3908 isl_multi_aff_free(ma); 3909 return NULL; 3910} 3911 3912#undef TYPE_BASE 3913#define TYPE_BASE multi_aff 3914#include "isl_read_from_str_templ.c" 3915 3916/* Read an isl_multi_pw_aff from "s" with parameter domain "dom".. 3917 * "v" contains a description of the identifiers parsed so far. 3918 */ 3919static __isl_give isl_multi_pw_aff *isl_stream_read_with_params_multi_pw_aff( 3920 __isl_keep isl_stream *s, __isl_keep isl_set *dom, struct vars *v) 3921{ 3922 return read_conditional_multi_pw_aff(s, isl_set_copy(dom), v); 3923} 3924 3925#undef TYPE_BASE 3926#define TYPE_BASE multi_pw_aff 3927#include "isl_stream_read_with_params_templ.c" 3928#include "isl_read_from_str_templ.c" 3929 3930/* Read the body of an isl_union_pw_aff from "s" with parameter domain "dom". 3931 */ 3932static __isl_give isl_union_pw_aff *read_union_pw_aff_with_dom( 3933 __isl_keep isl_stream *s, __isl_take isl_set *dom, struct vars *v) 3934{ 3935 isl_pw_aff *pa; 3936 isl_union_pw_aff *upa = NULL; 3937 isl_set *aff_dom; 3938 int n; 3939 3940 n = v->n; 3941 aff_dom = read_aff_domain(s, isl_set_copy(dom), v); 3942 pa = read_pw_aff_with_dom(s, aff_dom, v); 3943 vars_drop(v, v->n - n); 3944 3945 upa = isl_union_pw_aff_from_pw_aff(pa); 3946 3947 while (isl_stream_eat_if_available(s, ';')) { 3948 isl_pw_aff *pa_i; 3949 isl_union_pw_aff *upa_i; 3950 3951 n = v->n; 3952 aff_dom = read_aff_domain(s, isl_set_copy(dom), v); 3953 pa_i = read_pw_aff_with_dom(s, aff_dom, v); 3954 vars_drop(v, v->n - n); 3955 3956 upa_i = isl_union_pw_aff_from_pw_aff(pa_i); 3957 upa = isl_union_pw_aff_union_add(upa, upa_i); 3958 } 3959 3960 isl_set_free(dom); 3961 return upa; 3962} 3963 3964/* Read an isl_union_pw_aff from "s" with parameter domain "dom". 3965 * "v" contains a description of the identifiers parsed so far. 3966 */ 3967static __isl_give isl_union_pw_aff *isl_stream_read_with_params_union_pw_aff( 3968 __isl_keep isl_stream *s, __isl_keep isl_set *dom, struct vars *v) 3969{ 3970 return read_union_pw_aff_with_dom(s, isl_set_copy(dom), v); 3971} 3972 3973#undef TYPE_BASE 3974#define TYPE_BASE union_pw_aff 3975#include "isl_stream_read_with_params_templ.c" 3976#include "isl_read_from_str_templ.c" 3977 3978/* This function is called for each element in a tuple inside 3979 * isl_stream_read_multi_union_pw_aff. 3980 * 3981 * Read a '{', the union piecewise affine expression body and a '}' and 3982 * add the isl_union_pw_aff to *list. 3983 */ 3984static __isl_give isl_space *read_union_pw_aff_el(__isl_keep isl_stream *s, 3985 struct vars *v, __isl_take isl_space *space, int rational, void *user) 3986{ 3987 isl_set *dom; 3988 isl_union_pw_aff *upa; 3989 isl_union_pw_aff_list **list = (isl_union_pw_aff_list **) user; 3990 3991 dom = isl_set_universe(isl_space_params(isl_space_copy(space))); 3992 if (isl_stream_eat(s, '{')) 3993 goto error; 3994 upa = read_union_pw_aff_with_dom(s, dom, v); 3995 *list = isl_union_pw_aff_list_add(*list, upa); 3996 if (isl_stream_eat(s, '}')) 3997 return isl_space_free(space); 3998 if (!*list) 3999 return isl_space_free(space); 4000 return space; 4001error: 4002 isl_set_free(dom); 4003 return isl_space_free(space); 4004} 4005 4006/* Do the next tokens in "s" correspond to an empty tuple? 4007 * In particular, does the stream start with a '[', followed by a ']', 4008 * not followed by a "->"? 4009 */ 4010static int next_is_empty_tuple(__isl_keep isl_stream *s) 4011{ 4012 struct isl_token *tok, *tok2, *tok3; 4013 int is_empty_tuple = 0; 4014 4015 tok = isl_stream_next_token(s); 4016 if (!tok) 4017 return 0; 4018 if (tok->type != '[') { 4019 isl_stream_push_token(s, tok); 4020 return 0; 4021 } 4022 4023 tok2 = isl_stream_next_token(s); 4024 if (tok2 && tok2->type == ']') { 4025 tok3 = isl_stream_next_token(s); 4026 is_empty_tuple = !tok || tok->type != ISL_TOKEN_TO; 4027 if (tok3) 4028 isl_stream_push_token(s, tok3); 4029 } 4030 if (tok2) 4031 isl_stream_push_token(s, tok2); 4032 isl_stream_push_token(s, tok); 4033 4034 return is_empty_tuple; 4035} 4036 4037/* Do the next tokens in "s" correspond to a tuple of parameters? 4038 * In particular, does the stream start with a '[' that is not 4039 * followed by a '{' or a nested tuple? 4040 */ 4041static int next_is_param_tuple(__isl_keep isl_stream *s) 4042{ 4043 struct isl_token *tok, *tok2; 4044 int is_tuple; 4045 4046 tok = isl_stream_next_token(s); 4047 if (!tok) 4048 return 0; 4049 if (tok->type != '[' || next_is_tuple(s)) { 4050 isl_stream_push_token(s, tok); 4051 return 0; 4052 } 4053 4054 tok2 = isl_stream_next_token(s); 4055 is_tuple = tok2 && tok2->type != '{'; 4056 if (tok2) 4057 isl_stream_push_token(s, tok2); 4058 isl_stream_push_token(s, tok); 4059 4060 return is_tuple; 4061} 4062 4063/* Read the core of a body of an isl_multi_union_pw_aff from "s", 4064 * i.e., everything except the parameter specification and 4065 * without shared domain constraints. 4066 * "v" contains a description of the identifiers parsed so far. 4067 * The parameters, if any, are specified by "space". 4068 * 4069 * The body is of the form 4070 * 4071 * [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }] 4072 * 4073 * Read the tuple, collecting the individual isl_union_pw_aff 4074 * elements in a list and construct the result from the tuple space and 4075 * the list. 4076 */ 4077static __isl_give isl_multi_union_pw_aff *read_multi_union_pw_aff_body_core( 4078 __isl_keep isl_stream *s, struct vars *v, __isl_take isl_space *space) 4079{ 4080 isl_union_pw_aff_list *list; 4081 isl_multi_union_pw_aff *mupa; 4082 4083 list = isl_union_pw_aff_list_alloc(s->ctx, 0); 4084 space = read_tuple_space(s, v, space, 1, 0, 4085 &read_union_pw_aff_el, &list); 4086 mupa = isl_multi_union_pw_aff_from_union_pw_aff_list(space, list); 4087 4088 return mupa; 4089} 4090 4091/* Read the body of an isl_union_set from "s", 4092 * i.e., everything except the parameter specification. 4093 * "v" contains a description of the identifiers parsed so far. 4094 * The parameters, if any, are specified by "space". 4095 * 4096 * First read a generic disjunction of object bodies and then try and extract 4097 * an isl_union_set from that. 4098 */ 4099static __isl_give isl_union_set *read_union_set_body(__isl_keep isl_stream *s, 4100 struct vars *v, __isl_take isl_space *space) 4101{ 4102 struct isl_obj obj = { isl_obj_set, NULL }; 4103 isl_map *map; 4104 4105 map = isl_set_universe(space); 4106 if (isl_stream_eat(s, '{') < 0) 4107 goto error; 4108 obj = obj_read_disjuncts(s, v, map); 4109 if (isl_stream_eat(s, '}') < 0) 4110 goto error; 4111 isl_map_free(map); 4112 4113 return extract_union_set(s->ctx, obj); 4114error: 4115 obj.type->free(obj.v); 4116 isl_map_free(map); 4117 return NULL; 4118} 4119 4120/* Read the body of an isl_multi_union_pw_aff from "s", 4121 * i.e., everything except the parameter specification. 4122 * "v" contains a description of the identifiers parsed so far. 4123 * The parameters, if any, are specified by "space". 4124 * 4125 * In particular, handle the special case with shared domain constraints. 4126 * These are specified as 4127 * 4128 * ([...] : ...) 4129 * 4130 * and are especially useful for setting the explicit domain 4131 * of a zero-dimensional isl_multi_union_pw_aff. 4132 * The core isl_multi_union_pw_aff body ([...]) is read by 4133 * read_multi_union_pw_aff_body_core. 4134 */ 4135static __isl_give isl_multi_union_pw_aff *read_multi_union_pw_aff_body( 4136 __isl_keep isl_stream *s, struct vars *v, __isl_take isl_space *space) 4137{ 4138 isl_multi_union_pw_aff *mupa; 4139 4140 if (!isl_stream_next_token_is(s, '(')) 4141 return read_multi_union_pw_aff_body_core(s, v, space); 4142 4143 if (isl_stream_eat(s, '(') < 0) 4144 goto error; 4145 mupa = read_multi_union_pw_aff_body_core(s, v, isl_space_copy(space)); 4146 if (isl_stream_eat_if_available(s, ':')) { 4147 isl_union_set *dom; 4148 4149 dom = read_union_set_body(s, v, space); 4150 mupa = isl_multi_union_pw_aff_intersect_domain(mupa, dom); 4151 } else { 4152 isl_space_free(space); 4153 } 4154 if (isl_stream_eat(s, ')') < 0) 4155 return isl_multi_union_pw_aff_free(mupa); 4156 4157 return mupa; 4158error: 4159 isl_space_free(space); 4160 return NULL; 4161} 4162 4163/* Read an isl_multi_union_pw_aff from "s". 4164 * 4165 * The input has the form 4166 * 4167 * [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }] 4168 * 4169 * or 4170 * 4171 * [..] -> [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }] 4172 * 4173 * Additionally, a shared domain may be specified as 4174 * 4175 * ([..] : ...) 4176 * 4177 * or 4178 * 4179 * [..] -> ([..] : ...) 4180 * 4181 * The first case is handled by the caller, the second case 4182 * is handled by read_multi_union_pw_aff_body. 4183 * 4184 * We first check for the special case of an empty tuple "[]". 4185 * Then we check if there are any parameters. 4186 * Finally, read the tuple and construct the result. 4187 */ 4188static __isl_give isl_multi_union_pw_aff *read_multi_union_pw_aff_core( 4189 __isl_keep isl_stream *s) 4190{ 4191 struct vars *v; 4192 isl_set *dom = NULL; 4193 isl_space *space; 4194 isl_multi_union_pw_aff *mupa = NULL; 4195 4196 if (next_is_empty_tuple(s)) { 4197 if (isl_stream_eat(s, '[')) 4198 return NULL; 4199 if (isl_stream_eat(s, ']')) 4200 return NULL; 4201 space = isl_space_set_alloc(s->ctx, 0, 0); 4202 return isl_multi_union_pw_aff_zero(space); 4203 } 4204 4205 v = vars_new(s->ctx); 4206 if (!v) 4207 return NULL; 4208 4209 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0)); 4210 if (next_is_param_tuple(s)) { 4211 dom = read_map_tuple(s, dom, isl_dim_param, v, 0); 4212 if (isl_stream_eat(s, ISL_TOKEN_TO)) 4213 goto error; 4214 } 4215 space = isl_set_get_space(dom); 4216 isl_set_free(dom); 4217 mupa = read_multi_union_pw_aff_body(s, v, space); 4218 4219 vars_free(v); 4220 4221 return mupa; 4222error: 4223 vars_free(v); 4224 isl_set_free(dom); 4225 isl_multi_union_pw_aff_free(mupa); 4226 return NULL; 4227} 4228 4229/* Read an isl_multi_union_pw_aff from "s". 4230 * 4231 * In particular, handle the special case with shared domain constraints. 4232 * These are specified as 4233 * 4234 * ([...] : ...) 4235 * 4236 * and are especially useful for setting the explicit domain 4237 * of a zero-dimensional isl_multi_union_pw_aff. 4238 * The core isl_multi_union_pw_aff ([...]) is read by 4239 * read_multi_union_pw_aff_core. 4240 */ 4241__isl_give isl_multi_union_pw_aff *isl_stream_read_multi_union_pw_aff( 4242 __isl_keep isl_stream *s) 4243{ 4244 isl_multi_union_pw_aff *mupa; 4245 4246 if (!isl_stream_next_token_is(s, '(')) 4247 return read_multi_union_pw_aff_core(s); 4248 4249 if (isl_stream_eat(s, '(') < 0) 4250 return NULL; 4251 mupa = read_multi_union_pw_aff_core(s); 4252 if (isl_stream_eat_if_available(s, ':')) { 4253 isl_union_set *dom; 4254 4255 dom = isl_stream_read_union_set(s); 4256 mupa = isl_multi_union_pw_aff_intersect_domain(mupa, dom); 4257 } 4258 if (isl_stream_eat(s, ')') < 0) 4259 return isl_multi_union_pw_aff_free(mupa); 4260 return mupa; 4261} 4262 4263#undef TYPE_BASE 4264#define TYPE_BASE multi_union_pw_aff 4265#include "isl_read_from_str_templ.c" 4266 4267__isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial( 4268 __isl_keep isl_stream *s) 4269{ 4270 struct isl_obj obj; 4271 4272 obj = obj_read(s); 4273 if (obj.type == isl_obj_pw_qpolynomial) { 4274 obj.type = isl_obj_union_pw_qpolynomial; 4275 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v); 4276 } 4277 if (obj.v) 4278 isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial, 4279 goto error); 4280 4281 return obj.v; 4282error: 4283 obj.type->free(obj.v); 4284 return NULL; 4285} 4286 4287#undef TYPE_BASE 4288#define TYPE_BASE union_pw_qpolynomial 4289#include "isl_read_from_str_templ.c" 4290