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
);
249 /* Read an isl_val from "str".
251 __isl_give isl_val
*isl_val_read_from_str(isl_ctx
*ctx
, const char *str
)
254 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
257 val
= isl_stream_read_val(s
);
262 static isl_stat
accept_cst_factor(__isl_keep isl_stream
*s
, isl_int
*f
)
264 struct isl_token
*tok
;
266 if (isl_stream_eat_if_available(s
, '-'))
269 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
270 isl_stream_error(s
, tok
, "expecting constant value");
274 isl_int_mul(*f
, *f
, tok
->u
.v
);
278 if (isl_stream_eat_if_available(s
, '*'))
279 return accept_cst_factor(s
, f
);
284 return isl_stat_error
;
287 /* Given an affine expression aff, return an affine expression
288 * for aff % d, with d the next token on the stream, which is
289 * assumed to be a constant.
291 * We introduce an integer division q = [aff/d] and the result
292 * is set to aff - d q.
294 static __isl_give isl_pw_aff
*affine_mod(__isl_keep isl_stream
*s
,
295 struct vars
*v
, __isl_take isl_pw_aff
*aff
)
297 struct isl_token
*tok
;
301 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
302 isl_stream_error(s
, tok
, "expecting constant value");
306 q
= isl_pw_aff_copy(aff
);
307 q
= isl_pw_aff_scale_down(q
, tok
->u
.v
);
308 q
= isl_pw_aff_floor(q
);
309 q
= isl_pw_aff_scale(q
, tok
->u
.v
);
311 aff
= isl_pw_aff_sub(aff
, q
);
316 isl_pw_aff_free(aff
);
321 static __isl_give isl_pw_aff
*accept_affine(__isl_keep isl_stream
*s
,
322 __isl_take isl_space
*space
, struct vars
*v
);
323 static __isl_give isl_pw_aff_list
*accept_affine_list(__isl_keep isl_stream
*s
,
324 __isl_take isl_space
*space
, struct vars
*v
);
326 static __isl_give isl_pw_aff
*accept_minmax(__isl_keep isl_stream
*s
,
327 __isl_take isl_space
*space
, struct vars
*v
)
329 struct isl_token
*tok
;
330 isl_pw_aff_list
*list
= NULL
;
333 tok
= isl_stream_next_token(s
);
336 min
= tok
->type
== ISL_TOKEN_MIN
;
339 if (isl_stream_eat(s
, '('))
342 list
= accept_affine_list(s
, isl_space_copy(space
), v
);
346 if (isl_stream_eat(s
, ')'))
349 isl_space_free(space
);
350 return min
? isl_pw_aff_list_min(list
) : isl_pw_aff_list_max(list
);
352 isl_space_free(space
);
353 isl_pw_aff_list_free(list
);
357 /* Divide "pa" by an integer constant read from the stream.
359 static __isl_give isl_pw_aff
*pw_aff_div_by_cst(__isl_keep isl_stream
*s
,
360 __isl_take isl_pw_aff
*pa
)
362 struct isl_token
*tok
;
365 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
366 isl_stream_error(s
, tok
, "expecting denominator");
368 return isl_pw_aff_free(pa
);
371 pa
= isl_pw_aff_scale_down(pa
, tok
->u
.v
);
378 /* Return the (signed) value that is next on the stream,
379 * using "next" to read the next token and printing "msg" in case of an error.
381 static struct isl_token
*next_signed_value_fn(__isl_keep isl_stream
*s
,
382 struct isl_token
*(*next
)(__isl_keep isl_stream
*s
), char *msg
)
384 struct isl_token
*tok
;
387 if (isl_stream_eat_if_available(s
, '-'))
390 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
391 isl_stream_error(s
, tok
, msg
);
396 isl_int_neg(tok
->u
.v
, tok
->u
.v
);
400 /* Return the (signed) value that is next on the stream,
401 * printing "msg" in case of an error.
403 static struct isl_token
*next_signed_value(__isl_keep isl_stream
*s
, char *msg
)
405 return next_signed_value_fn(s
, &isl_stream_next_token
, msg
);
408 /* Return the (signed) value that is next on the stream,
409 * provided it is on the same line,
410 * printing "msg" in case of an error.
412 static struct isl_token
*next_signed_value_on_same_line(
413 __isl_keep isl_stream
*s
, char *msg
)
415 return next_signed_value_fn(s
,
416 &isl_stream_next_token_on_same_line
, msg
);
419 /* Is "tok" the start of an integer division?
421 static int is_start_of_div(struct isl_token
*tok
)
425 if (tok
->type
== '[')
427 if (tok
->type
== ISL_TOKEN_FLOOR
)
429 if (tok
->type
== ISL_TOKEN_CEIL
)
431 if (tok
->type
== ISL_TOKEN_FLOORD
)
433 if (tok
->type
== ISL_TOKEN_CEILD
)
438 /* Read an integer division from "s" and return it as an isl_pw_aff.
440 * The integer division can be of the form
442 * [<affine expression>]
443 * floor(<affine expression>)
444 * ceil(<affine expression>)
445 * floord(<affine expression>,<denominator>)
446 * ceild(<affine expression>,<denominator>)
448 static __isl_give isl_pw_aff
*accept_div(__isl_keep isl_stream
*s
,
449 __isl_take isl_space
*space
, struct vars
*v
)
454 isl_pw_aff
*pwaff
= NULL
;
456 if (isl_stream_eat_if_available(s
, ISL_TOKEN_FLOORD
))
458 else if (isl_stream_eat_if_available(s
, ISL_TOKEN_CEILD
))
460 else if (isl_stream_eat_if_available(s
, ISL_TOKEN_FLOOR
))
462 else if (isl_stream_eat_if_available(s
, ISL_TOKEN_CEIL
))
465 if (isl_stream_eat(s
, '('))
468 if (isl_stream_eat(s
, '['))
472 pwaff
= accept_affine(s
, isl_space_copy(space
), v
);
475 if (isl_stream_eat(s
, ','))
478 pwaff
= pw_aff_div_by_cst(s
, pwaff
);
482 pwaff
= isl_pw_aff_ceil(pwaff
);
484 pwaff
= isl_pw_aff_floor(pwaff
);
487 if (isl_stream_eat(s
, ')'))
490 if (isl_stream_eat(s
, ']'))
494 isl_space_free(space
);
497 isl_space_free(space
);
498 isl_pw_aff_free(pwaff
);
502 static __isl_give isl_pw_aff
*accept_affine_factor(__isl_keep isl_stream
*s
,
503 __isl_take isl_space
*space
, struct vars
*v
)
505 struct isl_token
*tok
= NULL
;
506 isl_pw_aff
*res
= NULL
;
510 isl_stream_error(s
, NULL
, "unexpected EOF");
514 if (tok
->type
== ISL_TOKEN_AFF
) {
515 res
= isl_pw_aff_copy(tok
->u
.pwaff
);
517 } else if (tok
->type
== ISL_TOKEN_IDENT
) {
519 int pos
= vars_pos(v
, tok
->u
.s
, -1);
525 vars_drop(v
, v
->n
- n
);
526 isl_stream_error(s
, tok
, "unknown identifier");
530 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(isl_space_copy(space
)));
533 aff
->v
= isl_vec_set_element_si(aff
->v
, 2 + pos
, 1);
535 aff
= isl_aff_free(aff
);
536 res
= isl_pw_aff_from_aff(aff
);
538 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
539 if (isl_stream_eat_if_available(s
, '*') ||
540 isl_stream_next_token_is(s
, ISL_TOKEN_IDENT
)) {
541 if (isl_stream_eat_if_available(s
, '-'))
542 isl_int_neg(tok
->u
.v
, tok
->u
.v
);
543 res
= accept_affine_factor(s
, isl_space_copy(space
), v
);
544 res
= isl_pw_aff_scale(res
, tok
->u
.v
);
548 ls
= isl_local_space_from_space(isl_space_copy(space
));
549 aff
= isl_aff_zero_on_domain(ls
);
550 aff
= isl_aff_add_constant(aff
, tok
->u
.v
);
551 res
= isl_pw_aff_from_aff(aff
);
554 } else if (tok
->type
== '(') {
557 res
= accept_affine(s
, isl_space_copy(space
), v
);
560 if (isl_stream_eat(s
, ')'))
562 } else if (is_start_of_div(tok
)) {
563 isl_stream_push_token(s
, tok
);
565 res
= accept_div(s
, isl_space_copy(space
), v
);
566 } else if (tok
->type
== ISL_TOKEN_MIN
|| tok
->type
== ISL_TOKEN_MAX
) {
567 isl_stream_push_token(s
, tok
);
569 res
= accept_minmax(s
, isl_space_copy(space
), v
);
571 isl_stream_error(s
, tok
, "expecting factor");
574 if (isl_stream_eat_if_available(s
, '%') ||
575 isl_stream_eat_if_available(s
, ISL_TOKEN_MOD
)) {
576 isl_space_free(space
);
577 return affine_mod(s
, v
, res
);
579 if (isl_stream_eat_if_available(s
, '*')) {
582 isl_int_set_si(f
, 1);
583 if (accept_cst_factor(s
, &f
) < 0) {
587 res
= isl_pw_aff_scale(res
, f
);
590 if (isl_stream_eat_if_available(s
, '/'))
591 res
= pw_aff_div_by_cst(s
, res
);
592 if (isl_stream_eat_if_available(s
, ISL_TOKEN_INT_DIV
))
593 res
= isl_pw_aff_floor(pw_aff_div_by_cst(s
, res
));
595 isl_space_free(space
);
600 isl_pw_aff_free(res
);
601 isl_space_free(space
);
605 /* Return a piecewise affine expression defined on the specified domain
606 * that represents NaN.
608 static __isl_give isl_pw_aff
*nan_on_domain(__isl_keep isl_space
*space
)
610 return isl_pw_aff_nan_on_domain_space(isl_space_copy(space
));
613 static __isl_give isl_pw_aff
*accept_affine(__isl_keep isl_stream
*s
,
614 __isl_take isl_space
*space
, struct vars
*v
)
616 struct isl_token
*tok
= NULL
;
622 ls
= isl_local_space_from_space(isl_space_copy(space
));
623 res
= isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls
));
630 isl_stream_error(s
, NULL
, "unexpected EOF");
633 if (tok
->type
== '-') {
638 if (tok
->type
== '(' || is_start_of_div(tok
) ||
639 tok
->type
== ISL_TOKEN_MIN
|| tok
->type
== ISL_TOKEN_MAX
||
640 tok
->type
== ISL_TOKEN_IDENT
||
641 tok
->type
== ISL_TOKEN_VALUE
||
642 tok
->type
== ISL_TOKEN_AFF
) {
644 if (tok
->type
== ISL_TOKEN_VALUE
&& sign
< 0) {
645 isl_int_neg(tok
->u
.v
, tok
->u
.v
);
648 isl_stream_push_token(s
, tok
);
650 term
= accept_affine_factor(s
,
651 isl_space_copy(space
), v
);
653 res
= isl_pw_aff_sub(res
, term
);
655 res
= isl_pw_aff_add(res
, term
);
658 } else if (tok
->type
== ISL_TOKEN_NAN
) {
659 res
= isl_pw_aff_add(res
, nan_on_domain(space
));
661 isl_stream_error(s
, tok
, "unexpected isl_token");
662 isl_stream_push_token(s
, tok
);
663 isl_pw_aff_free(res
);
664 isl_space_free(space
);
671 if (tok
&& tok
->type
== '-') {
674 } else if (tok
&& tok
->type
== '+') {
679 isl_stream_push_token(s
, tok
);
684 isl_space_free(space
);
687 isl_space_free(space
);
689 isl_pw_aff_free(res
);
693 /* Is "type" the type of a comparison operator between lists
694 * of affine expressions?
696 static int is_list_comparator_type(int type
)
699 case ISL_TOKEN_LEX_LT
:
700 case ISL_TOKEN_LEX_GT
:
701 case ISL_TOKEN_LEX_LE
:
702 case ISL_TOKEN_LEX_GE
:
709 static int is_comparator(struct isl_token
*tok
)
713 if (is_list_comparator_type(tok
->type
))
729 static __isl_give isl_map
*read_formula(__isl_keep isl_stream
*s
,
730 struct vars
*v
, __isl_take isl_map
*map
, int rational
);
731 static __isl_give isl_pw_aff
*accept_extended_affine(__isl_keep isl_stream
*s
,
732 __isl_take isl_space
*space
, struct vars
*v
, int rational
);
734 /* Accept a ternary operator, given the first argument.
736 static __isl_give isl_pw_aff
*accept_ternary(__isl_keep isl_stream
*s
,
737 __isl_take isl_map
*cond
, struct vars
*v
, int rational
)
740 isl_pw_aff
*pwaff1
= NULL
, *pwaff2
= NULL
, *pa_cond
;
745 if (isl_stream_eat(s
, '?'))
748 space
= isl_space_wrap(isl_map_get_space(cond
));
749 pwaff1
= accept_extended_affine(s
, space
, v
, rational
);
753 if (isl_stream_eat(s
, ':'))
756 space
= isl_pw_aff_get_domain_space(pwaff1
);
757 pwaff2
= accept_extended_affine(s
, space
, v
, rational
);
761 pa_cond
= isl_set_indicator_function(isl_map_wrap(cond
));
762 return isl_pw_aff_cond(pa_cond
, pwaff1
, pwaff2
);
765 isl_pw_aff_free(pwaff1
);
766 isl_pw_aff_free(pwaff2
);
770 /* Set *line and *col to those of the next token, if any.
772 static void set_current_line_col(__isl_keep isl_stream
*s
, int *line
, int *col
)
774 struct isl_token
*tok
;
776 tok
= isl_stream_next_token(s
);
782 isl_stream_push_token(s
, tok
);
785 /* Push a token encapsulating "pa" onto "s", with the given
788 static isl_stat
push_aff(__isl_keep isl_stream
*s
, int line
, int col
,
789 __isl_take isl_pw_aff
*pa
)
791 struct isl_token
*tok
;
793 tok
= isl_token_new(s
->ctx
, line
, col
, 0);
796 tok
->type
= ISL_TOKEN_AFF
;
798 isl_stream_push_token(s
, tok
);
803 return isl_stat_error
;
806 /* Is the next token a comparison operator?
808 static int next_is_comparator(__isl_keep isl_stream
*s
)
811 struct isl_token
*tok
;
813 tok
= isl_stream_next_token(s
);
817 is_comp
= is_comparator(tok
);
818 isl_stream_push_token(s
, tok
);
823 /* Accept an affine expression that may involve ternary operators.
824 * We first read an affine expression.
825 * If it is not followed by a comparison operator, we simply return it.
826 * Otherwise, we assume the affine expression is part of the first
827 * argument of a ternary operator and try to parse that.
829 static __isl_give isl_pw_aff
*accept_extended_affine(__isl_keep isl_stream
*s
,
830 __isl_take isl_space
*space
, struct vars
*v
, int rational
)
834 int line
= -1, col
= -1;
836 set_current_line_col(s
, &line
, &col
);
838 pwaff
= accept_affine(s
, space
, v
);
840 pwaff
= isl_pw_aff_set_rational(pwaff
);
843 if (!next_is_comparator(s
))
846 space
= isl_pw_aff_get_domain_space(pwaff
);
847 cond
= isl_map_universe(isl_space_unwrap(space
));
849 if (push_aff(s
, line
, col
, pwaff
) < 0)
850 cond
= isl_map_free(cond
);
854 cond
= read_formula(s
, v
, cond
, rational
);
856 return accept_ternary(s
, cond
, v
, rational
);
859 static __isl_give isl_map
*read_var_def(__isl_keep isl_stream
*s
,
860 __isl_take isl_map
*map
, enum isl_dim_type type
, struct vars
*v
,
867 if (type
== isl_dim_param
)
868 pos
= isl_map_dim(map
, isl_dim_param
);
870 pos
= isl_map_dim(map
, isl_dim_in
);
871 if (type
== isl_dim_out
) {
872 isl_size n_out
= isl_map_dim(map
, isl_dim_out
);
873 if (pos
< 0 || n_out
< 0)
874 return isl_map_free(map
);
880 return isl_map_free(map
);
883 def
= accept_extended_affine(s
, isl_space_wrap(isl_map_get_space(map
)),
885 def_map
= isl_map_from_pw_aff(def
);
886 def_map
= isl_map_equate(def_map
, type
, pos
, isl_dim_out
, 0);
887 def_map
= isl_set_unwrap(isl_map_domain(def_map
));
889 map
= isl_map_intersect(map
, def_map
);
894 static __isl_give isl_pw_aff_list
*accept_affine_list(__isl_keep isl_stream
*s
,
895 __isl_take isl_space
*space
, struct vars
*v
)
898 isl_pw_aff_list
*list
;
899 struct isl_token
*tok
= NULL
;
901 pwaff
= accept_affine(s
, isl_space_copy(space
), v
);
902 list
= isl_pw_aff_list_from_pw_aff(pwaff
);
907 tok
= isl_stream_next_token(s
);
909 isl_stream_error(s
, NULL
, "unexpected EOF");
912 if (tok
->type
!= ',') {
913 isl_stream_push_token(s
, tok
);
918 pwaff
= accept_affine(s
, isl_space_copy(space
), v
);
919 list
= isl_pw_aff_list_concat(list
,
920 isl_pw_aff_list_from_pw_aff(pwaff
));
925 isl_space_free(space
);
928 isl_space_free(space
);
929 isl_pw_aff_list_free(list
);
933 static __isl_give isl_map
*read_defined_var_list(__isl_keep isl_stream
*s
,
934 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
936 struct isl_token
*tok
;
938 while ((tok
= isl_stream_next_token(s
)) != NULL
) {
942 if (tok
->type
!= ISL_TOKEN_IDENT
)
945 p
= vars_pos(v
, tok
->u
.s
, -1);
949 isl_stream_error(s
, tok
, "expecting unique identifier");
953 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
956 tok
= isl_stream_next_token(s
);
957 if (tok
&& tok
->type
== '=') {
959 map
= read_var_def(s
, map
, isl_dim_out
, v
, rational
);
960 tok
= isl_stream_next_token(s
);
963 if (!tok
|| tok
->type
!= ',')
969 isl_stream_push_token(s
, tok
);
978 static int next_is_tuple(__isl_keep isl_stream
*s
)
980 struct isl_token
*tok
;
983 tok
= isl_stream_next_token(s
);
986 if (tok
->type
== '[') {
987 isl_stream_push_token(s
, tok
);
990 if (tok
->type
!= ISL_TOKEN_IDENT
&& !tok
->is_keyword
) {
991 isl_stream_push_token(s
, tok
);
995 is_tuple
= isl_stream_next_token_is(s
, '[');
997 isl_stream_push_token(s
, tok
);
1002 /* Does the next token mark the end of a tuple element?
1004 static int next_is_end_tuple_element(__isl_keep isl_stream
*s
)
1006 return isl_stream_next_token_is(s
, ',') ||
1007 isl_stream_next_token_is(s
, ']');
1010 /* Is the next token one that necessarily forms the start of a condition?
1012 static int next_is_condition_start(__isl_keep isl_stream
*s
)
1014 return isl_stream_next_token_is(s
, ISL_TOKEN_EXISTS
) ||
1015 isl_stream_next_token_is(s
, ISL_TOKEN_NOT
) ||
1016 isl_stream_next_token_is(s
, ISL_TOKEN_TRUE
) ||
1017 isl_stream_next_token_is(s
, ISL_TOKEN_FALSE
) ||
1018 isl_stream_next_token_is(s
, ISL_TOKEN_MAP
);
1021 /* Is "pa" an expression in term of earlier dimensions?
1022 * The alternative is that the dimension is defined to be equal to itself,
1023 * meaning that it has a universe domain and an expression that depends
1024 * on itself. "i" is the position of the expression in a sequence
1025 * of "n" expressions. The final dimensions of "pa" correspond to
1026 * these "n" expressions.
1028 static isl_bool
pw_aff_is_expr(__isl_keep isl_pw_aff
*pa
, int i
, int n
)
1033 return isl_bool_error
;
1035 return isl_bool_true
;
1036 if (!isl_set_plain_is_universe(pa
->p
[0].set
))
1037 return isl_bool_true
;
1040 if (isl_int_is_zero(aff
->v
->el
[aff
->v
->size
- n
+ i
]))
1041 return isl_bool_true
;
1042 return isl_bool_false
;
1045 /* Does the tuple contain any dimensions that are defined
1046 * in terms of earlier dimensions?
1048 static isl_bool
tuple_has_expr(__isl_keep isl_multi_pw_aff
*tuple
)
1052 isl_bool has_expr
= isl_bool_false
;
1055 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
1057 return isl_bool_error
;
1058 for (i
= 0; i
< n
; ++i
) {
1059 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
1060 has_expr
= pw_aff_is_expr(pa
, i
, n
);
1061 isl_pw_aff_free(pa
);
1062 if (has_expr
< 0 || has_expr
)
1069 /* Set the name of dimension "pos" in "space" to "name".
1070 * During printing, we add primes if the same name appears more than once
1071 * to distinguish the occurrences. Here, we remove those primes from "name"
1072 * before setting the name of the dimension.
1074 static __isl_give isl_space
*space_set_dim_name(__isl_take isl_space
*space
,
1075 int pos
, char *name
)
1082 prime
= strchr(name
, '\'');
1085 space
= isl_space_set_dim_name(space
, isl_dim_out
, pos
, name
);
1092 /* Set the name of the last (output) dimension of "space" to "name",
1093 * ignoring any primes in "name".
1095 static __isl_give isl_space
*space_set_last_dim_name(
1096 __isl_take isl_space
*space
, char *name
)
1100 pos
= isl_space_dim(space
, isl_dim_out
);
1102 return isl_space_free(space
);
1103 return space_set_dim_name(space
, pos
- 1, name
);
1106 /* Construct an isl_pw_aff defined on a "space" (with v->n variables)
1107 * that is equal to the last of those variables.
1109 static __isl_give isl_pw_aff
*identity_tuple_el_on_space(
1110 __isl_take isl_space
*space
, struct vars
*v
)
1114 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
1115 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, v
->n
- 1, 1);
1116 return isl_pw_aff_from_aff(aff
);
1119 /* Construct an isl_pw_aff defined on the domain space of "pa"
1120 * that is equal to the last variable in "v".
1122 * That is, if D is the domain space of "pa", then construct
1126 static __isl_give isl_pw_aff
*init_range(__isl_keep isl_pw_aff
*pa
,
1131 space
= isl_pw_aff_get_domain_space(pa
);
1132 return identity_tuple_el_on_space(space
, v
);
1135 /* Impose the lower bound "lower" on the variable represented by "range_pa".
1137 * In particular, "range_pa" is of the form
1139 * D[..., i] -> i : C
1141 * with D also the domains space of "lower' and "C" some constraints.
1143 * Return the expression
1145 * D[..., i] -> i : C and i >= lower
1147 static __isl_give isl_pw_aff
*set_lower(__isl_take isl_pw_aff
*range_pa
,
1148 __isl_take isl_pw_aff
*lower
)
1152 range
= isl_pw_aff_ge_set(isl_pw_aff_copy(range_pa
), lower
);
1153 return isl_pw_aff_intersect_domain(range_pa
, range
);
1156 /* Impose the upper bound "upper" on the variable represented by "range_pa".
1158 * In particular, "range_pa" is of the form
1160 * D[..., i] -> i : C
1162 * with D also the domains space of "upper' and "C" some constraints.
1164 * Return the expression
1166 * D[..., i] -> i : C and i <= upper
1168 static __isl_give isl_pw_aff
*set_upper(__isl_take isl_pw_aff
*range_pa
,
1169 __isl_take isl_pw_aff
*upper
)
1173 range
= isl_pw_aff_le_set(isl_pw_aff_copy(range_pa
), upper
);
1174 return isl_pw_aff_intersect_domain(range_pa
, range
);
1177 /* Construct a piecewise affine expression corresponding
1178 * to the last variable in "v" that is greater than or equal to "pa".
1180 * In particular, if D is the domain space of "pa",
1181 * then construct the expression
1185 * impose lower bound "pa" and return
1187 * D[..., i] -> i : i >= pa
1189 static __isl_give isl_pw_aff
*construct_lower(__isl_take isl_pw_aff
*pa
,
1192 return set_lower(init_range(pa
, v
), pa
);
1195 /* Construct a piecewise affine expression corresponding
1196 * to the last variable in "v" that is smaller than or equal to "pa".
1198 * In particular, if D is the domain space of "pa",
1199 * then construct the expression
1203 * impose lower bound "pa" and return
1205 * D[..., i] -> i : i <= pa
1207 static __isl_give isl_pw_aff
*construct_upper(__isl_take isl_pw_aff
*pa
,
1210 return set_upper(init_range(pa
, v
), pa
);
1213 /* Construct a piecewise affine expression corresponding
1214 * to the last variable in "v" that ranges between "pa" and "pa2".
1216 * In particular, if D is the domain space of "pa" (and "pa2"),
1217 * then construct the expression
1221 * impose lower bound "pa" and upper bound "pa2" and return
1223 * D[..., i] -> i : pa <= i <= pa2
1225 static __isl_give isl_pw_aff
*construct_range(__isl_take isl_pw_aff
*pa
,
1226 __isl_take isl_pw_aff
*pa2
, struct vars
*v
)
1228 return set_upper(set_lower(init_range(pa
, v
), pa
), pa2
);
1231 static int resolve_paren_expr(__isl_keep isl_stream
*s
,
1232 struct vars
*v
, __isl_take isl_map
*map
, int rational
);
1234 /* Given that the (piecewise) affine expression "pa"
1235 * has just been parsed, followed by a colon,
1236 * continue parsing as part of a piecewise affine expression.
1238 * In particular, check if the colon is followed by a condition.
1239 * If so, parse the conditions(a) on "pa" and include them in the domain.
1240 * Otherwise, if the colon is followed by another (piecewise) affine expression
1241 * then consider the two expressions as endpoints of a range of values and
1242 * return a piecewise affine expression that takes values in that range.
1243 * Note that an affine expression followed by a comparison operator
1244 * is considered to be part of a condition.
1245 * If the colon is not followed by anything (inside the tuple element),
1246 * then consider "pa" as a lower bound on a range of values without upper bound
1247 * and return a piecewise affine expression that takes values in that range.
1249 static __isl_give isl_pw_aff
*update_piecewise_affine_colon(
1250 __isl_take isl_pw_aff
*pa
, __isl_keep isl_stream
*s
,
1251 struct vars
*v
, int rational
)
1253 isl_space
*dom_space
;
1256 dom_space
= isl_pw_aff_get_domain_space(pa
);
1257 map
= isl_map_universe(isl_space_from_domain(dom_space
));
1259 if (isl_stream_next_token_is(s
, '('))
1260 if (resolve_paren_expr(s
, v
, isl_map_copy(map
), rational
))
1262 if (next_is_end_tuple_element(s
)) {
1264 return construct_lower(pa
, v
);
1266 if (!next_is_condition_start(s
)) {
1267 int line
= -1, col
= -1;
1271 set_current_line_col(s
, &line
, &col
);
1272 space
= isl_space_wrap(isl_map_get_space(map
));
1273 pa2
= accept_affine(s
, space
, v
);
1275 pa2
= isl_pw_aff_set_rational(pa2
);
1276 if (!next_is_comparator(s
)) {
1278 pa2
= isl_pw_aff_domain_factor_domain(pa2
);
1279 return construct_range(pa
, pa2
, v
);
1281 if (push_aff(s
, line
, col
, pa2
) < 0)
1285 map
= read_formula(s
, v
, map
, rational
);
1286 pa
= isl_pw_aff_intersect_domain(pa
, isl_map_domain(map
));
1291 isl_pw_aff_free(pa
);
1295 /* Accept a piecewise affine expression.
1297 * At the outer level, the piecewise affine expression may be of the form
1299 * aff1 : condition1; aff2 : conditions2; ...
1312 * each of the affine expressions may in turn include ternary operators.
1314 * If the first token is a colon, then the expression must be
1315 * ":" or ": aff2", depending on whether anything follows the colon
1316 * inside the tuple element.
1317 * The first is considered to represent an arbitrary value.
1318 * The second is considered to represent a range of values
1319 * with the given upper bound and no lower bound.
1321 * There may be parentheses around some subexpression of "aff1"
1322 * around "aff1" itself, around "aff1 : condition1" and/or
1323 * around the entire piecewise affine expression.
1324 * We therefore remove the opening parenthesis (if any) from the stream
1325 * in case the closing parenthesis follows the colon, but if the closing
1326 * parenthesis is the first thing in the stream after the parsed affine
1327 * expression, we push the parsed expression onto the stream and parse
1328 * again in case the parentheses enclose some subexpression of "aff1".
1330 static __isl_give isl_pw_aff
*accept_piecewise_affine(__isl_keep isl_stream
*s
,
1331 __isl_take isl_space
*space
, struct vars
*v
, int rational
)
1334 isl_space
*res_space
;
1336 if (isl_stream_eat_if_available(s
, ':')) {
1337 if (next_is_end_tuple_element(s
))
1338 return identity_tuple_el_on_space(space
, v
);
1340 return construct_upper(accept_affine(s
, space
, v
), v
);
1343 res_space
= isl_space_from_domain(isl_space_copy(space
));
1344 res_space
= isl_space_add_dims(res_space
, isl_dim_out
, 1);
1345 res
= isl_pw_aff_empty(res_space
);
1349 int line
= -1, col
= -1;
1351 set_current_line_col(s
, &line
, &col
);
1352 seen_paren
= isl_stream_eat_if_available(s
, '(');
1354 pa
= accept_piecewise_affine(s
, isl_space_copy(space
),
1357 pa
= accept_extended_affine(s
, isl_space_copy(space
),
1359 if (seen_paren
&& isl_stream_eat_if_available(s
, ')')) {
1361 if (push_aff(s
, line
, col
, pa
) < 0)
1363 pa
= accept_extended_affine(s
, isl_space_copy(space
),
1366 if (pa
&& isl_stream_eat_if_available(s
, ':'))
1367 pa
= update_piecewise_affine_colon(pa
, s
, v
, rational
);
1369 res
= isl_pw_aff_union_add(res
, pa
);
1371 if (!res
|| (seen_paren
&& isl_stream_eat(s
, ')')))
1373 } while (isl_stream_eat_if_available(s
, ';'));
1375 isl_space_free(space
);
1379 isl_space_free(space
);
1380 return isl_pw_aff_free(res
);
1383 /* Read an affine expression from "s" for use in read_tuple.
1385 * accept_extended_affine requires a wrapped space as input.
1386 * read_tuple on the other hand expects each isl_pw_aff
1387 * to have an anonymous space. We therefore adjust the space
1388 * of the isl_pw_aff before returning it.
1390 static __isl_give isl_pw_aff
*read_tuple_var_def(__isl_keep isl_stream
*s
,
1391 struct vars
*v
, int rational
)
1396 space
= isl_space_wrap(isl_space_alloc(s
->ctx
, 0, v
->n
, 0));
1398 def
= accept_piecewise_affine(s
, space
, v
, rational
);
1399 def
= isl_pw_aff_domain_factor_domain(def
);
1404 /* Read a list of tuple elements by calling "read_el" on each of them and
1405 * return a space with the same number of set dimensions derived from
1406 * the parameter space "space" and possibly updated by "read_el".
1407 * The elements in the list are separated by either "," or "][".
1408 * If "comma" is set then only "," is allowed.
1410 static __isl_give isl_space
*read_tuple_list(__isl_keep isl_stream
*s
,
1411 struct vars
*v
, __isl_take isl_space
*space
, int rational
, int comma
,
1412 __isl_give isl_space
*(*read_el
)(__isl_keep isl_stream
*s
,
1413 struct vars
*v
, __isl_take isl_space
*space
, int rational
,
1420 space
= isl_space_set_from_params(space
);
1422 if (isl_stream_next_token_is(s
, ']'))
1426 struct isl_token
*tok
;
1428 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1430 space
= read_el(s
, v
, space
, rational
, user
);
1434 tok
= isl_stream_next_token(s
);
1435 if (!comma
&& tok
&& tok
->type
== ']' &&
1436 isl_stream_next_token_is(s
, '[')) {
1437 isl_token_free(tok
);
1438 tok
= isl_stream_next_token(s
);
1439 } else if (!tok
|| tok
->type
!= ',') {
1441 isl_stream_push_token(s
, tok
);
1445 isl_token_free(tok
);
1451 /* Read a tuple space from "s" derived from the parameter space "space".
1452 * Call "read_el" on each element in the tuples.
1454 static __isl_give isl_space
*read_tuple_space(__isl_keep isl_stream
*s
,
1455 struct vars
*v
, __isl_take isl_space
*space
, int rational
, int comma
,
1456 __isl_give isl_space
*(*read_el
)(__isl_keep isl_stream
*s
,
1457 struct vars
*v
, __isl_take isl_space
*space
, int rational
,
1461 struct isl_token
*tok
;
1463 isl_space
*res
= NULL
;
1465 tok
= isl_stream_next_token(s
);
1468 if (tok
->type
== ISL_TOKEN_IDENT
|| tok
->is_keyword
) {
1469 name
= strdup(tok
->u
.s
);
1470 isl_token_free(tok
);
1474 isl_stream_push_token(s
, tok
);
1475 if (isl_stream_eat(s
, '['))
1477 if (next_is_tuple(s
)) {
1479 res
= read_tuple_space(s
, v
, isl_space_copy(space
),
1480 rational
, comma
, read_el
, user
);
1481 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
1483 out
= read_tuple_space(s
, v
, isl_space_copy(space
),
1484 rational
, comma
, read_el
, user
);
1485 res
= isl_space_product(res
, out
);
1487 res
= read_tuple_list(s
, v
, isl_space_copy(space
),
1488 rational
, comma
, read_el
, user
);
1489 if (!res
|| isl_stream_eat(s
, ']'))
1493 res
= isl_space_set_tuple_name(res
, isl_dim_set
, name
);
1497 isl_space_free(space
);
1501 isl_space_free(res
);
1502 isl_space_free(space
);
1506 /* Construct an isl_pw_aff defined on a space with v->n variables
1507 * that is equal to the last of those variables.
1509 static __isl_give isl_pw_aff
*identity_tuple_el(struct vars
*v
)
1513 space
= isl_space_set_alloc(v
->ctx
, 0, v
->n
);
1514 return identity_tuple_el_on_space(space
, v
);
1517 /* This function is called for each element in a tuple inside read_tuple.
1518 * Add a new variable to "v" and construct a corresponding isl_pw_aff defined
1519 * over a space containing all variables in "v" defined so far.
1520 * The isl_pw_aff expresses the new variable in terms of earlier variables
1521 * if a definition is provided. Otherwise, it is represented as being
1523 * Add the isl_pw_aff to *list.
1524 * If the new variable was named, then adjust "space" accordingly and
1525 * return the updated space.
1527 static __isl_give isl_space
*read_tuple_pw_aff_el(__isl_keep isl_stream
*s
,
1528 struct vars
*v
, __isl_take isl_space
*space
, int rational
, void *user
)
1530 isl_pw_aff_list
**list
= (isl_pw_aff_list
**) user
;
1532 struct isl_token
*tok
;
1535 tok
= next_token(s
);
1537 isl_stream_error(s
, NULL
, "unexpected EOF");
1538 return isl_space_free(space
);
1541 if (tok
->type
== ISL_TOKEN_IDENT
) {
1543 int p
= vars_pos(v
, tok
->u
.s
, -1);
1549 if (tok
->type
== '*') {
1550 if (vars_add_anon(v
) < 0)
1552 isl_token_free(tok
);
1553 pa
= identity_tuple_el(v
);
1554 } else if (new_name
) {
1555 space
= space_set_last_dim_name(space
, v
->v
->name
);
1556 isl_token_free(tok
);
1557 if (isl_stream_eat_if_available(s
, '='))
1558 pa
= read_tuple_var_def(s
, v
, rational
);
1560 pa
= identity_tuple_el(v
);
1562 isl_stream_push_token(s
, tok
);
1564 if (vars_add_anon(v
) < 0)
1566 pa
= read_tuple_var_def(s
, v
, rational
);
1569 *list
= isl_pw_aff_list_add(*list
, pa
);
1571 return isl_space_free(space
);
1575 isl_token_free(tok
);
1576 return isl_space_free(space
);
1579 /* Read a tuple and represent it as an isl_multi_pw_aff.
1580 * The range space of the isl_multi_pw_aff is the space of the tuple.
1581 * The domain space is an anonymous space
1582 * with a dimension for each variable in the set of variables in "v",
1583 * including the variables in the range.
1584 * If a given dimension is not defined in terms of earlier dimensions in
1585 * the input, then the corresponding isl_pw_aff is set equal to one time
1586 * the variable corresponding to the dimension being defined.
1588 * The elements in the tuple are collected in a list by read_tuple_pw_aff_el.
1589 * Each element in this list is defined over a space representing
1590 * the variables defined so far. We need to adjust the earlier
1591 * elements to have as many variables in the domain as the final
1592 * element in the list.
1594 static __isl_give isl_multi_pw_aff
*read_tuple(__isl_keep isl_stream
*s
,
1595 struct vars
*v
, int rational
, int comma
)
1600 isl_pw_aff_list
*list
;
1602 space
= isl_space_params_alloc(v
->ctx
, 0);
1603 list
= isl_pw_aff_list_alloc(s
->ctx
, 0);
1604 space
= read_tuple_space(s
, v
, space
, rational
, comma
,
1605 &read_tuple_pw_aff_el
, &list
);
1606 n
= isl_space_dim(space
, isl_dim_set
);
1608 space
= isl_space_free(space
);
1609 for (i
= 0; i
+ 1 < n
; ++i
) {
1612 pa
= isl_pw_aff_list_get_pw_aff(list
, i
);
1613 pa
= isl_pw_aff_add_dims(pa
, isl_dim_in
, n
- (i
+ 1));
1614 list
= isl_pw_aff_list_set_pw_aff(list
, i
, pa
);
1617 space
= isl_space_from_range(space
);
1618 space
= isl_space_add_dims(space
, isl_dim_in
, v
->n
);
1619 return isl_multi_pw_aff_from_pw_aff_list(space
, list
);
1622 /* Add the tuple represented by the isl_multi_pw_aff "tuple" to "map".
1623 * We first create the appropriate space in "map" based on the range
1624 * space of this isl_multi_pw_aff. Then, we add equalities based
1625 * on the affine expressions. These live in an anonymous space,
1626 * however, so we first need to reset the space to that of "map".
1628 static __isl_give isl_map
*map_from_tuple(__isl_take isl_multi_pw_aff
*tuple
,
1629 __isl_take isl_map
*map
, enum isl_dim_type type
, struct vars
*v
,
1635 isl_space
*space
= NULL
;
1637 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
1640 ctx
= isl_multi_pw_aff_get_ctx(tuple
);
1641 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
1645 if (type
== isl_dim_param
) {
1646 if (isl_space_has_tuple_name(space
, isl_dim_set
) ||
1647 isl_space_is_wrapping(space
)) {
1648 isl_die(ctx
, isl_error_invalid
,
1649 "parameter tuples cannot be named or nested",
1652 map
= isl_map_add_dims(map
, type
, n
);
1653 for (i
= 0; i
< n
; ++i
) {
1655 if (!isl_space_has_dim_name(space
, isl_dim_set
, i
))
1656 isl_die(ctx
, isl_error_invalid
,
1657 "parameters must be named",
1659 id
= isl_space_get_dim_id(space
, isl_dim_set
, i
);
1660 map
= isl_map_set_dim_id(map
, isl_dim_param
, i
, id
);
1662 } else if (type
== isl_dim_in
) {
1665 set
= isl_set_universe(isl_space_copy(space
));
1667 set
= isl_set_set_rational(set
);
1668 set
= isl_set_intersect_params(set
, isl_map_params(map
));
1669 map
= isl_map_from_domain(set
);
1673 set
= isl_set_universe(isl_space_copy(space
));
1675 set
= isl_set_set_rational(set
);
1676 map
= isl_map_from_domain_and_range(isl_map_domain(map
), set
);
1679 for (i
= 0; i
< n
; ++i
) {
1686 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
1687 space
= isl_pw_aff_get_domain_space(pa
);
1688 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
1689 aff
= isl_aff_add_coefficient_si(aff
,
1690 isl_dim_in
, v
->n
- n
+ i
, -1);
1691 pa
= isl_pw_aff_add(pa
, isl_pw_aff_from_aff(aff
));
1693 pa
= isl_pw_aff_set_rational(pa
);
1694 set
= isl_pw_aff_zero_set(pa
);
1695 map_i
= isl_map_from_range(set
);
1696 map_i
= isl_map_reset_space(map_i
, isl_map_get_space(map
));
1697 map
= isl_map_intersect(map
, map_i
);
1700 isl_space_free(space
);
1701 isl_multi_pw_aff_free(tuple
);
1704 isl_space_free(space
);
1705 isl_multi_pw_aff_free(tuple
);
1710 /* Read a tuple from "s" and add it to "map".
1711 * The tuple is initially represented as an isl_multi_pw_aff and
1712 * then added to "map".
1714 static __isl_give isl_map
*read_map_tuple(__isl_keep isl_stream
*s
,
1715 __isl_take isl_map
*map
, enum isl_dim_type type
, struct vars
*v
,
1716 int rational
, int comma
)
1718 isl_multi_pw_aff
*tuple
;
1720 tuple
= read_tuple(s
, v
, rational
, comma
);
1722 return isl_map_free(map
);
1724 return map_from_tuple(tuple
, map
, type
, v
, rational
);
1727 /* Read the parameter domain of an expression from "s" (if any) and
1728 * check that it does not involve any constraints.
1729 * "v" contains a description of the identifiers parsed so far
1730 * (of which there should not be any at this point) and is extended
1733 static __isl_give isl_set
*read_universe_params(__isl_keep isl_stream
*s
,
1738 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
1739 if (next_is_tuple(s
)) {
1740 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
1741 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
1742 return isl_set_free(dom
);
1744 if (!isl_set_plain_is_universe(dom
))
1745 isl_die(s
->ctx
, isl_error_invalid
,
1746 "expecting universe parameter domain",
1747 return isl_set_free(dom
));
1752 /* This function is called for each element in a tuple inside read_space_tuples.
1753 * Add a new variable to "v" and adjust "space" accordingly
1754 * if the variable has a name.
1756 static __isl_give isl_space
*read_tuple_id(__isl_keep isl_stream
*s
,
1757 struct vars
*v
, __isl_take isl_space
*space
, int rational
, void *user
)
1759 struct isl_token
*tok
;
1761 tok
= next_token(s
);
1763 isl_stream_error(s
, NULL
, "unexpected EOF");
1764 return isl_space_free(space
);
1767 if (tok
->type
== ISL_TOKEN_IDENT
) {
1769 int p
= vars_pos(v
, tok
->u
.s
, -1);
1773 isl_stream_error(s
, tok
, "expecting fresh identifier");
1776 space
= space_set_last_dim_name(space
, v
->v
->name
);
1777 } else if (tok
->type
== '*') {
1778 if (vars_add_anon(v
) < 0)
1781 isl_stream_error(s
, tok
, "expecting identifier or '*'");
1785 isl_token_free(tok
);
1788 isl_token_free(tok
);
1789 return isl_space_free(space
);
1792 /* Given a parameter space "params", extend it with one or two tuples
1794 * "v" contains a description of the identifiers parsed so far and is extended
1797 static __isl_give isl_space
*read_space_tuples(__isl_keep isl_stream
*s
,
1798 struct vars
*v
, __isl_take isl_space
*params
)
1800 isl_space
*space
, *ran
;
1802 space
= read_tuple_space(s
, v
, isl_space_copy(params
), 1, 1,
1803 &read_tuple_id
, NULL
);
1804 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TO
)) {
1805 ran
= read_tuple_space(s
, v
, isl_space_copy(params
), 1, 1,
1806 &read_tuple_id
, NULL
);
1807 space
= isl_space_unwrap(isl_space_product(space
, ran
));
1809 isl_space_free(params
);
1814 /* Read an isl_space object from "s".
1816 * First read the parameters (if any).
1818 * Then check if the description is of the special form "{ : }",
1819 * in which case it represents a parameter space.
1820 * Otherwise, it has one or two tuples.
1822 __isl_give isl_space
*isl_stream_read_space(__isl_keep isl_stream
*s
)
1828 v
= vars_new(s
->ctx
);
1831 dom
= read_universe_params(s
, v
);
1832 space
= isl_set_get_space(dom
);
1835 if (isl_stream_eat(s
, '{'))
1838 if (!isl_stream_eat_if_available(s
, ':'))
1839 space
= read_space_tuples(s
, v
, space
);
1841 if (isl_stream_eat(s
, '}'))
1848 isl_space_free(space
);
1852 /* Read an isl_space object from "str".
1854 __isl_give isl_space
*isl_space_read_from_str(isl_ctx
*ctx
,
1857 struct isl_space
*space
;
1858 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
1861 space
= isl_stream_read_space(s
);
1866 /* Given two equal-length lists of piecewise affine expression with the space
1867 * of "set" as domain, construct a set in the same space that expresses
1868 * that "left" and "right" satisfy the comparison "type".
1870 * A space is constructed of the same dimension as the number of elements
1871 * in the two lists. The comparison is then expressed in a map from
1872 * this space to itself and wrapped into a set. Finally the two lists
1873 * of piecewise affine expressions are plugged into this set.
1875 * Let S be the space of "set" and T the constructed space.
1876 * The lists are first changed into two isl_multi_pw_affs in S -> T and
1877 * then combined into an isl_multi_pw_aff in S -> [T -> T],
1878 * while the comparison is first expressed in T -> T, then [T -> T]
1881 static __isl_give isl_set
*list_cmp(__isl_keep isl_set
*set
, int type
,
1882 __isl_take isl_pw_aff_list
*left
, __isl_take isl_pw_aff_list
*right
)
1886 isl_multi_pw_aff
*mpa1
, *mpa2
;
1888 n
= isl_pw_aff_list_n_pw_aff(left
);
1889 if (!set
|| n
< 0 || !right
)
1892 space
= isl_set_get_space(set
);
1893 space
= isl_space_from_domain(space
);
1894 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
1895 mpa1
= isl_multi_pw_aff_from_pw_aff_list(isl_space_copy(space
), left
);
1896 mpa2
= isl_multi_pw_aff_from_pw_aff_list(isl_space_copy(space
), right
);
1897 mpa1
= isl_multi_pw_aff_range_product(mpa1
, mpa2
);
1899 space
= isl_space_range(space
);
1901 case ISL_TOKEN_LEX_LT
:
1902 set
= isl_map_wrap(isl_map_lex_lt(space
));
1904 case ISL_TOKEN_LEX_GT
:
1905 set
= isl_map_wrap(isl_map_lex_gt(space
));
1907 case ISL_TOKEN_LEX_LE
:
1908 set
= isl_map_wrap(isl_map_lex_le(space
));
1910 case ISL_TOKEN_LEX_GE
:
1911 set
= isl_map_wrap(isl_map_lex_ge(space
));
1914 isl_multi_pw_aff_free(mpa1
);
1915 isl_space_free(space
);
1916 isl_die(isl_set_get_ctx(set
), isl_error_internal
,
1917 "unhandled list comparison type", return NULL
);
1919 set
= isl_set_preimage_multi_pw_aff(set
, mpa1
);
1922 isl_pw_aff_list_free(left
);
1923 isl_pw_aff_list_free(right
);
1927 /* Construct constraints of the form
1931 * where a is an element in "left", op is an operator of type "type" and
1932 * b is an element in "right", add the constraints to "set" and return
1934 * "rational" is set if the constraints should be treated as
1935 * a rational constraints.
1937 * If "type" is the type of a comparison operator between lists
1938 * of affine expressions, then a single (compound) constraint
1939 * is constructed by list_cmp instead.
1941 static __isl_give isl_set
*construct_constraints(
1942 __isl_take isl_set
*set
, int type
,
1943 __isl_keep isl_pw_aff_list
*left
, __isl_keep isl_pw_aff_list
*right
,
1948 left
= isl_pw_aff_list_copy(left
);
1949 right
= isl_pw_aff_list_copy(right
);
1951 left
= isl_pw_aff_list_set_rational(left
);
1952 right
= isl_pw_aff_list_set_rational(right
);
1954 if (is_list_comparator_type(type
))
1955 cond
= list_cmp(set
, type
, left
, right
);
1956 else if (type
== ISL_TOKEN_LE
)
1957 cond
= isl_pw_aff_list_le_set(left
, right
);
1958 else if (type
== ISL_TOKEN_GE
)
1959 cond
= isl_pw_aff_list_ge_set(left
, right
);
1960 else if (type
== ISL_TOKEN_LT
)
1961 cond
= isl_pw_aff_list_lt_set(left
, right
);
1962 else if (type
== ISL_TOKEN_GT
)
1963 cond
= isl_pw_aff_list_gt_set(left
, right
);
1964 else if (type
== ISL_TOKEN_NE
)
1965 cond
= isl_pw_aff_list_ne_set(left
, right
);
1967 cond
= isl_pw_aff_list_eq_set(left
, right
);
1969 return isl_set_intersect(set
, cond
);
1972 /* Read a constraint from "s", add it to "map" and return the result.
1973 * "v" contains a description of the identifiers parsed so far.
1974 * "rational" is set if the constraint should be treated as
1975 * a rational constraint.
1976 * The constraint read from "s" may be applied to multiple pairs
1977 * of affine expressions and may be chained.
1978 * In particular, a list of affine expressions is read, followed
1979 * by a comparison operator and another list of affine expressions.
1980 * The comparison operator is then applied to each pair of elements
1981 * in the two lists and the results are added to "map".
1982 * However, if the operator expects two lists of affine expressions,
1983 * then it is applied directly to those lists and the two lists
1984 * are required to have the same length.
1985 * If the next token is another comparison operator, then another
1986 * list of affine expressions is read and the process repeats.
1988 * The processing is performed on a wrapped copy of "map" because
1989 * an affine expression cannot have a binary relation as domain.
1991 static __isl_give isl_map
*add_constraint(__isl_keep isl_stream
*s
,
1992 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
1994 struct isl_token
*tok
;
1996 isl_pw_aff_list
*list1
= NULL
, *list2
= NULL
;
2000 set
= isl_map_wrap(map
);
2001 list1
= accept_affine_list(s
, isl_set_get_space(set
), v
);
2004 tok
= isl_stream_next_token(s
);
2005 if (!is_comparator(tok
)) {
2006 isl_stream_error(s
, tok
, "missing operator");
2008 isl_stream_push_token(s
, tok
);
2012 isl_token_free(tok
);
2014 list2
= accept_affine_list(s
, isl_set_get_space(set
), v
);
2015 n1
= isl_pw_aff_list_n_pw_aff(list1
);
2016 n2
= isl_pw_aff_list_n_pw_aff(list2
);
2017 if (n1
< 0 || n2
< 0)
2019 if (is_list_comparator_type(type
) && n1
!= n2
) {
2020 isl_stream_error(s
, NULL
,
2021 "list arguments not of same size");
2025 set
= construct_constraints(set
, type
, list1
, list2
, rational
);
2026 isl_pw_aff_list_free(list1
);
2029 if (!next_is_comparator(s
))
2031 tok
= isl_stream_next_token(s
);
2033 isl_token_free(tok
);
2035 isl_pw_aff_list_free(list1
);
2037 return isl_set_unwrap(set
);
2039 isl_pw_aff_list_free(list1
);
2040 isl_pw_aff_list_free(list2
);
2045 static __isl_give isl_map
*read_exists(__isl_keep isl_stream
*s
,
2046 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2049 int seen_paren
= isl_stream_eat_if_available(s
, '(');
2051 map
= isl_map_from_domain(isl_map_wrap(map
));
2052 map
= read_defined_var_list(s
, v
, map
, rational
);
2054 if (isl_stream_eat(s
, ':'))
2057 map
= read_formula(s
, v
, map
, rational
);
2058 map
= isl_set_unwrap(isl_map_domain(map
));
2060 vars_drop(v
, v
->n
- n
);
2061 if (seen_paren
&& isl_stream_eat(s
, ')'))
2070 /* Parse an expression between parentheses and push the result
2071 * back on the stream.
2073 * The parsed expression may be either an affine expression
2074 * or a condition. The first type is pushed onto the stream
2075 * as an isl_pw_aff, while the second is pushed as an isl_map.
2077 * If the initial token indicates the start of a condition,
2078 * we parse it as such.
2079 * Otherwise, we first parse an affine expression and push
2080 * that onto the stream. If the affine expression covers the
2081 * entire expression between parentheses, we return.
2082 * Otherwise, we assume that the affine expression is the
2083 * start of a condition and continue parsing.
2085 static int resolve_paren_expr(__isl_keep isl_stream
*s
,
2086 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2088 struct isl_token
*tok
, *tok2
;
2093 tok
= isl_stream_next_token(s
);
2094 if (!tok
|| tok
->type
!= '(')
2097 if (isl_stream_next_token_is(s
, '('))
2098 if (resolve_paren_expr(s
, v
, isl_map_copy(map
), rational
))
2101 if (next_is_condition_start(s
)) {
2102 map
= read_formula(s
, v
, map
, rational
);
2103 if (isl_stream_eat(s
, ')'))
2105 tok
->type
= ISL_TOKEN_MAP
;
2107 isl_stream_push_token(s
, tok
);
2111 tok2
= isl_stream_next_token(s
);
2116 isl_stream_push_token(s
, tok2
);
2118 pwaff
= accept_affine(s
, isl_space_wrap(isl_map_get_space(map
)), v
);
2122 has_paren
= isl_stream_eat_if_available(s
, ')');
2124 if (push_aff(s
, line
, col
, pwaff
) < 0)
2128 isl_token_free(tok
);
2133 map
= read_formula(s
, v
, map
, rational
);
2134 if (isl_stream_eat(s
, ')'))
2137 tok
->type
= ISL_TOKEN_MAP
;
2139 isl_stream_push_token(s
, tok
);
2143 isl_token_free(tok
);
2148 static __isl_give isl_map
*read_conjunct(__isl_keep isl_stream
*s
,
2149 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2151 if (isl_stream_next_token_is(s
, '('))
2152 if (resolve_paren_expr(s
, v
, isl_map_copy(map
), rational
))
2155 if (isl_stream_next_token_is(s
, ISL_TOKEN_MAP
)) {
2156 struct isl_token
*tok
;
2157 tok
= isl_stream_next_token(s
);
2161 map
= isl_map_copy(tok
->u
.map
);
2162 isl_token_free(tok
);
2166 if (isl_stream_eat_if_available(s
, ISL_TOKEN_EXISTS
))
2167 return read_exists(s
, v
, map
, rational
);
2169 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TRUE
))
2172 if (isl_stream_eat_if_available(s
, ISL_TOKEN_FALSE
)) {
2173 isl_space
*space
= isl_map_get_space(map
);
2175 return isl_map_empty(space
);
2178 return add_constraint(s
, v
, map
, rational
);
2184 static __isl_give isl_map
*read_conjuncts(__isl_keep isl_stream
*s
,
2185 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2190 negate
= isl_stream_eat_if_available(s
, ISL_TOKEN_NOT
);
2191 res
= read_conjunct(s
, v
, isl_map_copy(map
), rational
);
2193 res
= isl_map_subtract(isl_map_copy(map
), res
);
2195 while (res
&& isl_stream_eat_if_available(s
, ISL_TOKEN_AND
)) {
2198 negate
= isl_stream_eat_if_available(s
, ISL_TOKEN_NOT
);
2199 res_i
= read_conjunct(s
, v
, isl_map_copy(map
), rational
);
2201 res
= isl_map_subtract(res
, res_i
);
2203 res
= isl_map_intersect(res
, res_i
);
2210 static __isl_give isl_map
*read_disjuncts(__isl_keep isl_stream
*s
,
2211 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2215 if (isl_stream_next_token_is(s
, '}'))
2218 res
= read_conjuncts(s
, v
, isl_map_copy(map
), rational
);
2219 while (isl_stream_eat_if_available(s
, ISL_TOKEN_OR
)) {
2222 res_i
= read_conjuncts(s
, v
, isl_map_copy(map
), rational
);
2223 res
= isl_map_union(res
, res_i
);
2230 /* Read a first order formula from "s", add the corresponding
2231 * constraints to "map" and return the result.
2233 * In particular, read a formula of the form
2241 * where a and b are disjunctions.
2243 * In the first case, map is replaced by
2245 * map \cap { [..] : a }
2247 * In the second case, it is replaced by
2249 * (map \setminus { [..] : a}) \cup (map \cap { [..] : b })
2251 static __isl_give isl_map
*read_formula(__isl_keep isl_stream
*s
,
2252 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2256 res
= read_disjuncts(s
, v
, isl_map_copy(map
), rational
);
2258 if (isl_stream_eat_if_available(s
, ISL_TOKEN_IMPLIES
)) {
2261 res
= isl_map_subtract(isl_map_copy(map
), res
);
2262 res2
= read_disjuncts(s
, v
, map
, rational
);
2263 res
= isl_map_union(res
, res2
);
2270 static isl_size
polylib_pos_to_isl_pos(__isl_keep isl_basic_map
*bmap
, int pos
)
2272 isl_size n_out
, n_in
, n_param
, n_div
;
2274 n_param
= isl_basic_map_dim(bmap
, isl_dim_param
);
2275 n_in
= isl_basic_map_dim(bmap
, isl_dim_in
);
2276 n_out
= isl_basic_map_dim(bmap
, isl_dim_out
);
2277 n_div
= isl_basic_map_dim(bmap
, isl_dim_div
);
2278 if (n_param
< 0 || n_in
< 0 || n_out
< 0 || n_div
< 0)
2279 return isl_size_error
;
2282 return 1 + n_param
+ n_in
+ pos
;
2286 return 1 + n_param
+ pos
;
2290 return 1 + n_param
+ n_in
+ n_out
+ pos
;
2299 static __isl_give isl_basic_map
*basic_map_read_polylib_constraint(
2300 __isl_keep isl_stream
*s
, __isl_take isl_basic_map
*bmap
)
2303 struct isl_token
*tok
;
2312 tok
= isl_stream_next_token(s
);
2313 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2314 isl_stream_error(s
, tok
, "expecting coefficient");
2315 isl_token_free(tok
);
2318 if (!tok
->on_new_line
) {
2319 isl_stream_error(s
, tok
, "coefficient should appear on new line");
2320 isl_token_free(tok
);
2324 type
= isl_int_get_si(tok
->u
.v
);
2325 isl_token_free(tok
);
2327 isl_assert(s
->ctx
, type
== 0 || type
== 1, goto error
);
2329 k
= isl_basic_map_alloc_equality(bmap
);
2332 k
= isl_basic_map_alloc_inequality(bmap
);
2338 total
= isl_basic_map_dim(bmap
, isl_dim_all
);
2340 return isl_basic_map_free(bmap
);
2341 for (j
= 0; j
< 1 + total
; ++j
) {
2343 tok
= next_signed_value_on_same_line(s
,
2344 "expecting coefficient on same line");
2347 pos
= polylib_pos_to_isl_pos(bmap
, j
);
2349 isl_int_set(c
[pos
], tok
->u
.v
);
2350 isl_token_free(tok
);
2352 return isl_basic_map_free(bmap
);
2357 isl_basic_map_free(bmap
);
2361 static __isl_give isl_basic_map
*basic_map_read_polylib(
2362 __isl_keep isl_stream
*s
)
2365 struct isl_token
*tok
;
2366 struct isl_token
*tok2
;
2369 unsigned in
= 0, out
, local
= 0;
2370 struct isl_basic_map
*bmap
= NULL
;
2373 tok
= isl_stream_next_token(s
);
2375 isl_stream_error(s
, NULL
, "unexpected EOF");
2378 tok2
= isl_stream_next_token(s
);
2380 isl_token_free(tok
);
2381 isl_stream_error(s
, NULL
, "unexpected EOF");
2384 if (tok
->type
!= ISL_TOKEN_VALUE
|| tok2
->type
!= ISL_TOKEN_VALUE
) {
2385 isl_token_free(tok2
);
2386 isl_token_free(tok
);
2387 isl_stream_error(s
, NULL
,
2388 "expecting constraint matrix dimensions");
2391 n_row
= isl_int_get_si(tok
->u
.v
);
2392 n_col
= isl_int_get_si(tok2
->u
.v
);
2393 on_new_line
= tok2
->on_new_line
;
2394 isl_token_free(tok2
);
2395 isl_token_free(tok
);
2396 isl_assert(s
->ctx
, !on_new_line
, return NULL
);
2397 isl_assert(s
->ctx
, n_row
>= 0, return NULL
);
2398 isl_assert(s
->ctx
, n_col
>= 2 + nparam
, return NULL
);
2399 tok
= isl_stream_next_token_on_same_line(s
);
2401 if (tok
->type
!= ISL_TOKEN_VALUE
) {
2402 isl_stream_error(s
, tok
,
2403 "expecting number of output dimensions");
2404 isl_token_free(tok
);
2407 out
= isl_int_get_si(tok
->u
.v
);
2408 isl_token_free(tok
);
2410 tok
= isl_stream_next_token_on_same_line(s
);
2411 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2412 isl_stream_error(s
, tok
,
2413 "expecting number of input dimensions");
2414 isl_token_free(tok
);
2417 in
= isl_int_get_si(tok
->u
.v
);
2418 isl_token_free(tok
);
2420 tok
= isl_stream_next_token_on_same_line(s
);
2421 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2422 isl_stream_error(s
, tok
,
2423 "expecting number of existentials");
2424 isl_token_free(tok
);
2427 local
= isl_int_get_si(tok
->u
.v
);
2428 isl_token_free(tok
);
2430 tok
= isl_stream_next_token_on_same_line(s
);
2431 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2432 isl_stream_error(s
, tok
,
2433 "expecting number of parameters");
2434 isl_token_free(tok
);
2437 nparam
= isl_int_get_si(tok
->u
.v
);
2438 isl_token_free(tok
);
2439 if (n_col
!= 1 + out
+ in
+ local
+ nparam
+ 1) {
2440 isl_stream_error(s
, NULL
,
2441 "dimensions don't match");
2445 out
= n_col
- 2 - nparam
;
2446 bmap
= isl_basic_map_alloc(s
->ctx
, nparam
, in
, out
, local
, n_row
, n_row
);
2450 for (i
= 0; i
< local
; ++i
) {
2451 int k
= isl_basic_map_alloc_div(bmap
);
2454 isl_seq_clr(bmap
->div
[k
], 1 + 1 + nparam
+ in
+ out
+ local
);
2457 for (i
= 0; i
< n_row
; ++i
)
2458 bmap
= basic_map_read_polylib_constraint(s
, bmap
);
2463 tok
= isl_stream_next_token_on_same_line(s
);
2465 isl_stream_error(s
, tok
, "unexpected extra token on line");
2466 isl_token_free(tok
);
2470 bmap
= isl_basic_map_simplify(bmap
);
2471 bmap
= isl_basic_map_finalize(bmap
);
2474 isl_basic_map_free(bmap
);
2478 static __isl_give isl_map
*map_read_polylib(__isl_keep isl_stream
*s
)
2480 struct isl_token
*tok
;
2481 struct isl_token
*tok2
;
2483 struct isl_map
*map
;
2485 tok
= isl_stream_next_token(s
);
2487 isl_stream_error(s
, NULL
, "unexpected EOF");
2490 tok2
= isl_stream_next_token_on_same_line(s
);
2491 if (tok2
&& tok2
->type
== ISL_TOKEN_VALUE
) {
2492 isl_stream_push_token(s
, tok2
);
2493 isl_stream_push_token(s
, tok
);
2494 return isl_map_from_basic_map(basic_map_read_polylib(s
));
2497 isl_stream_error(s
, tok2
, "unexpected token");
2498 isl_stream_push_token(s
, tok2
);
2499 isl_stream_push_token(s
, tok
);
2502 n
= isl_int_get_si(tok
->u
.v
);
2503 isl_token_free(tok
);
2505 isl_assert(s
->ctx
, n
>= 1, return NULL
);
2507 map
= isl_map_from_basic_map(basic_map_read_polylib(s
));
2509 for (i
= 1; map
&& i
< n
; ++i
)
2510 map
= isl_map_union(map
,
2511 isl_map_from_basic_map(basic_map_read_polylib(s
)));
2516 static int optional_power(__isl_keep isl_stream
*s
)
2519 struct isl_token
*tok
;
2521 tok
= isl_stream_next_token(s
);
2524 if (tok
->type
!= '^') {
2525 isl_stream_push_token(s
, tok
);
2528 isl_token_free(tok
);
2529 tok
= isl_stream_next_token(s
);
2530 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2531 isl_stream_error(s
, tok
, "expecting exponent");
2533 isl_stream_push_token(s
, tok
);
2536 pow
= isl_int_get_si(tok
->u
.v
);
2537 isl_token_free(tok
);
2541 static __isl_give isl_pw_qpolynomial
*read_term(__isl_keep isl_stream
*s
,
2542 __isl_keep isl_map
*map
, struct vars
*v
);
2544 static __isl_give isl_pw_qpolynomial
*read_factor(__isl_keep isl_stream
*s
,
2545 __isl_keep isl_map
*map
, struct vars
*v
)
2547 isl_pw_qpolynomial
*pwqp
;
2548 struct isl_token
*tok
;
2550 tok
= next_token(s
);
2552 isl_stream_error(s
, NULL
, "unexpected EOF");
2555 if (tok
->type
== '(') {
2558 isl_token_free(tok
);
2559 pwqp
= read_term(s
, map
, v
);
2562 if (isl_stream_eat(s
, ')'))
2564 pow
= optional_power(s
);
2565 pwqp
= isl_pw_qpolynomial_pow(pwqp
, pow
);
2566 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
2567 struct isl_token
*tok2
;
2568 isl_qpolynomial
*qp
;
2570 tok2
= isl_stream_next_token(s
);
2571 if (tok2
&& tok2
->type
== '/') {
2572 isl_token_free(tok2
);
2573 tok2
= next_token(s
);
2574 if (!tok2
|| tok2
->type
!= ISL_TOKEN_VALUE
) {
2575 isl_stream_error(s
, tok2
, "expected denominator");
2576 isl_token_free(tok
);
2577 isl_token_free(tok2
);
2580 qp
= isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map
),
2581 tok
->u
.v
, tok2
->u
.v
);
2582 isl_token_free(tok2
);
2584 isl_stream_push_token(s
, tok2
);
2585 qp
= isl_qpolynomial_cst_on_domain(isl_map_get_space(map
),
2588 isl_token_free(tok
);
2589 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2590 } else if (tok
->type
== ISL_TOKEN_INFTY
) {
2591 isl_qpolynomial
*qp
;
2592 isl_token_free(tok
);
2593 qp
= isl_qpolynomial_infty_on_domain(isl_map_get_space(map
));
2594 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2595 } else if (tok
->type
== ISL_TOKEN_NAN
) {
2596 isl_qpolynomial
*qp
;
2597 isl_token_free(tok
);
2598 qp
= isl_qpolynomial_nan_on_domain(isl_map_get_space(map
));
2599 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2600 } else if (tok
->type
== ISL_TOKEN_IDENT
) {
2602 int pos
= vars_pos(v
, tok
->u
.s
, -1);
2604 isl_qpolynomial
*qp
;
2606 isl_token_free(tok
);
2610 vars_drop(v
, v
->n
- n
);
2611 isl_stream_error(s
, tok
, "unknown identifier");
2612 isl_token_free(tok
);
2615 isl_token_free(tok
);
2616 pow
= optional_power(s
);
2617 qp
= isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map
), pos
, pow
);
2618 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2619 } else if (is_start_of_div(tok
)) {
2623 isl_stream_push_token(s
, tok
);
2624 pwaff
= accept_div(s
, isl_map_get_space(map
), v
);
2625 pow
= optional_power(s
);
2626 pwqp
= isl_pw_qpolynomial_from_pw_aff(pwaff
);
2627 pwqp
= isl_pw_qpolynomial_pow(pwqp
, pow
);
2628 } else if (tok
->type
== '-') {
2629 isl_token_free(tok
);
2630 pwqp
= read_factor(s
, map
, v
);
2631 pwqp
= isl_pw_qpolynomial_neg(pwqp
);
2633 isl_stream_error(s
, tok
, "unexpected isl_token");
2634 isl_stream_push_token(s
, tok
);
2638 if (isl_stream_eat_if_available(s
, '*') ||
2639 isl_stream_next_token_is(s
, ISL_TOKEN_IDENT
)) {
2640 isl_pw_qpolynomial
*pwqp2
;
2642 pwqp2
= read_factor(s
, map
, v
);
2643 pwqp
= isl_pw_qpolynomial_mul(pwqp
, pwqp2
);
2648 isl_pw_qpolynomial_free(pwqp
);
2652 static __isl_give isl_pw_qpolynomial
*read_term(__isl_keep isl_stream
*s
,
2653 __isl_keep isl_map
*map
, struct vars
*v
)
2655 struct isl_token
*tok
;
2656 isl_pw_qpolynomial
*pwqp
;
2658 pwqp
= read_factor(s
, map
, v
);
2661 tok
= next_token(s
);
2665 if (tok
->type
== '+') {
2666 isl_pw_qpolynomial
*pwqp2
;
2668 isl_token_free(tok
);
2669 pwqp2
= read_factor(s
, map
, v
);
2670 pwqp
= isl_pw_qpolynomial_add(pwqp
, pwqp2
);
2671 } else if (tok
->type
== '-') {
2672 isl_pw_qpolynomial
*pwqp2
;
2674 isl_token_free(tok
);
2675 pwqp2
= read_factor(s
, map
, v
);
2676 pwqp
= isl_pw_qpolynomial_sub(pwqp
, pwqp2
);
2678 isl_stream_push_token(s
, tok
);
2686 static __isl_give isl_map
*read_optional_formula(__isl_keep isl_stream
*s
,
2687 __isl_take isl_map
*map
, struct vars
*v
, int rational
)
2689 struct isl_token
*tok
;
2691 tok
= isl_stream_next_token(s
);
2693 isl_stream_error(s
, NULL
, "unexpected EOF");
2696 if (tok
->type
== ':' ||
2697 (tok
->type
== ISL_TOKEN_OR
&& !strcmp(tok
->u
.s
, "|"))) {
2698 isl_token_free(tok
);
2699 map
= read_formula(s
, v
, map
, rational
);
2701 isl_stream_push_token(s
, tok
);
2709 static struct isl_obj
obj_read_poly(__isl_keep isl_stream
*s
,
2710 __isl_take isl_map
*map
, struct vars
*v
, int n
)
2712 struct isl_obj obj
= { isl_obj_pw_qpolynomial
, NULL
};
2713 isl_pw_qpolynomial
*pwqp
;
2714 struct isl_set
*set
;
2716 pwqp
= read_term(s
, map
, v
);
2717 map
= read_optional_formula(s
, map
, v
, 0);
2718 set
= isl_map_range(map
);
2720 pwqp
= isl_pw_qpolynomial_intersect_domain(pwqp
, set
);
2722 vars_drop(v
, v
->n
- n
);
2728 static struct isl_obj
obj_read_poly_or_fold(__isl_keep isl_stream
*s
,
2729 __isl_take isl_set
*set
, struct vars
*v
, int n
)
2732 struct isl_obj obj
= { isl_obj_pw_qpolynomial_fold
, NULL
};
2733 isl_pw_qpolynomial
*pwqp
;
2734 isl_pw_qpolynomial_fold
*pwf
= NULL
;
2737 max
= isl_stream_eat_if_available(s
, ISL_TOKEN_MAX
);
2738 min
= !max
&& isl_stream_eat_if_available(s
, ISL_TOKEN_MIN
);
2740 return obj_read_poly(s
, set
, v
, n
);
2741 fold
= max
? isl_fold_max
: isl_fold_min
;
2743 if (isl_stream_eat(s
, '('))
2746 pwqp
= read_term(s
, set
, v
);
2747 pwf
= isl_pw_qpolynomial_fold_from_pw_qpolynomial(fold
, pwqp
);
2749 while (isl_stream_eat_if_available(s
, ',')) {
2750 isl_pw_qpolynomial_fold
*pwf_i
;
2751 pwqp
= read_term(s
, set
, v
);
2752 pwf_i
= isl_pw_qpolynomial_fold_from_pw_qpolynomial(fold
, pwqp
);
2753 pwf
= isl_pw_qpolynomial_fold_fold(pwf
, pwf_i
);
2756 if (isl_stream_eat(s
, ')'))
2759 set
= read_optional_formula(s
, set
, v
, 0);
2760 pwf
= isl_pw_qpolynomial_fold_intersect_domain(pwf
, set
);
2762 vars_drop(v
, v
->n
- n
);
2768 isl_pw_qpolynomial_fold_free(pwf
);
2769 obj
.type
= isl_obj_none
;
2773 static int is_rational(__isl_keep isl_stream
*s
)
2775 struct isl_token
*tok
;
2777 tok
= isl_stream_next_token(s
);
2780 if (tok
->type
== ISL_TOKEN_RAT
&& isl_stream_next_token_is(s
, ':')) {
2781 isl_token_free(tok
);
2782 isl_stream_eat(s
, ':');
2786 isl_stream_push_token(s
, tok
);
2791 static struct isl_obj
obj_read_body(__isl_keep isl_stream
*s
,
2792 __isl_take isl_map
*map
, struct vars
*v
)
2794 struct isl_token
*tok
;
2795 struct isl_obj obj
= { isl_obj_set
, NULL
};
2799 rational
= is_rational(s
);
2801 map
= isl_map_set_rational(map
);
2803 if (isl_stream_next_token_is(s
, ':')) {
2804 obj
.type
= isl_obj_set
;
2805 obj
.v
= read_optional_formula(s
, map
, v
, rational
);
2809 if (!next_is_tuple(s
))
2810 return obj_read_poly_or_fold(s
, map
, v
, n
);
2812 map
= read_map_tuple(s
, map
, isl_dim_in
, v
, rational
, 0);
2815 tok
= isl_stream_next_token(s
);
2818 if (tok
->type
== ISL_TOKEN_TO
) {
2819 obj
.type
= isl_obj_map
;
2820 isl_token_free(tok
);
2821 if (!next_is_tuple(s
)) {
2822 isl_set
*set
= isl_map_domain(map
);
2823 return obj_read_poly_or_fold(s
, set
, v
, n
);
2825 map
= read_map_tuple(s
, map
, isl_dim_out
, v
, rational
, 0);
2829 map
= isl_map_domain(map
);
2830 isl_stream_push_token(s
, tok
);
2833 map
= read_optional_formula(s
, map
, v
, rational
);
2835 vars_drop(v
, v
->n
- n
);
2841 obj
.type
= isl_obj_none
;
2845 static struct isl_obj
to_union(isl_ctx
*ctx
, struct isl_obj obj
)
2847 if (obj
.type
== isl_obj_map
) {
2848 obj
.v
= isl_union_map_from_map(obj
.v
);
2849 obj
.type
= isl_obj_union_map
;
2850 } else if (obj
.type
== isl_obj_set
) {
2851 obj
.v
= isl_union_set_from_set(obj
.v
);
2852 obj
.type
= isl_obj_union_set
;
2853 } else if (obj
.type
== isl_obj_pw_qpolynomial
) {
2854 obj
.v
= isl_union_pw_qpolynomial_from_pw_qpolynomial(obj
.v
);
2855 obj
.type
= isl_obj_union_pw_qpolynomial
;
2856 } else if (obj
.type
== isl_obj_pw_qpolynomial_fold
) {
2857 obj
.v
= isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj
.v
);
2858 obj
.type
= isl_obj_union_pw_qpolynomial_fold
;
2860 isl_assert(ctx
, 0, goto error
);
2863 obj
.type
->free(obj
.v
);
2864 obj
.type
= isl_obj_none
;
2868 static struct isl_obj
obj_add(__isl_keep isl_stream
*s
,
2869 struct isl_obj obj1
, struct isl_obj obj2
)
2871 if (obj2
.type
== isl_obj_none
|| !obj2
.v
)
2873 if (obj1
.type
== isl_obj_set
&& obj2
.type
== isl_obj_union_set
)
2874 obj1
= to_union(s
->ctx
, obj1
);
2875 if (obj1
.type
== isl_obj_union_set
&& obj2
.type
== isl_obj_set
)
2876 obj2
= to_union(s
->ctx
, obj2
);
2877 if (obj1
.type
== isl_obj_map
&& obj2
.type
== isl_obj_union_map
)
2878 obj1
= to_union(s
->ctx
, obj1
);
2879 if (obj1
.type
== isl_obj_union_map
&& obj2
.type
== isl_obj_map
)
2880 obj2
= to_union(s
->ctx
, obj2
);
2881 if (obj1
.type
== isl_obj_pw_qpolynomial
&&
2882 obj2
.type
== isl_obj_union_pw_qpolynomial
)
2883 obj1
= to_union(s
->ctx
, obj1
);
2884 if (obj1
.type
== isl_obj_union_pw_qpolynomial
&&
2885 obj2
.type
== isl_obj_pw_qpolynomial
)
2886 obj2
= to_union(s
->ctx
, obj2
);
2887 if (obj1
.type
== isl_obj_pw_qpolynomial_fold
&&
2888 obj2
.type
== isl_obj_union_pw_qpolynomial_fold
)
2889 obj1
= to_union(s
->ctx
, obj1
);
2890 if (obj1
.type
== isl_obj_union_pw_qpolynomial_fold
&&
2891 obj2
.type
== isl_obj_pw_qpolynomial_fold
)
2892 obj2
= to_union(s
->ctx
, obj2
);
2893 if (obj1
.type
!= obj2
.type
) {
2894 isl_stream_error(s
, NULL
,
2895 "attempt to combine incompatible objects");
2898 if (!obj1
.type
->add
)
2899 isl_die(s
->ctx
, isl_error_internal
,
2900 "combination not supported on object type", goto error
);
2901 if (obj1
.type
== isl_obj_map
&& !isl_map_has_equal_space(obj1
.v
, obj2
.v
)) {
2902 obj1
= to_union(s
->ctx
, obj1
);
2903 obj2
= to_union(s
->ctx
, obj2
);
2905 if (obj1
.type
== isl_obj_set
&& !isl_set_has_equal_space(obj1
.v
, obj2
.v
)) {
2906 obj1
= to_union(s
->ctx
, obj1
);
2907 obj2
= to_union(s
->ctx
, obj2
);
2909 if (obj1
.type
== isl_obj_pw_qpolynomial
&&
2910 !isl_pw_qpolynomial_has_equal_space(obj1
.v
, obj2
.v
)) {
2911 obj1
= to_union(s
->ctx
, obj1
);
2912 obj2
= to_union(s
->ctx
, obj2
);
2914 if (obj1
.type
== isl_obj_pw_qpolynomial_fold
&&
2915 !isl_pw_qpolynomial_fold_has_equal_space(obj1
.v
, obj2
.v
)) {
2916 obj1
= to_union(s
->ctx
, obj1
);
2917 obj2
= to_union(s
->ctx
, obj2
);
2919 obj1
.v
= obj1
.type
->add(obj1
.v
, obj2
.v
);
2922 obj1
.type
->free(obj1
.v
);
2923 obj2
.type
->free(obj2
.v
);
2924 obj1
.type
= isl_obj_none
;
2929 /* Are the first two tokens on "s", "domain" (either as a string
2930 * or as an identifier) followed by ":"?
2932 static int next_is_domain_colon(__isl_keep isl_stream
*s
)
2934 struct isl_token
*tok
;
2938 tok
= isl_stream_next_token(s
);
2941 if (tok
->type
!= ISL_TOKEN_IDENT
&& tok
->type
!= ISL_TOKEN_STRING
) {
2942 isl_stream_push_token(s
, tok
);
2946 name
= isl_token_get_str(s
->ctx
, tok
);
2947 res
= !strcmp(name
, "domain") && isl_stream_next_token_is(s
, ':');
2950 isl_stream_push_token(s
, tok
);
2955 /* Do the first tokens on "s" look like a schedule?
2957 * The root of a schedule is always a domain node, so the first thing
2958 * we expect in the stream is a domain key, i.e., "domain" followed
2959 * by ":". If the schedule was printed in YAML flow style, then
2960 * we additionally expect a "{" to open the outer mapping.
2962 static int next_is_schedule(__isl_keep isl_stream
*s
)
2964 struct isl_token
*tok
;
2967 tok
= isl_stream_next_token(s
);
2970 if (tok
->type
!= '{') {
2971 isl_stream_push_token(s
, tok
);
2972 return next_is_domain_colon(s
);
2975 is_schedule
= next_is_domain_colon(s
);
2976 isl_stream_push_token(s
, tok
);
2981 /* Read an isl_schedule from "s" and store it in an isl_obj.
2983 static struct isl_obj
schedule_read(__isl_keep isl_stream
*s
)
2987 obj
.type
= isl_obj_schedule
;
2988 obj
.v
= isl_stream_read_schedule(s
);
2993 /* Read a disjunction of object bodies from "s".
2994 * That is, read the inside of the braces, but not the braces themselves.
2995 * "v" contains a description of the identifiers parsed so far.
2996 * "map" contains information about the parameters.
2998 static struct isl_obj
obj_read_disjuncts(__isl_keep isl_stream
*s
,
2999 struct vars
*v
, __isl_keep isl_map
*map
)
3001 struct isl_obj obj
= { isl_obj_set
, NULL
};
3003 if (isl_stream_next_token_is(s
, '}')) {
3004 obj
.type
= isl_obj_union_set
;
3005 obj
.v
= isl_union_set_empty(isl_map_get_space(map
));
3011 o
= obj_read_body(s
, isl_map_copy(map
), v
);
3015 obj
= obj_add(s
, obj
, o
);
3016 if (obj
.type
== isl_obj_none
|| !obj
.v
)
3018 if (!isl_stream_eat_if_available(s
, ';'))
3020 if (isl_stream_next_token_is(s
, '}'))
3027 static struct isl_obj
obj_read(__isl_keep isl_stream
*s
)
3029 isl_map
*map
= NULL
;
3030 struct isl_token
*tok
;
3031 struct vars
*v
= NULL
;
3032 struct isl_obj obj
= { isl_obj_set
, NULL
};
3034 if (next_is_schedule(s
))
3035 return schedule_read(s
);
3037 tok
= next_token(s
);
3039 isl_stream_error(s
, NULL
, "unexpected EOF");
3042 if (tok
->type
== ISL_TOKEN_VALUE
) {
3043 struct isl_token
*tok2
;
3044 struct isl_map
*map
;
3046 tok2
= isl_stream_next_token(s
);
3047 if (!tok2
|| tok2
->type
!= ISL_TOKEN_VALUE
||
3048 isl_int_is_neg(tok2
->u
.v
)) {
3050 isl_stream_push_token(s
, tok2
);
3051 obj
.type
= isl_obj_val
;
3052 obj
.v
= isl_val_int_from_isl_int(s
->ctx
, tok
->u
.v
);
3053 isl_token_free(tok
);
3056 isl_stream_push_token(s
, tok2
);
3057 isl_stream_push_token(s
, tok
);
3058 map
= map_read_polylib(s
);
3061 if (isl_map_may_be_set(map
))
3062 obj
.v
= isl_map_range(map
);
3064 obj
.type
= isl_obj_map
;
3069 v
= vars_new(s
->ctx
);
3071 isl_stream_push_token(s
, tok
);
3074 map
= isl_map_universe(isl_space_params_alloc(s
->ctx
, 0));
3075 if (tok
->type
== '[') {
3076 isl_stream_push_token(s
, tok
);
3077 map
= read_map_tuple(s
, map
, isl_dim_param
, v
, 0, 0);
3080 tok
= isl_stream_next_token(s
);
3081 if (!tok
|| tok
->type
!= ISL_TOKEN_TO
) {
3082 isl_stream_error(s
, tok
, "expecting '->'");
3084 isl_stream_push_token(s
, tok
);
3087 isl_token_free(tok
);
3088 tok
= isl_stream_next_token(s
);
3090 if (!tok
|| tok
->type
!= '{') {
3091 isl_stream_error(s
, tok
, "expecting '{'");
3093 isl_stream_push_token(s
, tok
);
3096 isl_token_free(tok
);
3098 tok
= isl_stream_next_token(s
);
3101 else if (tok
->type
== ISL_TOKEN_IDENT
&& !strcmp(tok
->u
.s
, "Sym")) {
3102 isl_token_free(tok
);
3103 if (isl_stream_eat(s
, '='))
3105 map
= read_map_tuple(s
, map
, isl_dim_param
, v
, 0, 1);
3109 isl_stream_push_token(s
, tok
);
3111 obj
= obj_read_disjuncts(s
, v
, map
);
3112 if (obj
.type
== isl_obj_none
|| !obj
.v
)
3115 tok
= isl_stream_next_token(s
);
3116 if (tok
&& tok
->type
== '}') {
3117 isl_token_free(tok
);
3119 isl_stream_error(s
, tok
, "unexpected isl_token");
3121 isl_token_free(tok
);
3131 obj
.type
->free(obj
.v
);
3138 struct isl_obj
isl_stream_read_obj(__isl_keep isl_stream
*s
)
3143 __isl_give isl_map
*isl_stream_read_map(__isl_keep isl_stream
*s
)
3149 isl_assert(s
->ctx
, obj
.type
== isl_obj_map
||
3150 obj
.type
== isl_obj_set
, goto error
);
3152 if (obj
.type
== isl_obj_set
)
3153 obj
.v
= isl_map_from_range(obj
.v
);
3157 obj
.type
->free(obj
.v
);
3161 __isl_give isl_set
*isl_stream_read_set(__isl_keep isl_stream
*s
)
3167 if (obj
.type
== isl_obj_map
&& isl_map_may_be_set(obj
.v
)) {
3168 obj
.v
= isl_map_range(obj
.v
);
3169 obj
.type
= isl_obj_set
;
3171 isl_assert(s
->ctx
, obj
.type
== isl_obj_set
, goto error
);
3176 obj
.type
->free(obj
.v
);
3180 __isl_give isl_union_map
*isl_stream_read_union_map(__isl_keep isl_stream
*s
)
3185 if (obj
.type
== isl_obj_map
) {
3186 obj
.type
= isl_obj_union_map
;
3187 obj
.v
= isl_union_map_from_map(obj
.v
);
3189 if (obj
.type
== isl_obj_set
) {
3190 obj
.type
= isl_obj_union_set
;
3191 obj
.v
= isl_union_set_from_set(obj
.v
);
3193 if (obj
.v
&& obj
.type
== isl_obj_union_set
&&
3194 isl_union_set_is_empty(obj
.v
))
3195 obj
.type
= isl_obj_union_map
;
3196 if (obj
.v
&& obj
.type
!= isl_obj_union_map
)
3197 isl_die(s
->ctx
, isl_error_invalid
, "invalid input", goto error
);
3201 obj
.type
->free(obj
.v
);
3205 /* Extract an isl_union_set from "obj".
3206 * This only works if the object was detected as either a set
3207 * (in which case it is converted to a union set) or a union set.
3209 static __isl_give isl_union_set
*extract_union_set(isl_ctx
*ctx
,
3212 if (obj
.type
== isl_obj_set
) {
3213 obj
.type
= isl_obj_union_set
;
3214 obj
.v
= isl_union_set_from_set(obj
.v
);
3217 isl_assert(ctx
, obj
.type
== isl_obj_union_set
, goto error
);
3221 obj
.type
->free(obj
.v
);
3225 /* Read an isl_union_set from "s".
3226 * First read a generic object and then try and extract
3227 * an isl_union_set from that.
3229 __isl_give isl_union_set
*isl_stream_read_union_set(__isl_keep isl_stream
*s
)
3234 return extract_union_set(s
->ctx
, obj
);
3237 static __isl_give isl_basic_map
*basic_map_read(__isl_keep isl_stream
*s
)
3240 struct isl_map
*map
;
3241 struct isl_basic_map
*bmap
;
3244 if (obj
.v
&& (obj
.type
!= isl_obj_map
&& obj
.type
!= isl_obj_set
))
3245 isl_die(s
->ctx
, isl_error_invalid
, "not a (basic) set or map",
3252 isl_die(s
->ctx
, isl_error_invalid
,
3253 "set or map description involves "
3254 "more than one disjunct", goto error
);
3257 bmap
= isl_basic_map_empty(isl_map_get_space(map
));
3259 bmap
= isl_basic_map_copy(map
->p
[0]);
3265 obj
.type
->free(obj
.v
);
3269 /* Read an isl_basic_set object from "s".
3271 __isl_give isl_basic_set
*isl_stream_read_basic_set(__isl_keep isl_stream
*s
)
3273 isl_basic_map
*bmap
;
3274 bmap
= basic_map_read(s
);
3277 if (!isl_basic_map_may_be_set(bmap
))
3278 isl_die(s
->ctx
, isl_error_invalid
,
3279 "input is not a set", goto error
);
3280 return isl_basic_map_range(bmap
);
3282 isl_basic_map_free(bmap
);
3286 __isl_give isl_basic_map
*isl_basic_map_read_from_file(isl_ctx
*ctx
,
3289 struct isl_basic_map
*bmap
;
3290 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3293 bmap
= basic_map_read(s
);
3298 __isl_give isl_basic_set
*isl_basic_set_read_from_file(isl_ctx
*ctx
,
3301 isl_basic_set
*bset
;
3302 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3305 bset
= isl_stream_read_basic_set(s
);
3310 __isl_give isl_basic_map
*isl_basic_map_read_from_str(isl_ctx
*ctx
,
3313 struct isl_basic_map
*bmap
;
3314 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3317 bmap
= basic_map_read(s
);
3322 __isl_give isl_basic_set
*isl_basic_set_read_from_str(isl_ctx
*ctx
,
3325 isl_basic_set
*bset
;
3326 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3329 bset
= isl_stream_read_basic_set(s
);
3334 __isl_give isl_map
*isl_map_read_from_file(struct isl_ctx
*ctx
,
3337 struct isl_map
*map
;
3338 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3341 map
= isl_stream_read_map(s
);
3346 __isl_give isl_map
*isl_map_read_from_str(struct isl_ctx
*ctx
,
3349 struct isl_map
*map
;
3350 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3353 map
= isl_stream_read_map(s
);
3358 __isl_give isl_set
*isl_set_read_from_file(struct isl_ctx
*ctx
,
3362 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3365 set
= isl_stream_read_set(s
);
3370 __isl_give isl_set
*isl_set_read_from_str(isl_ctx
*ctx
, const char *str
)
3373 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3376 set
= isl_stream_read_set(s
);
3381 __isl_give isl_union_map
*isl_union_map_read_from_file(isl_ctx
*ctx
,
3384 isl_union_map
*umap
;
3385 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3388 umap
= isl_stream_read_union_map(s
);
3393 __isl_give isl_union_map
*isl_union_map_read_from_str(struct isl_ctx
*ctx
,
3396 isl_union_map
*umap
;
3397 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3400 umap
= isl_stream_read_union_map(s
);
3405 __isl_give isl_union_set
*isl_union_set_read_from_file(isl_ctx
*ctx
,
3408 isl_union_set
*uset
;
3409 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3412 uset
= isl_stream_read_union_set(s
);
3417 __isl_give isl_union_set
*isl_union_set_read_from_str(struct isl_ctx
*ctx
,
3420 isl_union_set
*uset
;
3421 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3424 uset
= isl_stream_read_union_set(s
);
3429 static __isl_give isl_vec
*isl_vec_read_polylib(__isl_keep isl_stream
*s
)
3431 struct isl_vec
*vec
= NULL
;
3432 struct isl_token
*tok
;
3436 tok
= isl_stream_next_token(s
);
3437 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
3438 isl_stream_error(s
, tok
, "expecting vector length");
3442 size
= isl_int_get_si(tok
->u
.v
);
3443 isl_token_free(tok
);
3445 vec
= isl_vec_alloc(s
->ctx
, size
);
3447 for (j
= 0; j
< size
; ++j
) {
3448 tok
= next_signed_value(s
, "expecting constant value");
3451 isl_int_set(vec
->el
[j
], tok
->u
.v
);
3452 isl_token_free(tok
);
3457 isl_token_free(tok
);
3462 static __isl_give isl_vec
*vec_read(__isl_keep isl_stream
*s
)
3464 return isl_vec_read_polylib(s
);
3467 __isl_give isl_vec
*isl_vec_read_from_file(isl_ctx
*ctx
, FILE *input
)
3470 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3478 __isl_give isl_pw_qpolynomial
*isl_stream_read_pw_qpolynomial(
3479 __isl_keep isl_stream
*s
)
3485 isl_assert(s
->ctx
, obj
.type
== isl_obj_pw_qpolynomial
,
3490 obj
.type
->free(obj
.v
);
3494 __isl_give isl_pw_qpolynomial
*isl_pw_qpolynomial_read_from_str(isl_ctx
*ctx
,
3497 isl_pw_qpolynomial
*pwqp
;
3498 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3501 pwqp
= isl_stream_read_pw_qpolynomial(s
);
3506 __isl_give isl_pw_qpolynomial
*isl_pw_qpolynomial_read_from_file(isl_ctx
*ctx
,
3509 isl_pw_qpolynomial
*pwqp
;
3510 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3513 pwqp
= isl_stream_read_pw_qpolynomial(s
);
3518 /* Read an isl_pw_qpolynomial_fold from "s".
3519 * First read a generic object and
3520 * then check that it is an isl_pw_qpolynomial_fold.
3522 __isl_give isl_pw_qpolynomial_fold
*isl_stream_read_pw_qpolynomial_fold(
3523 __isl_keep isl_stream
*s
)
3528 if (obj
.v
&& obj
.type
!= isl_obj_pw_qpolynomial_fold
)
3529 isl_die(s
->ctx
, isl_error_invalid
, "invalid input", goto error
);
3533 obj
.type
->free(obj
.v
);
3537 /* Read an isl_pw_qpolynomial_fold from "str".
3539 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_read_from_str(
3540 isl_ctx
*ctx
, const char *str
)
3542 isl_pw_qpolynomial_fold
*pwqp
;
3545 s
= isl_stream_new_str(ctx
, str
);
3548 pwqp
= isl_stream_read_pw_qpolynomial_fold(s
);
3554 /* Is the next token an identifier not in "v"?
3556 static int next_is_fresh_ident(__isl_keep isl_stream
*s
, struct vars
*v
)
3560 struct isl_token
*tok
;
3562 tok
= isl_stream_next_token(s
);
3565 fresh
= tok
->type
== ISL_TOKEN_IDENT
&& vars_pos(v
, tok
->u
.s
, -1) >= n
;
3566 isl_stream_push_token(s
, tok
);
3568 vars_drop(v
, v
->n
- n
);
3573 /* First read the domain of the affine expression, which may be
3574 * a parameter space or a set.
3575 * The tricky part is that we don't know if the domain is a set or not,
3576 * so when we are trying to read the domain, we may actually be reading
3577 * the affine expression itself (defined on a parameter domains)
3578 * If the tuple we are reading is named, we assume it's the domain.
3579 * Also, if inside the tuple, the first thing we find is a nested tuple
3580 * or a new identifier, we again assume it's the domain.
3581 * Finally, if the tuple is empty, then it must be the domain
3582 * since it does not contain an affine expression.
3583 * Otherwise, we assume we are reading an affine expression.
3585 static __isl_give isl_set
*read_aff_domain(__isl_keep isl_stream
*s
,
3586 __isl_take isl_set
*dom
, struct vars
*v
)
3588 struct isl_token
*tok
, *tok2
;
3591 tok
= isl_stream_next_token(s
);
3592 if (tok
&& (tok
->type
== ISL_TOKEN_IDENT
|| tok
->is_keyword
)) {
3593 isl_stream_push_token(s
, tok
);
3594 return read_map_tuple(s
, dom
, isl_dim_set
, v
, 0, 0);
3596 if (!tok
|| tok
->type
!= '[') {
3597 isl_stream_error(s
, tok
, "expecting '['");
3600 tok2
= isl_stream_next_token(s
);
3601 is_empty
= tok2
&& tok2
->type
== ']';
3603 isl_stream_push_token(s
, tok2
);
3604 if (is_empty
|| next_is_tuple(s
) || next_is_fresh_ident(s
, v
)) {
3605 isl_stream_push_token(s
, tok
);
3606 dom
= read_map_tuple(s
, dom
, isl_dim_set
, v
, 0, 0);
3608 isl_stream_push_token(s
, tok
);
3613 isl_stream_push_token(s
, tok
);
3618 /* Read an affine expression from "s".
3620 __isl_give isl_aff
*isl_stream_read_aff(__isl_keep isl_stream
*s
)
3626 ma
= isl_stream_read_multi_aff(s
);
3627 dim
= isl_multi_aff_dim(ma
, isl_dim_out
);
3631 isl_die(s
->ctx
, isl_error_invalid
,
3632 "expecting single affine expression",
3635 aff
= isl_multi_aff_get_aff(ma
, 0);
3636 isl_multi_aff_free(ma
);
3639 isl_multi_aff_free(ma
);
3643 /* Read a piecewise affine expression from "s" with domain (space) "dom".
3645 static __isl_give isl_pw_aff
*read_pw_aff_with_dom(__isl_keep isl_stream
*s
,
3646 __isl_take isl_set
*dom
, struct vars
*v
)
3648 isl_pw_aff
*pwaff
= NULL
;
3650 if (!isl_set_is_params(dom
) && isl_stream_eat(s
, ISL_TOKEN_TO
))
3653 if (isl_stream_eat(s
, '['))
3656 pwaff
= accept_affine(s
, isl_set_get_space(dom
), v
);
3658 if (isl_stream_eat(s
, ']'))
3661 dom
= read_optional_formula(s
, dom
, v
, 0);
3662 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
3667 isl_pw_aff_free(pwaff
);
3671 __isl_give isl_pw_aff
*isl_stream_read_pw_aff(__isl_keep isl_stream
*s
)
3674 isl_set
*dom
= NULL
;
3676 isl_pw_aff
*pa
= NULL
;
3679 v
= vars_new(s
->ctx
);
3683 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
3684 if (next_is_tuple(s
)) {
3685 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
3686 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
3689 if (isl_stream_eat(s
, '{'))
3693 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
3694 pa
= read_pw_aff_with_dom(s
, aff_dom
, v
);
3695 vars_drop(v
, v
->n
- n
);
3697 while (isl_stream_eat_if_available(s
, ';')) {
3701 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
3702 pa_i
= read_pw_aff_with_dom(s
, aff_dom
, v
);
3703 vars_drop(v
, v
->n
- n
);
3705 pa
= isl_pw_aff_union_add(pa
, pa_i
);
3708 if (isl_stream_eat(s
, '}'))
3717 isl_pw_aff_free(pa
);
3721 __isl_give isl_aff
*isl_aff_read_from_str(isl_ctx
*ctx
, const char *str
)
3724 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3727 aff
= isl_stream_read_aff(s
);
3732 __isl_give isl_pw_aff
*isl_pw_aff_read_from_str(isl_ctx
*ctx
, const char *str
)
3735 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3738 pa
= isl_stream_read_pw_aff(s
);
3743 /* Extract an isl_multi_pw_aff with domain space "dom_space"
3744 * from a tuple "tuple" read by read_tuple.
3746 * Note that the function read_tuple accepts tuples where some output or
3747 * set dimensions are defined in terms of other output or set dimensions
3748 * since this function is also used to read maps. As a special case,
3749 * read_tuple also accepts dimensions that are defined in terms of themselves
3750 * (i.e., that are not defined).
3751 * These cases are not allowed when extracting an isl_multi_pw_aff so check
3752 * that the definitions of the output/set dimensions do not involve any
3753 * output/set dimensions.
3754 * Finally, drop the output dimensions from the domain of the result
3755 * of read_tuple (which is of the form [input, output] -> [output],
3756 * with anonymous domain) and reset the space.
3758 static __isl_give isl_multi_pw_aff
*extract_mpa_from_tuple(
3759 __isl_take isl_space
*dom_space
, __isl_keep isl_multi_pw_aff
*tuple
)
3764 isl_multi_pw_aff
*mpa
;
3766 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
3767 dim
= isl_space_dim(dom_space
, isl_dim_all
);
3768 if (n
< 0 || dim
< 0)
3769 dom_space
= isl_space_free(dom_space
);
3770 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
3771 space
= isl_space_align_params(space
, isl_space_copy(dom_space
));
3772 if (!isl_space_is_params(dom_space
))
3773 space
= isl_space_map_from_domain_and_range(
3774 isl_space_copy(dom_space
), space
);
3775 isl_space_free(dom_space
);
3776 mpa
= isl_multi_pw_aff_alloc(space
);
3778 for (i
= 0; i
< n
; ++i
) {
3780 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
3782 return isl_multi_pw_aff_free(mpa
);
3783 if (isl_pw_aff_involves_dims(pa
, isl_dim_in
, dim
, i
+ 1)) {
3784 isl_ctx
*ctx
= isl_pw_aff_get_ctx(pa
);
3785 isl_pw_aff_free(pa
);
3786 isl_die(ctx
, isl_error_invalid
,
3787 "not an affine expression",
3788 return isl_multi_pw_aff_free(mpa
));
3790 pa
= isl_pw_aff_drop_dims(pa
, isl_dim_in
, dim
, n
);
3791 space
= isl_multi_pw_aff_get_domain_space(mpa
);
3792 pa
= isl_pw_aff_reset_domain_space(pa
, space
);
3793 mpa
= isl_multi_pw_aff_set_pw_aff(mpa
, i
, pa
);
3799 /* Read a tuple of affine expressions, together with optional constraints
3800 * on the domain from "s". "dom" represents the initial constraints
3803 * The isl_multi_aff may live in either a set or a map space.
3804 * First read the first tuple and check if it is followed by a "->".
3805 * If so, convert the tuple into the domain of the isl_multi_pw_aff and
3806 * read in the next tuple. This tuple (or the first tuple if it was
3807 * not followed by a "->") is then converted into an isl_multi_pw_aff
3808 * through a call to extract_mpa_from_tuple.
3809 * The result is converted to an isl_pw_multi_aff and
3810 * its domain is intersected with the domain.
3812 * Note that the last tuple may introduce new identifiers,
3813 * but these cannot be referenced in the description of the domain.
3815 static __isl_give isl_pw_multi_aff
*read_conditional_multi_aff(
3816 __isl_keep isl_stream
*s
, __isl_take isl_set
*dom
, struct vars
*v
)
3818 isl_multi_pw_aff
*tuple
;
3819 isl_multi_pw_aff
*mpa
;
3820 isl_pw_multi_aff
*pma
;
3825 tuple
= read_tuple(s
, v
, 0, 0);
3828 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TO
)) {
3829 isl_map
*map
= map_from_tuple(tuple
, dom
, isl_dim_in
, v
, 0);
3830 dom
= isl_map_domain(map
);
3832 tuple
= read_tuple(s
, v
, 0, 0);
3836 mpa
= extract_mpa_from_tuple(isl_set_get_space(dom
), tuple
);
3837 isl_multi_pw_aff_free(tuple
);
3839 dom
= isl_set_free(dom
);
3841 vars_drop(v
, v
->n
- n_dom
);
3842 dom
= read_optional_formula(s
, dom
, v
, 0);
3844 vars_drop(v
, v
->n
- n
);
3846 pma
= isl_pw_multi_aff_from_multi_pw_aff(mpa
);
3847 pma
= isl_pw_multi_aff_intersect_domain(pma
, dom
);
3855 /* Read an isl_union_pw_multi_aff from "s".
3857 * In particular, first read the parameters and then read a sequence
3858 * of zero or more tuples of affine expressions with optional conditions and
3861 __isl_give isl_union_pw_multi_aff
*isl_stream_read_union_pw_multi_aff(
3862 __isl_keep isl_stream
*s
)
3866 isl_union_pw_multi_aff
*upma
= NULL
;
3868 v
= vars_new(s
->ctx
);
3872 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
3873 if (next_is_tuple(s
)) {
3874 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
3875 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
3878 if (isl_stream_eat(s
, '{'))
3881 upma
= isl_union_pw_multi_aff_empty(isl_set_get_space(dom
));
3884 isl_pw_multi_aff
*pma
;
3885 isl_union_pw_multi_aff
*upma2
;
3887 if (isl_stream_next_token_is(s
, '}'))
3890 pma
= read_conditional_multi_aff(s
, isl_set_copy(dom
), v
);
3891 upma2
= isl_union_pw_multi_aff_from_pw_multi_aff(pma
);
3892 upma
= isl_union_pw_multi_aff_union_add(upma
, upma2
);
3895 } while (isl_stream_eat_if_available(s
, ';'));
3897 if (isl_stream_eat(s
, '}'))
3904 isl_union_pw_multi_aff_free(upma
);
3910 /* Read an isl_pw_multi_aff from "s".
3912 * Read a more generic isl_union_pw_multi_aff first and
3913 * then check that the result lives in a single space.
3915 __isl_give isl_pw_multi_aff
*isl_stream_read_pw_multi_aff(
3916 __isl_keep isl_stream
*s
)
3918 isl_bool single_space
;
3919 isl_union_pw_multi_aff
*upma
;
3921 upma
= isl_stream_read_union_pw_multi_aff(s
);
3922 single_space
= isl_union_pw_multi_aff_isa_pw_multi_aff(upma
);
3923 if (single_space
< 0)
3924 upma
= isl_union_pw_multi_aff_free(upma
);
3925 else if (!single_space
)
3926 isl_die(s
->ctx
, isl_error_invalid
,
3927 "expecting expression in single space",
3928 upma
= isl_union_pw_multi_aff_free(upma
));
3929 return isl_union_pw_multi_aff_as_pw_multi_aff(upma
);
3932 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_read_from_str(isl_ctx
*ctx
,
3935 isl_pw_multi_aff
*pma
;
3936 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3939 pma
= isl_stream_read_pw_multi_aff(s
);
3944 /* Read an isl_union_pw_multi_aff from "str".
3946 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_read_from_str(
3947 isl_ctx
*ctx
, const char *str
)
3949 isl_union_pw_multi_aff
*upma
;
3950 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3953 upma
= isl_stream_read_union_pw_multi_aff(s
);
3958 /* Assuming "pa" represents a single affine expression defined on a universe
3959 * domain, extract this affine expression.
3961 static __isl_give isl_aff
*aff_from_pw_aff(__isl_take isl_pw_aff
*pa
)
3968 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
3969 "expecting single affine expression",
3971 if (!isl_set_plain_is_universe(pa
->p
[0].set
))
3972 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
3973 "expecting universe domain",
3976 aff
= isl_aff_copy(pa
->p
[0].aff
);
3977 isl_pw_aff_free(pa
);
3980 isl_pw_aff_free(pa
);
3987 #include <isl_multi_read_no_explicit_domain_templ.c>
3992 #include <isl_multi_read_no_explicit_domain_templ.c>
3994 /* Read a multi-affine expression from "s".
3995 * If the multi-affine expression has a domain, then the tuple
3996 * representing this domain cannot involve any affine expressions.
3997 * The tuple representing the actual expressions needs to consist
3998 * of only affine expressions. Moreover, these expressions can
3999 * only depend on parameters and input dimensions and not on other
4000 * output dimensions.
4002 __isl_give isl_multi_aff
*isl_stream_read_multi_aff(__isl_keep isl_stream
*s
)
4005 isl_set
*dom
= NULL
;
4006 isl_multi_pw_aff
*tuple
= NULL
;
4009 isl_space
*space
, *dom_space
;
4010 isl_multi_aff
*ma
= NULL
;
4012 v
= vars_new(s
->ctx
);
4016 dom
= read_universe_params(s
, v
);
4019 if (isl_stream_eat(s
, '{'))
4022 tuple
= read_tuple(s
, v
, 0, 0);
4025 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TO
)) {
4030 has_expr
= tuple_has_expr(tuple
);
4034 isl_die(s
->ctx
, isl_error_invalid
,
4035 "expecting universe domain", goto error
);
4036 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
4037 set
= isl_set_universe(space
);
4038 dom
= isl_set_intersect_params(set
, dom
);
4039 isl_multi_pw_aff_free(tuple
);
4040 tuple
= read_tuple(s
, v
, 0, 0);
4045 if (isl_stream_eat(s
, '}'))
4048 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
4049 dim
= isl_set_dim(dom
, isl_dim_all
);
4050 if (n
< 0 || dim
< 0)
4052 dom_space
= isl_set_get_space(dom
);
4053 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
4054 space
= isl_space_align_params(space
, isl_space_copy(dom_space
));
4055 if (!isl_space_is_params(dom_space
))
4056 space
= isl_space_map_from_domain_and_range(
4057 isl_space_copy(dom_space
), space
);
4058 isl_space_free(dom_space
);
4059 ma
= isl_multi_aff_alloc(space
);
4061 for (i
= 0; i
< n
; ++i
) {
4064 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
4065 aff
= aff_from_pw_aff(pa
);
4068 if (isl_aff_involves_dims(aff
, isl_dim_in
, dim
, i
+ 1)) {
4070 isl_die(s
->ctx
, isl_error_invalid
,
4071 "not an affine expression", goto error
);
4073 aff
= isl_aff_drop_dims(aff
, isl_dim_in
, dim
, n
);
4074 space
= isl_multi_aff_get_domain_space(ma
);
4075 aff
= isl_aff_reset_domain_space(aff
, space
);
4076 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
4079 isl_multi_pw_aff_free(tuple
);
4084 isl_multi_pw_aff_free(tuple
);
4087 isl_multi_aff_free(ma
);
4091 __isl_give isl_multi_aff
*isl_multi_aff_read_from_str(isl_ctx
*ctx
,
4094 isl_multi_aff
*maff
;
4095 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
4098 maff
= isl_stream_read_multi_aff(s
);
4103 /* Read an isl_multi_pw_aff from "s".
4105 * The input format is similar to that of map, except that any conditions
4106 * on the domains should be specified inside the tuple since each
4107 * piecewise affine expression may have a different domain.
4108 * However, additional, shared conditions can also be specified.
4109 * This is especially useful for setting the explicit domain
4110 * of a zero-dimensional isl_multi_pw_aff.
4112 * Since we do not know in advance if the isl_multi_pw_aff lives
4113 * in a set or a map space, we first read the first tuple and check
4114 * if it is followed by a "->". If so, we convert the tuple into
4115 * the domain of the isl_multi_pw_aff and read in the next tuple.
4116 * This tuple (or the first tuple if it was not followed by a "->")
4117 * is then converted into the isl_multi_pw_aff through a call
4118 * to extract_mpa_from_tuple and the domain of the result
4119 * is intersected with the domain.
4121 * Note that the last tuple may introduce new identifiers,
4122 * but these cannot be referenced in the description of the domain.
4124 __isl_give isl_multi_pw_aff
*isl_stream_read_multi_pw_aff(
4125 __isl_keep isl_stream
*s
)
4129 isl_set
*dom
= NULL
;
4130 isl_multi_pw_aff
*tuple
= NULL
;
4131 isl_multi_pw_aff
*mpa
= NULL
;
4133 v
= vars_new(s
->ctx
);
4137 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
4138 if (next_is_tuple(s
)) {
4139 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
4140 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
4143 if (isl_stream_eat(s
, '{'))
4147 tuple
= read_tuple(s
, v
, 0, 0);
4150 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TO
)) {
4151 isl_map
*map
= map_from_tuple(tuple
, dom
, isl_dim_in
, v
, 0);
4152 dom
= isl_map_domain(map
);
4154 tuple
= read_tuple(s
, v
, 0, 0);
4159 vars_drop(v
, v
->n
- n_dom
);
4160 if (isl_stream_eat_if_available(s
, ':'))
4161 dom
= read_formula(s
, v
, dom
, 0);
4163 if (isl_stream_eat(s
, '}'))
4166 mpa
= extract_mpa_from_tuple(isl_set_get_space(dom
), tuple
);
4168 isl_multi_pw_aff_free(tuple
);
4170 mpa
= isl_multi_pw_aff_intersect_domain(mpa
, dom
);
4173 isl_multi_pw_aff_free(tuple
);
4176 isl_multi_pw_aff_free(mpa
);
4180 /* Read an isl_multi_pw_aff from "str".
4182 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_read_from_str(isl_ctx
*ctx
,
4185 isl_multi_pw_aff
*mpa
;
4186 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
4189 mpa
= isl_stream_read_multi_pw_aff(s
);
4194 /* Read the body of an isl_union_pw_aff from "s" with parameter domain "dom".
4196 static __isl_give isl_union_pw_aff
*read_union_pw_aff_with_dom(
4197 __isl_keep isl_stream
*s
, __isl_take isl_set
*dom
, struct vars
*v
)
4200 isl_union_pw_aff
*upa
= NULL
;
4205 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
4206 pa
= read_pw_aff_with_dom(s
, aff_dom
, v
);
4207 vars_drop(v
, v
->n
- n
);
4209 upa
= isl_union_pw_aff_from_pw_aff(pa
);
4211 while (isl_stream_eat_if_available(s
, ';')) {
4213 isl_union_pw_aff
*upa_i
;
4216 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
4217 pa_i
= read_pw_aff_with_dom(s
, aff_dom
, v
);
4218 vars_drop(v
, v
->n
- n
);
4220 upa_i
= isl_union_pw_aff_from_pw_aff(pa_i
);
4221 upa
= isl_union_pw_aff_union_add(upa
, upa_i
);
4228 /* Read an isl_union_pw_aff from "s".
4230 * First check if there are any paramters, then read in the opening brace
4231 * and use read_union_pw_aff_with_dom to read in the body of
4232 * the isl_union_pw_aff. Finally, read the closing brace.
4234 __isl_give isl_union_pw_aff
*isl_stream_read_union_pw_aff(
4235 __isl_keep isl_stream
*s
)
4239 isl_union_pw_aff
*upa
= NULL
;
4241 v
= vars_new(s
->ctx
);
4245 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
4246 if (next_is_tuple(s
)) {
4247 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
4248 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
4251 if (isl_stream_eat(s
, '{'))
4254 upa
= read_union_pw_aff_with_dom(s
, isl_set_copy(dom
), v
);
4256 if (isl_stream_eat(s
, '}'))
4265 isl_union_pw_aff_free(upa
);
4269 /* Read an isl_union_pw_aff from "str".
4271 __isl_give isl_union_pw_aff
*isl_union_pw_aff_read_from_str(isl_ctx
*ctx
,
4274 isl_union_pw_aff
*upa
;
4275 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
4278 upa
= isl_stream_read_union_pw_aff(s
);
4283 /* This function is called for each element in a tuple inside
4284 * isl_stream_read_multi_union_pw_aff.
4286 * Read a '{', the union piecewise affine expression body and a '}' and
4287 * add the isl_union_pw_aff to *list.
4289 static __isl_give isl_space
*read_union_pw_aff_el(__isl_keep isl_stream
*s
,
4290 struct vars
*v
, __isl_take isl_space
*space
, int rational
, void *user
)
4293 isl_union_pw_aff
*upa
;
4294 isl_union_pw_aff_list
**list
= (isl_union_pw_aff_list
**) user
;
4296 dom
= isl_set_universe(isl_space_params(isl_space_copy(space
)));
4297 if (isl_stream_eat(s
, '{'))
4299 upa
= read_union_pw_aff_with_dom(s
, dom
, v
);
4300 *list
= isl_union_pw_aff_list_add(*list
, upa
);
4301 if (isl_stream_eat(s
, '}'))
4302 return isl_space_free(space
);
4304 return isl_space_free(space
);
4308 return isl_space_free(space
);
4311 /* Do the next tokens in "s" correspond to an empty tuple?
4312 * In particular, does the stream start with a '[', followed by a ']',
4313 * not followed by a "->"?
4315 static int next_is_empty_tuple(__isl_keep isl_stream
*s
)
4317 struct isl_token
*tok
, *tok2
, *tok3
;
4318 int is_empty_tuple
= 0;
4320 tok
= isl_stream_next_token(s
);
4323 if (tok
->type
!= '[') {
4324 isl_stream_push_token(s
, tok
);
4328 tok2
= isl_stream_next_token(s
);
4329 if (tok2
&& tok2
->type
== ']') {
4330 tok3
= isl_stream_next_token(s
);
4331 is_empty_tuple
= !tok
|| tok
->type
!= ISL_TOKEN_TO
;
4333 isl_stream_push_token(s
, tok3
);
4336 isl_stream_push_token(s
, tok2
);
4337 isl_stream_push_token(s
, tok
);
4339 return is_empty_tuple
;
4342 /* Do the next tokens in "s" correspond to a tuple of parameters?
4343 * In particular, does the stream start with a '[' that is not
4344 * followed by a '{' or a nested tuple?
4346 static int next_is_param_tuple(__isl_keep isl_stream
*s
)
4348 struct isl_token
*tok
, *tok2
;
4351 tok
= isl_stream_next_token(s
);
4354 if (tok
->type
!= '[' || next_is_tuple(s
)) {
4355 isl_stream_push_token(s
, tok
);
4359 tok2
= isl_stream_next_token(s
);
4360 is_tuple
= tok2
&& tok2
->type
!= '{';
4362 isl_stream_push_token(s
, tok2
);
4363 isl_stream_push_token(s
, tok
);
4368 /* Read the core of a body of an isl_multi_union_pw_aff from "s",
4369 * i.e., everything except the parameter specification and
4370 * without shared domain constraints.
4371 * "v" contains a description of the identifiers parsed so far.
4372 * The parameters, if any, are specified by "space".
4374 * The body is of the form
4376 * [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4378 * Read the tuple, collecting the individual isl_union_pw_aff
4379 * elements in a list and construct the result from the tuple space and
4382 static __isl_give isl_multi_union_pw_aff
*read_multi_union_pw_aff_body_core(
4383 __isl_keep isl_stream
*s
, struct vars
*v
, __isl_take isl_space
*space
)
4385 isl_union_pw_aff_list
*list
;
4386 isl_multi_union_pw_aff
*mupa
;
4388 list
= isl_union_pw_aff_list_alloc(s
->ctx
, 0);
4389 space
= read_tuple_space(s
, v
, space
, 1, 0,
4390 &read_union_pw_aff_el
, &list
);
4391 mupa
= isl_multi_union_pw_aff_from_union_pw_aff_list(space
, list
);
4396 /* Read the body of an isl_union_set from "s",
4397 * i.e., everything except the parameter specification.
4398 * "v" contains a description of the identifiers parsed so far.
4399 * The parameters, if any, are specified by "space".
4401 * First read a generic disjunction of object bodies and then try and extract
4402 * an isl_union_set from that.
4404 static __isl_give isl_union_set
*read_union_set_body(__isl_keep isl_stream
*s
,
4405 struct vars
*v
, __isl_take isl_space
*space
)
4407 struct isl_obj obj
= { isl_obj_set
, NULL
};
4410 map
= isl_set_universe(space
);
4411 if (isl_stream_eat(s
, '{') < 0)
4413 obj
= obj_read_disjuncts(s
, v
, map
);
4414 if (isl_stream_eat(s
, '}') < 0)
4418 return extract_union_set(s
->ctx
, obj
);
4420 obj
.type
->free(obj
.v
);
4425 /* Read the body of an isl_multi_union_pw_aff from "s",
4426 * i.e., everything except the parameter specification.
4427 * "v" contains a description of the identifiers parsed so far.
4428 * The parameters, if any, are specified by "space".
4430 * In particular, handle the special case with shared domain constraints.
4431 * These are specified as
4435 * and are especially useful for setting the explicit domain
4436 * of a zero-dimensional isl_multi_union_pw_aff.
4437 * The core isl_multi_union_pw_aff body ([...]) is read by
4438 * read_multi_union_pw_aff_body_core.
4440 static __isl_give isl_multi_union_pw_aff
*read_multi_union_pw_aff_body(
4441 __isl_keep isl_stream
*s
, struct vars
*v
, __isl_take isl_space
*space
)
4443 isl_multi_union_pw_aff
*mupa
;
4445 if (!isl_stream_next_token_is(s
, '('))
4446 return read_multi_union_pw_aff_body_core(s
, v
, space
);
4448 if (isl_stream_eat(s
, '(') < 0)
4450 mupa
= read_multi_union_pw_aff_body_core(s
, v
, isl_space_copy(space
));
4451 if (isl_stream_eat_if_available(s
, ':')) {
4454 dom
= read_union_set_body(s
, v
, space
);
4455 mupa
= isl_multi_union_pw_aff_intersect_domain(mupa
, dom
);
4457 isl_space_free(space
);
4459 if (isl_stream_eat(s
, ')') < 0)
4460 return isl_multi_union_pw_aff_free(mupa
);
4464 isl_space_free(space
);
4468 /* Read an isl_multi_union_pw_aff from "s".
4470 * The input has the form
4472 * [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4476 * [..] -> [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4478 * Additionally, a shared domain may be specified as
4484 * [..] -> ([..] : ...)
4486 * The first case is handled by the caller, the second case
4487 * is handled by read_multi_union_pw_aff_body.
4489 * We first check for the special case of an empty tuple "[]".
4490 * Then we check if there are any parameters.
4491 * Finally, read the tuple and construct the result.
4493 static __isl_give isl_multi_union_pw_aff
*read_multi_union_pw_aff_core(
4494 __isl_keep isl_stream
*s
)
4497 isl_set
*dom
= NULL
;
4499 isl_multi_union_pw_aff
*mupa
= NULL
;
4501 if (next_is_empty_tuple(s
)) {
4502 if (isl_stream_eat(s
, '['))
4504 if (isl_stream_eat(s
, ']'))
4506 space
= isl_space_set_alloc(s
->ctx
, 0, 0);
4507 return isl_multi_union_pw_aff_zero(space
);
4510 v
= vars_new(s
->ctx
);
4514 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
4515 if (next_is_param_tuple(s
)) {
4516 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
4517 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
4520 space
= isl_set_get_space(dom
);
4522 mupa
= read_multi_union_pw_aff_body(s
, v
, space
);
4530 isl_multi_union_pw_aff_free(mupa
);
4534 /* Read an isl_multi_union_pw_aff from "s".
4536 * In particular, handle the special case with shared domain constraints.
4537 * These are specified as
4541 * and are especially useful for setting the explicit domain
4542 * of a zero-dimensional isl_multi_union_pw_aff.
4543 * The core isl_multi_union_pw_aff ([...]) is read by
4544 * read_multi_union_pw_aff_core.
4546 __isl_give isl_multi_union_pw_aff
*isl_stream_read_multi_union_pw_aff(
4547 __isl_keep isl_stream
*s
)
4549 isl_multi_union_pw_aff
*mupa
;
4551 if (!isl_stream_next_token_is(s
, '('))
4552 return read_multi_union_pw_aff_core(s
);
4554 if (isl_stream_eat(s
, '(') < 0)
4556 mupa
= read_multi_union_pw_aff_core(s
);
4557 if (isl_stream_eat_if_available(s
, ':')) {
4560 dom
= isl_stream_read_union_set(s
);
4561 mupa
= isl_multi_union_pw_aff_intersect_domain(mupa
, dom
);
4563 if (isl_stream_eat(s
, ')') < 0)
4564 return isl_multi_union_pw_aff_free(mupa
);
4568 /* Read an isl_multi_union_pw_aff from "str".
4570 __isl_give isl_multi_union_pw_aff
*isl_multi_union_pw_aff_read_from_str(
4571 isl_ctx
*ctx
, const char *str
)
4573 isl_multi_union_pw_aff
*mupa
;
4574 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
4577 mupa
= isl_stream_read_multi_union_pw_aff(s
);
4582 __isl_give isl_union_pw_qpolynomial
*isl_stream_read_union_pw_qpolynomial(
4583 __isl_keep isl_stream
*s
)
4588 if (obj
.type
== isl_obj_pw_qpolynomial
) {
4589 obj
.type
= isl_obj_union_pw_qpolynomial
;
4590 obj
.v
= isl_union_pw_qpolynomial_from_pw_qpolynomial(obj
.v
);
4593 isl_assert(s
->ctx
, obj
.type
== isl_obj_union_pw_qpolynomial
,
4598 obj
.type
->free(obj
.v
);
4602 __isl_give isl_union_pw_qpolynomial
*isl_union_pw_qpolynomial_read_from_str(
4603 isl_ctx
*ctx
, const char *str
)
4605 isl_union_pw_qpolynomial
*upwqp
;
4606 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
4609 upwqp
= isl_stream_read_union_pw_qpolynomial(s
);