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         int c;
 218         if ((c = stream_getc(s)) == '=') {
 219             tok = token_new(line, col, old_line != line);
 220             tok->type = TOKEN_GE;
 221             return tok;
 222         }
 223         if (c != -1)
 224             stream_ungetc(s, c);
 225     }
 226     if (c == '!') {
 227         int c;
 228         if ((c = stream_getc(s)) == '=') {
 229             tok = token_new(line, col, old_line != line);
 230             tok->type = TOKEN_NE;
 231             return tok;
 232         }
 233         if (c != -1)
 234             stream_ungetc(s, c);
 235     }
 236
 237     tok = token_new(line, col, old_line != line);
 238     tok->type = TOKEN_UNKNOWN;
 239     return tok;
 240 }
 241
 242 void stream_error(struct stream *s, struct token *tok, char *msg)
 243 {
 244     int line = tok ? tok->line : s->line;
 245     int col = tok ? tok->col : s->col;
 246     fprintf(stderr, "syntax error (%d, %d): %s\n", line, col, msg);
 247     if (tok) {
 248         if (tok->type < 256)
 249             fprintf(stderr, "got '%c'\n", tok->type);
 250         else
 251             fprintf(stderr, "got token type %d\n", tok->type);
 252     }
 253 }
 254
 255 static void stream_free(struct stream *s)
 256 {
 257     free(s->buffer);
 258     if (s->n_token != 0) {
 259         struct token *tok = stream_next_token(s);
 260         stream_error(s, tok, "unexpected token");
 261     }
 262     free(s);
 263 }
 264
 265 struct parameter {
 266     char                *name;
 267     int                  pos;
 268     struct parameter    *next;
 269 };
 270
 271 struct parameter *parameter_new(const char *name, int len,
 272                                 int pos, struct parameter *next)
 273 {
 274     struct parameter *p = ALLOC(struct parameter);
 275     p->name = strdup(name);
 276     p->name[len] = '\0';
 277     p->pos = pos;
 278     p->next = next;
 279     return p;
 280 }
 281
 282 static int parameter_pos(struct parameter **p, const char *s, int len)
 283 {
 284     int pos = *p ? (*p)->pos+1 : 0;
 285     struct parameter *q;
 286
 287     if (len == -1)
 288         len = strlen(s);
 289     for (q = *p; q; q = q->next) {
 290         if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
 291             break;
 292     }
 293     if (q)
 294         pos = q->pos;
 295     else
 296         *p = parameter_new(s, len, pos, *p);
 297     return pos;
 298 }
 299
 300 static int optional_power(struct stream *s)
 301 {
 302     int pow;
 303     struct token *tok;
 304     tok = stream_next_token(s);
 305     if (!tok)
 306         return 1;
 307     if (tok->type != '^') {
 308         stream_push_token(s, tok);
 309         return 1;
 310     }
 311     token_free(tok);
 312     tok = stream_next_token(s);
 313     if (!tok || tok->type != TOKEN_VALUE) {
 314         stream_error(s, tok, "expecting exponent");
 315         if (tok)
 316             stream_push_token(s, tok);
 317         return 1;
 318     }
 319     pow = VALUE_TO_INT(tok->u.v);
 320     token_free(tok);
 321     return pow;
 322 }
 323
 324 static evalue *evalue_read_factor(struct stream *s, struct parameter **p);
 325 static evalue *evalue_read_term(struct stream *s, struct parameter **p,
 326                                 int multi_line);
 327
 328 static evalue *create_fract_like(struct stream *s, evalue *arg, enode_type type,
 329                                  struct parameter **p)
 330 {
 331     evalue *e;
 332     int pow;
 333     pow = optional_power(s);
 334
 335     e = ALLOC(evalue);
 336     value_init(e->d);
 337     e->x.p = new_enode(type, pow+2, -1);
 338     value_clear(e->x.p->arr[0].d);
 339     e->x.p->arr[0] = *arg;
 340     free(arg);
 341     evalue_set_si(&e->x.p->arr[1+pow], 1, 1);
 342     while (--pow >= 0)
 343         evalue_set_si(&e->x.p->arr[1+pow], 0, 1);
 344
 345     return e;
 346 }
 347
 348 static evalue *create_relation(evalue *arg, int ne)
 349 {
 350     evalue *e;
 351
 352     e = ALLOC(evalue);
 353     value_init(e->d);
 354     e->x.p = new_enode(relation, 2+ne, 0);
 355     value_clear(e->x.p->arr[0].d);
 356     e->x.p->arr[0] = *arg;
 357     free(arg);
 358     if (ne)
 359         evalue_set_si(&e->x.p->arr[1], 0, 1);
 360     evalue_set_si(&e->x.p->arr[1+ne], 1, 1);
 361
 362     return e;
 363 }
 364
 365 static evalue *read_fract(struct stream *s, struct token *tok, struct parameter **p)
 366 {
 367     evalue *arg;
 368
 369     tok = stream_next_token(s);
 370     assert(tok);
 371     assert(tok->type == '{');
 372
 373     token_free(tok);
 374     arg = evalue_read_term(s, p, 1);
 375     tok = stream_next_token(s);
 376     if (!tok || tok->type != '}') {
 377         stream_error(s, tok, "expecting \"}\"");
 378         if (tok)
 379             stream_push_token(s, tok);
 380     } else
 381         token_free(tok);
 382
 383     return create_fract_like(s, arg, fractional, p);
 384 }
 385
 386 static evalue *read_periodic(struct stream *s, struct parameter **p)
 387 {
 388     evalue **list;
 389     int len;
 390     int n;
 391     evalue *e = NULL;
 392
 393     struct token *tok;
 394     tok = stream_next_token(s);
 395     assert(tok && tok->type == '[');
 396     token_free(tok);
 397
 398     len = 100;
 399     list = (evalue **)malloc(len * sizeof(evalue *));
 400     n = 0;
 401
 402     for (;;) {
 403         evalue *e = evalue_read_term(s, p, 1);
 404         if (!e) {
 405             stream_error(s, NULL, "missing argument or list element");
 406             goto out;
 407         }
 408         if (n >= len) {
 409             len = (3*len)/2;
 410             list = (evalue **)realloc(list, len * sizeof(evalue *));
 411         }
 412         list[n++] = e;
 413
 414         tok = stream_next_token(s);
 415         if (!tok) {
 416             stream_error(s, NULL, "unexpected EOF");
 417             goto out;
 418         }
 419         if (tok->type != ',')
 420             break;
 421         token_free(tok);
 422     }
 423
 424     if (n == 1 && (tok->type == '=' || tok->type == TOKEN_NE)) {
 425         int ne = tok->type == TOKEN_NE;
 426         token_free(tok);
 427         tok = stream_next_token(s);
 428         if (!tok || tok->type != TOKEN_VALUE) {
 429             stream_error(s, tok, "expecting \"0\"");
 430             if (tok)
 431                 stream_push_token(s, tok);
 432             goto out;
 433         }
 434         token_free(tok);
 435         tok = stream_next_token(s);
 436         if (!tok || tok->type != ']') {
 437             stream_error(s, tok, "expecting \"]\"");
 438             if (tok)
 439                 stream_push_token(s, tok);
 440             goto out;
 441         }
 442         token_free(tok);
 443         e = create_relation(list[0], ne);
 444         n = 0;
 445         goto out;
 446     }
 447
 448     if (tok->type != ']') {
 449         stream_error(s, tok, "expecting \"]\"");
 450         stream_push_token(s, tok);
 451         goto out;
 452     }
 453
 454     token_free(tok);
 455
 456     tok = stream_next_token(s);
 457     if (tok && tok->type == '_') {
 458         int pos;
 459         token_free(tok);
 460         tok = stream_next_token(s);
 461         if (!tok || tok->type != TOKEN_IDENT) {
 462             stream_error(s, tok, "expecting identifier");
 463             if (tok)
 464                 stream_push_token(s, tok);
 465             goto out;
 466         }
 467         e = ALLOC(evalue);
 468         value_init(e->d);
 469         pos = parameter_pos(p, tok->u.s, -1);
 470         token_free(tok);
 471         e->x.p = new_enode(periodic, n, pos+1);
 472         while (--n >= 0) {
 473             value_clear(e->x.p->arr[n].d);
 474             e->x.p->arr[n] = *list[n];
 475             free(list[n]);
 476         }
 477     } else if (n == 1) {
 478         if (tok)
 479             stream_push_token(s, tok);
 480         e = create_fract_like(s, list[0], flooring, p);
 481         n = 0;
 482     } else {
 483         stream_error(s, tok, "unexpected token");
 484         if (tok)
 485             stream_push_token(s, tok);
 486     }
 487
 488 out:
 489     while (--n >= 0)
 490         evalue_free(list[n]);
 491     free(list);
 492     return e;
 493 }
 494
 495 /* frees product on error */
 496 static evalue *read_factor_and_multiply(struct stream *s, struct parameter **p,
 497                                         evalue *product)
 498 {
 499     evalue *e2;
 500     e2 = evalue_read_factor(s, p);
 501     if (!e2) {
 502         stream_error(s, NULL, "unexpected EOF");
 503         evalue_free(product);
 504         return NULL;
 505     }
 506     emul(e2, product);
 507     evalue_free(e2);
 508     return product;
 509 }
 510
 511 static evalue *evalue_read_factor(struct stream *s, struct parameter **p)
 512 {
 513     struct token *tok;
 514     evalue *e = NULL;
 515
 516     tok = stream_next_token(s);
 517     if (!tok)
 518         return NULL;
 519
 520     if (tok->type == '(') {
 521         token_free(tok);
 522         e = evalue_read_term(s, p, 1);
 523         tok = stream_next_token(s);
 524         if (!tok || tok->type != ')') {
 525             stream_error(s, tok, "expecting \")\"");
 526             if (tok)
 527                 stream_push_token(s, tok);
 528         } else
 529             token_free(tok);
 530     } else if (tok->type == TOKEN_VALUE) {
 531         int line = tok->line;
 532         e = ALLOC(evalue);
 533         value_init(e->d);
 534         value_set_si(e->d, 1);
 535         value_init(e->x.n);
 536         value_assign(e->x.n, tok->u.v);
 537         token_free(tok);
 538         tok = stream_next_token(s);
 539         if (tok && tok->type == '/') {
 540             token_free(tok);
 541             tok = stream_next_token(s);
 542             if (!tok || tok->type != TOKEN_VALUE) {
 543                 stream_error(s, tok, "expecting denominator");
 544                 if (tok)
 545                     stream_push_token(s, tok);
 546                 return NULL;
 547             }
 548             value_assign(e->d, tok->u.v);
 549             token_free(tok);
 550         } else if (tok && tok->type == TOKEN_IDENT && tok->line == line) {
 551             stream_push_token(s, tok);
 552             e = read_factor_and_multiply(s, p, e);
 553         } else if (tok)
 554             stream_push_token(s, tok);
 555     } else if (tok->type == TOKEN_IDENT) {
 556         int pos = parameter_pos(p, tok->u.s, -1);
 557         int pow = optional_power(s);
 558         token_free(tok);
 559         e = ALLOC(evalue);
 560         value_init(e->d);
 561         e->x.p = new_enode(polynomial, pow+1, pos+1);
 562         evalue_set_si(&e->x.p->arr[pow], 1, 1);
 563         while (--pow >= 0)
 564             evalue_set_si(&e->x.p->arr[pow], 0, 1);
 565     } else if (tok->type == '[') {
 566         stream_push_token(s, tok);
 567         e = read_periodic(s, p);
 568     } else if (tok->type == '{') {
 569         stream_push_token(s, tok);
 570         e = read_fract(s, tok, p);
 571     }
 572
 573     tok = stream_next_token(s);
 574     if (tok && tok->type == '*') {
 575         token_free(tok);
 576         e = read_factor_and_multiply(s, p, e);
 577     } else if (tok)
 578         stream_push_token(s, tok);
 579
 580     return e;
 581 }
 582
 583 static evalue *evalue_read_term(struct stream *s, struct parameter **p,
 584                                 int multi_line)
 585 {
 586     struct token *tok;
 587     evalue *e = NULL;
 588
 589     e = evalue_read_factor(s, p);
 590     if (!e)
 591         return NULL;
 592
 593     tok = stream_next_token(s);
 594     if (!tok)
 595         return e;
 596
 597     if (!multi_line && tok->on_new_line)
 598         stream_push_token(s, tok);
 599     else if (tok->type == '+' || tok->type == TOKEN_VALUE) {
 600         evalue *e2;
 601         if (tok->type == '+')
 602             token_free(tok);
 603         else
 604             stream_push_token(s, tok);
 605         e2 = evalue_read_term(s, p, multi_line);
 606         if (!e2) {
 607             stream_error(s, NULL, "unexpected EOF");
 608             return NULL;
 609         }
 610         eadd(e2, e);
 611         evalue_free(e2);
 612     } else
 613         stream_push_token(s, tok);
 614
 615     return e;
 616 }
 617
 618 struct constraint {
 619     int                  type;
 620     Vector              *v;
 621     struct constraint   *next;
 622     struct constraint   *union_next;
 623 };
 624
 625 static struct constraint *constraint_new()
 626 {
 627     struct constraint *c = ALLOC(struct constraint);
 628     c->type = -1;
 629     c->v = Vector_Alloc(16);
 630     c->next = NULL;
 631     c->union_next = NULL;
 632     return c;
 633 }
 634
 635 static void constraint_free(struct constraint *c)
 636 {
 637     while (c) {
 638         struct constraint *next = c->next ? c->next : c->union_next;
 639         Vector_Free(c->v);
 640         free(c);
 641         c = next;
 642     }
 643 }
 644
 645 static void constraint_extend(struct constraint *c, int pos)
 646 {
 647     Vector *v;
 648     if (pos < c->v->Size)
 649         return;
 650
 651     v = Vector_Alloc((3*c->v->Size)/2);
 652     Vector_Copy(c->v->p, v->p, c->v->Size);
 653     Vector_Free(c->v);
 654     c->v = v;
 655 }
 656
 657 static int evalue_read_constraint(struct stream *s, struct parameter **p,
 658                                   struct constraint **constraints,
 659                                   struct constraint *union_next)
 660 {
 661     struct token *tok;
 662     struct constraint *c = NULL;
 663
 664     while ((tok = stream_next_token(s))) {
 665         struct token *tok2;
 666         int pos;
 667         if (tok->type == '+')
 668             token_free(tok);
 669         else if (tok->type == TOKEN_IDENT) {
 670             if (!c)
 671                 c = constraint_new();
 672             pos = parameter_pos(p, tok->u.s, -1);
 673             constraint_extend(c, 1+pos);
 674             value_set_si(c->v->p[1+pos], 1);
 675             token_free(tok);
 676         } else if (tok->type == TOKEN_VALUE) {
 677             if (!c)
 678                 c = constraint_new();
 679             tok2 = stream_next_token(s);
 680             if (tok2 && tok2->type == TOKEN_VALUE) {
 681                 /* Handle "-" space cst, where "-" is translated to -1 */
 682                 value_multiply(tok->u.v, tok->u.v, tok2->u.v);
 683                 token_free(tok2);
 684                 tok2 = stream_next_token(s);
 685             }
 686             if (tok2 && tok2->type == TOKEN_IDENT) {
 687                 pos = parameter_pos(p, tok2->u.s, -1);
 688                 constraint_extend(c, 1+pos);
 689                 value_assign(c->v->p[1+pos], tok->u.v);
 690                 token_free(tok);
 691                 token_free(tok2);
 692             } else {
 693                 if (tok2)
 694                     stream_push_token(s, tok2);
 695                 value_assign(c->v->p[0], tok->u.v);
 696                 token_free(tok);
 697             }
 698         } else if (tok->type == TOKEN_GE || tok->type == '=') {
 699             int type = tok->type == TOKEN_GE;
 700             token_free(tok);
 701             tok = stream_next_token(s);
 702             if (!tok || tok->type != TOKEN_VALUE || value_notzero_p(tok->u.v)) {
 703                 stream_error(s, tok, "expecting \"0\"");
 704                 if (tok)
 705                     stream_push_token(s, tok);
 706                 *constraints = NULL;
 707             } else {
 708                 if (!c) {
 709                     stream_error(s, NULL, "empty constraint");
 710                     *constraints = NULL;
 711                 } else {
 712                     c->type = type;
 713                     c->next = *constraints;
 714                     c->union_next = union_next;
 715                     *constraints = c;
 716                 }
 717                 token_free(tok);
 718             }
 719             break;
 720         } else {
 721             if (!c)
 722                 stream_push_token(s, tok);
 723             else {
 724                 stream_error(s, tok, "unexpected token");
 725                 *constraints = NULL;
 726             }
 727             return 0;
 728         }
 729     }
 730     return tok != NULL;
 731 }
 732
 733 static struct constraint *evalue_read_domain(struct stream *s, struct parameter **p,
 734                                              unsigned MaxRays)
 735 {
 736     struct constraint *constraints = NULL;
 737     struct constraint *union_next = NULL;
 738     struct token *tok;
 739     int line;
 740
 741     tok = stream_next_token(s);
 742     if (!tok)
 743         return NULL;
 744     stream_push_token(s, tok);
 745
 746     line = tok->line;
 747     while (evalue_read_constraint(s, p, &constraints, union_next)) {
 748         tok = stream_next_token(s);
 749         if (tok) {
 750             if (tok->type == TOKEN_UNION) {
 751                 token_free(tok);
 752                 tok = stream_next_token(s);
 753                 if (!tok) {
 754                     stream_error(s, NULL, "unexpected EOF");
 755                     return constraints;
 756                 }
 757                 stream_push_token(s, tok);
 758                 union_next = constraints;
 759                 constraints = NULL;
 760             } else {
 761                 union_next = NULL;
 762                 stream_push_token(s, tok);
 763                 /* empty line separates domain from evalue */
 764                 if (tok->line > line+1)
 765                     break;
 766             }
 767             line = tok->line;
 768         }
 769     }
 770     return constraints;
 771 }
 772
 773 struct section {
 774     struct constraint   *constraints;
 775     evalue              *e;
 776     struct section      *next;
 777 };
 778
 779 static const char **extract_parameters(struct parameter *p, unsigned *nparam)
 780 {
 781     int i;
 782     const char **params;
 783
 784     *nparam = p ? p->pos+1 : 0;
 785     params = ALLOCN(const char *, *nparam);
 786     for (i = 0; i < *nparam; ++i) {
 787         struct parameter *next = p->next;
 788         params[p->pos] = p->name;
 789         free(p);
 790         p = next;
 791     }
 792     return params;
 793 }
 794
 795 static Polyhedron *constraints2domain(struct constraint *constraints,
 796                                       unsigned nparam, unsigned MaxRays)
 797 {
 798     Polyhedron *D;
 799     Matrix *M;
 800     int n;
 801     struct constraint *c;
 802     struct constraint *union_next = NULL;
 803
 804     for (n = 0, c = constraints; c; ++n, c = c->next)
 805         ;
 806     M = Matrix_Alloc(n, 1+nparam+1);
 807     while (--n >= 0) {
 808         struct constraint *next = constraints->next;
 809         union_next = constraints->union_next;
 810         Vector_Copy(constraints->v->p+1, M->p[n]+1, nparam);
 811         if (constraints->type)
 812             value_set_si(M->p[n][0], 1);
 813         value_assign(M->p[n][1+nparam], constraints->v->p[0]);
 814         constraints->next = NULL;
 815         constraints->union_next = NULL;
 816         constraint_free(constraints);
 817         constraints = next;
 818     }
 819     D = Constraints2Polyhedron(M, MaxRays);
 820     Matrix_Free(M);
 821
 822     if (union_next)
 823         D = DomainConcat(D, constraints2domain(union_next, nparam, MaxRays));
 824     return D;
 825 }
 826
 827 static evalue *evalue_read_partition(struct stream *s, struct parameter *p,
 828                                      const char ***ppp,
 829                                      unsigned *nparam, unsigned MaxRays)
 830 {
 831     struct section *part = NULL;
 832     struct constraint *constraints;
 833     evalue *e = NULL;
 834     int m = 0;
 835
 836     while ((constraints = evalue_read_domain(s, &p, MaxRays))) {
 837         struct section *sect;
 838         evalue *e = evalue_read_term(s, &p, 0);
 839         if (!e) {
 840             stream_error(s, NULL, "missing evalue");
 841             break;
 842         }
 843         sect = ALLOC(struct section);
 844         sect->constraints = constraints;
 845         sect->e = e;
 846         sect->next = part;
 847         part = sect;
 848         ++m;
 849     }
 850
 851     if (part) {
 852         Polyhedron *D;
 853         int j;
 854
 855         *ppp = extract_parameters(p, nparam);
 856         e = ALLOC(evalue);
 857         value_init(e->d);
 858         e->x.p = new_enode(partition, 2*m, *nparam);
 859
 860         for (j = 0; j < m; ++j) {
 861             int n;
 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 }