add isl_multi_union_pw_aff_zero_union_set
[isl.git] / isl_input.c
blob771d437a90a4323e07b3fe707f42020b6e371082
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 * Copyright 2012-2013 Ecole Normale Superieure
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, K.U.Leuven, Departement
9 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
10 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
11 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
12 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
15 #include <ctype.h>
16 #include <stdio.h>
17 #include <string.h>
18 #include <isl_ctx_private.h>
19 #include <isl_map_private.h>
20 #include <isl/set.h>
21 #include <isl_seq.h>
22 #include <isl_stream_private.h>
23 #include <isl/obj.h>
24 #include "isl_polynomial_private.h"
25 #include <isl/union_map.h>
26 #include <isl_mat_private.h>
27 #include <isl_aff_private.h>
28 #include <isl_vec_private.h>
29 #include <isl/list.h>
30 #include <isl_val_private.h>
32 struct variable {
33 char *name;
34 int pos;
35 struct variable *next;
38 struct vars {
39 struct isl_ctx *ctx;
40 int n;
41 struct variable *v;
44 static struct vars *vars_new(struct isl_ctx *ctx)
46 struct vars *v;
47 v = isl_alloc_type(ctx, struct vars);
48 if (!v)
49 return NULL;
50 v->ctx = ctx;
51 v->n = 0;
52 v->v = NULL;
53 return v;
56 static void variable_free(struct variable *var)
58 while (var) {
59 struct variable *next = var->next;
60 free(var->name);
61 free(var);
62 var = next;
66 static void vars_free(struct vars *v)
68 if (!v)
69 return;
70 variable_free(v->v);
71 free(v);
74 static void vars_drop(struct vars *v, int n)
76 struct variable *var;
78 if (!v || !v->v)
79 return;
81 v->n -= n;
83 var = v->v;
84 while (--n >= 0) {
85 struct variable *next = var->next;
86 free(var->name);
87 free(var);
88 var = next;
90 v->v = var;
93 static struct variable *variable_new(struct vars *v, const char *name, int len,
94 int pos)
96 struct variable *var;
97 var = isl_calloc_type(v->ctx, struct variable);
98 if (!var)
99 goto error;
100 var->name = strdup(name);
101 var->name[len] = '\0';
102 var->pos = pos;
103 var->next = v->v;
104 return var;
105 error:
106 variable_free(v->v);
107 return NULL;
110 static int vars_pos(struct vars *v, const char *s, int len)
112 int pos;
113 struct variable *q;
115 if (len == -1)
116 len = strlen(s);
117 for (q = v->v; q; q = q->next) {
118 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
119 break;
121 if (q)
122 pos = q->pos;
123 else {
124 pos = v->n;
125 v->v = variable_new(v, s, len, v->n);
126 if (!v->v)
127 return -1;
128 v->n++;
130 return pos;
133 static int vars_add_anon(struct vars *v)
135 v->v = variable_new(v, "", 0, v->n);
137 if (!v->v)
138 return -1;
139 v->n++;
141 return 0;
144 /* Obtain next token, with some preprocessing.
145 * In particular, evaluate expressions of the form x^y,
146 * with x and y values.
148 static struct isl_token *next_token(struct isl_stream *s)
150 struct isl_token *tok, *tok2;
152 tok = isl_stream_next_token(s);
153 if (!tok || tok->type != ISL_TOKEN_VALUE)
154 return tok;
155 if (!isl_stream_eat_if_available(s, '^'))
156 return tok;
157 tok2 = isl_stream_next_token(s);
158 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
159 isl_stream_error(s, tok2, "expecting constant value");
160 goto error;
163 isl_int_pow_ui(tok->u.v, tok->u.v, isl_int_get_ui(tok2->u.v));
165 isl_token_free(tok2);
166 return tok;
167 error:
168 isl_token_free(tok);
169 isl_token_free(tok2);
170 return NULL;
173 /* Read an isl_val from "s".
175 * The following token sequences are recognized
177 * "infty" -> infty
178 * "-" "infty" -> -infty
179 * "NaN" -> NaN
180 * n "/" d -> n/d
181 * v -> v
183 * where n, d and v are integer constants.
185 __isl_give isl_val *isl_stream_read_val(struct isl_stream *s)
187 struct isl_token *tok = NULL;
188 struct isl_token *tok2 = NULL;
189 isl_val *val;
191 tok = next_token(s);
192 if (!tok) {
193 isl_stream_error(s, NULL, "unexpected EOF");
194 goto error;
196 if (tok->type == ISL_TOKEN_INFTY) {
197 isl_token_free(tok);
198 return isl_val_infty(s->ctx);
200 if (tok->type == '-' &&
201 isl_stream_eat_if_available(s, ISL_TOKEN_INFTY)) {
202 isl_token_free(tok);
203 return isl_val_neginfty(s->ctx);
205 if (tok->type == ISL_TOKEN_NAN) {
206 isl_token_free(tok);
207 return isl_val_nan(s->ctx);
209 if (tok->type != ISL_TOKEN_VALUE) {
210 isl_stream_error(s, tok, "expecting value");
211 goto error;
214 if (isl_stream_eat_if_available(s, '/')) {
215 tok2 = next_token(s);
216 if (!tok2) {
217 isl_stream_error(s, NULL, "unexpected EOF");
218 goto error;
220 if (tok2->type != ISL_TOKEN_VALUE) {
221 isl_stream_error(s, tok2, "expecting value");
222 goto error;
224 val = isl_val_rat_from_isl_int(s->ctx, tok->u.v, tok2->u.v);
225 val = isl_val_normalize(val);
226 } else {
227 val = isl_val_int_from_isl_int(s->ctx, tok->u.v);
230 isl_token_free(tok);
231 isl_token_free(tok2);
232 return val;
233 error:
234 isl_token_free(tok);
235 isl_token_free(tok2);
236 return NULL;
239 /* Read an isl_val from "str".
241 struct isl_val *isl_val_read_from_str(struct isl_ctx *ctx,
242 const char *str)
244 isl_val *val;
245 struct isl_stream *s = isl_stream_new_str(ctx, str);
246 if (!s)
247 return NULL;
248 val = isl_stream_read_val(s);
249 isl_stream_free(s);
250 return val;
253 static int accept_cst_factor(struct isl_stream *s, isl_int *f)
255 struct isl_token *tok;
257 tok = next_token(s);
258 if (!tok || tok->type != ISL_TOKEN_VALUE) {
259 isl_stream_error(s, tok, "expecting constant value");
260 goto error;
263 isl_int_mul(*f, *f, tok->u.v);
265 isl_token_free(tok);
267 if (isl_stream_eat_if_available(s, '*'))
268 return accept_cst_factor(s, f);
270 return 0;
271 error:
272 isl_token_free(tok);
273 return -1;
276 /* Given an affine expression aff, return an affine expression
277 * for aff % d, with d the next token on the stream, which is
278 * assumed to be a constant.
280 * We introduce an integer division q = [aff/d] and the result
281 * is set to aff - d q.
283 static __isl_give isl_pw_aff *affine_mod(struct isl_stream *s,
284 struct vars *v, __isl_take isl_pw_aff *aff)
286 struct isl_token *tok;
287 isl_pw_aff *q;
289 tok = next_token(s);
290 if (!tok || tok->type != ISL_TOKEN_VALUE) {
291 isl_stream_error(s, tok, "expecting constant value");
292 goto error;
295 q = isl_pw_aff_copy(aff);
296 q = isl_pw_aff_scale_down(q, tok->u.v);
297 q = isl_pw_aff_floor(q);
298 q = isl_pw_aff_scale(q, tok->u.v);
300 aff = isl_pw_aff_sub(aff, q);
302 isl_token_free(tok);
303 return aff;
304 error:
305 isl_pw_aff_free(aff);
306 isl_token_free(tok);
307 return NULL;
310 static __isl_give isl_pw_aff *accept_affine(struct isl_stream *s,
311 __isl_take isl_space *space, struct vars *v);
312 static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s,
313 __isl_take isl_space *dim, struct vars *v);
315 static __isl_give isl_pw_aff *accept_minmax(struct isl_stream *s,
316 __isl_take isl_space *dim, struct vars *v)
318 struct isl_token *tok;
319 isl_pw_aff_list *list = NULL;
320 int min;
322 tok = isl_stream_next_token(s);
323 if (!tok)
324 goto error;
325 min = tok->type == ISL_TOKEN_MIN;
326 isl_token_free(tok);
328 if (isl_stream_eat(s, '('))
329 goto error;
331 list = accept_affine_list(s, isl_space_copy(dim), v);
332 if (!list)
333 goto error;
335 if (isl_stream_eat(s, ')'))
336 goto error;
338 isl_space_free(dim);
339 return min ? isl_pw_aff_list_min(list) : isl_pw_aff_list_max(list);
340 error:
341 isl_space_free(dim);
342 isl_pw_aff_list_free(list);
343 return NULL;
346 /* Is "tok" the start of an integer division?
348 static int is_start_of_div(struct isl_token *tok)
350 if (!tok)
351 return 0;
352 if (tok->type == '[')
353 return 1;
354 if (tok->type == ISL_TOKEN_FLOOR)
355 return 1;
356 if (tok->type == ISL_TOKEN_CEIL)
357 return 1;
358 if (tok->type == ISL_TOKEN_FLOORD)
359 return 1;
360 if (tok->type == ISL_TOKEN_CEILD)
361 return 1;
362 return 0;
365 /* Read an integer division from "s" and return it as an isl_pw_aff.
367 * The integer division can be of the form
369 * [<affine expression>]
370 * floor(<affine expression>)
371 * ceil(<affine expression>)
372 * floord(<affine expression>,<denominator>)
373 * ceild(<affine expression>,<denominator>)
375 static __isl_give isl_pw_aff *accept_div(struct isl_stream *s,
376 __isl_take isl_space *dim, struct vars *v)
378 struct isl_token *tok;
379 int f = 0;
380 int c = 0;
381 int extra = 0;
382 isl_pw_aff *pwaff = NULL;
384 if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOORD))
385 extra = f = 1;
386 else if (isl_stream_eat_if_available(s, ISL_TOKEN_CEILD))
387 extra = c = 1;
388 else if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOOR))
389 f = 1;
390 else if (isl_stream_eat_if_available(s, ISL_TOKEN_CEIL))
391 c = 1;
392 if (f || c) {
393 if (isl_stream_eat(s, '('))
394 goto error;
395 } else {
396 if (isl_stream_eat(s, '['))
397 goto error;
400 pwaff = accept_affine(s, isl_space_copy(dim), v);
402 if (extra) {
403 if (isl_stream_eat(s, ','))
404 goto error;
406 tok = next_token(s);
407 if (!tok)
408 goto error;
409 if (tok->type != ISL_TOKEN_VALUE) {
410 isl_stream_error(s, tok, "expected denominator");
411 isl_stream_push_token(s, tok);
412 goto error;
414 isl_pw_aff_scale_down(pwaff, tok->u.v);
415 isl_token_free(tok);
418 if (c)
419 pwaff = isl_pw_aff_ceil(pwaff);
420 else
421 pwaff = isl_pw_aff_floor(pwaff);
423 if (f || c) {
424 if (isl_stream_eat(s, ')'))
425 goto error;
426 } else {
427 if (isl_stream_eat(s, ']'))
428 goto error;
431 isl_space_free(dim);
432 return pwaff;
433 error:
434 isl_space_free(dim);
435 isl_pw_aff_free(pwaff);
436 return NULL;
439 static __isl_give isl_pw_aff *accept_affine_factor(struct isl_stream *s,
440 __isl_take isl_space *dim, struct vars *v)
442 struct isl_token *tok = NULL;
443 isl_pw_aff *res = NULL;
445 tok = next_token(s);
446 if (!tok) {
447 isl_stream_error(s, NULL, "unexpected EOF");
448 goto error;
451 if (tok->type == ISL_TOKEN_AFF) {
452 res = isl_pw_aff_copy(tok->u.pwaff);
453 isl_token_free(tok);
454 } else if (tok->type == ISL_TOKEN_IDENT) {
455 int n = v->n;
456 int pos = vars_pos(v, tok->u.s, -1);
457 isl_aff *aff;
459 if (pos < 0)
460 goto error;
461 if (pos >= n) {
462 vars_drop(v, v->n - n);
463 isl_stream_error(s, tok, "unknown identifier");
464 goto error;
467 aff = isl_aff_zero_on_domain(isl_local_space_from_space(isl_space_copy(dim)));
468 if (!aff)
469 goto error;
470 isl_int_set_si(aff->v->el[2 + pos], 1);
471 res = isl_pw_aff_from_aff(aff);
472 isl_token_free(tok);
473 } else if (tok->type == ISL_TOKEN_VALUE) {
474 if (isl_stream_eat_if_available(s, '*')) {
475 res = accept_affine_factor(s, isl_space_copy(dim), v);
476 res = isl_pw_aff_scale(res, tok->u.v);
477 } else {
478 isl_local_space *ls;
479 isl_aff *aff;
480 ls = isl_local_space_from_space(isl_space_copy(dim));
481 aff = isl_aff_zero_on_domain(ls);
482 aff = isl_aff_add_constant(aff, tok->u.v);
483 res = isl_pw_aff_from_aff(aff);
485 isl_token_free(tok);
486 } else if (tok->type == '(') {
487 isl_token_free(tok);
488 tok = NULL;
489 res = accept_affine(s, isl_space_copy(dim), v);
490 if (!res)
491 goto error;
492 if (isl_stream_eat(s, ')'))
493 goto error;
494 } else if (is_start_of_div(tok)) {
495 isl_stream_push_token(s, tok);
496 tok = NULL;
497 res = accept_div(s, isl_space_copy(dim), v);
498 } else if (tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX) {
499 isl_stream_push_token(s, tok);
500 tok = NULL;
501 res = accept_minmax(s, isl_space_copy(dim), v);
502 } else {
503 isl_stream_error(s, tok, "expecting factor");
504 goto error;
506 if (isl_stream_eat_if_available(s, '%') ||
507 isl_stream_eat_if_available(s, ISL_TOKEN_MOD)) {
508 isl_space_free(dim);
509 return affine_mod(s, v, res);
511 if (isl_stream_eat_if_available(s, '*')) {
512 isl_int f;
513 isl_int_init(f);
514 isl_int_set_si(f, 1);
515 if (accept_cst_factor(s, &f) < 0) {
516 isl_int_clear(f);
517 goto error2;
519 res = isl_pw_aff_scale(res, f);
520 isl_int_clear(f);
522 if (isl_stream_eat_if_available(s, '/')) {
523 isl_int f;
524 isl_int_init(f);
525 isl_int_set_si(f, 1);
526 if (accept_cst_factor(s, &f) < 0) {
527 isl_int_clear(f);
528 goto error2;
530 res = isl_pw_aff_scale_down(res, f);
531 isl_int_clear(f);
534 isl_space_free(dim);
535 return res;
536 error:
537 isl_token_free(tok);
538 error2:
539 isl_pw_aff_free(res);
540 isl_space_free(dim);
541 return NULL;
544 static __isl_give isl_pw_aff *add_cst(__isl_take isl_pw_aff *pwaff, isl_int v)
546 isl_aff *aff;
547 isl_space *space;
549 space = isl_pw_aff_get_domain_space(pwaff);
550 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
551 aff = isl_aff_add_constant(aff, v);
553 return isl_pw_aff_add(pwaff, isl_pw_aff_from_aff(aff));
556 /* Return a piecewise affine expression defined on the specified domain
557 * that represents NaN.
559 static __isl_give isl_pw_aff *nan_on_domain(__isl_keep isl_space *space)
561 isl_local_space *ls;
563 ls = isl_local_space_from_space(isl_space_copy(space));
564 return isl_pw_aff_nan_on_domain(ls);
567 static __isl_give isl_pw_aff *accept_affine(struct isl_stream *s,
568 __isl_take isl_space *space, struct vars *v)
570 struct isl_token *tok = NULL;
571 isl_local_space *ls;
572 isl_pw_aff *res;
573 int sign = 1;
575 ls = isl_local_space_from_space(isl_space_copy(space));
576 res = isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls));
577 if (!res)
578 goto error;
580 for (;;) {
581 tok = next_token(s);
582 if (!tok) {
583 isl_stream_error(s, NULL, "unexpected EOF");
584 goto error;
586 if (tok->type == '-') {
587 sign = -sign;
588 isl_token_free(tok);
589 continue;
591 if (tok->type == '(' || is_start_of_div(tok) ||
592 tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX ||
593 tok->type == ISL_TOKEN_IDENT ||
594 tok->type == ISL_TOKEN_AFF) {
595 isl_pw_aff *term;
596 isl_stream_push_token(s, tok);
597 tok = NULL;
598 term = accept_affine_factor(s,
599 isl_space_copy(space), v);
600 if (sign < 0)
601 res = isl_pw_aff_sub(res, term);
602 else
603 res = isl_pw_aff_add(res, term);
604 if (!res)
605 goto error;
606 sign = 1;
607 } else if (tok->type == ISL_TOKEN_VALUE) {
608 if (sign < 0)
609 isl_int_neg(tok->u.v, tok->u.v);
610 if (isl_stream_eat_if_available(s, '*') ||
611 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
612 isl_pw_aff *term;
613 term = accept_affine_factor(s,
614 isl_space_copy(space), v);
615 term = isl_pw_aff_scale(term, tok->u.v);
616 res = isl_pw_aff_add(res, term);
617 if (!res)
618 goto error;
619 } else {
620 res = add_cst(res, tok->u.v);
622 sign = 1;
623 } else if (tok->type == ISL_TOKEN_NAN) {
624 res = isl_pw_aff_add(res, nan_on_domain(space));
625 } else {
626 isl_stream_error(s, tok, "unexpected isl_token");
627 isl_stream_push_token(s, tok);
628 isl_pw_aff_free(res);
629 isl_space_free(space);
630 return NULL;
632 isl_token_free(tok);
634 tok = next_token(s);
635 if (tok && tok->type == '-') {
636 sign = -sign;
637 isl_token_free(tok);
638 } else if (tok && tok->type == '+') {
639 /* nothing */
640 isl_token_free(tok);
641 } else if (tok && tok->type == ISL_TOKEN_VALUE &&
642 isl_int_is_neg(tok->u.v)) {
643 isl_stream_push_token(s, tok);
644 } else {
645 if (tok)
646 isl_stream_push_token(s, tok);
647 break;
651 isl_space_free(space);
652 return res;
653 error:
654 isl_space_free(space);
655 isl_token_free(tok);
656 isl_pw_aff_free(res);
657 return NULL;
660 static int is_comparator(struct isl_token *tok)
662 if (!tok)
663 return 0;
665 switch (tok->type) {
666 case ISL_TOKEN_LT:
667 case ISL_TOKEN_GT:
668 case ISL_TOKEN_LE:
669 case ISL_TOKEN_GE:
670 case ISL_TOKEN_NE:
671 case '=':
672 return 1;
673 default:
674 return 0;
678 static __isl_give isl_map *read_formula(struct isl_stream *s,
679 struct vars *v, __isl_take isl_map *map, int rational);
680 static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s,
681 __isl_take isl_space *dim, struct vars *v, int rational);
683 /* Accept a ternary operator, given the first argument.
685 static __isl_give isl_pw_aff *accept_ternary(struct isl_stream *s,
686 __isl_take isl_map *cond, struct vars *v, int rational)
688 isl_space *dim;
689 isl_pw_aff *pwaff1 = NULL, *pwaff2 = NULL, *pa_cond;
691 if (!cond)
692 return NULL;
694 if (isl_stream_eat(s, '?'))
695 goto error;
697 dim = isl_space_wrap(isl_map_get_space(cond));
698 pwaff1 = accept_extended_affine(s, dim, v, rational);
699 if (!pwaff1)
700 goto error;
702 if (isl_stream_eat(s, ':'))
703 goto error;
705 dim = isl_pw_aff_get_domain_space(pwaff1);
706 pwaff2 = accept_extended_affine(s, dim, v, rational);
707 if (!pwaff1)
708 goto error;
710 pa_cond = isl_set_indicator_function(isl_map_wrap(cond));
711 return isl_pw_aff_cond(pa_cond, pwaff1, pwaff2);
712 error:
713 isl_map_free(cond);
714 isl_pw_aff_free(pwaff1);
715 isl_pw_aff_free(pwaff2);
716 return NULL;
719 /* Set *line and *col to those of the next token, if any.
721 static void set_current_line_col(struct isl_stream *s, int *line, int *col)
723 struct isl_token *tok;
725 tok = isl_stream_next_token(s);
726 if (!tok)
727 return;
729 *line = tok->line;
730 *col = tok->col;
731 isl_stream_push_token(s, tok);
734 /* Push a token encapsulating "pa" onto "s", with the given
735 * line and column.
737 static int push_aff(struct isl_stream *s, int line, int col,
738 __isl_take isl_pw_aff *pa)
740 struct isl_token *tok;
742 tok = isl_token_new(s->ctx, line, col, 0);
743 if (!tok)
744 goto error;
745 tok->type = ISL_TOKEN_AFF;
746 tok->u.pwaff = pa;
747 isl_stream_push_token(s, tok);
749 return 0;
750 error:
751 isl_pw_aff_free(pa);
752 return -1;
755 /* Accept an affine expression that may involve ternary operators.
756 * We first read an affine expression.
757 * If it is not followed by a comparison operator, we simply return it.
758 * Otherwise, we assume the affine expression is part of the first
759 * argument of a ternary operator and try to parse that.
761 static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s,
762 __isl_take isl_space *dim, struct vars *v, int rational)
764 isl_space *space;
765 isl_map *cond;
766 isl_pw_aff *pwaff;
767 struct isl_token *tok;
768 int line = -1, col = -1;
769 int is_comp;
771 set_current_line_col(s, &line, &col);
773 pwaff = accept_affine(s, dim, v);
774 if (rational)
775 pwaff = isl_pw_aff_set_rational(pwaff);
776 if (!pwaff)
777 return NULL;
779 tok = isl_stream_next_token(s);
780 if (!tok)
781 return isl_pw_aff_free(pwaff);
783 is_comp = is_comparator(tok);
784 isl_stream_push_token(s, tok);
785 if (!is_comp)
786 return pwaff;
788 space = isl_pw_aff_get_domain_space(pwaff);
789 cond = isl_map_universe(isl_space_unwrap(space));
791 if (push_aff(s, line, col, pwaff) < 0)
792 cond = isl_map_free(cond);
793 if (!cond)
794 return NULL;
796 cond = read_formula(s, v, cond, rational);
798 return accept_ternary(s, cond, v, rational);
801 static __isl_give isl_map *read_var_def(struct isl_stream *s,
802 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
803 int rational)
805 isl_pw_aff *def;
806 int pos;
807 isl_map *def_map;
809 if (type == isl_dim_param)
810 pos = isl_map_dim(map, isl_dim_param);
811 else {
812 pos = isl_map_dim(map, isl_dim_in);
813 if (type == isl_dim_out)
814 pos += isl_map_dim(map, isl_dim_out);
815 type = isl_dim_in;
817 --pos;
819 def = accept_extended_affine(s, isl_space_wrap(isl_map_get_space(map)),
820 v, rational);
821 def_map = isl_map_from_pw_aff(def);
822 def_map = isl_map_equate(def_map, type, pos, isl_dim_out, 0);
823 def_map = isl_set_unwrap(isl_map_domain(def_map));
825 map = isl_map_intersect(map, def_map);
827 return map;
830 static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s,
831 __isl_take isl_space *dim, struct vars *v)
833 isl_pw_aff *pwaff;
834 isl_pw_aff_list *list;
835 struct isl_token *tok = NULL;
837 pwaff = accept_affine(s, isl_space_copy(dim), v);
838 list = isl_pw_aff_list_from_pw_aff(pwaff);
839 if (!list)
840 goto error;
842 for (;;) {
843 tok = isl_stream_next_token(s);
844 if (!tok) {
845 isl_stream_error(s, NULL, "unexpected EOF");
846 goto error;
848 if (tok->type != ',') {
849 isl_stream_push_token(s, tok);
850 break;
852 isl_token_free(tok);
854 pwaff = accept_affine(s, isl_space_copy(dim), v);
855 list = isl_pw_aff_list_concat(list,
856 isl_pw_aff_list_from_pw_aff(pwaff));
857 if (!list)
858 goto error;
861 isl_space_free(dim);
862 return list;
863 error:
864 isl_space_free(dim);
865 isl_pw_aff_list_free(list);
866 return NULL;
869 static __isl_give isl_map *read_defined_var_list(struct isl_stream *s,
870 struct vars *v, __isl_take isl_map *map, int rational)
872 struct isl_token *tok;
874 while ((tok = isl_stream_next_token(s)) != NULL) {
875 int p;
876 int n = v->n;
878 if (tok->type != ISL_TOKEN_IDENT)
879 break;
881 p = vars_pos(v, tok->u.s, -1);
882 if (p < 0)
883 goto error;
884 if (p < n) {
885 isl_stream_error(s, tok, "expecting unique identifier");
886 goto error;
889 map = isl_map_add_dims(map, isl_dim_out, 1);
891 isl_token_free(tok);
892 tok = isl_stream_next_token(s);
893 if (tok && tok->type == '=') {
894 isl_token_free(tok);
895 map = read_var_def(s, map, isl_dim_out, v, rational);
896 tok = isl_stream_next_token(s);
899 if (!tok || tok->type != ',')
900 break;
902 isl_token_free(tok);
904 if (tok)
905 isl_stream_push_token(s, tok);
907 return map;
908 error:
909 isl_token_free(tok);
910 isl_map_free(map);
911 return NULL;
914 static int next_is_tuple(struct isl_stream *s)
916 struct isl_token *tok;
917 int is_tuple;
919 tok = isl_stream_next_token(s);
920 if (!tok)
921 return 0;
922 if (tok->type == '[') {
923 isl_stream_push_token(s, tok);
924 return 1;
926 if (tok->type != ISL_TOKEN_IDENT && !tok->is_keyword) {
927 isl_stream_push_token(s, tok);
928 return 0;
931 is_tuple = isl_stream_next_token_is(s, '[');
933 isl_stream_push_token(s, tok);
935 return is_tuple;
938 /* Is "pa" an expression in term of earlier dimensions?
939 * The alternative is that the dimension is defined to be equal to itself,
940 * meaning that it has a universe domain and an expression that depends
941 * on itself. "i" is the position of the expression in a sequence
942 * of "n" expressions. The final dimensions of "pa" correspond to
943 * these "n" expressions.
945 static int pw_aff_is_expr(__isl_keep isl_pw_aff *pa, int i, int n)
947 isl_aff *aff;
949 if (!pa)
950 return -1;
951 if (pa->n != 1)
952 return 1;
953 if (!isl_set_plain_is_universe(pa->p[0].set))
954 return 1;
956 aff = pa->p[0].aff;
957 if (isl_int_is_zero(aff->v->el[aff->v->size - n + i]))
958 return 1;
959 return 0;
962 /* Does the tuple contain any dimensions that are defined
963 * in terms of earlier dimensions?
965 static int tuple_has_expr(__isl_keep isl_multi_pw_aff *tuple)
967 int i, n;
968 int has_expr = 0;
969 isl_pw_aff *pa;
971 if (!tuple)
972 return -1;
973 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
974 for (i = 0; i < n; ++i) {
975 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
976 has_expr = pw_aff_is_expr(pa, i, n);
977 isl_pw_aff_free(pa);
978 if (has_expr < 0 || has_expr)
979 break;
982 return has_expr;
985 /* Set the name of dimension "pos" in "space" to "name".
986 * During printing, we add primes if the same name appears more than once
987 * to distinguish the occurrences. Here, we remove those primes from "name"
988 * before setting the name of the dimension.
990 static __isl_give isl_space *space_set_dim_name(__isl_take isl_space *space,
991 int pos, char *name)
993 char *prime;
995 if (!name)
996 return space;
998 prime = strchr(name, '\'');
999 if (prime)
1000 *prime = '\0';
1001 space = isl_space_set_dim_name(space, isl_dim_out, pos, name);
1002 if (prime)
1003 *prime = '\'';
1005 return space;
1008 /* Accept a piecewise affine expression.
1010 * At the outer level, the piecewise affine expression may be of the form
1012 * aff1 : condition1; aff2 : conditions2; ...
1014 * or simply
1016 * aff
1018 * each of the affine expressions may in turn include ternary operators.
1020 * There may be parentheses around some subexpression of "aff1"
1021 * around "aff1" itself, around "aff1 : condition1" and/or
1022 * around the entire piecewise affine expression.
1023 * We therefore remove the opening parenthesis (if any) from the stream
1024 * in case the closing parenthesis follows the colon, but if the closing
1025 * parenthesis is the first thing in the stream after the parsed affine
1026 * expression, we push the parsed expression onto the stream and parse
1027 * again in case the parentheses enclose some subexpression of "aff1".
1029 static __isl_give isl_pw_aff *accept_piecewise_affine(struct isl_stream *s,
1030 __isl_take isl_space *space, struct vars *v, int rational)
1032 isl_pw_aff *res;
1033 isl_space *res_space;
1035 res_space = isl_space_from_domain(isl_space_copy(space));
1036 res_space = isl_space_add_dims(res_space, isl_dim_out, 1);
1037 res = isl_pw_aff_empty(res_space);
1038 do {
1039 isl_pw_aff *pa;
1040 int seen_paren;
1041 int line = -1, col = -1;
1043 set_current_line_col(s, &line, &col);
1044 seen_paren = isl_stream_eat_if_available(s, '(');
1045 if (seen_paren)
1046 pa = accept_piecewise_affine(s, isl_space_copy(space),
1047 v, rational);
1048 else
1049 pa = accept_extended_affine(s, isl_space_copy(space),
1050 v, rational);
1051 if (seen_paren && isl_stream_eat_if_available(s, ')')) {
1052 seen_paren = 0;
1053 if (push_aff(s, line, col, pa) < 0)
1054 goto error;
1055 pa = accept_extended_affine(s, isl_space_copy(space),
1056 v, rational);
1058 if (isl_stream_eat_if_available(s, ':')) {
1059 isl_space *dom_space;
1060 isl_set *dom;
1062 dom_space = isl_pw_aff_get_domain_space(pa);
1063 dom = isl_set_universe(dom_space);
1064 dom = read_formula(s, v, dom, rational);
1065 pa = isl_pw_aff_intersect_domain(pa, dom);
1068 res = isl_pw_aff_union_add(res, pa);
1070 if (seen_paren && isl_stream_eat(s, ')'))
1071 goto error;
1072 } while (isl_stream_eat_if_available(s, ';'));
1074 isl_space_free(space);
1076 return res;
1077 error:
1078 isl_space_free(space);
1079 return isl_pw_aff_free(res);
1082 /* Read an affine expression from "s" for use in read_tuple.
1084 * accept_extended_affine requires a wrapped space as input.
1085 * read_tuple on the other hand expects each isl_pw_aff
1086 * to have an anonymous space. We therefore adjust the space
1087 * of the isl_pw_aff before returning it.
1089 static __isl_give isl_pw_aff *read_tuple_var_def(struct isl_stream *s,
1090 struct vars *v, int rational)
1092 isl_space *space;
1093 isl_pw_aff *def;
1095 space = isl_space_wrap(isl_space_alloc(s->ctx, 0, v->n, 0));
1097 def = accept_piecewise_affine(s, space, v, rational);
1099 space = isl_space_set_alloc(s->ctx, 0, v->n);
1100 def = isl_pw_aff_reset_domain_space(def, space);
1102 return def;
1105 /* Read a list of tuple elements by calling "read_el" on each of them and
1106 * return a space with the same number of set dimensions derived from
1107 * the parameter space "space" and possibly updated by "read_el".
1108 * The elements in the list are separated by either "," or "][".
1109 * If "comma" is set then only "," is allowed.
1111 static __isl_give isl_space *read_tuple_list(struct isl_stream *s,
1112 struct vars *v, __isl_take isl_space *space, int rational, int comma,
1113 __isl_give isl_space *(*read_el)(struct isl_stream *s, struct vars *v,
1114 __isl_take isl_space *space, int rational, void *user),
1115 void *user)
1117 if (!space)
1118 return NULL;
1120 space = isl_space_set_from_params(space);
1122 if (isl_stream_next_token_is(s, ']'))
1123 return space;
1125 for (;;) {
1126 struct isl_token *tok;
1128 space = isl_space_add_dims(space, isl_dim_set, 1);
1130 space = read_el(s, v, space, rational, user);
1131 if (!space)
1132 return NULL;
1134 tok = isl_stream_next_token(s);
1135 if (!comma && tok && tok->type == ']' &&
1136 isl_stream_next_token_is(s, '[')) {
1137 isl_token_free(tok);
1138 tok = isl_stream_next_token(s);
1139 } else if (!tok || tok->type != ',') {
1140 if (tok)
1141 isl_stream_push_token(s, tok);
1142 break;
1145 isl_token_free(tok);
1148 return space;
1151 /* Read a tuple space from "s" derived from the parameter space "space".
1152 * Call "read_el" on each element in the tuples.
1154 static __isl_give isl_space *read_tuple_space(struct isl_stream *s,
1155 struct vars *v, __isl_take isl_space *space, int rational, int comma,
1156 __isl_give isl_space *(*read_el)(struct isl_stream *s, struct vars *v,
1157 __isl_take isl_space *space, int rational, void *user),
1158 void *user)
1160 struct isl_token *tok;
1161 char *name = NULL;
1162 isl_space *res = NULL;
1164 tok = isl_stream_next_token(s);
1165 if (!tok)
1166 goto error;
1167 if (tok->type == ISL_TOKEN_IDENT || tok->is_keyword) {
1168 name = strdup(tok->u.s);
1169 isl_token_free(tok);
1170 if (!name)
1171 goto error;
1172 } else
1173 isl_stream_push_token(s, tok);
1174 if (isl_stream_eat(s, '['))
1175 goto error;
1176 if (next_is_tuple(s)) {
1177 isl_space *out;
1178 res = read_tuple_space(s, v, isl_space_copy(space),
1179 rational, comma, read_el, user);
1180 if (isl_stream_eat(s, ISL_TOKEN_TO))
1181 goto error;
1182 out = read_tuple_space(s, v, isl_space_copy(space),
1183 rational, comma, read_el, user);
1184 res = isl_space_range_product(res, out);
1185 } else
1186 res = read_tuple_list(s, v, isl_space_copy(space),
1187 rational, comma, read_el, user);
1188 if (isl_stream_eat(s, ']'))
1189 goto error;
1191 if (name) {
1192 res = isl_space_set_tuple_name(res, isl_dim_set, name);
1193 free(name);
1196 isl_space_free(space);
1197 return res;
1198 error:
1199 free(name);
1200 isl_space_free(res);
1201 isl_space_free(space);
1202 return NULL;
1205 /* Construct an isl_pw_aff defined on a space with v->n variables
1206 * that is equal to the last of those variables.
1208 static __isl_give isl_pw_aff *identity_tuple_el(struct vars *v)
1210 isl_space *space;
1211 isl_aff *aff;
1213 space = isl_space_set_alloc(v->ctx, 0, v->n);
1214 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1215 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, v->n - 1, 1);
1216 return isl_pw_aff_from_aff(aff);
1219 /* This function is called for each element in a tuple inside read_tuple.
1220 * Add a new variable to "v" and construct a corresponding isl_pw_aff defined
1221 * over a space containing all variables in "v" defined so far.
1222 * The isl_pw_aff expresses the new variable in terms of earlier variables
1223 * if a definition is provided. Otherwise, it is represented as being
1224 * equal to itself.
1225 * Add the isl_pw_aff to *list.
1226 * If the new variable was named, then adjust "space" accordingly and
1227 * return the updated space.
1229 static __isl_give isl_space *read_tuple_pw_aff_el(struct isl_stream *s,
1230 struct vars *v, __isl_take isl_space *space, int rational, void *user)
1232 isl_pw_aff_list **list = (isl_pw_aff_list **) user;
1233 isl_pw_aff *pa;
1234 struct isl_token *tok;
1235 int new_name = 0;
1237 tok = next_token(s);
1238 if (!tok) {
1239 isl_stream_error(s, NULL, "unexpected EOF");
1240 return isl_space_free(space);
1243 if (tok->type == ISL_TOKEN_IDENT) {
1244 int n = v->n;
1245 int p = vars_pos(v, tok->u.s, -1);
1246 if (p < 0)
1247 goto error;
1248 new_name = p >= n;
1251 if (tok->type == '*') {
1252 if (vars_add_anon(v) < 0)
1253 goto error;
1254 isl_token_free(tok);
1255 pa = identity_tuple_el(v);
1256 } else if (new_name) {
1257 int pos = isl_space_dim(space, isl_dim_out) - 1;
1258 space = space_set_dim_name(space, pos, v->v->name);
1259 isl_token_free(tok);
1260 if (isl_stream_eat_if_available(s, '='))
1261 pa = read_tuple_var_def(s, v, rational);
1262 else
1263 pa = identity_tuple_el(v);
1264 } else {
1265 isl_stream_push_token(s, tok);
1266 tok = NULL;
1267 if (vars_add_anon(v) < 0)
1268 goto error;
1269 pa = read_tuple_var_def(s, v, rational);
1272 *list = isl_pw_aff_list_add(*list, pa);
1273 if (!*list)
1274 return isl_space_free(space);
1276 return space;
1277 error:
1278 isl_token_free(tok);
1279 return isl_space_free(space);
1282 /* Read a tuple and represent it as an isl_multi_pw_aff.
1283 * The range space of the isl_multi_pw_aff is the space of the tuple.
1284 * The domain space is an anonymous space
1285 * with a dimension for each variable in the set of variables in "v",
1286 * including the variables in the range.
1287 * If a given dimension is not defined in terms of earlier dimensions in
1288 * the input, then the corresponding isl_pw_aff is set equal to one time
1289 * the variable corresponding to the dimension being defined.
1291 * The elements in the tuple are collected in a list by read_tuple_pw_aff_el.
1292 * Each element in this list is defined over a space representing
1293 * the variables defined so far. We need to adjust the earlier
1294 * elements to have as many variables in the domain as the final
1295 * element in the list.
1297 static __isl_give isl_multi_pw_aff *read_tuple(struct isl_stream *s,
1298 struct vars *v, int rational, int comma)
1300 int i, n;
1301 isl_space *space;
1302 isl_pw_aff_list *list;
1304 space = isl_space_params_alloc(v->ctx, 0);
1305 list = isl_pw_aff_list_alloc(s->ctx, 0);
1306 space = read_tuple_space(s, v, space, rational, comma,
1307 &read_tuple_pw_aff_el, &list);
1308 n = isl_space_dim(space, isl_dim_set);
1309 for (i = 0; i + 1 < n; ++i) {
1310 isl_pw_aff *pa;
1312 pa = isl_pw_aff_list_get_pw_aff(list, i);
1313 pa = isl_pw_aff_add_dims(pa, isl_dim_in, n - (i + 1));
1314 list = isl_pw_aff_list_set_pw_aff(list, i, pa);
1317 space = isl_space_from_range(space);
1318 space = isl_space_add_dims(space, isl_dim_in, v->n);
1319 return isl_multi_pw_aff_from_pw_aff_list(space, list);
1322 /* Add the tuple represented by the isl_multi_pw_aff "tuple" to "map".
1323 * We first create the appropriate space in "map" based on the range
1324 * space of this isl_multi_pw_aff. Then, we add equalities based
1325 * on the affine expressions. These live in an anonymous space,
1326 * however, so we first need to reset the space to that of "map".
1328 static __isl_give isl_map *map_from_tuple(__isl_take isl_multi_pw_aff *tuple,
1329 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
1330 int rational)
1332 int i, n;
1333 isl_ctx *ctx;
1334 isl_space *space = NULL;
1336 if (!map || !tuple)
1337 goto error;
1338 ctx = isl_multi_pw_aff_get_ctx(tuple);
1339 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
1340 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
1341 if (!space)
1342 goto error;
1344 if (type == isl_dim_param) {
1345 if (isl_space_has_tuple_name(space, isl_dim_set) ||
1346 isl_space_is_wrapping(space)) {
1347 isl_die(ctx, isl_error_invalid,
1348 "parameter tuples cannot be named or nested",
1349 goto error);
1351 map = isl_map_add_dims(map, type, n);
1352 for (i = 0; i < n; ++i) {
1353 isl_id *id;
1354 if (!isl_space_has_dim_name(space, isl_dim_set, i))
1355 isl_die(ctx, isl_error_invalid,
1356 "parameters must be named",
1357 goto error);
1358 id = isl_space_get_dim_id(space, isl_dim_set, i);
1359 map = isl_map_set_dim_id(map, isl_dim_param, i, id);
1361 } else if (type == isl_dim_in) {
1362 isl_set *set;
1364 set = isl_set_universe(isl_space_copy(space));
1365 if (rational)
1366 set = isl_set_set_rational(set);
1367 set = isl_set_intersect_params(set, isl_map_params(map));
1368 map = isl_map_from_domain(set);
1369 } else {
1370 isl_set *set;
1372 set = isl_set_universe(isl_space_copy(space));
1373 if (rational)
1374 set = isl_set_set_rational(set);
1375 map = isl_map_from_domain_and_range(isl_map_domain(map), set);
1378 for (i = 0; i < n; ++i) {
1379 isl_pw_aff *pa;
1380 isl_space *space;
1381 isl_aff *aff;
1382 isl_set *set;
1383 isl_map *map_i;
1385 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
1386 space = isl_pw_aff_get_domain_space(pa);
1387 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1388 aff = isl_aff_add_coefficient_si(aff,
1389 isl_dim_in, v->n - n + i, -1);
1390 pa = isl_pw_aff_add(pa, isl_pw_aff_from_aff(aff));
1391 if (rational)
1392 pa = isl_pw_aff_set_rational(pa);
1393 set = isl_pw_aff_zero_set(pa);
1394 map_i = isl_map_from_range(set);
1395 map_i = isl_map_reset_space(map_i, isl_map_get_space(map));
1396 map = isl_map_intersect(map, map_i);
1399 isl_space_free(space);
1400 isl_multi_pw_aff_free(tuple);
1401 return map;
1402 error:
1403 isl_space_free(space);
1404 isl_multi_pw_aff_free(tuple);
1405 isl_map_free(map);
1406 return NULL;
1409 /* Read a tuple from "s" and add it to "map".
1410 * The tuple is initially represented as an isl_multi_pw_aff and
1411 * then added to "map".
1413 static __isl_give isl_map *read_map_tuple(struct isl_stream *s,
1414 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
1415 int rational, int comma)
1417 isl_multi_pw_aff *tuple;
1419 tuple = read_tuple(s, v, rational, comma);
1420 if (!tuple)
1421 return isl_map_free(map);
1423 return map_from_tuple(tuple, map, type, v, rational);
1426 static __isl_give isl_set *construct_constraints(
1427 __isl_take isl_set *set, int type,
1428 __isl_keep isl_pw_aff_list *left, __isl_keep isl_pw_aff_list *right,
1429 int rational)
1431 isl_set *cond;
1433 left = isl_pw_aff_list_copy(left);
1434 right = isl_pw_aff_list_copy(right);
1435 if (rational) {
1436 left = isl_pw_aff_list_set_rational(left);
1437 right = isl_pw_aff_list_set_rational(right);
1439 if (type == ISL_TOKEN_LE)
1440 cond = isl_pw_aff_list_le_set(left, right);
1441 else if (type == ISL_TOKEN_GE)
1442 cond = isl_pw_aff_list_ge_set(left, right);
1443 else if (type == ISL_TOKEN_LT)
1444 cond = isl_pw_aff_list_lt_set(left, right);
1445 else if (type == ISL_TOKEN_GT)
1446 cond = isl_pw_aff_list_gt_set(left, right);
1447 else if (type == ISL_TOKEN_NE)
1448 cond = isl_pw_aff_list_ne_set(left, right);
1449 else
1450 cond = isl_pw_aff_list_eq_set(left, right);
1452 return isl_set_intersect(set, cond);
1455 static __isl_give isl_map *add_constraint(struct isl_stream *s,
1456 struct vars *v, __isl_take isl_map *map, int rational)
1458 struct isl_token *tok = NULL;
1459 isl_pw_aff_list *list1 = NULL, *list2 = NULL;
1460 isl_set *set;
1462 set = isl_map_wrap(map);
1463 list1 = accept_affine_list(s, isl_set_get_space(set), v);
1464 if (!list1)
1465 goto error;
1466 tok = isl_stream_next_token(s);
1467 if (!is_comparator(tok)) {
1468 isl_stream_error(s, tok, "missing operator");
1469 if (tok)
1470 isl_stream_push_token(s, tok);
1471 tok = NULL;
1472 goto error;
1474 for (;;) {
1475 list2 = accept_affine_list(s, isl_set_get_space(set), v);
1476 if (!list2)
1477 goto error;
1479 set = construct_constraints(set, tok->type, list1, list2,
1480 rational);
1481 isl_token_free(tok);
1482 isl_pw_aff_list_free(list1);
1483 list1 = list2;
1485 tok = isl_stream_next_token(s);
1486 if (!is_comparator(tok)) {
1487 if (tok)
1488 isl_stream_push_token(s, tok);
1489 break;
1492 isl_pw_aff_list_free(list1);
1494 return isl_set_unwrap(set);
1495 error:
1496 if (tok)
1497 isl_token_free(tok);
1498 isl_pw_aff_list_free(list1);
1499 isl_pw_aff_list_free(list2);
1500 isl_set_free(set);
1501 return NULL;
1504 static __isl_give isl_map *read_exists(struct isl_stream *s,
1505 struct vars *v, __isl_take isl_map *map, int rational)
1507 int n = v->n;
1508 int seen_paren = isl_stream_eat_if_available(s, '(');
1510 map = isl_map_from_domain(isl_map_wrap(map));
1511 map = read_defined_var_list(s, v, map, rational);
1513 if (isl_stream_eat(s, ':'))
1514 goto error;
1516 map = read_formula(s, v, map, rational);
1517 map = isl_set_unwrap(isl_map_domain(map));
1519 vars_drop(v, v->n - n);
1520 if (seen_paren && isl_stream_eat(s, ')'))
1521 goto error;
1523 return map;
1524 error:
1525 isl_map_free(map);
1526 return NULL;
1529 /* Parse an expression between parentheses and push the result
1530 * back on the stream.
1532 * The parsed expression may be either an affine expression
1533 * or a condition. The first type is pushed onto the stream
1534 * as an isl_pw_aff, while the second is pushed as an isl_map.
1536 * If the initial token indicates the start of a condition,
1537 * we parse it as such.
1538 * Otherwise, we first parse an affine expression and push
1539 * that onto the stream. If the affine expression covers the
1540 * entire expression between parentheses, we return.
1541 * Otherwise, we assume that the affine expression is the
1542 * start of a condition and continue parsing.
1544 static int resolve_paren_expr(struct isl_stream *s,
1545 struct vars *v, __isl_take isl_map *map, int rational)
1547 struct isl_token *tok, *tok2;
1548 int line, col;
1549 isl_pw_aff *pwaff;
1551 tok = isl_stream_next_token(s);
1552 if (!tok || tok->type != '(')
1553 goto error;
1555 if (isl_stream_next_token_is(s, '('))
1556 if (resolve_paren_expr(s, v, isl_map_copy(map), rational))
1557 goto error;
1559 if (isl_stream_next_token_is(s, ISL_TOKEN_EXISTS) ||
1560 isl_stream_next_token_is(s, ISL_TOKEN_NOT) ||
1561 isl_stream_next_token_is(s, ISL_TOKEN_TRUE) ||
1562 isl_stream_next_token_is(s, ISL_TOKEN_FALSE) ||
1563 isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1564 map = read_formula(s, v, map, rational);
1565 if (isl_stream_eat(s, ')'))
1566 goto error;
1567 tok->type = ISL_TOKEN_MAP;
1568 tok->u.map = map;
1569 isl_stream_push_token(s, tok);
1570 return 0;
1573 tok2 = isl_stream_next_token(s);
1574 if (!tok2)
1575 goto error;
1576 line = tok2->line;
1577 col = tok2->col;
1578 isl_stream_push_token(s, tok2);
1580 pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v);
1581 if (!pwaff)
1582 goto error;
1584 tok2 = isl_token_new(s->ctx, line, col, 0);
1585 if (!tok2)
1586 goto error2;
1587 tok2->type = ISL_TOKEN_AFF;
1588 tok2->u.pwaff = pwaff;
1590 if (isl_stream_eat_if_available(s, ')')) {
1591 isl_stream_push_token(s, tok2);
1592 isl_token_free(tok);
1593 isl_map_free(map);
1594 return 0;
1597 isl_stream_push_token(s, tok2);
1599 map = read_formula(s, v, map, rational);
1600 if (isl_stream_eat(s, ')'))
1601 goto error;
1603 tok->type = ISL_TOKEN_MAP;
1604 tok->u.map = map;
1605 isl_stream_push_token(s, tok);
1607 return 0;
1608 error2:
1609 isl_pw_aff_free(pwaff);
1610 error:
1611 isl_token_free(tok);
1612 isl_map_free(map);
1613 return -1;
1616 static __isl_give isl_map *read_conjunct(struct isl_stream *s,
1617 struct vars *v, __isl_take isl_map *map, int rational)
1619 if (isl_stream_next_token_is(s, '('))
1620 if (resolve_paren_expr(s, v, isl_map_copy(map), rational))
1621 goto error;
1623 if (isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1624 struct isl_token *tok;
1625 tok = isl_stream_next_token(s);
1626 if (!tok)
1627 goto error;
1628 isl_map_free(map);
1629 map = isl_map_copy(tok->u.map);
1630 isl_token_free(tok);
1631 return map;
1634 if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))
1635 return read_exists(s, v, map, rational);
1637 if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))
1638 return map;
1640 if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) {
1641 isl_space *dim = isl_map_get_space(map);
1642 isl_map_free(map);
1643 return isl_map_empty(dim);
1646 return add_constraint(s, v, map, rational);
1647 error:
1648 isl_map_free(map);
1649 return NULL;
1652 static __isl_give isl_map *read_conjuncts(struct isl_stream *s,
1653 struct vars *v, __isl_take isl_map *map, int rational)
1655 isl_map *res;
1656 int negate;
1658 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1659 res = read_conjunct(s, v, isl_map_copy(map), rational);
1660 if (negate)
1661 res = isl_map_subtract(isl_map_copy(map), res);
1663 while (res && isl_stream_eat_if_available(s, ISL_TOKEN_AND)) {
1664 isl_map *res_i;
1666 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1667 res_i = read_conjunct(s, v, isl_map_copy(map), rational);
1668 if (negate)
1669 res = isl_map_subtract(res, res_i);
1670 else
1671 res = isl_map_intersect(res, res_i);
1674 isl_map_free(map);
1675 return res;
1678 static struct isl_map *read_disjuncts(struct isl_stream *s,
1679 struct vars *v, __isl_take isl_map *map, int rational)
1681 isl_map *res;
1683 if (isl_stream_next_token_is(s, '}')) {
1684 isl_space *dim = isl_map_get_space(map);
1685 isl_map_free(map);
1686 return isl_map_universe(dim);
1689 res = read_conjuncts(s, v, isl_map_copy(map), rational);
1690 while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
1691 isl_map *res_i;
1693 res_i = read_conjuncts(s, v, isl_map_copy(map), rational);
1694 res = isl_map_union(res, res_i);
1697 isl_map_free(map);
1698 return res;
1701 /* Read a first order formula from "s", add the corresponding
1702 * constraints to "map" and return the result.
1704 * In particular, read a formula of the form
1708 * or
1710 * a implies b
1712 * where a and b are disjunctions.
1714 * In the first case, map is replaced by
1716 * map \cap { [..] : a }
1718 * In the second case, it is replaced by
1720 * (map \setminus { [..] : a}) \cup (map \cap { [..] : b })
1722 static __isl_give isl_map *read_formula(struct isl_stream *s,
1723 struct vars *v, __isl_take isl_map *map, int rational)
1725 isl_map *res;
1727 res = read_disjuncts(s, v, isl_map_copy(map), rational);
1729 if (isl_stream_eat_if_available(s, ISL_TOKEN_IMPLIES)) {
1730 isl_map *res2;
1732 res = isl_map_subtract(isl_map_copy(map), res);
1733 res2 = read_disjuncts(s, v, map, rational);
1734 res = isl_map_union(res, res2);
1735 } else
1736 isl_map_free(map);
1738 return res;
1741 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1743 if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1744 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1745 isl_basic_map_dim(bmap, isl_dim_in) + pos;
1746 pos -= isl_basic_map_dim(bmap, isl_dim_out);
1748 if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1749 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1750 pos -= isl_basic_map_dim(bmap, isl_dim_in);
1752 if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1753 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1754 isl_basic_map_dim(bmap, isl_dim_in) +
1755 isl_basic_map_dim(bmap, isl_dim_out) + pos;
1756 pos -= isl_basic_map_dim(bmap, isl_dim_div);
1758 if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1759 return 1 + pos;
1761 return 0;
1764 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1765 struct isl_stream *s, __isl_take isl_basic_map *bmap)
1767 int j;
1768 struct isl_token *tok;
1769 int type;
1770 int k;
1771 isl_int *c;
1772 unsigned nparam;
1773 unsigned dim;
1775 if (!bmap)
1776 return NULL;
1778 nparam = isl_basic_map_dim(bmap, isl_dim_param);
1779 dim = isl_basic_map_dim(bmap, isl_dim_out);
1781 tok = isl_stream_next_token(s);
1782 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1783 isl_stream_error(s, tok, "expecting coefficient");
1784 if (tok)
1785 isl_stream_push_token(s, tok);
1786 goto error;
1788 if (!tok->on_new_line) {
1789 isl_stream_error(s, tok, "coefficient should appear on new line");
1790 isl_stream_push_token(s, tok);
1791 goto error;
1794 type = isl_int_get_si(tok->u.v);
1795 isl_token_free(tok);
1797 isl_assert(s->ctx, type == 0 || type == 1, goto error);
1798 if (type == 0) {
1799 k = isl_basic_map_alloc_equality(bmap);
1800 c = bmap->eq[k];
1801 } else {
1802 k = isl_basic_map_alloc_inequality(bmap);
1803 c = bmap->ineq[k];
1805 if (k < 0)
1806 goto error;
1808 for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1809 int pos;
1810 tok = isl_stream_next_token(s);
1811 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1812 isl_stream_error(s, tok, "expecting coefficient");
1813 if (tok)
1814 isl_stream_push_token(s, tok);
1815 goto error;
1817 if (tok->on_new_line) {
1818 isl_stream_error(s, tok,
1819 "coefficient should not appear on new line");
1820 isl_stream_push_token(s, tok);
1821 goto error;
1823 pos = polylib_pos_to_isl_pos(bmap, j);
1824 isl_int_set(c[pos], tok->u.v);
1825 isl_token_free(tok);
1828 return bmap;
1829 error:
1830 isl_basic_map_free(bmap);
1831 return NULL;
1834 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s)
1836 int i;
1837 struct isl_token *tok;
1838 struct isl_token *tok2;
1839 int n_row, n_col;
1840 int on_new_line;
1841 unsigned in = 0, out, local = 0;
1842 struct isl_basic_map *bmap = NULL;
1843 int nparam = 0;
1845 tok = isl_stream_next_token(s);
1846 if (!tok) {
1847 isl_stream_error(s, NULL, "unexpected EOF");
1848 return NULL;
1850 tok2 = isl_stream_next_token(s);
1851 if (!tok2) {
1852 isl_token_free(tok);
1853 isl_stream_error(s, NULL, "unexpected EOF");
1854 return NULL;
1856 if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1857 isl_stream_push_token(s, tok2);
1858 isl_stream_push_token(s, tok);
1859 isl_stream_error(s, NULL,
1860 "expecting constraint matrix dimensions");
1861 return NULL;
1863 n_row = isl_int_get_si(tok->u.v);
1864 n_col = isl_int_get_si(tok2->u.v);
1865 on_new_line = tok2->on_new_line;
1866 isl_token_free(tok2);
1867 isl_token_free(tok);
1868 isl_assert(s->ctx, !on_new_line, return NULL);
1869 isl_assert(s->ctx, n_row >= 0, return NULL);
1870 isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1871 tok = isl_stream_next_token_on_same_line(s);
1872 if (tok) {
1873 if (tok->type != ISL_TOKEN_VALUE) {
1874 isl_stream_error(s, tok,
1875 "expecting number of output dimensions");
1876 isl_stream_push_token(s, tok);
1877 goto error;
1879 out = isl_int_get_si(tok->u.v);
1880 isl_token_free(tok);
1882 tok = isl_stream_next_token_on_same_line(s);
1883 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1884 isl_stream_error(s, tok,
1885 "expecting number of input dimensions");
1886 if (tok)
1887 isl_stream_push_token(s, tok);
1888 goto error;
1890 in = isl_int_get_si(tok->u.v);
1891 isl_token_free(tok);
1893 tok = isl_stream_next_token_on_same_line(s);
1894 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1895 isl_stream_error(s, tok,
1896 "expecting number of existentials");
1897 if (tok)
1898 isl_stream_push_token(s, tok);
1899 goto error;
1901 local = isl_int_get_si(tok->u.v);
1902 isl_token_free(tok);
1904 tok = isl_stream_next_token_on_same_line(s);
1905 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1906 isl_stream_error(s, tok,
1907 "expecting number of parameters");
1908 if (tok)
1909 isl_stream_push_token(s, tok);
1910 goto error;
1912 nparam = isl_int_get_si(tok->u.v);
1913 isl_token_free(tok);
1914 if (n_col != 1 + out + in + local + nparam + 1) {
1915 isl_stream_error(s, NULL,
1916 "dimensions don't match");
1917 goto error;
1919 } else
1920 out = n_col - 2 - nparam;
1921 bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1922 if (!bmap)
1923 return NULL;
1925 for (i = 0; i < local; ++i) {
1926 int k = isl_basic_map_alloc_div(bmap);
1927 if (k < 0)
1928 goto error;
1929 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1932 for (i = 0; i < n_row; ++i)
1933 bmap = basic_map_read_polylib_constraint(s, bmap);
1935 tok = isl_stream_next_token_on_same_line(s);
1936 if (tok) {
1937 isl_stream_error(s, tok, "unexpected extra token on line");
1938 isl_stream_push_token(s, tok);
1939 goto error;
1942 bmap = isl_basic_map_simplify(bmap);
1943 bmap = isl_basic_map_finalize(bmap);
1944 return bmap;
1945 error:
1946 isl_basic_map_free(bmap);
1947 return NULL;
1950 static struct isl_map *map_read_polylib(struct isl_stream *s)
1952 struct isl_token *tok;
1953 struct isl_token *tok2;
1954 int i, n;
1955 struct isl_map *map;
1957 tok = isl_stream_next_token(s);
1958 if (!tok) {
1959 isl_stream_error(s, NULL, "unexpected EOF");
1960 return NULL;
1962 tok2 = isl_stream_next_token_on_same_line(s);
1963 if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
1964 isl_stream_push_token(s, tok2);
1965 isl_stream_push_token(s, tok);
1966 return isl_map_from_basic_map(basic_map_read_polylib(s));
1968 if (tok2) {
1969 isl_stream_error(s, tok2, "unexpected token");
1970 isl_stream_push_token(s, tok2);
1971 isl_stream_push_token(s, tok);
1972 return NULL;
1974 n = isl_int_get_si(tok->u.v);
1975 isl_token_free(tok);
1977 isl_assert(s->ctx, n >= 1, return NULL);
1979 map = isl_map_from_basic_map(basic_map_read_polylib(s));
1981 for (i = 1; map && i < n; ++i)
1982 map = isl_map_union(map,
1983 isl_map_from_basic_map(basic_map_read_polylib(s)));
1985 return map;
1988 static int optional_power(struct isl_stream *s)
1990 int pow;
1991 struct isl_token *tok;
1993 tok = isl_stream_next_token(s);
1994 if (!tok)
1995 return 1;
1996 if (tok->type != '^') {
1997 isl_stream_push_token(s, tok);
1998 return 1;
2000 isl_token_free(tok);
2001 tok = isl_stream_next_token(s);
2002 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2003 isl_stream_error(s, tok, "expecting exponent");
2004 if (tok)
2005 isl_stream_push_token(s, tok);
2006 return 1;
2008 pow = isl_int_get_si(tok->u.v);
2009 isl_token_free(tok);
2010 return pow;
2013 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
2014 __isl_keep isl_map *map, struct vars *v);
2016 static __isl_give isl_pw_qpolynomial *read_factor(struct isl_stream *s,
2017 __isl_keep isl_map *map, struct vars *v)
2019 isl_pw_qpolynomial *pwqp;
2020 struct isl_token *tok;
2022 tok = next_token(s);
2023 if (!tok) {
2024 isl_stream_error(s, NULL, "unexpected EOF");
2025 return NULL;
2027 if (tok->type == '(') {
2028 int pow;
2030 isl_token_free(tok);
2031 pwqp = read_term(s, map, v);
2032 if (!pwqp)
2033 return NULL;
2034 if (isl_stream_eat(s, ')'))
2035 goto error;
2036 pow = optional_power(s);
2037 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
2038 } else if (tok->type == ISL_TOKEN_VALUE) {
2039 struct isl_token *tok2;
2040 isl_qpolynomial *qp;
2042 tok2 = isl_stream_next_token(s);
2043 if (tok2 && tok2->type == '/') {
2044 isl_token_free(tok2);
2045 tok2 = next_token(s);
2046 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
2047 isl_stream_error(s, tok2, "expected denominator");
2048 isl_token_free(tok);
2049 isl_token_free(tok2);
2050 return NULL;
2052 qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map),
2053 tok->u.v, tok2->u.v);
2054 isl_token_free(tok2);
2055 } else {
2056 isl_stream_push_token(s, tok2);
2057 qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map),
2058 tok->u.v);
2060 isl_token_free(tok);
2061 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2062 } else if (tok->type == ISL_TOKEN_INFTY) {
2063 isl_qpolynomial *qp;
2064 isl_token_free(tok);
2065 qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map));
2066 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2067 } else if (tok->type == ISL_TOKEN_NAN) {
2068 isl_qpolynomial *qp;
2069 isl_token_free(tok);
2070 qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map));
2071 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2072 } else if (tok->type == ISL_TOKEN_IDENT) {
2073 int n = v->n;
2074 int pos = vars_pos(v, tok->u.s, -1);
2075 int pow;
2076 isl_qpolynomial *qp;
2077 if (pos < 0) {
2078 isl_token_free(tok);
2079 return NULL;
2081 if (pos >= n) {
2082 vars_drop(v, v->n - n);
2083 isl_stream_error(s, tok, "unknown identifier");
2084 isl_token_free(tok);
2085 return NULL;
2087 isl_token_free(tok);
2088 pow = optional_power(s);
2089 qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow);
2090 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2091 } else if (is_start_of_div(tok)) {
2092 isl_pw_aff *pwaff;
2093 int pow;
2095 isl_stream_push_token(s, tok);
2096 pwaff = accept_div(s, isl_map_get_space(map), v);
2097 pow = optional_power(s);
2098 pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff);
2099 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
2100 } else if (tok->type == '-') {
2101 isl_token_free(tok);
2102 pwqp = read_factor(s, map, v);
2103 pwqp = isl_pw_qpolynomial_neg(pwqp);
2104 } else {
2105 isl_stream_error(s, tok, "unexpected isl_token");
2106 isl_stream_push_token(s, tok);
2107 return NULL;
2110 if (isl_stream_eat_if_available(s, '*') ||
2111 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
2112 isl_pw_qpolynomial *pwqp2;
2114 pwqp2 = read_factor(s, map, v);
2115 pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2);
2118 return pwqp;
2119 error:
2120 isl_pw_qpolynomial_free(pwqp);
2121 return NULL;
2124 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
2125 __isl_keep isl_map *map, struct vars *v)
2127 struct isl_token *tok;
2128 isl_pw_qpolynomial *pwqp;
2130 pwqp = read_factor(s, map, v);
2132 for (;;) {
2133 tok = next_token(s);
2134 if (!tok)
2135 return pwqp;
2137 if (tok->type == '+') {
2138 isl_pw_qpolynomial *pwqp2;
2140 isl_token_free(tok);
2141 pwqp2 = read_factor(s, map, v);
2142 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
2143 } else if (tok->type == '-') {
2144 isl_pw_qpolynomial *pwqp2;
2146 isl_token_free(tok);
2147 pwqp2 = read_factor(s, map, v);
2148 pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2);
2149 } else if (tok->type == ISL_TOKEN_VALUE &&
2150 isl_int_is_neg(tok->u.v)) {
2151 isl_pw_qpolynomial *pwqp2;
2153 isl_stream_push_token(s, tok);
2154 pwqp2 = read_factor(s, map, v);
2155 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
2156 } else {
2157 isl_stream_push_token(s, tok);
2158 break;
2162 return pwqp;
2165 static __isl_give isl_map *read_optional_formula(struct isl_stream *s,
2166 __isl_take isl_map *map, struct vars *v, int rational)
2168 struct isl_token *tok;
2170 tok = isl_stream_next_token(s);
2171 if (!tok) {
2172 isl_stream_error(s, NULL, "unexpected EOF");
2173 goto error;
2175 if (tok->type == ':' ||
2176 (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {
2177 isl_token_free(tok);
2178 map = read_formula(s, v, map, rational);
2179 } else
2180 isl_stream_push_token(s, tok);
2182 return map;
2183 error:
2184 isl_map_free(map);
2185 return NULL;
2188 static struct isl_obj obj_read_poly(struct isl_stream *s,
2189 __isl_take isl_map *map, struct vars *v, int n)
2191 struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
2192 isl_pw_qpolynomial *pwqp;
2193 struct isl_set *set;
2195 pwqp = read_term(s, map, v);
2196 map = read_optional_formula(s, map, v, 0);
2197 set = isl_map_range(map);
2199 pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set);
2201 vars_drop(v, v->n - n);
2203 obj.v = pwqp;
2204 return obj;
2207 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
2208 __isl_take isl_set *set, struct vars *v, int n)
2210 struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
2211 isl_pw_qpolynomial *pwqp;
2212 isl_pw_qpolynomial_fold *pwf = NULL;
2214 if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
2215 return obj_read_poly(s, set, v, n);
2217 if (isl_stream_eat(s, '('))
2218 goto error;
2220 pwqp = read_term(s, set, v);
2221 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, pwqp);
2223 while (isl_stream_eat_if_available(s, ',')) {
2224 isl_pw_qpolynomial_fold *pwf_i;
2225 pwqp = read_term(s, set, v);
2226 pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max,
2227 pwqp);
2228 pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i);
2231 if (isl_stream_eat(s, ')'))
2232 goto error;
2234 set = read_optional_formula(s, set, v, 0);
2235 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set);
2237 vars_drop(v, v->n - n);
2239 obj.v = pwf;
2240 return obj;
2241 error:
2242 isl_set_free(set);
2243 isl_pw_qpolynomial_fold_free(pwf);
2244 obj.type = isl_obj_none;
2245 return obj;
2248 static int is_rational(struct isl_stream *s)
2250 struct isl_token *tok;
2252 tok = isl_stream_next_token(s);
2253 if (!tok)
2254 return 0;
2255 if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) {
2256 isl_token_free(tok);
2257 isl_stream_eat(s, ':');
2258 return 1;
2261 isl_stream_push_token(s, tok);
2263 return 0;
2266 static struct isl_obj obj_read_body(struct isl_stream *s,
2267 __isl_take isl_map *map, struct vars *v)
2269 struct isl_token *tok;
2270 struct isl_obj obj = { isl_obj_set, NULL };
2271 int n = v->n;
2272 int rational;
2274 rational = is_rational(s);
2275 if (rational)
2276 map = isl_map_set_rational(map);
2278 if (isl_stream_next_token_is(s, ':')) {
2279 obj.type = isl_obj_set;
2280 obj.v = read_optional_formula(s, map, v, rational);
2281 return obj;
2284 if (!next_is_tuple(s))
2285 return obj_read_poly_or_fold(s, map, v, n);
2287 map = read_map_tuple(s, map, isl_dim_in, v, rational, 0);
2288 if (!map)
2289 goto error;
2290 tok = isl_stream_next_token(s);
2291 if (!tok)
2292 goto error;
2293 if (tok->type == ISL_TOKEN_TO) {
2294 obj.type = isl_obj_map;
2295 isl_token_free(tok);
2296 if (!next_is_tuple(s)) {
2297 isl_set *set = isl_map_domain(map);
2298 return obj_read_poly_or_fold(s, set, v, n);
2300 map = read_map_tuple(s, map, isl_dim_out, v, rational, 0);
2301 if (!map)
2302 goto error;
2303 } else {
2304 map = isl_map_domain(map);
2305 isl_stream_push_token(s, tok);
2308 map = read_optional_formula(s, map, v, rational);
2310 vars_drop(v, v->n - n);
2312 obj.v = map;
2313 return obj;
2314 error:
2315 isl_map_free(map);
2316 obj.type = isl_obj_none;
2317 return obj;
2320 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
2322 if (obj.type == isl_obj_map) {
2323 obj.v = isl_union_map_from_map(obj.v);
2324 obj.type = isl_obj_union_map;
2325 } else if (obj.type == isl_obj_set) {
2326 obj.v = isl_union_set_from_set(obj.v);
2327 obj.type = isl_obj_union_set;
2328 } else if (obj.type == isl_obj_pw_qpolynomial) {
2329 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2330 obj.type = isl_obj_union_pw_qpolynomial;
2331 } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
2332 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
2333 obj.type = isl_obj_union_pw_qpolynomial_fold;
2334 } else
2335 isl_assert(ctx, 0, goto error);
2336 return obj;
2337 error:
2338 obj.type->free(obj.v);
2339 obj.type = isl_obj_none;
2340 return obj;
2343 static struct isl_obj obj_add(struct isl_ctx *ctx,
2344 struct isl_obj obj1, struct isl_obj obj2)
2346 if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
2347 obj1 = to_union(ctx, obj1);
2348 if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
2349 obj2 = to_union(ctx, obj2);
2350 if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
2351 obj1 = to_union(ctx, obj1);
2352 if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
2353 obj2 = to_union(ctx, obj2);
2354 if (obj1.type == isl_obj_pw_qpolynomial &&
2355 obj2.type == isl_obj_union_pw_qpolynomial)
2356 obj1 = to_union(ctx, obj1);
2357 if (obj1.type == isl_obj_union_pw_qpolynomial &&
2358 obj2.type == isl_obj_pw_qpolynomial)
2359 obj2 = to_union(ctx, obj2);
2360 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2361 obj2.type == isl_obj_union_pw_qpolynomial_fold)
2362 obj1 = to_union(ctx, obj1);
2363 if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
2364 obj2.type == isl_obj_pw_qpolynomial_fold)
2365 obj2 = to_union(ctx, obj2);
2366 isl_assert(ctx, obj1.type == obj2.type, goto error);
2367 if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) {
2368 obj1 = to_union(ctx, obj1);
2369 obj2 = to_union(ctx, obj2);
2371 if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) {
2372 obj1 = to_union(ctx, obj1);
2373 obj2 = to_union(ctx, obj2);
2375 if (obj1.type == isl_obj_pw_qpolynomial &&
2376 !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) {
2377 obj1 = to_union(ctx, obj1);
2378 obj2 = to_union(ctx, obj2);
2380 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2381 !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) {
2382 obj1 = to_union(ctx, obj1);
2383 obj2 = to_union(ctx, obj2);
2385 obj1.v = obj1.type->add(obj1.v, obj2.v);
2386 return obj1;
2387 error:
2388 obj1.type->free(obj1.v);
2389 obj2.type->free(obj2.v);
2390 obj1.type = isl_obj_none;
2391 obj1.v = NULL;
2392 return obj1;
2395 static struct isl_obj obj_read(struct isl_stream *s)
2397 isl_map *map = NULL;
2398 struct isl_token *tok;
2399 struct vars *v = NULL;
2400 struct isl_obj obj = { isl_obj_set, NULL };
2402 tok = next_token(s);
2403 if (!tok) {
2404 isl_stream_error(s, NULL, "unexpected EOF");
2405 goto error;
2407 if (tok->type == ISL_TOKEN_VALUE) {
2408 struct isl_token *tok2;
2409 struct isl_map *map;
2411 tok2 = isl_stream_next_token(s);
2412 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
2413 isl_int_is_neg(tok2->u.v)) {
2414 if (tok2)
2415 isl_stream_push_token(s, tok2);
2416 obj.type = isl_obj_val;
2417 obj.v = isl_val_int_from_isl_int(s->ctx, tok->u.v);
2418 isl_token_free(tok);
2419 return obj;
2421 isl_stream_push_token(s, tok2);
2422 isl_stream_push_token(s, tok);
2423 map = map_read_polylib(s);
2424 if (!map)
2425 goto error;
2426 if (isl_map_may_be_set(map))
2427 obj.v = isl_map_range(map);
2428 else {
2429 obj.type = isl_obj_map;
2430 obj.v = map;
2432 return obj;
2434 v = vars_new(s->ctx);
2435 if (!v) {
2436 isl_stream_push_token(s, tok);
2437 goto error;
2439 map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));
2440 if (tok->type == '[') {
2441 isl_stream_push_token(s, tok);
2442 map = read_map_tuple(s, map, isl_dim_param, v, 0, 0);
2443 if (!map)
2444 goto error;
2445 tok = isl_stream_next_token(s);
2446 if (!tok || tok->type != ISL_TOKEN_TO) {
2447 isl_stream_error(s, tok, "expecting '->'");
2448 if (tok)
2449 isl_stream_push_token(s, tok);
2450 goto error;
2452 isl_token_free(tok);
2453 tok = isl_stream_next_token(s);
2455 if (!tok || tok->type != '{') {
2456 isl_stream_error(s, tok, "expecting '{'");
2457 if (tok)
2458 isl_stream_push_token(s, tok);
2459 goto error;
2461 isl_token_free(tok);
2463 tok = isl_stream_next_token(s);
2464 if (!tok)
2466 else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
2467 isl_token_free(tok);
2468 if (isl_stream_eat(s, '='))
2469 goto error;
2470 map = read_map_tuple(s, map, isl_dim_param, v, 0, 1);
2471 if (!map)
2472 goto error;
2473 } else if (tok->type == '}') {
2474 obj.type = isl_obj_union_set;
2475 obj.v = isl_union_set_empty(isl_map_get_space(map));
2476 isl_token_free(tok);
2477 goto done;
2478 } else
2479 isl_stream_push_token(s, tok);
2481 for (;;) {
2482 struct isl_obj o;
2483 tok = NULL;
2484 o = obj_read_body(s, isl_map_copy(map), v);
2485 if (o.type == isl_obj_none || !o.v)
2486 goto error;
2487 if (!obj.v)
2488 obj = o;
2489 else {
2490 obj = obj_add(s->ctx, obj, o);
2491 if (obj.type == isl_obj_none || !obj.v)
2492 goto error;
2494 tok = isl_stream_next_token(s);
2495 if (!tok || tok->type != ';')
2496 break;
2497 isl_token_free(tok);
2498 if (isl_stream_next_token_is(s, '}')) {
2499 tok = isl_stream_next_token(s);
2500 break;
2504 if (tok && tok->type == '}') {
2505 isl_token_free(tok);
2506 } else {
2507 isl_stream_error(s, tok, "unexpected isl_token");
2508 if (tok)
2509 isl_token_free(tok);
2510 goto error;
2512 done:
2513 vars_free(v);
2514 isl_map_free(map);
2516 return obj;
2517 error:
2518 isl_map_free(map);
2519 obj.type->free(obj.v);
2520 if (v)
2521 vars_free(v);
2522 obj.v = NULL;
2523 return obj;
2526 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
2528 return obj_read(s);
2531 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s)
2533 struct isl_obj obj;
2535 obj = obj_read(s);
2536 if (obj.v)
2537 isl_assert(s->ctx, obj.type == isl_obj_map ||
2538 obj.type == isl_obj_set, goto error);
2540 if (obj.type == isl_obj_set)
2541 obj.v = isl_map_from_range(obj.v);
2543 return obj.v;
2544 error:
2545 obj.type->free(obj.v);
2546 return NULL;
2549 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s)
2551 struct isl_obj obj;
2553 obj = obj_read(s);
2554 if (obj.v) {
2555 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) {
2556 obj.v = isl_map_range(obj.v);
2557 obj.type = isl_obj_set;
2559 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2562 return obj.v;
2563 error:
2564 obj.type->free(obj.v);
2565 return NULL;
2568 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2570 struct isl_obj obj;
2572 obj = obj_read(s);
2573 if (obj.type == isl_obj_map) {
2574 obj.type = isl_obj_union_map;
2575 obj.v = isl_union_map_from_map(obj.v);
2577 if (obj.type == isl_obj_set) {
2578 obj.type = isl_obj_union_set;
2579 obj.v = isl_union_set_from_set(obj.v);
2581 if (obj.v && obj.type == isl_obj_union_set &&
2582 isl_union_set_is_empty(obj.v))
2583 obj.type = isl_obj_union_map;
2584 if (obj.v && obj.type != isl_obj_union_map)
2585 isl_die(s->ctx, isl_error_invalid, "invalid input", goto error);
2587 return obj.v;
2588 error:
2589 obj.type->free(obj.v);
2590 return NULL;
2593 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2595 struct isl_obj obj;
2597 obj = obj_read(s);
2598 if (obj.type == isl_obj_set) {
2599 obj.type = isl_obj_union_set;
2600 obj.v = isl_union_set_from_set(obj.v);
2602 if (obj.v)
2603 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2605 return obj.v;
2606 error:
2607 obj.type->free(obj.v);
2608 return NULL;
2611 static __isl_give isl_basic_map *basic_map_read(struct isl_stream *s)
2613 struct isl_obj obj;
2614 struct isl_map *map;
2615 struct isl_basic_map *bmap;
2617 obj = obj_read(s);
2618 if (obj.v && (obj.type != isl_obj_map && obj.type != isl_obj_set))
2619 isl_die(s->ctx, isl_error_invalid, "not a (basic) set or map",
2620 goto error);
2621 map = obj.v;
2622 if (!map)
2623 return NULL;
2625 if (map->n > 1)
2626 isl_die(s->ctx, isl_error_invalid,
2627 "set or map description involves "
2628 "more than one disjunct", goto error);
2630 if (map->n == 0)
2631 bmap = isl_basic_map_empty_like_map(map);
2632 else
2633 bmap = isl_basic_map_copy(map->p[0]);
2635 isl_map_free(map);
2637 return bmap;
2638 error:
2639 obj.type->free(obj.v);
2640 return NULL;
2643 static __isl_give isl_basic_set *basic_set_read(struct isl_stream *s)
2645 isl_basic_map *bmap;
2646 bmap = basic_map_read(s);
2647 if (!bmap)
2648 return NULL;
2649 if (!isl_basic_map_may_be_set(bmap))
2650 isl_die(s->ctx, isl_error_invalid,
2651 "input is not a set", goto error);
2652 return isl_basic_map_range(bmap);
2653 error:
2654 isl_basic_map_free(bmap);
2655 return NULL;
2658 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2659 FILE *input)
2661 struct isl_basic_map *bmap;
2662 struct isl_stream *s = isl_stream_new_file(ctx, input);
2663 if (!s)
2664 return NULL;
2665 bmap = basic_map_read(s);
2666 isl_stream_free(s);
2667 return bmap;
2670 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2671 FILE *input)
2673 isl_basic_set *bset;
2674 struct isl_stream *s = isl_stream_new_file(ctx, input);
2675 if (!s)
2676 return NULL;
2677 bset = basic_set_read(s);
2678 isl_stream_free(s);
2679 return bset;
2682 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2683 const char *str)
2685 struct isl_basic_map *bmap;
2686 struct isl_stream *s = isl_stream_new_str(ctx, str);
2687 if (!s)
2688 return NULL;
2689 bmap = basic_map_read(s);
2690 isl_stream_free(s);
2691 return bmap;
2694 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2695 const char *str)
2697 isl_basic_set *bset;
2698 struct isl_stream *s = isl_stream_new_str(ctx, str);
2699 if (!s)
2700 return NULL;
2701 bset = basic_set_read(s);
2702 isl_stream_free(s);
2703 return bset;
2706 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2707 FILE *input)
2709 struct isl_map *map;
2710 struct isl_stream *s = isl_stream_new_file(ctx, input);
2711 if (!s)
2712 return NULL;
2713 map = isl_stream_read_map(s);
2714 isl_stream_free(s);
2715 return map;
2718 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2719 const char *str)
2721 struct isl_map *map;
2722 struct isl_stream *s = isl_stream_new_str(ctx, str);
2723 if (!s)
2724 return NULL;
2725 map = isl_stream_read_map(s);
2726 isl_stream_free(s);
2727 return map;
2730 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2731 FILE *input)
2733 isl_set *set;
2734 struct isl_stream *s = isl_stream_new_file(ctx, input);
2735 if (!s)
2736 return NULL;
2737 set = isl_stream_read_set(s);
2738 isl_stream_free(s);
2739 return set;
2742 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2743 const char *str)
2745 isl_set *set;
2746 struct isl_stream *s = isl_stream_new_str(ctx, str);
2747 if (!s)
2748 return NULL;
2749 set = isl_stream_read_set(s);
2750 isl_stream_free(s);
2751 return set;
2754 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2755 FILE *input)
2757 isl_union_map *umap;
2758 struct isl_stream *s = isl_stream_new_file(ctx, input);
2759 if (!s)
2760 return NULL;
2761 umap = isl_stream_read_union_map(s);
2762 isl_stream_free(s);
2763 return umap;
2766 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2767 const char *str)
2769 isl_union_map *umap;
2770 struct isl_stream *s = isl_stream_new_str(ctx, str);
2771 if (!s)
2772 return NULL;
2773 umap = isl_stream_read_union_map(s);
2774 isl_stream_free(s);
2775 return umap;
2778 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2779 FILE *input)
2781 isl_union_set *uset;
2782 struct isl_stream *s = isl_stream_new_file(ctx, input);
2783 if (!s)
2784 return NULL;
2785 uset = isl_stream_read_union_set(s);
2786 isl_stream_free(s);
2787 return uset;
2790 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2791 const char *str)
2793 isl_union_set *uset;
2794 struct isl_stream *s = isl_stream_new_str(ctx, str);
2795 if (!s)
2796 return NULL;
2797 uset = isl_stream_read_union_set(s);
2798 isl_stream_free(s);
2799 return uset;
2802 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2804 struct isl_vec *vec = NULL;
2805 struct isl_token *tok;
2806 unsigned size;
2807 int j;
2809 tok = isl_stream_next_token(s);
2810 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2811 isl_stream_error(s, tok, "expecting vector length");
2812 goto error;
2815 size = isl_int_get_si(tok->u.v);
2816 isl_token_free(tok);
2818 vec = isl_vec_alloc(s->ctx, size);
2820 for (j = 0; j < size; ++j) {
2821 tok = isl_stream_next_token(s);
2822 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2823 isl_stream_error(s, tok, "expecting constant value");
2824 goto error;
2826 isl_int_set(vec->el[j], tok->u.v);
2827 isl_token_free(tok);
2830 return vec;
2831 error:
2832 isl_token_free(tok);
2833 isl_vec_free(vec);
2834 return NULL;
2837 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2839 return isl_vec_read_polylib(s);
2842 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2844 isl_vec *v;
2845 struct isl_stream *s = isl_stream_new_file(ctx, input);
2846 if (!s)
2847 return NULL;
2848 v = vec_read(s);
2849 isl_stream_free(s);
2850 return v;
2853 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2854 struct isl_stream *s)
2856 struct isl_obj obj;
2858 obj = obj_read(s);
2859 if (obj.v)
2860 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2861 goto error);
2863 return obj.v;
2864 error:
2865 obj.type->free(obj.v);
2866 return NULL;
2869 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2870 const char *str)
2872 isl_pw_qpolynomial *pwqp;
2873 struct isl_stream *s = isl_stream_new_str(ctx, str);
2874 if (!s)
2875 return NULL;
2876 pwqp = isl_stream_read_pw_qpolynomial(s);
2877 isl_stream_free(s);
2878 return pwqp;
2881 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
2882 FILE *input)
2884 isl_pw_qpolynomial *pwqp;
2885 struct isl_stream *s = isl_stream_new_file(ctx, input);
2886 if (!s)
2887 return NULL;
2888 pwqp = isl_stream_read_pw_qpolynomial(s);
2889 isl_stream_free(s);
2890 return pwqp;
2893 /* Is the next token an identifer not in "v"?
2895 static int next_is_fresh_ident(struct isl_stream *s, struct vars *v)
2897 int n = v->n;
2898 int fresh;
2899 struct isl_token *tok;
2901 tok = isl_stream_next_token(s);
2902 if (!tok)
2903 return 0;
2904 fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n;
2905 isl_stream_push_token(s, tok);
2907 vars_drop(v, v->n - n);
2909 return fresh;
2912 /* First read the domain of the affine expression, which may be
2913 * a parameter space or a set.
2914 * The tricky part is that we don't know if the domain is a set or not,
2915 * so when we are trying to read the domain, we may actually be reading
2916 * the affine expression itself (defined on a parameter domains)
2917 * If the tuple we are reading is named, we assume it's the domain.
2918 * Also, if inside the tuple, the first thing we find is a nested tuple
2919 * or a new identifier, we again assume it's the domain.
2920 * Otherwise, we assume we are reading an affine expression.
2922 static __isl_give isl_set *read_aff_domain(struct isl_stream *s,
2923 __isl_take isl_set *dom, struct vars *v)
2925 struct isl_token *tok;
2927 tok = isl_stream_next_token(s);
2928 if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
2929 isl_stream_push_token(s, tok);
2930 return read_map_tuple(s, dom, isl_dim_set, v, 1, 0);
2932 if (!tok || tok->type != '[') {
2933 isl_stream_error(s, tok, "expecting '['");
2934 goto error;
2936 if (next_is_tuple(s) || next_is_fresh_ident(s, v)) {
2937 isl_stream_push_token(s, tok);
2938 dom = read_map_tuple(s, dom, isl_dim_set, v, 1, 0);
2939 } else
2940 isl_stream_push_token(s, tok);
2942 return dom;
2943 error:
2944 if (tok)
2945 isl_stream_push_token(s, tok);
2946 isl_set_free(dom);
2947 return NULL;
2950 /* Read an affine expression from "s".
2952 __isl_give isl_aff *isl_stream_read_aff(struct isl_stream *s)
2954 isl_aff *aff;
2955 isl_multi_aff *ma;
2957 ma = isl_stream_read_multi_aff(s);
2958 if (!ma)
2959 return NULL;
2960 if (isl_multi_aff_dim(ma, isl_dim_out) != 1)
2961 isl_die(s->ctx, isl_error_invalid,
2962 "expecting single affine expression",
2963 goto error);
2965 aff = isl_multi_aff_get_aff(ma, 0);
2966 isl_multi_aff_free(ma);
2967 return aff;
2968 error:
2969 isl_multi_aff_free(ma);
2970 return NULL;
2973 /* Read a piecewise affine expression from "s" with domain (space) "dom".
2975 static __isl_give isl_pw_aff *read_pw_aff_with_dom(struct isl_stream *s,
2976 __isl_take isl_set *dom, struct vars *v)
2978 isl_pw_aff *pwaff = NULL;
2980 if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2981 goto error;
2983 if (isl_stream_eat(s, '['))
2984 goto error;
2986 pwaff = accept_affine(s, isl_set_get_space(dom), v);
2988 if (isl_stream_eat(s, ']'))
2989 goto error;
2991 dom = read_optional_formula(s, dom, v, 0);
2992 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2994 return pwaff;
2995 error:
2996 isl_set_free(dom);
2997 isl_pw_aff_free(pwaff);
2998 return NULL;
3001 __isl_give isl_pw_aff *isl_stream_read_pw_aff(struct isl_stream *s)
3003 struct vars *v;
3004 isl_set *dom = NULL;
3005 isl_set *aff_dom;
3006 isl_pw_aff *pa = NULL;
3007 int n;
3009 v = vars_new(s->ctx);
3010 if (!v)
3011 return NULL;
3013 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3014 if (next_is_tuple(s)) {
3015 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3016 if (isl_stream_eat(s, ISL_TOKEN_TO))
3017 goto error;
3019 if (isl_stream_eat(s, '{'))
3020 goto error;
3022 n = v->n;
3023 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
3024 pa = read_pw_aff_with_dom(s, aff_dom, v);
3025 vars_drop(v, v->n - n);
3027 while (isl_stream_eat_if_available(s, ';')) {
3028 isl_pw_aff *pa_i;
3030 n = v->n;
3031 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
3032 pa_i = read_pw_aff_with_dom(s, aff_dom, v);
3033 vars_drop(v, v->n - n);
3035 pa = isl_pw_aff_union_add(pa, pa_i);
3038 if (isl_stream_eat(s, '}'))
3039 goto error;
3041 vars_free(v);
3042 isl_set_free(dom);
3043 return pa;
3044 error:
3045 vars_free(v);
3046 isl_set_free(dom);
3047 isl_pw_aff_free(pa);
3048 return NULL;
3051 __isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str)
3053 isl_aff *aff;
3054 struct isl_stream *s = isl_stream_new_str(ctx, str);
3055 if (!s)
3056 return NULL;
3057 aff = isl_stream_read_aff(s);
3058 isl_stream_free(s);
3059 return aff;
3062 __isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str)
3064 isl_pw_aff *pa;
3065 struct isl_stream *s = isl_stream_new_str(ctx, str);
3066 if (!s)
3067 return NULL;
3068 pa = isl_stream_read_pw_aff(s);
3069 isl_stream_free(s);
3070 return pa;
3073 /* Read an isl_pw_multi_aff from "s".
3074 * We currently read a generic object and if it turns out to be a set or
3075 * a map, we convert that to an isl_pw_multi_aff.
3076 * It would be more efficient if we were to construct the isl_pw_multi_aff
3077 * directly.
3079 __isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(struct isl_stream *s)
3081 struct isl_obj obj;
3083 obj = obj_read(s);
3084 if (!obj.v)
3085 return NULL;
3087 if (obj.type == isl_obj_map)
3088 return isl_pw_multi_aff_from_map(obj.v);
3089 if (obj.type == isl_obj_set)
3090 return isl_pw_multi_aff_from_set(obj.v);
3092 obj.type->free(obj.v);
3093 isl_die(s->ctx, isl_error_invalid, "unexpected object type",
3094 return NULL);
3097 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx,
3098 const char *str)
3100 isl_pw_multi_aff *pma;
3101 struct isl_stream *s = isl_stream_new_str(ctx, str);
3102 if (!s)
3103 return NULL;
3104 pma = isl_stream_read_pw_multi_aff(s);
3105 isl_stream_free(s);
3106 return pma;
3109 /* Read an isl_union_pw_multi_aff from "s".
3110 * We currently read a generic object and if it turns out to be a set or
3111 * a map, we convert that to an isl_union_pw_multi_aff.
3112 * It would be more efficient if we were to construct
3113 * the isl_union_pw_multi_aff directly.
3115 __isl_give isl_union_pw_multi_aff *isl_stream_read_union_pw_multi_aff(
3116 struct isl_stream *s)
3118 struct isl_obj obj;
3120 obj = obj_read(s);
3121 if (!obj.v)
3122 return NULL;
3124 if (obj.type == isl_obj_map || obj.type == isl_obj_set)
3125 obj = to_union(s->ctx, obj);
3126 if (obj.type == isl_obj_union_map)
3127 return isl_union_pw_multi_aff_from_union_map(obj.v);
3128 if (obj.type == isl_obj_union_set)
3129 return isl_union_pw_multi_aff_from_union_set(obj.v);
3131 obj.type->free(obj.v);
3132 isl_die(s->ctx, isl_error_invalid, "unexpected object type",
3133 return NULL);
3136 /* Read an isl_union_pw_multi_aff from "str".
3138 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_read_from_str(
3139 isl_ctx *ctx, const char *str)
3141 isl_union_pw_multi_aff *upma;
3142 struct isl_stream *s = isl_stream_new_str(ctx, str);
3143 if (!s)
3144 return NULL;
3145 upma = isl_stream_read_union_pw_multi_aff(s);
3146 isl_stream_free(s);
3147 return upma;
3150 /* Assuming "pa" represents a single affine expression defined on a universe
3151 * domain, extract this affine expression.
3153 static __isl_give isl_aff *aff_from_pw_aff(__isl_take isl_pw_aff *pa)
3155 isl_aff *aff;
3157 if (!pa)
3158 return NULL;
3159 if (pa->n != 1)
3160 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
3161 "expecting single affine expression",
3162 goto error);
3163 if (!isl_set_plain_is_universe(pa->p[0].set))
3164 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
3165 "expecting universe domain",
3166 goto error);
3168 aff = isl_aff_copy(pa->p[0].aff);
3169 isl_pw_aff_free(pa);
3170 return aff;
3171 error:
3172 isl_pw_aff_free(pa);
3173 return NULL;
3176 /* This function is called for each element in a tuple inside
3177 * isl_stream_read_multi_val.
3178 * Read an isl_val from "s" and add it to *list.
3180 static __isl_give isl_space *read_val_el(struct isl_stream *s,
3181 struct vars *v, __isl_take isl_space *space, int rational, void *user)
3183 isl_val_list **list = (isl_val_list **) user;
3184 isl_val *val;
3186 val = isl_stream_read_val(s);
3187 *list = isl_val_list_add(*list, val);
3188 if (!*list)
3189 return isl_space_free(space);
3191 return space;
3194 /* Read an isl_multi_val from "s".
3196 * We first read a tuple space, collecting the element values in a list.
3197 * Then we create an isl_multi_val from the space and the isl_val_list.
3199 __isl_give isl_multi_val *isl_stream_read_multi_val(struct isl_stream *s)
3201 struct vars *v;
3202 isl_set *dom = NULL;
3203 isl_space *space;
3204 isl_multi_val *mv = NULL;
3205 isl_val_list *list;
3207 v = vars_new(s->ctx);
3208 if (!v)
3209 return NULL;
3211 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3212 if (next_is_tuple(s)) {
3213 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3214 if (isl_stream_eat(s, ISL_TOKEN_TO))
3215 goto error;
3217 if (!isl_set_plain_is_universe(dom))
3218 isl_die(s->ctx, isl_error_invalid,
3219 "expecting universe parameter domain", goto error);
3220 if (isl_stream_eat(s, '{'))
3221 goto error;
3223 space = isl_set_get_space(dom);
3225 list = isl_val_list_alloc(s->ctx, 0);
3226 space = read_tuple_space(s, v, space, 1, 0, &read_val_el, &list);
3227 mv = isl_multi_val_from_val_list(space, list);
3229 if (isl_stream_eat(s, '}'))
3230 goto error;
3232 vars_free(v);
3233 isl_set_free(dom);
3234 return mv;
3235 error:
3236 vars_free(v);
3237 isl_set_free(dom);
3238 isl_multi_val_free(mv);
3239 return NULL;
3242 /* Read an isl_multi_val from "str".
3244 __isl_give isl_multi_val *isl_multi_val_read_from_str(isl_ctx *ctx,
3245 const char *str)
3247 isl_multi_val *mv;
3248 struct isl_stream *s = isl_stream_new_str(ctx, str);
3249 if (!s)
3250 return NULL;
3251 mv = isl_stream_read_multi_val(s);
3252 isl_stream_free(s);
3253 return mv;
3256 /* Read a multi-affine expression from "s".
3257 * If the multi-affine expression has a domain, then the tuple
3258 * representing this domain cannot involve any affine expressions.
3259 * The tuple representing the actual expressions needs to consist
3260 * of only affine expressions. Moreover, these expressions can
3261 * only depend on parameters and input dimensions and not on other
3262 * output dimensions.
3264 __isl_give isl_multi_aff *isl_stream_read_multi_aff(struct isl_stream *s)
3266 struct vars *v;
3267 isl_set *dom = NULL;
3268 isl_multi_pw_aff *tuple = NULL;
3269 int dim, i, n;
3270 isl_space *space, *dom_space;
3271 isl_multi_aff *ma = NULL;
3273 v = vars_new(s->ctx);
3274 if (!v)
3275 return NULL;
3277 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3278 if (next_is_tuple(s)) {
3279 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3280 if (isl_stream_eat(s, ISL_TOKEN_TO))
3281 goto error;
3283 if (!isl_set_plain_is_universe(dom))
3284 isl_die(s->ctx, isl_error_invalid,
3285 "expecting universe parameter domain", goto error);
3286 if (isl_stream_eat(s, '{'))
3287 goto error;
3289 tuple = read_tuple(s, v, 0, 0);
3290 if (!tuple)
3291 goto error;
3292 if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {
3293 isl_set *set;
3294 isl_space *space;
3295 int has_expr;
3297 has_expr = tuple_has_expr(tuple);
3298 if (has_expr < 0)
3299 goto error;
3300 if (has_expr)
3301 isl_die(s->ctx, isl_error_invalid,
3302 "expecting universe domain", goto error);
3303 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3304 set = isl_set_universe(space);
3305 dom = isl_set_intersect_params(set, dom);
3306 isl_multi_pw_aff_free(tuple);
3307 tuple = read_tuple(s, v, 0, 0);
3308 if (!tuple)
3309 goto error;
3312 if (isl_stream_eat(s, '}'))
3313 goto error;
3315 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
3316 dim = isl_set_dim(dom, isl_dim_all);
3317 dom_space = isl_set_get_space(dom);
3318 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3319 space = isl_space_align_params(space, isl_space_copy(dom_space));
3320 if (!isl_space_is_params(dom_space))
3321 space = isl_space_map_from_domain_and_range(
3322 isl_space_copy(dom_space), space);
3323 isl_space_free(dom_space);
3324 ma = isl_multi_aff_alloc(space);
3326 for (i = 0; i < n; ++i) {
3327 isl_pw_aff *pa;
3328 isl_aff *aff;
3329 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
3330 aff = aff_from_pw_aff(pa);
3331 if (!aff)
3332 goto error;
3333 if (isl_aff_involves_dims(aff, isl_dim_in, dim, i + 1)) {
3334 isl_aff_free(aff);
3335 isl_die(s->ctx, isl_error_invalid,
3336 "not an affine expression", goto error);
3338 aff = isl_aff_drop_dims(aff, isl_dim_in, dim, n);
3339 space = isl_multi_aff_get_domain_space(ma);
3340 aff = isl_aff_reset_domain_space(aff, space);
3341 ma = isl_multi_aff_set_aff(ma, i, aff);
3344 isl_multi_pw_aff_free(tuple);
3345 vars_free(v);
3346 isl_set_free(dom);
3347 return ma;
3348 error:
3349 isl_multi_pw_aff_free(tuple);
3350 vars_free(v);
3351 isl_set_free(dom);
3352 isl_multi_aff_free(ma);
3353 return NULL;
3356 __isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx,
3357 const char *str)
3359 isl_multi_aff *maff;
3360 struct isl_stream *s = isl_stream_new_str(ctx, str);
3361 if (!s)
3362 return NULL;
3363 maff = isl_stream_read_multi_aff(s);
3364 isl_stream_free(s);
3365 return maff;
3368 /* Read an isl_multi_pw_aff from "s".
3370 * The input format is similar to that of map, except that any conditions
3371 * on the domains should be specified inside the tuple since each
3372 * piecewise affine expression may have a different domain.
3374 * Since we do not know in advance if the isl_multi_pw_aff lives
3375 * in a set or a map space, we first read the first tuple and check
3376 * if it is followed by a "->". If so, we convert the tuple into
3377 * the domain of the isl_multi_pw_aff and read in the next tuple.
3378 * This tuple (or the first tuple if it was not followed by a "->")
3379 * is then converted into the isl_multi_pw_aff.
3381 * Note that the function read_tuple accepts tuples where some output or
3382 * set dimensions are defined in terms of other output or set dimensions
3383 * since this function is also used to read maps. As a special case,
3384 * read_tuple also accept dimensions that are defined in terms of themselves
3385 * (i.e., that are not defined).
3386 * These cases are not allowed when reading am isl_multi_pw_aff so we check
3387 * that the definition of the output/set dimensions does not involve any
3388 * output/set dimensions.
3389 * We then drop the output dimensions from the domain of the result
3390 * of read_tuple (which is of the form [input, output] -> [output],
3391 * with anonymous domain) and reset the space.
3393 __isl_give isl_multi_pw_aff *isl_stream_read_multi_pw_aff(struct isl_stream *s)
3395 struct vars *v;
3396 isl_set *dom = NULL;
3397 isl_multi_pw_aff *tuple = NULL;
3398 int dim, i, n;
3399 isl_space *space, *dom_space;
3400 isl_multi_pw_aff *mpa = NULL;
3402 v = vars_new(s->ctx);
3403 if (!v)
3404 return NULL;
3406 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3407 if (next_is_tuple(s)) {
3408 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3409 if (isl_stream_eat(s, ISL_TOKEN_TO))
3410 goto error;
3412 if (isl_stream_eat(s, '{'))
3413 goto error;
3415 tuple = read_tuple(s, v, 0, 0);
3416 if (!tuple)
3417 goto error;
3418 if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {
3419 isl_map *map = map_from_tuple(tuple, dom, isl_dim_in, v, 0);
3420 dom = isl_map_domain(map);
3421 tuple = read_tuple(s, v, 0, 0);
3422 if (!tuple)
3423 goto error;
3426 if (isl_stream_eat(s, '}'))
3427 goto error;
3429 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
3430 dim = isl_set_dim(dom, isl_dim_all);
3431 dom_space = isl_set_get_space(dom);
3432 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3433 space = isl_space_align_params(space, isl_space_copy(dom_space));
3434 if (!isl_space_is_params(dom_space))
3435 space = isl_space_map_from_domain_and_range(
3436 isl_space_copy(dom_space), space);
3437 isl_space_free(dom_space);
3438 mpa = isl_multi_pw_aff_alloc(space);
3440 for (i = 0; i < n; ++i) {
3441 isl_pw_aff *pa;
3442 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
3443 if (!pa)
3444 goto error;
3445 if (isl_pw_aff_involves_dims(pa, isl_dim_in, dim, i + 1)) {
3446 isl_pw_aff_free(pa);
3447 isl_die(s->ctx, isl_error_invalid,
3448 "not an affine expression", goto error);
3450 pa = isl_pw_aff_drop_dims(pa, isl_dim_in, dim, n);
3451 space = isl_multi_pw_aff_get_domain_space(mpa);
3452 pa = isl_pw_aff_reset_domain_space(pa, space);
3453 mpa = isl_multi_pw_aff_set_pw_aff(mpa, i, pa);
3456 isl_multi_pw_aff_free(tuple);
3457 vars_free(v);
3458 mpa = isl_multi_pw_aff_intersect_domain(mpa, dom);
3459 return mpa;
3460 error:
3461 isl_multi_pw_aff_free(tuple);
3462 vars_free(v);
3463 isl_set_free(dom);
3464 isl_multi_pw_aff_free(mpa);
3465 return NULL;
3468 /* Read an isl_multi_pw_aff from "str".
3470 __isl_give isl_multi_pw_aff *isl_multi_pw_aff_read_from_str(isl_ctx *ctx,
3471 const char *str)
3473 isl_multi_pw_aff *mpa;
3474 struct isl_stream *s = isl_stream_new_str(ctx, str);
3475 if (!s)
3476 return NULL;
3477 mpa = isl_stream_read_multi_pw_aff(s);
3478 isl_stream_free(s);
3479 return mpa;
3482 __isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial(
3483 struct isl_stream *s)
3485 struct isl_obj obj;
3487 obj = obj_read(s);
3488 if (obj.type == isl_obj_pw_qpolynomial) {
3489 obj.type = isl_obj_union_pw_qpolynomial;
3490 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
3492 if (obj.v)
3493 isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial,
3494 goto error);
3496 return obj.v;
3497 error:
3498 obj.type->free(obj.v);
3499 return NULL;
3502 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str(
3503 isl_ctx *ctx, const char *str)
3505 isl_union_pw_qpolynomial *upwqp;
3506 struct isl_stream *s = isl_stream_new_str(ctx, str);
3507 if (!s)
3508 return NULL;
3509 upwqp = isl_stream_read_union_pw_qpolynomial(s);
3510 isl_stream_free(s);
3511 return upwqp;