1/* 2 * Copyright 2008-2009 Katholieke Universiteit Leuven 3 * Copyright 2010 INRIA Saclay 4 * Copyright 2012 Ecole Normale Superieure 5 * 6 * Use of this software is governed by the MIT license 7 * 8 * Written by Sven Verdoolaege, K.U.Leuven, Departement 9 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium 10 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, 11 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 12 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France 13 */ 14 15#include <ctype.h> 16#include <stdio.h> 17#include <string.h> 18#include <isl_ctx_private.h> 19#include <isl_map_private.h> 20#include <isl/set.h> 21#include <isl/seq.h> 22#include <isl_stream_private.h> 23#include <isl/obj.h> 24#include "isl_polynomial_private.h" 25#include <isl/union_map.h> 26#include <isl_mat_private.h> 27#include <isl_aff_private.h> 28#include <isl/list.h> 29#include <isl_val_private.h> 30 31struct variable { 32 char *name; 33 int pos; 34 struct variable *next; 35}; 36 37struct vars { 38 struct isl_ctx *ctx; 39 int n; 40 struct variable *v; 41}; 42 43static struct vars *vars_new(struct isl_ctx *ctx) 44{ 45 struct vars *v; 46 v = isl_alloc_type(ctx, struct vars); 47 if (!v) 48 return NULL; 49 v->ctx = ctx; 50 v->n = 0; 51 v->v = NULL; 52 return v; 53} 54 55static void variable_free(struct variable *var) 56{ 57 while (var) { 58 struct variable *next = var->next; 59 free(var->name); 60 free(var); 61 var = next; 62 } 63} 64 65static void vars_free(struct vars *v) 66{ 67 if (!v) 68 return; 69 variable_free(v->v); 70 free(v); 71} 72 73static void vars_drop(struct vars *v, int n) 74{ 75 struct variable *var; 76 77 if (!v || !v->v) 78 return; 79 80 v->n -= n; 81 82 var = v->v; 83 while (--n >= 0) { 84 struct variable *next = var->next; 85 free(var->name); 86 free(var); 87 var = next; 88 } 89 v->v = var; 90} 91 92static struct variable *variable_new(struct vars *v, const char *name, int len, 93 int pos) 94{ 95 struct variable *var; 96 var = isl_calloc_type(v->ctx, struct variable); 97 if (!var) 98 goto error; 99 var->name = strdup(name); 100 var->name[len] = '\0'; 101 var->pos = pos; 102 var->next = v->v; 103 return var; 104error: 105 variable_free(v->v); 106 return NULL; 107} 108 109static int vars_pos(struct vars *v, const char *s, int len) 110{ 111 int pos; 112 struct variable *q; 113 114 if (len == -1) 115 len = strlen(s); 116 for (q = v->v; q; q = q->next) { 117 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0') 118 break; 119 } 120 if (q) 121 pos = q->pos; 122 else { 123 pos = v->n; 124 v->v = variable_new(v, s, len, v->n); 125 if (!v->v) 126 return -1; 127 v->n++; 128 } 129 return pos; 130} 131 132static int vars_add_anon(struct vars *v) 133{ 134 v->v = variable_new(v, "", 0, v->n); 135 136 if (!v->v) 137 return -1; 138 v->n++; 139 140 return 0; 141} 142 143/* Obtain next token, with some preprocessing. 144 * In particular, evaluate expressions of the form x^y, 145 * with x and y values. 146 */ 147static struct isl_token *next_token(struct isl_stream *s) 148{ 149 struct isl_token *tok, *tok2; 150 151 tok = isl_stream_next_token(s); 152 if (!tok || tok->type != ISL_TOKEN_VALUE) 153 return tok; 154 if (!isl_stream_eat_if_available(s, '^')) 155 return tok; 156 tok2 = isl_stream_next_token(s); 157 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) { 158 isl_stream_error(s, tok2, "expecting constant value"); 159 goto error; 160 } 161 162 isl_int_pow_ui(tok->u.v, tok->u.v, isl_int_get_ui(tok2->u.v)); 163 164 isl_token_free(tok2); 165 return tok; 166error: 167 isl_token_free(tok); 168 isl_token_free(tok2); 169 return NULL; 170} 171 172/* Read an isl_val from "s". 173 * 174 * The following token sequences are recognized 175 * 176 * "infty" -> infty 177 * "-" "infty" -> -infty 178 * "NaN" -> NaN 179 * n "/" d -> n/d 180 * v -> v 181 * 182 * where n, d and v are integer constants. 183 */ 184__isl_give isl_val *isl_stream_read_val(struct isl_stream *s) 185{ 186 struct isl_token *tok = NULL; 187 struct isl_token *tok2 = NULL; 188 isl_val *val; 189 190 tok = next_token(s); 191 if (!tok) { 192 isl_stream_error(s, NULL, "unexpected EOF"); 193 goto error; 194 } 195 if (tok->type == ISL_TOKEN_INFTY) { 196 isl_token_free(tok); 197 return isl_val_infty(s->ctx); 198 } 199 if (tok->type == '-' && 200 isl_stream_eat_if_available(s, ISL_TOKEN_INFTY)) { 201 isl_token_free(tok); 202 return isl_val_neginfty(s->ctx); 203 } 204 if (tok->type == ISL_TOKEN_NAN) { 205 isl_token_free(tok); 206 return isl_val_nan(s->ctx); 207 } 208 if (tok->type != ISL_TOKEN_VALUE) { 209 isl_stream_error(s, tok, "expecting value"); 210 goto error; 211 } 212 213 if (isl_stream_eat_if_available(s, '/')) { 214 tok2 = next_token(s); 215 if (!tok2) { 216 isl_stream_error(s, NULL, "unexpected EOF"); 217 goto error; 218 } 219 if (tok2->type != ISL_TOKEN_VALUE) { 220 isl_stream_error(s, tok2, "expecting value"); 221 goto error; 222 } 223 val = isl_val_rat_from_isl_int(s->ctx, tok->u.v, tok2->u.v); 224 val = isl_val_normalize(val); 225 } else { 226 val = isl_val_int_from_isl_int(s->ctx, tok->u.v); 227 } 228 229 isl_token_free(tok); 230 isl_token_free(tok2); 231 return val; 232error: 233 isl_token_free(tok); 234 isl_token_free(tok2); 235 return NULL; 236} 237 238/* Read an isl_val from "str". 239 */ 240struct isl_val *isl_val_read_from_str(struct isl_ctx *ctx, 241 const char *str) 242{ 243 isl_val *val; 244 struct isl_stream *s = isl_stream_new_str(ctx, str); 245 if (!s) 246 return NULL; 247 val = isl_stream_read_val(s); 248 isl_stream_free(s); 249 return val; 250} 251 252static int accept_cst_factor(struct isl_stream *s, isl_int *f) 253{ 254 struct isl_token *tok; 255 256 tok = next_token(s); 257 if (!tok || tok->type != ISL_TOKEN_VALUE) { 258 isl_stream_error(s, tok, "expecting constant value"); 259 goto error; 260 } 261 262 isl_int_mul(*f, *f, tok->u.v); 263 264 isl_token_free(tok); 265 266 if (isl_stream_eat_if_available(s, '*')) 267 return accept_cst_factor(s, f); 268 269 return 0; 270error: 271 isl_token_free(tok); 272 return -1; 273} 274 275/* Given an affine expression aff, return an affine expression 276 * for aff % d, with d the next token on the stream, which is 277 * assumed to be a constant. 278 * 279 * We introduce an integer division q = [aff/d] and the result 280 * is set to aff - d q. 281 */ 282static __isl_give isl_pw_aff *affine_mod(struct isl_stream *s, 283 struct vars *v, __isl_take isl_pw_aff *aff) 284{ 285 struct isl_token *tok; 286 isl_pw_aff *q; 287 288 tok = next_token(s); 289 if (!tok || tok->type != ISL_TOKEN_VALUE) { 290 isl_stream_error(s, tok, "expecting constant value"); 291 goto error; 292 } 293 294 q = isl_pw_aff_copy(aff); 295 q = isl_pw_aff_scale_down(q, tok->u.v); 296 q = isl_pw_aff_floor(q); 297 q = isl_pw_aff_scale(q, tok->u.v); 298 299 aff = isl_pw_aff_sub(aff, q); 300 301 isl_token_free(tok); 302 return aff; 303error: 304 isl_pw_aff_free(aff); 305 isl_token_free(tok); 306 return NULL; 307} 308 309static __isl_give isl_pw_aff *accept_affine(struct isl_stream *s, 310 __isl_take isl_space *dim, struct vars *v); 311static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s, 312 __isl_take isl_space *dim, struct vars *v); 313 314static __isl_give isl_pw_aff *accept_minmax(struct isl_stream *s, 315 __isl_take isl_space *dim, struct vars *v) 316{ 317 struct isl_token *tok; 318 isl_pw_aff_list *list = NULL; 319 int min; 320 321 tok = isl_stream_next_token(s); 322 if (!tok) 323 goto error; 324 min = tok->type == ISL_TOKEN_MIN; 325 isl_token_free(tok); 326 327 if (isl_stream_eat(s, '(')) 328 goto error; 329 330 list = accept_affine_list(s, isl_space_copy(dim), v); 331 if (!list) 332 goto error; 333 334 if (isl_stream_eat(s, ')')) 335 goto error; 336 337 isl_space_free(dim); 338 return min ? isl_pw_aff_list_min(list) : isl_pw_aff_list_max(list); 339error: 340 isl_space_free(dim); 341 isl_pw_aff_list_free(list); 342 return NULL; 343} 344 345/* Is "tok" the start of an integer division? 346 */ 347static int is_start_of_div(struct isl_token *tok) 348{ 349 if (!tok) 350 return 0; 351 if (tok->type == '[') 352 return 1; 353 if (tok->type == ISL_TOKEN_FLOOR) 354 return 1; 355 if (tok->type == ISL_TOKEN_CEIL) 356 return 1; 357 if (tok->type == ISL_TOKEN_FLOORD) 358 return 1; 359 if (tok->type == ISL_TOKEN_CEILD) 360 return 1; 361 return 0; 362} 363 364/* Read an integer division from "s" and return it as an isl_pw_aff. 365 * 366 * The integer division can be of the form 367 * 368 * [<affine expression>] 369 * floor(<affine expression>) 370 * ceil(<affine expression>) 371 * floord(<affine expression>,<denominator>) 372 * ceild(<affine expression>,<denominator>) 373 */ 374static __isl_give isl_pw_aff *accept_div(struct isl_stream *s, 375 __isl_take isl_space *dim, struct vars *v) 376{ 377 struct isl_token *tok; 378 int f = 0; 379 int c = 0; 380 int extra = 0; 381 isl_pw_aff *pwaff = NULL; 382 383 if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOORD)) 384 extra = f = 1; 385 else if (isl_stream_eat_if_available(s, ISL_TOKEN_CEILD)) 386 extra = c = 1; 387 else if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOOR)) 388 f = 1; 389 else if (isl_stream_eat_if_available(s, ISL_TOKEN_CEIL)) 390 c = 1; 391 if (f || c) { 392 if (isl_stream_eat(s, '(')) 393 goto error; 394 } else { 395 if (isl_stream_eat(s, '[')) 396 goto error; 397 } 398 399 pwaff = accept_affine(s, isl_space_copy(dim), v); 400 401 if (extra) { 402 if (isl_stream_eat(s, ',')) 403 goto error; 404 405 tok = next_token(s); 406 if (!tok) 407 goto error; 408 if (tok->type != ISL_TOKEN_VALUE) { 409 isl_stream_error(s, tok, "expected denominator"); 410 isl_stream_push_token(s, tok); 411 goto error; 412 } 413 isl_pw_aff_scale_down(pwaff, tok->u.v); 414 isl_token_free(tok); 415 } 416 417 if (c) 418 pwaff = isl_pw_aff_ceil(pwaff); 419 else 420 pwaff = isl_pw_aff_floor(pwaff); 421 422 if (f || c) { 423 if (isl_stream_eat(s, ')')) 424 goto error; 425 } else { 426 if (isl_stream_eat(s, ']')) 427 goto error; 428 } 429 430 isl_space_free(dim); 431 return pwaff; 432error: 433 isl_space_free(dim); 434 isl_pw_aff_free(pwaff); 435 return NULL; 436} 437 438static __isl_give isl_pw_aff *accept_affine_factor(struct isl_stream *s, 439 __isl_take isl_space *dim, struct vars *v) 440{ 441 struct isl_token *tok = NULL; 442 isl_pw_aff *res = NULL; 443 444 tok = next_token(s); 445 if (!tok) { 446 isl_stream_error(s, NULL, "unexpected EOF"); 447 goto error; 448 } 449 450 if (tok->type == ISL_TOKEN_AFF) { 451 res = isl_pw_aff_copy(tok->u.pwaff); 452 isl_token_free(tok); 453 } else if (tok->type == ISL_TOKEN_IDENT) { 454 int n = v->n; 455 int pos = vars_pos(v, tok->u.s, -1); 456 isl_aff *aff; 457 458 if (pos < 0) 459 goto error; 460 if (pos >= n) { 461 vars_drop(v, v->n - n); 462 isl_stream_error(s, tok, "unknown identifier"); 463 goto error; 464 } 465 466 aff = isl_aff_zero_on_domain(isl_local_space_from_space(isl_space_copy(dim))); 467 if (!aff) 468 goto error; 469 isl_int_set_si(aff->v->el[2 + pos], 1); 470 res = isl_pw_aff_from_aff(aff); 471 isl_token_free(tok); 472 } else if (tok->type == ISL_TOKEN_VALUE) { 473 if (isl_stream_eat_if_available(s, '*')) { 474 res = accept_affine_factor(s, isl_space_copy(dim), v); 475 res = isl_pw_aff_scale(res, tok->u.v); 476 } else { 477 isl_local_space *ls; 478 isl_aff *aff; 479 ls = isl_local_space_from_space(isl_space_copy(dim)); 480 aff = isl_aff_zero_on_domain(ls); 481 aff = isl_aff_add_constant(aff, tok->u.v); 482 res = isl_pw_aff_from_aff(aff); 483 } 484 isl_token_free(tok); 485 } else if (tok->type == '(') { 486 isl_token_free(tok); 487 tok = NULL; 488 res = accept_affine(s, isl_space_copy(dim), v); 489 if (!res) 490 goto error; 491 if (isl_stream_eat(s, ')')) 492 goto error; 493 } else if (is_start_of_div(tok)) { 494 isl_stream_push_token(s, tok); 495 tok = NULL; 496 res = accept_div(s, isl_space_copy(dim), v); 497 } else if (tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX) { 498 isl_stream_push_token(s, tok); 499 tok = NULL; 500 res = accept_minmax(s, isl_space_copy(dim), v); 501 } else { 502 isl_stream_error(s, tok, "expecting factor"); 503 goto error; 504 } 505 if (isl_stream_eat_if_available(s, '%') || 506 isl_stream_eat_if_available(s, ISL_TOKEN_MOD)) { 507 isl_space_free(dim); 508 return affine_mod(s, v, res); 509 } 510 if (isl_stream_eat_if_available(s, '*')) { 511 isl_int f; 512 isl_int_init(f); 513 isl_int_set_si(f, 1); 514 if (accept_cst_factor(s, &f) < 0) { 515 isl_int_clear(f); 516 goto error2; 517 } 518 res = isl_pw_aff_scale(res, f); 519 isl_int_clear(f); 520 } 521 if (isl_stream_eat_if_available(s, '/')) { 522 isl_int f; 523 isl_int_init(f); 524 isl_int_set_si(f, 1); 525 if (accept_cst_factor(s, &f) < 0) { 526 isl_int_clear(f); 527 goto error2; 528 } 529 res = isl_pw_aff_scale_down(res, f); 530 isl_int_clear(f); 531 } 532 533 isl_space_free(dim); 534 return res; 535error: 536 isl_token_free(tok); 537error2: 538 isl_pw_aff_free(res); 539 isl_space_free(dim); 540 return NULL; 541} 542 543static __isl_give isl_pw_aff *add_cst(__isl_take isl_pw_aff *pwaff, isl_int v) 544{ 545 isl_aff *aff; 546 isl_space *space; 547 548 space = isl_pw_aff_get_domain_space(pwaff); 549 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space)); 550 aff = isl_aff_add_constant(aff, v); 551 552 return isl_pw_aff_add(pwaff, isl_pw_aff_from_aff(aff)); 553} 554 555static __isl_give isl_pw_aff *accept_affine(struct isl_stream *s, 556 __isl_take isl_space *dim, struct vars *v) 557{ 558 struct isl_token *tok = NULL; 559 isl_local_space *ls; 560 isl_pw_aff *res; 561 int sign = 1; 562 563 ls = isl_local_space_from_space(isl_space_copy(dim)); 564 res = isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls)); 565 if (!res) 566 goto error; 567 568 for (;;) { 569 tok = next_token(s); 570 if (!tok) { 571 isl_stream_error(s, NULL, "unexpected EOF"); 572 goto error; 573 } 574 if (tok->type == '-') { 575 sign = -sign; 576 isl_token_free(tok); 577 continue; 578 } 579 if (tok->type == '(' || is_start_of_div(tok) || 580 tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX || 581 tok->type == ISL_TOKEN_IDENT || 582 tok->type == ISL_TOKEN_AFF) { 583 isl_pw_aff *term; 584 isl_stream_push_token(s, tok); 585 tok = NULL; 586 term = accept_affine_factor(s, isl_space_copy(dim), v); 587 if (sign < 0) 588 res = isl_pw_aff_sub(res, term); 589 else 590 res = isl_pw_aff_add(res, term); 591 if (!res) 592 goto error; 593 sign = 1; 594 } else if (tok->type == ISL_TOKEN_VALUE) { 595 if (sign < 0) 596 isl_int_neg(tok->u.v, tok->u.v); 597 if (isl_stream_eat_if_available(s, '*') || 598 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) { 599 isl_pw_aff *term; 600 term = accept_affine_factor(s, 601 isl_space_copy(dim), v); 602 term = isl_pw_aff_scale(term, tok->u.v); 603 res = isl_pw_aff_add(res, term); 604 if (!res) 605 goto error; 606 } else { 607 res = add_cst(res, tok->u.v); 608 } 609 sign = 1; 610 } else { 611 isl_stream_error(s, tok, "unexpected isl_token"); 612 isl_stream_push_token(s, tok); 613 isl_pw_aff_free(res); 614 isl_space_free(dim); 615 return NULL; 616 } 617 isl_token_free(tok); 618 619 tok = next_token(s); 620 if (tok && tok->type == '-') { 621 sign = -sign; 622 isl_token_free(tok); 623 } else if (tok && tok->type == '+') { 624 /* nothing */ 625 isl_token_free(tok); 626 } else if (tok && tok->type == ISL_TOKEN_VALUE && 627 isl_int_is_neg(tok->u.v)) { 628 isl_stream_push_token(s, tok); 629 } else { 630 if (tok) 631 isl_stream_push_token(s, tok); 632 break; 633 } 634 } 635 636 isl_space_free(dim); 637 return res; 638error: 639 isl_space_free(dim); 640 isl_token_free(tok); 641 isl_pw_aff_free(res); 642 return NULL; 643} 644 645static int is_comparator(struct isl_token *tok) 646{ 647 if (!tok) 648 return 0; 649 650 switch (tok->type) { 651 case ISL_TOKEN_LT: 652 case ISL_TOKEN_GT: 653 case ISL_TOKEN_LE: 654 case ISL_TOKEN_GE: 655 case ISL_TOKEN_NE: 656 case '=': 657 return 1; 658 default: 659 return 0; 660 } 661} 662 663static __isl_give isl_map *read_formula(struct isl_stream *s, 664 struct vars *v, __isl_take isl_map *map, int rational); 665static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s, 666 __isl_take isl_space *dim, struct vars *v, int rational); 667 668/* Accept a ternary operator, given the first argument. 669 */ 670static __isl_give isl_pw_aff *accept_ternary(struct isl_stream *s, 671 __isl_take isl_map *cond, struct vars *v, int rational) 672{ 673 isl_space *dim; 674 isl_pw_aff *pwaff1 = NULL, *pwaff2 = NULL, *pa_cond; 675 676 if (!cond) 677 return NULL; 678 679 if (isl_stream_eat(s, '?')) 680 goto error; 681 682 dim = isl_space_wrap(isl_map_get_space(cond)); 683 pwaff1 = accept_extended_affine(s, dim, v, rational); 684 if (!pwaff1) 685 goto error; 686 687 if (isl_stream_eat(s, ':')) 688 goto error; 689 690 dim = isl_pw_aff_get_domain_space(pwaff1); 691 pwaff2 = accept_extended_affine(s, dim, v, rational); 692 if (!pwaff1) 693 goto error; 694 695 pa_cond = isl_set_indicator_function(isl_map_wrap(cond)); 696 return isl_pw_aff_cond(pa_cond, pwaff1, pwaff2); 697error: 698 isl_map_free(cond); 699 isl_pw_aff_free(pwaff1); 700 isl_pw_aff_free(pwaff2); 701 return NULL; 702} 703 704/* Accept an affine expression that may involve ternary operators. 705 * We first read an affine expression. 706 * If it is not followed by a comparison operator, we simply return it. 707 * Otherwise, we assume the affine epxression is part of the first 708 * argument of a ternary operator and try to parse that. 709 */ 710static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s, 711 __isl_take isl_space *dim, struct vars *v, int rational) 712{ 713 isl_space *space; 714 isl_map *cond; 715 isl_pw_aff *pwaff; 716 struct isl_token *tok; 717 int line = -1, col = -1; 718 int is_comp; 719 720 tok = isl_stream_next_token(s); 721 if (tok) { 722 line = tok->line; 723 col = tok->col; 724 isl_stream_push_token(s, tok); 725 } 726 727 pwaff = accept_affine(s, dim, v); 728 if (rational) 729 pwaff = isl_pw_aff_set_rational(pwaff); 730 if (!pwaff) 731 return NULL; 732 733 tok = isl_stream_next_token(s); 734 if (!tok) 735 return isl_pw_aff_free(pwaff); 736 737 is_comp = is_comparator(tok); 738 isl_stream_push_token(s, tok); 739 if (!is_comp) 740 return pwaff; 741 742 tok = isl_token_new(s->ctx, line, col, 0); 743 if (!tok) 744 return isl_pw_aff_free(pwaff); 745 tok->type = ISL_TOKEN_AFF; 746 tok->u.pwaff = pwaff; 747 748 space = isl_pw_aff_get_domain_space(pwaff); 749 cond = isl_map_universe(isl_space_unwrap(space)); 750 751 isl_stream_push_token(s, tok); 752 753 cond = read_formula(s, v, cond, rational); 754 755 return accept_ternary(s, cond, v, rational); 756} 757 758static __isl_give isl_map *read_var_def(struct isl_stream *s, 759 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v, 760 int rational) 761{ 762 isl_pw_aff *def; 763 int pos; 764 isl_map *def_map; 765 766 if (type == isl_dim_param) 767 pos = isl_map_dim(map, isl_dim_param); 768 else { 769 pos = isl_map_dim(map, isl_dim_in); 770 if (type == isl_dim_out) 771 pos += isl_map_dim(map, isl_dim_out); 772 type = isl_dim_in; 773 } 774 --pos; 775 776 def = accept_extended_affine(s, isl_space_wrap(isl_map_get_space(map)), 777 v, rational); 778 def_map = isl_map_from_pw_aff(def); 779 def_map = isl_map_equate(def_map, type, pos, isl_dim_out, 0); 780 def_map = isl_set_unwrap(isl_map_domain(def_map)); 781 782 map = isl_map_intersect(map, def_map); 783 784 return map; 785} 786 787static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s, 788 __isl_take isl_space *dim, struct vars *v) 789{ 790 isl_pw_aff *pwaff; 791 isl_pw_aff_list *list; 792 struct isl_token *tok = NULL; 793 794 pwaff = accept_affine(s, isl_space_copy(dim), v); 795 list = isl_pw_aff_list_from_pw_aff(pwaff); 796 if (!list) 797 goto error; 798 799 for (;;) { 800 tok = isl_stream_next_token(s); 801 if (!tok) { 802 isl_stream_error(s, NULL, "unexpected EOF"); 803 goto error; 804 } 805 if (tok->type != ',') { 806 isl_stream_push_token(s, tok); 807 break; 808 } 809 isl_token_free(tok); 810 811 pwaff = accept_affine(s, isl_space_copy(dim), v); 812 list = isl_pw_aff_list_concat(list, 813 isl_pw_aff_list_from_pw_aff(pwaff)); 814 if (!list) 815 goto error; 816 } 817 818 isl_space_free(dim); 819 return list; 820error: 821 isl_space_free(dim); 822 isl_pw_aff_list_free(list); 823 return NULL; 824} 825 826static __isl_give isl_map *read_defined_var_list(struct isl_stream *s, 827 struct vars *v, __isl_take isl_map *map, int rational) 828{ 829 struct isl_token *tok; 830 831 while ((tok = isl_stream_next_token(s)) != NULL) { 832 int p; 833 int n = v->n; 834 835 if (tok->type != ISL_TOKEN_IDENT) 836 break; 837 838 p = vars_pos(v, tok->u.s, -1); 839 if (p < 0) 840 goto error; 841 if (p < n) { 842 isl_stream_error(s, tok, "expecting unique identifier"); 843 goto error; 844 } 845 846 map = isl_map_add_dims(map, isl_dim_out, 1); 847 848 isl_token_free(tok); 849 tok = isl_stream_next_token(s); 850 if (tok && tok->type == '=') { 851 isl_token_free(tok); 852 map = read_var_def(s, map, isl_dim_out, v, rational); 853 tok = isl_stream_next_token(s); 854 } 855 856 if (!tok || tok->type != ',') 857 break; 858 859 isl_token_free(tok); 860 } 861 if (tok) 862 isl_stream_push_token(s, tok); 863 864 return map; 865error: 866 isl_token_free(tok); 867 isl_map_free(map); 868 return NULL; 869} 870 871static int next_is_tuple(struct isl_stream *s) 872{ 873 struct isl_token *tok; 874 int is_tuple; 875 876 tok = isl_stream_next_token(s); 877 if (!tok) 878 return 0; 879 if (tok->type == '[') { 880 isl_stream_push_token(s, tok); 881 return 1; 882 } 883 if (tok->type != ISL_TOKEN_IDENT && !tok->is_keyword) { 884 isl_stream_push_token(s, tok); 885 return 0; 886 } 887 888 is_tuple = isl_stream_next_token_is(s, '['); 889 890 isl_stream_push_token(s, tok); 891 892 return is_tuple; 893} 894 895/* Allocate an initial tuple with zero dimensions and an anonymous, 896 * unstructured space. 897 * A tuple is represented as an isl_multi_pw_aff. 898 * The range space is the space of the tuple. 899 * The domain space is an anonymous space 900 * with a dimension for each variable in the set of variables in "v". 901 * If a given dimension is not defined in terms of earlier dimensions in 902 * the input, then the corresponding isl_pw_aff is set equal to one time 903 * the variable corresponding to the dimension being defined. 904 */ 905static __isl_give isl_multi_pw_aff *tuple_alloc(struct vars *v) 906{ 907 return isl_multi_pw_aff_alloc(isl_space_alloc(v->ctx, 0, v->n, 0)); 908} 909 910/* Is "pa" an expression in term of earlier dimensions? 911 * The alternative is that the dimension is defined to be equal to itself, 912 * meaning that it has a universe domain and an expression that depends 913 * on itself. "i" is the position of the expression in a sequence 914 * of "n" expressions. The final dimensions of "pa" correspond to 915 * these "n" expressions. 916 */ 917static int pw_aff_is_expr(__isl_keep isl_pw_aff *pa, int i, int n) 918{ 919 isl_aff *aff; 920 921 if (!pa) 922 return -1; 923 if (pa->n != 1) 924 return 1; 925 if (!isl_set_plain_is_universe(pa->p[0].set)) 926 return 1; 927 928 aff = pa->p[0].aff; 929 if (isl_int_is_zero(aff->v->el[aff->v->size - n + i])) 930 return 1; 931 return 0; 932} 933 934/* Does the tuple contain any dimensions that are defined 935 * in terms of earlier dimensions? 936 */ 937static int tuple_has_expr(__isl_keep isl_multi_pw_aff *tuple) 938{ 939 int i, n; 940 int has_expr = 0; 941 isl_pw_aff *pa; 942 943 if (!tuple) 944 return -1; 945 n = isl_multi_pw_aff_dim(tuple, isl_dim_out); 946 for (i = 0; i < n; ++i) { 947 pa = isl_multi_pw_aff_get_pw_aff(tuple, i); 948 has_expr = pw_aff_is_expr(pa, i, n); 949 isl_pw_aff_free(pa); 950 if (has_expr < 0 || has_expr) 951 break; 952 } 953 954 return has_expr; 955} 956 957/* Add a dimension to the given tuple. 958 * The dimension is initially undefined, so it is encoded 959 * as one times itself. 960 */ 961static __isl_give isl_multi_pw_aff *tuple_add_dim( 962 __isl_take isl_multi_pw_aff *tuple, struct vars *v) 963{ 964 isl_space *space; 965 isl_aff *aff; 966 isl_pw_aff *pa; 967 968 tuple = isl_multi_pw_aff_add_dims(tuple, isl_dim_in, 1); 969 space = isl_multi_pw_aff_get_domain_space(tuple); 970 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space)); 971 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, v->n, 1); 972 pa = isl_pw_aff_from_aff(aff); 973 tuple = isl_multi_pw_aff_flat_range_product(tuple, 974 isl_multi_pw_aff_from_pw_aff(pa)); 975 976 return tuple; 977} 978 979/* Set the name of dimension "pos" in "tuple" to "name". 980 * During printing, we add primes if the same name appears more than once 981 * to distinguish the occurrences. Here, we remove those primes from "name" 982 * before setting the name of the dimension. 983 */ 984static __isl_give isl_multi_pw_aff *tuple_set_dim_name( 985 __isl_take isl_multi_pw_aff *tuple, int pos, char *name) 986{ 987 char *prime; 988 989 if (!name) 990 return tuple; 991 992 prime = strchr(name, '\''); 993 if (prime) 994 *prime = '\0'; 995 tuple = isl_multi_pw_aff_set_dim_name(tuple, isl_dim_set, pos, name); 996 if (prime) 997 *prime = '\''; 998 999 return tuple; 1000} 1001 1002/* Read an affine expression from "s" and replace the definition 1003 * of dimension "pos" in "tuple" by this expression. 1004 * 1005 * accept_extended_affine requires a wrapped space as input. 1006 * The domain space of "tuple", on the other hand is an anonymous space, 1007 * so we have to adjust the space of the isl_pw_aff before adding it 1008 * to "tuple". 1009 */ 1010static __isl_give isl_multi_pw_aff *read_tuple_var_def(struct isl_stream *s, 1011 __isl_take isl_multi_pw_aff *tuple, int pos, struct vars *v, 1012 int rational) 1013{ 1014 isl_space *space; 1015 isl_pw_aff *def; 1016 1017 space = isl_space_wrap(isl_space_alloc(s->ctx, 0, v->n, 0)); 1018 def = accept_extended_affine(s, space, v, rational); 1019 space = isl_space_set_alloc(s->ctx, 0, v->n); 1020 def = isl_pw_aff_reset_domain_space(def, space); 1021 tuple = isl_multi_pw_aff_set_pw_aff(tuple, pos, def); 1022 1023 return tuple; 1024} 1025 1026/* Read a list of variables and/or affine expressions and return the list 1027 * as an isl_multi_pw_aff. 1028 * The elements in the list are separated by either "," or "][". 1029 * If "comma" is set then only "," is allowed. 1030 */ 1031static __isl_give isl_multi_pw_aff *read_tuple_var_list(struct isl_stream *s, 1032 struct vars *v, int rational, int comma) 1033{ 1034 int i = 0; 1035 struct isl_token *tok; 1036 isl_multi_pw_aff *res; 1037 1038 res = tuple_alloc(v); 1039 1040 if (isl_stream_next_token_is(s, ']')) 1041 return res; 1042 1043 while ((tok = next_token(s)) != NULL) { 1044 int new_name = 0; 1045 1046 res = tuple_add_dim(res, v); 1047 1048 if (tok->type == ISL_TOKEN_IDENT) { 1049 int n = v->n; 1050 int p = vars_pos(v, tok->u.s, -1); 1051 if (p < 0) 1052 goto error; 1053 new_name = p >= n; 1054 } 1055 1056 if (tok->type == '*') { 1057 if (vars_add_anon(v) < 0) 1058 goto error; 1059 isl_token_free(tok); 1060 } else if (new_name) { 1061 res = tuple_set_dim_name(res, i, v->v->name); 1062 isl_token_free(tok); 1063 if (isl_stream_eat_if_available(s, '=')) 1064 res = read_tuple_var_def(s, res, i, v, 1065 rational); 1066 } else { 1067 isl_stream_push_token(s, tok); 1068 tok = NULL; 1069 if (vars_add_anon(v) < 0) 1070 goto error; 1071 res = read_tuple_var_def(s, res, i, v, rational); 1072 } 1073 1074 tok = isl_stream_next_token(s); 1075 if (!comma && tok && tok->type == ']' && 1076 isl_stream_next_token_is(s, '[')) { 1077 isl_token_free(tok); 1078 tok = isl_stream_next_token(s); 1079 } else if (!tok || tok->type != ',') 1080 break; 1081 1082 isl_token_free(tok); 1083 i++; 1084 } 1085 if (tok) 1086 isl_stream_push_token(s, tok); 1087 1088 return res; 1089error: 1090 isl_token_free(tok); 1091 return isl_multi_pw_aff_free(res); 1092} 1093 1094/* Read a tuple and represent it as an isl_multi_pw_aff. See tuple_alloc. 1095 */ 1096static __isl_give isl_multi_pw_aff *read_tuple(struct isl_stream *s, 1097 struct vars *v, int rational, int comma) 1098{ 1099 struct isl_token *tok; 1100 char *name = NULL; 1101 isl_multi_pw_aff *res = NULL; 1102 1103 tok = isl_stream_next_token(s); 1104 if (!tok) 1105 goto error; 1106 if (tok->type == ISL_TOKEN_IDENT || tok->is_keyword) { 1107 name = strdup(tok->u.s); 1108 isl_token_free(tok); 1109 if (!name) 1110 goto error; 1111 } else 1112 isl_stream_push_token(s, tok); 1113 if (isl_stream_eat(s, '[')) 1114 goto error; 1115 if (next_is_tuple(s)) { 1116 isl_multi_pw_aff *out; 1117 int n; 1118 res = read_tuple(s, v, rational, comma); 1119 if (isl_stream_eat(s, ISL_TOKEN_TO)) 1120 goto error; 1121 out = read_tuple(s, v, rational, comma); 1122 n = isl_multi_pw_aff_dim(out, isl_dim_out); 1123 res = isl_multi_pw_aff_add_dims(res, isl_dim_in, n); 1124 res = isl_multi_pw_aff_range_product(res, out); 1125 } else 1126 res = read_tuple_var_list(s, v, rational, comma); 1127 if (isl_stream_eat(s, ']')) 1128 goto error; 1129 1130 if (name) { 1131 res = isl_multi_pw_aff_set_tuple_name(res, isl_dim_out, name); 1132 free(name); 1133 } 1134 1135 return res; 1136error: 1137 free(name); 1138 return isl_multi_pw_aff_free(res); 1139} 1140 1141/* Read a tuple from "s" and add it to "map". 1142 * The tuple is initially represented as an isl_multi_pw_aff. 1143 * We first create the appropriate space in "map" based on the range 1144 * space of this isl_multi_pw_aff. Then, we add equalities based 1145 * on the affine expressions. These live in an anonymous space, 1146 * however, so we first need to reset the space to that of "map". 1147 */ 1148static __isl_give isl_map *read_map_tuple(struct isl_stream *s, 1149 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v, 1150 int rational, int comma) 1151{ 1152 int i, n; 1153 isl_multi_pw_aff *tuple; 1154 isl_space *space = NULL; 1155 1156 tuple = read_tuple(s, v, rational, comma); 1157 if (!tuple) 1158 goto error; 1159 1160 n = isl_multi_pw_aff_dim(tuple, isl_dim_out); 1161 space = isl_space_range(isl_multi_pw_aff_get_space(tuple)); 1162 if (!space) 1163 goto error; 1164 1165 if (type == isl_dim_param) { 1166 if (isl_space_has_tuple_name(space, isl_dim_set) || 1167 isl_space_is_wrapping(space)) { 1168 isl_die(s->ctx, isl_error_invalid, 1169 "parameter tuples cannot be named or nested", 1170 goto error); 1171 } 1172 map = isl_map_add_dims(map, type, n); 1173 for (i = 0; i < n; ++i) { 1174 isl_id *id; 1175 if (!isl_space_has_dim_name(space, isl_dim_set, i)) 1176 isl_die(s->ctx, isl_error_invalid, 1177 "parameters must be named", 1178 goto error); 1179 id = isl_space_get_dim_id(space, isl_dim_set, i); 1180 map = isl_map_set_dim_id(map, isl_dim_param, i, id); 1181 } 1182 } else if (type == isl_dim_in) { 1183 isl_set *set; 1184 1185 set = isl_set_universe(isl_space_copy(space)); 1186 if (rational) 1187 set = isl_set_set_rational(set); 1188 set = isl_set_intersect_params(set, isl_map_params(map)); 1189 map = isl_map_from_domain(set); 1190 } else { 1191 isl_set *set; 1192 1193 set = isl_set_universe(isl_space_copy(space)); 1194 if (rational) 1195 set = isl_set_set_rational(set); 1196 map = isl_map_from_domain_and_range(isl_map_domain(map), set); 1197 } 1198 1199 for (i = 0; i < n; ++i) { 1200 isl_pw_aff *pa; 1201 isl_space *space; 1202 isl_aff *aff; 1203 isl_set *set; 1204 isl_map *map_i; 1205 1206 pa = isl_multi_pw_aff_get_pw_aff(tuple, i); 1207 space = isl_pw_aff_get_domain_space(pa); 1208 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space)); 1209 aff = isl_aff_add_coefficient_si(aff, 1210 isl_dim_in, v->n - n + i, -1); 1211 pa = isl_pw_aff_add(pa, isl_pw_aff_from_aff(aff)); 1212 if (rational) 1213 pa = isl_pw_aff_set_rational(pa); 1214 set = isl_pw_aff_zero_set(pa); 1215 map_i = isl_map_from_range(set); 1216 map_i = isl_map_reset_space(map_i, isl_map_get_space(map)); 1217 map = isl_map_intersect(map, map_i); 1218 } 1219 1220 isl_space_free(space); 1221 isl_multi_pw_aff_free(tuple); 1222 return map; 1223error: 1224 isl_space_free(space); 1225 isl_multi_pw_aff_free(tuple); 1226 isl_map_free(map); 1227 return NULL; 1228} 1229 1230static __isl_give isl_set *construct_constraints( 1231 __isl_take isl_set *set, int type, 1232 __isl_keep isl_pw_aff_list *left, __isl_keep isl_pw_aff_list *right, 1233 int rational) 1234{ 1235 isl_set *cond; 1236 1237 left = isl_pw_aff_list_copy(left); 1238 right = isl_pw_aff_list_copy(right); 1239 if (rational) { 1240 left = isl_pw_aff_list_set_rational(left); 1241 right = isl_pw_aff_list_set_rational(right); 1242 } 1243 if (type == ISL_TOKEN_LE) 1244 cond = isl_pw_aff_list_le_set(left, right); 1245 else if (type == ISL_TOKEN_GE) 1246 cond = isl_pw_aff_list_ge_set(left, right); 1247 else if (type == ISL_TOKEN_LT) 1248 cond = isl_pw_aff_list_lt_set(left, right); 1249 else if (type == ISL_TOKEN_GT) 1250 cond = isl_pw_aff_list_gt_set(left, right); 1251 else if (type == ISL_TOKEN_NE) 1252 cond = isl_pw_aff_list_ne_set(left, right); 1253 else 1254 cond = isl_pw_aff_list_eq_set(left, right); 1255 1256 return isl_set_intersect(set, cond); 1257} 1258 1259static __isl_give isl_map *add_constraint(struct isl_stream *s, 1260 struct vars *v, __isl_take isl_map *map, int rational) 1261{ 1262 struct isl_token *tok = NULL; 1263 isl_pw_aff_list *list1 = NULL, *list2 = NULL; 1264 isl_set *set; 1265 1266 set = isl_map_wrap(map); 1267 list1 = accept_affine_list(s, isl_set_get_space(set), v); 1268 if (!list1) 1269 goto error; 1270 tok = isl_stream_next_token(s); 1271 if (!is_comparator(tok)) { 1272 isl_stream_error(s, tok, "missing operator"); 1273 if (tok) 1274 isl_stream_push_token(s, tok); 1275 tok = NULL; 1276 goto error; 1277 } 1278 for (;;) { 1279 list2 = accept_affine_list(s, isl_set_get_space(set), v); 1280 if (!list2) 1281 goto error; 1282 1283 set = construct_constraints(set, tok->type, list1, list2, 1284 rational); 1285 isl_token_free(tok); 1286 isl_pw_aff_list_free(list1); 1287 list1 = list2; 1288 1289 tok = isl_stream_next_token(s); 1290 if (!is_comparator(tok)) { 1291 if (tok) 1292 isl_stream_push_token(s, tok); 1293 break; 1294 } 1295 } 1296 isl_pw_aff_list_free(list1); 1297 1298 return isl_set_unwrap(set); 1299error: 1300 if (tok) 1301 isl_token_free(tok); 1302 isl_pw_aff_list_free(list1); 1303 isl_pw_aff_list_free(list2); 1304 isl_set_free(set); 1305 return NULL; 1306} 1307 1308static __isl_give isl_map *read_exists(struct isl_stream *s, 1309 struct vars *v, __isl_take isl_map *map, int rational) 1310{ 1311 int n = v->n; 1312 int seen_paren = isl_stream_eat_if_available(s, '('); 1313 1314 map = isl_map_from_domain(isl_map_wrap(map)); 1315 map = read_defined_var_list(s, v, map, rational); 1316 1317 if (isl_stream_eat(s, ':')) 1318 goto error; 1319 1320 map = read_formula(s, v, map, rational); 1321 map = isl_set_unwrap(isl_map_domain(map)); 1322 1323 vars_drop(v, v->n - n); 1324 if (seen_paren && isl_stream_eat(s, ')')) 1325 goto error; 1326 1327 return map; 1328error: 1329 isl_map_free(map); 1330 return NULL; 1331} 1332 1333/* Parse an expression between parentheses and push the result 1334 * back on the stream. 1335 * 1336 * The parsed expression may be either an affine expression 1337 * or a condition. The first type is pushed onto the stream 1338 * as an isl_pw_aff, while the second is pushed as an isl_map. 1339 * 1340 * If the initial token indicates the start of a condition, 1341 * we parse it as such. 1342 * Otherwise, we first parse an affine expression and push 1343 * that onto the stream. If the affine expression covers the 1344 * entire expression between parentheses, we return. 1345 * Otherwise, we assume that the affine expression is the 1346 * start of a condition and continue parsing. 1347 */ 1348static int resolve_paren_expr(struct isl_stream *s, 1349 struct vars *v, __isl_take isl_map *map, int rational) 1350{ 1351 struct isl_token *tok, *tok2; 1352 int line, col; 1353 isl_pw_aff *pwaff; 1354 1355 tok = isl_stream_next_token(s); 1356 if (!tok || tok->type != '(') 1357 goto error; 1358 1359 if (isl_stream_next_token_is(s, '(')) 1360 if (resolve_paren_expr(s, v, isl_map_copy(map), rational)) 1361 goto error; 1362 1363 if (isl_stream_next_token_is(s, ISL_TOKEN_EXISTS) || 1364 isl_stream_next_token_is(s, ISL_TOKEN_NOT) || 1365 isl_stream_next_token_is(s, ISL_TOKEN_TRUE) || 1366 isl_stream_next_token_is(s, ISL_TOKEN_FALSE) || 1367 isl_stream_next_token_is(s, ISL_TOKEN_MAP)) { 1368 map = read_formula(s, v, map, rational); 1369 if (isl_stream_eat(s, ')')) 1370 goto error; 1371 tok->type = ISL_TOKEN_MAP; 1372 tok->u.map = map; 1373 isl_stream_push_token(s, tok); 1374 return 0; 1375 } 1376 1377 tok2 = isl_stream_next_token(s); 1378 if (!tok2) 1379 goto error; 1380 line = tok2->line; 1381 col = tok2->col; 1382 isl_stream_push_token(s, tok2); 1383 1384 pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v); 1385 if (!pwaff) 1386 goto error; 1387 1388 tok2 = isl_token_new(s->ctx, line, col, 0); 1389 if (!tok2) 1390 goto error2; 1391 tok2->type = ISL_TOKEN_AFF; 1392 tok2->u.pwaff = pwaff; 1393 1394 if (isl_stream_eat_if_available(s, ')')) { 1395 isl_stream_push_token(s, tok2); 1396 isl_token_free(tok); 1397 isl_map_free(map); 1398 return 0; 1399 } 1400 1401 isl_stream_push_token(s, tok2); 1402 1403 map = read_formula(s, v, map, rational); 1404 if (isl_stream_eat(s, ')')) 1405 goto error; 1406 1407 tok->type = ISL_TOKEN_MAP; 1408 tok->u.map = map; 1409 isl_stream_push_token(s, tok); 1410 1411 return 0; 1412error2: 1413 isl_pw_aff_free(pwaff); 1414error: 1415 isl_token_free(tok); 1416 isl_map_free(map); 1417 return -1; 1418} 1419 1420static __isl_give isl_map *read_conjunct(struct isl_stream *s, 1421 struct vars *v, __isl_take isl_map *map, int rational) 1422{ 1423 if (isl_stream_next_token_is(s, '(')) 1424 if (resolve_paren_expr(s, v, isl_map_copy(map), rational)) 1425 goto error; 1426 1427 if (isl_stream_next_token_is(s, ISL_TOKEN_MAP)) { 1428 struct isl_token *tok; 1429 tok = isl_stream_next_token(s); 1430 if (!tok) 1431 goto error; 1432 isl_map_free(map); 1433 map = isl_map_copy(tok->u.map); 1434 isl_token_free(tok); 1435 return map; 1436 } 1437 1438 if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS)) 1439 return read_exists(s, v, map, rational); 1440 1441 if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE)) 1442 return map; 1443 1444 if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) { 1445 isl_space *dim = isl_map_get_space(map); 1446 isl_map_free(map); 1447 return isl_map_empty(dim); 1448 } 1449 1450 return add_constraint(s, v, map, rational); 1451error: 1452 isl_map_free(map); 1453 return NULL; 1454} 1455 1456static __isl_give isl_map *read_conjuncts(struct isl_stream *s, 1457 struct vars *v, __isl_take isl_map *map, int rational) 1458{ 1459 isl_map *res; 1460 int negate; 1461 1462 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT); 1463 res = read_conjunct(s, v, isl_map_copy(map), rational); 1464 if (negate) 1465 res = isl_map_subtract(isl_map_copy(map), res); 1466 1467 while (res && isl_stream_eat_if_available(s, ISL_TOKEN_AND)) { 1468 isl_map *res_i; 1469 1470 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT); 1471 res_i = read_conjunct(s, v, isl_map_copy(map), rational); 1472 if (negate) 1473 res = isl_map_subtract(res, res_i); 1474 else 1475 res = isl_map_intersect(res, res_i); 1476 } 1477 1478 isl_map_free(map); 1479 return res; 1480} 1481 1482static struct isl_map *read_disjuncts(struct isl_stream *s, 1483 struct vars *v, __isl_take isl_map *map, int rational) 1484{ 1485 isl_map *res; 1486 1487 if (isl_stream_next_token_is(s, '}')) { 1488 isl_space *dim = isl_map_get_space(map); 1489 isl_map_free(map); 1490 return isl_map_universe(dim); 1491 } 1492 1493 res = read_conjuncts(s, v, isl_map_copy(map), rational); 1494 while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) { 1495 isl_map *res_i; 1496 1497 res_i = read_conjuncts(s, v, isl_map_copy(map), rational); 1498 res = isl_map_union(res, res_i); 1499 } 1500 1501 isl_map_free(map); 1502 return res; 1503} 1504 1505/* Read a first order formula from "s", add the corresponding 1506 * constraints to "map" and return the result. 1507 * 1508 * In particular, read a formula of the form 1509 * 1510 * a 1511 * 1512 * or 1513 * 1514 * a implies b 1515 * 1516 * where a and b are disjunctions. 1517 * 1518 * In the first case, map is replaced by 1519 * 1520 * map \cap { [..] : a } 1521 * 1522 * In the second case, it is replaced by 1523 * 1524 * (map \setminus { [..] : a}) \cup (map \cap { [..] : b }) 1525 */ 1526static __isl_give isl_map *read_formula(struct isl_stream *s, 1527 struct vars *v, __isl_take isl_map *map, int rational) 1528{ 1529 isl_map *res; 1530 1531 res = read_disjuncts(s, v, isl_map_copy(map), rational); 1532 1533 if (isl_stream_eat_if_available(s, ISL_TOKEN_IMPLIES)) { 1534 isl_map *res2; 1535 1536 res = isl_map_subtract(isl_map_copy(map), res); 1537 res2 = read_disjuncts(s, v, map, rational); 1538 res = isl_map_union(res, res2); 1539 } else 1540 isl_map_free(map); 1541 1542 return res; 1543} 1544 1545static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos) 1546{ 1547 if (pos < isl_basic_map_dim(bmap, isl_dim_out)) 1548 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + 1549 isl_basic_map_dim(bmap, isl_dim_in) + pos; 1550 pos -= isl_basic_map_dim(bmap, isl_dim_out); 1551 1552 if (pos < isl_basic_map_dim(bmap, isl_dim_in)) 1553 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos; 1554 pos -= isl_basic_map_dim(bmap, isl_dim_in); 1555 1556 if (pos < isl_basic_map_dim(bmap, isl_dim_div)) 1557 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + 1558 isl_basic_map_dim(bmap, isl_dim_in) + 1559 isl_basic_map_dim(bmap, isl_dim_out) + pos; 1560 pos -= isl_basic_map_dim(bmap, isl_dim_div); 1561 1562 if (pos < isl_basic_map_dim(bmap, isl_dim_param)) 1563 return 1 + pos; 1564 1565 return 0; 1566} 1567 1568static __isl_give isl_basic_map *basic_map_read_polylib_constraint( 1569 struct isl_stream *s, __isl_take isl_basic_map *bmap) 1570{ 1571 int j; 1572 struct isl_token *tok; 1573 int type; 1574 int k; 1575 isl_int *c; 1576 unsigned nparam; 1577 unsigned dim; 1578 1579 if (!bmap) 1580 return NULL; 1581 1582 nparam = isl_basic_map_dim(bmap, isl_dim_param); 1583 dim = isl_basic_map_dim(bmap, isl_dim_out); 1584 1585 tok = isl_stream_next_token(s); 1586 if (!tok || tok->type != ISL_TOKEN_VALUE) { 1587 isl_stream_error(s, tok, "expecting coefficient"); 1588 if (tok) 1589 isl_stream_push_token(s, tok); 1590 goto error; 1591 } 1592 if (!tok->on_new_line) { 1593 isl_stream_error(s, tok, "coefficient should appear on new line"); 1594 isl_stream_push_token(s, tok); 1595 goto error; 1596 } 1597 1598 type = isl_int_get_si(tok->u.v); 1599 isl_token_free(tok); 1600 1601 isl_assert(s->ctx, type == 0 || type == 1, goto error); 1602 if (type == 0) { 1603 k = isl_basic_map_alloc_equality(bmap); 1604 c = bmap->eq[k]; 1605 } else { 1606 k = isl_basic_map_alloc_inequality(bmap); 1607 c = bmap->ineq[k]; 1608 } 1609 if (k < 0) 1610 goto error; 1611 1612 for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) { 1613 int pos; 1614 tok = isl_stream_next_token(s); 1615 if (!tok || tok->type != ISL_TOKEN_VALUE) { 1616 isl_stream_error(s, tok, "expecting coefficient"); 1617 if (tok) 1618 isl_stream_push_token(s, tok); 1619 goto error; 1620 } 1621 if (tok->on_new_line) { 1622 isl_stream_error(s, tok, 1623 "coefficient should not appear on new line"); 1624 isl_stream_push_token(s, tok); 1625 goto error; 1626 } 1627 pos = polylib_pos_to_isl_pos(bmap, j); 1628 isl_int_set(c[pos], tok->u.v); 1629 isl_token_free(tok); 1630 } 1631 1632 return bmap; 1633error: 1634 isl_basic_map_free(bmap); 1635 return NULL; 1636} 1637 1638static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s) 1639{ 1640 int i; 1641 struct isl_token *tok; 1642 struct isl_token *tok2; 1643 int n_row, n_col; 1644 int on_new_line; 1645 unsigned in = 0, out, local = 0; 1646 struct isl_basic_map *bmap = NULL; 1647 int nparam = 0; 1648 1649 tok = isl_stream_next_token(s); 1650 if (!tok) { 1651 isl_stream_error(s, NULL, "unexpected EOF"); 1652 return NULL; 1653 } 1654 tok2 = isl_stream_next_token(s); 1655 if (!tok2) { 1656 isl_token_free(tok); 1657 isl_stream_error(s, NULL, "unexpected EOF"); 1658 return NULL; 1659 } 1660 if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) { 1661 isl_stream_push_token(s, tok2); 1662 isl_stream_push_token(s, tok); 1663 isl_stream_error(s, NULL, 1664 "expecting constraint matrix dimensions"); 1665 return NULL; 1666 } 1667 n_row = isl_int_get_si(tok->u.v); 1668 n_col = isl_int_get_si(tok2->u.v); 1669 on_new_line = tok2->on_new_line; 1670 isl_token_free(tok2); 1671 isl_token_free(tok); 1672 isl_assert(s->ctx, !on_new_line, return NULL); 1673 isl_assert(s->ctx, n_row >= 0, return NULL); 1674 isl_assert(s->ctx, n_col >= 2 + nparam, return NULL); 1675 tok = isl_stream_next_token_on_same_line(s); 1676 if (tok) { 1677 if (tok->type != ISL_TOKEN_VALUE) { 1678 isl_stream_error(s, tok, 1679 "expecting number of output dimensions"); 1680 isl_stream_push_token(s, tok); 1681 goto error; 1682 } 1683 out = isl_int_get_si(tok->u.v); 1684 isl_token_free(tok); 1685 1686 tok = isl_stream_next_token_on_same_line(s); 1687 if (!tok || tok->type != ISL_TOKEN_VALUE) { 1688 isl_stream_error(s, tok, 1689 "expecting number of input dimensions"); 1690 if (tok) 1691 isl_stream_push_token(s, tok); 1692 goto error; 1693 } 1694 in = isl_int_get_si(tok->u.v); 1695 isl_token_free(tok); 1696 1697 tok = isl_stream_next_token_on_same_line(s); 1698 if (!tok || tok->type != ISL_TOKEN_VALUE) { 1699 isl_stream_error(s, tok, 1700 "expecting number of existentials"); 1701 if (tok) 1702 isl_stream_push_token(s, tok); 1703 goto error; 1704 } 1705 local = isl_int_get_si(tok->u.v); 1706 isl_token_free(tok); 1707 1708 tok = isl_stream_next_token_on_same_line(s); 1709 if (!tok || tok->type != ISL_TOKEN_VALUE) { 1710 isl_stream_error(s, tok, 1711 "expecting number of parameters"); 1712 if (tok) 1713 isl_stream_push_token(s, tok); 1714 goto error; 1715 } 1716 nparam = isl_int_get_si(tok->u.v); 1717 isl_token_free(tok); 1718 if (n_col != 1 + out + in + local + nparam + 1) { 1719 isl_stream_error(s, NULL, 1720 "dimensions don't match"); 1721 goto error; 1722 } 1723 } else 1724 out = n_col - 2 - nparam; 1725 bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row); 1726 if (!bmap) 1727 return NULL; 1728 1729 for (i = 0; i < local; ++i) { 1730 int k = isl_basic_map_alloc_div(bmap); 1731 if (k < 0) 1732 goto error; 1733 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local); 1734 } 1735 1736 for (i = 0; i < n_row; ++i) 1737 bmap = basic_map_read_polylib_constraint(s, bmap); 1738 1739 tok = isl_stream_next_token_on_same_line(s); 1740 if (tok) { 1741 isl_stream_error(s, tok, "unexpected extra token on line"); 1742 isl_stream_push_token(s, tok); 1743 goto error; 1744 } 1745 1746 bmap = isl_basic_map_simplify(bmap); 1747 bmap = isl_basic_map_finalize(bmap); 1748 return bmap; 1749error: 1750 isl_basic_map_free(bmap); 1751 return NULL; 1752} 1753 1754static struct isl_map *map_read_polylib(struct isl_stream *s) 1755{ 1756 struct isl_token *tok; 1757 struct isl_token *tok2; 1758 int i, n; 1759 struct isl_map *map; 1760 1761 tok = isl_stream_next_token(s); 1762 if (!tok) { 1763 isl_stream_error(s, NULL, "unexpected EOF"); 1764 return NULL; 1765 } 1766 tok2 = isl_stream_next_token_on_same_line(s); 1767 if (tok2 && tok2->type == ISL_TOKEN_VALUE) { 1768 isl_stream_push_token(s, tok2); 1769 isl_stream_push_token(s, tok); 1770 return isl_map_from_basic_map(basic_map_read_polylib(s)); 1771 } 1772 if (tok2) { 1773 isl_stream_error(s, tok2, "unexpected token"); 1774 isl_stream_push_token(s, tok2); 1775 isl_stream_push_token(s, tok); 1776 return NULL; 1777 } 1778 n = isl_int_get_si(tok->u.v); 1779 isl_token_free(tok); 1780 1781 isl_assert(s->ctx, n >= 1, return NULL); 1782 1783 map = isl_map_from_basic_map(basic_map_read_polylib(s)); 1784 1785 for (i = 1; map && i < n; ++i) 1786 map = isl_map_union(map, 1787 isl_map_from_basic_map(basic_map_read_polylib(s))); 1788 1789 return map; 1790} 1791 1792static int optional_power(struct isl_stream *s) 1793{ 1794 int pow; 1795 struct isl_token *tok; 1796 1797 tok = isl_stream_next_token(s); 1798 if (!tok) 1799 return 1; 1800 if (tok->type != '^') { 1801 isl_stream_push_token(s, tok); 1802 return 1; 1803 } 1804 isl_token_free(tok); 1805 tok = isl_stream_next_token(s); 1806 if (!tok || tok->type != ISL_TOKEN_VALUE) { 1807 isl_stream_error(s, tok, "expecting exponent"); 1808 if (tok) 1809 isl_stream_push_token(s, tok); 1810 return 1; 1811 } 1812 pow = isl_int_get_si(tok->u.v); 1813 isl_token_free(tok); 1814 return pow; 1815} 1816 1817static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s, 1818 __isl_keep isl_map *map, struct vars *v); 1819 1820static __isl_give isl_pw_qpolynomial *read_factor(struct isl_stream *s, 1821 __isl_keep isl_map *map, struct vars *v) 1822{ 1823 isl_pw_qpolynomial *pwqp; 1824 struct isl_token *tok; 1825 1826 tok = next_token(s); 1827 if (!tok) { 1828 isl_stream_error(s, NULL, "unexpected EOF"); 1829 return NULL; 1830 } 1831 if (tok->type == '(') { 1832 int pow; 1833 1834 isl_token_free(tok); 1835 pwqp = read_term(s, map, v); 1836 if (!pwqp) 1837 return NULL; 1838 if (isl_stream_eat(s, ')')) 1839 goto error; 1840 pow = optional_power(s); 1841 pwqp = isl_pw_qpolynomial_pow(pwqp, pow); 1842 } else if (tok->type == ISL_TOKEN_VALUE) { 1843 struct isl_token *tok2; 1844 isl_qpolynomial *qp; 1845 1846 tok2 = isl_stream_next_token(s); 1847 if (tok2 && tok2->type == '/') { 1848 isl_token_free(tok2); 1849 tok2 = next_token(s); 1850 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) { 1851 isl_stream_error(s, tok2, "expected denominator"); 1852 isl_token_free(tok); 1853 isl_token_free(tok2); 1854 return NULL; 1855 } 1856 qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map), 1857 tok->u.v, tok2->u.v); 1858 isl_token_free(tok2); 1859 } else { 1860 isl_stream_push_token(s, tok2); 1861 qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map), 1862 tok->u.v); 1863 } 1864 isl_token_free(tok); 1865 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp); 1866 } else if (tok->type == ISL_TOKEN_INFTY) { 1867 isl_qpolynomial *qp; 1868 isl_token_free(tok); 1869 qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map)); 1870 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp); 1871 } else if (tok->type == ISL_TOKEN_NAN) { 1872 isl_qpolynomial *qp; 1873 isl_token_free(tok); 1874 qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map)); 1875 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp); 1876 } else if (tok->type == ISL_TOKEN_IDENT) { 1877 int n = v->n; 1878 int pos = vars_pos(v, tok->u.s, -1); 1879 int pow; 1880 isl_qpolynomial *qp; 1881 if (pos < 0) { 1882 isl_token_free(tok); 1883 return NULL; 1884 } 1885 if (pos >= n) { 1886 vars_drop(v, v->n - n); 1887 isl_stream_error(s, tok, "unknown identifier"); 1888 isl_token_free(tok); 1889 return NULL; 1890 } 1891 isl_token_free(tok); 1892 pow = optional_power(s); 1893 qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow); 1894 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp); 1895 } else if (is_start_of_div(tok)) { 1896 isl_pw_aff *pwaff; 1897 int pow; 1898 1899 isl_stream_push_token(s, tok); 1900 pwaff = accept_div(s, isl_map_get_space(map), v); 1901 pow = optional_power(s); 1902 pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff); 1903 pwqp = isl_pw_qpolynomial_pow(pwqp, pow); 1904 } else if (tok->type == '-') { 1905 isl_token_free(tok); 1906 pwqp = read_factor(s, map, v); 1907 pwqp = isl_pw_qpolynomial_neg(pwqp); 1908 } else { 1909 isl_stream_error(s, tok, "unexpected isl_token"); 1910 isl_stream_push_token(s, tok); 1911 return NULL; 1912 } 1913 1914 if (isl_stream_eat_if_available(s, '*') || 1915 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) { 1916 isl_pw_qpolynomial *pwqp2; 1917 1918 pwqp2 = read_factor(s, map, v); 1919 pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2); 1920 } 1921 1922 return pwqp; 1923error: 1924 isl_pw_qpolynomial_free(pwqp); 1925 return NULL; 1926} 1927 1928static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s, 1929 __isl_keep isl_map *map, struct vars *v) 1930{ 1931 struct isl_token *tok; 1932 isl_pw_qpolynomial *pwqp; 1933 1934 pwqp = read_factor(s, map, v); 1935 1936 for (;;) { 1937 tok = next_token(s); 1938 if (!tok) 1939 return pwqp; 1940 1941 if (tok->type == '+') { 1942 isl_pw_qpolynomial *pwqp2; 1943 1944 isl_token_free(tok); 1945 pwqp2 = read_factor(s, map, v); 1946 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2); 1947 } else if (tok->type == '-') { 1948 isl_pw_qpolynomial *pwqp2; 1949 1950 isl_token_free(tok); 1951 pwqp2 = read_factor(s, map, v); 1952 pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2); 1953 } else if (tok->type == ISL_TOKEN_VALUE && 1954 isl_int_is_neg(tok->u.v)) { 1955 isl_pw_qpolynomial *pwqp2; 1956 1957 isl_stream_push_token(s, tok); 1958 pwqp2 = read_factor(s, map, v); 1959 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2); 1960 } else { 1961 isl_stream_push_token(s, tok); 1962 break; 1963 } 1964 } 1965 1966 return pwqp; 1967} 1968 1969static __isl_give isl_map *read_optional_formula(struct isl_stream *s, 1970 __isl_take isl_map *map, struct vars *v, int rational) 1971{ 1972 struct isl_token *tok; 1973 1974 tok = isl_stream_next_token(s); 1975 if (!tok) { 1976 isl_stream_error(s, NULL, "unexpected EOF"); 1977 goto error; 1978 } 1979 if (tok->type == ':' || 1980 (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) { 1981 isl_token_free(tok); 1982 map = read_formula(s, v, map, rational); 1983 } else 1984 isl_stream_push_token(s, tok); 1985 1986 return map; 1987error: 1988 isl_map_free(map); 1989 return NULL; 1990} 1991 1992static struct isl_obj obj_read_poly(struct isl_stream *s, 1993 __isl_take isl_map *map, struct vars *v, int n) 1994{ 1995 struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL }; 1996 isl_pw_qpolynomial *pwqp; 1997 struct isl_set *set; 1998 1999 pwqp = read_term(s, map, v); 2000 map = read_optional_formula(s, map, v, 0); 2001 set = isl_map_range(map); 2002 2003 pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set); 2004 2005 vars_drop(v, v->n - n); 2006 2007 obj.v = pwqp; 2008 return obj; 2009} 2010 2011static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s, 2012 __isl_take isl_set *set, struct vars *v, int n) 2013{ 2014 struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL }; 2015 isl_pw_qpolynomial *pwqp; 2016 isl_pw_qpolynomial_fold *pwf = NULL; 2017 2018 if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX)) 2019 return obj_read_poly(s, set, v, n); 2020 2021 if (isl_stream_eat(s, '(')) 2022 goto error; 2023 2024 pwqp = read_term(s, set, v); 2025 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, pwqp); 2026 2027 while (isl_stream_eat_if_available(s, ',')) { 2028 isl_pw_qpolynomial_fold *pwf_i; 2029 pwqp = read_term(s, set, v); 2030 pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, 2031 pwqp); 2032 pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i); 2033 } 2034 2035 if (isl_stream_eat(s, ')')) 2036 goto error; 2037 2038 set = read_optional_formula(s, set, v, 0); 2039 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set); 2040 2041 vars_drop(v, v->n - n); 2042 2043 obj.v = pwf; 2044 return obj; 2045error: 2046 isl_set_free(set); 2047 isl_pw_qpolynomial_fold_free(pwf); 2048 obj.type = isl_obj_none; 2049 return obj; 2050} 2051 2052static int is_rational(struct isl_stream *s) 2053{ 2054 struct isl_token *tok; 2055 2056 tok = isl_stream_next_token(s); 2057 if (!tok) 2058 return 0; 2059 if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) { 2060 isl_token_free(tok); 2061 isl_stream_eat(s, ':'); 2062 return 1; 2063 } 2064 2065 isl_stream_push_token(s, tok); 2066 2067 return 0; 2068} 2069 2070static struct isl_obj obj_read_body(struct isl_stream *s, 2071 __isl_take isl_map *map, struct vars *v) 2072{ 2073 struct isl_token *tok; 2074 struct isl_obj obj = { isl_obj_set, NULL }; 2075 int n = v->n; 2076 int rational; 2077 2078 rational = is_rational(s); 2079 if (rational) 2080 map = isl_map_set_rational(map); 2081 2082 if (isl_stream_next_token_is(s, ':')) { 2083 obj.type = isl_obj_set; 2084 obj.v = read_optional_formula(s, map, v, rational); 2085 return obj; 2086 } 2087 2088 if (!next_is_tuple(s)) 2089 return obj_read_poly_or_fold(s, map, v, n); 2090 2091 map = read_map_tuple(s, map, isl_dim_in, v, rational, 0); 2092 if (!map) 2093 goto error; 2094 tok = isl_stream_next_token(s); 2095 if (!tok) 2096 goto error; 2097 if (tok->type == ISL_TOKEN_TO) { 2098 obj.type = isl_obj_map; 2099 isl_token_free(tok); 2100 if (!next_is_tuple(s)) { 2101 isl_set *set = isl_map_domain(map); 2102 return obj_read_poly_or_fold(s, set, v, n); 2103 } 2104 map = read_map_tuple(s, map, isl_dim_out, v, rational, 0); 2105 if (!map) 2106 goto error; 2107 } else { 2108 map = isl_map_domain(map); 2109 isl_stream_push_token(s, tok); 2110 } 2111 2112 map = read_optional_formula(s, map, v, rational); 2113 2114 vars_drop(v, v->n - n); 2115 2116 obj.v = map; 2117 return obj; 2118error: 2119 isl_map_free(map); 2120 obj.type = isl_obj_none; 2121 return obj; 2122} 2123 2124static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj) 2125{ 2126 if (obj.type == isl_obj_map) { 2127 obj.v = isl_union_map_from_map(obj.v); 2128 obj.type = isl_obj_union_map; 2129 } else if (obj.type == isl_obj_set) { 2130 obj.v = isl_union_set_from_set(obj.v); 2131 obj.type = isl_obj_union_set; 2132 } else if (obj.type == isl_obj_pw_qpolynomial) { 2133 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v); 2134 obj.type = isl_obj_union_pw_qpolynomial; 2135 } else if (obj.type == isl_obj_pw_qpolynomial_fold) { 2136 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v); 2137 obj.type = isl_obj_union_pw_qpolynomial_fold; 2138 } else 2139 isl_assert(ctx, 0, goto error); 2140 return obj; 2141error: 2142 obj.type->free(obj.v); 2143 obj.type = isl_obj_none; 2144 return obj; 2145} 2146 2147static struct isl_obj obj_add(struct isl_ctx *ctx, 2148 struct isl_obj obj1, struct isl_obj obj2) 2149{ 2150 if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set) 2151 obj1 = to_union(ctx, obj1); 2152 if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set) 2153 obj2 = to_union(ctx, obj2); 2154 if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map) 2155 obj1 = to_union(ctx, obj1); 2156 if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map) 2157 obj2 = to_union(ctx, obj2); 2158 if (obj1.type == isl_obj_pw_qpolynomial && 2159 obj2.type == isl_obj_union_pw_qpolynomial) 2160 obj1 = to_union(ctx, obj1); 2161 if (obj1.type == isl_obj_union_pw_qpolynomial && 2162 obj2.type == isl_obj_pw_qpolynomial) 2163 obj2 = to_union(ctx, obj2); 2164 if (obj1.type == isl_obj_pw_qpolynomial_fold && 2165 obj2.type == isl_obj_union_pw_qpolynomial_fold) 2166 obj1 = to_union(ctx, obj1); 2167 if (obj1.type == isl_obj_union_pw_qpolynomial_fold && 2168 obj2.type == isl_obj_pw_qpolynomial_fold) 2169 obj2 = to_union(ctx, obj2); 2170 isl_assert(ctx, obj1.type == obj2.type, goto error); 2171 if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) { 2172 obj1 = to_union(ctx, obj1); 2173 obj2 = to_union(ctx, obj2); 2174 } 2175 if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) { 2176 obj1 = to_union(ctx, obj1); 2177 obj2 = to_union(ctx, obj2); 2178 } 2179 if (obj1.type == isl_obj_pw_qpolynomial && 2180 !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) { 2181 obj1 = to_union(ctx, obj1); 2182 obj2 = to_union(ctx, obj2); 2183 } 2184 if (obj1.type == isl_obj_pw_qpolynomial_fold && 2185 !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) { 2186 obj1 = to_union(ctx, obj1); 2187 obj2 = to_union(ctx, obj2); 2188 } 2189 obj1.v = obj1.type->add(obj1.v, obj2.v); 2190 return obj1; 2191error: 2192 obj1.type->free(obj1.v); 2193 obj2.type->free(obj2.v); 2194 obj1.type = isl_obj_none; 2195 obj1.v = NULL; 2196 return obj1; 2197} 2198 2199static struct isl_obj obj_read(struct isl_stream *s) 2200{ 2201 isl_map *map = NULL; 2202 struct isl_token *tok; 2203 struct vars *v = NULL; 2204 struct isl_obj obj = { isl_obj_set, NULL }; 2205 2206 tok = next_token(s); 2207 if (!tok) { 2208 isl_stream_error(s, NULL, "unexpected EOF"); 2209 goto error; 2210 } 2211 if (tok->type == ISL_TOKEN_VALUE) { 2212 struct isl_token *tok2; 2213 struct isl_map *map; 2214 2215 tok2 = isl_stream_next_token(s); 2216 if (!tok2 || tok2->type != ISL_TOKEN_VALUE || 2217 isl_int_is_neg(tok2->u.v)) { 2218 if (tok2) 2219 isl_stream_push_token(s, tok2); 2220 obj.type = isl_obj_int; 2221 obj.v = isl_int_obj_alloc(s->ctx, tok->u.v); 2222 isl_token_free(tok); 2223 return obj; 2224 } 2225 isl_stream_push_token(s, tok2); 2226 isl_stream_push_token(s, tok); 2227 map = map_read_polylib(s); 2228 if (!map) 2229 goto error; 2230 if (isl_map_may_be_set(map)) 2231 obj.v = isl_map_range(map); 2232 else { 2233 obj.type = isl_obj_map; 2234 obj.v = map; 2235 } 2236 return obj; 2237 } 2238 v = vars_new(s->ctx); 2239 if (!v) { 2240 isl_stream_push_token(s, tok); 2241 goto error; 2242 } 2243 map = isl_map_universe(isl_space_params_alloc(s->ctx, 0)); 2244 if (tok->type == '[') { 2245 isl_stream_push_token(s, tok); 2246 map = read_map_tuple(s, map, isl_dim_param, v, 0, 0); 2247 if (!map) 2248 goto error; 2249 tok = isl_stream_next_token(s); 2250 if (!tok || tok->type != ISL_TOKEN_TO) { 2251 isl_stream_error(s, tok, "expecting '->'"); 2252 if (tok) 2253 isl_stream_push_token(s, tok); 2254 goto error; 2255 } 2256 isl_token_free(tok); 2257 tok = isl_stream_next_token(s); 2258 } 2259 if (!tok || tok->type != '{') { 2260 isl_stream_error(s, tok, "expecting '{'"); 2261 if (tok) 2262 isl_stream_push_token(s, tok); 2263 goto error; 2264 } 2265 isl_token_free(tok); 2266 2267 tok = isl_stream_next_token(s); 2268 if (!tok) 2269 ; 2270 else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) { 2271 isl_token_free(tok); 2272 if (isl_stream_eat(s, '=')) 2273 goto error; 2274 map = read_map_tuple(s, map, isl_dim_param, v, 0, 1); 2275 if (!map) 2276 goto error; 2277 } else if (tok->type == '}') { 2278 obj.type = isl_obj_union_set; 2279 obj.v = isl_union_set_empty(isl_map_get_space(map)); 2280 isl_token_free(tok); 2281 goto done; 2282 } else 2283 isl_stream_push_token(s, tok); 2284 2285 for (;;) { 2286 struct isl_obj o; 2287 tok = NULL; 2288 o = obj_read_body(s, isl_map_copy(map), v); 2289 if (o.type == isl_obj_none || !o.v) 2290 goto error; 2291 if (!obj.v) 2292 obj = o; 2293 else { 2294 obj = obj_add(s->ctx, obj, o); 2295 if (obj.type == isl_obj_none || !obj.v) 2296 goto error; 2297 } 2298 tok = isl_stream_next_token(s); 2299 if (!tok || tok->type != ';') 2300 break; 2301 isl_token_free(tok); 2302 if (isl_stream_next_token_is(s, '}')) { 2303 tok = isl_stream_next_token(s); 2304 break; 2305 } 2306 } 2307 2308 if (tok && tok->type == '}') { 2309 isl_token_free(tok); 2310 } else { 2311 isl_stream_error(s, tok, "unexpected isl_token"); 2312 if (tok) 2313 isl_token_free(tok); 2314 goto error; 2315 } 2316done: 2317 vars_free(v); 2318 isl_map_free(map); 2319 2320 return obj; 2321error: 2322 isl_map_free(map); 2323 obj.type->free(obj.v); 2324 if (v) 2325 vars_free(v); 2326 obj.v = NULL; 2327 return obj; 2328} 2329 2330struct isl_obj isl_stream_read_obj(struct isl_stream *s) 2331{ 2332 return obj_read(s); 2333} 2334 2335__isl_give isl_map *isl_stream_read_map(struct isl_stream *s) 2336{ 2337 struct isl_obj obj; 2338 2339 obj = obj_read(s); 2340 if (obj.v) 2341 isl_assert(s->ctx, obj.type == isl_obj_map || 2342 obj.type == isl_obj_set, goto error); 2343 2344 if (obj.type == isl_obj_set) 2345 obj.v = isl_map_from_range(obj.v); 2346 2347 return obj.v; 2348error: 2349 obj.type->free(obj.v); 2350 return NULL; 2351} 2352 2353__isl_give isl_set *isl_stream_read_set(struct isl_stream *s) 2354{ 2355 struct isl_obj obj; 2356 2357 obj = obj_read(s); 2358 if (obj.v) { 2359 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) { 2360 obj.v = isl_map_range(obj.v); 2361 obj.type = isl_obj_set; 2362 } 2363 isl_assert(s->ctx, obj.type == isl_obj_set, goto error); 2364 } 2365 2366 return obj.v; 2367error: 2368 obj.type->free(obj.v); 2369 return NULL; 2370} 2371 2372__isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s) 2373{ 2374 struct isl_obj obj; 2375 2376 obj = obj_read(s); 2377 if (obj.type == isl_obj_map) { 2378 obj.type = isl_obj_union_map; 2379 obj.v = isl_union_map_from_map(obj.v); 2380 } 2381 if (obj.type == isl_obj_set) { 2382 obj.type = isl_obj_union_set; 2383 obj.v = isl_union_set_from_set(obj.v); 2384 } 2385 if (obj.v && obj.type == isl_obj_union_set && 2386 isl_union_set_is_empty(obj.v)) 2387 obj.type = isl_obj_union_map; 2388 if (obj.v && obj.type != isl_obj_union_map) 2389 isl_die(s->ctx, isl_error_invalid, "invalid input", goto error); 2390 2391 return obj.v; 2392error: 2393 obj.type->free(obj.v); 2394 return NULL; 2395} 2396 2397__isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s) 2398{ 2399 struct isl_obj obj; 2400 2401 obj = obj_read(s); 2402 if (obj.type == isl_obj_set) { 2403 obj.type = isl_obj_union_set; 2404 obj.v = isl_union_set_from_set(obj.v); 2405 } 2406 if (obj.v) 2407 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error); 2408 2409 return obj.v; 2410error: 2411 obj.type->free(obj.v); 2412 return NULL; 2413} 2414 2415static __isl_give isl_basic_map *basic_map_read(struct isl_stream *s) 2416{ 2417 struct isl_obj obj; 2418 struct isl_map *map; 2419 struct isl_basic_map *bmap; 2420 2421 obj = obj_read(s); 2422 map = obj.v; 2423 if (!map) 2424 return NULL; 2425 2426 isl_assert(map->ctx, map->n <= 1, goto error); 2427 2428 if (map->n == 0) 2429 bmap = isl_basic_map_empty_like_map(map); 2430 else 2431 bmap = isl_basic_map_copy(map->p[0]); 2432 2433 isl_map_free(map); 2434 2435 return bmap; 2436error: 2437 isl_map_free(map); 2438 return NULL; 2439} 2440 2441static __isl_give isl_basic_set *basic_set_read(struct isl_stream *s) 2442{ 2443 isl_basic_map *bmap; 2444 bmap = basic_map_read(s); 2445 if (!bmap) 2446 return NULL; 2447 if (!isl_basic_map_may_be_set(bmap)) 2448 isl_die(s->ctx, isl_error_invalid, 2449 "input is not a set", goto error); 2450 return isl_basic_map_range(bmap); 2451error: 2452 isl_basic_map_free(bmap); 2453 return NULL; 2454} 2455 2456__isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx, 2457 FILE *input) 2458{ 2459 struct isl_basic_map *bmap; 2460 struct isl_stream *s = isl_stream_new_file(ctx, input); 2461 if (!s) 2462 return NULL; 2463 bmap = basic_map_read(s); 2464 isl_stream_free(s); 2465 return bmap; 2466} 2467 2468__isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx, 2469 FILE *input) 2470{ 2471 isl_basic_set *bset; 2472 struct isl_stream *s = isl_stream_new_file(ctx, input); 2473 if (!s) 2474 return NULL; 2475 bset = basic_set_read(s); 2476 isl_stream_free(s); 2477 return bset; 2478} 2479 2480struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx, 2481 const char *str) 2482{ 2483 struct isl_basic_map *bmap; 2484 struct isl_stream *s = isl_stream_new_str(ctx, str); 2485 if (!s) 2486 return NULL; 2487 bmap = basic_map_read(s); 2488 isl_stream_free(s); 2489 return bmap; 2490} 2491 2492struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx, 2493 const char *str) 2494{ 2495 isl_basic_set *bset; 2496 struct isl_stream *s = isl_stream_new_str(ctx, str); 2497 if (!s) 2498 return NULL; 2499 bset = basic_set_read(s); 2500 isl_stream_free(s); 2501 return bset; 2502} 2503 2504__isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx, 2505 FILE *input) 2506{ 2507 struct isl_map *map; 2508 struct isl_stream *s = isl_stream_new_file(ctx, input); 2509 if (!s) 2510 return NULL; 2511 map = isl_stream_read_map(s); 2512 isl_stream_free(s); 2513 return map; 2514} 2515 2516__isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx, 2517 const char *str) 2518{ 2519 struct isl_map *map; 2520 struct isl_stream *s = isl_stream_new_str(ctx, str); 2521 if (!s) 2522 return NULL; 2523 map = isl_stream_read_map(s); 2524 isl_stream_free(s); 2525 return map; 2526} 2527 2528__isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx, 2529 FILE *input) 2530{ 2531 isl_set *set; 2532 struct isl_stream *s = isl_stream_new_file(ctx, input); 2533 if (!s) 2534 return NULL; 2535 set = isl_stream_read_set(s); 2536 isl_stream_free(s); 2537 return set; 2538} 2539 2540struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx, 2541 const char *str) 2542{ 2543 isl_set *set; 2544 struct isl_stream *s = isl_stream_new_str(ctx, str); 2545 if (!s) 2546 return NULL; 2547 set = isl_stream_read_set(s); 2548 isl_stream_free(s); 2549 return set; 2550} 2551 2552__isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx, 2553 FILE *input) 2554{ 2555 isl_union_map *umap; 2556 struct isl_stream *s = isl_stream_new_file(ctx, input); 2557 if (!s) 2558 return NULL; 2559 umap = isl_stream_read_union_map(s); 2560 isl_stream_free(s); 2561 return umap; 2562} 2563 2564__isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx, 2565 const char *str) 2566{ 2567 isl_union_map *umap; 2568 struct isl_stream *s = isl_stream_new_str(ctx, str); 2569 if (!s) 2570 return NULL; 2571 umap = isl_stream_read_union_map(s); 2572 isl_stream_free(s); 2573 return umap; 2574} 2575 2576__isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx, 2577 FILE *input) 2578{ 2579 isl_union_set *uset; 2580 struct isl_stream *s = isl_stream_new_file(ctx, input); 2581 if (!s) 2582 return NULL; 2583 uset = isl_stream_read_union_set(s); 2584 isl_stream_free(s); 2585 return uset; 2586} 2587 2588__isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx, 2589 const char *str) 2590{ 2591 isl_union_set *uset; 2592 struct isl_stream *s = isl_stream_new_str(ctx, str); 2593 if (!s) 2594 return NULL; 2595 uset = isl_stream_read_union_set(s); 2596 isl_stream_free(s); 2597 return uset; 2598} 2599 2600static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s) 2601{ 2602 struct isl_vec *vec = NULL; 2603 struct isl_token *tok; 2604 unsigned size; 2605 int j; 2606 2607 tok = isl_stream_next_token(s); 2608 if (!tok || tok->type != ISL_TOKEN_VALUE) { 2609 isl_stream_error(s, tok, "expecting vector length"); 2610 goto error; 2611 } 2612 2613 size = isl_int_get_si(tok->u.v); 2614 isl_token_free(tok); 2615 2616 vec = isl_vec_alloc(s->ctx, size); 2617 2618 for (j = 0; j < size; ++j) { 2619 tok = isl_stream_next_token(s); 2620 if (!tok || tok->type != ISL_TOKEN_VALUE) { 2621 isl_stream_error(s, tok, "expecting constant value"); 2622 goto error; 2623 } 2624 isl_int_set(vec->el[j], tok->u.v); 2625 isl_token_free(tok); 2626 } 2627 2628 return vec; 2629error: 2630 isl_token_free(tok); 2631 isl_vec_free(vec); 2632 return NULL; 2633} 2634 2635static __isl_give isl_vec *vec_read(struct isl_stream *s) 2636{ 2637 return isl_vec_read_polylib(s); 2638} 2639 2640__isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input) 2641{ 2642 isl_vec *v; 2643 struct isl_stream *s = isl_stream_new_file(ctx, input); 2644 if (!s) 2645 return NULL; 2646 v = vec_read(s); 2647 isl_stream_free(s); 2648 return v; 2649} 2650 2651__isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial( 2652 struct isl_stream *s) 2653{ 2654 struct isl_obj obj; 2655 2656 obj = obj_read(s); 2657 if (obj.v) 2658 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial, 2659 goto error); 2660 2661 return obj.v; 2662error: 2663 obj.type->free(obj.v); 2664 return NULL; 2665} 2666 2667__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx, 2668 const char *str) 2669{ 2670 isl_pw_qpolynomial *pwqp; 2671 struct isl_stream *s = isl_stream_new_str(ctx, str); 2672 if (!s) 2673 return NULL; 2674 pwqp = isl_stream_read_pw_qpolynomial(s); 2675 isl_stream_free(s); 2676 return pwqp; 2677} 2678 2679__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx, 2680 FILE *input) 2681{ 2682 isl_pw_qpolynomial *pwqp; 2683 struct isl_stream *s = isl_stream_new_file(ctx, input); 2684 if (!s) 2685 return NULL; 2686 pwqp = isl_stream_read_pw_qpolynomial(s); 2687 isl_stream_free(s); 2688 return pwqp; 2689} 2690 2691/* Is the next token an identifer not in "v"? 2692 */ 2693static int next_is_fresh_ident(struct isl_stream *s, struct vars *v) 2694{ 2695 int n = v->n; 2696 int fresh; 2697 struct isl_token *tok; 2698 2699 tok = isl_stream_next_token(s); 2700 if (!tok) 2701 return 0; 2702 fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n; 2703 isl_stream_push_token(s, tok); 2704 2705 vars_drop(v, v->n - n); 2706 2707 return fresh; 2708} 2709 2710/* First read the domain of the affine expression, which may be 2711 * a parameter space or a set. 2712 * The tricky part is that we don't know if the domain is a set or not, 2713 * so when we are trying to read the domain, we may actually be reading 2714 * the affine expression itself (defined on a parameter domains) 2715 * If the tuple we are reading is named, we assume it's the domain. 2716 * Also, if inside the tuple, the first thing we find is a nested tuple 2717 * or a new identifier, we again assume it's the domain. 2718 * Otherwise, we assume we are reading an affine expression. 2719 */ 2720static __isl_give isl_set *read_aff_domain(struct isl_stream *s, 2721 __isl_take isl_set *dom, struct vars *v) 2722{ 2723 struct isl_token *tok; 2724 2725 tok = isl_stream_next_token(s); 2726 if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) { 2727 isl_stream_push_token(s, tok); 2728 return read_map_tuple(s, dom, isl_dim_set, v, 1, 0); 2729 } 2730 if (!tok || tok->type != '[') { 2731 isl_stream_error(s, tok, "expecting '['"); 2732 goto error; 2733 } 2734 if (next_is_tuple(s) || next_is_fresh_ident(s, v)) { 2735 isl_stream_push_token(s, tok); 2736 dom = read_map_tuple(s, dom, isl_dim_set, v, 1, 0); 2737 } else 2738 isl_stream_push_token(s, tok); 2739 2740 return dom; 2741error: 2742 if (tok) 2743 isl_stream_push_token(s, tok); 2744 isl_set_free(dom); 2745 return NULL; 2746} 2747 2748/* Read an affine expression from "s". 2749 */ 2750__isl_give isl_aff *isl_stream_read_aff(struct isl_stream *s) 2751{ 2752 isl_aff *aff; 2753 isl_multi_aff *ma; 2754 2755 ma = isl_stream_read_multi_aff(s); 2756 if (!ma) 2757 return NULL; 2758 if (isl_multi_aff_dim(ma, isl_dim_out) != 1) 2759 isl_die(s->ctx, isl_error_invalid, 2760 "expecting single affine expression", 2761 goto error); 2762 2763 aff = isl_multi_aff_get_aff(ma, 0); 2764 isl_multi_aff_free(ma); 2765 return aff; 2766error: 2767 isl_multi_aff_free(ma); 2768 return NULL; 2769} 2770 2771/* Read a piecewise affine expression from "s" with domain (space) "dom". 2772 */ 2773static __isl_give isl_pw_aff *read_pw_aff_with_dom(struct isl_stream *s, 2774 __isl_take isl_set *dom, struct vars *v) 2775{ 2776 isl_pw_aff *pwaff = NULL; 2777 2778 if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO)) 2779 goto error; 2780 2781 if (isl_stream_eat(s, '[')) 2782 goto error; 2783 2784 pwaff = accept_affine(s, isl_set_get_space(dom), v); 2785 2786 if (isl_stream_eat(s, ']')) 2787 goto error; 2788 2789 dom = read_optional_formula(s, dom, v, 0); 2790 pwaff = isl_pw_aff_intersect_domain(pwaff, dom); 2791 2792 return pwaff; 2793error: 2794 isl_set_free(dom); 2795 isl_pw_aff_free(pwaff); 2796 return NULL; 2797} 2798 2799__isl_give isl_pw_aff *isl_stream_read_pw_aff(struct isl_stream *s) 2800{ 2801 struct vars *v; 2802 isl_set *dom = NULL; 2803 isl_set *aff_dom; 2804 isl_pw_aff *pa = NULL; 2805 int n; 2806 2807 v = vars_new(s->ctx); 2808 if (!v) 2809 return NULL; 2810 2811 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0)); 2812 if (next_is_tuple(s)) { 2813 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0); 2814 if (isl_stream_eat(s, ISL_TOKEN_TO)) 2815 goto error; 2816 } 2817 if (isl_stream_eat(s, '{')) 2818 goto error; 2819 2820 n = v->n; 2821 aff_dom = read_aff_domain(s, isl_set_copy(dom), v); 2822 pa = read_pw_aff_with_dom(s, aff_dom, v); 2823 vars_drop(v, v->n - n); 2824 2825 while (isl_stream_eat_if_available(s, ';')) { 2826 isl_pw_aff *pa_i; 2827 2828 n = v->n; 2829 aff_dom = read_aff_domain(s, isl_set_copy(dom), v); 2830 pa_i = read_pw_aff_with_dom(s, aff_dom, v); 2831 vars_drop(v, v->n - n); 2832 2833 pa = isl_pw_aff_union_add(pa, pa_i); 2834 } 2835 2836 if (isl_stream_eat(s, '}')) 2837 goto error; 2838 2839 vars_free(v); 2840 isl_set_free(dom); 2841 return pa; 2842error: 2843 vars_free(v); 2844 isl_set_free(dom); 2845 isl_pw_aff_free(pa); 2846 return NULL; 2847} 2848 2849__isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str) 2850{ 2851 isl_aff *aff; 2852 struct isl_stream *s = isl_stream_new_str(ctx, str); 2853 if (!s) 2854 return NULL; 2855 aff = isl_stream_read_aff(s); 2856 isl_stream_free(s); 2857 return aff; 2858} 2859 2860__isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str) 2861{ 2862 isl_pw_aff *pa; 2863 struct isl_stream *s = isl_stream_new_str(ctx, str); 2864 if (!s) 2865 return NULL; 2866 pa = isl_stream_read_pw_aff(s); 2867 isl_stream_free(s); 2868 return pa; 2869} 2870 2871/* Read an isl_pw_multi_aff from "s". 2872 * We currently read a generic object and if it turns out to be a set or 2873 * a map, we convert that to an isl_pw_multi_aff. 2874 * It would be more efficient if we were to construct the isl_pw_multi_aff 2875 * directly. 2876 */ 2877__isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(struct isl_stream *s) 2878{ 2879 struct isl_obj obj; 2880 2881 obj = obj_read(s); 2882 if (!obj.v) 2883 return NULL; 2884 2885 if (obj.type == isl_obj_map) 2886 return isl_pw_multi_aff_from_map(obj.v); 2887 if (obj.type == isl_obj_set) 2888 return isl_pw_multi_aff_from_set(obj.v); 2889 2890 obj.type->free(obj.v); 2891 isl_die(s->ctx, isl_error_invalid, "unexpected object type", 2892 return NULL); 2893} 2894 2895__isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx, 2896 const char *str) 2897{ 2898 isl_pw_multi_aff *pma; 2899 struct isl_stream *s = isl_stream_new_str(ctx, str); 2900 if (!s) 2901 return NULL; 2902 pma = isl_stream_read_pw_multi_aff(s); 2903 isl_stream_free(s); 2904 return pma; 2905} 2906 2907/* Read an isl_union_pw_multi_aff from "s". 2908 * We currently read a generic object and if it turns out to be a set or 2909 * a map, we convert that to an isl_union_pw_multi_aff. 2910 * It would be more efficient if we were to construct 2911 * the isl_union_pw_multi_aff directly. 2912 */ 2913__isl_give isl_union_pw_multi_aff *isl_stream_read_union_pw_multi_aff( 2914 struct isl_stream *s) 2915{ 2916 struct isl_obj obj; 2917 2918 obj = obj_read(s); 2919 if (!obj.v) 2920 return NULL; 2921 2922 if (obj.type == isl_obj_map || obj.type == isl_obj_set) 2923 obj = to_union(s->ctx, obj); 2924 if (obj.type == isl_obj_union_map) 2925 return isl_union_pw_multi_aff_from_union_map(obj.v); 2926 if (obj.type == isl_obj_union_set) 2927 return isl_union_pw_multi_aff_from_union_set(obj.v); 2928 2929 obj.type->free(obj.v); 2930 isl_die(s->ctx, isl_error_invalid, "unexpected object type", 2931 return NULL); 2932} 2933 2934/* Read an isl_union_pw_multi_aff from "str". 2935 */ 2936__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_read_from_str( 2937 isl_ctx *ctx, const char *str) 2938{ 2939 isl_union_pw_multi_aff *upma; 2940 struct isl_stream *s = isl_stream_new_str(ctx, str); 2941 if (!s) 2942 return NULL; 2943 upma = isl_stream_read_union_pw_multi_aff(s); 2944 isl_stream_free(s); 2945 return upma; 2946} 2947 2948/* Assuming "pa" represents a single affine expression defined on a universe 2949 * domain, extract this affine expression. 2950 */ 2951static __isl_give isl_aff *aff_from_pw_aff(__isl_take isl_pw_aff *pa) 2952{ 2953 isl_aff *aff; 2954 2955 if (!pa) 2956 return NULL; 2957 if (pa->n != 1) 2958 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid, 2959 "expecting single affine expression", 2960 goto error); 2961 if (!isl_set_plain_is_universe(pa->p[0].set)) 2962 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid, 2963 "expecting universe domain", 2964 goto error); 2965 2966 aff = isl_aff_copy(pa->p[0].aff); 2967 isl_pw_aff_free(pa); 2968 return aff; 2969error: 2970 isl_pw_aff_free(pa); 2971 return NULL; 2972} 2973 2974/* Read a multi-affine expression from "s". 2975 * If the multi-affine expression has a domain, then then tuple 2976 * representing this domain cannot involve any affine expressions. 2977 * The tuple representing the actual expressions needs to consist 2978 * of only affine expressions. Moreover, these expressions can 2979 * only depend on parameters and input dimensions and not on other 2980 * output dimensions. 2981 */ 2982__isl_give isl_multi_aff *isl_stream_read_multi_aff(struct isl_stream *s) 2983{ 2984 struct vars *v; 2985 isl_set *dom = NULL; 2986 isl_multi_pw_aff *tuple = NULL; 2987 int dim, i, n; 2988 isl_space *space, *dom_space; 2989 isl_multi_aff *ma = NULL; 2990 2991 v = vars_new(s->ctx); 2992 if (!v) 2993 return NULL; 2994 2995 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0)); 2996 if (next_is_tuple(s)) { 2997 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0); 2998 if (isl_stream_eat(s, ISL_TOKEN_TO)) 2999 goto error; 3000 } 3001 if (!isl_set_plain_is_universe(dom)) 3002 isl_die(s->ctx, isl_error_invalid, 3003 "expecting universe parameter domain", goto error); 3004 if (isl_stream_eat(s, '{')) 3005 goto error; 3006 3007 tuple = read_tuple(s, v, 0, 0); 3008 if (!tuple) 3009 goto error; 3010 if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) { 3011 isl_set *set; 3012 isl_space *space; 3013 int has_expr; 3014 3015 has_expr = tuple_has_expr(tuple); 3016 if (has_expr < 0) 3017 goto error; 3018 if (has_expr) 3019 isl_die(s->ctx, isl_error_invalid, 3020 "expecting universe domain", goto error); 3021 space = isl_space_range(isl_multi_pw_aff_get_space(tuple)); 3022 set = isl_set_universe(space); 3023 dom = isl_set_intersect_params(set, dom); 3024 isl_multi_pw_aff_free(tuple); 3025 tuple = read_tuple(s, v, 0, 0); 3026 if (!tuple) 3027 goto error; 3028 } 3029 3030 if (isl_stream_eat(s, '}')) 3031 goto error; 3032 3033 n = isl_multi_pw_aff_dim(tuple, isl_dim_out); 3034 dim = isl_set_dim(dom, isl_dim_all); 3035 dom_space = isl_set_get_space(dom); 3036 space = isl_space_range(isl_multi_pw_aff_get_space(tuple)); 3037 space = isl_space_align_params(space, isl_space_copy(dom_space)); 3038 if (!isl_space_is_params(dom_space)) 3039 space = isl_space_map_from_domain_and_range( 3040 isl_space_copy(dom_space), space); 3041 isl_space_free(dom_space); 3042 ma = isl_multi_aff_alloc(space); 3043 3044 for (i = 0; i < n; ++i) { 3045 isl_pw_aff *pa; 3046 isl_aff *aff; 3047 pa = isl_multi_pw_aff_get_pw_aff(tuple, i); 3048 aff = aff_from_pw_aff(pa); 3049 if (!aff) 3050 goto error; 3051 if (isl_aff_involves_dims(aff, isl_dim_in, dim, i + 1)) { 3052 isl_aff_free(aff); 3053 isl_die(s->ctx, isl_error_invalid, 3054 "not an affine expression", goto error); 3055 } 3056 aff = isl_aff_drop_dims(aff, isl_dim_in, dim, n); 3057 space = isl_multi_aff_get_domain_space(ma); 3058 aff = isl_aff_reset_domain_space(aff, space); 3059 ma = isl_multi_aff_set_aff(ma, i, aff); 3060 } 3061 3062 isl_multi_pw_aff_free(tuple); 3063 vars_free(v); 3064 isl_set_free(dom); 3065 return ma; 3066error: 3067 isl_multi_pw_aff_free(tuple); 3068 vars_free(v); 3069 isl_set_free(dom); 3070 isl_multi_aff_free(ma); 3071 return NULL; 3072} 3073 3074__isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx, 3075 const char *str) 3076{ 3077 isl_multi_aff *maff; 3078 struct isl_stream *s = isl_stream_new_str(ctx, str); 3079 if (!s) 3080 return NULL; 3081 maff = isl_stream_read_multi_aff(s); 3082 isl_stream_free(s); 3083 return maff; 3084} 3085 3086__isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial( 3087 struct isl_stream *s) 3088{ 3089 struct isl_obj obj; 3090 3091 obj = obj_read(s); 3092 if (obj.type == isl_obj_pw_qpolynomial) { 3093 obj.type = isl_obj_union_pw_qpolynomial; 3094 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v); 3095 } 3096 if (obj.v) 3097 isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial, 3098 goto error); 3099 3100 return obj.v; 3101error: 3102 obj.type->free(obj.v); 3103 return NULL; 3104} 3105 3106__isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str( 3107 isl_ctx *ctx, const char *str) 3108{ 3109 isl_union_pw_qpolynomial *upwqp; 3110 struct isl_stream *s = isl_stream_new_str(ctx, str); 3111 if (!s) 3112 return NULL; 3113 upwqp = isl_stream_read_union_pw_qpolynomial(s); 3114 isl_stream_free(s); 3115 return upwqp; 3116} 3117