evalue_read.c

   1 #include <assert.h>
   2 #include <barvinok/util.h>
   3 #include "evalue_read.h"
   4
   5 #define ALLOC(type) (type*)malloc(sizeof(type))
   6 #define ALLOCN(type,n) (type*)malloc((n) * sizeof(type))
   7
   8 enum token_type { TOKEN_UNKNOWN = 256, TOKEN_VALUE, TOKEN_IDENT, TOKEN_GE,
   9                   TOKEN_NE, TOKEN_UNION, TOKEN_VARS };
  10
  11 struct token {
  12     enum token_type  type;
  13
  14     int line;
  15     int col;
  16
  17     union {
  18         Value   v;
  19         char    *s;
  20     } u;
  21 };
  22
  23 static struct token *token_new(int line, int col)
  24 {
  25     struct token *tok = ALLOC(struct token);
  26     tok->line = line;
  27     tok->col = col;
  28     return tok;
  29 }
  30
  31 void token_free(struct token *tok)
  32 {
  33     if (tok->type == TOKEN_VALUE)
  34         value_clear(tok->u.v);
  35     else if (tok->type == TOKEN_IDENT)
  36         free(tok->u.s);
  37     free(tok);
  38 }
  39
  40 struct stream {
  41     FILE            *file;
  42     const char      *str;
  43     int             line;
  44     int             col;
  45     int             eof;
  46
  47     char            *buffer;
  48     size_t          size;
  49     size_t          len;
  50     int             c;
  51
  52     struct token    *tokens[5];
  53     int             n_token;
  54 };
  55
  56 static struct stream* stream_new()
  57 {
  58     int i;
  59     struct stream *s = ALLOC(struct stream);
  60     s->size = 256;
  61     s->file = NULL;
  62     s->str = NULL;
  63     s->buffer = (char*)malloc(s->size);
  64     s->len = 0;
  65     s->line = 1;
  66     s->col = 0;
  67     s->eof = 0;
  68     s->c = -1;
  69     for (i = 0; i < 5; ++i)
  70         s->tokens[i] = NULL;
  71     s->n_token = 0;
  72     return s;
  73 }
  74
  75 static struct stream* stream_new_file(FILE *file)
  76 {
  77     struct stream *s = stream_new();
  78     s->file = file;
  79     return s;
  80 }
  81
  82 static struct stream* stream_new_str(const char *str)
  83 {
  84     struct stream *s = stream_new();
  85     s->str = str;
  86     return s;
  87 }
  88
  89 static int stream_getc(struct stream *s)
  90 {
  91     int c;
  92     if (s->eof)
  93         return -1;
  94     if (s->file)
  95         c = fgetc(s->file);
  96     else {
  97         c = *s->str++;
  98         if (c == '\0')
  99             c = -1;
 100     }
 101     if (c == -1)
 102         s->eof = 1;
 103     if (!s->eof) {
 104         if (s->c == '\n') {
 105             s->line++;
 106             s->col = 0;
 107         } else
 108             s->col++;
 109     }
 110     s->c = c;
 111     return c;
 112 }
 113
 114 static void stream_ungetc(struct stream *s, int c)
 115 {
 116     if (s->file)
 117         ungetc(c, s->file);
 118     else
 119         --s->str;
 120     s->c = -1;
 121 }
 122
 123 static void stream_push_char(struct stream *s, int c)
 124 {
 125     if (s->len >= s->size) {
 126         s->size = (3*s->size)/2;
 127         s->buffer = (char*)realloc(s->buffer, s->size);
 128     }
 129     s->buffer[s->len++] = c;
 130 }
 131
 132 static struct token *stream_push_token(struct stream *s, struct token *tok)
 133 {
 134     assert(s->n_token < 5);
 135     s->tokens[s->n_token++] = tok;
 136 }
 137
 138 static struct token *stream_next_token(struct stream *s)
 139 {
 140     int c;
 141     struct token *tok;
 142     int line, col;
 143
 144     if (s->n_token)
 145         return s->tokens[--s->n_token];
 146
 147     s->len = 0;
 148
 149     /* skip spaces */
 150     while ((c = stream_getc(s)) != -1 && isspace(c))
 151         /* nothing */
 152         ;
 153
 154     line = s->line;
 155     col = s->col;
 156
 157     if (c == -1)
 158         return NULL;
 159     if (c == '(' ||
 160         c == ')' ||
 161         c == '+' ||
 162         c == '/' ||
 163         c == '*' ||
 164         c == '^' ||
 165         c == '=' ||
 166         c == ',' ||
 167         c == '_' ||
 168         c == '[' ||
 169         c == ']' ||
 170         c == '{' ||
 171         c == '}') {
 172         tok = token_new(line, col);
 173         tok->type = (enum token_type)c;
 174         return tok;
 175     }
 176     if (c == '-' || isdigit(c)) {
 177         tok = token_new(line, col);
 178         tok->type = TOKEN_VALUE;
 179         value_init(tok->u.v);
 180         stream_push_char(s, c);
 181         while ((c = stream_getc(s)) != -1 && isdigit(c))
 182             stream_push_char(s, c);
 183         if (c != -1)
 184             stream_ungetc(s, c);
 185         if (s->len == 1 && s->buffer[0] == '-')
 186             value_set_si(tok->u.v, -1);
 187         else {
 188             stream_push_char(s, '\0');
 189             mpz_set_str(tok->u.v, s->buffer, 0);
 190         }
 191         return tok;
 192     }
 193     if (c == '#' || isalpha(c)) {
 194         tok = token_new(line, col);
 195         stream_push_char(s, c);
 196         while ((c = stream_getc(s)) != -1 && isalnum(c))
 197             stream_push_char(s, c);
 198         if (c != -1)
 199             stream_ungetc(s, c);
 200         stream_push_char(s, '\0');
 201         if (!strcmp(s->buffer, "#variables")) {
 202             tok->type = TOKEN_VARS;
 203         } else if (s->buffer[0] == '#') {
 204             tok->type = TOKEN_UNKNOWN;
 205         } else if (!strcmp(s->buffer, "UNION")) {
 206             tok->type = TOKEN_UNION;
 207         } else {
 208             tok->type = TOKEN_IDENT;
 209             tok->u.s = strdup(s->buffer);
 210         }
 211         return tok;
 212     }
 213     if (c == '>') {
 214         if ((c = stream_getc(s)) == '=') {
 215             tok = token_new(line, col);
 216             tok->type = TOKEN_GE;
 217             return tok;
 218         }
 219         if (c != -1)
 220             stream_ungetc(s, c);
 221     }
 222     if (c == '!') {
 223         if ((c = stream_getc(s)) == '=') {
 224             tok = token_new(line, col);
 225             tok->type = TOKEN_NE;
 226             return tok;
 227         }
 228         if (c != -1)
 229             stream_ungetc(s, c);
 230     }
 231
 232     tok = token_new(line, col);
 233     tok->type = TOKEN_UNKNOWN;
 234     return tok;
 235 }
 236
 237 void stream_error(struct stream *s, struct token *tok, char *msg)
 238 {
 239     int line = tok ? tok->line : s->line;
 240     int col = tok ? tok->col : s->col;
 241     fprintf(stderr, "syntax error (%d, %d): %s\n", line, col, msg);
 242     if (tok) {
 243         if (tok->type < 256)
 244             fprintf(stderr, "got '%c'\n", tok->type);
 245         else
 246             fprintf(stderr, "got token type %d\n", tok->type);
 247     }
 248 }
 249
 250 static void stream_free(struct stream *s)
 251 {
 252     free(s->buffer);
 253     if (s->n_token != 0) {
 254         struct token *tok = stream_next_token(s);
 255         stream_error(s, tok, "unexpected token");
 256     }
 257     free(s);
 258 }
 259
 260 struct parameter {
 261     char                *name;
 262     int                  pos;
 263     struct parameter    *next;
 264 };
 265
 266 struct parameter *parameter_new(const char *name, int len,
 267                                 int pos, struct parameter *next)
 268 {
 269     struct parameter *p = ALLOC(struct parameter);
 270     p->name = strdup(name);
 271     p->name[len] = '\0';
 272     p->pos = pos;
 273     p->next = next;
 274     return p;
 275 }
 276
 277 static int parameter_pos(struct parameter **p, const char *s, int len)
 278 {
 279     int pos = *p ? (*p)->pos+1 : 0;
 280     struct parameter *q;
 281
 282     if (len == -1)
 283         len = strlen(s);
 284     for (q = *p; q; q = q->next) {
 285         if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
 286             break;
 287     }
 288     if (q)
 289         pos = q->pos;
 290     else
 291         *p = parameter_new(s, len, pos, *p);
 292     return pos;
 293 }
 294
 295 static int optional_power(struct stream *s)
 296 {
 297     int pow;
 298     struct token *tok;
 299     tok = stream_next_token(s);
 300     if (!tok)
 301         return 1;
 302     if (tok->type != '^') {
 303         stream_push_token(s, tok);
 304         return 1;
 305     }
 306     token_free(tok);
 307     tok = stream_next_token(s);
 308     if (!tok || tok->type != TOKEN_VALUE) {
 309         stream_error(s, tok, "expecting exponent");
 310         if (tok)
 311             stream_push_token(s, tok);
 312         return 1;
 313     }
 314     pow = VALUE_TO_INT(tok->u.v);
 315     token_free(tok);
 316     return pow;
 317 }
 318
 319 static evalue *evalue_read_factor(struct stream *s, struct parameter **p);
 320 static evalue *evalue_read_term(struct stream *s, struct parameter **p);
 321
 322 static evalue *create_fract_like(struct stream *s, evalue *arg, enode_type type,
 323                                  struct parameter **p)
 324 {
 325     evalue *e;
 326     int pow;
 327     pow = optional_power(s);
 328
 329     e = ALLOC(evalue);
 330     value_init(e->d);
 331     e->x.p = new_enode(type, pow+2, -1);
 332     value_clear(e->x.p->arr[0].d);
 333     e->x.p->arr[0] = *arg;
 334     free(arg);
 335     evalue_set_si(&e->x.p->arr[1+pow], 1, 1);
 336     while (--pow >= 0)
 337         evalue_set_si(&e->x.p->arr[1+pow], 0, 1);
 338
 339     return e;
 340 }
 341
 342 static evalue *create_relation(evalue *arg, int ne)
 343 {
 344     evalue *e;
 345
 346     e = ALLOC(evalue);
 347     value_init(e->d);
 348     e->x.p = new_enode(relation, 2+ne, 0);
 349     value_clear(e->x.p->arr[0].d);
 350     e->x.p->arr[0] = *arg;
 351     free(arg);
 352     if (ne)
 353         evalue_set_si(&e->x.p->arr[1], 0, 1);
 354     evalue_set_si(&e->x.p->arr[1+ne], 1, 1);
 355
 356     return e;
 357 }
 358
 359 static evalue *read_fract(struct stream *s, struct token *tok, struct parameter **p)
 360 {
 361     evalue *arg;
 362
 363     tok = stream_next_token(s);
 364     assert(tok);
 365     assert(tok->type == '{');
 366
 367     token_free(tok);
 368     arg = evalue_read_term(s, p);
 369     tok = stream_next_token(s);
 370     if (!tok || tok->type != '}') {
 371         stream_error(s, tok, "expecting \"}\"");
 372         if (tok)
 373             stream_push_token(s, tok);
 374     } else
 375         token_free(tok);
 376
 377     return create_fract_like(s, arg, fractional, p);
 378 }
 379
 380 static evalue *read_periodic(struct stream *s, struct parameter **p)
 381 {
 382     evalue **list;
 383     int len;
 384     int n;
 385     evalue *e = NULL;
 386
 387     struct token *tok;
 388     tok = stream_next_token(s);
 389     assert(tok && tok->type == '[');
 390     token_free(tok);
 391
 392     len = 100;
 393     list = (evalue **)malloc(len * sizeof(evalue *));
 394     n = 0;
 395
 396     for (;;) {
 397         evalue *e = evalue_read_term(s, p);
 398         if (!e) {
 399             stream_error(s, NULL, "missing argument or list element");
 400             goto out;
 401         }
 402         if (n >= len) {
 403             len = (3*len)/2;
 404             list = (evalue **)realloc(list, len * sizeof(evalue *));
 405         }
 406         list[n++] = e;
 407
 408         tok = stream_next_token(s);
 409         if (!tok) {
 410             stream_error(s, NULL, "unexpected EOF");
 411             goto out;
 412         }
 413         if (tok->type != ',')
 414             break;
 415         token_free(tok);
 416     }
 417
 418     if (n == 1 && (tok->type == '=' || tok->type == TOKEN_NE)) {
 419         int ne = tok->type == TOKEN_NE;
 420         token_free(tok);
 421         tok = stream_next_token(s);
 422         if (!tok || tok->type != TOKEN_VALUE) {
 423             stream_error(s, tok, "expecting \"0\"");
 424             if (tok)
 425                 stream_push_token(s, tok);
 426             goto out;
 427         }
 428         token_free(tok);
 429         tok = stream_next_token(s);
 430         if (!tok || tok->type != ']') {
 431             stream_error(s, tok, "expecting \"]\"");
 432             if (tok)
 433                 stream_push_token(s, tok);
 434             goto out;
 435         }
 436         token_free(tok);
 437         e = create_relation(list[0], ne);
 438         n = 0;
 439         goto out;
 440     }
 441
 442     if (tok->type != ']') {
 443         stream_error(s, tok, "expecting \"]\"");
 444         stream_push_token(s, tok);
 445         goto out;
 446     }
 447
 448     token_free(tok);
 449
 450     tok = stream_next_token(s);
 451     if (tok && tok->type == '_') {
 452         int pos;
 453         token_free(tok);
 454         tok = stream_next_token(s);
 455         if (!tok || tok->type != TOKEN_IDENT) {
 456             stream_error(s, tok, "expecting identifier");
 457             if (tok)
 458                 stream_push_token(s, tok);
 459             goto out;
 460         }
 461         e = ALLOC(evalue);
 462         value_init(e->d);
 463         pos = parameter_pos(p, tok->u.s, -1);
 464         token_free(tok);
 465         e->x.p = new_enode(periodic, n, pos+1);
 466         while (--n >= 0) {
 467             value_clear(e->x.p->arr[n].d);
 468             e->x.p->arr[n] = *list[n];
 469             free(list[n]);
 470         }
 471     } else if (n == 1) {
 472         if (tok)
 473             stream_push_token(s, tok);
 474         e = create_fract_like(s, list[0], flooring, p);
 475         n = 0;
 476     } else {
 477         stream_error(s, tok, "unexpected token");
 478         if (tok)
 479             stream_push_token(s, tok);
 480     }
 481
 482 out:
 483     while (--n >= 0)
 484         evalue_free(list[n]);
 485     free(list);
 486     return e;
 487 }
 488
 489 /* frees product on error */
 490 static evalue *read_factor_and_multiply(struct stream *s, struct parameter **p,
 491                                         evalue *product)
 492 {
 493     evalue *e2;
 494     e2 = evalue_read_factor(s, p);
 495     if (!e2) {
 496         stream_error(s, NULL, "unexpected EOF");
 497         evalue_free(product);
 498         return NULL;
 499     }
 500     emul(e2, product);
 501     evalue_free(e2);
 502     return product;
 503 }
 504
 505 static evalue *evalue_read_factor(struct stream *s, struct parameter **p)
 506 {
 507     struct token *tok;
 508     evalue *e = NULL;
 509
 510     tok = stream_next_token(s);
 511     if (!tok)
 512         return NULL;
 513
 514     if (tok->type == '(') {
 515         token_free(tok);
 516         e = evalue_read_term(s, p);
 517         tok = stream_next_token(s);
 518         if (!tok || tok->type != ')') {
 519             stream_error(s, tok, "expecting \")\"");
 520             if (tok)
 521                 stream_push_token(s, tok);
 522         } else
 523             token_free(tok);
 524     } else if (tok->type == TOKEN_VALUE) {
 525         e = ALLOC(evalue);
 526         value_init(e->d);
 527         value_set_si(e->d, 1);
 528         value_init(e->x.n);
 529         value_assign(e->x.n, tok->u.v);
 530         token_free(tok);
 531         tok = stream_next_token(s);
 532         if (tok && tok->type == '/') {
 533             token_free(tok);
 534             tok = stream_next_token(s);
 535             if (!tok || tok->type != TOKEN_VALUE) {
 536                 stream_error(s, tok, "expecting denominator");
 537                 if (tok)
 538                     stream_push_token(s, tok);
 539                 return NULL;
 540             }
 541             value_assign(e->d, tok->u.v);
 542             token_free(tok);
 543         } else if (tok && tok->type == TOKEN_IDENT) {
 544             stream_push_token(s, tok);
 545             e = read_factor_and_multiply(s, p, e);
 546         } else if (tok)
 547             stream_push_token(s, tok);
 548     } else if (tok->type == TOKEN_IDENT) {
 549         int pos = parameter_pos(p, tok->u.s, -1);
 550         int pow = optional_power(s);
 551         token_free(tok);
 552         e = ALLOC(evalue);
 553         value_init(e->d);
 554         e->x.p = new_enode(polynomial, pow+1, pos+1);
 555         evalue_set_si(&e->x.p->arr[pow], 1, 1);
 556         while (--pow >= 0)
 557             evalue_set_si(&e->x.p->arr[pow], 0, 1);
 558     } else if (tok->type == '[') {
 559         stream_push_token(s, tok);
 560         e = read_periodic(s, p);
 561     } else if (tok->type == '{') {
 562         stream_push_token(s, tok);
 563         e = read_fract(s, tok, p);
 564     }
 565
 566     tok = stream_next_token(s);
 567     if (tok && tok->type == '*') {
 568         token_free(tok);
 569         e = read_factor_and_multiply(s, p, e);
 570     } else if (tok)
 571         stream_push_token(s, tok);
 572
 573     return e;
 574 }
 575
 576 static evalue *evalue_read_term(struct stream *s, struct parameter **p)
 577 {
 578     struct token *tok;
 579     evalue *e = NULL;
 580
 581     e = evalue_read_factor(s, p);
 582     if (!e)
 583         return NULL;
 584
 585     tok = stream_next_token(s);
 586     if (!tok)
 587         return e;
 588
 589     if (tok->type == '+' || tok->type == TOKEN_VALUE) {
 590         evalue *e2;
 591         if (tok->type == '+')
 592             token_free(tok);
 593         else
 594             stream_push_token(s, tok);
 595         e2 = evalue_read_term(s, p);
 596         if (!e2) {
 597             stream_error(s, NULL, "unexpected EOF");
 598             return NULL;
 599         }
 600         eadd(e2, e);
 601         evalue_free(e2);
 602     } else
 603         stream_push_token(s, tok);
 604
 605     return e;
 606 }
 607
 608 struct constraint {
 609     int                  type;
 610     Vector              *v;
 611     struct constraint   *next;
 612     struct constraint   *union_next;
 613 };
 614
 615 static struct constraint *constraint_new()
 616 {
 617     struct constraint *c = ALLOC(struct constraint);
 618     c->type = -1;
 619     c->v = Vector_Alloc(16);
 620     c->next = NULL;
 621     c->union_next = NULL;
 622     return c;
 623 }
 624
 625 static void constraint_free(struct constraint *c)
 626 {
 627     while (c) {
 628         struct constraint *next = c->next ? c->next : c->union_next;
 629         Vector_Free(c->v);
 630         free(c);
 631         c = next;
 632     }
 633 }
 634
 635 static void constraint_extend(struct constraint *c, int pos)
 636 {
 637     Vector *v;
 638     if (pos < c->v->Size)
 639         return;
 640
 641     v = Vector_Alloc((3*c->v->Size)/2);
 642     Vector_Copy(c->v->p, v->p, c->v->Size);
 643     Vector_Free(c->v);
 644     c->v = v;
 645 }
 646
 647 static int evalue_read_constraint(struct stream *s, struct parameter **p,
 648                                   struct constraint **constraints,
 649                                   struct constraint *union_next)
 650 {
 651     struct token *tok;
 652     struct constraint *c = NULL;
 653
 654     while ((tok = stream_next_token(s))) {
 655         struct token *tok2;
 656         int pos;
 657         if (tok->type == '+')
 658             token_free(tok);
 659         else if (tok->type == TOKEN_IDENT) {
 660             if (!c)
 661                 c = constraint_new();
 662             pos = parameter_pos(p, tok->u.s, -1);
 663             constraint_extend(c, 1+pos);
 664             value_set_si(c->v->p[1+pos], 1);
 665             token_free(tok);
 666         } else if (tok->type == TOKEN_VALUE) {
 667             if (!c)
 668                 c = constraint_new();
 669             tok2 = stream_next_token(s);
 670             if (tok2 && tok2->type == TOKEN_IDENT) {
 671                 pos = parameter_pos(p, tok2->u.s, -1);
 672                 constraint_extend(c, 1+pos);
 673                 value_assign(c->v->p[1+pos], tok->u.v);
 674                 token_free(tok);
 675                 token_free(tok2);
 676             } else {
 677                 if (tok2)
 678                     stream_push_token(s, tok2);
 679                 value_assign(c->v->p[0], tok->u.v);
 680                 token_free(tok);
 681             }
 682         } else if (tok->type == TOKEN_GE || tok->type == '=') {
 683             int type = tok->type == TOKEN_GE;
 684             token_free(tok);
 685             tok = stream_next_token(s);
 686             if (!tok || tok->type != TOKEN_VALUE || value_notzero_p(tok->u.v)) {
 687                 stream_error(s, tok, "expecting \"0\"");
 688                 if (tok)
 689                     stream_push_token(s, tok);
 690                 *constraints = NULL;
 691             } else {
 692                 c->type = type;
 693                 c->next = *constraints;
 694                 c->union_next = union_next;
 695                 *constraints = c;
 696                 token_free(tok);
 697             }
 698             break;
 699         } else {
 700             if (!c)
 701                 stream_push_token(s, tok);
 702             else {
 703                 stream_error(s, tok, "unexpected token");
 704                 *constraints = NULL;
 705             }
 706             return 0;
 707         }
 708     }
 709     return tok != NULL;
 710 }
 711
 712 static struct constraint *evalue_read_domain(struct stream *s, struct parameter **p,
 713                                              unsigned MaxRays)
 714 {
 715     struct constraint *constraints = NULL;
 716     struct constraint *union_next = NULL;
 717     struct token *tok;
 718     int line;
 719
 720     tok = stream_next_token(s);
 721     if (!tok)
 722         return NULL;
 723     stream_push_token(s, tok);
 724
 725     line = tok->line;
 726     while (evalue_read_constraint(s, p, &constraints, union_next)) {
 727         tok = stream_next_token(s);
 728         if (tok) {
 729             if (tok->type == TOKEN_UNION) {
 730                 token_free(tok);
 731                 tok = stream_next_token(s);
 732                 if (!tok) {
 733                     stream_error(s, NULL, "unexpected EOF");
 734                     return constraints;
 735                 }
 736                 stream_push_token(s, tok);
 737                 union_next = constraints;
 738                 constraints = NULL;
 739             } else {
 740                 union_next = NULL;
 741                 stream_push_token(s, tok);
 742                 /* empty line separates domain from evalue */
 743                 if (tok->line > line+1)
 744                     break;
 745             }
 746             line = tok->line;
 747         }
 748     }
 749     return constraints;
 750 }
 751
 752 struct section {
 753     struct constraint   *constraints;
 754     evalue              *e;
 755     struct section      *next;
 756 };
 757
 758 static char **extract_parameters(struct parameter *p, unsigned *nparam)
 759 {
 760     int i;
 761     char **params;
 762
 763     *nparam = p ? p->pos+1 : 0;
 764     params = ALLOCN(char *, *nparam);
 765     for (i = 0; i < *nparam; ++i) {
 766         struct parameter *next = p->next;
 767         params[p->pos] = p->name;
 768         free(p);
 769         p = next;
 770     }
 771     return params;
 772 }
 773
 774 static Polyhedron *constraints2domain(struct constraint *constraints,
 775                                       unsigned nparam, unsigned MaxRays)
 776 {
 777     Polyhedron *D;
 778     Matrix *M;
 779     int n;
 780     struct constraint *c;
 781     struct constraint *union_next = NULL;
 782
 783     for (n = 0, c = constraints; c; ++n, c = c->next)
 784         ;
 785     M = Matrix_Alloc(n, 1+nparam+1);
 786     while (--n >= 0) {
 787         struct constraint *next = constraints->next;
 788         union_next = constraints->union_next;
 789         Vector_Copy(constraints->v->p+1, M->p[n]+1, nparam);
 790         if (constraints->type)
 791             value_set_si(M->p[n][0], 1);
 792         value_assign(M->p[n][1+nparam], constraints->v->p[0]);
 793         constraints->next = NULL;
 794         constraints->union_next = NULL;
 795         constraint_free(constraints);
 796         constraints = next;
 797     }
 798     D = Constraints2Polyhedron(M, MaxRays);
 799     Matrix_Free(M);
 800
 801     if (union_next)
 802         D = DomainConcat(D, constraints2domain(union_next, nparam, MaxRays));
 803     return D;
 804 }
 805
 806 static evalue *evalue_read_partition(struct stream *s, struct parameter *p,
 807                                      char ***ppp,
 808                                      unsigned *nparam, unsigned MaxRays)
 809 {
 810     struct section *part = NULL;
 811     struct constraint *constraints;
 812     evalue *e = NULL;
 813     int m = 0;
 814
 815     while ((constraints = evalue_read_domain(s, &p, MaxRays))) {
 816         struct section *sect;
 817         evalue *e = evalue_read_term(s, &p);
 818         if (!e) {
 819             stream_error(s, NULL, "missing evalue");
 820             break;
 821         }
 822         sect = ALLOC(struct section);
 823         sect->constraints = constraints;
 824         sect->e = e;
 825         sect->next = part;
 826         part = sect;
 827         ++m;
 828     }
 829
 830     if (part) {
 831         Polyhedron *D;
 832         int j;
 833
 834         *ppp = extract_parameters(p, nparam);
 835         e = ALLOC(evalue);
 836         value_init(e->d);
 837         e->x.p = new_enode(partition, 2*m, *nparam);
 838
 839         for (j = 0; j < m; ++j) {
 840             int n;
 841             struct section *next = part->next;
 842             constraints = part->constraints;
 843             D = constraints2domain(part->constraints, *nparam, MaxRays);
 844             EVALUE_SET_DOMAIN(e->x.p->arr[2*(m-j-1)], D);
 845             value_clear(e->x.p->arr[2*(m-j-1)+1].d);
 846             e->x.p->arr[2*(m-j-1)+1] = *part->e;
 847             free(part->e);
 848             free(part);
 849             part = next;
 850         }
 851     }
 852     return e;
 853 }
 854
 855 static evalue *evalue_read(struct stream *s, const char *var_list, char ***ppp,
 856                            unsigned *nvar, unsigned *nparam, unsigned MaxRays)
 857 {
 858     struct token *tok;
 859     evalue *e;
 860     struct parameter *p = NULL;
 861     char *next;
 862     int nv;
 863
 864     if (var_list) {
 865         while ((next = strchr(var_list, ','))) {
 866             if (next > var_list)
 867                 parameter_pos(&p, var_list, next-var_list);
 868             var_list = next+1;
 869         }
 870         if (strlen(var_list) > 0)
 871             parameter_pos(&p, var_list, -1);
 872         nv = p ? p->pos+1 : 0;
 873     } else
 874         nv = -1;
 875
 876     if (!(tok = stream_next_token(s)))
 877         return NULL;
 878
 879     if (tok->type == TOKEN_VARS) {
 880         token_free(tok);
 881         for (;;) {
 882             tok = stream_next_token(s);
 883             if (!tok || tok->type != TOKEN_IDENT) {
 884                 stream_error(s, tok, "expecting identifier");
 885                 break;
 886             }
 887             if (nv == -1)
 888                 parameter_pos(&p, tok->u.s, -1);
 889             token_free(tok);
 890             tok = stream_next_token(s);
 891             if (!tok || tok->type != ',')
 892                 break;
 893             token_free(tok);
 894         }
 895         if (!tok)
 896             return NULL;
 897         if (nv = -1)
 898             nv = p ? p->pos+1 : 0;
 899     }
 900
 901     if (tok->type == '(' || tok->type == '[') {
 902         stream_push_token(s, tok);
 903         e = evalue_read_term(s, &p);
 904         *ppp = extract_parameters(p, nparam);
 905     } else if (tok->type == TOKEN_VALUE) {
 906         struct token *tok2 = stream_next_token(s);
 907         if (tok2)
 908             stream_push_token(s, tok2);
 909         stream_push_token(s, tok);
 910         if (tok2 && (tok2->type == TOKEN_IDENT || tok2->type == TOKEN_GE))
 911             e = evalue_read_partition(s, p, ppp, nparam, MaxRays);
 912         else {
 913             e = evalue_read_term(s, &p);
 914             *ppp = extract_parameters(p, nparam);
 915         }
 916     } else if (tok->type == TOKEN_IDENT) {
 917         stream_push_token(s, tok);
 918         e = evalue_read_partition(s, p, ppp, nparam, MaxRays);
 919     } else {
 920         stream_error(s, tok, "unexpected token");
 921         *nparam = nv == -1 ? 0 : nv;
 922         e = NULL;
 923     }
 924     if (nv == -1)
 925         *nvar = *nparam;
 926     else
 927         *nvar = nv;
 928     *nparam -= *nvar;
 929     return e;
 930 }
 931
 932 evalue *evalue_read_from_file(FILE *in, const char *var_list, char ***ppp,
 933                               unsigned *nvar, unsigned *nparam, unsigned MaxRays)
 934 {
 935     evalue *e;
 936     struct stream *s = stream_new_file(in);
 937     e = evalue_read(s, var_list, ppp, nvar, nparam, MaxRays);
 938     stream_free(s);
 939     return e;
 940 }
 941
 942 evalue *evalue_read_from_str(const char *str, const char *var_list, char ***ppp,
 943                              unsigned *nvar, unsigned *nparam, unsigned MaxRays)
 944 {
 945     evalue *e;
 946     struct stream *s = stream_new_str(str);
 947     e = evalue_read(s, var_list, ppp, nvar, nparam, MaxRays);
 948     stream_free(s);
 949     return e;
 950 }