1 #include <barvinok/util.h>
2 #include "evalue_read.h"
4 #define ALLOC(type) (type*)malloc(sizeof(type))
5 #define ALLOCN(type,n) (type*)malloc((n) * sizeof(type))
7 enum token_type
{ TOKEN_UNKNOWN
= 256, TOKEN_VALUE
, TOKEN_IDENT
, TOKEN_GE
,
8 TOKEN_NE
, TOKEN_UNION
, TOKEN_VARS
};
22 static struct token
*token_new(int line
, int col
)
24 struct token
*tok
= ALLOC(struct token
);
30 void token_free(struct token
*tok
)
32 if (tok
->type
== TOKEN_VALUE
)
33 value_clear(tok
->u
.v
);
34 else if (tok
->type
== TOKEN_IDENT
)
51 struct token
*tokens
[5];
55 static struct stream
* stream_new()
58 struct stream
*s
= ALLOC(struct stream
);
62 s
->buffer
= (char*)malloc(s
->size
);
68 for (i
= 0; i
< 5; ++i
)
74 static struct stream
* stream_new_file(FILE *file
)
76 struct stream
*s
= stream_new();
81 static struct stream
* stream_new_str(const char *str
)
83 struct stream
*s
= stream_new();
88 static int stream_getc(struct stream
*s
)
113 static void stream_ungetc(struct stream
*s
, int c
)
122 static void stream_push_char(struct stream
*s
, int c
)
124 if (s
->len
>= s
->size
) {
125 s
->size
= (3*s
->size
)/2;
126 s
->buffer
= (char*)realloc(s
->buffer
, s
->size
);
128 s
->buffer
[s
->len
++] = c
;
131 static struct token
*stream_push_token(struct stream
*s
, struct token
*tok
)
133 assert(s
->n_token
< 5);
134 s
->tokens
[s
->n_token
++] = tok
;
137 static struct token
*stream_next_token(struct stream
*s
)
144 return s
->tokens
[--s
->n_token
];
149 while ((c
= stream_getc(s
)) != -1 && isspace(c
))
171 tok
= token_new(line
, col
);
172 tok
->type
= (enum token_type
)c
;
175 if (c
== '-' || isdigit(c
)) {
176 tok
= token_new(line
, col
);
177 tok
->type
= TOKEN_VALUE
;
178 value_init(tok
->u
.v
);
179 stream_push_char(s
, c
);
180 while ((c
= stream_getc(s
)) != -1 && isdigit(c
))
181 stream_push_char(s
, c
);
184 if (s
->len
== 1 && s
->buffer
[0] == '-')
185 value_set_si(tok
->u
.v
, -1);
187 stream_push_char(s
, '\0');
188 mpz_set_str(tok
->u
.v
, s
->buffer
, 0);
192 if (c
== '#' || isalpha(c
)) {
193 tok
= token_new(line
, col
);
194 stream_push_char(s
, c
);
195 while ((c
= stream_getc(s
)) != -1 && isalnum(c
))
196 stream_push_char(s
, c
);
199 stream_push_char(s
, '\0');
200 if (!strcmp(s
->buffer
, "#variables")) {
201 tok
->type
= TOKEN_VARS
;
202 } else if (s
->buffer
[0] == '#') {
203 tok
->type
= TOKEN_UNKNOWN
;
204 } else if (!strcmp(s
->buffer
, "UNION")) {
205 tok
->type
= TOKEN_UNION
;
207 tok
->type
= TOKEN_IDENT
;
208 tok
->u
.s
= strdup(s
->buffer
);
213 if ((c
= stream_getc(s
)) == '=') {
214 tok
= token_new(line
, col
);
215 tok
->type
= TOKEN_GE
;
222 if ((c
= stream_getc(s
)) == '=') {
223 tok
= token_new(line
, col
);
224 tok
->type
= TOKEN_NE
;
231 tok
= token_new(line
, col
);
232 tok
->type
= TOKEN_UNKNOWN
;
236 void stream_error(struct stream
*s
, struct token
*tok
, char *msg
)
238 int line
= tok
? tok
->line
: s
->line
;
239 int col
= tok
? tok
->col
: s
->col
;
240 fprintf(stderr
, "syntax error (%d, %d): %s\n", line
, col
, msg
);
243 fprintf(stderr
, "got '%c'\n", tok
->type
);
245 fprintf(stderr
, "got token type %d\n", tok
->type
);
249 static void stream_free(struct stream
*s
)
252 if (s
->n_token
!= 0) {
253 struct token
*tok
= stream_next_token(s
);
254 stream_error(s
, tok
, "unexpected token");
262 struct parameter
*next
;
265 struct parameter
*parameter_new(const char *name
, int pos
, struct parameter
*next
)
267 struct parameter
*p
= ALLOC(struct parameter
);
268 p
->name
= strdup(name
);
274 static int parameter_pos(struct parameter
**p
, const char *s
, int len
)
276 int pos
= *p
? (*p
)->pos
+1 : 0;
281 for (q
= *p
; q
; q
= q
->next
) {
282 if (strncmp(q
->name
, s
, len
) == 0)
288 *p
= parameter_new(s
, pos
, *p
);
292 static int optional_power(struct stream
*s
)
296 tok
= stream_next_token(s
);
299 if (tok
->type
!= '^') {
300 stream_push_token(s
, tok
);
304 tok
= stream_next_token(s
);
305 if (!tok
|| tok
->type
!= TOKEN_VALUE
) {
306 stream_error(s
, tok
, "expecting exponent");
308 stream_push_token(s
, tok
);
311 pow
= VALUE_TO_INT(tok
->u
.v
);
316 static evalue
*evalue_read_factor(struct stream
*s
, struct parameter
**p
);
317 static evalue
*evalue_read_term(struct stream
*s
, struct parameter
**p
);
319 static evalue
*create_fract_like(struct stream
*s
, evalue
*arg
, enode_type type
,
320 struct parameter
**p
)
324 pow
= optional_power(s
);
328 e
->x
.p
= new_enode(type
, pow
+2, -1);
329 value_clear(e
->x
.p
->arr
[0].d
);
330 e
->x
.p
->arr
[0] = *arg
;
332 evalue_set_si(&e
->x
.p
->arr
[1+pow
], 1, 1);
334 evalue_set_si(&e
->x
.p
->arr
[1+pow
], 0, 1);
339 static evalue
*create_relation(evalue
*arg
, int ne
)
345 e
->x
.p
= new_enode(relation
, 2+ne
, 0);
346 value_clear(e
->x
.p
->arr
[0].d
);
347 e
->x
.p
->arr
[0] = *arg
;
350 evalue_set_si(&e
->x
.p
->arr
[1], 0, 1);
351 evalue_set_si(&e
->x
.p
->arr
[1+ne
], 1, 1);
356 static evalue
*read_fract(struct stream
*s
, struct token
*tok
, struct parameter
**p
)
360 tok
= stream_next_token(s
);
362 assert(tok
->type
== '{');
365 arg
= evalue_read_term(s
, p
);
366 tok
= stream_next_token(s
);
367 if (!tok
|| tok
->type
!= '}') {
368 stream_error(s
, tok
, "expecting \"}\"");
370 stream_push_token(s
, tok
);
374 return create_fract_like(s
, arg
, fractional
, p
);
377 static evalue
*read_periodic(struct stream
*s
, struct parameter
**p
)
385 tok
= stream_next_token(s
);
386 assert(tok
&& tok
->type
== '[');
390 list
= (evalue
**)malloc(len
* sizeof(evalue
*));
394 evalue
*e
= evalue_read_term(s
, p
);
396 stream_error(s
, NULL
, "missing argument or list element");
401 list
= (evalue
**)realloc(list
, len
* sizeof(evalue
*));
405 tok
= stream_next_token(s
);
407 stream_error(s
, NULL
, "unexpected EOF");
410 if (tok
->type
!= ',')
415 if (n
== 1 && (tok
->type
== '=' || tok
->type
== TOKEN_NE
)) {
416 int ne
= tok
->type
== TOKEN_NE
;
418 tok
= stream_next_token(s
);
419 if (!tok
|| tok
->type
!= TOKEN_VALUE
) {
420 stream_error(s
, tok
, "expecting \"0\"");
422 stream_push_token(s
, tok
);
426 tok
= stream_next_token(s
);
427 if (!tok
|| tok
->type
!= ']') {
428 stream_error(s
, tok
, "expecting \"]\"");
430 stream_push_token(s
, tok
);
434 e
= create_relation(list
[0], ne
);
439 if (tok
->type
!= ']') {
440 stream_error(s
, tok
, "expecting \"]\"");
441 stream_push_token(s
, tok
);
447 tok
= stream_next_token(s
);
448 if (tok
&& tok
->type
== '_') {
451 tok
= stream_next_token(s
);
452 if (!tok
|| tok
->type
!= TOKEN_IDENT
) {
453 stream_error(s
, tok
, "expecting identifier");
455 stream_push_token(s
, tok
);
460 pos
= parameter_pos(p
, tok
->u
.s
, -1);
462 e
->x
.p
= new_enode(periodic
, n
, pos
+1);
464 value_clear(e
->x
.p
->arr
[n
].d
);
465 e
->x
.p
->arr
[n
] = *list
[n
];
470 stream_push_token(s
, tok
);
471 e
= create_fract_like(s
, list
[0], flooring
, p
);
474 stream_error(s
, tok
, "unexpected token");
476 stream_push_token(s
, tok
);
481 free_evalue_refs(list
[n
]);
488 /* frees product on error */
489 static evalue
*read_factor_and_multiply(struct stream
*s
, struct parameter
**p
,
493 e2
= evalue_read_factor(s
, p
);
495 stream_error(s
, NULL
, "unexpected EOF");
496 free_evalue_refs(product
);
501 free_evalue_refs(e2
);
506 static evalue
*evalue_read_factor(struct stream
*s
, struct parameter
**p
)
511 tok
= stream_next_token(s
);
515 if (tok
->type
== '(') {
517 e
= evalue_read_term(s
, p
);
518 tok
= stream_next_token(s
);
519 if (!tok
|| tok
->type
!= ')') {
520 stream_error(s
, tok
, "expecting \")\"");
522 stream_push_token(s
, tok
);
525 } else if (tok
->type
== TOKEN_VALUE
) {
528 value_set_si(e
->d
, 1);
530 value_assign(e
->x
.n
, tok
->u
.v
);
532 tok
= stream_next_token(s
);
533 if (tok
&& tok
->type
== '/') {
535 tok
= stream_next_token(s
);
536 if (!tok
|| tok
->type
!= TOKEN_VALUE
) {
537 stream_error(s
, tok
, "expecting denominator");
539 stream_push_token(s
, tok
);
542 value_assign(e
->d
, tok
->u
.v
);
544 } else if (tok
&& tok
->type
== TOKEN_IDENT
) {
545 stream_push_token(s
, tok
);
546 e
= read_factor_and_multiply(s
, p
, e
);
548 stream_push_token(s
, tok
);
549 } else if (tok
->type
== TOKEN_IDENT
) {
550 int pos
= parameter_pos(p
, tok
->u
.s
, -1);
551 int pow
= optional_power(s
);
555 e
->x
.p
= new_enode(polynomial
, pow
+1, pos
+1);
556 evalue_set_si(&e
->x
.p
->arr
[pow
], 1, 1);
558 evalue_set_si(&e
->x
.p
->arr
[pow
], 0, 1);
559 } else if (tok
->type
== '[') {
560 stream_push_token(s
, tok
);
561 e
= read_periodic(s
, p
);
562 } else if (tok
->type
== '{') {
563 stream_push_token(s
, tok
);
564 e
= read_fract(s
, tok
, p
);
567 tok
= stream_next_token(s
);
568 if (tok
&& tok
->type
== '*') {
570 e
= read_factor_and_multiply(s
, p
, e
);
572 stream_push_token(s
, tok
);
577 static evalue
*evalue_read_term(struct stream
*s
, struct parameter
**p
)
582 e
= evalue_read_factor(s
, p
);
586 tok
= stream_next_token(s
);
590 if (tok
->type
== '+' || tok
->type
== TOKEN_VALUE
) {
592 if (tok
->type
== '+')
595 stream_push_token(s
, tok
);
596 e2
= evalue_read_term(s
, p
);
598 stream_error(s
, NULL
, "unexpected EOF");
602 free_evalue_refs(e2
);
605 stream_push_token(s
, tok
);
613 struct constraint
*next
;
614 struct constraint
*union_next
;
617 static struct constraint
*constraint_new()
619 struct constraint
*c
= ALLOC(struct constraint
);
621 c
->v
= Vector_Alloc(16);
623 c
->union_next
= NULL
;
627 static void constraint_free(struct constraint
*c
)
630 struct constraint
*next
= c
->next
? c
->next
: c
->union_next
;
637 static void constraint_extend(struct constraint
*c
, int pos
)
640 if (pos
< c
->v
->Size
)
643 v
= Vector_Alloc((3*c
->v
->Size
)/2);
644 Vector_Copy(c
->v
->p
, v
->p
, c
->v
->Size
);
649 static int evalue_read_constraint(struct stream
*s
, struct parameter
**p
,
650 struct constraint
**constraints
,
651 struct constraint
*union_next
)
654 struct constraint
*c
= NULL
;
656 while ((tok
= stream_next_token(s
))) {
659 if (tok
->type
== '+')
661 else if (tok
->type
== TOKEN_IDENT
) {
663 c
= constraint_new();
664 pos
= parameter_pos(p
, tok
->u
.s
, -1);
665 constraint_extend(c
, 1+pos
);
666 value_set_si(c
->v
->p
[1+pos
], 1);
668 } else if (tok
->type
== TOKEN_VALUE
) {
670 c
= constraint_new();
671 tok2
= stream_next_token(s
);
672 if (tok2
&& tok2
->type
== TOKEN_IDENT
) {
673 pos
= parameter_pos(p
, tok2
->u
.s
, -1);
674 constraint_extend(c
, 1+pos
);
675 value_assign(c
->v
->p
[1+pos
], tok
->u
.v
);
680 stream_push_token(s
, tok2
);
681 value_assign(c
->v
->p
[0], tok
->u
.v
);
684 } else if (tok
->type
== TOKEN_GE
|| tok
->type
== '=') {
685 int type
= tok
->type
== TOKEN_GE
;
687 tok
= stream_next_token(s
);
688 if (!tok
|| tok
->type
!= TOKEN_VALUE
|| value_notzero_p(tok
->u
.v
)) {
689 stream_error(s
, tok
, "expecting \"0\"");
691 stream_push_token(s
, tok
);
695 c
->next
= *constraints
;
696 c
->union_next
= union_next
;
703 stream_push_token(s
, tok
);
705 stream_error(s
, tok
, "unexpected token");
714 static struct constraint
*evalue_read_domain(struct stream
*s
, struct parameter
**p
,
717 struct constraint
*constraints
= NULL
;
718 struct constraint
*union_next
= NULL
;
722 tok
= stream_next_token(s
);
725 stream_push_token(s
, tok
);
728 while (evalue_read_constraint(s
, p
, &constraints
, union_next
)) {
729 tok
= stream_next_token(s
);
731 if (tok
->type
== TOKEN_UNION
) {
733 tok
= stream_next_token(s
);
735 stream_error(s
, NULL
, "unexpected EOF");
738 stream_push_token(s
, tok
);
739 union_next
= constraints
;
743 stream_push_token(s
, tok
);
744 /* empty line separates domain from evalue */
745 if (tok
->line
> line
+1)
755 struct constraint
*constraints
;
757 struct section
*next
;
760 static char **extract_parameters(struct parameter
*p
, unsigned *nparam
)
765 *nparam
= p
? p
->pos
+1 : 0;
766 params
= ALLOCN(char *, *nparam
);
767 for (i
= 0; i
< *nparam
; ++i
) {
768 struct parameter
*next
= p
->next
;
769 params
[p
->pos
] = p
->name
;
776 static Polyhedron
*constraints2domain(struct constraint
*constraints
,
777 unsigned nparam
, unsigned MaxRays
)
782 struct constraint
*c
;
783 struct constraint
*union_next
= NULL
;
785 for (n
= 0, c
= constraints
; c
; ++n
, c
= c
->next
)
787 M
= Matrix_Alloc(n
, 1+nparam
+1);
789 struct constraint
*next
= constraints
->next
;
790 union_next
= constraints
->union_next
;
791 Vector_Copy(constraints
->v
->p
+1, M
->p
[n
]+1, nparam
);
792 if (constraints
->type
)
793 value_set_si(M
->p
[n
][0], 1);
794 value_assign(M
->p
[n
][1+nparam
], constraints
->v
->p
[0]);
795 constraints
->next
= NULL
;
796 constraints
->union_next
= NULL
;
797 constraint_free(constraints
);
800 D
= Constraints2Polyhedron(M
, MaxRays
);
804 D
= DomainConcat(D
, constraints2domain(union_next
, nparam
, MaxRays
));
808 static evalue
*evalue_read_partition(struct stream
*s
, struct parameter
*p
,
810 unsigned *nparam
, unsigned MaxRays
)
812 struct section
*part
= NULL
;
813 struct constraint
*constraints
;
817 while ((constraints
= evalue_read_domain(s
, &p
, MaxRays
))) {
818 evalue
*e
= evalue_read_term(s
, &p
);
820 stream_error(s
, NULL
, "missing evalue");
823 struct section
*sect
= ALLOC(struct section
);
824 sect
->constraints
= constraints
;
835 *ppp
= extract_parameters(p
, nparam
);
838 e
->x
.p
= new_enode(partition
, 2*m
, *nparam
);
840 for (j
= 0; j
< m
; ++j
) {
842 struct section
*next
= part
->next
;
843 constraints
= part
->constraints
;
844 D
= constraints2domain(part
->constraints
, *nparam
, MaxRays
);
845 EVALUE_SET_DOMAIN(e
->x
.p
->arr
[2*j
], D
);
846 value_clear(e
->x
.p
->arr
[2*j
+1].d
);
847 e
->x
.p
->arr
[2*j
+1] = *part
->e
;
856 static evalue
*evalue_read(struct stream
*s
, const char *var_list
, char ***ppp
,
857 unsigned *nvar
, unsigned *nparam
, unsigned MaxRays
)
861 struct parameter
*p
= NULL
;
866 while ((next
= strchr(var_list
, ','))) {
868 parameter_pos(&p
, var_list
, next
-var_list
);
871 if (strlen(var_list
) > 0)
872 parameter_pos(&p
, var_list
, -1);
873 nv
= p
? p
->pos
+1 : 0;
877 if (!(tok
= stream_next_token(s
)))
880 if (tok
->type
== TOKEN_VARS
) {
883 tok
= stream_next_token(s
);
884 if (!tok
|| tok
->type
!= TOKEN_IDENT
) {
885 stream_error(s
, tok
, "expecting identifier");
889 parameter_pos(&p
, tok
->u
.s
, -1);
891 tok
= stream_next_token(s
);
892 if (!tok
|| tok
->type
!= ',')
899 nv
= p
? p
->pos
+1 : 0;
902 if (tok
->type
== '(') {
903 stream_push_token(s
, tok
);
904 e
= evalue_read_term(s
, &p
);
905 *ppp
= extract_parameters(p
, nparam
);
906 } else if (tok
->type
== TOKEN_VALUE
) {
907 struct token
*tok2
= stream_next_token(s
);
909 stream_push_token(s
, tok2
);
910 stream_push_token(s
, tok
);
911 if (tok2
&& (tok2
->type
== TOKEN_IDENT
|| tok2
->type
== TOKEN_GE
))
912 e
= evalue_read_partition(s
, p
, ppp
, nparam
, MaxRays
);
914 e
= evalue_read_term(s
, &p
);
915 *ppp
= extract_parameters(p
, nparam
);
917 } else if (tok
->type
== TOKEN_IDENT
) {
918 stream_push_token(s
, tok
);
919 e
= evalue_read_partition(s
, p
, ppp
, nparam
, MaxRays
);
921 stream_error(s
, tok
, "unexpected token");
922 *nparam
= nv
== -1 ? 0 : nv
;
933 evalue
*evalue_read_from_file(FILE *in
, const char *var_list
, char ***ppp
,
934 unsigned *nvar
, unsigned *nparam
, unsigned MaxRays
)
937 struct stream
*s
= stream_new_file(in
);
938 e
= evalue_read(s
, var_list
, ppp
, nvar
, nparam
, MaxRays
);
943 evalue
*evalue_read_from_str(const char *str
, const char *var_list
, char ***ppp
,
944 unsigned *nvar
, unsigned *nparam
, unsigned MaxRays
)
947 struct stream
*s
= stream_new_str(str
);
948 e
= evalue_read(s
, var_list
, ppp
, nvar
, nparam
, MaxRays
);