2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
5 * Use of this software is governed by the GNU LGPLv2.1 license
7 * Written by Sven Verdoolaege, K.U.Leuven, Departement
8 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
9 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
10 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
19 #include "isl_stream.h"
20 #include "isl_map_private.h"
25 struct variable *next;
34 static struct vars *vars_new(struct isl_ctx *ctx)
37 v = isl_alloc_type(ctx, struct vars);
46 static void variable_free(struct variable *var)
49 struct variable *next = var->next;
56 static void vars_free(struct vars *v)
64 static struct variable *variable_new(struct vars *v, const char *name, int len,
68 var = isl_alloc_type(v->ctx, struct variable);
71 var->name = strdup(name);
72 var->name[len] = '\0';
81 static int vars_pos(struct vars *v, const char *s, int len)
88 for (q = v->v; q; q = q->next) {
89 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
96 v->v = variable_new(v, s, len, v->n);
104 static struct vars *read_var_list(struct isl_stream *s, struct vars *v)
106 struct isl_token *tok;
108 while ((tok = isl_stream_next_token(s)) != NULL) {
112 if (tok->type != ISL_TOKEN_IDENT)
115 p = vars_pos(v, tok->u.s, -1);
119 isl_stream_error(s, tok, "expecting unique identifier");
123 tok = isl_stream_next_token(s);
124 if (!tok || tok->type != ',')
130 isl_stream_push_token(s, tok);
139 static struct vars *read_tuple(struct isl_stream *s, struct vars *v)
141 struct isl_token *tok;
143 tok = isl_stream_next_token(s);
144 if (!tok || tok->type != '[') {
145 isl_stream_error(s, tok, "expecting '['");
149 v = read_var_list(s, v);
150 tok = isl_stream_next_token(s);
151 if (!tok || tok->type != ']') {
152 isl_stream_error(s, tok, "expecting ']'");
165 static struct isl_basic_map *add_constraints(struct isl_stream *s,
166 struct vars **v, struct isl_basic_map *bmap);
168 static struct isl_basic_map *add_exists(struct isl_stream *s,
169 struct vars **v, struct isl_basic_map *bmap)
171 struct isl_token *tok;
178 tok = isl_stream_next_token(s);
181 if (tok->type == '(') {
185 isl_stream_push_token(s, tok);
186 *v = read_var_list(s, *v);
190 bmap = isl_basic_map_cow(bmap);
191 bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
193 total = isl_basic_map_total_dim(bmap);
194 for (i = 0; i < extra; ++i) {
196 if ((k = isl_basic_map_alloc_div(bmap)) < 0)
198 isl_seq_clr(bmap->div[k], 1+1+total);
202 if (isl_stream_eat(s, ':'))
204 bmap = add_constraints(s, v, bmap);
205 if (seen_paren && isl_stream_eat(s, ')'))
209 isl_basic_map_free(bmap);
213 static struct isl_basic_map *add_constraint(struct isl_stream *s,
214 struct vars **v, struct isl_basic_map *bmap)
216 unsigned total = isl_basic_map_total_dim(bmap);
221 struct isl_token *tok = NULL;
223 tok = isl_stream_next_token(s);
226 if (tok->type == ISL_TOKEN_EXISTS) {
228 return add_exists(s, v, bmap);
230 isl_stream_push_token(s, tok);
232 bmap = isl_basic_map_cow(bmap);
233 bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
234 k = isl_basic_map_alloc_inequality(bmap);
237 isl_seq_clr(bmap->ineq[k], 1+total);
240 tok = isl_stream_next_token(s);
242 isl_stream_error(s, NULL, "unexpected EOF");
245 if (tok->type == ISL_TOKEN_IDENT) {
247 int pos = vars_pos(*v, tok->u.s, -1);
251 isl_stream_error(s, tok, "unknown identifier");
255 isl_int_add_ui(bmap->ineq[k][1+pos],
256 bmap->ineq[k][1+pos], 1);
258 isl_int_sub_ui(bmap->ineq[k][1+pos],
259 bmap->ineq[k][1+pos], 1);
260 } else if (tok->type == ISL_TOKEN_VALUE) {
261 struct isl_token *tok2;
264 tok2 = isl_stream_next_token(s);
265 if (tok2 && tok2->type == ISL_TOKEN_IDENT) {
266 pos = vars_pos(*v, tok2->u.s, -1);
270 isl_stream_error(s, tok2,
271 "unknown identifier");
272 isl_token_free(tok2);
275 isl_token_free(tok2);
277 isl_stream_push_token(s, tok2);
279 isl_int_neg(tok->u.v, tok->u.v);
280 isl_int_add(bmap->ineq[k][1+pos],
281 bmap->ineq[k][1+pos], tok->u.v);
282 } else if (tok->type == '+') {
284 } else if (tok->type == ISL_TOKEN_LE) {
286 isl_seq_neg(bmap->ineq[k], bmap->ineq[k], 1+total);
287 } else if (tok->type == ISL_TOKEN_GE) {
290 } else if (tok->type == '=') {
292 isl_stream_error(s, tok, "too many operators");
299 isl_stream_push_token(s, tok);
306 isl_stream_error(s, tok, "missing operator");
310 isl_basic_map_inequality_to_equality(bmap, k);
315 isl_basic_map_free(bmap);
319 static struct isl_basic_map *add_constraints(struct isl_stream *s,
320 struct vars **v, struct isl_basic_map *bmap)
322 struct isl_token *tok;
325 bmap = add_constraint(s, v, bmap);
328 tok = isl_stream_next_token(s);
330 isl_stream_error(s, NULL, "unexpected EOF");
333 if (tok->type != ISL_TOKEN_AND)
337 isl_stream_push_token(s, tok);
343 isl_basic_map_free(bmap);
347 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
348 struct isl_stream *s, __isl_take isl_basic_map *bmap)
351 struct isl_token *tok;
361 nparam = isl_basic_map_dim(bmap, isl_dim_param);
362 dim = isl_basic_map_dim(bmap, isl_dim_out);
364 tok = isl_stream_next_token(s);
365 if (!tok || tok->type != ISL_TOKEN_VALUE) {
366 isl_stream_error(s, tok, "expecting coefficient");
368 isl_stream_push_token(s, tok);
371 if (!tok->on_new_line) {
372 isl_stream_error(s, tok, "coefficient should appear on new line");
373 isl_stream_push_token(s, tok);
377 type = isl_int_get_si(tok->u.v);
380 isl_assert(s->ctx, type == 0 || type == 1, goto error);
382 k = isl_basic_map_alloc_equality(bmap);
385 k = isl_basic_map_alloc_inequality(bmap);
391 for (j = 0; j < dim; ++j) {
392 tok = isl_stream_next_token(s);
393 if (!tok || tok->type != ISL_TOKEN_VALUE) {
394 isl_stream_error(s, tok, "expecting coefficient");
396 isl_stream_push_token(s, tok);
399 isl_int_set(c[1 + nparam + j], tok->u.v);
402 for (j = 0; j < nparam; ++j) {
403 tok = isl_stream_next_token(s);
404 if (!tok || tok->type != ISL_TOKEN_VALUE) {
405 isl_stream_error(s, tok, "expecting coefficient");
407 isl_stream_push_token(s, tok);
410 isl_int_set(c[1 + j], tok->u.v);
413 tok = isl_stream_next_token(s);
414 if (!tok || tok->type != ISL_TOKEN_VALUE) {
415 isl_stream_error(s, tok, "expecting coefficient");
417 isl_stream_push_token(s, tok);
420 isl_int_set(c[0], tok->u.v);
425 isl_basic_map_free(bmap);
429 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s,
433 struct isl_token *tok;
434 struct isl_token *tok2;
438 struct isl_basic_map *bmap = NULL;
443 tok = isl_stream_next_token(s);
445 isl_stream_error(s, NULL, "unexpected EOF");
448 tok2 = isl_stream_next_token(s);
451 isl_stream_error(s, NULL, "unexpected EOF");
454 n_row = isl_int_get_si(tok->u.v);
455 n_col = isl_int_get_si(tok2->u.v);
456 on_new_line = tok2->on_new_line;
457 isl_token_free(tok2);
459 isl_assert(s->ctx, !on_new_line, return NULL);
460 isl_assert(s->ctx, n_row >= 0, return NULL);
461 isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
462 dim = n_col - 2 - nparam;
463 bmap = isl_basic_map_alloc(s->ctx, nparam, 0, dim, 0, n_row, n_row);
467 for (i = 0; i < n_row; ++i)
468 bmap = basic_map_read_polylib_constraint(s, bmap);
470 bmap = isl_basic_map_simplify(bmap);
471 bmap = isl_basic_map_finalize(bmap);
475 static struct isl_map *map_read_polylib(struct isl_stream *s, int nparam)
477 struct isl_token *tok;
478 struct isl_token *tok2;
482 tok = isl_stream_next_token(s);
484 isl_stream_error(s, NULL, "unexpected EOF");
487 tok2 = isl_stream_next_token(s);
490 isl_stream_error(s, NULL, "unexpected EOF");
493 if (!tok2->on_new_line) {
494 isl_stream_push_token(s, tok2);
495 isl_stream_push_token(s, tok);
496 return isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
498 isl_stream_push_token(s, tok2);
499 n = isl_int_get_si(tok->u.v);
502 isl_assert(s->ctx, n >= 1, return NULL);
504 map = isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
506 for (i = 1; i < n; ++i)
507 map = isl_map_union(map,
508 isl_map_from_basic_map(basic_map_read_polylib(s, nparam)));
513 static struct isl_map *map_read(struct isl_stream *s, int nparam)
515 struct isl_basic_map *bmap = NULL;
516 struct isl_token *tok;
517 struct vars *v = NULL;
521 tok = isl_stream_next_token(s);
523 isl_stream_error(s, NULL, "unexpected EOF");
526 if (tok->type == ISL_TOKEN_VALUE) {
527 isl_stream_push_token(s, tok);
528 return map_read_polylib(s, nparam);
530 if (tok->type != '{') {
531 isl_stream_error(s, tok, "expecting '{'");
533 isl_stream_push_token(s, tok);
537 isl_assert(s->ctx, nparam == 0, goto error);
538 v = vars_new(s->ctx);
539 v = read_tuple(s, v);
543 tok = isl_stream_next_token(s);
544 if (tok && tok->type == ISL_TOKEN_TO) {
546 v = read_tuple(s, v);
552 isl_stream_push_token(s, tok);
556 bmap = isl_basic_map_alloc(s->ctx, 0, n1, n2, 0, 0,0);
559 tok = isl_stream_next_token(s);
560 if (tok && tok->type == ':') {
562 bmap = add_constraints(s, &v, bmap);
563 tok = isl_stream_next_token(s);
565 if (tok && tok->type == '}') {
568 isl_stream_error(s, tok, "unexpected isl_token");
575 bmap = isl_basic_map_simplify(bmap);
576 bmap = isl_basic_map_finalize(bmap);
577 return isl_map_from_basic_map(bmap);
579 isl_basic_map_free(bmap);
585 static struct isl_basic_map *basic_map_read(struct isl_stream *s, int nparam)
588 struct isl_basic_map *bmap;
590 map = map_read(s, nparam);
594 isl_assert(map->ctx, map->n <= 1, goto error);
597 bmap = isl_basic_map_empty_like_map(map);
599 bmap = isl_basic_map_copy(map->p[0]);
609 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
610 FILE *input, unsigned nparam, unsigned input_format)
612 struct isl_basic_map *bmap;
613 struct isl_stream *s = isl_stream_new_file(ctx, input);
616 bmap = basic_map_read(s, nparam);
621 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
622 FILE *input, unsigned nparam, unsigned input_format)
624 struct isl_basic_map *bmap;
625 bmap = isl_basic_map_read_from_file(ctx, input, nparam, input_format);
628 isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
629 return (struct isl_basic_set *)bmap;
631 isl_basic_map_free(bmap);
635 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
636 const char *str, unsigned nparam, unsigned input_format)
638 struct isl_basic_map *bmap;
639 struct isl_stream *s = isl_stream_new_str(ctx, str);
642 bmap = basic_map_read(s, nparam);
647 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
648 const char *str, unsigned nparam, unsigned input_format)
650 struct isl_basic_map *bmap;
651 bmap = isl_basic_map_read_from_str(ctx, str, nparam, input_format);
654 isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
655 return (struct isl_basic_set *)bmap;
657 isl_basic_map_free(bmap);
661 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
662 FILE *input, unsigned nparam, unsigned input_format)
665 struct isl_stream *s = isl_stream_new_file(ctx, input);
668 map = map_read(s, nparam);
673 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
674 FILE *input, unsigned nparam, unsigned input_format)
677 map = isl_map_read_from_file(ctx, input, nparam, input_format);
680 isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
681 return (struct isl_set *)map;
687 static char *next_line(FILE *input, char *line, unsigned len)
692 if (!(p = fgets(line, len, input)))
694 while (isspace(*p) && *p != '\n')
696 } while (*p == '#' || *p == '\n');
701 static struct isl_vec *isl_vec_read_from_file_polylib(struct isl_ctx *ctx,
704 struct isl_vec *vec = NULL;
713 isl_assert(ctx, next_line(input, line, sizeof(line)), return NULL);
714 isl_assert(ctx, sscanf(line, "%u", &size) == 1, return NULL);
716 vec = isl_vec_alloc(ctx, size);
718 p = next_line(input, line, sizeof(line));
719 isl_assert(ctx, p, goto error);
721 for (j = 0; j < size; ++j) {
722 n = sscanf(p, "%s%n", val, &offset);
723 isl_assert(ctx, n != 0, goto error);
724 isl_int_read(vec->el[j], val);
734 struct isl_vec *isl_vec_read_from_file(struct isl_ctx *ctx,
735 FILE *input, unsigned input_format)
737 if (input_format == ISL_FORMAT_POLYLIB)
738 return isl_vec_read_from_file_polylib(ctx, input);
740 isl_assert(ctx, 0, return NULL);