2 #include <barvinok/util.h>
3 #include "evalue_read.h"
5 #define ALLOC(type) (type*)malloc(sizeof(type))
6 #define ALLOCN(type,n) (type*)malloc((n) * sizeof(type))
8 enum token_type
{ TOKEN_UNKNOWN
= 256, TOKEN_VALUE
, TOKEN_IDENT
, TOKEN_GE
,
9 TOKEN_NE
, TOKEN_UNION
, TOKEN_VARS
};
23 static struct token
*token_new(int line
, int col
)
25 struct token
*tok
= ALLOC(struct token
);
31 void token_free(struct token
*tok
)
33 if (tok
->type
== TOKEN_VALUE
)
34 value_clear(tok
->u
.v
);
35 else if (tok
->type
== TOKEN_IDENT
)
52 struct token
*tokens
[5];
56 static struct stream
* stream_new()
59 struct stream
*s
= ALLOC(struct stream
);
63 s
->buffer
= (char*)malloc(s
->size
);
69 for (i
= 0; i
< 5; ++i
)
75 static struct stream
* stream_new_file(FILE *file
)
77 struct stream
*s
= stream_new();
82 static struct stream
* stream_new_str(const char *str
)
84 struct stream
*s
= stream_new();
89 static int stream_getc(struct stream
*s
)
114 static void stream_ungetc(struct stream
*s
, int c
)
123 static void stream_push_char(struct stream
*s
, int c
)
125 if (s
->len
>= s
->size
) {
126 s
->size
= (3*s
->size
)/2;
127 s
->buffer
= (char*)realloc(s
->buffer
, s
->size
);
129 s
->buffer
[s
->len
++] = c
;
132 static struct token
*stream_push_token(struct stream
*s
, struct token
*tok
)
134 assert(s
->n_token
< 5);
135 s
->tokens
[s
->n_token
++] = tok
;
138 static struct token
*stream_next_token(struct stream
*s
)
145 return s
->tokens
[--s
->n_token
];
150 while ((c
= stream_getc(s
)) != -1 && isspace(c
))
172 tok
= token_new(line
, col
);
173 tok
->type
= (enum token_type
)c
;
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
);
185 if (s
->len
== 1 && s
->buffer
[0] == '-')
186 value_set_si(tok
->u
.v
, -1);
188 stream_push_char(s
, '\0');
189 mpz_set_str(tok
->u
.v
, s
->buffer
, 0);
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
);
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
;
208 tok
->type
= TOKEN_IDENT
;
209 tok
->u
.s
= strdup(s
->buffer
);
214 if ((c
= stream_getc(s
)) == '=') {
215 tok
= token_new(line
, col
);
216 tok
->type
= TOKEN_GE
;
223 if ((c
= stream_getc(s
)) == '=') {
224 tok
= token_new(line
, col
);
225 tok
->type
= TOKEN_NE
;
232 tok
= token_new(line
, col
);
233 tok
->type
= TOKEN_UNKNOWN
;
237 void stream_error(struct stream
*s
, struct token
*tok
, char *msg
)
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
);
244 fprintf(stderr
, "got '%c'\n", tok
->type
);
246 fprintf(stderr
, "got token type %d\n", tok
->type
);
250 static void stream_free(struct stream
*s
)
253 if (s
->n_token
!= 0) {
254 struct token
*tok
= stream_next_token(s
);
255 stream_error(s
, tok
, "unexpected token");
263 struct parameter
*next
;
266 struct parameter
*parameter_new(const char *name
, int pos
, struct parameter
*next
)
268 struct parameter
*p
= ALLOC(struct parameter
);
269 p
->name
= strdup(name
);
275 static int parameter_pos(struct parameter
**p
, const char *s
, int len
)
277 int pos
= *p
? (*p
)->pos
+1 : 0;
282 for (q
= *p
; q
; q
= q
->next
) {
283 if (strncmp(q
->name
, s
, len
) == 0)
289 *p
= parameter_new(s
, pos
, *p
);
293 static int optional_power(struct stream
*s
)
297 tok
= stream_next_token(s
);
300 if (tok
->type
!= '^') {
301 stream_push_token(s
, tok
);
305 tok
= stream_next_token(s
);
306 if (!tok
|| tok
->type
!= TOKEN_VALUE
) {
307 stream_error(s
, tok
, "expecting exponent");
309 stream_push_token(s
, tok
);
312 pow
= VALUE_TO_INT(tok
->u
.v
);
317 static evalue
*evalue_read_factor(struct stream
*s
, struct parameter
**p
);
318 static evalue
*evalue_read_term(struct stream
*s
, struct parameter
**p
);
320 static evalue
*create_fract_like(struct stream
*s
, evalue
*arg
, enode_type type
,
321 struct parameter
**p
)
325 pow
= optional_power(s
);
329 e
->x
.p
= new_enode(type
, pow
+2, -1);
330 value_clear(e
->x
.p
->arr
[0].d
);
331 e
->x
.p
->arr
[0] = *arg
;
333 evalue_set_si(&e
->x
.p
->arr
[1+pow
], 1, 1);
335 evalue_set_si(&e
->x
.p
->arr
[1+pow
], 0, 1);
340 static evalue
*create_relation(evalue
*arg
, int ne
)
346 e
->x
.p
= new_enode(relation
, 2+ne
, 0);
347 value_clear(e
->x
.p
->arr
[0].d
);
348 e
->x
.p
->arr
[0] = *arg
;
351 evalue_set_si(&e
->x
.p
->arr
[1], 0, 1);
352 evalue_set_si(&e
->x
.p
->arr
[1+ne
], 1, 1);
357 static evalue
*read_fract(struct stream
*s
, struct token
*tok
, struct parameter
**p
)
361 tok
= stream_next_token(s
);
363 assert(tok
->type
== '{');
366 arg
= evalue_read_term(s
, p
);
367 tok
= stream_next_token(s
);
368 if (!tok
|| tok
->type
!= '}') {
369 stream_error(s
, tok
, "expecting \"}\"");
371 stream_push_token(s
, tok
);
375 return create_fract_like(s
, arg
, fractional
, p
);
378 static evalue
*read_periodic(struct stream
*s
, struct parameter
**p
)
386 tok
= stream_next_token(s
);
387 assert(tok
&& tok
->type
== '[');
391 list
= (evalue
**)malloc(len
* sizeof(evalue
*));
395 evalue
*e
= evalue_read_term(s
, p
);
397 stream_error(s
, NULL
, "missing argument or list element");
402 list
= (evalue
**)realloc(list
, len
* sizeof(evalue
*));
406 tok
= stream_next_token(s
);
408 stream_error(s
, NULL
, "unexpected EOF");
411 if (tok
->type
!= ',')
416 if (n
== 1 && (tok
->type
== '=' || tok
->type
== TOKEN_NE
)) {
417 int ne
= tok
->type
== TOKEN_NE
;
419 tok
= stream_next_token(s
);
420 if (!tok
|| tok
->type
!= TOKEN_VALUE
) {
421 stream_error(s
, tok
, "expecting \"0\"");
423 stream_push_token(s
, tok
);
427 tok
= stream_next_token(s
);
428 if (!tok
|| tok
->type
!= ']') {
429 stream_error(s
, tok
, "expecting \"]\"");
431 stream_push_token(s
, tok
);
435 e
= create_relation(list
[0], ne
);
440 if (tok
->type
!= ']') {
441 stream_error(s
, tok
, "expecting \"]\"");
442 stream_push_token(s
, tok
);
448 tok
= stream_next_token(s
);
449 if (tok
&& tok
->type
== '_') {
452 tok
= stream_next_token(s
);
453 if (!tok
|| tok
->type
!= TOKEN_IDENT
) {
454 stream_error(s
, tok
, "expecting identifier");
456 stream_push_token(s
, tok
);
461 pos
= parameter_pos(p
, tok
->u
.s
, -1);
463 e
->x
.p
= new_enode(periodic
, n
, pos
+1);
465 value_clear(e
->x
.p
->arr
[n
].d
);
466 e
->x
.p
->arr
[n
] = *list
[n
];
471 stream_push_token(s
, tok
);
472 e
= create_fract_like(s
, list
[0], flooring
, p
);
475 stream_error(s
, tok
, "unexpected token");
477 stream_push_token(s
, tok
);
482 evalue_free(list
[n
]);
487 /* frees product on error */
488 static evalue
*read_factor_and_multiply(struct stream
*s
, struct parameter
**p
,
492 e2
= evalue_read_factor(s
, p
);
494 stream_error(s
, NULL
, "unexpected EOF");
495 evalue_free(product
);
503 static evalue
*evalue_read_factor(struct stream
*s
, struct parameter
**p
)
508 tok
= stream_next_token(s
);
512 if (tok
->type
== '(') {
514 e
= evalue_read_term(s
, p
);
515 tok
= stream_next_token(s
);
516 if (!tok
|| tok
->type
!= ')') {
517 stream_error(s
, tok
, "expecting \")\"");
519 stream_push_token(s
, tok
);
522 } else if (tok
->type
== TOKEN_VALUE
) {
525 value_set_si(e
->d
, 1);
527 value_assign(e
->x
.n
, tok
->u
.v
);
529 tok
= stream_next_token(s
);
530 if (tok
&& tok
->type
== '/') {
532 tok
= stream_next_token(s
);
533 if (!tok
|| tok
->type
!= TOKEN_VALUE
) {
534 stream_error(s
, tok
, "expecting denominator");
536 stream_push_token(s
, tok
);
539 value_assign(e
->d
, tok
->u
.v
);
541 } else if (tok
&& tok
->type
== TOKEN_IDENT
) {
542 stream_push_token(s
, tok
);
543 e
= read_factor_and_multiply(s
, p
, e
);
545 stream_push_token(s
, tok
);
546 } else if (tok
->type
== TOKEN_IDENT
) {
547 int pos
= parameter_pos(p
, tok
->u
.s
, -1);
548 int pow
= optional_power(s
);
552 e
->x
.p
= new_enode(polynomial
, pow
+1, pos
+1);
553 evalue_set_si(&e
->x
.p
->arr
[pow
], 1, 1);
555 evalue_set_si(&e
->x
.p
->arr
[pow
], 0, 1);
556 } else if (tok
->type
== '[') {
557 stream_push_token(s
, tok
);
558 e
= read_periodic(s
, p
);
559 } else if (tok
->type
== '{') {
560 stream_push_token(s
, tok
);
561 e
= read_fract(s
, tok
, p
);
564 tok
= stream_next_token(s
);
565 if (tok
&& tok
->type
== '*') {
567 e
= read_factor_and_multiply(s
, p
, e
);
569 stream_push_token(s
, tok
);
574 static evalue
*evalue_read_term(struct stream
*s
, struct parameter
**p
)
579 e
= evalue_read_factor(s
, p
);
583 tok
= stream_next_token(s
);
587 if (tok
->type
== '+' || tok
->type
== TOKEN_VALUE
) {
589 if (tok
->type
== '+')
592 stream_push_token(s
, tok
);
593 e2
= evalue_read_term(s
, p
);
595 stream_error(s
, NULL
, "unexpected EOF");
601 stream_push_token(s
, tok
);
609 struct constraint
*next
;
610 struct constraint
*union_next
;
613 static struct constraint
*constraint_new()
615 struct constraint
*c
= ALLOC(struct constraint
);
617 c
->v
= Vector_Alloc(16);
619 c
->union_next
= NULL
;
623 static void constraint_free(struct constraint
*c
)
626 struct constraint
*next
= c
->next
? c
->next
: c
->union_next
;
633 static void constraint_extend(struct constraint
*c
, int pos
)
636 if (pos
< c
->v
->Size
)
639 v
= Vector_Alloc((3*c
->v
->Size
)/2);
640 Vector_Copy(c
->v
->p
, v
->p
, c
->v
->Size
);
645 static int evalue_read_constraint(struct stream
*s
, struct parameter
**p
,
646 struct constraint
**constraints
,
647 struct constraint
*union_next
)
650 struct constraint
*c
= NULL
;
652 while ((tok
= stream_next_token(s
))) {
655 if (tok
->type
== '+')
657 else if (tok
->type
== TOKEN_IDENT
) {
659 c
= constraint_new();
660 pos
= parameter_pos(p
, tok
->u
.s
, -1);
661 constraint_extend(c
, 1+pos
);
662 value_set_si(c
->v
->p
[1+pos
], 1);
664 } else if (tok
->type
== TOKEN_VALUE
) {
666 c
= constraint_new();
667 tok2
= stream_next_token(s
);
668 if (tok2
&& tok2
->type
== TOKEN_IDENT
) {
669 pos
= parameter_pos(p
, tok2
->u
.s
, -1);
670 constraint_extend(c
, 1+pos
);
671 value_assign(c
->v
->p
[1+pos
], tok
->u
.v
);
676 stream_push_token(s
, tok2
);
677 value_assign(c
->v
->p
[0], tok
->u
.v
);
680 } else if (tok
->type
== TOKEN_GE
|| tok
->type
== '=') {
681 int type
= tok
->type
== TOKEN_GE
;
683 tok
= stream_next_token(s
);
684 if (!tok
|| tok
->type
!= TOKEN_VALUE
|| value_notzero_p(tok
->u
.v
)) {
685 stream_error(s
, tok
, "expecting \"0\"");
687 stream_push_token(s
, tok
);
691 c
->next
= *constraints
;
692 c
->union_next
= union_next
;
699 stream_push_token(s
, tok
);
701 stream_error(s
, tok
, "unexpected token");
710 static struct constraint
*evalue_read_domain(struct stream
*s
, struct parameter
**p
,
713 struct constraint
*constraints
= NULL
;
714 struct constraint
*union_next
= NULL
;
718 tok
= stream_next_token(s
);
721 stream_push_token(s
, tok
);
724 while (evalue_read_constraint(s
, p
, &constraints
, union_next
)) {
725 tok
= stream_next_token(s
);
727 if (tok
->type
== TOKEN_UNION
) {
729 tok
= stream_next_token(s
);
731 stream_error(s
, NULL
, "unexpected EOF");
734 stream_push_token(s
, tok
);
735 union_next
= constraints
;
739 stream_push_token(s
, tok
);
740 /* empty line separates domain from evalue */
741 if (tok
->line
> line
+1)
751 struct constraint
*constraints
;
753 struct section
*next
;
756 static char **extract_parameters(struct parameter
*p
, unsigned *nparam
)
761 *nparam
= p
? p
->pos
+1 : 0;
762 params
= ALLOCN(char *, *nparam
);
763 for (i
= 0; i
< *nparam
; ++i
) {
764 struct parameter
*next
= p
->next
;
765 params
[p
->pos
] = p
->name
;
772 static Polyhedron
*constraints2domain(struct constraint
*constraints
,
773 unsigned nparam
, unsigned MaxRays
)
778 struct constraint
*c
;
779 struct constraint
*union_next
= NULL
;
781 for (n
= 0, c
= constraints
; c
; ++n
, c
= c
->next
)
783 M
= Matrix_Alloc(n
, 1+nparam
+1);
785 struct constraint
*next
= constraints
->next
;
786 union_next
= constraints
->union_next
;
787 Vector_Copy(constraints
->v
->p
+1, M
->p
[n
]+1, nparam
);
788 if (constraints
->type
)
789 value_set_si(M
->p
[n
][0], 1);
790 value_assign(M
->p
[n
][1+nparam
], constraints
->v
->p
[0]);
791 constraints
->next
= NULL
;
792 constraints
->union_next
= NULL
;
793 constraint_free(constraints
);
796 D
= Constraints2Polyhedron(M
, MaxRays
);
800 D
= DomainConcat(D
, constraints2domain(union_next
, nparam
, MaxRays
));
804 static evalue
*evalue_read_partition(struct stream
*s
, struct parameter
*p
,
806 unsigned *nparam
, unsigned MaxRays
)
808 struct section
*part
= NULL
;
809 struct constraint
*constraints
;
813 while ((constraints
= evalue_read_domain(s
, &p
, MaxRays
))) {
814 struct section
*sect
;
815 evalue
*e
= evalue_read_term(s
, &p
);
817 stream_error(s
, NULL
, "missing evalue");
820 sect
= ALLOC(struct section
);
821 sect
->constraints
= constraints
;
832 *ppp
= extract_parameters(p
, nparam
);
835 e
->x
.p
= new_enode(partition
, 2*m
, *nparam
);
837 for (j
= 0; j
< m
; ++j
) {
839 struct section
*next
= part
->next
;
840 constraints
= part
->constraints
;
841 D
= constraints2domain(part
->constraints
, *nparam
, MaxRays
);
842 EVALUE_SET_DOMAIN(e
->x
.p
->arr
[2*j
], D
);
843 value_clear(e
->x
.p
->arr
[2*j
+1].d
);
844 e
->x
.p
->arr
[2*j
+1] = *part
->e
;
853 static evalue
*evalue_read(struct stream
*s
, const char *var_list
, char ***ppp
,
854 unsigned *nvar
, unsigned *nparam
, unsigned MaxRays
)
858 struct parameter
*p
= NULL
;
863 while ((next
= strchr(var_list
, ','))) {
865 parameter_pos(&p
, var_list
, next
-var_list
);
868 if (strlen(var_list
) > 0)
869 parameter_pos(&p
, var_list
, -1);
870 nv
= p
? p
->pos
+1 : 0;
874 if (!(tok
= stream_next_token(s
)))
877 if (tok
->type
== TOKEN_VARS
) {
880 tok
= stream_next_token(s
);
881 if (!tok
|| tok
->type
!= TOKEN_IDENT
) {
882 stream_error(s
, tok
, "expecting identifier");
886 parameter_pos(&p
, tok
->u
.s
, -1);
888 tok
= stream_next_token(s
);
889 if (!tok
|| tok
->type
!= ',')
896 nv
= p
? p
->pos
+1 : 0;
899 if (tok
->type
== '(' || tok
->type
== '[') {
900 stream_push_token(s
, tok
);
901 e
= evalue_read_term(s
, &p
);
902 *ppp
= extract_parameters(p
, nparam
);
903 } else if (tok
->type
== TOKEN_VALUE
) {
904 struct token
*tok2
= stream_next_token(s
);
906 stream_push_token(s
, tok2
);
907 stream_push_token(s
, tok
);
908 if (tok2
&& (tok2
->type
== TOKEN_IDENT
|| tok2
->type
== TOKEN_GE
))
909 e
= evalue_read_partition(s
, p
, ppp
, nparam
, MaxRays
);
911 e
= evalue_read_term(s
, &p
);
912 *ppp
= extract_parameters(p
, nparam
);
914 } else if (tok
->type
== TOKEN_IDENT
) {
915 stream_push_token(s
, tok
);
916 e
= evalue_read_partition(s
, p
, ppp
, nparam
, MaxRays
);
918 stream_error(s
, tok
, "unexpected token");
919 *nparam
= nv
== -1 ? 0 : nv
;
930 evalue
*evalue_read_from_file(FILE *in
, const char *var_list
, char ***ppp
,
931 unsigned *nvar
, unsigned *nparam
, unsigned MaxRays
)
934 struct stream
*s
= stream_new_file(in
);
935 e
= evalue_read(s
, var_list
, ppp
, nvar
, nparam
, MaxRays
);
940 evalue
*evalue_read_from_str(const char *str
, const char *var_list
, char ***ppp
,
941 unsigned *nvar
, unsigned *nparam
, unsigned MaxRays
)
944 struct stream
*s
= stream_new_str(str
);
945 e
= evalue_read(s
, var_list
, ppp
, nvar
, nparam
, MaxRays
);