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 struct stream* stream_new_str(struct isl_ctx *ctx, const char *str)
117 struct stream *s = stream_new(ctx);
122 static int stream_getc(struct stream *s)
147 static void stream_ungetc(struct stream *s, int c)
156 static int stream_push_char(struct stream *s, int c)
158 if (s->len >= s->size) {
159 s->size = (3*s->size)/2;
160 s->buffer = isl_realloc_array(ctx, s->buffer, char, s->size);
164 s->buffer[s->len++] = c;
168 static void stream_push_token(struct stream *s, struct token *tok)
170 isl_assert(s->ctx, s->n_token < 5, return);
171 s->tokens[s->n_token++] = tok;
174 static struct token *stream_next_token(struct stream *s)
177 struct token *tok = NULL;
179 int old_line = s->line;
182 return s->tokens[--s->n_token];
187 while ((c = stream_getc(s)) != -1 && isspace(c))
209 tok = token_new(s->ctx, line, col, old_line != line);
212 tok->type = (enum token_type)c;
217 if ((c = stream_getc(s)) == '>') {
218 tok = token_new(s->ctx, line, col, old_line != line);
221 tok->type = TOKEN_TO;
227 if (c == '-' || isdigit(c)) {
228 tok = token_new(s->ctx, line, col, old_line != line);
231 tok->type = TOKEN_VALUE;
232 isl_int_init(tok->u.v);
233 if (stream_push_char(s, c))
235 while ((c = stream_getc(s)) != -1 && isdigit(c))
236 if (stream_push_char(s, c))
240 if (s->len == 1 && s->buffer[0] == '-')
241 isl_int_set_si(tok->u.v, -1);
243 stream_push_char(s, '\0');
244 isl_int_read(tok->u.v, s->buffer);
249 tok = token_new(s->ctx, line, col, old_line != line);
252 stream_push_char(s, c);
253 while ((c = stream_getc(s)) != -1 && isalnum(c))
254 stream_push_char(s, c);
257 stream_push_char(s, '\0');
258 if (!strcasecmp(s->buffer, "exists"))
259 tok->type = TOKEN_EXISTS;
261 tok->type = TOKEN_IDENT;
262 tok->u.s = strdup(s->buffer);
268 if ((c = stream_getc(s)) == '=') {
269 tok = token_new(s->ctx, line, col, old_line != line);
272 tok->type = TOKEN_GE;
280 if ((c = stream_getc(s)) == '=') {
281 tok = token_new(s->ctx, line, col, old_line != line);
284 tok->type = TOKEN_LE;
291 tok = token_new(s->ctx, line, col, old_line != line);
294 tok->type = TOKEN_AND;
295 if ((c = stream_getc(s)) != '&' && c != -1)
300 tok = token_new(s->ctx, line, col, old_line != line);
303 tok->type = TOKEN_UNKNOWN;
310 static int stream_eat(struct stream *s, int type)
314 tok = stream_next_token(s);
317 if (tok->type == type) {
321 stream_error(s, tok, "expecting other token");
322 stream_push_token(s, tok);
326 static void stream_free(struct stream *s)
331 if (s->n_token != 0) {
332 struct token *tok = stream_next_token(s);
333 stream_error(s, tok, "unexpected token");
342 struct variable *next;
351 static struct vars *vars_new(struct isl_ctx *ctx)
354 v = isl_alloc_type(ctx, struct vars);
363 void variable_free(struct variable *var)
366 struct variable *next = var->next;
373 static void vars_free(struct vars *v)
381 struct variable *variable_new(struct vars *v, const char *name, int len,
384 struct variable *var;
385 var = isl_alloc_type(v->ctx, struct variable);
388 var->name = strdup(name);
389 var->name[len] = '\0';
398 static int vars_pos(struct vars *v, const char *s, int len)
405 for (q = v->v; q; q = q->next) {
406 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
413 v->v = variable_new(v, s, len, v->n);
421 static struct vars *read_var_list(struct stream *s, struct vars *v)
425 while ((tok = stream_next_token(s)) != NULL) {
429 if (tok->type != TOKEN_IDENT)
432 p = vars_pos(v, tok->u.s, -1);
436 stream_error(s, tok, "expecting unique identifier");
440 tok = stream_next_token(s);
441 if (!tok || tok->type != ',')
447 stream_push_token(s, tok);
456 static struct vars *read_tuple(struct stream *s, struct vars *v)
460 tok = stream_next_token(s);
461 if (!tok || tok->type != '[') {
462 stream_error(s, tok, "expecting '['");
466 v = read_var_list(s, v);
467 tok = stream_next_token(s);
468 if (!tok || tok->type != ']') {
469 stream_error(s, tok, "expecting ']'");
482 static struct isl_basic_map *add_constraints(struct stream *s,
483 struct vars **v, struct isl_basic_map *bmap);
485 static struct isl_basic_map *add_exists(struct stream *s,
486 struct vars **v, struct isl_basic_map *bmap)
495 tok = stream_next_token(s);
498 if (tok->type == '(') {
502 stream_push_token(s, tok);
503 *v = read_var_list(s, *v);
507 bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
509 total = isl_basic_map_total_dim(bmap);
510 for (i = 0; i < extra; ++i) {
512 if ((k = isl_basic_map_alloc_div(bmap)) < 0)
514 isl_seq_clr(bmap->div[k], 1+1+total);
518 if (stream_eat(s, ':'))
520 bmap = add_constraints(s, v, bmap);
521 if (seen_paren && stream_eat(s, ')'))
525 isl_basic_map_free(bmap);
529 static struct isl_basic_map *add_constraint(struct stream *s,
530 struct vars **v, struct isl_basic_map *bmap)
532 unsigned total = isl_basic_map_total_dim(bmap);
537 struct token *tok = NULL;
539 tok = stream_next_token(s);
542 if (tok->type == TOKEN_EXISTS) {
544 return add_exists(s, v, bmap);
546 stream_push_token(s, tok);
548 bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
549 k = isl_basic_map_alloc_inequality(bmap);
552 isl_seq_clr(bmap->ineq[k], 1+total);
555 tok = stream_next_token(s);
557 stream_error(s, NULL, "unexpected EOF");
560 if (tok->type == TOKEN_IDENT) {
562 int pos = vars_pos(*v, tok->u.s, -1);
566 stream_error(s, tok, "unknown identifier");
570 isl_int_add_ui(bmap->ineq[k][1+pos],
571 bmap->ineq[k][1+pos], 1);
573 isl_int_sub_ui(bmap->ineq[k][1+pos],
574 bmap->ineq[k][1+pos], 1);
575 } else if (tok->type == TOKEN_VALUE) {
579 tok2 = stream_next_token(s);
580 if (tok2 && tok2->type == TOKEN_IDENT) {
581 pos = vars_pos(*v, tok2->u.s, -1);
585 stream_error(s, tok2,
586 "unknown identifier");
592 stream_push_token(s, tok2);
594 isl_int_neg(tok->u.v, tok->u.v);
595 isl_int_add(bmap->ineq[k][1+pos],
596 bmap->ineq[k][1+pos], tok->u.v);
597 } else if (tok->type == TOKEN_LE) {
599 isl_seq_neg(bmap->ineq[k], bmap->ineq[k], 1+total);
600 } else if (tok->type == TOKEN_GE) {
603 } else if (tok->type == '=') {
605 stream_error(s, tok, "too many operators");
612 stream_push_token(s, tok);
619 stream_error(s, tok, "missing operator");
623 isl_basic_map_inequality_to_equality(bmap, k);
628 isl_basic_map_free(bmap);
632 static struct isl_basic_map *add_constraints(struct stream *s,
633 struct vars **v, struct isl_basic_map *bmap)
638 bmap = add_constraint(s, v, bmap);
641 tok = stream_next_token(s);
643 stream_error(s, NULL, "unexpected EOF");
646 if (tok->type != TOKEN_AND)
650 stream_push_token(s, tok);
656 isl_basic_map_free(bmap);
660 static struct isl_basic_map *basic_map_read(struct stream *s)
662 struct isl_basic_map *bmap = NULL;
664 struct vars *v = NULL;
668 tok = stream_next_token(s);
669 if (!tok || tok->type != '{') {
670 stream_error(s, tok, "expecting '{'");
672 stream_push_token(s, tok);
676 v = vars_new(s->ctx);
677 v = read_tuple(s, v);
681 tok = stream_next_token(s);
682 if (tok && tok->type == TOKEN_TO) {
684 v = read_tuple(s, v);
690 stream_push_token(s, tok);
694 bmap = isl_basic_map_alloc(s->ctx, 0, n1, n2, 0, 0,0);
697 tok = stream_next_token(s);
698 if (tok && tok->type == ':') {
700 bmap = add_constraints(s, &v, bmap);
701 tok = stream_next_token(s);
703 if (tok && tok->type == '}') {
706 stream_error(s, tok, "unexpected token");
715 isl_basic_map_free(bmap);
721 struct isl_basic_map *isl_basic_map_read_from_file_omega(
722 struct isl_ctx *ctx, FILE *input)
724 struct isl_basic_map *bmap;
725 struct stream *s = stream_new_file(ctx, input);
728 bmap = basic_map_read(s);
733 struct isl_basic_set *isl_basic_set_read_from_file_omega(
734 struct isl_ctx *ctx, FILE *input)
736 struct isl_basic_map *bmap;
737 bmap = isl_basic_map_read_from_file_omega(ctx, input);
740 isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
741 return (struct isl_basic_set *)bmap;
743 isl_basic_map_free(bmap);
747 struct isl_basic_map *isl_basic_map_read_from_str_omega(
748 struct isl_ctx *ctx, const char *str)
750 struct isl_basic_map *bmap;
751 struct stream *s = stream_new_str(ctx, str);
754 bmap = basic_map_read(s);
759 struct isl_basic_set *isl_basic_set_read_from_str_omega(
760 struct isl_ctx *ctx, const char *str)
762 struct isl_basic_map *bmap;
763 bmap = isl_basic_map_read_from_str_omega(ctx, str);
766 isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
767 return (struct isl_basic_set *)bmap;
769 isl_basic_map_free(bmap);