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
185 * "-" n "/" d -> -n/d
189 * where n, d and v are integer constants.
191 __isl_give isl_val
*isl_stream_read_val(__isl_keep isl_stream
*s
)
193 struct isl_token
*tok
= NULL
;
194 struct isl_token
*tok2
= NULL
;
198 if (isl_stream_eat_if_available(s
, '-'))
202 isl_stream_error(s
, NULL
, "unexpected EOF");
205 if (tok
->type
== ISL_TOKEN_INFTY
) {
208 return isl_val_infty(s
->ctx
);
210 return isl_val_neginfty(s
->ctx
);
212 if (sign
> 0 && tok
->type
== ISL_TOKEN_NAN
) {
214 return isl_val_nan(s
->ctx
);
216 if (tok
->type
!= ISL_TOKEN_VALUE
) {
217 isl_stream_error(s
, tok
, "expecting value");
222 isl_int_neg(tok
->u
.v
, tok
->u
.v
);
224 if (isl_stream_eat_if_available(s
, '/')) {
225 tok2
= next_token(s
);
227 isl_stream_error(s
, NULL
, "unexpected EOF");
230 if (tok2
->type
!= ISL_TOKEN_VALUE
) {
231 isl_stream_error(s
, tok2
, "expecting value");
234 val
= isl_val_rat_from_isl_int(s
->ctx
, tok
->u
.v
, tok2
->u
.v
);
235 val
= isl_val_normalize(val
);
237 val
= isl_val_int_from_isl_int(s
->ctx
, tok
->u
.v
);
241 isl_token_free(tok2
);
245 isl_token_free(tok2
);
250 #define TYPE_BASE val
251 #include "isl_read_from_str_templ.c"
253 static isl_stat
accept_cst_factor(__isl_keep isl_stream
*s
, isl_int
*f
)
255 struct isl_token
*tok
;
257 if (isl_stream_eat_if_available(s
, '-'))
260 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
261 isl_stream_error(s
, tok
, "expecting constant value");
265 isl_int_mul(*f
, *f
, tok
->u
.v
);
269 if (isl_stream_eat_if_available(s
, '*'))
270 return accept_cst_factor(s
, f
);
275 return isl_stat_error
;
278 /* Given an affine expression aff, return an affine expression
279 * for aff % d, with d the next token on the stream, which is
280 * assumed to be a constant.
282 * We introduce an integer division q = [aff/d] and the result
283 * is set to aff - d q.
285 static __isl_give isl_pw_aff
*affine_mod(__isl_keep isl_stream
*s
,
286 struct vars
*v
, __isl_take isl_pw_aff
*aff
)
288 struct isl_token
*tok
;
292 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
293 isl_stream_error(s
, tok
, "expecting constant value");
297 q
= isl_pw_aff_copy(aff
);
298 q
= isl_pw_aff_scale_down(q
, tok
->u
.v
);
299 q
= isl_pw_aff_floor(q
);
300 q
= isl_pw_aff_scale(q
, tok
->u
.v
);
302 aff
= isl_pw_aff_sub(aff
, q
);
307 isl_pw_aff_free(aff
);
312 static __isl_give isl_pw_aff
*accept_affine(__isl_keep isl_stream
*s
,
313 __isl_take isl_space
*space
, struct vars
*v
);
314 static __isl_give isl_pw_aff_list
*accept_affine_list(__isl_keep isl_stream
*s
,
315 __isl_take isl_space
*space
, struct vars
*v
);
317 static __isl_give isl_pw_aff
*accept_minmax(__isl_keep isl_stream
*s
,
318 __isl_take isl_space
*space
, struct vars
*v
)
320 struct isl_token
*tok
;
321 isl_pw_aff_list
*list
= NULL
;
324 tok
= isl_stream_next_token(s
);
327 min
= tok
->type
== ISL_TOKEN_MIN
;
330 if (isl_stream_eat(s
, '('))
333 list
= accept_affine_list(s
, isl_space_copy(space
), v
);
337 if (isl_stream_eat(s
, ')'))
340 isl_space_free(space
);
341 return min
? isl_pw_aff_list_min(list
) : isl_pw_aff_list_max(list
);
343 isl_space_free(space
);
344 isl_pw_aff_list_free(list
);
348 /* Divide "pa" by an integer constant read from the stream.
350 static __isl_give isl_pw_aff
*pw_aff_div_by_cst(__isl_keep isl_stream
*s
,
351 __isl_take isl_pw_aff
*pa
)
353 struct isl_token
*tok
;
356 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
357 isl_stream_error(s
, tok
, "expecting denominator");
359 return isl_pw_aff_free(pa
);
362 pa
= isl_pw_aff_scale_down(pa
, tok
->u
.v
);
369 /* Return the (signed) value that is next on the stream,
370 * using "next" to read the next token and printing "msg" in case of an error.
372 static struct isl_token
*next_signed_value_fn(__isl_keep isl_stream
*s
,
373 struct isl_token
*(*next
)(__isl_keep isl_stream
*s
), char *msg
)
375 struct isl_token
*tok
;
378 if (isl_stream_eat_if_available(s
, '-'))
381 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
382 isl_stream_error(s
, tok
, msg
);
387 isl_int_neg(tok
->u
.v
, tok
->u
.v
);
391 /* Return the (signed) value that is next on the stream,
392 * printing "msg" in case of an error.
394 static struct isl_token
*next_signed_value(__isl_keep isl_stream
*s
, char *msg
)
396 return next_signed_value_fn(s
, &isl_stream_next_token
, msg
);
399 /* Return the (signed) value that is next on the stream,
400 * provided it is on the same line,
401 * printing "msg" in case of an error.
403 static struct isl_token
*next_signed_value_on_same_line(
404 __isl_keep isl_stream
*s
, char *msg
)
406 return next_signed_value_fn(s
,
407 &isl_stream_next_token_on_same_line
, msg
);
410 /* Is "tok" the start of an integer division?
412 static int is_start_of_div(struct isl_token
*tok
)
416 if (tok
->type
== '[')
418 if (tok
->type
== ISL_TOKEN_FLOOR
)
420 if (tok
->type
== ISL_TOKEN_CEIL
)
422 if (tok
->type
== ISL_TOKEN_FLOORD
)
424 if (tok
->type
== ISL_TOKEN_CEILD
)
429 /* Read an integer division from "s" and return it as an isl_pw_aff.
431 * The integer division can be of the form
433 * [<affine expression>]
434 * floor(<affine expression>)
435 * ceil(<affine expression>)
436 * floord(<affine expression>,<denominator>)
437 * ceild(<affine expression>,<denominator>)
439 static __isl_give isl_pw_aff
*accept_div(__isl_keep isl_stream
*s
,
440 __isl_take isl_space
*space
, struct vars
*v
)
445 isl_pw_aff
*pwaff
= NULL
;
447 if (isl_stream_eat_if_available(s
, ISL_TOKEN_FLOORD
))
449 else if (isl_stream_eat_if_available(s
, ISL_TOKEN_CEILD
))
451 else if (isl_stream_eat_if_available(s
, ISL_TOKEN_FLOOR
))
453 else if (isl_stream_eat_if_available(s
, ISL_TOKEN_CEIL
))
456 if (isl_stream_eat(s
, '('))
459 if (isl_stream_eat(s
, '['))
463 pwaff
= accept_affine(s
, isl_space_copy(space
), v
);
466 if (isl_stream_eat(s
, ','))
469 pwaff
= pw_aff_div_by_cst(s
, pwaff
);
473 pwaff
= isl_pw_aff_ceil(pwaff
);
475 pwaff
= isl_pw_aff_floor(pwaff
);
478 if (isl_stream_eat(s
, ')'))
481 if (isl_stream_eat(s
, ']'))
485 isl_space_free(space
);
488 isl_space_free(space
);
489 isl_pw_aff_free(pwaff
);
493 static __isl_give isl_pw_aff
*accept_affine_factor(__isl_keep isl_stream
*s
,
494 __isl_take isl_space
*space
, struct vars
*v
)
496 struct isl_token
*tok
= NULL
;
497 isl_pw_aff
*res
= NULL
;
501 isl_stream_error(s
, NULL
, "unexpected EOF");
505 if (tok
->type
== ISL_TOKEN_AFF
) {
506 res
= isl_pw_aff_copy(tok
->u
.pwaff
);
508 } else if (tok
->type
== ISL_TOKEN_IDENT
) {
510 int pos
= vars_pos(v
, tok
->u
.s
, -1);
516 vars_drop(v
, v
->n
- n
);
517 isl_stream_error(s
, tok
, "unknown identifier");
521 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(isl_space_copy(space
)));
524 aff
->v
= isl_vec_set_element_si(aff
->v
, 2 + pos
, 1);
526 aff
= isl_aff_free(aff
);
527 res
= isl_pw_aff_from_aff(aff
);
529 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
530 if (isl_stream_eat_if_available(s
, '*') ||
531 isl_stream_next_token_is(s
, ISL_TOKEN_IDENT
)) {
532 if (isl_stream_eat_if_available(s
, '-'))
533 isl_int_neg(tok
->u
.v
, tok
->u
.v
);
534 res
= accept_affine_factor(s
, isl_space_copy(space
), v
);
535 res
= isl_pw_aff_scale(res
, tok
->u
.v
);
539 ls
= isl_local_space_from_space(isl_space_copy(space
));
540 aff
= isl_aff_zero_on_domain(ls
);
541 aff
= isl_aff_add_constant(aff
, tok
->u
.v
);
542 res
= isl_pw_aff_from_aff(aff
);
545 } else if (tok
->type
== '(') {
548 res
= accept_affine(s
, isl_space_copy(space
), v
);
551 if (isl_stream_eat(s
, ')'))
553 } else if (is_start_of_div(tok
)) {
554 isl_stream_push_token(s
, tok
);
556 res
= accept_div(s
, isl_space_copy(space
), v
);
557 } else if (tok
->type
== ISL_TOKEN_MIN
|| tok
->type
== ISL_TOKEN_MAX
) {
558 isl_stream_push_token(s
, tok
);
560 res
= accept_minmax(s
, isl_space_copy(space
), v
);
562 isl_stream_error(s
, tok
, "expecting factor");
565 if (isl_stream_eat_if_available(s
, '%') ||
566 isl_stream_eat_if_available(s
, ISL_TOKEN_MOD
)) {
567 isl_space_free(space
);
568 return affine_mod(s
, v
, res
);
570 if (isl_stream_eat_if_available(s
, '*')) {
573 isl_int_set_si(f
, 1);
574 if (accept_cst_factor(s
, &f
) < 0) {
578 res
= isl_pw_aff_scale(res
, f
);
581 if (isl_stream_eat_if_available(s
, '/'))
582 res
= pw_aff_div_by_cst(s
, res
);
583 if (isl_stream_eat_if_available(s
, ISL_TOKEN_INT_DIV
))
584 res
= isl_pw_aff_floor(pw_aff_div_by_cst(s
, res
));
586 isl_space_free(space
);
591 isl_pw_aff_free(res
);
592 isl_space_free(space
);
596 /* Return a piecewise affine expression defined on the specified domain
597 * that represents NaN.
599 static __isl_give isl_pw_aff
*nan_on_domain(__isl_keep isl_space
*space
)
601 return isl_pw_aff_nan_on_domain_space(isl_space_copy(space
));
604 static __isl_give isl_pw_aff
*accept_affine(__isl_keep isl_stream
*s
,
605 __isl_take isl_space
*space
, struct vars
*v
)
607 struct isl_token
*tok
= NULL
;
613 ls
= isl_local_space_from_space(isl_space_copy(space
));
614 res
= isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls
));
621 isl_stream_error(s
, NULL
, "unexpected EOF");
624 if (tok
->type
== '-') {
629 if (tok
->type
== '(' || is_start_of_div(tok
) ||
630 tok
->type
== ISL_TOKEN_MIN
|| tok
->type
== ISL_TOKEN_MAX
||
631 tok
->type
== ISL_TOKEN_IDENT
||
632 tok
->type
== ISL_TOKEN_VALUE
||
633 tok
->type
== ISL_TOKEN_AFF
) {
635 if (tok
->type
== ISL_TOKEN_VALUE
&& sign
< 0) {
636 isl_int_neg(tok
->u
.v
, tok
->u
.v
);
639 isl_stream_push_token(s
, tok
);
641 term
= accept_affine_factor(s
,
642 isl_space_copy(space
), v
);
644 res
= isl_pw_aff_sub(res
, term
);
646 res
= isl_pw_aff_add(res
, term
);
649 } else if (tok
->type
== ISL_TOKEN_NAN
) {
650 res
= isl_pw_aff_add(res
, nan_on_domain(space
));
652 isl_stream_error(s
, tok
, "unexpected isl_token");
653 isl_stream_push_token(s
, tok
);
654 isl_pw_aff_free(res
);
655 isl_space_free(space
);
662 if (tok
&& tok
->type
== '-') {
665 } else if (tok
&& tok
->type
== '+') {
670 isl_stream_push_token(s
, tok
);
675 isl_space_free(space
);
678 isl_space_free(space
);
680 isl_pw_aff_free(res
);
684 /* Is "type" the type of a comparison operator between lists
685 * of affine expressions?
687 static int is_list_comparator_type(int type
)
690 case ISL_TOKEN_LEX_LT
:
691 case ISL_TOKEN_LEX_GT
:
692 case ISL_TOKEN_LEX_LE
:
693 case ISL_TOKEN_LEX_GE
:
700 static int is_comparator(struct isl_token
*tok
)
704 if (is_list_comparator_type(tok
->type
))
720 static __isl_give isl_map
*read_formula(__isl_keep isl_stream
*s
,
721 struct vars
*v
, __isl_take isl_map
*map
, int rational
);
722 static __isl_give isl_pw_aff
*accept_extended_affine(__isl_keep isl_stream
*s
,
723 __isl_take isl_space
*space
, struct vars
*v
, int rational
);
725 /* Accept a ternary operator, given the first argument.
727 static __isl_give isl_pw_aff
*accept_ternary(__isl_keep isl_stream
*s
,
728 __isl_take isl_map
*cond
, struct vars
*v
, int rational
)
731 isl_pw_aff
*pwaff1
= NULL
, *pwaff2
= NULL
, *pa_cond
;
736 if (isl_stream_eat(s
, '?'))
739 space
= isl_space_wrap(isl_map_get_space(cond
));
740 pwaff1
= accept_extended_affine(s
, space
, v
, rational
);
744 if (isl_stream_eat(s
, ':'))
747 space
= isl_pw_aff_get_domain_space(pwaff1
);
748 pwaff2
= accept_extended_affine(s
, space
, v
, rational
);
752 pa_cond
= isl_set_indicator_function(isl_map_wrap(cond
));
753 return isl_pw_aff_cond(pa_cond
, pwaff1
, pwaff2
);
756 isl_pw_aff_free(pwaff1
);
757 isl_pw_aff_free(pwaff2
);
761 /* Set *line and *col to those of the next token, if any.
763 static void set_current_line_col(__isl_keep isl_stream
*s
, int *line
, int *col
)
765 struct isl_token
*tok
;
767 tok
= isl_stream_next_token(s
);
773 isl_stream_push_token(s
, tok
);
776 /* Push a token encapsulating "pa" onto "s", with the given
779 static isl_stat
push_aff(__isl_keep isl_stream
*s
, int line
, int col
,
780 __isl_take isl_pw_aff
*pa
)
782 struct isl_token
*tok
;
784 tok
= isl_token_new(s
->ctx
, line
, col
, 0);
787 tok
->type
= ISL_TOKEN_AFF
;
789 isl_stream_push_token(s
, tok
);
794 return isl_stat_error
;
797 /* Is the next token a comparison operator?
799 static int next_is_comparator(__isl_keep isl_stream
*s
)
802 struct isl_token
*tok
;
804 tok
= isl_stream_next_token(s
);
808 is_comp
= is_comparator(tok
);
809 isl_stream_push_token(s
, tok
);
814 /* Accept an affine expression that may involve ternary operators.
815 * We first read an affine expression.
816 * If it is not followed by a comparison operator, we simply return it.
817 * Otherwise, we assume the affine expression is part of the first
818 * argument of a ternary operator and try to parse that.
820 static __isl_give isl_pw_aff
*accept_extended_affine(__isl_keep isl_stream
*s
,
821 __isl_take isl_space
*space
, struct vars
*v
, int rational
)
825 int line
= -1, col
= -1;
827 set_current_line_col(s
, &line
, &col
);
829 pwaff
= accept_affine(s
, space
, v
);
831 pwaff
= isl_pw_aff_set_rational(pwaff
);
834 if (!next_is_comparator(s
))
837 space
= isl_pw_aff_get_domain_space(pwaff
);
838 cond
= isl_map_universe(isl_space_unwrap(space
));
840 if (push_aff(s
, line
, col
, pwaff
) < 0)
841 cond
= isl_map_free(cond
);
845 cond
= read_formula(s
, v
, cond
, rational
);
847 return accept_ternary(s
, cond
, v
, rational
);
850 static __isl_give isl_map
*read_var_def(__isl_keep isl_stream
*s
,
851 __isl_take isl_map
*map
, enum isl_dim_type type
, struct vars
*v
,
858 if (type
== isl_dim_param
)
859 pos
= isl_map_dim(map
, isl_dim_param
);
861 pos
= isl_map_dim(map
, isl_dim_in
);
862 if (type
== isl_dim_out
) {
863 isl_size n_out
= isl_map_dim(map
, isl_dim_out
);
864 if (pos
< 0 || n_out
< 0)
865 return isl_map_free(map
);
871 return isl_map_free(map
);
874 def
= accept_extended_affine(s
, isl_space_wrap(isl_map_get_space(map
)),
876 def_map
= isl_map_from_pw_aff(def
);
877 def_map
= isl_map_equate(def_map
, type
, pos
, isl_dim_out
, 0);
878 def_map
= isl_set_unwrap(isl_map_domain(def_map
));
880 map
= isl_map_intersect(map
, def_map
);
885 static __isl_give isl_pw_aff_list
*accept_affine_list(__isl_keep isl_stream
*s
,
886 __isl_take isl_space
*space
, struct vars
*v
)
889 isl_pw_aff_list
*list
;
890 struct isl_token
*tok
= NULL
;
892 pwaff
= accept_affine(s
, isl_space_copy(space
), v
);
893 list
= isl_pw_aff_list_from_pw_aff(pwaff
);
898 tok
= isl_stream_next_token(s
);
900 isl_stream_error(s
, NULL
, "unexpected EOF");
903 if (tok
->type
!= ',') {
904 isl_stream_push_token(s
, tok
);
909 pwaff
= accept_affine(s
, isl_space_copy(space
), v
);
910 list
= isl_pw_aff_list_concat(list
,
911 isl_pw_aff_list_from_pw_aff(pwaff
));
916 isl_space_free(space
);
919 isl_space_free(space
);
920 isl_pw_aff_list_free(list
);
924 static __isl_give isl_map
*read_defined_var_list(__isl_keep isl_stream
*s
,
925 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
927 struct isl_token
*tok
;
929 while ((tok
= isl_stream_next_token(s
)) != NULL
) {
933 if (tok
->type
!= ISL_TOKEN_IDENT
)
936 p
= vars_pos(v
, tok
->u
.s
, -1);
940 isl_stream_error(s
, tok
, "expecting unique identifier");
944 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
947 tok
= isl_stream_next_token(s
);
948 if (tok
&& tok
->type
== '=') {
950 map
= read_var_def(s
, map
, isl_dim_out
, v
, rational
);
951 tok
= isl_stream_next_token(s
);
954 if (!tok
|| tok
->type
!= ',')
960 isl_stream_push_token(s
, tok
);
969 static int next_is_tuple(__isl_keep isl_stream
*s
)
971 struct isl_token
*tok
;
974 tok
= isl_stream_next_token(s
);
977 if (tok
->type
== '[') {
978 isl_stream_push_token(s
, tok
);
981 if (tok
->type
!= ISL_TOKEN_IDENT
&& !tok
->is_keyword
) {
982 isl_stream_push_token(s
, tok
);
986 is_tuple
= isl_stream_next_token_is(s
, '[');
988 isl_stream_push_token(s
, tok
);
993 /* Does the next token mark the end of a tuple element?
995 static int next_is_end_tuple_element(__isl_keep isl_stream
*s
)
997 return isl_stream_next_token_is(s
, ',') ||
998 isl_stream_next_token_is(s
, ']');
1001 /* Is the next token one that necessarily forms the start of a condition?
1003 static int next_is_condition_start(__isl_keep isl_stream
*s
)
1005 return isl_stream_next_token_is(s
, ISL_TOKEN_EXISTS
) ||
1006 isl_stream_next_token_is(s
, ISL_TOKEN_NOT
) ||
1007 isl_stream_next_token_is(s
, ISL_TOKEN_TRUE
) ||
1008 isl_stream_next_token_is(s
, ISL_TOKEN_FALSE
) ||
1009 isl_stream_next_token_is(s
, ISL_TOKEN_MAP
);
1012 /* Is "pa" an expression in term of earlier dimensions?
1013 * The alternative is that the dimension is defined to be equal to itself,
1014 * meaning that it has a universe domain and an expression that depends
1015 * on itself. "i" is the position of the expression in a sequence
1016 * of "n" expressions. The final dimensions of "pa" correspond to
1017 * these "n" expressions.
1019 static isl_bool
pw_aff_is_expr(__isl_keep isl_pw_aff
*pa
, int i
, int n
)
1024 return isl_bool_error
;
1026 return isl_bool_true
;
1027 if (!isl_set_plain_is_universe(pa
->p
[0].set
))
1028 return isl_bool_true
;
1031 if (isl_int_is_zero(aff
->v
->el
[aff
->v
->size
- n
+ i
]))
1032 return isl_bool_true
;
1033 return isl_bool_false
;
1036 /* Does the tuple contain any dimensions that are defined
1037 * in terms of earlier dimensions?
1039 static isl_bool
tuple_has_expr(__isl_keep isl_multi_pw_aff
*tuple
)
1043 isl_bool has_expr
= isl_bool_false
;
1046 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
1048 return isl_bool_error
;
1049 for (i
= 0; i
< n
; ++i
) {
1050 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
1051 has_expr
= pw_aff_is_expr(pa
, i
, n
);
1052 isl_pw_aff_free(pa
);
1053 if (has_expr
< 0 || has_expr
)
1060 /* Set the name of dimension "pos" in "space" to "name".
1061 * During printing, we add primes if the same name appears more than once
1062 * to distinguish the occurrences. Here, we remove those primes from "name"
1063 * before setting the name of the dimension.
1065 static __isl_give isl_space
*space_set_dim_name(__isl_take isl_space
*space
,
1066 int pos
, char *name
)
1073 prime
= strchr(name
, '\'');
1076 space
= isl_space_set_dim_name(space
, isl_dim_out
, pos
, name
);
1083 /* Set the name of the last (output) dimension of "space" to "name",
1084 * ignoring any primes in "name".
1086 static __isl_give isl_space
*space_set_last_dim_name(
1087 __isl_take isl_space
*space
, char *name
)
1091 pos
= isl_space_dim(space
, isl_dim_out
);
1093 return isl_space_free(space
);
1094 return space_set_dim_name(space
, pos
- 1, name
);
1097 /* Construct an isl_pw_aff defined on a "space" (with v->n variables)
1098 * that is equal to the last of those variables.
1100 static __isl_give isl_pw_aff
*identity_tuple_el_on_space(
1101 __isl_take isl_space
*space
, struct vars
*v
)
1105 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
1106 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, v
->n
- 1, 1);
1107 return isl_pw_aff_from_aff(aff
);
1110 /* Construct an isl_pw_aff defined on the domain space of "pa"
1111 * that is equal to the last variable in "v".
1113 * That is, if D is the domain space of "pa", then construct
1117 static __isl_give isl_pw_aff
*init_range(__isl_keep isl_pw_aff
*pa
,
1122 space
= isl_pw_aff_get_domain_space(pa
);
1123 return identity_tuple_el_on_space(space
, v
);
1126 /* Impose the lower bound "lower" on the variable represented by "range_pa".
1128 * In particular, "range_pa" is of the form
1130 * D[..., i] -> i : C
1132 * with D also the domains space of "lower' and "C" some constraints.
1134 * Return the expression
1136 * D[..., i] -> i : C and i >= lower
1138 static __isl_give isl_pw_aff
*set_lower(__isl_take isl_pw_aff
*range_pa
,
1139 __isl_take isl_pw_aff
*lower
)
1143 range
= isl_pw_aff_ge_set(isl_pw_aff_copy(range_pa
), lower
);
1144 return isl_pw_aff_intersect_domain(range_pa
, range
);
1147 /* Impose the upper bound "upper" on the variable represented by "range_pa".
1149 * In particular, "range_pa" is of the form
1151 * D[..., i] -> i : C
1153 * with D also the domains space of "upper' and "C" some constraints.
1155 * Return the expression
1157 * D[..., i] -> i : C and i <= upper
1159 static __isl_give isl_pw_aff
*set_upper(__isl_take isl_pw_aff
*range_pa
,
1160 __isl_take isl_pw_aff
*upper
)
1164 range
= isl_pw_aff_le_set(isl_pw_aff_copy(range_pa
), upper
);
1165 return isl_pw_aff_intersect_domain(range_pa
, range
);
1168 /* Construct a piecewise affine expression corresponding
1169 * to the last variable in "v" that is greater than or equal to "pa".
1171 * In particular, if D is the domain space of "pa",
1172 * then construct the expression
1176 * impose lower bound "pa" and return
1178 * D[..., i] -> i : i >= pa
1180 static __isl_give isl_pw_aff
*construct_lower(__isl_take isl_pw_aff
*pa
,
1183 return set_lower(init_range(pa
, v
), pa
);
1186 /* Construct a piecewise affine expression corresponding
1187 * to the last variable in "v" that is smaller than or equal to "pa".
1189 * In particular, if D is the domain space of "pa",
1190 * then construct the expression
1194 * impose lower bound "pa" and return
1196 * D[..., i] -> i : i <= pa
1198 static __isl_give isl_pw_aff
*construct_upper(__isl_take isl_pw_aff
*pa
,
1201 return set_upper(init_range(pa
, v
), pa
);
1204 /* Construct a piecewise affine expression corresponding
1205 * to the last variable in "v" that ranges between "pa" and "pa2".
1207 * In particular, if D is the domain space of "pa" (and "pa2"),
1208 * then construct the expression
1212 * impose lower bound "pa" and upper bound "pa2" and return
1214 * D[..., i] -> i : pa <= i <= pa2
1216 static __isl_give isl_pw_aff
*construct_range(__isl_take isl_pw_aff
*pa
,
1217 __isl_take isl_pw_aff
*pa2
, struct vars
*v
)
1219 return set_upper(set_lower(init_range(pa
, v
), pa
), pa2
);
1222 static int resolve_paren_expr(__isl_keep isl_stream
*s
,
1223 struct vars
*v
, __isl_take isl_map
*map
, int rational
);
1225 /* Given that the (piecewise) affine expression "pa"
1226 * has just been parsed, followed by a colon,
1227 * continue parsing as part of a piecewise affine expression.
1229 * In particular, check if the colon is followed by a condition.
1230 * If so, parse the conditions(a) on "pa" and include them in the domain.
1231 * Otherwise, if the colon is followed by another (piecewise) affine expression
1232 * then consider the two expressions as endpoints of a range of values and
1233 * return a piecewise affine expression that takes values in that range.
1234 * Note that an affine expression followed by a comparison operator
1235 * is considered to be part of a condition.
1236 * If the colon is not followed by anything (inside the tuple element),
1237 * then consider "pa" as a lower bound on a range of values without upper bound
1238 * and return a piecewise affine expression that takes values in that range.
1240 static __isl_give isl_pw_aff
*update_piecewise_affine_colon(
1241 __isl_take isl_pw_aff
*pa
, __isl_keep isl_stream
*s
,
1242 struct vars
*v
, int rational
)
1244 isl_space
*dom_space
;
1247 dom_space
= isl_pw_aff_get_domain_space(pa
);
1248 map
= isl_map_universe(isl_space_from_domain(dom_space
));
1250 if (isl_stream_next_token_is(s
, '('))
1251 if (resolve_paren_expr(s
, v
, isl_map_copy(map
), rational
))
1253 if (next_is_end_tuple_element(s
)) {
1255 return construct_lower(pa
, v
);
1257 if (!next_is_condition_start(s
)) {
1258 int line
= -1, col
= -1;
1262 set_current_line_col(s
, &line
, &col
);
1263 space
= isl_space_wrap(isl_map_get_space(map
));
1264 pa2
= accept_affine(s
, space
, v
);
1266 pa2
= isl_pw_aff_set_rational(pa2
);
1267 if (!next_is_comparator(s
)) {
1269 pa2
= isl_pw_aff_domain_factor_domain(pa2
);
1270 return construct_range(pa
, pa2
, v
);
1272 if (push_aff(s
, line
, col
, pa2
) < 0)
1276 map
= read_formula(s
, v
, map
, rational
);
1277 pa
= isl_pw_aff_intersect_domain(pa
, isl_map_domain(map
));
1282 isl_pw_aff_free(pa
);
1286 /* Accept a piecewise affine expression.
1288 * At the outer level, the piecewise affine expression may be of the form
1290 * aff1 : condition1; aff2 : conditions2; ...
1303 * each of the affine expressions may in turn include ternary operators.
1305 * If the first token is a colon, then the expression must be
1306 * ":" or ": aff2", depending on whether anything follows the colon
1307 * inside the tuple element.
1308 * The first is considered to represent an arbitrary value.
1309 * The second is considered to represent a range of values
1310 * with the given upper bound and no lower bound.
1312 * There may be parentheses around some subexpression of "aff1"
1313 * around "aff1" itself, around "aff1 : condition1" and/or
1314 * around the entire piecewise affine expression.
1315 * We therefore remove the opening parenthesis (if any) from the stream
1316 * in case the closing parenthesis follows the colon, but if the closing
1317 * parenthesis is the first thing in the stream after the parsed affine
1318 * expression, we push the parsed expression onto the stream and parse
1319 * again in case the parentheses enclose some subexpression of "aff1".
1321 static __isl_give isl_pw_aff
*accept_piecewise_affine(__isl_keep isl_stream
*s
,
1322 __isl_take isl_space
*space
, struct vars
*v
, int rational
)
1325 isl_space
*res_space
;
1327 if (isl_stream_eat_if_available(s
, ':')) {
1328 if (next_is_end_tuple_element(s
))
1329 return identity_tuple_el_on_space(space
, v
);
1331 return construct_upper(accept_affine(s
, space
, v
), v
);
1334 res_space
= isl_space_from_domain(isl_space_copy(space
));
1335 res_space
= isl_space_add_dims(res_space
, isl_dim_out
, 1);
1336 res
= isl_pw_aff_empty(res_space
);
1340 int line
= -1, col
= -1;
1342 set_current_line_col(s
, &line
, &col
);
1343 seen_paren
= isl_stream_eat_if_available(s
, '(');
1345 pa
= accept_piecewise_affine(s
, isl_space_copy(space
),
1348 pa
= accept_extended_affine(s
, isl_space_copy(space
),
1350 if (seen_paren
&& isl_stream_eat_if_available(s
, ')')) {
1352 if (push_aff(s
, line
, col
, pa
) < 0)
1354 pa
= accept_extended_affine(s
, isl_space_copy(space
),
1357 if (pa
&& isl_stream_eat_if_available(s
, ':'))
1358 pa
= update_piecewise_affine_colon(pa
, s
, v
, rational
);
1360 res
= isl_pw_aff_union_add(res
, pa
);
1362 if (!res
|| (seen_paren
&& isl_stream_eat(s
, ')')))
1364 } while (isl_stream_eat_if_available(s
, ';'));
1366 isl_space_free(space
);
1370 isl_space_free(space
);
1371 return isl_pw_aff_free(res
);
1374 /* Read an affine expression from "s" for use in read_tuple.
1376 * accept_extended_affine requires a wrapped space as input.
1377 * read_tuple on the other hand expects each isl_pw_aff
1378 * to have an anonymous space. We therefore adjust the space
1379 * of the isl_pw_aff before returning it.
1381 static __isl_give isl_pw_aff
*read_tuple_var_def(__isl_keep isl_stream
*s
,
1382 struct vars
*v
, int rational
)
1387 space
= isl_space_wrap(isl_space_alloc(s
->ctx
, 0, v
->n
, 0));
1389 def
= accept_piecewise_affine(s
, space
, v
, rational
);
1390 def
= isl_pw_aff_domain_factor_domain(def
);
1395 /* Read a list of tuple elements by calling "read_el" on each of them and
1396 * return a space with the same number of set dimensions derived from
1397 * the parameter space "space" and possibly updated by "read_el".
1398 * The elements in the list are separated by either "," or "][".
1399 * If "comma" is set then only "," is allowed.
1401 static __isl_give isl_space
*read_tuple_list(__isl_keep isl_stream
*s
,
1402 struct vars
*v
, __isl_take isl_space
*space
, int rational
, int comma
,
1403 __isl_give isl_space
*(*read_el
)(__isl_keep isl_stream
*s
,
1404 struct vars
*v
, __isl_take isl_space
*space
, int rational
,
1411 space
= isl_space_set_from_params(space
);
1413 if (isl_stream_next_token_is(s
, ']'))
1417 struct isl_token
*tok
;
1419 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1421 space
= read_el(s
, v
, space
, rational
, user
);
1425 tok
= isl_stream_next_token(s
);
1426 if (!comma
&& tok
&& tok
->type
== ']' &&
1427 isl_stream_next_token_is(s
, '[')) {
1428 isl_token_free(tok
);
1429 tok
= isl_stream_next_token(s
);
1430 } else if (!tok
|| tok
->type
!= ',') {
1432 isl_stream_push_token(s
, tok
);
1436 isl_token_free(tok
);
1442 /* Read a tuple space from "s" derived from the parameter space "space".
1443 * Call "read_el" on each element in the tuples.
1445 static __isl_give isl_space
*read_tuple_space(__isl_keep isl_stream
*s
,
1446 struct vars
*v
, __isl_take isl_space
*space
, int rational
, int comma
,
1447 __isl_give isl_space
*(*read_el
)(__isl_keep isl_stream
*s
,
1448 struct vars
*v
, __isl_take isl_space
*space
, int rational
,
1452 struct isl_token
*tok
;
1454 isl_space
*res
= NULL
;
1456 tok
= isl_stream_next_token(s
);
1459 if (tok
->type
== ISL_TOKEN_IDENT
|| tok
->is_keyword
) {
1460 name
= strdup(tok
->u
.s
);
1461 isl_token_free(tok
);
1465 isl_stream_push_token(s
, tok
);
1466 if (isl_stream_eat(s
, '['))
1468 if (next_is_tuple(s
)) {
1470 res
= read_tuple_space(s
, v
, isl_space_copy(space
),
1471 rational
, comma
, read_el
, user
);
1472 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
1474 out
= read_tuple_space(s
, v
, isl_space_copy(space
),
1475 rational
, comma
, read_el
, user
);
1476 res
= isl_space_product(res
, out
);
1478 res
= read_tuple_list(s
, v
, isl_space_copy(space
),
1479 rational
, comma
, read_el
, user
);
1480 if (!res
|| isl_stream_eat(s
, ']'))
1484 res
= isl_space_set_tuple_name(res
, isl_dim_set
, name
);
1488 isl_space_free(space
);
1492 isl_space_free(res
);
1493 isl_space_free(space
);
1497 /* Construct an isl_pw_aff defined on a space with v->n variables
1498 * that is equal to the last of those variables.
1500 static __isl_give isl_pw_aff
*identity_tuple_el(struct vars
*v
)
1504 space
= isl_space_set_alloc(v
->ctx
, 0, v
->n
);
1505 return identity_tuple_el_on_space(space
, v
);
1508 /* This function is called for each element in a tuple inside read_tuple.
1509 * Add a new variable to "v" and construct a corresponding isl_pw_aff defined
1510 * over a space containing all variables in "v" defined so far.
1511 * The isl_pw_aff expresses the new variable in terms of earlier variables
1512 * if a definition is provided. Otherwise, it is represented as being
1514 * Add the isl_pw_aff to *list.
1515 * If the new variable was named, then adjust "space" accordingly and
1516 * return the updated space.
1518 static __isl_give isl_space
*read_tuple_pw_aff_el(__isl_keep isl_stream
*s
,
1519 struct vars
*v
, __isl_take isl_space
*space
, int rational
, void *user
)
1521 isl_pw_aff_list
**list
= (isl_pw_aff_list
**) user
;
1523 struct isl_token
*tok
;
1526 tok
= next_token(s
);
1528 isl_stream_error(s
, NULL
, "unexpected EOF");
1529 return isl_space_free(space
);
1532 if (tok
->type
== ISL_TOKEN_IDENT
) {
1534 int p
= vars_pos(v
, tok
->u
.s
, -1);
1540 if (tok
->type
== '*') {
1541 if (vars_add_anon(v
) < 0)
1543 isl_token_free(tok
);
1544 pa
= identity_tuple_el(v
);
1545 } else if (new_name
) {
1546 space
= space_set_last_dim_name(space
, v
->v
->name
);
1547 isl_token_free(tok
);
1548 if (isl_stream_eat_if_available(s
, '='))
1549 pa
= read_tuple_var_def(s
, v
, rational
);
1551 pa
= identity_tuple_el(v
);
1553 isl_stream_push_token(s
, tok
);
1555 if (vars_add_anon(v
) < 0)
1557 pa
= read_tuple_var_def(s
, v
, rational
);
1560 *list
= isl_pw_aff_list_add(*list
, pa
);
1562 return isl_space_free(space
);
1566 isl_token_free(tok
);
1567 return isl_space_free(space
);
1570 /* Read a tuple and represent it as an isl_multi_pw_aff.
1571 * The range space of the isl_multi_pw_aff is the space of the tuple.
1572 * The domain space is an anonymous space
1573 * with a dimension for each variable in the set of variables in "v",
1574 * including the variables in the range.
1575 * If a given dimension is not defined in terms of earlier dimensions in
1576 * the input, then the corresponding isl_pw_aff is set equal to one time
1577 * the variable corresponding to the dimension being defined.
1579 * The elements in the tuple are collected in a list by read_tuple_pw_aff_el.
1580 * Each element in this list is defined over a space representing
1581 * the variables defined so far. We need to adjust the earlier
1582 * elements to have as many variables in the domain as the final
1583 * element in the list.
1585 static __isl_give isl_multi_pw_aff
*read_tuple(__isl_keep isl_stream
*s
,
1586 struct vars
*v
, int rational
, int comma
)
1591 isl_pw_aff_list
*list
;
1593 space
= isl_space_params_alloc(v
->ctx
, 0);
1594 list
= isl_pw_aff_list_alloc(s
->ctx
, 0);
1595 space
= read_tuple_space(s
, v
, space
, rational
, comma
,
1596 &read_tuple_pw_aff_el
, &list
);
1597 n
= isl_space_dim(space
, isl_dim_set
);
1599 space
= isl_space_free(space
);
1600 for (i
= 0; i
+ 1 < n
; ++i
) {
1603 pa
= isl_pw_aff_list_get_pw_aff(list
, i
);
1604 pa
= isl_pw_aff_add_dims(pa
, isl_dim_in
, n
- (i
+ 1));
1605 list
= isl_pw_aff_list_set_pw_aff(list
, i
, pa
);
1608 space
= isl_space_from_range(space
);
1609 space
= isl_space_add_dims(space
, isl_dim_in
, v
->n
);
1610 return isl_multi_pw_aff_from_pw_aff_list(space
, list
);
1613 /* Add the tuple represented by the isl_multi_pw_aff "tuple" to "map".
1614 * We first create the appropriate space in "map" based on the range
1615 * space of this isl_multi_pw_aff. Then, we add equalities based
1616 * on the affine expressions. These live in an anonymous space,
1617 * however, so we first need to reset the space to that of "map".
1619 static __isl_give isl_map
*map_from_tuple(__isl_take isl_multi_pw_aff
*tuple
,
1620 __isl_take isl_map
*map
, enum isl_dim_type type
, struct vars
*v
,
1626 isl_space
*space
= NULL
;
1628 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
1631 ctx
= isl_multi_pw_aff_get_ctx(tuple
);
1632 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
1636 if (type
== isl_dim_param
) {
1637 if (isl_space_has_tuple_name(space
, isl_dim_set
) ||
1638 isl_space_is_wrapping(space
)) {
1639 isl_die(ctx
, isl_error_invalid
,
1640 "parameter tuples cannot be named or nested",
1643 map
= isl_map_add_dims(map
, type
, n
);
1644 for (i
= 0; i
< n
; ++i
) {
1646 if (!isl_space_has_dim_name(space
, isl_dim_set
, i
))
1647 isl_die(ctx
, isl_error_invalid
,
1648 "parameters must be named",
1650 id
= isl_space_get_dim_id(space
, isl_dim_set
, i
);
1651 map
= isl_map_set_dim_id(map
, isl_dim_param
, i
, id
);
1653 } else if (type
== isl_dim_in
) {
1656 set
= isl_set_universe(isl_space_copy(space
));
1658 set
= isl_set_set_rational(set
);
1659 set
= isl_set_intersect_params(set
, isl_map_params(map
));
1660 map
= isl_map_from_domain(set
);
1664 set
= isl_set_universe(isl_space_copy(space
));
1666 set
= isl_set_set_rational(set
);
1667 map
= isl_map_from_domain_and_range(isl_map_domain(map
), set
);
1670 for (i
= 0; i
< n
; ++i
) {
1677 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
1678 space
= isl_pw_aff_get_domain_space(pa
);
1679 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
1680 aff
= isl_aff_add_coefficient_si(aff
,
1681 isl_dim_in
, v
->n
- n
+ i
, -1);
1682 pa
= isl_pw_aff_add(pa
, isl_pw_aff_from_aff(aff
));
1684 pa
= isl_pw_aff_set_rational(pa
);
1685 set
= isl_pw_aff_zero_set(pa
);
1686 map_i
= isl_map_from_range(set
);
1687 map_i
= isl_map_reset_space(map_i
, isl_map_get_space(map
));
1688 map
= isl_map_intersect(map
, map_i
);
1691 isl_space_free(space
);
1692 isl_multi_pw_aff_free(tuple
);
1695 isl_space_free(space
);
1696 isl_multi_pw_aff_free(tuple
);
1701 /* Read a tuple from "s" and add it to "map".
1702 * The tuple is initially represented as an isl_multi_pw_aff and
1703 * then added to "map".
1705 static __isl_give isl_map
*read_map_tuple(__isl_keep isl_stream
*s
,
1706 __isl_take isl_map
*map
, enum isl_dim_type type
, struct vars
*v
,
1707 int rational
, int comma
)
1709 isl_multi_pw_aff
*tuple
;
1711 tuple
= read_tuple(s
, v
, rational
, comma
);
1713 return isl_map_free(map
);
1715 return map_from_tuple(tuple
, map
, type
, v
, rational
);
1718 /* Read the parameter domain of an expression from "s" (if any) and
1719 * check that it does not involve any constraints.
1720 * "v" contains a description of the identifiers parsed so far
1721 * (of which there should not be any at this point) and is extended
1724 static __isl_give isl_set
*read_universe_params(__isl_keep isl_stream
*s
,
1729 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
1730 if (next_is_tuple(s
)) {
1731 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
1732 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
1733 return isl_set_free(dom
);
1735 if (!isl_set_plain_is_universe(dom
))
1736 isl_die(s
->ctx
, isl_error_invalid
,
1737 "expecting universe parameter domain",
1738 return isl_set_free(dom
));
1743 /* Read the parameter domain of an expression from "s" (if any),
1744 * check that it does not involve any constraints and return its space.
1745 * "v" contains a description of the identifiers parsed so far
1746 * (of which there should not be any at this point) and is extended
1749 static __isl_give isl_space
*read_params(__isl_keep isl_stream
*s
,
1755 set
= read_universe_params(s
, v
);
1756 space
= isl_set_get_space(set
);
1762 /* This function is called for each element in a tuple inside read_space_tuples.
1763 * Add a new variable to "v" and adjust "space" accordingly
1764 * if the variable has a name.
1766 static __isl_give isl_space
*read_tuple_id(__isl_keep isl_stream
*s
,
1767 struct vars
*v
, __isl_take isl_space
*space
, int rational
, void *user
)
1769 struct isl_token
*tok
;
1771 tok
= next_token(s
);
1773 isl_stream_error(s
, NULL
, "unexpected EOF");
1774 return isl_space_free(space
);
1777 if (tok
->type
== ISL_TOKEN_IDENT
) {
1779 int p
= vars_pos(v
, tok
->u
.s
, -1);
1783 isl_stream_error(s
, tok
, "expecting fresh identifier");
1786 space
= space_set_last_dim_name(space
, v
->v
->name
);
1787 } else if (tok
->type
== '*') {
1788 if (vars_add_anon(v
) < 0)
1791 isl_stream_error(s
, tok
, "expecting identifier or '*'");
1795 isl_token_free(tok
);
1798 isl_token_free(tok
);
1799 return isl_space_free(space
);
1802 /* Given a parameter space "params", extend it with one or two tuples
1804 * "v" contains a description of the identifiers parsed so far and is extended
1807 static __isl_give isl_space
*read_space_tuples(__isl_keep isl_stream
*s
,
1808 struct vars
*v
, __isl_take isl_space
*params
)
1810 isl_space
*space
, *ran
;
1812 space
= read_tuple_space(s
, v
, isl_space_copy(params
), 1, 1,
1813 &read_tuple_id
, NULL
);
1814 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TO
)) {
1815 ran
= read_tuple_space(s
, v
, isl_space_copy(params
), 1, 1,
1816 &read_tuple_id
, NULL
);
1817 space
= isl_space_unwrap(isl_space_product(space
, ran
));
1819 isl_space_free(params
);
1824 /* Read an isl_space object from "s".
1826 * First read the parameters (if any).
1828 * Then check if the description is of the special form "{ : }",
1829 * in which case it represents a parameter space.
1830 * Otherwise, it has one or two tuples.
1832 __isl_give isl_space
*isl_stream_read_space(__isl_keep isl_stream
*s
)
1837 v
= vars_new(s
->ctx
);
1840 space
= read_params(s
, v
);
1842 if (isl_stream_eat(s
, '{'))
1845 if (!isl_stream_eat_if_available(s
, ':'))
1846 space
= read_space_tuples(s
, v
, space
);
1848 if (isl_stream_eat(s
, '}'))
1855 isl_space_free(space
);
1860 #define TYPE_BASE space
1861 #include "isl_read_from_str_templ.c"
1863 /* Given two equal-length lists of piecewise affine expression with the space
1864 * of "set" as domain, construct a set in the same space that expresses
1865 * that "left" and "right" satisfy the comparison "type".
1867 * A space is constructed of the same dimension as the number of elements
1868 * in the two lists. The comparison is then expressed in a map from
1869 * this space to itself and wrapped into a set. Finally the two lists
1870 * of piecewise affine expressions are plugged into this set.
1872 * Let S be the space of "set" and T the constructed space.
1873 * The lists are first changed into two isl_multi_pw_affs in S -> T and
1874 * then combined into an isl_multi_pw_aff in S -> [T -> T],
1875 * while the comparison is first expressed in T -> T, then [T -> T]
1878 static __isl_give isl_set
*list_cmp(__isl_keep isl_set
*set
, int type
,
1879 __isl_take isl_pw_aff_list
*left
, __isl_take isl_pw_aff_list
*right
)
1883 isl_multi_pw_aff
*mpa1
, *mpa2
;
1885 n
= isl_pw_aff_list_n_pw_aff(left
);
1886 if (!set
|| n
< 0 || !right
)
1889 space
= isl_set_get_space(set
);
1890 space
= isl_space_from_domain(space
);
1891 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
1892 mpa1
= isl_multi_pw_aff_from_pw_aff_list(isl_space_copy(space
), left
);
1893 mpa2
= isl_multi_pw_aff_from_pw_aff_list(isl_space_copy(space
), right
);
1894 mpa1
= isl_multi_pw_aff_range_product(mpa1
, mpa2
);
1896 space
= isl_space_range(space
);
1898 case ISL_TOKEN_LEX_LT
:
1899 set
= isl_map_wrap(isl_map_lex_lt(space
));
1901 case ISL_TOKEN_LEX_GT
:
1902 set
= isl_map_wrap(isl_map_lex_gt(space
));
1904 case ISL_TOKEN_LEX_LE
:
1905 set
= isl_map_wrap(isl_map_lex_le(space
));
1907 case ISL_TOKEN_LEX_GE
:
1908 set
= isl_map_wrap(isl_map_lex_ge(space
));
1911 isl_multi_pw_aff_free(mpa1
);
1912 isl_space_free(space
);
1913 isl_die(isl_set_get_ctx(set
), isl_error_internal
,
1914 "unhandled list comparison type", return NULL
);
1916 set
= isl_set_preimage_multi_pw_aff(set
, mpa1
);
1919 isl_pw_aff_list_free(left
);
1920 isl_pw_aff_list_free(right
);
1924 /* Construct constraints of the form
1928 * where a is an element in "left", op is an operator of type "type" and
1929 * b is an element in "right", add the constraints to "set" and return
1931 * "rational" is set if the constraints should be treated as
1932 * a rational constraints.
1934 * If "type" is the type of a comparison operator between lists
1935 * of affine expressions, then a single (compound) constraint
1936 * is constructed by list_cmp instead.
1938 static __isl_give isl_set
*construct_constraints(
1939 __isl_take isl_set
*set
, int type
,
1940 __isl_keep isl_pw_aff_list
*left
, __isl_keep isl_pw_aff_list
*right
,
1945 left
= isl_pw_aff_list_copy(left
);
1946 right
= isl_pw_aff_list_copy(right
);
1948 left
= isl_pw_aff_list_set_rational(left
);
1949 right
= isl_pw_aff_list_set_rational(right
);
1951 if (is_list_comparator_type(type
))
1952 cond
= list_cmp(set
, type
, left
, right
);
1953 else if (type
== ISL_TOKEN_LE
)
1954 cond
= isl_pw_aff_list_le_set(left
, right
);
1955 else if (type
== ISL_TOKEN_GE
)
1956 cond
= isl_pw_aff_list_ge_set(left
, right
);
1957 else if (type
== ISL_TOKEN_LT
)
1958 cond
= isl_pw_aff_list_lt_set(left
, right
);
1959 else if (type
== ISL_TOKEN_GT
)
1960 cond
= isl_pw_aff_list_gt_set(left
, right
);
1961 else if (type
== ISL_TOKEN_NE
)
1962 cond
= isl_pw_aff_list_ne_set(left
, right
);
1964 cond
= isl_pw_aff_list_eq_set(left
, right
);
1966 return isl_set_intersect(set
, cond
);
1969 /* Read a constraint from "s", add it to "map" and return the result.
1970 * "v" contains a description of the identifiers parsed so far.
1971 * "rational" is set if the constraint should be treated as
1972 * a rational constraint.
1973 * The constraint read from "s" may be applied to multiple pairs
1974 * of affine expressions and may be chained.
1975 * In particular, a list of affine expressions is read, followed
1976 * by a comparison operator and another list of affine expressions.
1977 * The comparison operator is then applied to each pair of elements
1978 * in the two lists and the results are added to "map".
1979 * However, if the operator expects two lists of affine expressions,
1980 * then it is applied directly to those lists and the two lists
1981 * are required to have the same length.
1982 * If the next token is another comparison operator, then another
1983 * list of affine expressions is read and the process repeats.
1985 * The processing is performed on a wrapped copy of "map" because
1986 * an affine expression cannot have a binary relation as domain.
1988 static __isl_give isl_map
*add_constraint(__isl_keep isl_stream
*s
,
1989 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
1991 struct isl_token
*tok
;
1993 isl_pw_aff_list
*list1
= NULL
, *list2
= NULL
;
1997 set
= isl_map_wrap(map
);
1998 list1
= accept_affine_list(s
, isl_set_get_space(set
), v
);
2001 tok
= isl_stream_next_token(s
);
2002 if (!is_comparator(tok
)) {
2003 isl_stream_error(s
, tok
, "missing operator");
2005 isl_stream_push_token(s
, tok
);
2009 isl_token_free(tok
);
2011 list2
= accept_affine_list(s
, isl_set_get_space(set
), v
);
2012 n1
= isl_pw_aff_list_n_pw_aff(list1
);
2013 n2
= isl_pw_aff_list_n_pw_aff(list2
);
2014 if (n1
< 0 || n2
< 0)
2016 if (is_list_comparator_type(type
) && n1
!= n2
) {
2017 isl_stream_error(s
, NULL
,
2018 "list arguments not of same size");
2022 set
= construct_constraints(set
, type
, list1
, list2
, rational
);
2023 isl_pw_aff_list_free(list1
);
2026 if (!next_is_comparator(s
))
2028 tok
= isl_stream_next_token(s
);
2030 isl_token_free(tok
);
2032 isl_pw_aff_list_free(list1
);
2034 return isl_set_unwrap(set
);
2036 isl_pw_aff_list_free(list1
);
2037 isl_pw_aff_list_free(list2
);
2042 static __isl_give isl_map
*read_exists(__isl_keep isl_stream
*s
,
2043 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2046 int seen_paren
= isl_stream_eat_if_available(s
, '(');
2048 map
= isl_map_from_domain(isl_map_wrap(map
));
2049 map
= read_defined_var_list(s
, v
, map
, rational
);
2051 if (isl_stream_eat(s
, ':'))
2054 map
= read_formula(s
, v
, map
, rational
);
2055 map
= isl_set_unwrap(isl_map_domain(map
));
2057 vars_drop(v
, v
->n
- n
);
2058 if (seen_paren
&& isl_stream_eat(s
, ')'))
2067 /* Parse an expression between parentheses and push the result
2068 * back on the stream.
2070 * The parsed expression may be either an affine expression
2071 * or a condition. The first type is pushed onto the stream
2072 * as an isl_pw_aff, while the second is pushed as an isl_map.
2074 * If the initial token indicates the start of a condition,
2075 * we parse it as such.
2076 * Otherwise, we first parse an affine expression and push
2077 * that onto the stream. If the affine expression covers the
2078 * entire expression between parentheses, we return.
2079 * Otherwise, we assume that the affine expression is the
2080 * start of a condition and continue parsing.
2082 static int resolve_paren_expr(__isl_keep isl_stream
*s
,
2083 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2085 struct isl_token
*tok
, *tok2
;
2090 tok
= isl_stream_next_token(s
);
2091 if (!tok
|| tok
->type
!= '(')
2094 if (isl_stream_next_token_is(s
, '('))
2095 if (resolve_paren_expr(s
, v
, isl_map_copy(map
), rational
))
2098 if (next_is_condition_start(s
)) {
2099 map
= read_formula(s
, v
, map
, rational
);
2100 if (isl_stream_eat(s
, ')'))
2102 tok
->type
= ISL_TOKEN_MAP
;
2104 isl_stream_push_token(s
, tok
);
2108 tok2
= isl_stream_next_token(s
);
2113 isl_stream_push_token(s
, tok2
);
2115 pwaff
= accept_affine(s
, isl_space_wrap(isl_map_get_space(map
)), v
);
2119 has_paren
= isl_stream_eat_if_available(s
, ')');
2121 if (push_aff(s
, line
, col
, pwaff
) < 0)
2125 isl_token_free(tok
);
2130 map
= read_formula(s
, v
, map
, rational
);
2131 if (isl_stream_eat(s
, ')'))
2134 tok
->type
= ISL_TOKEN_MAP
;
2136 isl_stream_push_token(s
, tok
);
2140 isl_token_free(tok
);
2145 static __isl_give isl_map
*read_conjunct(__isl_keep isl_stream
*s
,
2146 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2148 if (isl_stream_next_token_is(s
, '('))
2149 if (resolve_paren_expr(s
, v
, isl_map_copy(map
), rational
))
2152 if (isl_stream_next_token_is(s
, ISL_TOKEN_MAP
)) {
2153 struct isl_token
*tok
;
2154 tok
= isl_stream_next_token(s
);
2158 map
= isl_map_copy(tok
->u
.map
);
2159 isl_token_free(tok
);
2163 if (isl_stream_eat_if_available(s
, ISL_TOKEN_EXISTS
))
2164 return read_exists(s
, v
, map
, rational
);
2166 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TRUE
))
2169 if (isl_stream_eat_if_available(s
, ISL_TOKEN_FALSE
)) {
2170 isl_space
*space
= isl_map_get_space(map
);
2172 return isl_map_empty(space
);
2175 return add_constraint(s
, v
, map
, rational
);
2181 static __isl_give isl_map
*read_conjuncts(__isl_keep isl_stream
*s
,
2182 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2187 negate
= isl_stream_eat_if_available(s
, ISL_TOKEN_NOT
);
2188 res
= read_conjunct(s
, v
, isl_map_copy(map
), rational
);
2190 res
= isl_map_subtract(isl_map_copy(map
), res
);
2192 while (res
&& isl_stream_eat_if_available(s
, ISL_TOKEN_AND
)) {
2195 negate
= isl_stream_eat_if_available(s
, ISL_TOKEN_NOT
);
2196 res_i
= read_conjunct(s
, v
, isl_map_copy(map
), rational
);
2198 res
= isl_map_subtract(res
, res_i
);
2200 res
= isl_map_intersect(res
, res_i
);
2207 static __isl_give isl_map
*read_disjuncts(__isl_keep isl_stream
*s
,
2208 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2212 if (isl_stream_next_token_is(s
, '}'))
2215 res
= read_conjuncts(s
, v
, isl_map_copy(map
), rational
);
2216 while (isl_stream_eat_if_available(s
, ISL_TOKEN_OR
)) {
2219 res_i
= read_conjuncts(s
, v
, isl_map_copy(map
), rational
);
2220 res
= isl_map_union(res
, res_i
);
2227 /* Read a first order formula from "s", add the corresponding
2228 * constraints to "map" and return the result.
2230 * In particular, read a formula of the form
2238 * where a and b are disjunctions.
2240 * In the first case, map is replaced by
2242 * map \cap { [..] : a }
2244 * In the second case, it is replaced by
2246 * (map \setminus { [..] : a}) \cup (map \cap { [..] : b })
2248 static __isl_give isl_map
*read_formula(__isl_keep isl_stream
*s
,
2249 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2253 res
= read_disjuncts(s
, v
, isl_map_copy(map
), rational
);
2255 if (isl_stream_eat_if_available(s
, ISL_TOKEN_IMPLIES
)) {
2258 res
= isl_map_subtract(isl_map_copy(map
), res
);
2259 res2
= read_disjuncts(s
, v
, map
, rational
);
2260 res
= isl_map_union(res
, res2
);
2267 static isl_size
polylib_pos_to_isl_pos(__isl_keep isl_basic_map
*bmap
, int pos
)
2269 isl_size n_out
, n_in
, n_param
, n_div
;
2271 n_param
= isl_basic_map_dim(bmap
, isl_dim_param
);
2272 n_in
= isl_basic_map_dim(bmap
, isl_dim_in
);
2273 n_out
= isl_basic_map_dim(bmap
, isl_dim_out
);
2274 n_div
= isl_basic_map_dim(bmap
, isl_dim_div
);
2275 if (n_param
< 0 || n_in
< 0 || n_out
< 0 || n_div
< 0)
2276 return isl_size_error
;
2279 return 1 + n_param
+ n_in
+ pos
;
2283 return 1 + n_param
+ pos
;
2287 return 1 + n_param
+ n_in
+ n_out
+ pos
;
2296 static __isl_give isl_basic_map
*basic_map_read_polylib_constraint(
2297 __isl_keep isl_stream
*s
, __isl_take isl_basic_map
*bmap
)
2300 struct isl_token
*tok
;
2309 tok
= isl_stream_next_token(s
);
2310 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2311 isl_stream_error(s
, tok
, "expecting coefficient");
2312 isl_token_free(tok
);
2315 if (!tok
->on_new_line
) {
2316 isl_stream_error(s
, tok
, "coefficient should appear on new line");
2317 isl_token_free(tok
);
2321 type
= isl_int_get_si(tok
->u
.v
);
2322 isl_token_free(tok
);
2324 isl_assert(s
->ctx
, type
== 0 || type
== 1, goto error
);
2326 k
= isl_basic_map_alloc_equality(bmap
);
2329 k
= isl_basic_map_alloc_inequality(bmap
);
2335 total
= isl_basic_map_dim(bmap
, isl_dim_all
);
2337 return isl_basic_map_free(bmap
);
2338 for (j
= 0; j
< 1 + total
; ++j
) {
2340 tok
= next_signed_value_on_same_line(s
,
2341 "expecting coefficient on same line");
2344 pos
= polylib_pos_to_isl_pos(bmap
, j
);
2346 isl_int_set(c
[pos
], tok
->u
.v
);
2347 isl_token_free(tok
);
2349 return isl_basic_map_free(bmap
);
2354 isl_basic_map_free(bmap
);
2358 static __isl_give isl_basic_map
*basic_map_read_polylib(
2359 __isl_keep isl_stream
*s
)
2362 struct isl_token
*tok
;
2363 struct isl_token
*tok2
;
2366 unsigned in
= 0, out
, local
= 0;
2367 struct isl_basic_map
*bmap
= NULL
;
2370 tok
= isl_stream_next_token(s
);
2372 isl_stream_error(s
, NULL
, "unexpected EOF");
2375 tok2
= isl_stream_next_token(s
);
2377 isl_token_free(tok
);
2378 isl_stream_error(s
, NULL
, "unexpected EOF");
2381 if (tok
->type
!= ISL_TOKEN_VALUE
|| tok2
->type
!= ISL_TOKEN_VALUE
) {
2382 isl_token_free(tok2
);
2383 isl_token_free(tok
);
2384 isl_stream_error(s
, NULL
,
2385 "expecting constraint matrix dimensions");
2388 n_row
= isl_int_get_si(tok
->u
.v
);
2389 n_col
= isl_int_get_si(tok2
->u
.v
);
2390 on_new_line
= tok2
->on_new_line
;
2391 isl_token_free(tok2
);
2392 isl_token_free(tok
);
2393 isl_assert(s
->ctx
, !on_new_line
, return NULL
);
2394 isl_assert(s
->ctx
, n_row
>= 0, return NULL
);
2395 isl_assert(s
->ctx
, n_col
>= 2 + nparam
, return NULL
);
2396 tok
= isl_stream_next_token_on_same_line(s
);
2398 if (tok
->type
!= ISL_TOKEN_VALUE
) {
2399 isl_stream_error(s
, tok
,
2400 "expecting number of output dimensions");
2401 isl_token_free(tok
);
2404 out
= isl_int_get_si(tok
->u
.v
);
2405 isl_token_free(tok
);
2407 tok
= isl_stream_next_token_on_same_line(s
);
2408 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2409 isl_stream_error(s
, tok
,
2410 "expecting number of input dimensions");
2411 isl_token_free(tok
);
2414 in
= isl_int_get_si(tok
->u
.v
);
2415 isl_token_free(tok
);
2417 tok
= isl_stream_next_token_on_same_line(s
);
2418 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2419 isl_stream_error(s
, tok
,
2420 "expecting number of existentials");
2421 isl_token_free(tok
);
2424 local
= isl_int_get_si(tok
->u
.v
);
2425 isl_token_free(tok
);
2427 tok
= isl_stream_next_token_on_same_line(s
);
2428 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2429 isl_stream_error(s
, tok
,
2430 "expecting number of parameters");
2431 isl_token_free(tok
);
2434 nparam
= isl_int_get_si(tok
->u
.v
);
2435 isl_token_free(tok
);
2436 if (n_col
!= 1 + out
+ in
+ local
+ nparam
+ 1) {
2437 isl_stream_error(s
, NULL
,
2438 "dimensions don't match");
2442 out
= n_col
- 2 - nparam
;
2443 bmap
= isl_basic_map_alloc(s
->ctx
, nparam
, in
, out
, local
, n_row
, n_row
);
2447 for (i
= 0; i
< local
; ++i
) {
2448 int k
= isl_basic_map_alloc_div(bmap
);
2451 isl_seq_clr(bmap
->div
[k
], 1 + 1 + nparam
+ in
+ out
+ local
);
2454 for (i
= 0; i
< n_row
; ++i
)
2455 bmap
= basic_map_read_polylib_constraint(s
, bmap
);
2460 tok
= isl_stream_next_token_on_same_line(s
);
2462 isl_stream_error(s
, tok
, "unexpected extra token on line");
2463 isl_token_free(tok
);
2467 bmap
= isl_basic_map_simplify(bmap
);
2468 bmap
= isl_basic_map_finalize(bmap
);
2471 isl_basic_map_free(bmap
);
2475 static __isl_give isl_map
*map_read_polylib(__isl_keep isl_stream
*s
)
2477 struct isl_token
*tok
;
2478 struct isl_token
*tok2
;
2480 struct isl_map
*map
;
2482 tok
= isl_stream_next_token(s
);
2484 isl_stream_error(s
, NULL
, "unexpected EOF");
2487 tok2
= isl_stream_next_token_on_same_line(s
);
2488 if (tok2
&& tok2
->type
== ISL_TOKEN_VALUE
) {
2489 isl_stream_push_token(s
, tok2
);
2490 isl_stream_push_token(s
, tok
);
2491 return isl_map_from_basic_map(basic_map_read_polylib(s
));
2494 isl_stream_error(s
, tok2
, "unexpected token");
2495 isl_stream_push_token(s
, tok2
);
2496 isl_stream_push_token(s
, tok
);
2499 n
= isl_int_get_si(tok
->u
.v
);
2500 isl_token_free(tok
);
2502 isl_assert(s
->ctx
, n
>= 1, return NULL
);
2504 map
= isl_map_from_basic_map(basic_map_read_polylib(s
));
2506 for (i
= 1; map
&& i
< n
; ++i
)
2507 map
= isl_map_union(map
,
2508 isl_map_from_basic_map(basic_map_read_polylib(s
)));
2513 static int optional_power(__isl_keep isl_stream
*s
)
2516 struct isl_token
*tok
;
2518 tok
= isl_stream_next_token(s
);
2521 if (tok
->type
!= '^') {
2522 isl_stream_push_token(s
, tok
);
2525 isl_token_free(tok
);
2526 tok
= isl_stream_next_token(s
);
2527 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2528 isl_stream_error(s
, tok
, "expecting exponent");
2530 isl_stream_push_token(s
, tok
);
2533 pow
= isl_int_get_si(tok
->u
.v
);
2534 isl_token_free(tok
);
2538 static __isl_give isl_pw_qpolynomial
*read_term(__isl_keep isl_stream
*s
,
2539 __isl_keep isl_map
*map
, struct vars
*v
);
2541 static __isl_give isl_pw_qpolynomial
*read_factor(__isl_keep isl_stream
*s
,
2542 __isl_keep isl_map
*map
, struct vars
*v
)
2544 isl_pw_qpolynomial
*pwqp
;
2545 struct isl_token
*tok
;
2547 tok
= next_token(s
);
2549 isl_stream_error(s
, NULL
, "unexpected EOF");
2552 if (tok
->type
== '(') {
2555 isl_token_free(tok
);
2556 pwqp
= read_term(s
, map
, v
);
2559 if (isl_stream_eat(s
, ')'))
2561 pow
= optional_power(s
);
2562 pwqp
= isl_pw_qpolynomial_pow(pwqp
, pow
);
2563 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
2564 struct isl_token
*tok2
;
2565 isl_qpolynomial
*qp
;
2567 tok2
= isl_stream_next_token(s
);
2568 if (tok2
&& tok2
->type
== '/') {
2569 isl_token_free(tok2
);
2570 tok2
= next_token(s
);
2571 if (!tok2
|| tok2
->type
!= ISL_TOKEN_VALUE
) {
2572 isl_stream_error(s
, tok2
, "expected denominator");
2573 isl_token_free(tok
);
2574 isl_token_free(tok2
);
2577 qp
= isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map
),
2578 tok
->u
.v
, tok2
->u
.v
);
2579 isl_token_free(tok2
);
2581 isl_stream_push_token(s
, tok2
);
2582 qp
= isl_qpolynomial_cst_on_domain(isl_map_get_space(map
),
2585 isl_token_free(tok
);
2586 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2587 } else if (tok
->type
== ISL_TOKEN_INFTY
) {
2588 isl_qpolynomial
*qp
;
2589 isl_token_free(tok
);
2590 qp
= isl_qpolynomial_infty_on_domain(isl_map_get_space(map
));
2591 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2592 } else if (tok
->type
== ISL_TOKEN_NAN
) {
2593 isl_qpolynomial
*qp
;
2594 isl_token_free(tok
);
2595 qp
= isl_qpolynomial_nan_on_domain(isl_map_get_space(map
));
2596 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2597 } else if (tok
->type
== ISL_TOKEN_IDENT
) {
2599 int pos
= vars_pos(v
, tok
->u
.s
, -1);
2601 isl_qpolynomial
*qp
;
2603 isl_token_free(tok
);
2607 vars_drop(v
, v
->n
- n
);
2608 isl_stream_error(s
, tok
, "unknown identifier");
2609 isl_token_free(tok
);
2612 isl_token_free(tok
);
2613 pow
= optional_power(s
);
2614 qp
= isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map
), pos
, pow
);
2615 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2616 } else if (is_start_of_div(tok
)) {
2620 isl_stream_push_token(s
, tok
);
2621 pwaff
= accept_div(s
, isl_map_get_space(map
), v
);
2622 pow
= optional_power(s
);
2623 pwqp
= isl_pw_qpolynomial_from_pw_aff(pwaff
);
2624 pwqp
= isl_pw_qpolynomial_pow(pwqp
, pow
);
2625 } else if (tok
->type
== '-') {
2626 isl_token_free(tok
);
2627 pwqp
= read_factor(s
, map
, v
);
2628 pwqp
= isl_pw_qpolynomial_neg(pwqp
);
2630 isl_stream_error(s
, tok
, "unexpected isl_token");
2631 isl_stream_push_token(s
, tok
);
2635 if (isl_stream_eat_if_available(s
, '*') ||
2636 isl_stream_next_token_is(s
, ISL_TOKEN_IDENT
)) {
2637 isl_pw_qpolynomial
*pwqp2
;
2639 pwqp2
= read_factor(s
, map
, v
);
2640 pwqp
= isl_pw_qpolynomial_mul(pwqp
, pwqp2
);
2645 isl_pw_qpolynomial_free(pwqp
);
2649 static __isl_give isl_pw_qpolynomial
*read_term(__isl_keep isl_stream
*s
,
2650 __isl_keep isl_map
*map
, struct vars
*v
)
2652 struct isl_token
*tok
;
2653 isl_pw_qpolynomial
*pwqp
;
2655 pwqp
= read_factor(s
, map
, v
);
2658 tok
= next_token(s
);
2662 if (tok
->type
== '+') {
2663 isl_pw_qpolynomial
*pwqp2
;
2665 isl_token_free(tok
);
2666 pwqp2
= read_factor(s
, map
, v
);
2667 pwqp
= isl_pw_qpolynomial_add(pwqp
, pwqp2
);
2668 } else if (tok
->type
== '-') {
2669 isl_pw_qpolynomial
*pwqp2
;
2671 isl_token_free(tok
);
2672 pwqp2
= read_factor(s
, map
, v
);
2673 pwqp
= isl_pw_qpolynomial_sub(pwqp
, pwqp2
);
2675 isl_stream_push_token(s
, tok
);
2683 static __isl_give isl_map
*read_optional_formula(__isl_keep isl_stream
*s
,
2684 __isl_take isl_map
*map
, struct vars
*v
, int rational
)
2686 struct isl_token
*tok
;
2688 tok
= isl_stream_next_token(s
);
2690 isl_stream_error(s
, NULL
, "unexpected EOF");
2693 if (tok
->type
== ':' ||
2694 (tok
->type
== ISL_TOKEN_OR
&& !strcmp(tok
->u
.s
, "|"))) {
2695 isl_token_free(tok
);
2696 map
= read_formula(s
, v
, map
, rational
);
2698 isl_stream_push_token(s
, tok
);
2706 static struct isl_obj
obj_read_poly(__isl_keep isl_stream
*s
,
2707 __isl_take isl_map
*map
, struct vars
*v
, int n
)
2709 struct isl_obj obj
= { isl_obj_pw_qpolynomial
, NULL
};
2710 isl_pw_qpolynomial
*pwqp
;
2711 struct isl_set
*set
;
2713 pwqp
= read_term(s
, map
, v
);
2714 map
= read_optional_formula(s
, map
, v
, 0);
2715 set
= isl_map_range(map
);
2717 pwqp
= isl_pw_qpolynomial_intersect_domain(pwqp
, set
);
2719 vars_drop(v
, v
->n
- n
);
2725 static struct isl_obj
obj_read_poly_or_fold(__isl_keep isl_stream
*s
,
2726 __isl_take isl_set
*set
, struct vars
*v
, int n
)
2729 struct isl_obj obj
= { isl_obj_pw_qpolynomial_fold
, NULL
};
2730 isl_pw_qpolynomial
*pwqp
;
2731 isl_pw_qpolynomial_fold
*pwf
= NULL
;
2734 max
= isl_stream_eat_if_available(s
, ISL_TOKEN_MAX
);
2735 min
= !max
&& isl_stream_eat_if_available(s
, ISL_TOKEN_MIN
);
2737 return obj_read_poly(s
, set
, v
, n
);
2738 fold
= max
? isl_fold_max
: isl_fold_min
;
2740 if (isl_stream_eat(s
, '('))
2743 pwqp
= read_term(s
, set
, v
);
2744 pwf
= isl_pw_qpolynomial_fold_from_pw_qpolynomial(fold
, pwqp
);
2746 while (isl_stream_eat_if_available(s
, ',')) {
2747 isl_pw_qpolynomial_fold
*pwf_i
;
2748 pwqp
= read_term(s
, set
, v
);
2749 pwf_i
= isl_pw_qpolynomial_fold_from_pw_qpolynomial(fold
, pwqp
);
2750 pwf
= isl_pw_qpolynomial_fold_fold(pwf
, pwf_i
);
2753 if (isl_stream_eat(s
, ')'))
2756 set
= read_optional_formula(s
, set
, v
, 0);
2757 pwf
= isl_pw_qpolynomial_fold_intersect_domain(pwf
, set
);
2759 vars_drop(v
, v
->n
- n
);
2765 isl_pw_qpolynomial_fold_free(pwf
);
2766 obj
.type
= isl_obj_none
;
2770 static int is_rational(__isl_keep isl_stream
*s
)
2772 struct isl_token
*tok
;
2774 tok
= isl_stream_next_token(s
);
2777 if (tok
->type
== ISL_TOKEN_RAT
&& isl_stream_next_token_is(s
, ':')) {
2778 isl_token_free(tok
);
2779 isl_stream_eat(s
, ':');
2783 isl_stream_push_token(s
, tok
);
2788 static struct isl_obj
obj_read_body(__isl_keep isl_stream
*s
,
2789 __isl_take isl_map
*map
, struct vars
*v
)
2791 struct isl_token
*tok
;
2792 struct isl_obj obj
= { isl_obj_set
, NULL
};
2796 rational
= is_rational(s
);
2798 map
= isl_map_set_rational(map
);
2800 if (isl_stream_next_token_is(s
, ':')) {
2801 obj
.type
= isl_obj_set
;
2802 obj
.v
= read_optional_formula(s
, map
, v
, rational
);
2806 if (!next_is_tuple(s
))
2807 return obj_read_poly_or_fold(s
, map
, v
, n
);
2809 map
= read_map_tuple(s
, map
, isl_dim_in
, v
, rational
, 0);
2812 tok
= isl_stream_next_token(s
);
2815 if (tok
->type
== ISL_TOKEN_TO
) {
2816 obj
.type
= isl_obj_map
;
2817 isl_token_free(tok
);
2818 if (!next_is_tuple(s
)) {
2819 isl_set
*set
= isl_map_domain(map
);
2820 return obj_read_poly_or_fold(s
, set
, v
, n
);
2822 map
= read_map_tuple(s
, map
, isl_dim_out
, v
, rational
, 0);
2826 map
= isl_map_domain(map
);
2827 isl_stream_push_token(s
, tok
);
2830 map
= read_optional_formula(s
, map
, v
, rational
);
2832 vars_drop(v
, v
->n
- n
);
2838 obj
.type
= isl_obj_none
;
2842 static struct isl_obj
to_union(isl_ctx
*ctx
, struct isl_obj obj
)
2844 if (obj
.type
== isl_obj_map
) {
2845 obj
.v
= isl_union_map_from_map(obj
.v
);
2846 obj
.type
= isl_obj_union_map
;
2847 } else if (obj
.type
== isl_obj_set
) {
2848 obj
.v
= isl_union_set_from_set(obj
.v
);
2849 obj
.type
= isl_obj_union_set
;
2850 } else if (obj
.type
== isl_obj_pw_qpolynomial
) {
2851 obj
.v
= isl_union_pw_qpolynomial_from_pw_qpolynomial(obj
.v
);
2852 obj
.type
= isl_obj_union_pw_qpolynomial
;
2853 } else if (obj
.type
== isl_obj_pw_qpolynomial_fold
) {
2854 obj
.v
= isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj
.v
);
2855 obj
.type
= isl_obj_union_pw_qpolynomial_fold
;
2857 isl_assert(ctx
, 0, goto error
);
2860 obj
.type
->free(obj
.v
);
2861 obj
.type
= isl_obj_none
;
2865 static struct isl_obj
obj_add(__isl_keep isl_stream
*s
,
2866 struct isl_obj obj1
, struct isl_obj obj2
)
2868 if (obj2
.type
== isl_obj_none
|| !obj2
.v
)
2870 if (obj1
.type
== isl_obj_set
&& obj2
.type
== isl_obj_union_set
)
2871 obj1
= to_union(s
->ctx
, obj1
);
2872 if (obj1
.type
== isl_obj_union_set
&& obj2
.type
== isl_obj_set
)
2873 obj2
= to_union(s
->ctx
, obj2
);
2874 if (obj1
.type
== isl_obj_map
&& obj2
.type
== isl_obj_union_map
)
2875 obj1
= to_union(s
->ctx
, obj1
);
2876 if (obj1
.type
== isl_obj_union_map
&& obj2
.type
== isl_obj_map
)
2877 obj2
= to_union(s
->ctx
, obj2
);
2878 if (obj1
.type
== isl_obj_pw_qpolynomial
&&
2879 obj2
.type
== isl_obj_union_pw_qpolynomial
)
2880 obj1
= to_union(s
->ctx
, obj1
);
2881 if (obj1
.type
== isl_obj_union_pw_qpolynomial
&&
2882 obj2
.type
== isl_obj_pw_qpolynomial
)
2883 obj2
= to_union(s
->ctx
, obj2
);
2884 if (obj1
.type
== isl_obj_pw_qpolynomial_fold
&&
2885 obj2
.type
== isl_obj_union_pw_qpolynomial_fold
)
2886 obj1
= to_union(s
->ctx
, obj1
);
2887 if (obj1
.type
== isl_obj_union_pw_qpolynomial_fold
&&
2888 obj2
.type
== isl_obj_pw_qpolynomial_fold
)
2889 obj2
= to_union(s
->ctx
, obj2
);
2890 if (obj1
.type
!= obj2
.type
) {
2891 isl_stream_error(s
, NULL
,
2892 "attempt to combine incompatible objects");
2895 if (!obj1
.type
->add
)
2896 isl_die(s
->ctx
, isl_error_internal
,
2897 "combination not supported on object type", goto error
);
2898 if (obj1
.type
== isl_obj_map
&& !isl_map_has_equal_space(obj1
.v
, obj2
.v
)) {
2899 obj1
= to_union(s
->ctx
, obj1
);
2900 obj2
= to_union(s
->ctx
, obj2
);
2902 if (obj1
.type
== isl_obj_set
&& !isl_set_has_equal_space(obj1
.v
, obj2
.v
)) {
2903 obj1
= to_union(s
->ctx
, obj1
);
2904 obj2
= to_union(s
->ctx
, obj2
);
2906 if (obj1
.type
== isl_obj_pw_qpolynomial
&&
2907 !isl_pw_qpolynomial_has_equal_space(obj1
.v
, obj2
.v
)) {
2908 obj1
= to_union(s
->ctx
, obj1
);
2909 obj2
= to_union(s
->ctx
, obj2
);
2911 if (obj1
.type
== isl_obj_pw_qpolynomial_fold
&&
2912 !isl_pw_qpolynomial_fold_has_equal_space(obj1
.v
, obj2
.v
)) {
2913 obj1
= to_union(s
->ctx
, obj1
);
2914 obj2
= to_union(s
->ctx
, obj2
);
2916 obj1
.v
= obj1
.type
->add(obj1
.v
, obj2
.v
);
2919 obj1
.type
->free(obj1
.v
);
2920 obj2
.type
->free(obj2
.v
);
2921 obj1
.type
= isl_obj_none
;
2926 /* Are the first two tokens on "s", "domain" (either as a string
2927 * or as an identifier) followed by ":"?
2929 static int next_is_domain_colon(__isl_keep isl_stream
*s
)
2931 struct isl_token
*tok
;
2935 tok
= isl_stream_next_token(s
);
2938 if (tok
->type
!= ISL_TOKEN_IDENT
&& tok
->type
!= ISL_TOKEN_STRING
) {
2939 isl_stream_push_token(s
, tok
);
2943 name
= isl_token_get_str(s
->ctx
, tok
);
2944 res
= !strcmp(name
, "domain") && isl_stream_next_token_is(s
, ':');
2947 isl_stream_push_token(s
, tok
);
2952 /* Do the first tokens on "s" look like a schedule?
2954 * The root of a schedule is always a domain node, so the first thing
2955 * we expect in the stream is a domain key, i.e., "domain" followed
2956 * by ":". If the schedule was printed in YAML flow style, then
2957 * we additionally expect a "{" to open the outer mapping.
2959 static int next_is_schedule(__isl_keep isl_stream
*s
)
2961 struct isl_token
*tok
;
2964 tok
= isl_stream_next_token(s
);
2967 if (tok
->type
!= '{') {
2968 isl_stream_push_token(s
, tok
);
2969 return next_is_domain_colon(s
);
2972 is_schedule
= next_is_domain_colon(s
);
2973 isl_stream_push_token(s
, tok
);
2978 /* Read an isl_schedule from "s" and store it in an isl_obj.
2980 static struct isl_obj
schedule_read(__isl_keep isl_stream
*s
)
2984 obj
.type
= isl_obj_schedule
;
2985 obj
.v
= isl_stream_read_schedule(s
);
2990 /* Read a disjunction of object bodies from "s".
2991 * That is, read the inside of the braces, but not the braces themselves.
2992 * "v" contains a description of the identifiers parsed so far.
2993 * "map" contains information about the parameters.
2995 static struct isl_obj
obj_read_disjuncts(__isl_keep isl_stream
*s
,
2996 struct vars
*v
, __isl_keep isl_map
*map
)
2998 struct isl_obj obj
= { isl_obj_set
, NULL
};
3000 if (isl_stream_next_token_is(s
, '}')) {
3001 obj
.type
= isl_obj_union_set
;
3002 obj
.v
= isl_union_set_empty(isl_map_get_space(map
));
3008 o
= obj_read_body(s
, isl_map_copy(map
), v
);
3012 obj
= obj_add(s
, obj
, o
);
3013 if (obj
.type
== isl_obj_none
|| !obj
.v
)
3015 if (!isl_stream_eat_if_available(s
, ';'))
3017 if (isl_stream_next_token_is(s
, '}'))
3024 static struct isl_obj
obj_read(__isl_keep isl_stream
*s
)
3026 isl_map
*map
= NULL
;
3027 struct isl_token
*tok
;
3028 struct vars
*v
= NULL
;
3029 struct isl_obj obj
= { isl_obj_set
, NULL
};
3031 if (next_is_schedule(s
))
3032 return schedule_read(s
);
3034 tok
= next_token(s
);
3036 isl_stream_error(s
, NULL
, "unexpected EOF");
3039 if (tok
->type
== ISL_TOKEN_VALUE
) {
3040 struct isl_token
*tok2
;
3041 struct isl_map
*map
;
3043 tok2
= isl_stream_next_token(s
);
3044 if (!tok2
|| tok2
->type
!= ISL_TOKEN_VALUE
||
3045 isl_int_is_neg(tok2
->u
.v
)) {
3047 isl_stream_push_token(s
, tok2
);
3048 obj
.type
= isl_obj_val
;
3049 obj
.v
= isl_val_int_from_isl_int(s
->ctx
, tok
->u
.v
);
3050 isl_token_free(tok
);
3053 isl_stream_push_token(s
, tok2
);
3054 isl_stream_push_token(s
, tok
);
3055 map
= map_read_polylib(s
);
3058 if (isl_map_may_be_set(map
))
3059 obj
.v
= isl_map_range(map
);
3061 obj
.type
= isl_obj_map
;
3066 v
= vars_new(s
->ctx
);
3068 isl_stream_push_token(s
, tok
);
3071 map
= isl_map_universe(isl_space_params_alloc(s
->ctx
, 0));
3072 if (tok
->type
== '[') {
3073 isl_stream_push_token(s
, tok
);
3074 map
= read_map_tuple(s
, map
, isl_dim_param
, v
, 0, 0);
3077 tok
= isl_stream_next_token(s
);
3078 if (!tok
|| tok
->type
!= ISL_TOKEN_TO
) {
3079 isl_stream_error(s
, tok
, "expecting '->'");
3081 isl_stream_push_token(s
, tok
);
3084 isl_token_free(tok
);
3085 tok
= isl_stream_next_token(s
);
3087 if (!tok
|| tok
->type
!= '{') {
3088 isl_stream_error(s
, tok
, "expecting '{'");
3090 isl_stream_push_token(s
, tok
);
3093 isl_token_free(tok
);
3095 tok
= isl_stream_next_token(s
);
3098 else if (tok
->type
== ISL_TOKEN_IDENT
&& !strcmp(tok
->u
.s
, "Sym")) {
3099 isl_token_free(tok
);
3100 if (isl_stream_eat(s
, '='))
3102 map
= read_map_tuple(s
, map
, isl_dim_param
, v
, 0, 1);
3106 isl_stream_push_token(s
, tok
);
3108 obj
= obj_read_disjuncts(s
, v
, map
);
3109 if (obj
.type
== isl_obj_none
|| !obj
.v
)
3112 tok
= isl_stream_next_token(s
);
3113 if (tok
&& tok
->type
== '}') {
3114 isl_token_free(tok
);
3116 isl_stream_error(s
, tok
, "unexpected isl_token");
3118 isl_token_free(tok
);
3128 obj
.type
->free(obj
.v
);
3135 struct isl_obj
isl_stream_read_obj(__isl_keep isl_stream
*s
)
3140 __isl_give isl_map
*isl_stream_read_map(__isl_keep isl_stream
*s
)
3146 isl_assert(s
->ctx
, obj
.type
== isl_obj_map
||
3147 obj
.type
== isl_obj_set
, goto error
);
3149 if (obj
.type
== isl_obj_set
)
3150 obj
.v
= isl_map_from_range(obj
.v
);
3154 obj
.type
->free(obj
.v
);
3158 __isl_give isl_set
*isl_stream_read_set(__isl_keep isl_stream
*s
)
3164 if (obj
.type
== isl_obj_map
&& isl_map_may_be_set(obj
.v
)) {
3165 obj
.v
= isl_map_range(obj
.v
);
3166 obj
.type
= isl_obj_set
;
3168 isl_assert(s
->ctx
, obj
.type
== isl_obj_set
, goto error
);
3173 obj
.type
->free(obj
.v
);
3177 __isl_give isl_union_map
*isl_stream_read_union_map(__isl_keep isl_stream
*s
)
3182 if (obj
.type
== isl_obj_map
) {
3183 obj
.type
= isl_obj_union_map
;
3184 obj
.v
= isl_union_map_from_map(obj
.v
);
3186 if (obj
.type
== isl_obj_set
) {
3187 obj
.type
= isl_obj_union_set
;
3188 obj
.v
= isl_union_set_from_set(obj
.v
);
3190 if (obj
.v
&& obj
.type
== isl_obj_union_set
&&
3191 isl_union_set_is_empty(obj
.v
))
3192 obj
.type
= isl_obj_union_map
;
3193 if (obj
.v
&& obj
.type
!= isl_obj_union_map
)
3194 isl_die(s
->ctx
, isl_error_invalid
, "invalid input", goto error
);
3198 obj
.type
->free(obj
.v
);
3202 /* Extract an isl_union_set from "obj".
3203 * This only works if the object was detected as either a set
3204 * (in which case it is converted to a union set) or a union set.
3206 static __isl_give isl_union_set
*extract_union_set(isl_ctx
*ctx
,
3209 if (obj
.type
== isl_obj_set
) {
3210 obj
.type
= isl_obj_union_set
;
3211 obj
.v
= isl_union_set_from_set(obj
.v
);
3214 isl_assert(ctx
, obj
.type
== isl_obj_union_set
, goto error
);
3218 obj
.type
->free(obj
.v
);
3222 /* Read an isl_union_set from "s".
3223 * First read a generic object and then try and extract
3224 * an isl_union_set from that.
3226 __isl_give isl_union_set
*isl_stream_read_union_set(__isl_keep isl_stream
*s
)
3231 return extract_union_set(s
->ctx
, obj
);
3234 static __isl_give isl_basic_map
*isl_stream_read_basic_map(
3235 __isl_keep isl_stream
*s
)
3238 struct isl_map
*map
;
3239 struct isl_basic_map
*bmap
;
3242 if (obj
.v
&& (obj
.type
!= isl_obj_map
&& obj
.type
!= isl_obj_set
))
3243 isl_die(s
->ctx
, isl_error_invalid
, "not a (basic) set or map",
3250 isl_die(s
->ctx
, isl_error_invalid
,
3251 "set or map description involves "
3252 "more than one disjunct", goto error
);
3255 bmap
= isl_basic_map_empty(isl_map_get_space(map
));
3257 bmap
= isl_basic_map_copy(map
->p
[0]);
3263 obj
.type
->free(obj
.v
);
3267 /* Read an isl_basic_set object from "s".
3269 __isl_give isl_basic_set
*isl_stream_read_basic_set(__isl_keep isl_stream
*s
)
3271 isl_basic_map
*bmap
;
3272 bmap
= isl_stream_read_basic_map(s
);
3275 if (!isl_basic_map_may_be_set(bmap
))
3276 isl_die(s
->ctx
, isl_error_invalid
,
3277 "input is not a set", goto error
);
3278 return isl_basic_map_range(bmap
);
3280 isl_basic_map_free(bmap
);
3284 __isl_give isl_basic_map
*isl_basic_map_read_from_file(isl_ctx
*ctx
,
3287 struct isl_basic_map
*bmap
;
3288 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3291 bmap
= isl_stream_read_basic_map(s
);
3296 __isl_give isl_basic_set
*isl_basic_set_read_from_file(isl_ctx
*ctx
,
3299 isl_basic_set
*bset
;
3300 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3303 bset
= isl_stream_read_basic_set(s
);
3309 #define TYPE_BASE basic_map
3310 #include "isl_read_from_str_templ.c"
3313 #define TYPE_BASE basic_set
3314 #include "isl_read_from_str_templ.c"
3316 __isl_give isl_map
*isl_map_read_from_file(struct isl_ctx
*ctx
,
3319 struct isl_map
*map
;
3320 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3323 map
= isl_stream_read_map(s
);
3329 #define TYPE_BASE map
3330 #include "isl_read_from_str_templ.c"
3332 __isl_give isl_set
*isl_set_read_from_file(struct isl_ctx
*ctx
,
3336 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3339 set
= isl_stream_read_set(s
);
3345 #define TYPE_BASE set
3346 #include "isl_read_from_str_templ.c"
3348 __isl_give isl_union_map
*isl_union_map_read_from_file(isl_ctx
*ctx
,
3351 isl_union_map
*umap
;
3352 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3355 umap
= isl_stream_read_union_map(s
);
3361 #define TYPE_BASE union_map
3362 #include "isl_read_from_str_templ.c"
3364 __isl_give isl_union_set
*isl_union_set_read_from_file(isl_ctx
*ctx
,
3367 isl_union_set
*uset
;
3368 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3371 uset
= isl_stream_read_union_set(s
);
3377 #define TYPE_BASE union_set
3378 #include "isl_read_from_str_templ.c"
3380 static __isl_give isl_vec
*isl_vec_read_polylib(__isl_keep isl_stream
*s
)
3382 struct isl_vec
*vec
= NULL
;
3383 struct isl_token
*tok
;
3387 tok
= isl_stream_next_token(s
);
3388 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
3389 isl_stream_error(s
, tok
, "expecting vector length");
3393 size
= isl_int_get_si(tok
->u
.v
);
3394 isl_token_free(tok
);
3396 vec
= isl_vec_alloc(s
->ctx
, size
);
3398 for (j
= 0; j
< size
; ++j
) {
3399 tok
= next_signed_value(s
, "expecting constant value");
3402 isl_int_set(vec
->el
[j
], tok
->u
.v
);
3403 isl_token_free(tok
);
3408 isl_token_free(tok
);
3413 static __isl_give isl_vec
*vec_read(__isl_keep isl_stream
*s
)
3415 return isl_vec_read_polylib(s
);
3418 __isl_give isl_vec
*isl_vec_read_from_file(isl_ctx
*ctx
, FILE *input
)
3421 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3429 __isl_give isl_pw_qpolynomial
*isl_stream_read_pw_qpolynomial(
3430 __isl_keep isl_stream
*s
)
3436 isl_assert(s
->ctx
, obj
.type
== isl_obj_pw_qpolynomial
,
3441 obj
.type
->free(obj
.v
);
3446 #define TYPE_BASE pw_qpolynomial
3447 #include "isl_read_from_str_templ.c"
3449 __isl_give isl_pw_qpolynomial
*isl_pw_qpolynomial_read_from_file(isl_ctx
*ctx
,
3452 isl_pw_qpolynomial
*pwqp
;
3453 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3456 pwqp
= isl_stream_read_pw_qpolynomial(s
);
3461 /* Read an isl_pw_qpolynomial_fold from "s".
3462 * First read a generic object and
3463 * then check that it is an isl_pw_qpolynomial_fold.
3465 __isl_give isl_pw_qpolynomial_fold
*isl_stream_read_pw_qpolynomial_fold(
3466 __isl_keep isl_stream
*s
)
3471 if (obj
.v
&& obj
.type
!= isl_obj_pw_qpolynomial_fold
)
3472 isl_die(s
->ctx
, isl_error_invalid
, "invalid input", goto error
);
3476 obj
.type
->free(obj
.v
);
3481 #define TYPE_BASE pw_qpolynomial_fold
3482 #include "isl_read_from_str_templ.c"
3484 /* Is the next token an identifier not in "v"?
3486 static int next_is_fresh_ident(__isl_keep isl_stream
*s
, struct vars
*v
)
3490 struct isl_token
*tok
;
3492 tok
= isl_stream_next_token(s
);
3495 fresh
= tok
->type
== ISL_TOKEN_IDENT
&& vars_pos(v
, tok
->u
.s
, -1) >= n
;
3496 isl_stream_push_token(s
, tok
);
3498 vars_drop(v
, v
->n
- n
);
3503 /* First read the domain of the affine expression, which may be
3504 * a parameter space or a set.
3505 * The tricky part is that we don't know if the domain is a set or not,
3506 * so when we are trying to read the domain, we may actually be reading
3507 * the affine expression itself (defined on a parameter domains)
3508 * If the tuple we are reading is named, we assume it's the domain.
3509 * Also, if inside the tuple, the first thing we find is a nested tuple
3510 * or a new identifier, we again assume it's the domain.
3511 * Finally, if the tuple is empty, then it must be the domain
3512 * since it does not contain an affine expression.
3513 * Otherwise, we assume we are reading an affine expression.
3515 static __isl_give isl_set
*read_aff_domain(__isl_keep isl_stream
*s
,
3516 __isl_take isl_set
*dom
, struct vars
*v
)
3518 struct isl_token
*tok
, *tok2
;
3521 tok
= isl_stream_next_token(s
);
3522 if (tok
&& (tok
->type
== ISL_TOKEN_IDENT
|| tok
->is_keyword
)) {
3523 isl_stream_push_token(s
, tok
);
3524 return read_map_tuple(s
, dom
, isl_dim_set
, v
, 0, 0);
3526 if (!tok
|| tok
->type
!= '[') {
3527 isl_stream_error(s
, tok
, "expecting '['");
3530 tok2
= isl_stream_next_token(s
);
3531 is_empty
= tok2
&& tok2
->type
== ']';
3533 isl_stream_push_token(s
, tok2
);
3534 if (is_empty
|| next_is_tuple(s
) || next_is_fresh_ident(s
, v
)) {
3535 isl_stream_push_token(s
, tok
);
3536 dom
= read_map_tuple(s
, dom
, isl_dim_set
, v
, 0, 0);
3538 isl_stream_push_token(s
, tok
);
3543 isl_stream_push_token(s
, tok
);
3548 /* Read an affine expression from "s".
3550 __isl_give isl_aff
*isl_stream_read_aff(__isl_keep isl_stream
*s
)
3556 ma
= isl_stream_read_multi_aff(s
);
3557 dim
= isl_multi_aff_dim(ma
, isl_dim_out
);
3561 isl_die(s
->ctx
, isl_error_invalid
,
3562 "expecting single affine expression",
3565 aff
= isl_multi_aff_get_aff(ma
, 0);
3566 isl_multi_aff_free(ma
);
3569 isl_multi_aff_free(ma
);
3573 /* Read a piecewise affine expression from "s" with domain (space) "dom".
3575 static __isl_give isl_pw_aff
*read_pw_aff_with_dom(__isl_keep isl_stream
*s
,
3576 __isl_take isl_set
*dom
, struct vars
*v
)
3578 isl_pw_aff
*pwaff
= NULL
;
3580 if (!isl_set_is_params(dom
) && isl_stream_eat(s
, ISL_TOKEN_TO
))
3583 if (isl_stream_eat(s
, '['))
3586 pwaff
= accept_affine(s
, isl_set_get_space(dom
), v
);
3588 if (isl_stream_eat(s
, ']'))
3591 dom
= read_optional_formula(s
, dom
, v
, 0);
3592 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
3597 isl_pw_aff_free(pwaff
);
3601 __isl_give isl_pw_aff
*isl_stream_read_pw_aff(__isl_keep isl_stream
*s
)
3604 isl_set
*dom
= NULL
;
3606 isl_pw_aff
*pa
= NULL
;
3609 v
= vars_new(s
->ctx
);
3613 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
3614 if (next_is_tuple(s
)) {
3615 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
3616 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
3619 if (isl_stream_eat(s
, '{'))
3623 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
3624 pa
= read_pw_aff_with_dom(s
, aff_dom
, v
);
3625 vars_drop(v
, v
->n
- n
);
3627 while (isl_stream_eat_if_available(s
, ';')) {
3631 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
3632 pa_i
= read_pw_aff_with_dom(s
, aff_dom
, v
);
3633 vars_drop(v
, v
->n
- n
);
3635 pa
= isl_pw_aff_union_add(pa
, pa_i
);
3638 if (isl_stream_eat(s
, '}'))
3647 isl_pw_aff_free(pa
);
3652 #define TYPE_BASE aff
3653 #include "isl_read_from_str_templ.c"
3656 #define TYPE_BASE pw_aff
3657 #include "isl_read_from_str_templ.c"
3659 /* Given that "pa" is the element at position "pos" of a tuple
3660 * returned by read_tuple, check that it does not involve any
3661 * output/set dimensions (appearing at the "n" positions starting at "first"),
3662 * remove those from the domain and replace the domain space
3663 * with "domain_space".
3665 * In particular, the result of read_tuple is of the form
3666 * [input, output] -> [output], with anonymous domain.
3667 * The function read_tuple accepts tuples where some output or
3668 * set dimensions are defined in terms of other output or set dimensions
3669 * since this function is also used to read maps. As a special case,
3670 * read_tuple also accepts dimensions that are defined in terms of themselves
3671 * (i.e., that are not defined).
3672 * These cases are not allowed here.
3674 static __isl_give isl_pw_aff
*separate_tuple_entry(__isl_take isl_pw_aff
*pa
,
3675 int pos
, unsigned first
, unsigned n
, __isl_take isl_space
*domain_space
)
3679 involves
= isl_pw_aff_involves_dims(pa
, isl_dim_in
, first
, pos
+ 1);
3681 pa
= isl_pw_aff_free(pa
);
3682 } else if (involves
) {
3683 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
3684 "not an affine expression",
3685 pa
= isl_pw_aff_free(pa
));
3687 pa
= isl_pw_aff_drop_dims(pa
, isl_dim_in
, first
, n
);
3688 pa
= isl_pw_aff_reset_domain_space(pa
, domain_space
);
3693 /* Extract an isl_multi_pw_aff with domain space "dom_space"
3694 * from a tuple "tuple" read by read_tuple.
3696 * Check that none of the expressions depend on any other output/set dimensions.
3698 static __isl_give isl_multi_pw_aff
*extract_mpa_from_tuple(
3699 __isl_take isl_space
*dom_space
, __isl_keep isl_multi_pw_aff
*tuple
)
3704 isl_multi_pw_aff
*mpa
;
3706 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
3707 dim
= isl_space_dim(dom_space
, isl_dim_all
);
3708 if (n
< 0 || dim
< 0)
3709 dom_space
= isl_space_free(dom_space
);
3710 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
3711 space
= isl_space_align_params(space
, isl_space_copy(dom_space
));
3712 if (!isl_space_is_params(dom_space
))
3713 space
= isl_space_map_from_domain_and_range(
3714 isl_space_copy(dom_space
), space
);
3715 isl_space_free(dom_space
);
3716 mpa
= isl_multi_pw_aff_alloc(space
);
3718 for (i
= 0; i
< n
; ++i
) {
3720 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
3721 space
= isl_multi_pw_aff_get_domain_space(mpa
);
3722 pa
= separate_tuple_entry(pa
, i
, dim
, n
, space
);
3723 mpa
= isl_multi_pw_aff_set_pw_aff(mpa
, i
, pa
);
3729 /* Read a tuple of piecewise affine expressions,
3730 * including optional constraints on the domain from "s".
3731 * "dom" represents the initial constraints on the domain.
3733 * The input format is similar to that of a map, except that any conditions
3734 * on the domains should be specified inside the tuple since each
3735 * piecewise affine expression may have a different domain.
3736 * However, additional, shared conditions can also be specified.
3737 * This is especially useful for setting the explicit domain
3738 * of a zero-dimensional isl_multi_pw_aff.
3740 * The isl_multi_pw_aff may live in either a set or a map space.
3741 * First read the first tuple and check if it is followed by a "->".
3742 * If so, convert the tuple into the domain of the isl_multi_pw_aff and
3743 * read in the next tuple. This tuple (or the first tuple if it was
3744 * not followed by a "->") is then converted into an isl_multi_pw_aff
3745 * through a call to extract_mpa_from_tuple.
3746 * The domain of the result is intersected with the domain.
3748 * Note that the last tuple may introduce new identifiers,
3749 * but these cannot be referenced in the description of the domain.
3751 static __isl_give isl_multi_pw_aff
*read_conditional_multi_pw_aff(
3752 __isl_keep isl_stream
*s
, __isl_take isl_set
*dom
, struct vars
*v
)
3754 isl_multi_pw_aff
*tuple
;
3755 isl_multi_pw_aff
*mpa
;
3760 tuple
= read_tuple(s
, v
, 0, 0);
3763 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TO
)) {
3764 isl_map
*map
= map_from_tuple(tuple
, dom
, isl_dim_in
, v
, 0);
3765 dom
= isl_map_domain(map
);
3767 tuple
= read_tuple(s
, v
, 0, 0);
3771 mpa
= extract_mpa_from_tuple(isl_set_get_space(dom
), tuple
);
3772 isl_multi_pw_aff_free(tuple
);
3774 dom
= isl_set_free(dom
);
3776 vars_drop(v
, v
->n
- n_dom
);
3777 dom
= read_optional_formula(s
, dom
, v
, 0);
3779 vars_drop(v
, v
->n
- n
);
3781 mpa
= isl_multi_pw_aff_intersect_domain(mpa
, dom
);
3789 /* Read a tuple of affine expressions, together with optional constraints
3790 * on the domain from "s". "dom" represents the initial constraints
3793 * Read a tuple of piecewise affine expressions with optional constraints and
3794 * convert the result to an isl_pw_multi_aff on the shared domain.
3796 static __isl_give isl_pw_multi_aff
*read_conditional_multi_aff(
3797 __isl_keep isl_stream
*s
, __isl_take isl_set
*dom
, struct vars
*v
)
3799 isl_multi_pw_aff
*mpa
;
3801 mpa
= read_conditional_multi_pw_aff(s
, dom
, v
);
3802 return isl_pw_multi_aff_from_multi_pw_aff(mpa
);
3805 /* Read an isl_union_pw_multi_aff from "s".
3807 * In particular, first read the parameters and then read a sequence
3808 * of zero or more tuples of affine expressions with optional conditions and
3811 __isl_give isl_union_pw_multi_aff
*isl_stream_read_union_pw_multi_aff(
3812 __isl_keep isl_stream
*s
)
3816 isl_union_pw_multi_aff
*upma
= NULL
;
3818 v
= vars_new(s
->ctx
);
3822 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
3823 if (next_is_tuple(s
)) {
3824 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
3825 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
3828 if (isl_stream_eat(s
, '{'))
3831 upma
= isl_union_pw_multi_aff_empty(isl_set_get_space(dom
));
3834 isl_pw_multi_aff
*pma
;
3835 isl_union_pw_multi_aff
*upma2
;
3837 if (isl_stream_next_token_is(s
, '}'))
3840 pma
= read_conditional_multi_aff(s
, isl_set_copy(dom
), v
);
3841 upma2
= isl_union_pw_multi_aff_from_pw_multi_aff(pma
);
3842 upma
= isl_union_pw_multi_aff_union_add(upma
, upma2
);
3845 } while (isl_stream_eat_if_available(s
, ';'));
3847 if (isl_stream_eat(s
, '}'))
3854 isl_union_pw_multi_aff_free(upma
);
3860 /* Read an isl_pw_multi_aff from "s".
3862 * Read a more generic isl_union_pw_multi_aff first and
3863 * then check that the result lives in a single space.
3865 __isl_give isl_pw_multi_aff
*isl_stream_read_pw_multi_aff(
3866 __isl_keep isl_stream
*s
)
3868 isl_bool single_space
;
3869 isl_union_pw_multi_aff
*upma
;
3871 upma
= isl_stream_read_union_pw_multi_aff(s
);
3872 single_space
= isl_union_pw_multi_aff_isa_pw_multi_aff(upma
);
3873 if (single_space
< 0)
3874 upma
= isl_union_pw_multi_aff_free(upma
);
3875 else if (!single_space
)
3876 isl_die(s
->ctx
, isl_error_invalid
,
3877 "expecting expression in single space",
3878 upma
= isl_union_pw_multi_aff_free(upma
));
3879 return isl_union_pw_multi_aff_as_pw_multi_aff(upma
);
3883 #define TYPE_BASE pw_multi_aff
3884 #include "isl_read_from_str_templ.c"
3887 #define TYPE_BASE union_pw_multi_aff
3888 #include "isl_read_from_str_templ.c"
3893 #include <isl_multi_read_no_explicit_domain_templ.c>
3898 #include <isl_multi_read_no_explicit_domain_templ.c>
3900 /* Read a multi-affine expression from "s".
3901 * If the multi-affine expression has a domain, then the tuple
3902 * representing this domain cannot involve any affine expressions.
3903 * The tuple representing the actual expressions needs to consist
3904 * of only affine expressions. Moreover, these expressions can
3905 * only depend on parameters and input dimensions and not on other
3906 * output dimensions.
3908 __isl_give isl_multi_aff
*isl_stream_read_multi_aff(__isl_keep isl_stream
*s
)
3911 isl_multi_pw_aff
*tuple
= NULL
;
3914 isl_space
*space
, *dom_space
= NULL
;
3915 isl_multi_aff
*ma
= NULL
;
3917 v
= vars_new(s
->ctx
);
3921 dom_space
= read_params(s
, v
);
3924 if (isl_stream_eat(s
, '{'))
3927 tuple
= read_tuple(s
, v
, 0, 0);
3930 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TO
)) {
3934 has_expr
= tuple_has_expr(tuple
);
3938 isl_die(s
->ctx
, isl_error_invalid
,
3939 "expecting universe domain", goto error
);
3940 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
3941 dom_space
= isl_space_align_params(space
, dom_space
);
3942 isl_multi_pw_aff_free(tuple
);
3943 tuple
= read_tuple(s
, v
, 0, 0);
3948 if (isl_stream_eat(s
, '}'))
3951 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
3952 dim
= isl_space_dim(dom_space
, isl_dim_all
);
3953 if (n
< 0 || dim
< 0)
3955 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
3956 space
= isl_space_align_params(space
, isl_space_copy(dom_space
));
3957 if (!isl_space_is_params(dom_space
))
3958 space
= isl_space_map_from_domain_and_range(
3959 isl_space_copy(dom_space
), space
);
3960 ma
= isl_multi_aff_alloc(space
);
3962 for (i
= 0; i
< n
; ++i
) {
3965 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
3966 space
= isl_multi_aff_get_domain_space(ma
);
3967 pa
= separate_tuple_entry(pa
, i
, dim
, n
, space
);
3968 aff
= isl_pw_aff_as_aff(pa
);
3969 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3972 isl_multi_pw_aff_free(tuple
);
3974 isl_space_free(dom_space
);
3977 isl_multi_pw_aff_free(tuple
);
3979 isl_space_free(dom_space
);
3980 isl_multi_aff_free(ma
);
3985 #define TYPE_BASE multi_aff
3986 #include "isl_read_from_str_templ.c"
3988 /* Read an isl_multi_pw_aff from "s".
3990 __isl_give isl_multi_pw_aff
*isl_stream_read_multi_pw_aff(
3991 __isl_keep isl_stream
*s
)
3994 isl_set
*dom
= NULL
;
3995 isl_multi_pw_aff
*mpa
= NULL
;
3997 v
= vars_new(s
->ctx
);
4001 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
4002 if (next_is_tuple(s
)) {
4003 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
4004 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
4007 if (isl_stream_eat(s
, '{'))
4010 mpa
= read_conditional_multi_pw_aff(s
, isl_set_copy(dom
), v
);
4012 if (isl_stream_eat(s
, '}'))
4021 isl_multi_pw_aff_free(mpa
);
4026 #define TYPE_BASE multi_pw_aff
4027 #include "isl_read_from_str_templ.c"
4029 /* Read the body of an isl_union_pw_aff from "s" with parameter domain "dom".
4031 static __isl_give isl_union_pw_aff
*read_union_pw_aff_with_dom(
4032 __isl_keep isl_stream
*s
, __isl_take isl_set
*dom
, struct vars
*v
)
4035 isl_union_pw_aff
*upa
= NULL
;
4040 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
4041 pa
= read_pw_aff_with_dom(s
, aff_dom
, v
);
4042 vars_drop(v
, v
->n
- n
);
4044 upa
= isl_union_pw_aff_from_pw_aff(pa
);
4046 while (isl_stream_eat_if_available(s
, ';')) {
4048 isl_union_pw_aff
*upa_i
;
4051 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
4052 pa_i
= read_pw_aff_with_dom(s
, aff_dom
, v
);
4053 vars_drop(v
, v
->n
- n
);
4055 upa_i
= isl_union_pw_aff_from_pw_aff(pa_i
);
4056 upa
= isl_union_pw_aff_union_add(upa
, upa_i
);
4063 /* Read an isl_union_pw_aff from "s".
4065 * First check if there are any paramters, then read in the opening brace
4066 * and use read_union_pw_aff_with_dom to read in the body of
4067 * the isl_union_pw_aff. Finally, read the closing brace.
4069 __isl_give isl_union_pw_aff
*isl_stream_read_union_pw_aff(
4070 __isl_keep isl_stream
*s
)
4074 isl_union_pw_aff
*upa
= NULL
;
4076 v
= vars_new(s
->ctx
);
4080 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
4081 if (next_is_tuple(s
)) {
4082 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
4083 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
4086 if (isl_stream_eat(s
, '{'))
4089 upa
= read_union_pw_aff_with_dom(s
, isl_set_copy(dom
), v
);
4091 if (isl_stream_eat(s
, '}'))
4100 isl_union_pw_aff_free(upa
);
4105 #define TYPE_BASE union_pw_aff
4106 #include "isl_read_from_str_templ.c"
4108 /* This function is called for each element in a tuple inside
4109 * isl_stream_read_multi_union_pw_aff.
4111 * Read a '{', the union piecewise affine expression body and a '}' and
4112 * add the isl_union_pw_aff to *list.
4114 static __isl_give isl_space
*read_union_pw_aff_el(__isl_keep isl_stream
*s
,
4115 struct vars
*v
, __isl_take isl_space
*space
, int rational
, void *user
)
4118 isl_union_pw_aff
*upa
;
4119 isl_union_pw_aff_list
**list
= (isl_union_pw_aff_list
**) user
;
4121 dom
= isl_set_universe(isl_space_params(isl_space_copy(space
)));
4122 if (isl_stream_eat(s
, '{'))
4124 upa
= read_union_pw_aff_with_dom(s
, dom
, v
);
4125 *list
= isl_union_pw_aff_list_add(*list
, upa
);
4126 if (isl_stream_eat(s
, '}'))
4127 return isl_space_free(space
);
4129 return isl_space_free(space
);
4133 return isl_space_free(space
);
4136 /* Do the next tokens in "s" correspond to an empty tuple?
4137 * In particular, does the stream start with a '[', followed by a ']',
4138 * not followed by a "->"?
4140 static int next_is_empty_tuple(__isl_keep isl_stream
*s
)
4142 struct isl_token
*tok
, *tok2
, *tok3
;
4143 int is_empty_tuple
= 0;
4145 tok
= isl_stream_next_token(s
);
4148 if (tok
->type
!= '[') {
4149 isl_stream_push_token(s
, tok
);
4153 tok2
= isl_stream_next_token(s
);
4154 if (tok2
&& tok2
->type
== ']') {
4155 tok3
= isl_stream_next_token(s
);
4156 is_empty_tuple
= !tok
|| tok
->type
!= ISL_TOKEN_TO
;
4158 isl_stream_push_token(s
, tok3
);
4161 isl_stream_push_token(s
, tok2
);
4162 isl_stream_push_token(s
, tok
);
4164 return is_empty_tuple
;
4167 /* Do the next tokens in "s" correspond to a tuple of parameters?
4168 * In particular, does the stream start with a '[' that is not
4169 * followed by a '{' or a nested tuple?
4171 static int next_is_param_tuple(__isl_keep isl_stream
*s
)
4173 struct isl_token
*tok
, *tok2
;
4176 tok
= isl_stream_next_token(s
);
4179 if (tok
->type
!= '[' || next_is_tuple(s
)) {
4180 isl_stream_push_token(s
, tok
);
4184 tok2
= isl_stream_next_token(s
);
4185 is_tuple
= tok2
&& tok2
->type
!= '{';
4187 isl_stream_push_token(s
, tok2
);
4188 isl_stream_push_token(s
, tok
);
4193 /* Read the core of a body of an isl_multi_union_pw_aff from "s",
4194 * i.e., everything except the parameter specification and
4195 * without shared domain constraints.
4196 * "v" contains a description of the identifiers parsed so far.
4197 * The parameters, if any, are specified by "space".
4199 * The body is of the form
4201 * [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4203 * Read the tuple, collecting the individual isl_union_pw_aff
4204 * elements in a list and construct the result from the tuple space and
4207 static __isl_give isl_multi_union_pw_aff
*read_multi_union_pw_aff_body_core(
4208 __isl_keep isl_stream
*s
, struct vars
*v
, __isl_take isl_space
*space
)
4210 isl_union_pw_aff_list
*list
;
4211 isl_multi_union_pw_aff
*mupa
;
4213 list
= isl_union_pw_aff_list_alloc(s
->ctx
, 0);
4214 space
= read_tuple_space(s
, v
, space
, 1, 0,
4215 &read_union_pw_aff_el
, &list
);
4216 mupa
= isl_multi_union_pw_aff_from_union_pw_aff_list(space
, list
);
4221 /* Read the body of an isl_union_set from "s",
4222 * i.e., everything except the parameter specification.
4223 * "v" contains a description of the identifiers parsed so far.
4224 * The parameters, if any, are specified by "space".
4226 * First read a generic disjunction of object bodies and then try and extract
4227 * an isl_union_set from that.
4229 static __isl_give isl_union_set
*read_union_set_body(__isl_keep isl_stream
*s
,
4230 struct vars
*v
, __isl_take isl_space
*space
)
4232 struct isl_obj obj
= { isl_obj_set
, NULL
};
4235 map
= isl_set_universe(space
);
4236 if (isl_stream_eat(s
, '{') < 0)
4238 obj
= obj_read_disjuncts(s
, v
, map
);
4239 if (isl_stream_eat(s
, '}') < 0)
4243 return extract_union_set(s
->ctx
, obj
);
4245 obj
.type
->free(obj
.v
);
4250 /* Read the body of an isl_multi_union_pw_aff from "s",
4251 * i.e., everything except the parameter specification.
4252 * "v" contains a description of the identifiers parsed so far.
4253 * The parameters, if any, are specified by "space".
4255 * In particular, handle the special case with shared domain constraints.
4256 * These are specified as
4260 * and are especially useful for setting the explicit domain
4261 * of a zero-dimensional isl_multi_union_pw_aff.
4262 * The core isl_multi_union_pw_aff body ([...]) is read by
4263 * read_multi_union_pw_aff_body_core.
4265 static __isl_give isl_multi_union_pw_aff
*read_multi_union_pw_aff_body(
4266 __isl_keep isl_stream
*s
, struct vars
*v
, __isl_take isl_space
*space
)
4268 isl_multi_union_pw_aff
*mupa
;
4270 if (!isl_stream_next_token_is(s
, '('))
4271 return read_multi_union_pw_aff_body_core(s
, v
, space
);
4273 if (isl_stream_eat(s
, '(') < 0)
4275 mupa
= read_multi_union_pw_aff_body_core(s
, v
, isl_space_copy(space
));
4276 if (isl_stream_eat_if_available(s
, ':')) {
4279 dom
= read_union_set_body(s
, v
, space
);
4280 mupa
= isl_multi_union_pw_aff_intersect_domain(mupa
, dom
);
4282 isl_space_free(space
);
4284 if (isl_stream_eat(s
, ')') < 0)
4285 return isl_multi_union_pw_aff_free(mupa
);
4289 isl_space_free(space
);
4293 /* Read an isl_multi_union_pw_aff from "s".
4295 * The input has the form
4297 * [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4301 * [..] -> [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4303 * Additionally, a shared domain may be specified as
4309 * [..] -> ([..] : ...)
4311 * The first case is handled by the caller, the second case
4312 * is handled by read_multi_union_pw_aff_body.
4314 * We first check for the special case of an empty tuple "[]".
4315 * Then we check if there are any parameters.
4316 * Finally, read the tuple and construct the result.
4318 static __isl_give isl_multi_union_pw_aff
*read_multi_union_pw_aff_core(
4319 __isl_keep isl_stream
*s
)
4322 isl_set
*dom
= NULL
;
4324 isl_multi_union_pw_aff
*mupa
= NULL
;
4326 if (next_is_empty_tuple(s
)) {
4327 if (isl_stream_eat(s
, '['))
4329 if (isl_stream_eat(s
, ']'))
4331 space
= isl_space_set_alloc(s
->ctx
, 0, 0);
4332 return isl_multi_union_pw_aff_zero(space
);
4335 v
= vars_new(s
->ctx
);
4339 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
4340 if (next_is_param_tuple(s
)) {
4341 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
4342 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
4345 space
= isl_set_get_space(dom
);
4347 mupa
= read_multi_union_pw_aff_body(s
, v
, space
);
4355 isl_multi_union_pw_aff_free(mupa
);
4359 /* Read an isl_multi_union_pw_aff from "s".
4361 * In particular, handle the special case with shared domain constraints.
4362 * These are specified as
4366 * and are especially useful for setting the explicit domain
4367 * of a zero-dimensional isl_multi_union_pw_aff.
4368 * The core isl_multi_union_pw_aff ([...]) is read by
4369 * read_multi_union_pw_aff_core.
4371 __isl_give isl_multi_union_pw_aff
*isl_stream_read_multi_union_pw_aff(
4372 __isl_keep isl_stream
*s
)
4374 isl_multi_union_pw_aff
*mupa
;
4376 if (!isl_stream_next_token_is(s
, '('))
4377 return read_multi_union_pw_aff_core(s
);
4379 if (isl_stream_eat(s
, '(') < 0)
4381 mupa
= read_multi_union_pw_aff_core(s
);
4382 if (isl_stream_eat_if_available(s
, ':')) {
4385 dom
= isl_stream_read_union_set(s
);
4386 mupa
= isl_multi_union_pw_aff_intersect_domain(mupa
, dom
);
4388 if (isl_stream_eat(s
, ')') < 0)
4389 return isl_multi_union_pw_aff_free(mupa
);
4394 #define TYPE_BASE multi_union_pw_aff
4395 #include "isl_read_from_str_templ.c"
4397 __isl_give isl_union_pw_qpolynomial
*isl_stream_read_union_pw_qpolynomial(
4398 __isl_keep isl_stream
*s
)
4403 if (obj
.type
== isl_obj_pw_qpolynomial
) {
4404 obj
.type
= isl_obj_union_pw_qpolynomial
;
4405 obj
.v
= isl_union_pw_qpolynomial_from_pw_qpolynomial(obj
.v
);
4408 isl_assert(s
->ctx
, obj
.type
== isl_obj_union_pw_qpolynomial
,
4413 obj
.type
->free(obj
.v
);
4418 #define TYPE_BASE union_pw_qpolynomial
4419 #include "isl_read_from_str_templ.c"