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