2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 * Copyright 2012-2013 Ecole Normale Superieure
5 * Copyright 2019,2022 Cerebras Systems
7 * Use of this software is governed by the MIT license
9 * Written by Sven Verdoolaege, K.U.Leuven, Departement
10 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
11 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
12 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
13 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14 * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA
20 #include <isl_ctx_private.h>
21 #include <isl_map_private.h>
22 #include <isl_id_private.h>
25 #include <isl_stream_private.h>
27 #include "isl_polynomial_private.h"
28 #include <isl/union_set.h>
29 #include <isl/union_map.h>
30 #include <isl_mat_private.h>
31 #include <isl_aff_private.h>
32 #include <isl_vec_private.h>
34 #include <isl_val_private.h>
39 struct variable
*next
;
48 static struct vars
*vars_new(struct isl_ctx
*ctx
)
51 v
= isl_alloc_type(ctx
, struct vars
);
60 static void variable_free(struct variable
*var
)
63 struct variable
*next
= var
->next
;
70 static void vars_free(struct vars
*v
)
78 static void vars_drop(struct vars
*v
, int n
)
89 struct variable
*next
= var
->next
;
97 static struct variable
*variable_new(struct vars
*v
, const char *name
, int len
,
100 struct variable
*var
;
101 var
= isl_calloc_type(v
->ctx
, struct variable
);
104 var
->name
= strdup(name
);
105 var
->name
[len
] = '\0';
114 static int vars_pos(struct vars
*v
, const char *s
, int len
)
121 for (q
= v
->v
; q
; q
= q
->next
) {
122 if (strncmp(q
->name
, s
, len
) == 0 && q
->name
[len
] == '\0')
129 v
->v
= variable_new(v
, s
, len
, v
->n
);
137 static int vars_add_anon(struct vars
*v
)
139 v
->v
= variable_new(v
, "", 0, v
->n
);
148 /* Obtain next token, with some preprocessing.
149 * In particular, evaluate expressions of the form x^y,
150 * with x and y values.
152 static struct isl_token
*next_token(__isl_keep isl_stream
*s
)
154 struct isl_token
*tok
, *tok2
;
156 tok
= isl_stream_next_token(s
);
157 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
)
159 if (!isl_stream_eat_if_available(s
, '^'))
161 tok2
= isl_stream_next_token(s
);
162 if (!tok2
|| tok2
->type
!= ISL_TOKEN_VALUE
) {
163 isl_stream_error(s
, tok2
, "expecting constant value");
167 isl_int_pow_ui(tok
->u
.v
, tok
->u
.v
, isl_int_get_ui(tok2
->u
.v
));
169 isl_token_free(tok2
);
173 isl_token_free(tok2
);
177 /* Read an isl_val from "s".
179 * The following token sequences are recognized
182 * "-" "infty" -> -infty
187 * where n, d and v are integer constants.
189 __isl_give isl_val
*isl_stream_read_val(__isl_keep isl_stream
*s
)
191 struct isl_token
*tok
= NULL
;
192 struct isl_token
*tok2
= NULL
;
197 isl_stream_error(s
, NULL
, "unexpected EOF");
200 if (tok
->type
== ISL_TOKEN_INFTY
) {
202 return isl_val_infty(s
->ctx
);
204 if (tok
->type
== '-' &&
205 isl_stream_eat_if_available(s
, ISL_TOKEN_INFTY
)) {
207 return isl_val_neginfty(s
->ctx
);
209 if (tok
->type
== ISL_TOKEN_NAN
) {
211 return isl_val_nan(s
->ctx
);
213 if (tok
->type
!= ISL_TOKEN_VALUE
) {
214 isl_stream_error(s
, tok
, "expecting value");
218 if (isl_stream_eat_if_available(s
, '/')) {
219 tok2
= next_token(s
);
221 isl_stream_error(s
, NULL
, "unexpected EOF");
224 if (tok2
->type
!= ISL_TOKEN_VALUE
) {
225 isl_stream_error(s
, tok2
, "expecting value");
228 val
= isl_val_rat_from_isl_int(s
->ctx
, tok
->u
.v
, tok2
->u
.v
);
229 val
= isl_val_normalize(val
);
231 val
= isl_val_int_from_isl_int(s
->ctx
, tok
->u
.v
);
235 isl_token_free(tok2
);
239 isl_token_free(tok2
);
243 /* Read an isl_val from "str".
245 __isl_give isl_val
*isl_val_read_from_str(isl_ctx
*ctx
, const char *str
)
248 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
251 val
= isl_stream_read_val(s
);
256 /* Perform an integer division on *f and
257 * an integer value read from the stream.
259 static isl_stat
int_div_by_cst(__isl_keep isl_stream
*s
, isl_int
*f
)
261 struct isl_token
*tok
;
264 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
265 isl_stream_error(s
, tok
, "expecting constant value");
269 isl_int_fdiv_q(*f
, *f
, tok
->u
.v
);
276 return isl_stat_error
;
279 static isl_stat
accept_cst_factor(__isl_keep isl_stream
*s
, isl_int
*f
)
281 struct isl_token
*tok
;
284 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
285 isl_stream_error(s
, tok
, "expecting constant value");
289 isl_int_mul(*f
, *f
, tok
->u
.v
);
293 if (isl_stream_eat_if_available(s
, '*'))
294 return accept_cst_factor(s
, f
);
299 return isl_stat_error
;
302 /* Given an affine expression aff, return an affine expression
303 * for aff % d, with d the next token on the stream, which is
304 * assumed to be a constant.
306 * We introduce an integer division q = [aff/d] and the result
307 * is set to aff - d q.
309 static __isl_give isl_pw_aff
*affine_mod(__isl_keep isl_stream
*s
,
310 struct vars
*v
, __isl_take isl_pw_aff
*aff
)
312 struct isl_token
*tok
;
316 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
317 isl_stream_error(s
, tok
, "expecting constant value");
321 q
= isl_pw_aff_copy(aff
);
322 q
= isl_pw_aff_scale_down(q
, tok
->u
.v
);
323 q
= isl_pw_aff_floor(q
);
324 q
= isl_pw_aff_scale(q
, tok
->u
.v
);
326 aff
= isl_pw_aff_sub(aff
, q
);
331 isl_pw_aff_free(aff
);
336 static __isl_give isl_pw_aff
*accept_affine(__isl_keep isl_stream
*s
,
337 __isl_take isl_space
*space
, struct vars
*v
);
338 static __isl_give isl_pw_aff_list
*accept_affine_list(__isl_keep isl_stream
*s
,
339 __isl_take isl_space
*space
, struct vars
*v
);
341 static __isl_give isl_pw_aff
*accept_minmax(__isl_keep isl_stream
*s
,
342 __isl_take isl_space
*space
, struct vars
*v
)
344 struct isl_token
*tok
;
345 isl_pw_aff_list
*list
= NULL
;
348 tok
= isl_stream_next_token(s
);
351 min
= tok
->type
== ISL_TOKEN_MIN
;
354 if (isl_stream_eat(s
, '('))
357 list
= accept_affine_list(s
, isl_space_copy(space
), v
);
361 if (isl_stream_eat(s
, ')'))
364 isl_space_free(space
);
365 return min
? isl_pw_aff_list_min(list
) : isl_pw_aff_list_max(list
);
367 isl_space_free(space
);
368 isl_pw_aff_list_free(list
);
372 /* Is "tok" the start of an integer division?
374 static int is_start_of_div(struct isl_token
*tok
)
378 if (tok
->type
== '[')
380 if (tok
->type
== ISL_TOKEN_FLOOR
)
382 if (tok
->type
== ISL_TOKEN_CEIL
)
384 if (tok
->type
== ISL_TOKEN_FLOORD
)
386 if (tok
->type
== ISL_TOKEN_CEILD
)
391 /* Read an integer division from "s" and return it as an isl_pw_aff.
393 * The integer division can be of the form
395 * [<affine expression>]
396 * floor(<affine expression>)
397 * ceil(<affine expression>)
398 * floord(<affine expression>,<denominator>)
399 * ceild(<affine expression>,<denominator>)
401 static __isl_give isl_pw_aff
*accept_div(__isl_keep isl_stream
*s
,
402 __isl_take isl_space
*space
, struct vars
*v
)
404 struct isl_token
*tok
;
408 isl_pw_aff
*pwaff
= NULL
;
410 if (isl_stream_eat_if_available(s
, ISL_TOKEN_FLOORD
))
412 else if (isl_stream_eat_if_available(s
, ISL_TOKEN_CEILD
))
414 else if (isl_stream_eat_if_available(s
, ISL_TOKEN_FLOOR
))
416 else if (isl_stream_eat_if_available(s
, ISL_TOKEN_CEIL
))
419 if (isl_stream_eat(s
, '('))
422 if (isl_stream_eat(s
, '['))
426 pwaff
= accept_affine(s
, isl_space_copy(space
), v
);
429 if (isl_stream_eat(s
, ','))
435 if (tok
->type
!= ISL_TOKEN_VALUE
) {
436 isl_stream_error(s
, tok
, "expected denominator");
437 isl_stream_push_token(s
, tok
);
440 pwaff
= isl_pw_aff_scale_down(pwaff
, tok
->u
.v
);
445 pwaff
= isl_pw_aff_ceil(pwaff
);
447 pwaff
= isl_pw_aff_floor(pwaff
);
450 if (isl_stream_eat(s
, ')'))
453 if (isl_stream_eat(s
, ']'))
457 isl_space_free(space
);
460 isl_space_free(space
);
461 isl_pw_aff_free(pwaff
);
465 /* Divide "pa" by an integer constant read from the stream.
467 static __isl_give isl_pw_aff
*pw_aff_div_by_cst(__isl_keep isl_stream
*s
,
468 __isl_take isl_pw_aff
*pa
)
472 isl_int_set_si(f
, 1);
473 if (accept_cst_factor(s
, &f
) < 0)
474 pa
= isl_pw_aff_free(pa
);
475 pa
= isl_pw_aff_scale_down(pa
, f
);
481 static __isl_give isl_pw_aff
*accept_affine_factor(__isl_keep isl_stream
*s
,
482 __isl_take isl_space
*space
, struct vars
*v
)
484 struct isl_token
*tok
= NULL
;
485 isl_pw_aff
*res
= NULL
;
489 isl_stream_error(s
, NULL
, "unexpected EOF");
493 if (tok
->type
== ISL_TOKEN_AFF
) {
494 res
= isl_pw_aff_copy(tok
->u
.pwaff
);
496 } else if (tok
->type
== ISL_TOKEN_IDENT
) {
498 int pos
= vars_pos(v
, tok
->u
.s
, -1);
504 vars_drop(v
, v
->n
- n
);
505 isl_stream_error(s
, tok
, "unknown identifier");
509 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(isl_space_copy(space
)));
512 aff
->v
= isl_vec_set_element_si(aff
->v
, 2 + pos
, 1);
514 aff
= isl_aff_free(aff
);
515 res
= isl_pw_aff_from_aff(aff
);
517 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
518 if (isl_stream_eat_if_available(s
, '*')) {
519 res
= accept_affine_factor(s
, isl_space_copy(space
), v
);
520 res
= isl_pw_aff_scale(res
, tok
->u
.v
);
524 ls
= isl_local_space_from_space(isl_space_copy(space
));
525 aff
= isl_aff_zero_on_domain(ls
);
526 aff
= isl_aff_add_constant(aff
, tok
->u
.v
);
527 res
= isl_pw_aff_from_aff(aff
);
530 } else if (tok
->type
== '(') {
533 res
= accept_affine(s
, isl_space_copy(space
), v
);
536 if (isl_stream_eat(s
, ')'))
538 } else if (is_start_of_div(tok
)) {
539 isl_stream_push_token(s
, tok
);
541 res
= accept_div(s
, isl_space_copy(space
), v
);
542 } else if (tok
->type
== ISL_TOKEN_MIN
|| tok
->type
== ISL_TOKEN_MAX
) {
543 isl_stream_push_token(s
, tok
);
545 res
= accept_minmax(s
, isl_space_copy(space
), v
);
547 isl_stream_error(s
, tok
, "expecting factor");
550 if (isl_stream_eat_if_available(s
, '%') ||
551 isl_stream_eat_if_available(s
, ISL_TOKEN_MOD
)) {
552 isl_space_free(space
);
553 return affine_mod(s
, v
, res
);
555 if (isl_stream_eat_if_available(s
, '*')) {
558 isl_int_set_si(f
, 1);
559 if (accept_cst_factor(s
, &f
) < 0) {
563 res
= isl_pw_aff_scale(res
, f
);
566 if (isl_stream_eat_if_available(s
, '/'))
567 res
= pw_aff_div_by_cst(s
, res
);
568 if (isl_stream_eat_if_available(s
, ISL_TOKEN_INT_DIV
))
569 res
= isl_pw_aff_floor(pw_aff_div_by_cst(s
, res
));
571 isl_space_free(space
);
576 isl_pw_aff_free(res
);
577 isl_space_free(space
);
581 static __isl_give isl_pw_aff
*add_cst(__isl_take isl_pw_aff
*pwaff
, isl_int v
)
586 space
= isl_pw_aff_get_domain_space(pwaff
);
587 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
588 aff
= isl_aff_add_constant(aff
, v
);
590 return isl_pw_aff_add(pwaff
, isl_pw_aff_from_aff(aff
));
593 /* Return a piecewise affine expression defined on the specified domain
594 * that represents NaN.
596 static __isl_give isl_pw_aff
*nan_on_domain(__isl_keep isl_space
*space
)
598 return isl_pw_aff_nan_on_domain_space(isl_space_copy(space
));
601 static __isl_give isl_pw_aff
*accept_affine(__isl_keep isl_stream
*s
,
602 __isl_take isl_space
*space
, struct vars
*v
)
604 struct isl_token
*tok
= NULL
;
609 ls
= isl_local_space_from_space(isl_space_copy(space
));
610 res
= isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls
));
617 isl_stream_error(s
, NULL
, "unexpected EOF");
620 if (tok
->type
== '-') {
625 if (tok
->type
== '(' || is_start_of_div(tok
) ||
626 tok
->type
== ISL_TOKEN_MIN
|| tok
->type
== ISL_TOKEN_MAX
||
627 tok
->type
== ISL_TOKEN_IDENT
||
628 tok
->type
== ISL_TOKEN_AFF
) {
630 isl_stream_push_token(s
, tok
);
632 term
= accept_affine_factor(s
,
633 isl_space_copy(space
), v
);
635 res
= isl_pw_aff_sub(res
, term
);
637 res
= isl_pw_aff_add(res
, term
);
641 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
643 isl_int_neg(tok
->u
.v
, tok
->u
.v
);
644 if (isl_stream_eat_if_available(s
, '*') ||
645 isl_stream_next_token_is(s
, ISL_TOKEN_IDENT
)) {
647 term
= accept_affine_factor(s
,
648 isl_space_copy(space
), v
);
649 term
= isl_pw_aff_scale(term
, tok
->u
.v
);
650 res
= isl_pw_aff_add(res
, term
);
654 if (isl_stream_eat_if_available(s
,
655 ISL_TOKEN_INT_DIV
) &&
656 int_div_by_cst(s
, &tok
->u
.v
) < 0)
658 res
= add_cst(res
, tok
->u
.v
);
661 } else if (tok
->type
== ISL_TOKEN_NAN
) {
662 res
= isl_pw_aff_add(res
, nan_on_domain(space
));
664 isl_stream_error(s
, tok
, "unexpected isl_token");
665 isl_stream_push_token(s
, tok
);
666 isl_pw_aff_free(res
);
667 isl_space_free(space
);
673 if (tok
&& tok
->type
== '-') {
676 } else if (tok
&& tok
->type
== '+') {
679 } else if (tok
&& tok
->type
== ISL_TOKEN_VALUE
&&
680 isl_int_is_neg(tok
->u
.v
)) {
681 isl_stream_push_token(s
, tok
);
684 isl_stream_push_token(s
, tok
);
689 isl_space_free(space
);
692 isl_space_free(space
);
694 isl_pw_aff_free(res
);
698 /* Is "type" the type of a comparison operator between lists
699 * of affine expressions?
701 static int is_list_comparator_type(int type
)
704 case ISL_TOKEN_LEX_LT
:
705 case ISL_TOKEN_LEX_GT
:
706 case ISL_TOKEN_LEX_LE
:
707 case ISL_TOKEN_LEX_GE
:
714 static int is_comparator(struct isl_token
*tok
)
718 if (is_list_comparator_type(tok
->type
))
734 static __isl_give isl_map
*read_formula(__isl_keep isl_stream
*s
,
735 struct vars
*v
, __isl_take isl_map
*map
, int rational
);
736 static __isl_give isl_pw_aff
*accept_extended_affine(__isl_keep isl_stream
*s
,
737 __isl_take isl_space
*space
, struct vars
*v
, int rational
);
739 /* Accept a ternary operator, given the first argument.
741 static __isl_give isl_pw_aff
*accept_ternary(__isl_keep isl_stream
*s
,
742 __isl_take isl_map
*cond
, struct vars
*v
, int rational
)
745 isl_pw_aff
*pwaff1
= NULL
, *pwaff2
= NULL
, *pa_cond
;
750 if (isl_stream_eat(s
, '?'))
753 space
= isl_space_wrap(isl_map_get_space(cond
));
754 pwaff1
= accept_extended_affine(s
, space
, v
, rational
);
758 if (isl_stream_eat(s
, ':'))
761 space
= isl_pw_aff_get_domain_space(pwaff1
);
762 pwaff2
= accept_extended_affine(s
, space
, v
, rational
);
766 pa_cond
= isl_set_indicator_function(isl_map_wrap(cond
));
767 return isl_pw_aff_cond(pa_cond
, pwaff1
, pwaff2
);
770 isl_pw_aff_free(pwaff1
);
771 isl_pw_aff_free(pwaff2
);
775 /* Set *line and *col to those of the next token, if any.
777 static void set_current_line_col(__isl_keep isl_stream
*s
, int *line
, int *col
)
779 struct isl_token
*tok
;
781 tok
= isl_stream_next_token(s
);
787 isl_stream_push_token(s
, tok
);
790 /* Push a token encapsulating "pa" onto "s", with the given
793 static isl_stat
push_aff(__isl_keep isl_stream
*s
, int line
, int col
,
794 __isl_take isl_pw_aff
*pa
)
796 struct isl_token
*tok
;
798 tok
= isl_token_new(s
->ctx
, line
, col
, 0);
801 tok
->type
= ISL_TOKEN_AFF
;
803 isl_stream_push_token(s
, tok
);
808 return isl_stat_error
;
811 /* Is the next token a comparison operator?
813 static int next_is_comparator(__isl_keep isl_stream
*s
)
816 struct isl_token
*tok
;
818 tok
= isl_stream_next_token(s
);
822 is_comp
= is_comparator(tok
);
823 isl_stream_push_token(s
, tok
);
828 /* Accept an affine expression that may involve ternary operators.
829 * We first read an affine expression.
830 * If it is not followed by a comparison operator, we simply return it.
831 * Otherwise, we assume the affine expression is part of the first
832 * argument of a ternary operator and try to parse that.
834 static __isl_give isl_pw_aff
*accept_extended_affine(__isl_keep isl_stream
*s
,
835 __isl_take isl_space
*space
, struct vars
*v
, int rational
)
839 int line
= -1, col
= -1;
841 set_current_line_col(s
, &line
, &col
);
843 pwaff
= accept_affine(s
, space
, v
);
845 pwaff
= isl_pw_aff_set_rational(pwaff
);
848 if (!next_is_comparator(s
))
851 space
= isl_pw_aff_get_domain_space(pwaff
);
852 cond
= isl_map_universe(isl_space_unwrap(space
));
854 if (push_aff(s
, line
, col
, pwaff
) < 0)
855 cond
= isl_map_free(cond
);
859 cond
= read_formula(s
, v
, cond
, rational
);
861 return accept_ternary(s
, cond
, v
, rational
);
864 static __isl_give isl_map
*read_var_def(__isl_keep isl_stream
*s
,
865 __isl_take isl_map
*map
, enum isl_dim_type type
, struct vars
*v
,
872 if (type
== isl_dim_param
)
873 pos
= isl_map_dim(map
, isl_dim_param
);
875 pos
= isl_map_dim(map
, isl_dim_in
);
876 if (type
== isl_dim_out
) {
877 isl_size n_out
= isl_map_dim(map
, isl_dim_out
);
878 if (pos
< 0 || n_out
< 0)
879 return isl_map_free(map
);
885 return isl_map_free(map
);
888 def
= accept_extended_affine(s
, isl_space_wrap(isl_map_get_space(map
)),
890 def_map
= isl_map_from_pw_aff(def
);
891 def_map
= isl_map_equate(def_map
, type
, pos
, isl_dim_out
, 0);
892 def_map
= isl_set_unwrap(isl_map_domain(def_map
));
894 map
= isl_map_intersect(map
, def_map
);
899 static __isl_give isl_pw_aff_list
*accept_affine_list(__isl_keep isl_stream
*s
,
900 __isl_take isl_space
*space
, struct vars
*v
)
903 isl_pw_aff_list
*list
;
904 struct isl_token
*tok
= NULL
;
906 pwaff
= accept_affine(s
, isl_space_copy(space
), v
);
907 list
= isl_pw_aff_list_from_pw_aff(pwaff
);
912 tok
= isl_stream_next_token(s
);
914 isl_stream_error(s
, NULL
, "unexpected EOF");
917 if (tok
->type
!= ',') {
918 isl_stream_push_token(s
, tok
);
923 pwaff
= accept_affine(s
, isl_space_copy(space
), v
);
924 list
= isl_pw_aff_list_concat(list
,
925 isl_pw_aff_list_from_pw_aff(pwaff
));
930 isl_space_free(space
);
933 isl_space_free(space
);
934 isl_pw_aff_list_free(list
);
938 static __isl_give isl_map
*read_defined_var_list(__isl_keep isl_stream
*s
,
939 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
941 struct isl_token
*tok
;
943 while ((tok
= isl_stream_next_token(s
)) != NULL
) {
947 if (tok
->type
!= ISL_TOKEN_IDENT
)
950 p
= vars_pos(v
, tok
->u
.s
, -1);
954 isl_stream_error(s
, tok
, "expecting unique identifier");
958 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
961 tok
= isl_stream_next_token(s
);
962 if (tok
&& tok
->type
== '=') {
964 map
= read_var_def(s
, map
, isl_dim_out
, v
, rational
);
965 tok
= isl_stream_next_token(s
);
968 if (!tok
|| tok
->type
!= ',')
974 isl_stream_push_token(s
, tok
);
983 static int next_is_tuple(__isl_keep isl_stream
*s
)
985 struct isl_token
*tok
;
988 tok
= isl_stream_next_token(s
);
991 if (tok
->type
== '[') {
992 isl_stream_push_token(s
, tok
);
995 if (tok
->type
!= ISL_TOKEN_IDENT
&& !tok
->is_keyword
) {
996 isl_stream_push_token(s
, tok
);
1000 is_tuple
= isl_stream_next_token_is(s
, '[');
1002 isl_stream_push_token(s
, tok
);
1007 /* Does the next token mark the end of a tuple element?
1009 static int next_is_end_tuple_element(__isl_keep isl_stream
*s
)
1011 return isl_stream_next_token_is(s
, ',') ||
1012 isl_stream_next_token_is(s
, ']');
1015 /* Is the next token one that necessarily forms the start of a condition?
1017 static int next_is_condition_start(__isl_keep isl_stream
*s
)
1019 return isl_stream_next_token_is(s
, ISL_TOKEN_EXISTS
) ||
1020 isl_stream_next_token_is(s
, ISL_TOKEN_NOT
) ||
1021 isl_stream_next_token_is(s
, ISL_TOKEN_TRUE
) ||
1022 isl_stream_next_token_is(s
, ISL_TOKEN_FALSE
) ||
1023 isl_stream_next_token_is(s
, ISL_TOKEN_MAP
);
1026 /* Is "pa" an expression in term of earlier dimensions?
1027 * The alternative is that the dimension is defined to be equal to itself,
1028 * meaning that it has a universe domain and an expression that depends
1029 * on itself. "i" is the position of the expression in a sequence
1030 * of "n" expressions. The final dimensions of "pa" correspond to
1031 * these "n" expressions.
1033 static isl_bool
pw_aff_is_expr(__isl_keep isl_pw_aff
*pa
, int i
, int n
)
1038 return isl_bool_error
;
1040 return isl_bool_true
;
1041 if (!isl_set_plain_is_universe(pa
->p
[0].set
))
1042 return isl_bool_true
;
1045 if (isl_int_is_zero(aff
->v
->el
[aff
->v
->size
- n
+ i
]))
1046 return isl_bool_true
;
1047 return isl_bool_false
;
1050 /* Does the tuple contain any dimensions that are defined
1051 * in terms of earlier dimensions?
1053 static isl_bool
tuple_has_expr(__isl_keep isl_multi_pw_aff
*tuple
)
1057 isl_bool has_expr
= isl_bool_false
;
1060 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
1062 return isl_bool_error
;
1063 for (i
= 0; i
< n
; ++i
) {
1064 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
1065 has_expr
= pw_aff_is_expr(pa
, i
, n
);
1066 isl_pw_aff_free(pa
);
1067 if (has_expr
< 0 || has_expr
)
1074 /* Set the name of dimension "pos" in "space" to "name".
1075 * During printing, we add primes if the same name appears more than once
1076 * to distinguish the occurrences. Here, we remove those primes from "name"
1077 * before setting the name of the dimension.
1079 static __isl_give isl_space
*space_set_dim_name(__isl_take isl_space
*space
,
1080 int pos
, char *name
)
1087 prime
= strchr(name
, '\'');
1090 space
= isl_space_set_dim_name(space
, isl_dim_out
, pos
, name
);
1097 /* Set the name of the last (output) dimension of "space" to "name",
1098 * ignoring any primes in "name".
1100 static __isl_give isl_space
*space_set_last_dim_name(
1101 __isl_take isl_space
*space
, char *name
)
1105 pos
= isl_space_dim(space
, isl_dim_out
);
1107 return isl_space_free(space
);
1108 return space_set_dim_name(space
, pos
- 1, name
);
1111 /* Construct an isl_pw_aff defined on a "space" (with v->n variables)
1112 * that is equal to the last of those variables.
1114 static __isl_give isl_pw_aff
*identity_tuple_el_on_space(
1115 __isl_take isl_space
*space
, struct vars
*v
)
1119 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
1120 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, v
->n
- 1, 1);
1121 return isl_pw_aff_from_aff(aff
);
1124 /* Construct an isl_pw_aff defined on the domain space of "pa"
1125 * that is equal to the last variable in "v".
1127 * That is, if D is the domain space of "pa", then construct
1131 static __isl_give isl_pw_aff
*init_range(__isl_keep isl_pw_aff
*pa
,
1136 space
= isl_pw_aff_get_domain_space(pa
);
1137 return identity_tuple_el_on_space(space
, v
);
1140 /* Impose the lower bound "lower" on the variable represented by "range_pa".
1142 * In particular, "range_pa" is of the form
1144 * D[..., i] -> i : C
1146 * with D also the domains space of "lower' and "C" some constraints.
1148 * Return the expression
1150 * D[..., i] -> i : C and i >= lower
1152 static __isl_give isl_pw_aff
*set_lower(__isl_take isl_pw_aff
*range_pa
,
1153 __isl_take isl_pw_aff
*lower
)
1157 range
= isl_pw_aff_ge_set(isl_pw_aff_copy(range_pa
), lower
);
1158 return isl_pw_aff_intersect_domain(range_pa
, range
);
1161 /* Impose the upper bound "upper" on the variable represented by "range_pa".
1163 * In particular, "range_pa" is of the form
1165 * D[..., i] -> i : C
1167 * with D also the domains space of "upper' and "C" some constraints.
1169 * Return the expression
1171 * D[..., i] -> i : C and i <= upper
1173 static __isl_give isl_pw_aff
*set_upper(__isl_take isl_pw_aff
*range_pa
,
1174 __isl_take isl_pw_aff
*upper
)
1178 range
= isl_pw_aff_le_set(isl_pw_aff_copy(range_pa
), upper
);
1179 return isl_pw_aff_intersect_domain(range_pa
, range
);
1182 /* Construct a piecewise affine expression corresponding
1183 * to the last variable in "v" that is greater than or equal to "pa".
1185 * In particular, if D is the domain space of "pa",
1186 * then construct the expression
1190 * impose lower bound "pa" and return
1192 * D[..., i] -> i : i >= pa
1194 static __isl_give isl_pw_aff
*construct_lower(__isl_take isl_pw_aff
*pa
,
1197 return set_lower(init_range(pa
, v
), pa
);
1200 /* Construct a piecewise affine expression corresponding
1201 * to the last variable in "v" that is smaller than or equal to "pa".
1203 * In particular, if D is the domain space of "pa",
1204 * then construct the expression
1208 * impose lower bound "pa" and return
1210 * D[..., i] -> i : i <= pa
1212 static __isl_give isl_pw_aff
*construct_upper(__isl_take isl_pw_aff
*pa
,
1215 return set_upper(init_range(pa
, v
), pa
);
1218 /* Construct a piecewise affine expression corresponding
1219 * to the last variable in "v" that ranges between "pa" and "pa2".
1221 * In particular, if D is the domain space of "pa" (and "pa2"),
1222 * then construct the expression
1226 * impose lower bound "pa" and upper bound "pa2" and return
1228 * D[..., i] -> i : pa <= i <= pa2
1230 static __isl_give isl_pw_aff
*construct_range(__isl_take isl_pw_aff
*pa
,
1231 __isl_take isl_pw_aff
*pa2
, struct vars
*v
)
1233 return set_upper(set_lower(init_range(pa
, v
), pa
), pa2
);
1236 static int resolve_paren_expr(__isl_keep isl_stream
*s
,
1237 struct vars
*v
, __isl_take isl_map
*map
, int rational
);
1239 /* Given that the (piecewise) affine expression "pa"
1240 * has just been parsed, followed by a colon,
1241 * continue parsing as part of a piecewise affine expression.
1243 * In particular, check if the colon is followed by a condition.
1244 * If so, parse the conditions(a) on "pa" and include them in the domain.
1245 * Otherwise, if the colon is followed by another (piecewise) affine expression
1246 * then consider the two expressions as endpoints of a range of values and
1247 * return a piecewise affine expression that takes values in that range.
1248 * Note that an affine expression followed by a comparison operator
1249 * is considered to be part of a condition.
1250 * If the colon is not followed by anything (inside the tuple element),
1251 * then consider "pa" as a lower bound on a range of values without upper bound
1252 * and return a piecewise affine expression that takes values in that range.
1254 static __isl_give isl_pw_aff
*update_piecewise_affine_colon(
1255 __isl_take isl_pw_aff
*pa
, __isl_keep isl_stream
*s
,
1256 struct vars
*v
, int rational
)
1258 isl_space
*dom_space
;
1261 dom_space
= isl_pw_aff_get_domain_space(pa
);
1262 map
= isl_map_universe(isl_space_from_domain(dom_space
));
1264 if (isl_stream_next_token_is(s
, '('))
1265 if (resolve_paren_expr(s
, v
, isl_map_copy(map
), rational
))
1267 if (next_is_end_tuple_element(s
)) {
1269 return construct_lower(pa
, v
);
1271 if (!next_is_condition_start(s
)) {
1272 int line
= -1, col
= -1;
1276 set_current_line_col(s
, &line
, &col
);
1277 space
= isl_space_wrap(isl_map_get_space(map
));
1278 pa2
= accept_affine(s
, space
, v
);
1280 pa2
= isl_pw_aff_set_rational(pa2
);
1281 if (!next_is_comparator(s
)) {
1283 pa2
= isl_pw_aff_domain_factor_domain(pa2
);
1284 return construct_range(pa
, pa2
, v
);
1286 if (push_aff(s
, line
, col
, pa2
) < 0)
1290 map
= read_formula(s
, v
, map
, rational
);
1291 pa
= isl_pw_aff_intersect_domain(pa
, isl_map_domain(map
));
1296 isl_pw_aff_free(pa
);
1300 /* Accept a piecewise affine expression.
1302 * At the outer level, the piecewise affine expression may be of the form
1304 * aff1 : condition1; aff2 : conditions2; ...
1317 * each of the affine expressions may in turn include ternary operators.
1319 * If the first token is a colon, then the expression must be
1320 * ":" or ": aff2", depending on whether anything follows the colon
1321 * inside the tuple element.
1322 * The first is considered to represent an arbitrary value.
1323 * The second is considered to represent a range of values
1324 * with the given upper bound and no lower bound.
1326 * There may be parentheses around some subexpression of "aff1"
1327 * around "aff1" itself, around "aff1 : condition1" and/or
1328 * around the entire piecewise affine expression.
1329 * We therefore remove the opening parenthesis (if any) from the stream
1330 * in case the closing parenthesis follows the colon, but if the closing
1331 * parenthesis is the first thing in the stream after the parsed affine
1332 * expression, we push the parsed expression onto the stream and parse
1333 * again in case the parentheses enclose some subexpression of "aff1".
1335 static __isl_give isl_pw_aff
*accept_piecewise_affine(__isl_keep isl_stream
*s
,
1336 __isl_take isl_space
*space
, struct vars
*v
, int rational
)
1339 isl_space
*res_space
;
1341 if (isl_stream_eat_if_available(s
, ':')) {
1342 if (next_is_end_tuple_element(s
))
1343 return identity_tuple_el_on_space(space
, v
);
1345 return construct_upper(accept_affine(s
, space
, v
), v
);
1348 res_space
= isl_space_from_domain(isl_space_copy(space
));
1349 res_space
= isl_space_add_dims(res_space
, isl_dim_out
, 1);
1350 res
= isl_pw_aff_empty(res_space
);
1354 int line
= -1, col
= -1;
1356 set_current_line_col(s
, &line
, &col
);
1357 seen_paren
= isl_stream_eat_if_available(s
, '(');
1359 pa
= accept_piecewise_affine(s
, isl_space_copy(space
),
1362 pa
= accept_extended_affine(s
, isl_space_copy(space
),
1364 if (seen_paren
&& isl_stream_eat_if_available(s
, ')')) {
1366 if (push_aff(s
, line
, col
, pa
) < 0)
1368 pa
= accept_extended_affine(s
, isl_space_copy(space
),
1371 if (isl_stream_eat_if_available(s
, ':'))
1372 pa
= update_piecewise_affine_colon(pa
, s
, v
, rational
);
1374 res
= isl_pw_aff_union_add(res
, pa
);
1376 if (seen_paren
&& isl_stream_eat(s
, ')'))
1378 } while (isl_stream_eat_if_available(s
, ';'));
1380 isl_space_free(space
);
1384 isl_space_free(space
);
1385 return isl_pw_aff_free(res
);
1388 /* Read an affine expression from "s" for use in read_tuple.
1390 * accept_extended_affine requires a wrapped space as input.
1391 * read_tuple on the other hand expects each isl_pw_aff
1392 * to have an anonymous space. We therefore adjust the space
1393 * of the isl_pw_aff before returning it.
1395 static __isl_give isl_pw_aff
*read_tuple_var_def(__isl_keep isl_stream
*s
,
1396 struct vars
*v
, int rational
)
1401 space
= isl_space_wrap(isl_space_alloc(s
->ctx
, 0, v
->n
, 0));
1403 def
= accept_piecewise_affine(s
, space
, v
, rational
);
1404 def
= isl_pw_aff_domain_factor_domain(def
);
1409 /* Read a list of tuple elements by calling "read_el" on each of them and
1410 * return a space with the same number of set dimensions derived from
1411 * the parameter space "space" and possibly updated by "read_el".
1412 * The elements in the list are separated by either "," or "][".
1413 * If "comma" is set then only "," is allowed.
1415 static __isl_give isl_space
*read_tuple_list(__isl_keep isl_stream
*s
,
1416 struct vars
*v
, __isl_take isl_space
*space
, int rational
, int comma
,
1417 __isl_give isl_space
*(*read_el
)(__isl_keep isl_stream
*s
,
1418 struct vars
*v
, __isl_take isl_space
*space
, int rational
,
1425 space
= isl_space_set_from_params(space
);
1427 if (isl_stream_next_token_is(s
, ']'))
1431 struct isl_token
*tok
;
1433 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1435 space
= read_el(s
, v
, space
, rational
, user
);
1439 tok
= isl_stream_next_token(s
);
1440 if (!comma
&& tok
&& tok
->type
== ']' &&
1441 isl_stream_next_token_is(s
, '[')) {
1442 isl_token_free(tok
);
1443 tok
= isl_stream_next_token(s
);
1444 } else if (!tok
|| tok
->type
!= ',') {
1446 isl_stream_push_token(s
, tok
);
1450 isl_token_free(tok
);
1456 /* Read a tuple space from "s" derived from the parameter space "space".
1457 * Call "read_el" on each element in the tuples.
1459 static __isl_give isl_space
*read_tuple_space(__isl_keep isl_stream
*s
,
1460 struct vars
*v
, __isl_take isl_space
*space
, int rational
, int comma
,
1461 __isl_give isl_space
*(*read_el
)(__isl_keep isl_stream
*s
,
1462 struct vars
*v
, __isl_take isl_space
*space
, int rational
,
1466 struct isl_token
*tok
;
1468 isl_space
*res
= NULL
;
1470 tok
= isl_stream_next_token(s
);
1473 if (tok
->type
== ISL_TOKEN_IDENT
|| tok
->is_keyword
) {
1474 name
= strdup(tok
->u
.s
);
1475 isl_token_free(tok
);
1479 isl_stream_push_token(s
, tok
);
1480 if (isl_stream_eat(s
, '['))
1482 if (next_is_tuple(s
)) {
1484 res
= read_tuple_space(s
, v
, isl_space_copy(space
),
1485 rational
, comma
, read_el
, user
);
1486 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
1488 out
= read_tuple_space(s
, v
, isl_space_copy(space
),
1489 rational
, comma
, read_el
, user
);
1490 res
= isl_space_product(res
, out
);
1492 res
= read_tuple_list(s
, v
, isl_space_copy(space
),
1493 rational
, comma
, read_el
, user
);
1494 if (isl_stream_eat(s
, ']'))
1498 res
= isl_space_set_tuple_name(res
, isl_dim_set
, name
);
1502 isl_space_free(space
);
1506 isl_space_free(res
);
1507 isl_space_free(space
);
1511 /* Construct an isl_pw_aff defined on a space with v->n variables
1512 * that is equal to the last of those variables.
1514 static __isl_give isl_pw_aff
*identity_tuple_el(struct vars
*v
)
1518 space
= isl_space_set_alloc(v
->ctx
, 0, v
->n
);
1519 return identity_tuple_el_on_space(space
, v
);
1522 /* This function is called for each element in a tuple inside read_tuple.
1523 * Add a new variable to "v" and construct a corresponding isl_pw_aff defined
1524 * over a space containing all variables in "v" defined so far.
1525 * The isl_pw_aff expresses the new variable in terms of earlier variables
1526 * if a definition is provided. Otherwise, it is represented as being
1528 * Add the isl_pw_aff to *list.
1529 * If the new variable was named, then adjust "space" accordingly and
1530 * return the updated space.
1532 static __isl_give isl_space
*read_tuple_pw_aff_el(__isl_keep isl_stream
*s
,
1533 struct vars
*v
, __isl_take isl_space
*space
, int rational
, void *user
)
1535 isl_pw_aff_list
**list
= (isl_pw_aff_list
**) user
;
1537 struct isl_token
*tok
;
1540 tok
= next_token(s
);
1542 isl_stream_error(s
, NULL
, "unexpected EOF");
1543 return isl_space_free(space
);
1546 if (tok
->type
== ISL_TOKEN_IDENT
) {
1548 int p
= vars_pos(v
, tok
->u
.s
, -1);
1554 if (tok
->type
== '*') {
1555 if (vars_add_anon(v
) < 0)
1557 isl_token_free(tok
);
1558 pa
= identity_tuple_el(v
);
1559 } else if (new_name
) {
1560 space
= space_set_last_dim_name(space
, v
->v
->name
);
1561 isl_token_free(tok
);
1562 if (isl_stream_eat_if_available(s
, '='))
1563 pa
= read_tuple_var_def(s
, v
, rational
);
1565 pa
= identity_tuple_el(v
);
1567 isl_stream_push_token(s
, tok
);
1569 if (vars_add_anon(v
) < 0)
1571 pa
= read_tuple_var_def(s
, v
, rational
);
1574 *list
= isl_pw_aff_list_add(*list
, pa
);
1576 return isl_space_free(space
);
1580 isl_token_free(tok
);
1581 return isl_space_free(space
);
1584 /* Read a tuple and represent it as an isl_multi_pw_aff.
1585 * The range space of the isl_multi_pw_aff is the space of the tuple.
1586 * The domain space is an anonymous space
1587 * with a dimension for each variable in the set of variables in "v",
1588 * including the variables in the range.
1589 * If a given dimension is not defined in terms of earlier dimensions in
1590 * the input, then the corresponding isl_pw_aff is set equal to one time
1591 * the variable corresponding to the dimension being defined.
1593 * The elements in the tuple are collected in a list by read_tuple_pw_aff_el.
1594 * Each element in this list is defined over a space representing
1595 * the variables defined so far. We need to adjust the earlier
1596 * elements to have as many variables in the domain as the final
1597 * element in the list.
1599 static __isl_give isl_multi_pw_aff
*read_tuple(__isl_keep isl_stream
*s
,
1600 struct vars
*v
, int rational
, int comma
)
1605 isl_pw_aff_list
*list
;
1607 space
= isl_space_params_alloc(v
->ctx
, 0);
1608 list
= isl_pw_aff_list_alloc(s
->ctx
, 0);
1609 space
= read_tuple_space(s
, v
, space
, rational
, comma
,
1610 &read_tuple_pw_aff_el
, &list
);
1611 n
= isl_space_dim(space
, isl_dim_set
);
1613 space
= isl_space_free(space
);
1614 for (i
= 0; i
+ 1 < n
; ++i
) {
1617 pa
= isl_pw_aff_list_get_pw_aff(list
, i
);
1618 pa
= isl_pw_aff_add_dims(pa
, isl_dim_in
, n
- (i
+ 1));
1619 list
= isl_pw_aff_list_set_pw_aff(list
, i
, pa
);
1622 space
= isl_space_from_range(space
);
1623 space
= isl_space_add_dims(space
, isl_dim_in
, v
->n
);
1624 return isl_multi_pw_aff_from_pw_aff_list(space
, list
);
1627 /* Add the tuple represented by the isl_multi_pw_aff "tuple" to "map".
1628 * We first create the appropriate space in "map" based on the range
1629 * space of this isl_multi_pw_aff. Then, we add equalities based
1630 * on the affine expressions. These live in an anonymous space,
1631 * however, so we first need to reset the space to that of "map".
1633 static __isl_give isl_map
*map_from_tuple(__isl_take isl_multi_pw_aff
*tuple
,
1634 __isl_take isl_map
*map
, enum isl_dim_type type
, struct vars
*v
,
1640 isl_space
*space
= NULL
;
1642 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
1645 ctx
= isl_multi_pw_aff_get_ctx(tuple
);
1646 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
1650 if (type
== isl_dim_param
) {
1651 if (isl_space_has_tuple_name(space
, isl_dim_set
) ||
1652 isl_space_is_wrapping(space
)) {
1653 isl_die(ctx
, isl_error_invalid
,
1654 "parameter tuples cannot be named or nested",
1657 map
= isl_map_add_dims(map
, type
, n
);
1658 for (i
= 0; i
< n
; ++i
) {
1660 if (!isl_space_has_dim_name(space
, isl_dim_set
, i
))
1661 isl_die(ctx
, isl_error_invalid
,
1662 "parameters must be named",
1664 id
= isl_space_get_dim_id(space
, isl_dim_set
, i
);
1665 map
= isl_map_set_dim_id(map
, isl_dim_param
, i
, id
);
1667 } else if (type
== isl_dim_in
) {
1670 set
= isl_set_universe(isl_space_copy(space
));
1672 set
= isl_set_set_rational(set
);
1673 set
= isl_set_intersect_params(set
, isl_map_params(map
));
1674 map
= isl_map_from_domain(set
);
1678 set
= isl_set_universe(isl_space_copy(space
));
1680 set
= isl_set_set_rational(set
);
1681 map
= isl_map_from_domain_and_range(isl_map_domain(map
), set
);
1684 for (i
= 0; i
< n
; ++i
) {
1691 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
1692 space
= isl_pw_aff_get_domain_space(pa
);
1693 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
1694 aff
= isl_aff_add_coefficient_si(aff
,
1695 isl_dim_in
, v
->n
- n
+ i
, -1);
1696 pa
= isl_pw_aff_add(pa
, isl_pw_aff_from_aff(aff
));
1698 pa
= isl_pw_aff_set_rational(pa
);
1699 set
= isl_pw_aff_zero_set(pa
);
1700 map_i
= isl_map_from_range(set
);
1701 map_i
= isl_map_reset_space(map_i
, isl_map_get_space(map
));
1702 map
= isl_map_intersect(map
, map_i
);
1705 isl_space_free(space
);
1706 isl_multi_pw_aff_free(tuple
);
1709 isl_space_free(space
);
1710 isl_multi_pw_aff_free(tuple
);
1715 /* Read a tuple from "s" and add it to "map".
1716 * The tuple is initially represented as an isl_multi_pw_aff and
1717 * then added to "map".
1719 static __isl_give isl_map
*read_map_tuple(__isl_keep isl_stream
*s
,
1720 __isl_take isl_map
*map
, enum isl_dim_type type
, struct vars
*v
,
1721 int rational
, int comma
)
1723 isl_multi_pw_aff
*tuple
;
1725 tuple
= read_tuple(s
, v
, rational
, comma
);
1727 return isl_map_free(map
);
1729 return map_from_tuple(tuple
, map
, type
, v
, rational
);
1732 /* Read the parameter domain of an expression from "s" (if any) and
1733 * check that it does not involve any constraints.
1734 * "v" contains a description of the identifiers parsed so far
1735 * (of which there should not be any at this point) and is extended
1738 static __isl_give isl_set
*read_universe_params(__isl_keep isl_stream
*s
,
1743 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
1744 if (next_is_tuple(s
)) {
1745 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
1746 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
1747 return isl_set_free(dom
);
1749 if (!isl_set_plain_is_universe(dom
))
1750 isl_die(s
->ctx
, isl_error_invalid
,
1751 "expecting universe parameter domain",
1752 return isl_set_free(dom
));
1757 /* This function is called for each element in a tuple inside read_space_tuples.
1758 * Add a new variable to "v" and adjust "space" accordingly
1759 * if the variable has a name.
1761 static __isl_give isl_space
*read_tuple_id(__isl_keep isl_stream
*s
,
1762 struct vars
*v
, __isl_take isl_space
*space
, int rational
, void *user
)
1764 struct isl_token
*tok
;
1766 tok
= next_token(s
);
1768 isl_stream_error(s
, NULL
, "unexpected EOF");
1769 return isl_space_free(space
);
1772 if (tok
->type
== ISL_TOKEN_IDENT
) {
1774 int p
= vars_pos(v
, tok
->u
.s
, -1);
1778 isl_stream_error(s
, tok
, "expecting fresh identifier");
1781 space
= space_set_last_dim_name(space
, v
->v
->name
);
1782 } else if (tok
->type
== '*') {
1783 if (vars_add_anon(v
) < 0)
1786 isl_stream_error(s
, tok
, "expecting identifier or '*'");
1790 isl_token_free(tok
);
1793 isl_token_free(tok
);
1794 return isl_space_free(space
);
1797 /* Given a parameter space "params", extend it with one or two tuples
1799 * "v" contains a description of the identifiers parsed so far and is extended
1802 static __isl_give isl_space
*read_space_tuples(__isl_keep isl_stream
*s
,
1803 struct vars
*v
, __isl_take isl_space
*params
)
1805 isl_space
*space
, *ran
;
1807 space
= read_tuple_space(s
, v
, isl_space_copy(params
), 1, 1,
1808 &read_tuple_id
, NULL
);
1809 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TO
)) {
1810 ran
= read_tuple_space(s
, v
, isl_space_copy(params
), 1, 1,
1811 &read_tuple_id
, NULL
);
1812 space
= isl_space_unwrap(isl_space_product(space
, ran
));
1814 isl_space_free(params
);
1819 /* Read an isl_space object from "s".
1821 * First read the parameters (if any).
1823 * Then check if the description is of the special form "{ : }",
1824 * in which case it represents a parameter space.
1825 * Otherwise, it has one or two tuples.
1827 __isl_give isl_space
*isl_stream_read_space(__isl_keep isl_stream
*s
)
1833 v
= vars_new(s
->ctx
);
1836 dom
= read_universe_params(s
, v
);
1837 space
= isl_set_get_space(dom
);
1840 if (isl_stream_eat(s
, '{'))
1843 if (!isl_stream_eat_if_available(s
, ':'))
1844 space
= read_space_tuples(s
, v
, space
);
1846 if (isl_stream_eat(s
, '}'))
1853 isl_space_free(space
);
1857 /* Read an isl_space object from "str".
1859 __isl_give isl_space
*isl_space_read_from_str(isl_ctx
*ctx
,
1862 struct isl_space
*space
;
1863 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
1866 space
= isl_stream_read_space(s
);
1871 /* Given two equal-length lists of piecewise affine expression with the space
1872 * of "set" as domain, construct a set in the same space that expresses
1873 * that "left" and "right" satisfy the comparison "type".
1875 * A space is constructed of the same dimension as the number of elements
1876 * in the two lists. The comparison is then expressed in a map from
1877 * this space to itself and wrapped into a set. Finally the two lists
1878 * of piecewise affine expressions are plugged into this set.
1880 * Let S be the space of "set" and T the constructed space.
1881 * The lists are first changed into two isl_multi_pw_affs in S -> T and
1882 * then combined into an isl_multi_pw_aff in S -> [T -> T],
1883 * while the comparison is first expressed in T -> T, then [T -> T]
1886 static __isl_give isl_set
*list_cmp(__isl_keep isl_set
*set
, int type
,
1887 __isl_take isl_pw_aff_list
*left
, __isl_take isl_pw_aff_list
*right
)
1891 isl_multi_pw_aff
*mpa1
, *mpa2
;
1893 n
= isl_pw_aff_list_n_pw_aff(left
);
1894 if (!set
|| n
< 0 || !right
)
1897 space
= isl_set_get_space(set
);
1898 space
= isl_space_from_domain(space
);
1899 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
1900 mpa1
= isl_multi_pw_aff_from_pw_aff_list(isl_space_copy(space
), left
);
1901 mpa2
= isl_multi_pw_aff_from_pw_aff_list(isl_space_copy(space
), right
);
1902 mpa1
= isl_multi_pw_aff_range_product(mpa1
, mpa2
);
1904 space
= isl_space_range(space
);
1906 case ISL_TOKEN_LEX_LT
:
1907 set
= isl_map_wrap(isl_map_lex_lt(space
));
1909 case ISL_TOKEN_LEX_GT
:
1910 set
= isl_map_wrap(isl_map_lex_gt(space
));
1912 case ISL_TOKEN_LEX_LE
:
1913 set
= isl_map_wrap(isl_map_lex_le(space
));
1915 case ISL_TOKEN_LEX_GE
:
1916 set
= isl_map_wrap(isl_map_lex_ge(space
));
1919 isl_multi_pw_aff_free(mpa1
);
1920 isl_space_free(space
);
1921 isl_die(isl_set_get_ctx(set
), isl_error_internal
,
1922 "unhandled list comparison type", return NULL
);
1924 set
= isl_set_preimage_multi_pw_aff(set
, mpa1
);
1927 isl_pw_aff_list_free(left
);
1928 isl_pw_aff_list_free(right
);
1932 /* Construct constraints of the form
1936 * where a is an element in "left", op is an operator of type "type" and
1937 * b is an element in "right", add the constraints to "set" and return
1939 * "rational" is set if the constraints should be treated as
1940 * a rational constraints.
1942 * If "type" is the type of a comparison operator between lists
1943 * of affine expressions, then a single (compound) constraint
1944 * is constructed by list_cmp instead.
1946 static __isl_give isl_set
*construct_constraints(
1947 __isl_take isl_set
*set
, int type
,
1948 __isl_keep isl_pw_aff_list
*left
, __isl_keep isl_pw_aff_list
*right
,
1953 left
= isl_pw_aff_list_copy(left
);
1954 right
= isl_pw_aff_list_copy(right
);
1956 left
= isl_pw_aff_list_set_rational(left
);
1957 right
= isl_pw_aff_list_set_rational(right
);
1959 if (is_list_comparator_type(type
))
1960 cond
= list_cmp(set
, type
, left
, right
);
1961 else if (type
== ISL_TOKEN_LE
)
1962 cond
= isl_pw_aff_list_le_set(left
, right
);
1963 else if (type
== ISL_TOKEN_GE
)
1964 cond
= isl_pw_aff_list_ge_set(left
, right
);
1965 else if (type
== ISL_TOKEN_LT
)
1966 cond
= isl_pw_aff_list_lt_set(left
, right
);
1967 else if (type
== ISL_TOKEN_GT
)
1968 cond
= isl_pw_aff_list_gt_set(left
, right
);
1969 else if (type
== ISL_TOKEN_NE
)
1970 cond
= isl_pw_aff_list_ne_set(left
, right
);
1972 cond
= isl_pw_aff_list_eq_set(left
, right
);
1974 return isl_set_intersect(set
, cond
);
1977 /* Read a constraint from "s", add it to "map" and return the result.
1978 * "v" contains a description of the identifiers parsed so far.
1979 * "rational" is set if the constraint should be treated as
1980 * a rational constraint.
1981 * The constraint read from "s" may be applied to multiple pairs
1982 * of affine expressions and may be chained.
1983 * In particular, a list of affine expressions is read, followed
1984 * by a comparison operator and another list of affine expressions.
1985 * The comparison operator is then applied to each pair of elements
1986 * in the two lists and the results are added to "map".
1987 * However, if the operator expects two lists of affine expressions,
1988 * then it is applied directly to those lists and the two lists
1989 * are required to have the same length.
1990 * If the next token is another comparison operator, then another
1991 * list of affine expressions is read and the process repeats.
1993 * The processing is performed on a wrapped copy of "map" because
1994 * an affine expression cannot have a binary relation as domain.
1996 static __isl_give isl_map
*add_constraint(__isl_keep isl_stream
*s
,
1997 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
1999 struct isl_token
*tok
;
2001 isl_pw_aff_list
*list1
= NULL
, *list2
= NULL
;
2005 set
= isl_map_wrap(map
);
2006 list1
= accept_affine_list(s
, isl_set_get_space(set
), v
);
2009 tok
= isl_stream_next_token(s
);
2010 if (!is_comparator(tok
)) {
2011 isl_stream_error(s
, tok
, "missing operator");
2013 isl_stream_push_token(s
, tok
);
2017 isl_token_free(tok
);
2019 list2
= accept_affine_list(s
, isl_set_get_space(set
), v
);
2020 n1
= isl_pw_aff_list_n_pw_aff(list1
);
2021 n2
= isl_pw_aff_list_n_pw_aff(list2
);
2022 if (n1
< 0 || n2
< 0)
2024 if (is_list_comparator_type(type
) && n1
!= n2
) {
2025 isl_stream_error(s
, NULL
,
2026 "list arguments not of same size");
2030 set
= construct_constraints(set
, type
, list1
, list2
, rational
);
2031 isl_pw_aff_list_free(list1
);
2034 if (!next_is_comparator(s
))
2036 tok
= isl_stream_next_token(s
);
2038 isl_token_free(tok
);
2040 isl_pw_aff_list_free(list1
);
2042 return isl_set_unwrap(set
);
2044 isl_pw_aff_list_free(list1
);
2045 isl_pw_aff_list_free(list2
);
2050 static __isl_give isl_map
*read_exists(__isl_keep isl_stream
*s
,
2051 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2054 int seen_paren
= isl_stream_eat_if_available(s
, '(');
2056 map
= isl_map_from_domain(isl_map_wrap(map
));
2057 map
= read_defined_var_list(s
, v
, map
, rational
);
2059 if (isl_stream_eat(s
, ':'))
2062 map
= read_formula(s
, v
, map
, rational
);
2063 map
= isl_set_unwrap(isl_map_domain(map
));
2065 vars_drop(v
, v
->n
- n
);
2066 if (seen_paren
&& isl_stream_eat(s
, ')'))
2075 /* Parse an expression between parentheses and push the result
2076 * back on the stream.
2078 * The parsed expression may be either an affine expression
2079 * or a condition. The first type is pushed onto the stream
2080 * as an isl_pw_aff, while the second is pushed as an isl_map.
2082 * If the initial token indicates the start of a condition,
2083 * we parse it as such.
2084 * Otherwise, we first parse an affine expression and push
2085 * that onto the stream. If the affine expression covers the
2086 * entire expression between parentheses, we return.
2087 * Otherwise, we assume that the affine expression is the
2088 * start of a condition and continue parsing.
2090 static int resolve_paren_expr(__isl_keep isl_stream
*s
,
2091 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2093 struct isl_token
*tok
, *tok2
;
2098 tok
= isl_stream_next_token(s
);
2099 if (!tok
|| tok
->type
!= '(')
2102 if (isl_stream_next_token_is(s
, '('))
2103 if (resolve_paren_expr(s
, v
, isl_map_copy(map
), rational
))
2106 if (next_is_condition_start(s
)) {
2107 map
= read_formula(s
, v
, map
, rational
);
2108 if (isl_stream_eat(s
, ')'))
2110 tok
->type
= ISL_TOKEN_MAP
;
2112 isl_stream_push_token(s
, tok
);
2116 tok2
= isl_stream_next_token(s
);
2121 isl_stream_push_token(s
, tok2
);
2123 pwaff
= accept_affine(s
, isl_space_wrap(isl_map_get_space(map
)), v
);
2127 has_paren
= isl_stream_eat_if_available(s
, ')');
2129 if (push_aff(s
, line
, col
, pwaff
) < 0)
2133 isl_token_free(tok
);
2138 map
= read_formula(s
, v
, map
, rational
);
2139 if (isl_stream_eat(s
, ')'))
2142 tok
->type
= ISL_TOKEN_MAP
;
2144 isl_stream_push_token(s
, tok
);
2148 isl_token_free(tok
);
2153 static __isl_give isl_map
*read_conjunct(__isl_keep isl_stream
*s
,
2154 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2156 if (isl_stream_next_token_is(s
, '('))
2157 if (resolve_paren_expr(s
, v
, isl_map_copy(map
), rational
))
2160 if (isl_stream_next_token_is(s
, ISL_TOKEN_MAP
)) {
2161 struct isl_token
*tok
;
2162 tok
= isl_stream_next_token(s
);
2166 map
= isl_map_copy(tok
->u
.map
);
2167 isl_token_free(tok
);
2171 if (isl_stream_eat_if_available(s
, ISL_TOKEN_EXISTS
))
2172 return read_exists(s
, v
, map
, rational
);
2174 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TRUE
))
2177 if (isl_stream_eat_if_available(s
, ISL_TOKEN_FALSE
)) {
2178 isl_space
*space
= isl_map_get_space(map
);
2180 return isl_map_empty(space
);
2183 return add_constraint(s
, v
, map
, rational
);
2189 static __isl_give isl_map
*read_conjuncts(__isl_keep isl_stream
*s
,
2190 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2195 negate
= isl_stream_eat_if_available(s
, ISL_TOKEN_NOT
);
2196 res
= read_conjunct(s
, v
, isl_map_copy(map
), rational
);
2198 res
= isl_map_subtract(isl_map_copy(map
), res
);
2200 while (res
&& isl_stream_eat_if_available(s
, ISL_TOKEN_AND
)) {
2203 negate
= isl_stream_eat_if_available(s
, ISL_TOKEN_NOT
);
2204 res_i
= read_conjunct(s
, v
, isl_map_copy(map
), rational
);
2206 res
= isl_map_subtract(res
, res_i
);
2208 res
= isl_map_intersect(res
, res_i
);
2215 static __isl_give isl_map
*read_disjuncts(__isl_keep isl_stream
*s
,
2216 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2220 if (isl_stream_next_token_is(s
, '}'))
2223 res
= read_conjuncts(s
, v
, isl_map_copy(map
), rational
);
2224 while (isl_stream_eat_if_available(s
, ISL_TOKEN_OR
)) {
2227 res_i
= read_conjuncts(s
, v
, isl_map_copy(map
), rational
);
2228 res
= isl_map_union(res
, res_i
);
2235 /* Read a first order formula from "s", add the corresponding
2236 * constraints to "map" and return the result.
2238 * In particular, read a formula of the form
2246 * where a and b are disjunctions.
2248 * In the first case, map is replaced by
2250 * map \cap { [..] : a }
2252 * In the second case, it is replaced by
2254 * (map \setminus { [..] : a}) \cup (map \cap { [..] : b })
2256 static __isl_give isl_map
*read_formula(__isl_keep isl_stream
*s
,
2257 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2261 res
= read_disjuncts(s
, v
, isl_map_copy(map
), rational
);
2263 if (isl_stream_eat_if_available(s
, ISL_TOKEN_IMPLIES
)) {
2266 res
= isl_map_subtract(isl_map_copy(map
), res
);
2267 res2
= read_disjuncts(s
, v
, map
, rational
);
2268 res
= isl_map_union(res
, res2
);
2275 static isl_size
polylib_pos_to_isl_pos(__isl_keep isl_basic_map
*bmap
, int pos
)
2277 isl_size n_out
, n_in
, n_param
, n_div
;
2279 n_param
= isl_basic_map_dim(bmap
, isl_dim_param
);
2280 n_in
= isl_basic_map_dim(bmap
, isl_dim_in
);
2281 n_out
= isl_basic_map_dim(bmap
, isl_dim_out
);
2282 n_div
= isl_basic_map_dim(bmap
, isl_dim_div
);
2283 if (n_param
< 0 || n_in
< 0 || n_out
< 0 || n_div
< 0)
2284 return isl_size_error
;
2287 return 1 + n_param
+ n_in
+ pos
;
2291 return 1 + n_param
+ pos
;
2295 return 1 + n_param
+ n_in
+ n_out
+ pos
;
2304 static __isl_give isl_basic_map
*basic_map_read_polylib_constraint(
2305 __isl_keep isl_stream
*s
, __isl_take isl_basic_map
*bmap
)
2308 struct isl_token
*tok
;
2317 tok
= isl_stream_next_token(s
);
2318 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2319 isl_stream_error(s
, tok
, "expecting coefficient");
2321 isl_stream_push_token(s
, tok
);
2324 if (!tok
->on_new_line
) {
2325 isl_stream_error(s
, tok
, "coefficient should appear on new line");
2326 isl_stream_push_token(s
, tok
);
2330 type
= isl_int_get_si(tok
->u
.v
);
2331 isl_token_free(tok
);
2333 isl_assert(s
->ctx
, type
== 0 || type
== 1, goto error
);
2335 k
= isl_basic_map_alloc_equality(bmap
);
2338 k
= isl_basic_map_alloc_inequality(bmap
);
2344 total
= isl_basic_map_dim(bmap
, isl_dim_all
);
2346 return isl_basic_map_free(bmap
);
2347 for (j
= 0; j
< 1 + total
; ++j
) {
2349 tok
= isl_stream_next_token(s
);
2350 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2351 isl_stream_error(s
, tok
, "expecting coefficient");
2353 isl_stream_push_token(s
, tok
);
2356 if (tok
->on_new_line
) {
2357 isl_stream_error(s
, tok
,
2358 "coefficient should not appear on new line");
2359 isl_stream_push_token(s
, tok
);
2362 pos
= polylib_pos_to_isl_pos(bmap
, j
);
2364 isl_int_set(c
[pos
], tok
->u
.v
);
2365 isl_token_free(tok
);
2367 return isl_basic_map_free(bmap
);
2372 isl_basic_map_free(bmap
);
2376 static __isl_give isl_basic_map
*basic_map_read_polylib(
2377 __isl_keep isl_stream
*s
)
2380 struct isl_token
*tok
;
2381 struct isl_token
*tok2
;
2384 unsigned in
= 0, out
, local
= 0;
2385 struct isl_basic_map
*bmap
= NULL
;
2388 tok
= isl_stream_next_token(s
);
2390 isl_stream_error(s
, NULL
, "unexpected EOF");
2393 tok2
= isl_stream_next_token(s
);
2395 isl_token_free(tok
);
2396 isl_stream_error(s
, NULL
, "unexpected EOF");
2399 if (tok
->type
!= ISL_TOKEN_VALUE
|| tok2
->type
!= ISL_TOKEN_VALUE
) {
2400 isl_stream_push_token(s
, tok2
);
2401 isl_stream_push_token(s
, tok
);
2402 isl_stream_error(s
, NULL
,
2403 "expecting constraint matrix dimensions");
2406 n_row
= isl_int_get_si(tok
->u
.v
);
2407 n_col
= isl_int_get_si(tok2
->u
.v
);
2408 on_new_line
= tok2
->on_new_line
;
2409 isl_token_free(tok2
);
2410 isl_token_free(tok
);
2411 isl_assert(s
->ctx
, !on_new_line
, return NULL
);
2412 isl_assert(s
->ctx
, n_row
>= 0, return NULL
);
2413 isl_assert(s
->ctx
, n_col
>= 2 + nparam
, return NULL
);
2414 tok
= isl_stream_next_token_on_same_line(s
);
2416 if (tok
->type
!= ISL_TOKEN_VALUE
) {
2417 isl_stream_error(s
, tok
,
2418 "expecting number of output dimensions");
2419 isl_stream_push_token(s
, tok
);
2422 out
= isl_int_get_si(tok
->u
.v
);
2423 isl_token_free(tok
);
2425 tok
= isl_stream_next_token_on_same_line(s
);
2426 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2427 isl_stream_error(s
, tok
,
2428 "expecting number of input dimensions");
2430 isl_stream_push_token(s
, tok
);
2433 in
= isl_int_get_si(tok
->u
.v
);
2434 isl_token_free(tok
);
2436 tok
= isl_stream_next_token_on_same_line(s
);
2437 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2438 isl_stream_error(s
, tok
,
2439 "expecting number of existentials");
2441 isl_stream_push_token(s
, tok
);
2444 local
= isl_int_get_si(tok
->u
.v
);
2445 isl_token_free(tok
);
2447 tok
= isl_stream_next_token_on_same_line(s
);
2448 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2449 isl_stream_error(s
, tok
,
2450 "expecting number of parameters");
2452 isl_stream_push_token(s
, tok
);
2455 nparam
= isl_int_get_si(tok
->u
.v
);
2456 isl_token_free(tok
);
2457 if (n_col
!= 1 + out
+ in
+ local
+ nparam
+ 1) {
2458 isl_stream_error(s
, NULL
,
2459 "dimensions don't match");
2463 out
= n_col
- 2 - nparam
;
2464 bmap
= isl_basic_map_alloc(s
->ctx
, nparam
, in
, out
, local
, n_row
, n_row
);
2468 for (i
= 0; i
< local
; ++i
) {
2469 int k
= isl_basic_map_alloc_div(bmap
);
2472 isl_seq_clr(bmap
->div
[k
], 1 + 1 + nparam
+ in
+ out
+ local
);
2475 for (i
= 0; i
< n_row
; ++i
)
2476 bmap
= basic_map_read_polylib_constraint(s
, bmap
);
2478 tok
= isl_stream_next_token_on_same_line(s
);
2480 isl_stream_error(s
, tok
, "unexpected extra token on line");
2481 isl_stream_push_token(s
, tok
);
2485 bmap
= isl_basic_map_simplify(bmap
);
2486 bmap
= isl_basic_map_finalize(bmap
);
2489 isl_basic_map_free(bmap
);
2493 static __isl_give isl_map
*map_read_polylib(__isl_keep isl_stream
*s
)
2495 struct isl_token
*tok
;
2496 struct isl_token
*tok2
;
2498 struct isl_map
*map
;
2500 tok
= isl_stream_next_token(s
);
2502 isl_stream_error(s
, NULL
, "unexpected EOF");
2505 tok2
= isl_stream_next_token_on_same_line(s
);
2506 if (tok2
&& tok2
->type
== ISL_TOKEN_VALUE
) {
2507 isl_stream_push_token(s
, tok2
);
2508 isl_stream_push_token(s
, tok
);
2509 return isl_map_from_basic_map(basic_map_read_polylib(s
));
2512 isl_stream_error(s
, tok2
, "unexpected token");
2513 isl_stream_push_token(s
, tok2
);
2514 isl_stream_push_token(s
, tok
);
2517 n
= isl_int_get_si(tok
->u
.v
);
2518 isl_token_free(tok
);
2520 isl_assert(s
->ctx
, n
>= 1, return NULL
);
2522 map
= isl_map_from_basic_map(basic_map_read_polylib(s
));
2524 for (i
= 1; map
&& i
< n
; ++i
)
2525 map
= isl_map_union(map
,
2526 isl_map_from_basic_map(basic_map_read_polylib(s
)));
2531 static int optional_power(__isl_keep isl_stream
*s
)
2534 struct isl_token
*tok
;
2536 tok
= isl_stream_next_token(s
);
2539 if (tok
->type
!= '^') {
2540 isl_stream_push_token(s
, tok
);
2543 isl_token_free(tok
);
2544 tok
= isl_stream_next_token(s
);
2545 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2546 isl_stream_error(s
, tok
, "expecting exponent");
2548 isl_stream_push_token(s
, tok
);
2551 pow
= isl_int_get_si(tok
->u
.v
);
2552 isl_token_free(tok
);
2556 static __isl_give isl_pw_qpolynomial
*read_term(__isl_keep isl_stream
*s
,
2557 __isl_keep isl_map
*map
, struct vars
*v
);
2559 static __isl_give isl_pw_qpolynomial
*read_factor(__isl_keep isl_stream
*s
,
2560 __isl_keep isl_map
*map
, struct vars
*v
)
2562 isl_pw_qpolynomial
*pwqp
;
2563 struct isl_token
*tok
;
2565 tok
= next_token(s
);
2567 isl_stream_error(s
, NULL
, "unexpected EOF");
2570 if (tok
->type
== '(') {
2573 isl_token_free(tok
);
2574 pwqp
= read_term(s
, map
, v
);
2577 if (isl_stream_eat(s
, ')'))
2579 pow
= optional_power(s
);
2580 pwqp
= isl_pw_qpolynomial_pow(pwqp
, pow
);
2581 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
2582 struct isl_token
*tok2
;
2583 isl_qpolynomial
*qp
;
2585 tok2
= isl_stream_next_token(s
);
2586 if (tok2
&& tok2
->type
== '/') {
2587 isl_token_free(tok2
);
2588 tok2
= next_token(s
);
2589 if (!tok2
|| tok2
->type
!= ISL_TOKEN_VALUE
) {
2590 isl_stream_error(s
, tok2
, "expected denominator");
2591 isl_token_free(tok
);
2592 isl_token_free(tok2
);
2595 qp
= isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map
),
2596 tok
->u
.v
, tok2
->u
.v
);
2597 isl_token_free(tok2
);
2599 isl_stream_push_token(s
, tok2
);
2600 qp
= isl_qpolynomial_cst_on_domain(isl_map_get_space(map
),
2603 isl_token_free(tok
);
2604 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2605 } else if (tok
->type
== ISL_TOKEN_INFTY
) {
2606 isl_qpolynomial
*qp
;
2607 isl_token_free(tok
);
2608 qp
= isl_qpolynomial_infty_on_domain(isl_map_get_space(map
));
2609 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2610 } else if (tok
->type
== ISL_TOKEN_NAN
) {
2611 isl_qpolynomial
*qp
;
2612 isl_token_free(tok
);
2613 qp
= isl_qpolynomial_nan_on_domain(isl_map_get_space(map
));
2614 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2615 } else if (tok
->type
== ISL_TOKEN_IDENT
) {
2617 int pos
= vars_pos(v
, tok
->u
.s
, -1);
2619 isl_qpolynomial
*qp
;
2621 isl_token_free(tok
);
2625 vars_drop(v
, v
->n
- n
);
2626 isl_stream_error(s
, tok
, "unknown identifier");
2627 isl_token_free(tok
);
2630 isl_token_free(tok
);
2631 pow
= optional_power(s
);
2632 qp
= isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map
), pos
, pow
);
2633 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2634 } else if (is_start_of_div(tok
)) {
2638 isl_stream_push_token(s
, tok
);
2639 pwaff
= accept_div(s
, isl_map_get_space(map
), v
);
2640 pow
= optional_power(s
);
2641 pwqp
= isl_pw_qpolynomial_from_pw_aff(pwaff
);
2642 pwqp
= isl_pw_qpolynomial_pow(pwqp
, pow
);
2643 } else if (tok
->type
== '-') {
2644 isl_token_free(tok
);
2645 pwqp
= read_factor(s
, map
, v
);
2646 pwqp
= isl_pw_qpolynomial_neg(pwqp
);
2648 isl_stream_error(s
, tok
, "unexpected isl_token");
2649 isl_stream_push_token(s
, tok
);
2653 if (isl_stream_eat_if_available(s
, '*') ||
2654 isl_stream_next_token_is(s
, ISL_TOKEN_IDENT
)) {
2655 isl_pw_qpolynomial
*pwqp2
;
2657 pwqp2
= read_factor(s
, map
, v
);
2658 pwqp
= isl_pw_qpolynomial_mul(pwqp
, pwqp2
);
2663 isl_pw_qpolynomial_free(pwqp
);
2667 static __isl_give isl_pw_qpolynomial
*read_term(__isl_keep isl_stream
*s
,
2668 __isl_keep isl_map
*map
, struct vars
*v
)
2670 struct isl_token
*tok
;
2671 isl_pw_qpolynomial
*pwqp
;
2673 pwqp
= read_factor(s
, map
, v
);
2676 tok
= next_token(s
);
2680 if (tok
->type
== '+') {
2681 isl_pw_qpolynomial
*pwqp2
;
2683 isl_token_free(tok
);
2684 pwqp2
= read_factor(s
, map
, v
);
2685 pwqp
= isl_pw_qpolynomial_add(pwqp
, pwqp2
);
2686 } else if (tok
->type
== '-') {
2687 isl_pw_qpolynomial
*pwqp2
;
2689 isl_token_free(tok
);
2690 pwqp2
= read_factor(s
, map
, v
);
2691 pwqp
= isl_pw_qpolynomial_sub(pwqp
, pwqp2
);
2692 } else if (tok
->type
== ISL_TOKEN_VALUE
&&
2693 isl_int_is_neg(tok
->u
.v
)) {
2694 isl_pw_qpolynomial
*pwqp2
;
2696 isl_stream_push_token(s
, tok
);
2697 pwqp2
= read_factor(s
, map
, v
);
2698 pwqp
= isl_pw_qpolynomial_add(pwqp
, pwqp2
);
2700 isl_stream_push_token(s
, tok
);
2708 static __isl_give isl_map
*read_optional_formula(__isl_keep isl_stream
*s
,
2709 __isl_take isl_map
*map
, struct vars
*v
, int rational
)
2711 struct isl_token
*tok
;
2713 tok
= isl_stream_next_token(s
);
2715 isl_stream_error(s
, NULL
, "unexpected EOF");
2718 if (tok
->type
== ':' ||
2719 (tok
->type
== ISL_TOKEN_OR
&& !strcmp(tok
->u
.s
, "|"))) {
2720 isl_token_free(tok
);
2721 map
= read_formula(s
, v
, map
, rational
);
2723 isl_stream_push_token(s
, tok
);
2731 static struct isl_obj
obj_read_poly(__isl_keep isl_stream
*s
,
2732 __isl_take isl_map
*map
, struct vars
*v
, int n
)
2734 struct isl_obj obj
= { isl_obj_pw_qpolynomial
, NULL
};
2735 isl_pw_qpolynomial
*pwqp
;
2736 struct isl_set
*set
;
2738 pwqp
= read_term(s
, map
, v
);
2739 map
= read_optional_formula(s
, map
, v
, 0);
2740 set
= isl_map_range(map
);
2742 pwqp
= isl_pw_qpolynomial_intersect_domain(pwqp
, set
);
2744 vars_drop(v
, v
->n
- n
);
2750 static struct isl_obj
obj_read_poly_or_fold(__isl_keep isl_stream
*s
,
2751 __isl_take isl_set
*set
, struct vars
*v
, int n
)
2754 struct isl_obj obj
= { isl_obj_pw_qpolynomial_fold
, NULL
};
2755 isl_pw_qpolynomial
*pwqp
;
2756 isl_pw_qpolynomial_fold
*pwf
= NULL
;
2759 max
= isl_stream_eat_if_available(s
, ISL_TOKEN_MAX
);
2760 min
= !max
&& isl_stream_eat_if_available(s
, ISL_TOKEN_MIN
);
2762 return obj_read_poly(s
, set
, v
, n
);
2763 fold
= max
? isl_fold_max
: isl_fold_min
;
2765 if (isl_stream_eat(s
, '('))
2768 pwqp
= read_term(s
, set
, v
);
2769 pwf
= isl_pw_qpolynomial_fold_from_pw_qpolynomial(fold
, pwqp
);
2771 while (isl_stream_eat_if_available(s
, ',')) {
2772 isl_pw_qpolynomial_fold
*pwf_i
;
2773 pwqp
= read_term(s
, set
, v
);
2774 pwf_i
= isl_pw_qpolynomial_fold_from_pw_qpolynomial(fold
, pwqp
);
2775 pwf
= isl_pw_qpolynomial_fold_fold(pwf
, pwf_i
);
2778 if (isl_stream_eat(s
, ')'))
2781 set
= read_optional_formula(s
, set
, v
, 0);
2782 pwf
= isl_pw_qpolynomial_fold_intersect_domain(pwf
, set
);
2784 vars_drop(v
, v
->n
- n
);
2790 isl_pw_qpolynomial_fold_free(pwf
);
2791 obj
.type
= isl_obj_none
;
2795 static int is_rational(__isl_keep isl_stream
*s
)
2797 struct isl_token
*tok
;
2799 tok
= isl_stream_next_token(s
);
2802 if (tok
->type
== ISL_TOKEN_RAT
&& isl_stream_next_token_is(s
, ':')) {
2803 isl_token_free(tok
);
2804 isl_stream_eat(s
, ':');
2808 isl_stream_push_token(s
, tok
);
2813 static struct isl_obj
obj_read_body(__isl_keep isl_stream
*s
,
2814 __isl_take isl_map
*map
, struct vars
*v
)
2816 struct isl_token
*tok
;
2817 struct isl_obj obj
= { isl_obj_set
, NULL
};
2821 rational
= is_rational(s
);
2823 map
= isl_map_set_rational(map
);
2825 if (isl_stream_next_token_is(s
, ':')) {
2826 obj
.type
= isl_obj_set
;
2827 obj
.v
= read_optional_formula(s
, map
, v
, rational
);
2831 if (!next_is_tuple(s
))
2832 return obj_read_poly_or_fold(s
, map
, v
, n
);
2834 map
= read_map_tuple(s
, map
, isl_dim_in
, v
, rational
, 0);
2837 tok
= isl_stream_next_token(s
);
2840 if (tok
->type
== ISL_TOKEN_TO
) {
2841 obj
.type
= isl_obj_map
;
2842 isl_token_free(tok
);
2843 if (!next_is_tuple(s
)) {
2844 isl_set
*set
= isl_map_domain(map
);
2845 return obj_read_poly_or_fold(s
, set
, v
, n
);
2847 map
= read_map_tuple(s
, map
, isl_dim_out
, v
, rational
, 0);
2851 map
= isl_map_domain(map
);
2852 isl_stream_push_token(s
, tok
);
2855 map
= read_optional_formula(s
, map
, v
, rational
);
2857 vars_drop(v
, v
->n
- n
);
2863 obj
.type
= isl_obj_none
;
2867 static struct isl_obj
to_union(isl_ctx
*ctx
, struct isl_obj obj
)
2869 if (obj
.type
== isl_obj_map
) {
2870 obj
.v
= isl_union_map_from_map(obj
.v
);
2871 obj
.type
= isl_obj_union_map
;
2872 } else if (obj
.type
== isl_obj_set
) {
2873 obj
.v
= isl_union_set_from_set(obj
.v
);
2874 obj
.type
= isl_obj_union_set
;
2875 } else if (obj
.type
== isl_obj_pw_qpolynomial
) {
2876 obj
.v
= isl_union_pw_qpolynomial_from_pw_qpolynomial(obj
.v
);
2877 obj
.type
= isl_obj_union_pw_qpolynomial
;
2878 } else if (obj
.type
== isl_obj_pw_qpolynomial_fold
) {
2879 obj
.v
= isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj
.v
);
2880 obj
.type
= isl_obj_union_pw_qpolynomial_fold
;
2882 isl_assert(ctx
, 0, goto error
);
2885 obj
.type
->free(obj
.v
);
2886 obj
.type
= isl_obj_none
;
2890 static struct isl_obj
obj_add(__isl_keep isl_stream
*s
,
2891 struct isl_obj obj1
, struct isl_obj obj2
)
2893 if (obj2
.type
== isl_obj_none
|| !obj2
.v
)
2895 if (obj1
.type
== isl_obj_set
&& obj2
.type
== isl_obj_union_set
)
2896 obj1
= to_union(s
->ctx
, obj1
);
2897 if (obj1
.type
== isl_obj_union_set
&& obj2
.type
== isl_obj_set
)
2898 obj2
= to_union(s
->ctx
, obj2
);
2899 if (obj1
.type
== isl_obj_map
&& obj2
.type
== isl_obj_union_map
)
2900 obj1
= to_union(s
->ctx
, obj1
);
2901 if (obj1
.type
== isl_obj_union_map
&& obj2
.type
== isl_obj_map
)
2902 obj2
= to_union(s
->ctx
, obj2
);
2903 if (obj1
.type
== isl_obj_pw_qpolynomial
&&
2904 obj2
.type
== isl_obj_union_pw_qpolynomial
)
2905 obj1
= to_union(s
->ctx
, obj1
);
2906 if (obj1
.type
== isl_obj_union_pw_qpolynomial
&&
2907 obj2
.type
== isl_obj_pw_qpolynomial
)
2908 obj2
= to_union(s
->ctx
, obj2
);
2909 if (obj1
.type
== isl_obj_pw_qpolynomial_fold
&&
2910 obj2
.type
== isl_obj_union_pw_qpolynomial_fold
)
2911 obj1
= to_union(s
->ctx
, obj1
);
2912 if (obj1
.type
== isl_obj_union_pw_qpolynomial_fold
&&
2913 obj2
.type
== isl_obj_pw_qpolynomial_fold
)
2914 obj2
= to_union(s
->ctx
, obj2
);
2915 if (obj1
.type
!= obj2
.type
) {
2916 isl_stream_error(s
, NULL
,
2917 "attempt to combine incompatible objects");
2920 if (!obj1
.type
->add
)
2921 isl_die(s
->ctx
, isl_error_internal
,
2922 "combination not supported on object type", goto error
);
2923 if (obj1
.type
== isl_obj_map
&& !isl_map_has_equal_space(obj1
.v
, obj2
.v
)) {
2924 obj1
= to_union(s
->ctx
, obj1
);
2925 obj2
= to_union(s
->ctx
, obj2
);
2927 if (obj1
.type
== isl_obj_set
&& !isl_set_has_equal_space(obj1
.v
, obj2
.v
)) {
2928 obj1
= to_union(s
->ctx
, obj1
);
2929 obj2
= to_union(s
->ctx
, obj2
);
2931 if (obj1
.type
== isl_obj_pw_qpolynomial
&&
2932 !isl_pw_qpolynomial_has_equal_space(obj1
.v
, obj2
.v
)) {
2933 obj1
= to_union(s
->ctx
, obj1
);
2934 obj2
= to_union(s
->ctx
, obj2
);
2936 if (obj1
.type
== isl_obj_pw_qpolynomial_fold
&&
2937 !isl_pw_qpolynomial_fold_has_equal_space(obj1
.v
, obj2
.v
)) {
2938 obj1
= to_union(s
->ctx
, obj1
);
2939 obj2
= to_union(s
->ctx
, obj2
);
2941 obj1
.v
= obj1
.type
->add(obj1
.v
, obj2
.v
);
2944 obj1
.type
->free(obj1
.v
);
2945 obj2
.type
->free(obj2
.v
);
2946 obj1
.type
= isl_obj_none
;
2951 /* Are the first two tokens on "s", "domain" (either as a string
2952 * or as an identifier) followed by ":"?
2954 static int next_is_domain_colon(__isl_keep isl_stream
*s
)
2956 struct isl_token
*tok
;
2960 tok
= isl_stream_next_token(s
);
2963 if (tok
->type
!= ISL_TOKEN_IDENT
&& tok
->type
!= ISL_TOKEN_STRING
) {
2964 isl_stream_push_token(s
, tok
);
2968 name
= isl_token_get_str(s
->ctx
, tok
);
2969 res
= !strcmp(name
, "domain") && isl_stream_next_token_is(s
, ':');
2972 isl_stream_push_token(s
, tok
);
2977 /* Do the first tokens on "s" look like a schedule?
2979 * The root of a schedule is always a domain node, so the first thing
2980 * we expect in the stream is a domain key, i.e., "domain" followed
2981 * by ":". If the schedule was printed in YAML flow style, then
2982 * we additionally expect a "{" to open the outer mapping.
2984 static int next_is_schedule(__isl_keep isl_stream
*s
)
2986 struct isl_token
*tok
;
2989 tok
= isl_stream_next_token(s
);
2992 if (tok
->type
!= '{') {
2993 isl_stream_push_token(s
, tok
);
2994 return next_is_domain_colon(s
);
2997 is_schedule
= next_is_domain_colon(s
);
2998 isl_stream_push_token(s
, tok
);
3003 /* Read an isl_schedule from "s" and store it in an isl_obj.
3005 static struct isl_obj
schedule_read(__isl_keep isl_stream
*s
)
3009 obj
.type
= isl_obj_schedule
;
3010 obj
.v
= isl_stream_read_schedule(s
);
3015 /* Read a disjunction of object bodies from "s".
3016 * That is, read the inside of the braces, but not the braces themselves.
3017 * "v" contains a description of the identifiers parsed so far.
3018 * "map" contains information about the parameters.
3020 static struct isl_obj
obj_read_disjuncts(__isl_keep isl_stream
*s
,
3021 struct vars
*v
, __isl_keep isl_map
*map
)
3023 struct isl_obj obj
= { isl_obj_set
, NULL
};
3025 if (isl_stream_next_token_is(s
, '}')) {
3026 obj
.type
= isl_obj_union_set
;
3027 obj
.v
= isl_union_set_empty(isl_map_get_space(map
));
3033 o
= obj_read_body(s
, isl_map_copy(map
), v
);
3037 obj
= obj_add(s
, obj
, o
);
3038 if (obj
.type
== isl_obj_none
|| !obj
.v
)
3040 if (!isl_stream_eat_if_available(s
, ';'))
3042 if (isl_stream_next_token_is(s
, '}'))
3049 static struct isl_obj
obj_read(__isl_keep isl_stream
*s
)
3051 isl_map
*map
= NULL
;
3052 struct isl_token
*tok
;
3053 struct vars
*v
= NULL
;
3054 struct isl_obj obj
= { isl_obj_set
, NULL
};
3056 if (next_is_schedule(s
))
3057 return schedule_read(s
);
3059 tok
= next_token(s
);
3061 isl_stream_error(s
, NULL
, "unexpected EOF");
3064 if (tok
->type
== ISL_TOKEN_VALUE
) {
3065 struct isl_token
*tok2
;
3066 struct isl_map
*map
;
3068 tok2
= isl_stream_next_token(s
);
3069 if (!tok2
|| tok2
->type
!= ISL_TOKEN_VALUE
||
3070 isl_int_is_neg(tok2
->u
.v
)) {
3072 isl_stream_push_token(s
, tok2
);
3073 obj
.type
= isl_obj_val
;
3074 obj
.v
= isl_val_int_from_isl_int(s
->ctx
, tok
->u
.v
);
3075 isl_token_free(tok
);
3078 isl_stream_push_token(s
, tok2
);
3079 isl_stream_push_token(s
, tok
);
3080 map
= map_read_polylib(s
);
3083 if (isl_map_may_be_set(map
))
3084 obj
.v
= isl_map_range(map
);
3086 obj
.type
= isl_obj_map
;
3091 v
= vars_new(s
->ctx
);
3093 isl_stream_push_token(s
, tok
);
3096 map
= isl_map_universe(isl_space_params_alloc(s
->ctx
, 0));
3097 if (tok
->type
== '[') {
3098 isl_stream_push_token(s
, tok
);
3099 map
= read_map_tuple(s
, map
, isl_dim_param
, v
, 0, 0);
3102 tok
= isl_stream_next_token(s
);
3103 if (!tok
|| tok
->type
!= ISL_TOKEN_TO
) {
3104 isl_stream_error(s
, tok
, "expecting '->'");
3106 isl_stream_push_token(s
, tok
);
3109 isl_token_free(tok
);
3110 tok
= isl_stream_next_token(s
);
3112 if (!tok
|| tok
->type
!= '{') {
3113 isl_stream_error(s
, tok
, "expecting '{'");
3115 isl_stream_push_token(s
, tok
);
3118 isl_token_free(tok
);
3120 tok
= isl_stream_next_token(s
);
3123 else if (tok
->type
== ISL_TOKEN_IDENT
&& !strcmp(tok
->u
.s
, "Sym")) {
3124 isl_token_free(tok
);
3125 if (isl_stream_eat(s
, '='))
3127 map
= read_map_tuple(s
, map
, isl_dim_param
, v
, 0, 1);
3131 isl_stream_push_token(s
, tok
);
3133 obj
= obj_read_disjuncts(s
, v
, map
);
3134 if (obj
.type
== isl_obj_none
|| !obj
.v
)
3137 tok
= isl_stream_next_token(s
);
3138 if (tok
&& tok
->type
== '}') {
3139 isl_token_free(tok
);
3141 isl_stream_error(s
, tok
, "unexpected isl_token");
3143 isl_token_free(tok
);
3153 obj
.type
->free(obj
.v
);
3160 struct isl_obj
isl_stream_read_obj(__isl_keep isl_stream
*s
)
3165 __isl_give isl_map
*isl_stream_read_map(__isl_keep isl_stream
*s
)
3171 isl_assert(s
->ctx
, obj
.type
== isl_obj_map
||
3172 obj
.type
== isl_obj_set
, goto error
);
3174 if (obj
.type
== isl_obj_set
)
3175 obj
.v
= isl_map_from_range(obj
.v
);
3179 obj
.type
->free(obj
.v
);
3183 __isl_give isl_set
*isl_stream_read_set(__isl_keep isl_stream
*s
)
3189 if (obj
.type
== isl_obj_map
&& isl_map_may_be_set(obj
.v
)) {
3190 obj
.v
= isl_map_range(obj
.v
);
3191 obj
.type
= isl_obj_set
;
3193 isl_assert(s
->ctx
, obj
.type
== isl_obj_set
, goto error
);
3198 obj
.type
->free(obj
.v
);
3202 __isl_give isl_union_map
*isl_stream_read_union_map(__isl_keep isl_stream
*s
)
3207 if (obj
.type
== isl_obj_map
) {
3208 obj
.type
= isl_obj_union_map
;
3209 obj
.v
= isl_union_map_from_map(obj
.v
);
3211 if (obj
.type
== isl_obj_set
) {
3212 obj
.type
= isl_obj_union_set
;
3213 obj
.v
= isl_union_set_from_set(obj
.v
);
3215 if (obj
.v
&& obj
.type
== isl_obj_union_set
&&
3216 isl_union_set_is_empty(obj
.v
))
3217 obj
.type
= isl_obj_union_map
;
3218 if (obj
.v
&& obj
.type
!= isl_obj_union_map
)
3219 isl_die(s
->ctx
, isl_error_invalid
, "invalid input", goto error
);
3223 obj
.type
->free(obj
.v
);
3227 /* Extract an isl_union_set from "obj".
3228 * This only works if the object was detected as either a set
3229 * (in which case it is converted to a union set) or a union set.
3231 static __isl_give isl_union_set
*extract_union_set(isl_ctx
*ctx
,
3234 if (obj
.type
== isl_obj_set
) {
3235 obj
.type
= isl_obj_union_set
;
3236 obj
.v
= isl_union_set_from_set(obj
.v
);
3239 isl_assert(ctx
, obj
.type
== isl_obj_union_set
, goto error
);
3243 obj
.type
->free(obj
.v
);
3247 /* Read an isl_union_set from "s".
3248 * First read a generic object and then try and extract
3249 * an isl_union_set from that.
3251 __isl_give isl_union_set
*isl_stream_read_union_set(__isl_keep isl_stream
*s
)
3256 return extract_union_set(s
->ctx
, obj
);
3259 static __isl_give isl_basic_map
*basic_map_read(__isl_keep isl_stream
*s
)
3262 struct isl_map
*map
;
3263 struct isl_basic_map
*bmap
;
3266 if (obj
.v
&& (obj
.type
!= isl_obj_map
&& obj
.type
!= isl_obj_set
))
3267 isl_die(s
->ctx
, isl_error_invalid
, "not a (basic) set or map",
3274 isl_die(s
->ctx
, isl_error_invalid
,
3275 "set or map description involves "
3276 "more than one disjunct", goto error
);
3279 bmap
= isl_basic_map_empty(isl_map_get_space(map
));
3281 bmap
= isl_basic_map_copy(map
->p
[0]);
3287 obj
.type
->free(obj
.v
);
3291 static __isl_give isl_basic_set
*basic_set_read(__isl_keep isl_stream
*s
)
3293 isl_basic_map
*bmap
;
3294 bmap
= basic_map_read(s
);
3297 if (!isl_basic_map_may_be_set(bmap
))
3298 isl_die(s
->ctx
, isl_error_invalid
,
3299 "input is not a set", goto error
);
3300 return isl_basic_map_range(bmap
);
3302 isl_basic_map_free(bmap
);
3306 __isl_give isl_basic_map
*isl_basic_map_read_from_file(isl_ctx
*ctx
,
3309 struct isl_basic_map
*bmap
;
3310 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3313 bmap
= basic_map_read(s
);
3318 __isl_give isl_basic_set
*isl_basic_set_read_from_file(isl_ctx
*ctx
,
3321 isl_basic_set
*bset
;
3322 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3325 bset
= basic_set_read(s
);
3330 __isl_give isl_basic_map
*isl_basic_map_read_from_str(isl_ctx
*ctx
,
3333 struct isl_basic_map
*bmap
;
3334 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3337 bmap
= basic_map_read(s
);
3342 __isl_give isl_basic_set
*isl_basic_set_read_from_str(isl_ctx
*ctx
,
3345 isl_basic_set
*bset
;
3346 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3349 bset
= basic_set_read(s
);
3354 __isl_give isl_map
*isl_map_read_from_file(struct isl_ctx
*ctx
,
3357 struct isl_map
*map
;
3358 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3361 map
= isl_stream_read_map(s
);
3366 __isl_give isl_map
*isl_map_read_from_str(struct isl_ctx
*ctx
,
3369 struct isl_map
*map
;
3370 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3373 map
= isl_stream_read_map(s
);
3378 __isl_give isl_set
*isl_set_read_from_file(struct isl_ctx
*ctx
,
3382 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3385 set
= isl_stream_read_set(s
);
3390 __isl_give isl_set
*isl_set_read_from_str(isl_ctx
*ctx
, const char *str
)
3393 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3396 set
= isl_stream_read_set(s
);
3401 __isl_give isl_union_map
*isl_union_map_read_from_file(isl_ctx
*ctx
,
3404 isl_union_map
*umap
;
3405 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3408 umap
= isl_stream_read_union_map(s
);
3413 __isl_give isl_union_map
*isl_union_map_read_from_str(struct isl_ctx
*ctx
,
3416 isl_union_map
*umap
;
3417 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3420 umap
= isl_stream_read_union_map(s
);
3425 __isl_give isl_union_set
*isl_union_set_read_from_file(isl_ctx
*ctx
,
3428 isl_union_set
*uset
;
3429 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3432 uset
= isl_stream_read_union_set(s
);
3437 __isl_give isl_union_set
*isl_union_set_read_from_str(struct isl_ctx
*ctx
,
3440 isl_union_set
*uset
;
3441 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3444 uset
= isl_stream_read_union_set(s
);
3449 static __isl_give isl_vec
*isl_vec_read_polylib(__isl_keep isl_stream
*s
)
3451 struct isl_vec
*vec
= NULL
;
3452 struct isl_token
*tok
;
3456 tok
= isl_stream_next_token(s
);
3457 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
3458 isl_stream_error(s
, tok
, "expecting vector length");
3462 size
= isl_int_get_si(tok
->u
.v
);
3463 isl_token_free(tok
);
3465 vec
= isl_vec_alloc(s
->ctx
, size
);
3467 for (j
= 0; j
< size
; ++j
) {
3468 tok
= isl_stream_next_token(s
);
3469 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
3470 isl_stream_error(s
, tok
, "expecting constant value");
3473 isl_int_set(vec
->el
[j
], tok
->u
.v
);
3474 isl_token_free(tok
);
3479 isl_token_free(tok
);
3484 static __isl_give isl_vec
*vec_read(__isl_keep isl_stream
*s
)
3486 return isl_vec_read_polylib(s
);
3489 __isl_give isl_vec
*isl_vec_read_from_file(isl_ctx
*ctx
, FILE *input
)
3492 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3500 __isl_give isl_pw_qpolynomial
*isl_stream_read_pw_qpolynomial(
3501 __isl_keep isl_stream
*s
)
3507 isl_assert(s
->ctx
, obj
.type
== isl_obj_pw_qpolynomial
,
3512 obj
.type
->free(obj
.v
);
3516 __isl_give isl_pw_qpolynomial
*isl_pw_qpolynomial_read_from_str(isl_ctx
*ctx
,
3519 isl_pw_qpolynomial
*pwqp
;
3520 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3523 pwqp
= isl_stream_read_pw_qpolynomial(s
);
3528 __isl_give isl_pw_qpolynomial
*isl_pw_qpolynomial_read_from_file(isl_ctx
*ctx
,
3531 isl_pw_qpolynomial
*pwqp
;
3532 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3535 pwqp
= isl_stream_read_pw_qpolynomial(s
);
3540 /* Read an isl_pw_qpolynomial_fold from "s".
3541 * First read a generic object and
3542 * then check that it is an isl_pw_qpolynomial_fold.
3544 __isl_give isl_pw_qpolynomial_fold
*isl_stream_read_pw_qpolynomial_fold(
3545 __isl_keep isl_stream
*s
)
3550 if (obj
.v
&& obj
.type
!= isl_obj_pw_qpolynomial_fold
)
3551 isl_die(s
->ctx
, isl_error_invalid
, "invalid input", goto error
);
3555 obj
.type
->free(obj
.v
);
3559 /* Read an isl_pw_qpolynomial_fold from "str".
3561 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_read_from_str(
3562 isl_ctx
*ctx
, const char *str
)
3564 isl_pw_qpolynomial_fold
*pwqp
;
3567 s
= isl_stream_new_str(ctx
, str
);
3570 pwqp
= isl_stream_read_pw_qpolynomial_fold(s
);
3576 /* Is the next token an identifier not in "v"?
3578 static int next_is_fresh_ident(__isl_keep isl_stream
*s
, struct vars
*v
)
3582 struct isl_token
*tok
;
3584 tok
= isl_stream_next_token(s
);
3587 fresh
= tok
->type
== ISL_TOKEN_IDENT
&& vars_pos(v
, tok
->u
.s
, -1) >= n
;
3588 isl_stream_push_token(s
, tok
);
3590 vars_drop(v
, v
->n
- n
);
3595 /* First read the domain of the affine expression, which may be
3596 * a parameter space or a set.
3597 * The tricky part is that we don't know if the domain is a set or not,
3598 * so when we are trying to read the domain, we may actually be reading
3599 * the affine expression itself (defined on a parameter domains)
3600 * If the tuple we are reading is named, we assume it's the domain.
3601 * Also, if inside the tuple, the first thing we find is a nested tuple
3602 * or a new identifier, we again assume it's the domain.
3603 * Finally, if the tuple is empty, then it must be the domain
3604 * since it does not contain an affine expression.
3605 * Otherwise, we assume we are reading an affine expression.
3607 static __isl_give isl_set
*read_aff_domain(__isl_keep isl_stream
*s
,
3608 __isl_take isl_set
*dom
, struct vars
*v
)
3610 struct isl_token
*tok
, *tok2
;
3613 tok
= isl_stream_next_token(s
);
3614 if (tok
&& (tok
->type
== ISL_TOKEN_IDENT
|| tok
->is_keyword
)) {
3615 isl_stream_push_token(s
, tok
);
3616 return read_map_tuple(s
, dom
, isl_dim_set
, v
, 0, 0);
3618 if (!tok
|| tok
->type
!= '[') {
3619 isl_stream_error(s
, tok
, "expecting '['");
3622 tok2
= isl_stream_next_token(s
);
3623 is_empty
= tok2
&& tok2
->type
== ']';
3625 isl_stream_push_token(s
, tok2
);
3626 if (is_empty
|| next_is_tuple(s
) || next_is_fresh_ident(s
, v
)) {
3627 isl_stream_push_token(s
, tok
);
3628 dom
= read_map_tuple(s
, dom
, isl_dim_set
, v
, 0, 0);
3630 isl_stream_push_token(s
, tok
);
3635 isl_stream_push_token(s
, tok
);
3640 /* Read an affine expression from "s".
3642 __isl_give isl_aff
*isl_stream_read_aff(__isl_keep isl_stream
*s
)
3648 ma
= isl_stream_read_multi_aff(s
);
3649 dim
= isl_multi_aff_dim(ma
, isl_dim_out
);
3653 isl_die(s
->ctx
, isl_error_invalid
,
3654 "expecting single affine expression",
3657 aff
= isl_multi_aff_get_aff(ma
, 0);
3658 isl_multi_aff_free(ma
);
3661 isl_multi_aff_free(ma
);
3665 /* Read a piecewise affine expression from "s" with domain (space) "dom".
3667 static __isl_give isl_pw_aff
*read_pw_aff_with_dom(__isl_keep isl_stream
*s
,
3668 __isl_take isl_set
*dom
, struct vars
*v
)
3670 isl_pw_aff
*pwaff
= NULL
;
3672 if (!isl_set_is_params(dom
) && isl_stream_eat(s
, ISL_TOKEN_TO
))
3675 if (isl_stream_eat(s
, '['))
3678 pwaff
= accept_affine(s
, isl_set_get_space(dom
), v
);
3680 if (isl_stream_eat(s
, ']'))
3683 dom
= read_optional_formula(s
, dom
, v
, 0);
3684 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
3689 isl_pw_aff_free(pwaff
);
3693 __isl_give isl_pw_aff
*isl_stream_read_pw_aff(__isl_keep isl_stream
*s
)
3696 isl_set
*dom
= NULL
;
3698 isl_pw_aff
*pa
= NULL
;
3701 v
= vars_new(s
->ctx
);
3705 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
3706 if (next_is_tuple(s
)) {
3707 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
3708 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
3711 if (isl_stream_eat(s
, '{'))
3715 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
3716 pa
= read_pw_aff_with_dom(s
, aff_dom
, v
);
3717 vars_drop(v
, v
->n
- n
);
3719 while (isl_stream_eat_if_available(s
, ';')) {
3723 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
3724 pa_i
= read_pw_aff_with_dom(s
, aff_dom
, v
);
3725 vars_drop(v
, v
->n
- n
);
3727 pa
= isl_pw_aff_union_add(pa
, pa_i
);
3730 if (isl_stream_eat(s
, '}'))
3739 isl_pw_aff_free(pa
);
3743 __isl_give isl_aff
*isl_aff_read_from_str(isl_ctx
*ctx
, const char *str
)
3746 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3749 aff
= isl_stream_read_aff(s
);
3754 __isl_give isl_pw_aff
*isl_pw_aff_read_from_str(isl_ctx
*ctx
, const char *str
)
3757 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3760 pa
= isl_stream_read_pw_aff(s
);
3765 /* Extract an isl_multi_pw_aff with domain space "dom_space"
3766 * from a tuple "tuple" read by read_tuple.
3768 * Note that the function read_tuple accepts tuples where some output or
3769 * set dimensions are defined in terms of other output or set dimensions
3770 * since this function is also used to read maps. As a special case,
3771 * read_tuple also accept dimensions that are defined in terms of themselves
3772 * (i.e., that are not defined).
3773 * These cases are not allowed when extracting an isl_multi_pw_aff so check
3774 * that the definitions of the output/set dimensions do not involve any
3775 * output/set dimensions.
3776 * Finally, drop the output dimensions from the domain of the result
3777 * of read_tuple (which is of the form [input, output] -> [output],
3778 * with anonymous domain) and reset the space.
3780 static __isl_give isl_multi_pw_aff
*extract_mpa_from_tuple(
3781 __isl_take isl_space
*dom_space
, __isl_keep isl_multi_pw_aff
*tuple
)
3786 isl_multi_pw_aff
*mpa
;
3788 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
3789 dim
= isl_space_dim(dom_space
, isl_dim_all
);
3790 if (n
< 0 || dim
< 0)
3791 dom_space
= isl_space_free(dom_space
);
3792 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
3793 space
= isl_space_align_params(space
, isl_space_copy(dom_space
));
3794 if (!isl_space_is_params(dom_space
))
3795 space
= isl_space_map_from_domain_and_range(
3796 isl_space_copy(dom_space
), space
);
3797 isl_space_free(dom_space
);
3798 mpa
= isl_multi_pw_aff_alloc(space
);
3800 for (i
= 0; i
< n
; ++i
) {
3802 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
3804 return isl_multi_pw_aff_free(mpa
);
3805 if (isl_pw_aff_involves_dims(pa
, isl_dim_in
, dim
, i
+ 1)) {
3806 isl_ctx
*ctx
= isl_pw_aff_get_ctx(pa
);
3807 isl_pw_aff_free(pa
);
3808 isl_die(ctx
, isl_error_invalid
,
3809 "not an affine expression",
3810 return isl_multi_pw_aff_free(mpa
));
3812 pa
= isl_pw_aff_drop_dims(pa
, isl_dim_in
, dim
, n
);
3813 space
= isl_multi_pw_aff_get_domain_space(mpa
);
3814 pa
= isl_pw_aff_reset_domain_space(pa
, space
);
3815 mpa
= isl_multi_pw_aff_set_pw_aff(mpa
, i
, pa
);
3821 /* Read a tuple of affine expressions, together with optional constraints
3822 * on the domain from "s". "dom" represents the initial constraints
3825 * The isl_multi_aff may live in either a set or a map space.
3826 * First read the first tuple and check if it is followed by a "->".
3827 * If so, convert the tuple into the domain of the isl_multi_pw_aff and
3828 * read in the next tuple. This tuple (or the first tuple if it was
3829 * not followed by a "->") is then converted into an isl_multi_pw_aff
3830 * through a call to extract_mpa_from_tuple.
3831 * The result is converted to an isl_pw_multi_aff and
3832 * its domain is intersected with the domain.
3834 * Note that the last tuple may introduce new identifiers,
3835 * but these cannot be referenced in the description of the domain.
3837 static __isl_give isl_pw_multi_aff
*read_conditional_multi_aff(
3838 __isl_keep isl_stream
*s
, __isl_take isl_set
*dom
, struct vars
*v
)
3840 isl_multi_pw_aff
*tuple
;
3841 isl_multi_pw_aff
*mpa
;
3842 isl_pw_multi_aff
*pma
;
3847 tuple
= read_tuple(s
, v
, 0, 0);
3850 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TO
)) {
3851 isl_map
*map
= map_from_tuple(tuple
, dom
, isl_dim_in
, v
, 0);
3852 dom
= isl_map_domain(map
);
3854 tuple
= read_tuple(s
, v
, 0, 0);
3858 mpa
= extract_mpa_from_tuple(isl_set_get_space(dom
), tuple
);
3859 isl_multi_pw_aff_free(tuple
);
3861 dom
= isl_set_free(dom
);
3863 vars_drop(v
, v
->n
- n_dom
);
3864 dom
= read_optional_formula(s
, dom
, v
, 0);
3866 vars_drop(v
, v
->n
- n
);
3868 pma
= isl_pw_multi_aff_from_multi_pw_aff(mpa
);
3869 pma
= isl_pw_multi_aff_intersect_domain(pma
, dom
);
3877 /* Read an isl_union_pw_multi_aff from "s".
3879 * In particular, first read the parameters and then read a sequence
3880 * of zero or more tuples of affine expressions with optional conditions and
3883 __isl_give isl_union_pw_multi_aff
*isl_stream_read_union_pw_multi_aff(
3884 __isl_keep isl_stream
*s
)
3888 isl_union_pw_multi_aff
*upma
= NULL
;
3890 v
= vars_new(s
->ctx
);
3894 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
3895 if (next_is_tuple(s
)) {
3896 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
3897 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
3900 if (isl_stream_eat(s
, '{'))
3903 upma
= isl_union_pw_multi_aff_empty(isl_set_get_space(dom
));
3906 isl_pw_multi_aff
*pma
;
3907 isl_union_pw_multi_aff
*upma2
;
3909 if (isl_stream_next_token_is(s
, '}'))
3912 pma
= read_conditional_multi_aff(s
, isl_set_copy(dom
), v
);
3913 upma2
= isl_union_pw_multi_aff_from_pw_multi_aff(pma
);
3914 upma
= isl_union_pw_multi_aff_union_add(upma
, upma2
);
3917 } while (isl_stream_eat_if_available(s
, ';'));
3919 if (isl_stream_eat(s
, '}'))
3926 isl_union_pw_multi_aff_free(upma
);
3932 /* Read an isl_pw_multi_aff from "s".
3934 * Read a more generic isl_union_pw_multi_aff first and
3935 * then check that the result lives in a single space.
3937 __isl_give isl_pw_multi_aff
*isl_stream_read_pw_multi_aff(
3938 __isl_keep isl_stream
*s
)
3940 isl_bool single_space
;
3941 isl_union_pw_multi_aff
*upma
;
3943 upma
= isl_stream_read_union_pw_multi_aff(s
);
3944 single_space
= isl_union_pw_multi_aff_isa_pw_multi_aff(upma
);
3945 if (single_space
< 0)
3946 upma
= isl_union_pw_multi_aff_free(upma
);
3947 else if (!single_space
)
3948 isl_die(s
->ctx
, isl_error_invalid
,
3949 "expecting expression in single space",
3950 upma
= isl_union_pw_multi_aff_free(upma
));
3951 return isl_union_pw_multi_aff_as_pw_multi_aff(upma
);
3954 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_read_from_str(isl_ctx
*ctx
,
3957 isl_pw_multi_aff
*pma
;
3958 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3961 pma
= isl_stream_read_pw_multi_aff(s
);
3966 /* Read an isl_union_pw_multi_aff from "str".
3968 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_read_from_str(
3969 isl_ctx
*ctx
, const char *str
)
3971 isl_union_pw_multi_aff
*upma
;
3972 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3975 upma
= isl_stream_read_union_pw_multi_aff(s
);
3980 /* Assuming "pa" represents a single affine expression defined on a universe
3981 * domain, extract this affine expression.
3983 static __isl_give isl_aff
*aff_from_pw_aff(__isl_take isl_pw_aff
*pa
)
3990 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
3991 "expecting single affine expression",
3993 if (!isl_set_plain_is_universe(pa
->p
[0].set
))
3994 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
3995 "expecting universe domain",
3998 aff
= isl_aff_copy(pa
->p
[0].aff
);
3999 isl_pw_aff_free(pa
);
4002 isl_pw_aff_free(pa
);
4009 #include <isl_multi_read_no_explicit_domain_templ.c>
4014 #include <isl_multi_read_no_explicit_domain_templ.c>
4016 /* Read a multi-affine expression from "s".
4017 * If the multi-affine expression has a domain, then the tuple
4018 * representing this domain cannot involve any affine expressions.
4019 * The tuple representing the actual expressions needs to consist
4020 * of only affine expressions. Moreover, these expressions can
4021 * only depend on parameters and input dimensions and not on other
4022 * output dimensions.
4024 __isl_give isl_multi_aff
*isl_stream_read_multi_aff(__isl_keep isl_stream
*s
)
4027 isl_set
*dom
= NULL
;
4028 isl_multi_pw_aff
*tuple
= NULL
;
4031 isl_space
*space
, *dom_space
;
4032 isl_multi_aff
*ma
= NULL
;
4034 v
= vars_new(s
->ctx
);
4038 dom
= read_universe_params(s
, v
);
4041 if (isl_stream_eat(s
, '{'))
4044 tuple
= read_tuple(s
, v
, 0, 0);
4047 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TO
)) {
4052 has_expr
= tuple_has_expr(tuple
);
4056 isl_die(s
->ctx
, isl_error_invalid
,
4057 "expecting universe domain", goto error
);
4058 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
4059 set
= isl_set_universe(space
);
4060 dom
= isl_set_intersect_params(set
, dom
);
4061 isl_multi_pw_aff_free(tuple
);
4062 tuple
= read_tuple(s
, v
, 0, 0);
4067 if (isl_stream_eat(s
, '}'))
4070 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
4071 dim
= isl_set_dim(dom
, isl_dim_all
);
4072 if (n
< 0 || dim
< 0)
4074 dom_space
= isl_set_get_space(dom
);
4075 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
4076 space
= isl_space_align_params(space
, isl_space_copy(dom_space
));
4077 if (!isl_space_is_params(dom_space
))
4078 space
= isl_space_map_from_domain_and_range(
4079 isl_space_copy(dom_space
), space
);
4080 isl_space_free(dom_space
);
4081 ma
= isl_multi_aff_alloc(space
);
4083 for (i
= 0; i
< n
; ++i
) {
4086 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
4087 aff
= aff_from_pw_aff(pa
);
4090 if (isl_aff_involves_dims(aff
, isl_dim_in
, dim
, i
+ 1)) {
4092 isl_die(s
->ctx
, isl_error_invalid
,
4093 "not an affine expression", goto error
);
4095 aff
= isl_aff_drop_dims(aff
, isl_dim_in
, dim
, n
);
4096 space
= isl_multi_aff_get_domain_space(ma
);
4097 aff
= isl_aff_reset_domain_space(aff
, space
);
4098 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
4101 isl_multi_pw_aff_free(tuple
);
4106 isl_multi_pw_aff_free(tuple
);
4109 isl_multi_aff_free(ma
);
4113 __isl_give isl_multi_aff
*isl_multi_aff_read_from_str(isl_ctx
*ctx
,
4116 isl_multi_aff
*maff
;
4117 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
4120 maff
= isl_stream_read_multi_aff(s
);
4125 /* Read an isl_multi_pw_aff from "s".
4127 * The input format is similar to that of map, except that any conditions
4128 * on the domains should be specified inside the tuple since each
4129 * piecewise affine expression may have a different domain.
4130 * However, additional, shared conditions can also be specified.
4131 * This is especially useful for setting the explicit domain
4132 * of a zero-dimensional isl_multi_pw_aff.
4134 * Since we do not know in advance if the isl_multi_pw_aff lives
4135 * in a set or a map space, we first read the first tuple and check
4136 * if it is followed by a "->". If so, we convert the tuple into
4137 * the domain of the isl_multi_pw_aff and read in the next tuple.
4138 * This tuple (or the first tuple if it was not followed by a "->")
4139 * is then converted into the isl_multi_pw_aff through a call
4140 * to extract_mpa_from_tuple and the domain of the result
4141 * is intersected with the domain.
4143 * Note that the last tuple may introduce new identifiers,
4144 * but these cannot be referenced in the description of the domain.
4146 __isl_give isl_multi_pw_aff
*isl_stream_read_multi_pw_aff(
4147 __isl_keep isl_stream
*s
)
4151 isl_set
*dom
= NULL
;
4152 isl_multi_pw_aff
*tuple
= NULL
;
4153 isl_multi_pw_aff
*mpa
= NULL
;
4155 v
= vars_new(s
->ctx
);
4159 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
4160 if (next_is_tuple(s
)) {
4161 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
4162 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
4165 if (isl_stream_eat(s
, '{'))
4169 tuple
= read_tuple(s
, v
, 0, 0);
4172 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TO
)) {
4173 isl_map
*map
= map_from_tuple(tuple
, dom
, isl_dim_in
, v
, 0);
4174 dom
= isl_map_domain(map
);
4176 tuple
= read_tuple(s
, v
, 0, 0);
4181 vars_drop(v
, v
->n
- n_dom
);
4182 if (isl_stream_eat_if_available(s
, ':'))
4183 dom
= read_formula(s
, v
, dom
, 0);
4185 if (isl_stream_eat(s
, '}'))
4188 mpa
= extract_mpa_from_tuple(isl_set_get_space(dom
), tuple
);
4190 isl_multi_pw_aff_free(tuple
);
4192 mpa
= isl_multi_pw_aff_intersect_domain(mpa
, dom
);
4195 isl_multi_pw_aff_free(tuple
);
4198 isl_multi_pw_aff_free(mpa
);
4202 /* Read an isl_multi_pw_aff from "str".
4204 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_read_from_str(isl_ctx
*ctx
,
4207 isl_multi_pw_aff
*mpa
;
4208 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
4211 mpa
= isl_stream_read_multi_pw_aff(s
);
4216 /* Read the body of an isl_union_pw_aff from "s" with parameter domain "dom".
4218 static __isl_give isl_union_pw_aff
*read_union_pw_aff_with_dom(
4219 __isl_keep isl_stream
*s
, __isl_take isl_set
*dom
, struct vars
*v
)
4222 isl_union_pw_aff
*upa
= NULL
;
4227 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
4228 pa
= read_pw_aff_with_dom(s
, aff_dom
, v
);
4229 vars_drop(v
, v
->n
- n
);
4231 upa
= isl_union_pw_aff_from_pw_aff(pa
);
4233 while (isl_stream_eat_if_available(s
, ';')) {
4235 isl_union_pw_aff
*upa_i
;
4238 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
4239 pa_i
= read_pw_aff_with_dom(s
, aff_dom
, v
);
4240 vars_drop(v
, v
->n
- n
);
4242 upa_i
= isl_union_pw_aff_from_pw_aff(pa_i
);
4243 upa
= isl_union_pw_aff_union_add(upa
, upa_i
);
4250 /* Read an isl_union_pw_aff from "s".
4252 * First check if there are any paramters, then read in the opening brace
4253 * and use read_union_pw_aff_with_dom to read in the body of
4254 * the isl_union_pw_aff. Finally, read the closing brace.
4256 __isl_give isl_union_pw_aff
*isl_stream_read_union_pw_aff(
4257 __isl_keep isl_stream
*s
)
4261 isl_union_pw_aff
*upa
= NULL
;
4263 v
= vars_new(s
->ctx
);
4267 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
4268 if (next_is_tuple(s
)) {
4269 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
4270 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
4273 if (isl_stream_eat(s
, '{'))
4276 upa
= read_union_pw_aff_with_dom(s
, isl_set_copy(dom
), v
);
4278 if (isl_stream_eat(s
, '}'))
4287 isl_union_pw_aff_free(upa
);
4291 /* Read an isl_union_pw_aff from "str".
4293 __isl_give isl_union_pw_aff
*isl_union_pw_aff_read_from_str(isl_ctx
*ctx
,
4296 isl_union_pw_aff
*upa
;
4297 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
4300 upa
= isl_stream_read_union_pw_aff(s
);
4305 /* This function is called for each element in a tuple inside
4306 * isl_stream_read_multi_union_pw_aff.
4308 * Read a '{', the union piecewise affine expression body and a '}' and
4309 * add the isl_union_pw_aff to *list.
4311 static __isl_give isl_space
*read_union_pw_aff_el(__isl_keep isl_stream
*s
,
4312 struct vars
*v
, __isl_take isl_space
*space
, int rational
, void *user
)
4315 isl_union_pw_aff
*upa
;
4316 isl_union_pw_aff_list
**list
= (isl_union_pw_aff_list
**) user
;
4318 dom
= isl_set_universe(isl_space_params(isl_space_copy(space
)));
4319 if (isl_stream_eat(s
, '{'))
4321 upa
= read_union_pw_aff_with_dom(s
, dom
, v
);
4322 *list
= isl_union_pw_aff_list_add(*list
, upa
);
4323 if (isl_stream_eat(s
, '}'))
4324 return isl_space_free(space
);
4326 return isl_space_free(space
);
4330 return isl_space_free(space
);
4333 /* Do the next tokens in "s" correspond to an empty tuple?
4334 * In particular, does the stream start with a '[', followed by a ']',
4335 * not followed by a "->"?
4337 static int next_is_empty_tuple(__isl_keep isl_stream
*s
)
4339 struct isl_token
*tok
, *tok2
, *tok3
;
4340 int is_empty_tuple
= 0;
4342 tok
= isl_stream_next_token(s
);
4345 if (tok
->type
!= '[') {
4346 isl_stream_push_token(s
, tok
);
4350 tok2
= isl_stream_next_token(s
);
4351 if (tok2
&& tok2
->type
== ']') {
4352 tok3
= isl_stream_next_token(s
);
4353 is_empty_tuple
= !tok
|| tok
->type
!= ISL_TOKEN_TO
;
4355 isl_stream_push_token(s
, tok3
);
4358 isl_stream_push_token(s
, tok2
);
4359 isl_stream_push_token(s
, tok
);
4361 return is_empty_tuple
;
4364 /* Do the next tokens in "s" correspond to a tuple of parameters?
4365 * In particular, does the stream start with a '[' that is not
4366 * followed by a '{' or a nested tuple?
4368 static int next_is_param_tuple(__isl_keep isl_stream
*s
)
4370 struct isl_token
*tok
, *tok2
;
4373 tok
= isl_stream_next_token(s
);
4376 if (tok
->type
!= '[' || next_is_tuple(s
)) {
4377 isl_stream_push_token(s
, tok
);
4381 tok2
= isl_stream_next_token(s
);
4382 is_tuple
= tok2
&& tok2
->type
!= '{';
4384 isl_stream_push_token(s
, tok2
);
4385 isl_stream_push_token(s
, tok
);
4390 /* Read the core of a body of an isl_multi_union_pw_aff from "s",
4391 * i.e., everything except the parameter specification and
4392 * without shared domain constraints.
4393 * "v" contains a description of the identifiers parsed so far.
4394 * The parameters, if any, are specified by "space".
4396 * The body is of the form
4398 * [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4400 * Read the tuple, collecting the individual isl_union_pw_aff
4401 * elements in a list and construct the result from the tuple space and
4404 static __isl_give isl_multi_union_pw_aff
*read_multi_union_pw_aff_body_core(
4405 __isl_keep isl_stream
*s
, struct vars
*v
, __isl_take isl_space
*space
)
4407 isl_union_pw_aff_list
*list
;
4408 isl_multi_union_pw_aff
*mupa
;
4410 list
= isl_union_pw_aff_list_alloc(s
->ctx
, 0);
4411 space
= read_tuple_space(s
, v
, space
, 1, 0,
4412 &read_union_pw_aff_el
, &list
);
4413 mupa
= isl_multi_union_pw_aff_from_union_pw_aff_list(space
, list
);
4418 /* Read the body of an isl_union_set from "s",
4419 * i.e., everything except the parameter specification.
4420 * "v" contains a description of the identifiers parsed so far.
4421 * The parameters, if any, are specified by "space".
4423 * First read a generic disjunction of object bodies and then try and extract
4424 * an isl_union_set from that.
4426 static __isl_give isl_union_set
*read_union_set_body(__isl_keep isl_stream
*s
,
4427 struct vars
*v
, __isl_take isl_space
*space
)
4429 struct isl_obj obj
= { isl_obj_set
, NULL
};
4432 map
= isl_set_universe(space
);
4433 if (isl_stream_eat(s
, '{') < 0)
4435 obj
= obj_read_disjuncts(s
, v
, map
);
4436 if (isl_stream_eat(s
, '}') < 0)
4440 return extract_union_set(s
->ctx
, obj
);
4442 obj
.type
->free(obj
.v
);
4447 /* Read the body of an isl_multi_union_pw_aff from "s",
4448 * i.e., everything except the parameter specification.
4449 * "v" contains a description of the identifiers parsed so far.
4450 * The parameters, if any, are specified by "space".
4452 * In particular, handle the special case with shared domain constraints.
4453 * These are specified as
4457 * and are especially useful for setting the explicit domain
4458 * of a zero-dimensional isl_multi_union_pw_aff.
4459 * The core isl_multi_union_pw_aff body ([...]) is read by
4460 * read_multi_union_pw_aff_body_core.
4462 static __isl_give isl_multi_union_pw_aff
*read_multi_union_pw_aff_body(
4463 __isl_keep isl_stream
*s
, struct vars
*v
, __isl_take isl_space
*space
)
4465 isl_multi_union_pw_aff
*mupa
;
4467 if (!isl_stream_next_token_is(s
, '('))
4468 return read_multi_union_pw_aff_body_core(s
, v
, space
);
4470 if (isl_stream_eat(s
, '(') < 0)
4472 mupa
= read_multi_union_pw_aff_body_core(s
, v
, isl_space_copy(space
));
4473 if (isl_stream_eat_if_available(s
, ':')) {
4476 dom
= read_union_set_body(s
, v
, space
);
4477 mupa
= isl_multi_union_pw_aff_intersect_domain(mupa
, dom
);
4479 isl_space_free(space
);
4481 if (isl_stream_eat(s
, ')') < 0)
4482 return isl_multi_union_pw_aff_free(mupa
);
4486 isl_space_free(space
);
4490 /* Read an isl_multi_union_pw_aff from "s".
4492 * The input has the form
4494 * [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4498 * [..] -> [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4500 * Additionally, a shared domain may be specified as
4506 * [..] -> ([..] : ...)
4508 * The first case is handled by the caller, the second case
4509 * is handled by read_multi_union_pw_aff_body.
4511 * We first check for the special case of an empty tuple "[]".
4512 * Then we check if there are any parameters.
4513 * Finally, read the tuple and construct the result.
4515 static __isl_give isl_multi_union_pw_aff
*read_multi_union_pw_aff_core(
4516 __isl_keep isl_stream
*s
)
4519 isl_set
*dom
= NULL
;
4521 isl_multi_union_pw_aff
*mupa
= NULL
;
4523 if (next_is_empty_tuple(s
)) {
4524 if (isl_stream_eat(s
, '['))
4526 if (isl_stream_eat(s
, ']'))
4528 space
= isl_space_set_alloc(s
->ctx
, 0, 0);
4529 return isl_multi_union_pw_aff_zero(space
);
4532 v
= vars_new(s
->ctx
);
4536 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
4537 if (next_is_param_tuple(s
)) {
4538 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
4539 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
4542 space
= isl_set_get_space(dom
);
4544 mupa
= read_multi_union_pw_aff_body(s
, v
, space
);
4552 isl_multi_union_pw_aff_free(mupa
);
4556 /* Read an isl_multi_union_pw_aff from "s".
4558 * In particular, handle the special case with shared domain constraints.
4559 * These are specified as
4563 * and are especially useful for setting the explicit domain
4564 * of a zero-dimensional isl_multi_union_pw_aff.
4565 * The core isl_multi_union_pw_aff ([...]) is read by
4566 * read_multi_union_pw_aff_core.
4568 __isl_give isl_multi_union_pw_aff
*isl_stream_read_multi_union_pw_aff(
4569 __isl_keep isl_stream
*s
)
4571 isl_multi_union_pw_aff
*mupa
;
4573 if (!isl_stream_next_token_is(s
, '('))
4574 return read_multi_union_pw_aff_core(s
);
4576 if (isl_stream_eat(s
, '(') < 0)
4578 mupa
= read_multi_union_pw_aff_core(s
);
4579 if (isl_stream_eat_if_available(s
, ':')) {
4582 dom
= isl_stream_read_union_set(s
);
4583 mupa
= isl_multi_union_pw_aff_intersect_domain(mupa
, dom
);
4585 if (isl_stream_eat(s
, ')') < 0)
4586 return isl_multi_union_pw_aff_free(mupa
);
4590 /* Read an isl_multi_union_pw_aff from "str".
4592 __isl_give isl_multi_union_pw_aff
*isl_multi_union_pw_aff_read_from_str(
4593 isl_ctx
*ctx
, const char *str
)
4595 isl_multi_union_pw_aff
*mupa
;
4596 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
4599 mupa
= isl_stream_read_multi_union_pw_aff(s
);
4604 __isl_give isl_union_pw_qpolynomial
*isl_stream_read_union_pw_qpolynomial(
4605 __isl_keep isl_stream
*s
)
4610 if (obj
.type
== isl_obj_pw_qpolynomial
) {
4611 obj
.type
= isl_obj_union_pw_qpolynomial
;
4612 obj
.v
= isl_union_pw_qpolynomial_from_pw_qpolynomial(obj
.v
);
4615 isl_assert(s
->ctx
, obj
.type
== isl_obj_union_pw_qpolynomial
,
4620 obj
.type
->free(obj
.v
);
4624 __isl_give isl_union_pw_qpolynomial
*isl_union_pw_qpolynomial_read_from_str(
4625 isl_ctx
*ctx
, const char *str
)
4627 isl_union_pw_qpolynomial
*upwqp
;
4628 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
4631 upwqp
= isl_stream_read_union_pw_qpolynomial(s
);