evalue_read.c

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