5 #include "isl_map_private.h"
6 #include "isl_input_omega.h"
8 enum token_type
{ TOKEN_UNKNOWN
= 256, TOKEN_VALUE
, TOKEN_IDENT
, TOKEN_GE
,
9 TOKEN_LE
, TOKEN_TO
, TOKEN_AND
, TOKEN_EXISTS
};
14 unsigned int on_new_line
: 1;
24 static struct token
*token_new(struct isl_ctx
*ctx
,
25 int line
, int col
, unsigned on_new_line
)
27 struct token
*tok
= isl_alloc_type(ctx
, struct token
);
32 tok
->on_new_line
= on_new_line
;
36 void token_free(struct token
*tok
)
40 if (tok
->type
== TOKEN_VALUE
)
41 isl_int_clear(tok
->u
.v
);
42 else if (tok
->type
== TOKEN_IDENT
)
60 struct token
*tokens
[5];
64 void stream_error(struct stream
*s
, struct token
*tok
, char *msg
)
66 int line
= tok
? tok
->line
: s
->line
;
67 int col
= tok
? tok
->col
: s
->col
;
68 fprintf(stderr
, "syntax error (%d, %d): %s\n", line
, col
, msg
);
71 fprintf(stderr
, "got '%c'\n", tok
->type
);
73 fprintf(stderr
, "got token type %d\n", tok
->type
);
77 static void stream_free(struct stream
*s
);
79 static struct stream
* stream_new(struct isl_ctx
*ctx
)
82 struct stream
*s
= isl_alloc_type(ctx
, struct stream
);
89 s
->buffer
= isl_alloc_array(ctx
, char, s
->size
);
97 for (i
= 0; i
< 5; ++i
)
106 static struct stream
* stream_new_file(struct isl_ctx
*ctx
, FILE *file
)
108 struct stream
*s
= stream_new(ctx
);
115 static int stream_getc(struct stream
*s
)
140 static void stream_ungetc(struct stream
*s
, int c
)
149 static int stream_push_char(struct stream
*s
, int c
)
151 if (s
->len
>= s
->size
) {
152 s
->size
= (3*s
->size
)/2;
153 s
->buffer
= isl_realloc_array(ctx
, s
->buffer
, char, s
->size
);
157 s
->buffer
[s
->len
++] = c
;
161 static void stream_push_token(struct stream
*s
, struct token
*tok
)
163 isl_assert(s
->ctx
, s
->n_token
< 5, return);
164 s
->tokens
[s
->n_token
++] = tok
;
167 static struct token
*stream_next_token(struct stream
*s
)
170 struct token
*tok
= NULL
;
172 int old_line
= s
->line
;
175 return s
->tokens
[--s
->n_token
];
180 while ((c
= stream_getc(s
)) != -1 && isspace(c
))
202 tok
= token_new(s
->ctx
, line
, col
, old_line
!= line
);
205 tok
->type
= (enum token_type
)c
;
210 if ((c
= stream_getc(s
)) == '>') {
211 tok
= token_new(s
->ctx
, line
, col
, old_line
!= line
);
214 tok
->type
= TOKEN_TO
;
220 if (c
== '-' || isdigit(c
)) {
221 tok
= token_new(s
->ctx
, line
, col
, old_line
!= line
);
224 tok
->type
= TOKEN_VALUE
;
225 isl_int_init(tok
->u
.v
);
226 if (stream_push_char(s
, c
))
228 while ((c
= stream_getc(s
)) != -1 && isdigit(c
))
229 if (stream_push_char(s
, c
))
233 if (s
->len
== 1 && s
->buffer
[0] == '-')
234 isl_int_set_si(tok
->u
.v
, -1);
236 stream_push_char(s
, '\0');
237 isl_int_read(tok
->u
.v
, s
->buffer
);
242 tok
= token_new(s
->ctx
, line
, col
, old_line
!= line
);
245 stream_push_char(s
, c
);
246 while ((c
= stream_getc(s
)) != -1 && isalnum(c
))
247 stream_push_char(s
, c
);
250 stream_push_char(s
, '\0');
251 if (!strcasecmp(s
->buffer
, "exists"))
252 tok
->type
= TOKEN_EXISTS
;
254 tok
->type
= TOKEN_IDENT
;
255 tok
->u
.s
= strdup(s
->buffer
);
261 if ((c
= stream_getc(s
)) == '=') {
262 tok
= token_new(s
->ctx
, line
, col
, old_line
!= line
);
265 tok
->type
= TOKEN_GE
;
273 if ((c
= stream_getc(s
)) == '=') {
274 tok
= token_new(s
->ctx
, line
, col
, old_line
!= line
);
277 tok
->type
= TOKEN_LE
;
284 tok
= token_new(s
->ctx
, line
, col
, old_line
!= line
);
287 tok
->type
= TOKEN_AND
;
288 if ((c
= stream_getc(s
)) != '&' && c
!= -1)
293 tok
= token_new(s
->ctx
, line
, col
, old_line
!= line
);
296 tok
->type
= TOKEN_UNKNOWN
;
303 static int stream_eat(struct stream
*s
, int type
)
307 tok
= stream_next_token(s
);
310 if (tok
->type
== type
) {
314 stream_error(s
, tok
, "expecting other token");
315 stream_push_token(s
, tok
);
319 static void stream_free(struct stream
*s
)
324 if (s
->n_token
!= 0) {
325 struct token
*tok
= stream_next_token(s
);
326 stream_error(s
, tok
, "unexpected token");
335 struct variable
*next
;
344 static struct vars
*vars_new(struct isl_ctx
*ctx
)
347 v
= isl_alloc_type(ctx
, struct vars
);
356 void variable_free(struct variable
*var
)
359 struct variable
*next
= var
->next
;
366 static void vars_free(struct vars
*v
)
374 struct variable
*variable_new(struct vars
*v
, const char *name
, int len
,
377 struct variable
*var
;
378 var
= isl_alloc_type(v
->ctx
, struct variable
);
381 var
->name
= strdup(name
);
382 var
->name
[len
] = '\0';
391 static int vars_pos(struct vars
*v
, const char *s
, int len
)
398 for (q
= v
->v
; q
; q
= q
->next
) {
399 if (strncmp(q
->name
, s
, len
) == 0 && q
->name
[len
] == '\0')
406 v
->v
= variable_new(v
, s
, len
, v
->n
);
414 static struct vars
*read_var_list(struct stream
*s
, struct vars
*v
)
418 while ((tok
= stream_next_token(s
)) != NULL
) {
422 if (tok
->type
!= TOKEN_IDENT
)
425 p
= vars_pos(v
, tok
->u
.s
, -1);
429 stream_error(s
, tok
, "expecting unique identifier");
433 tok
= stream_next_token(s
);
434 if (!tok
|| tok
->type
!= ',')
440 stream_push_token(s
, tok
);
449 static struct vars
*read_tuple(struct stream
*s
, struct vars
*v
)
453 tok
= stream_next_token(s
);
454 if (!tok
|| tok
->type
!= '[') {
455 stream_error(s
, tok
, "expecting '['");
459 v
= read_var_list(s
, v
);
460 tok
= stream_next_token(s
);
461 if (!tok
|| tok
->type
!= ']') {
462 stream_error(s
, tok
, "expecting ']'");
475 static struct isl_basic_map
*add_constraints(struct stream
*s
,
476 struct vars
**v
, struct isl_basic_map
*bmap
);
478 static struct isl_basic_map
*add_exists(struct stream
*s
,
479 struct vars
**v
, struct isl_basic_map
*bmap
)
488 tok
= stream_next_token(s
);
491 if (tok
->type
== '(') {
495 stream_push_token(s
, tok
);
496 *v
= read_var_list(s
, *v
);
500 bmap
= isl_basic_map_extend(bmap
, bmap
->nparam
,
501 bmap
->n_in
, bmap
->n_out
, extra
, 0, 0);
502 total
= bmap
->nparam
+bmap
->n_in
+bmap
->n_out
+bmap
->extra
;
503 for (i
= 0; i
< extra
; ++i
) {
505 if ((k
= isl_basic_map_alloc_div(bmap
)) < 0)
507 isl_seq_clr(bmap
->div
[k
], 1+1+total
);
511 if (stream_eat(s
, ':'))
513 bmap
= add_constraints(s
, v
, bmap
);
514 if (seen_paren
&& stream_eat(s
, ')'))
518 isl_basic_map_free(bmap
);
522 static struct isl_basic_map
*add_constraint(struct stream
*s
,
523 struct vars
**v
, struct isl_basic_map
*bmap
)
525 unsigned total
= bmap
->nparam
+bmap
->n_in
+bmap
->n_out
+bmap
->extra
;
530 struct token
*tok
= NULL
;
532 tok
= stream_next_token(s
);
535 if (tok
->type
== TOKEN_EXISTS
) {
537 return add_exists(s
, v
, bmap
);
539 stream_push_token(s
, tok
);
541 bmap
= isl_basic_map_extend(bmap
, bmap
->nparam
,
542 bmap
->n_in
, bmap
->n_out
, 0, 0, 1);
543 k
= isl_basic_map_alloc_inequality(bmap
);
546 isl_seq_clr(bmap
->ineq
[k
], 1+total
);
549 tok
= stream_next_token(s
);
551 stream_error(s
, NULL
, "unexpected EOF");
554 if (tok
->type
== TOKEN_IDENT
) {
556 int pos
= vars_pos(*v
, tok
->u
.s
, -1);
560 stream_error(s
, tok
, "unknown identifier");
564 isl_int_add_ui(bmap
->ineq
[k
][1+pos
],
565 bmap
->ineq
[k
][1+pos
], 1);
567 isl_int_sub_ui(bmap
->ineq
[k
][1+pos
],
568 bmap
->ineq
[k
][1+pos
], 1);
569 } else if (tok
->type
== TOKEN_VALUE
) {
573 tok2
= stream_next_token(s
);
574 if (tok2
&& tok2
->type
== TOKEN_IDENT
) {
575 pos
= vars_pos(*v
, tok2
->u
.s
, -1);
579 stream_error(s
, tok2
,
580 "unknown identifier");
586 stream_push_token(s
, tok2
);
588 isl_int_neg(tok
->u
.v
, tok
->u
.v
);
589 isl_int_add(bmap
->ineq
[k
][1+pos
],
590 bmap
->ineq
[k
][1+pos
], tok
->u
.v
);
591 } else if (tok
->type
== TOKEN_LE
) {
593 isl_seq_neg(bmap
->ineq
[k
], bmap
->ineq
[k
], 1+total
);
594 } else if (tok
->type
== TOKEN_GE
) {
597 } else if (tok
->type
== '=') {
599 stream_error(s
, tok
, "too many operators");
606 stream_push_token(s
, tok
);
613 stream_error(s
, tok
, "missing operator");
617 isl_basic_map_inequality_to_equality(bmap
, k
);
622 isl_basic_map_free(bmap
);
626 static struct isl_basic_map
*add_constraints(struct stream
*s
,
627 struct vars
**v
, struct isl_basic_map
*bmap
)
632 bmap
= add_constraint(s
, v
, bmap
);
635 tok
= stream_next_token(s
);
637 stream_error(s
, NULL
, "unexpected EOF");
640 if (tok
->type
!= TOKEN_AND
)
644 stream_push_token(s
, tok
);
650 isl_basic_map_free(bmap
);
654 static struct isl_basic_map
*basic_map_read(struct stream
*s
)
656 struct isl_basic_map
*bmap
= NULL
;
658 struct vars
*v
= NULL
;
662 tok
= stream_next_token(s
);
663 if (!tok
|| tok
->type
!= '{') {
664 stream_error(s
, tok
, "expecting '{'");
666 stream_push_token(s
, tok
);
670 v
= vars_new(s
->ctx
);
671 v
= read_tuple(s
, v
);
675 tok
= stream_next_token(s
);
676 if (tok
&& tok
->type
== TOKEN_TO
) {
678 v
= read_tuple(s
, v
);
684 stream_push_token(s
, tok
);
688 bmap
= isl_basic_map_alloc(s
->ctx
, 0, n1
, n2
, 0, 0,0);
691 tok
= stream_next_token(s
);
692 if (tok
&& tok
->type
== ':') {
694 bmap
= add_constraints(s
, &v
, bmap
);
695 tok
= stream_next_token(s
);
697 if (tok
&& tok
->type
== '}') {
700 stream_error(s
, tok
, "unexpected token");
709 isl_basic_map_free(bmap
);
715 struct isl_basic_map
*isl_basic_map_read_from_file_omega(
716 struct isl_ctx
*ctx
, FILE *input
)
718 struct isl_basic_map
*bmap
;
719 struct stream
*s
= stream_new_file(ctx
, input
);
722 bmap
= basic_map_read(s
);
727 struct isl_basic_set
*isl_basic_set_read_from_file_omega(
728 struct isl_ctx
*ctx
, FILE *input
)
730 struct isl_basic_map
*bmap
;
731 bmap
= isl_basic_map_read_from_file_omega(ctx
, input
);
734 isl_assert(ctx
, bmap
->n_in
== 0, goto error
);
735 return (struct isl_basic_set
*)bmap
;
737 isl_basic_map_free(bmap
);