2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 * Copyright 2012-2013 Ecole Normale Superieure
5 * Copyright 2019 Cerebras Systems
7 * Use of this software is governed by the MIT license
9 * Written by Sven Verdoolaege, K.U.Leuven, Departement
10 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
11 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
12 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
13 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14 * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA
20 #include <isl_ctx_private.h>
21 #include <isl_map_private.h>
22 #include <isl_id_private.h>
25 #include <isl_stream_private.h>
27 #include "isl_polynomial_private.h"
28 #include <isl/union_set.h>
29 #include <isl/union_map.h>
30 #include <isl_mat_private.h>
31 #include <isl_aff_private.h>
32 #include <isl_vec_private.h>
34 #include <isl_val_private.h>
39 struct variable
*next
;
48 static struct vars
*vars_new(struct isl_ctx
*ctx
)
51 v
= isl_alloc_type(ctx
, struct vars
);
60 static void variable_free(struct variable
*var
)
63 struct variable
*next
= var
->next
;
70 static void vars_free(struct vars
*v
)
78 static void vars_drop(struct vars
*v
, int n
)
89 struct variable
*next
= var
->next
;
97 static struct variable
*variable_new(struct vars
*v
, const char *name
, int len
,
100 struct variable
*var
;
101 var
= isl_calloc_type(v
->ctx
, struct variable
);
104 var
->name
= strdup(name
);
105 var
->name
[len
] = '\0';
114 static int vars_pos(struct vars
*v
, const char *s
, int len
)
121 for (q
= v
->v
; q
; q
= q
->next
) {
122 if (strncmp(q
->name
, s
, len
) == 0 && q
->name
[len
] == '\0')
129 v
->v
= variable_new(v
, s
, len
, v
->n
);
137 static int vars_add_anon(struct vars
*v
)
139 v
->v
= variable_new(v
, "", 0, v
->n
);
148 /* Obtain next token, with some preprocessing.
149 * In particular, evaluate expressions of the form x^y,
150 * with x and y values.
152 static struct isl_token
*next_token(__isl_keep isl_stream
*s
)
154 struct isl_token
*tok
, *tok2
;
156 tok
= isl_stream_next_token(s
);
157 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
)
159 if (!isl_stream_eat_if_available(s
, '^'))
161 tok2
= isl_stream_next_token(s
);
162 if (!tok2
|| tok2
->type
!= ISL_TOKEN_VALUE
) {
163 isl_stream_error(s
, tok2
, "expecting constant value");
167 isl_int_pow_ui(tok
->u
.v
, tok
->u
.v
, isl_int_get_ui(tok2
->u
.v
));
169 isl_token_free(tok2
);
173 isl_token_free(tok2
);
177 /* Read an isl_val from "s".
179 * The following token sequences are recognized
182 * "-" "infty" -> -infty
187 * where n, d and v are integer constants.
189 __isl_give isl_val
*isl_stream_read_val(__isl_keep isl_stream
*s
)
191 struct isl_token
*tok
= NULL
;
192 struct isl_token
*tok2
= NULL
;
197 isl_stream_error(s
, NULL
, "unexpected EOF");
200 if (tok
->type
== ISL_TOKEN_INFTY
) {
202 return isl_val_infty(s
->ctx
);
204 if (tok
->type
== '-' &&
205 isl_stream_eat_if_available(s
, ISL_TOKEN_INFTY
)) {
207 return isl_val_neginfty(s
->ctx
);
209 if (tok
->type
== ISL_TOKEN_NAN
) {
211 return isl_val_nan(s
->ctx
);
213 if (tok
->type
!= ISL_TOKEN_VALUE
) {
214 isl_stream_error(s
, tok
, "expecting value");
218 if (isl_stream_eat_if_available(s
, '/')) {
219 tok2
= next_token(s
);
221 isl_stream_error(s
, NULL
, "unexpected EOF");
224 if (tok2
->type
!= ISL_TOKEN_VALUE
) {
225 isl_stream_error(s
, tok2
, "expecting value");
228 val
= isl_val_rat_from_isl_int(s
->ctx
, tok
->u
.v
, tok2
->u
.v
);
229 val
= isl_val_normalize(val
);
231 val
= isl_val_int_from_isl_int(s
->ctx
, tok
->u
.v
);
235 isl_token_free(tok2
);
239 isl_token_free(tok2
);
243 /* Read an isl_val from "str".
245 __isl_give isl_val
*isl_val_read_from_str(isl_ctx
*ctx
, const char *str
)
248 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
251 val
= isl_stream_read_val(s
);
256 /* Perform an integer division on *f and
257 * an integer value read from the stream.
259 static isl_stat
int_div_by_cst(__isl_keep isl_stream
*s
, isl_int
*f
)
261 struct isl_token
*tok
;
264 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
265 isl_stream_error(s
, tok
, "expecting constant value");
269 isl_int_fdiv_q(*f
, *f
, tok
->u
.v
);
276 return isl_stat_error
;
279 static isl_stat
accept_cst_factor(__isl_keep isl_stream
*s
, isl_int
*f
)
281 struct isl_token
*tok
;
284 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
285 isl_stream_error(s
, tok
, "expecting constant value");
289 isl_int_mul(*f
, *f
, tok
->u
.v
);
293 if (isl_stream_eat_if_available(s
, '*'))
294 return accept_cst_factor(s
, f
);
299 return isl_stat_error
;
302 /* Given an affine expression aff, return an affine expression
303 * for aff % d, with d the next token on the stream, which is
304 * assumed to be a constant.
306 * We introduce an integer division q = [aff/d] and the result
307 * is set to aff - d q.
309 static __isl_give isl_pw_aff
*affine_mod(__isl_keep isl_stream
*s
,
310 struct vars
*v
, __isl_take isl_pw_aff
*aff
)
312 struct isl_token
*tok
;
316 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
317 isl_stream_error(s
, tok
, "expecting constant value");
321 q
= isl_pw_aff_copy(aff
);
322 q
= isl_pw_aff_scale_down(q
, tok
->u
.v
);
323 q
= isl_pw_aff_floor(q
);
324 q
= isl_pw_aff_scale(q
, tok
->u
.v
);
326 aff
= isl_pw_aff_sub(aff
, q
);
331 isl_pw_aff_free(aff
);
336 static __isl_give isl_pw_aff
*accept_affine(__isl_keep isl_stream
*s
,
337 __isl_take isl_space
*space
, struct vars
*v
);
338 static __isl_give isl_pw_aff_list
*accept_affine_list(__isl_keep isl_stream
*s
,
339 __isl_take isl_space
*space
, struct vars
*v
);
341 static __isl_give isl_pw_aff
*accept_minmax(__isl_keep isl_stream
*s
,
342 __isl_take isl_space
*space
, struct vars
*v
)
344 struct isl_token
*tok
;
345 isl_pw_aff_list
*list
= NULL
;
348 tok
= isl_stream_next_token(s
);
351 min
= tok
->type
== ISL_TOKEN_MIN
;
354 if (isl_stream_eat(s
, '('))
357 list
= accept_affine_list(s
, isl_space_copy(space
), v
);
361 if (isl_stream_eat(s
, ')'))
364 isl_space_free(space
);
365 return min
? isl_pw_aff_list_min(list
) : isl_pw_aff_list_max(list
);
367 isl_space_free(space
);
368 isl_pw_aff_list_free(list
);
372 /* Is "tok" the start of an integer division?
374 static int is_start_of_div(struct isl_token
*tok
)
378 if (tok
->type
== '[')
380 if (tok
->type
== ISL_TOKEN_FLOOR
)
382 if (tok
->type
== ISL_TOKEN_CEIL
)
384 if (tok
->type
== ISL_TOKEN_FLOORD
)
386 if (tok
->type
== ISL_TOKEN_CEILD
)
391 /* Read an integer division from "s" and return it as an isl_pw_aff.
393 * The integer division can be of the form
395 * [<affine expression>]
396 * floor(<affine expression>)
397 * ceil(<affine expression>)
398 * floord(<affine expression>,<denominator>)
399 * ceild(<affine expression>,<denominator>)
401 static __isl_give isl_pw_aff
*accept_div(__isl_keep isl_stream
*s
,
402 __isl_take isl_space
*space
, struct vars
*v
)
404 struct isl_token
*tok
;
408 isl_pw_aff
*pwaff
= NULL
;
410 if (isl_stream_eat_if_available(s
, ISL_TOKEN_FLOORD
))
412 else if (isl_stream_eat_if_available(s
, ISL_TOKEN_CEILD
))
414 else if (isl_stream_eat_if_available(s
, ISL_TOKEN_FLOOR
))
416 else if (isl_stream_eat_if_available(s
, ISL_TOKEN_CEIL
))
419 if (isl_stream_eat(s
, '('))
422 if (isl_stream_eat(s
, '['))
426 pwaff
= accept_affine(s
, isl_space_copy(space
), v
);
429 if (isl_stream_eat(s
, ','))
435 if (tok
->type
!= ISL_TOKEN_VALUE
) {
436 isl_stream_error(s
, tok
, "expected denominator");
437 isl_stream_push_token(s
, tok
);
440 pwaff
= isl_pw_aff_scale_down(pwaff
, tok
->u
.v
);
445 pwaff
= isl_pw_aff_ceil(pwaff
);
447 pwaff
= isl_pw_aff_floor(pwaff
);
450 if (isl_stream_eat(s
, ')'))
453 if (isl_stream_eat(s
, ']'))
457 isl_space_free(space
);
460 isl_space_free(space
);
461 isl_pw_aff_free(pwaff
);
465 /* Divide "pa" by an integer constant read from the stream.
467 static __isl_give isl_pw_aff
*pw_aff_div_by_cst(__isl_keep isl_stream
*s
,
468 __isl_take isl_pw_aff
*pa
)
472 isl_int_set_si(f
, 1);
473 if (accept_cst_factor(s
, &f
) < 0)
474 pa
= isl_pw_aff_free(pa
);
475 pa
= isl_pw_aff_scale_down(pa
, f
);
481 static __isl_give isl_pw_aff
*accept_affine_factor(__isl_keep isl_stream
*s
,
482 __isl_take isl_space
*space
, struct vars
*v
)
484 struct isl_token
*tok
= NULL
;
485 isl_pw_aff
*res
= NULL
;
489 isl_stream_error(s
, NULL
, "unexpected EOF");
493 if (tok
->type
== ISL_TOKEN_AFF
) {
494 res
= isl_pw_aff_copy(tok
->u
.pwaff
);
496 } else if (tok
->type
== ISL_TOKEN_IDENT
) {
498 int pos
= vars_pos(v
, tok
->u
.s
, -1);
504 vars_drop(v
, v
->n
- n
);
505 isl_stream_error(s
, tok
, "unknown identifier");
509 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(isl_space_copy(space
)));
512 isl_int_set_si(aff
->v
->el
[2 + pos
], 1);
513 res
= isl_pw_aff_from_aff(aff
);
515 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
516 if (isl_stream_eat_if_available(s
, '*')) {
517 res
= accept_affine_factor(s
, isl_space_copy(space
), v
);
518 res
= isl_pw_aff_scale(res
, tok
->u
.v
);
522 ls
= isl_local_space_from_space(isl_space_copy(space
));
523 aff
= isl_aff_zero_on_domain(ls
);
524 aff
= isl_aff_add_constant(aff
, tok
->u
.v
);
525 res
= isl_pw_aff_from_aff(aff
);
528 } else if (tok
->type
== '(') {
531 res
= accept_affine(s
, isl_space_copy(space
), v
);
534 if (isl_stream_eat(s
, ')'))
536 } else if (is_start_of_div(tok
)) {
537 isl_stream_push_token(s
, tok
);
539 res
= accept_div(s
, isl_space_copy(space
), v
);
540 } else if (tok
->type
== ISL_TOKEN_MIN
|| tok
->type
== ISL_TOKEN_MAX
) {
541 isl_stream_push_token(s
, tok
);
543 res
= accept_minmax(s
, isl_space_copy(space
), v
);
545 isl_stream_error(s
, tok
, "expecting factor");
548 if (isl_stream_eat_if_available(s
, '%') ||
549 isl_stream_eat_if_available(s
, ISL_TOKEN_MOD
)) {
550 isl_space_free(space
);
551 return affine_mod(s
, v
, res
);
553 if (isl_stream_eat_if_available(s
, '*')) {
556 isl_int_set_si(f
, 1);
557 if (accept_cst_factor(s
, &f
) < 0) {
561 res
= isl_pw_aff_scale(res
, f
);
564 if (isl_stream_eat_if_available(s
, '/'))
565 res
= pw_aff_div_by_cst(s
, res
);
566 if (isl_stream_eat_if_available(s
, ISL_TOKEN_INT_DIV
))
567 res
= isl_pw_aff_floor(pw_aff_div_by_cst(s
, res
));
569 isl_space_free(space
);
574 isl_pw_aff_free(res
);
575 isl_space_free(space
);
579 static __isl_give isl_pw_aff
*add_cst(__isl_take isl_pw_aff
*pwaff
, isl_int v
)
584 space
= isl_pw_aff_get_domain_space(pwaff
);
585 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
586 aff
= isl_aff_add_constant(aff
, v
);
588 return isl_pw_aff_add(pwaff
, isl_pw_aff_from_aff(aff
));
591 /* Return a piecewise affine expression defined on the specified domain
592 * that represents NaN.
594 static __isl_give isl_pw_aff
*nan_on_domain(__isl_keep isl_space
*space
)
598 ls
= isl_local_space_from_space(isl_space_copy(space
));
599 return isl_pw_aff_nan_on_domain(ls
);
602 static __isl_give isl_pw_aff
*accept_affine(__isl_keep isl_stream
*s
,
603 __isl_take isl_space
*space
, struct vars
*v
)
605 struct isl_token
*tok
= NULL
;
610 ls
= isl_local_space_from_space(isl_space_copy(space
));
611 res
= isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls
));
618 isl_stream_error(s
, NULL
, "unexpected EOF");
621 if (tok
->type
== '-') {
626 if (tok
->type
== '(' || is_start_of_div(tok
) ||
627 tok
->type
== ISL_TOKEN_MIN
|| tok
->type
== ISL_TOKEN_MAX
||
628 tok
->type
== ISL_TOKEN_IDENT
||
629 tok
->type
== ISL_TOKEN_AFF
) {
631 isl_stream_push_token(s
, tok
);
633 term
= accept_affine_factor(s
,
634 isl_space_copy(space
), v
);
636 res
= isl_pw_aff_sub(res
, term
);
638 res
= isl_pw_aff_add(res
, term
);
642 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
644 isl_int_neg(tok
->u
.v
, tok
->u
.v
);
645 if (isl_stream_eat_if_available(s
, '*') ||
646 isl_stream_next_token_is(s
, ISL_TOKEN_IDENT
)) {
648 term
= accept_affine_factor(s
,
649 isl_space_copy(space
), v
);
650 term
= isl_pw_aff_scale(term
, tok
->u
.v
);
651 res
= isl_pw_aff_add(res
, term
);
655 if (isl_stream_eat_if_available(s
,
656 ISL_TOKEN_INT_DIV
) &&
657 int_div_by_cst(s
, &tok
->u
.v
) < 0)
659 res
= add_cst(res
, tok
->u
.v
);
662 } else if (tok
->type
== ISL_TOKEN_NAN
) {
663 res
= isl_pw_aff_add(res
, nan_on_domain(space
));
665 isl_stream_error(s
, tok
, "unexpected isl_token");
666 isl_stream_push_token(s
, tok
);
667 isl_pw_aff_free(res
);
668 isl_space_free(space
);
674 if (tok
&& tok
->type
== '-') {
677 } else if (tok
&& tok
->type
== '+') {
680 } else if (tok
&& tok
->type
== ISL_TOKEN_VALUE
&&
681 isl_int_is_neg(tok
->u
.v
)) {
682 isl_stream_push_token(s
, tok
);
685 isl_stream_push_token(s
, tok
);
690 isl_space_free(space
);
693 isl_space_free(space
);
695 isl_pw_aff_free(res
);
699 /* Is "type" the type of a comparison operator between lists
700 * of affine expressions?
702 static int is_list_comparator_type(int type
)
705 case ISL_TOKEN_LEX_LT
:
706 case ISL_TOKEN_LEX_GT
:
707 case ISL_TOKEN_LEX_LE
:
708 case ISL_TOKEN_LEX_GE
:
715 static int is_comparator(struct isl_token
*tok
)
719 if (is_list_comparator_type(tok
->type
))
735 static __isl_give isl_map
*read_formula(__isl_keep isl_stream
*s
,
736 struct vars
*v
, __isl_take isl_map
*map
, int rational
);
737 static __isl_give isl_pw_aff
*accept_extended_affine(__isl_keep isl_stream
*s
,
738 __isl_take isl_space
*space
, struct vars
*v
, int rational
);
740 /* Accept a ternary operator, given the first argument.
742 static __isl_give isl_pw_aff
*accept_ternary(__isl_keep isl_stream
*s
,
743 __isl_take isl_map
*cond
, struct vars
*v
, int rational
)
746 isl_pw_aff
*pwaff1
= NULL
, *pwaff2
= NULL
, *pa_cond
;
751 if (isl_stream_eat(s
, '?'))
754 space
= isl_space_wrap(isl_map_get_space(cond
));
755 pwaff1
= accept_extended_affine(s
, space
, v
, rational
);
759 if (isl_stream_eat(s
, ':'))
762 space
= isl_pw_aff_get_domain_space(pwaff1
);
763 pwaff2
= accept_extended_affine(s
, space
, v
, rational
);
767 pa_cond
= isl_set_indicator_function(isl_map_wrap(cond
));
768 return isl_pw_aff_cond(pa_cond
, pwaff1
, pwaff2
);
771 isl_pw_aff_free(pwaff1
);
772 isl_pw_aff_free(pwaff2
);
776 /* Set *line and *col to those of the next token, if any.
778 static void set_current_line_col(__isl_keep isl_stream
*s
, int *line
, int *col
)
780 struct isl_token
*tok
;
782 tok
= isl_stream_next_token(s
);
788 isl_stream_push_token(s
, tok
);
791 /* Push a token encapsulating "pa" onto "s", with the given
794 static isl_stat
push_aff(__isl_keep isl_stream
*s
, int line
, int col
,
795 __isl_take isl_pw_aff
*pa
)
797 struct isl_token
*tok
;
799 tok
= isl_token_new(s
->ctx
, line
, col
, 0);
802 tok
->type
= ISL_TOKEN_AFF
;
804 isl_stream_push_token(s
, tok
);
809 return isl_stat_error
;
812 /* Is the next token a comparison operator?
814 static int next_is_comparator(__isl_keep isl_stream
*s
)
817 struct isl_token
*tok
;
819 tok
= isl_stream_next_token(s
);
823 is_comp
= is_comparator(tok
);
824 isl_stream_push_token(s
, tok
);
829 /* Accept an affine expression that may involve ternary operators.
830 * We first read an affine expression.
831 * If it is not followed by a comparison operator, we simply return it.
832 * Otherwise, we assume the affine expression is part of the first
833 * argument of a ternary operator and try to parse that.
835 static __isl_give isl_pw_aff
*accept_extended_affine(__isl_keep isl_stream
*s
,
836 __isl_take isl_space
*space
, struct vars
*v
, int rational
)
840 int line
= -1, col
= -1;
842 set_current_line_col(s
, &line
, &col
);
844 pwaff
= accept_affine(s
, space
, v
);
846 pwaff
= isl_pw_aff_set_rational(pwaff
);
849 if (!next_is_comparator(s
))
852 space
= isl_pw_aff_get_domain_space(pwaff
);
853 cond
= isl_map_universe(isl_space_unwrap(space
));
855 if (push_aff(s
, line
, col
, pwaff
) < 0)
856 cond
= isl_map_free(cond
);
860 cond
= read_formula(s
, v
, cond
, rational
);
862 return accept_ternary(s
, cond
, v
, rational
);
865 static __isl_give isl_map
*read_var_def(__isl_keep isl_stream
*s
,
866 __isl_take isl_map
*map
, enum isl_dim_type type
, struct vars
*v
,
873 if (type
== isl_dim_param
)
874 pos
= isl_map_dim(map
, isl_dim_param
);
876 pos
= isl_map_dim(map
, isl_dim_in
);
877 if (type
== isl_dim_out
) {
878 isl_size n_out
= isl_map_dim(map
, isl_dim_out
);
879 if (pos
< 0 || n_out
< 0)
880 return isl_map_free(map
);
886 return isl_map_free(map
);
889 def
= accept_extended_affine(s
, isl_space_wrap(isl_map_get_space(map
)),
891 def_map
= isl_map_from_pw_aff(def
);
892 def_map
= isl_map_equate(def_map
, type
, pos
, isl_dim_out
, 0);
893 def_map
= isl_set_unwrap(isl_map_domain(def_map
));
895 map
= isl_map_intersect(map
, def_map
);
900 static __isl_give isl_pw_aff_list
*accept_affine_list(__isl_keep isl_stream
*s
,
901 __isl_take isl_space
*space
, struct vars
*v
)
904 isl_pw_aff_list
*list
;
905 struct isl_token
*tok
= NULL
;
907 pwaff
= accept_affine(s
, isl_space_copy(space
), v
);
908 list
= isl_pw_aff_list_from_pw_aff(pwaff
);
913 tok
= isl_stream_next_token(s
);
915 isl_stream_error(s
, NULL
, "unexpected EOF");
918 if (tok
->type
!= ',') {
919 isl_stream_push_token(s
, tok
);
924 pwaff
= accept_affine(s
, isl_space_copy(space
), v
);
925 list
= isl_pw_aff_list_concat(list
,
926 isl_pw_aff_list_from_pw_aff(pwaff
));
931 isl_space_free(space
);
934 isl_space_free(space
);
935 isl_pw_aff_list_free(list
);
939 static __isl_give isl_map
*read_defined_var_list(__isl_keep isl_stream
*s
,
940 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
942 struct isl_token
*tok
;
944 while ((tok
= isl_stream_next_token(s
)) != NULL
) {
948 if (tok
->type
!= ISL_TOKEN_IDENT
)
951 p
= vars_pos(v
, tok
->u
.s
, -1);
955 isl_stream_error(s
, tok
, "expecting unique identifier");
959 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
962 tok
= isl_stream_next_token(s
);
963 if (tok
&& tok
->type
== '=') {
965 map
= read_var_def(s
, map
, isl_dim_out
, v
, rational
);
966 tok
= isl_stream_next_token(s
);
969 if (!tok
|| tok
->type
!= ',')
975 isl_stream_push_token(s
, tok
);
984 static int next_is_tuple(__isl_keep isl_stream
*s
)
986 struct isl_token
*tok
;
989 tok
= isl_stream_next_token(s
);
992 if (tok
->type
== '[') {
993 isl_stream_push_token(s
, tok
);
996 if (tok
->type
!= ISL_TOKEN_IDENT
&& !tok
->is_keyword
) {
997 isl_stream_push_token(s
, tok
);
1001 is_tuple
= isl_stream_next_token_is(s
, '[');
1003 isl_stream_push_token(s
, tok
);
1008 /* Does the next token mark the end of a tuple element?
1010 static int next_is_end_tuple_element(__isl_keep isl_stream
*s
)
1012 return isl_stream_next_token_is(s
, ',') ||
1013 isl_stream_next_token_is(s
, ']');
1016 /* Is the next token one that necessarily forms the start of a condition?
1018 static int next_is_condition_start(__isl_keep isl_stream
*s
)
1020 return isl_stream_next_token_is(s
, ISL_TOKEN_EXISTS
) ||
1021 isl_stream_next_token_is(s
, ISL_TOKEN_NOT
) ||
1022 isl_stream_next_token_is(s
, ISL_TOKEN_TRUE
) ||
1023 isl_stream_next_token_is(s
, ISL_TOKEN_FALSE
) ||
1024 isl_stream_next_token_is(s
, ISL_TOKEN_MAP
);
1027 /* Is "pa" an expression in term of earlier dimensions?
1028 * The alternative is that the dimension is defined to be equal to itself,
1029 * meaning that it has a universe domain and an expression that depends
1030 * on itself. "i" is the position of the expression in a sequence
1031 * of "n" expressions. The final dimensions of "pa" correspond to
1032 * these "n" expressions.
1034 static isl_bool
pw_aff_is_expr(__isl_keep isl_pw_aff
*pa
, int i
, int n
)
1039 return isl_bool_error
;
1041 return isl_bool_true
;
1042 if (!isl_set_plain_is_universe(pa
->p
[0].set
))
1043 return isl_bool_true
;
1046 if (isl_int_is_zero(aff
->v
->el
[aff
->v
->size
- n
+ i
]))
1047 return isl_bool_true
;
1048 return isl_bool_false
;
1051 /* Does the tuple contain any dimensions that are defined
1052 * in terms of earlier dimensions?
1054 static isl_bool
tuple_has_expr(__isl_keep isl_multi_pw_aff
*tuple
)
1058 isl_bool has_expr
= isl_bool_false
;
1061 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
1063 return isl_bool_error
;
1064 for (i
= 0; i
< n
; ++i
) {
1065 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
1066 has_expr
= pw_aff_is_expr(pa
, i
, n
);
1067 isl_pw_aff_free(pa
);
1068 if (has_expr
< 0 || has_expr
)
1075 /* Set the name of dimension "pos" in "space" to "name".
1076 * During printing, we add primes if the same name appears more than once
1077 * to distinguish the occurrences. Here, we remove those primes from "name"
1078 * before setting the name of the dimension.
1080 static __isl_give isl_space
*space_set_dim_name(__isl_take isl_space
*space
,
1081 int pos
, char *name
)
1088 prime
= strchr(name
, '\'');
1091 space
= isl_space_set_dim_name(space
, isl_dim_out
, pos
, name
);
1098 /* Construct an isl_pw_aff defined on a "space" (with v->n variables)
1099 * that is equal to the last of those variables.
1101 static __isl_give isl_pw_aff
*identity_tuple_el_on_space(
1102 __isl_take isl_space
*space
, struct vars
*v
)
1106 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
1107 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, v
->n
- 1, 1);
1108 return isl_pw_aff_from_aff(aff
);
1111 /* Construct an isl_pw_aff defined on the domain space of "pa"
1112 * that is equal to the last variable in "v".
1114 * That is, if D is the domain space of "pa", then construct
1118 static __isl_give isl_pw_aff
*init_range(__isl_keep isl_pw_aff
*pa
,
1123 space
= isl_pw_aff_get_domain_space(pa
);
1124 return identity_tuple_el_on_space(space
, v
);
1127 /* Impose the lower bound "lower" on the variable represented by "range_pa".
1129 * In particular, "range_pa" is of the form
1131 * D[..., i] -> i : C
1133 * with D also the domains space of "lower' and "C" some constraints.
1135 * Return the expression
1137 * D[..., i] -> i : C and i >= lower
1139 static __isl_give isl_pw_aff
*set_lower(__isl_take isl_pw_aff
*range_pa
,
1140 __isl_take isl_pw_aff
*lower
)
1144 range
= isl_pw_aff_ge_set(isl_pw_aff_copy(range_pa
), lower
);
1145 return isl_pw_aff_intersect_domain(range_pa
, range
);
1148 /* Impose the upper bound "upper" on the variable represented by "range_pa".
1150 * In particular, "range_pa" is of the form
1152 * D[..., i] -> i : C
1154 * with D also the domains space of "upper' and "C" some constraints.
1156 * Return the expression
1158 * D[..., i] -> i : C and i <= upper
1160 static __isl_give isl_pw_aff
*set_upper(__isl_take isl_pw_aff
*range_pa
,
1161 __isl_take isl_pw_aff
*upper
)
1165 range
= isl_pw_aff_le_set(isl_pw_aff_copy(range_pa
), upper
);
1166 return isl_pw_aff_intersect_domain(range_pa
, range
);
1169 /* Construct a piecewise affine expression corresponding
1170 * to the last variable in "v" that is greater than or equal to "pa".
1172 * In particular, if D is the domain space of "pa",
1173 * then construct the expression
1177 * impose lower bound "pa" and return
1179 * D[..., i] -> i : i >= pa
1181 static __isl_give isl_pw_aff
*construct_lower(__isl_take isl_pw_aff
*pa
,
1184 return set_lower(init_range(pa
, v
), pa
);
1187 /* Construct a piecewise affine expression corresponding
1188 * to the last variable in "v" that is smaller than or equal to "pa".
1190 * In particular, if D is the domain space of "pa",
1191 * then construct the expression
1195 * impose lower bound "pa" and return
1197 * D[..., i] -> i : i <= pa
1199 static __isl_give isl_pw_aff
*construct_upper(__isl_take isl_pw_aff
*pa
,
1202 return set_upper(init_range(pa
, v
), pa
);
1205 /* Construct a piecewise affine expression corresponding
1206 * to the last variable in "v" that ranges between "pa" and "pa2".
1208 * In particular, if D is the domain space of "pa" (and "pa2"),
1209 * then construct the expression
1213 * impose lower bound "pa" and upper bound "pa2" and return
1215 * D[..., i] -> i : pa <= i <= pa2
1217 static __isl_give isl_pw_aff
*construct_range(__isl_take isl_pw_aff
*pa
,
1218 __isl_take isl_pw_aff
*pa2
, struct vars
*v
)
1220 return set_upper(set_lower(init_range(pa
, v
), pa
), pa2
);
1223 static int resolve_paren_expr(__isl_keep isl_stream
*s
,
1224 struct vars
*v
, __isl_take isl_map
*map
, int rational
);
1226 /* Given that the (piecewise) affine expression "pa"
1227 * has just been parsed, followed by a colon,
1228 * continue parsing as part of a piecewise affine expression.
1230 * In particular, check if the colon is followed by a condition.
1231 * If so, parse the conditions(a) on "pa" and include them in the domain.
1232 * Otherwise, if the colon is followed by another (piecewise) affine expression
1233 * then consider the two expressions as endpoints of a range of values and
1234 * return a piecewise affine expression that takes values in that range.
1235 * Note that an affine expression followed by a comparison operator
1236 * is considered to be part of a condition.
1237 * If the colon is not followed by anything (inside the tuple element),
1238 * then consider "pa" as a lower bound on a range of values without upper bound
1239 * and return a piecewise affine expression that takes values in that range.
1241 static __isl_give isl_pw_aff
*update_piecewise_affine_colon(
1242 __isl_take isl_pw_aff
*pa
, __isl_keep isl_stream
*s
,
1243 struct vars
*v
, int rational
)
1245 isl_space
*dom_space
;
1248 dom_space
= isl_pw_aff_get_domain_space(pa
);
1249 map
= isl_map_universe(isl_space_from_domain(dom_space
));
1251 if (isl_stream_next_token_is(s
, '('))
1252 if (resolve_paren_expr(s
, v
, isl_map_copy(map
), rational
))
1254 if (next_is_end_tuple_element(s
)) {
1256 return construct_lower(pa
, v
);
1258 if (!next_is_condition_start(s
)) {
1259 int line
= -1, col
= -1;
1263 set_current_line_col(s
, &line
, &col
);
1264 space
= isl_space_wrap(isl_map_get_space(map
));
1265 pa2
= accept_affine(s
, space
, v
);
1267 pa2
= isl_pw_aff_set_rational(pa2
);
1268 if (!next_is_comparator(s
)) {
1270 pa2
= isl_pw_aff_domain_factor_domain(pa2
);
1271 return construct_range(pa
, pa2
, v
);
1273 if (push_aff(s
, line
, col
, pa2
) < 0)
1277 map
= read_formula(s
, v
, map
, rational
);
1278 pa
= isl_pw_aff_intersect_domain(pa
, isl_map_domain(map
));
1283 isl_pw_aff_free(pa
);
1287 /* Accept a piecewise affine expression.
1289 * At the outer level, the piecewise affine expression may be of the form
1291 * aff1 : condition1; aff2 : conditions2; ...
1304 * each of the affine expressions may in turn include ternary operators.
1306 * If the first token is a colon, then the expression must be
1307 * ":" or ": aff2", depending on whether anything follows the colon
1308 * inside the tuple element.
1309 * The first is considered to represent an arbitrary value.
1310 * The second is considered to represent a range of values
1311 * with the given upper bound and no lower bound.
1313 * There may be parentheses around some subexpression of "aff1"
1314 * around "aff1" itself, around "aff1 : condition1" and/or
1315 * around the entire piecewise affine expression.
1316 * We therefore remove the opening parenthesis (if any) from the stream
1317 * in case the closing parenthesis follows the colon, but if the closing
1318 * parenthesis is the first thing in the stream after the parsed affine
1319 * expression, we push the parsed expression onto the stream and parse
1320 * again in case the parentheses enclose some subexpression of "aff1".
1322 static __isl_give isl_pw_aff
*accept_piecewise_affine(__isl_keep isl_stream
*s
,
1323 __isl_take isl_space
*space
, struct vars
*v
, int rational
)
1326 isl_space
*res_space
;
1328 if (isl_stream_eat_if_available(s
, ':')) {
1329 if (next_is_end_tuple_element(s
))
1330 return identity_tuple_el_on_space(space
, v
);
1332 return construct_upper(accept_affine(s
, space
, v
), v
);
1335 res_space
= isl_space_from_domain(isl_space_copy(space
));
1336 res_space
= isl_space_add_dims(res_space
, isl_dim_out
, 1);
1337 res
= isl_pw_aff_empty(res_space
);
1341 int line
= -1, col
= -1;
1343 set_current_line_col(s
, &line
, &col
);
1344 seen_paren
= isl_stream_eat_if_available(s
, '(');
1346 pa
= accept_piecewise_affine(s
, isl_space_copy(space
),
1349 pa
= accept_extended_affine(s
, isl_space_copy(space
),
1351 if (seen_paren
&& isl_stream_eat_if_available(s
, ')')) {
1353 if (push_aff(s
, line
, col
, pa
) < 0)
1355 pa
= accept_extended_affine(s
, isl_space_copy(space
),
1358 if (isl_stream_eat_if_available(s
, ':'))
1359 pa
= update_piecewise_affine_colon(pa
, s
, v
, rational
);
1361 res
= isl_pw_aff_union_add(res
, pa
);
1363 if (seen_paren
&& isl_stream_eat(s
, ')'))
1365 } while (isl_stream_eat_if_available(s
, ';'));
1367 isl_space_free(space
);
1371 isl_space_free(space
);
1372 return isl_pw_aff_free(res
);
1375 /* Read an affine expression from "s" for use in read_tuple.
1377 * accept_extended_affine requires a wrapped space as input.
1378 * read_tuple on the other hand expects each isl_pw_aff
1379 * to have an anonymous space. We therefore adjust the space
1380 * of the isl_pw_aff before returning it.
1382 static __isl_give isl_pw_aff
*read_tuple_var_def(__isl_keep isl_stream
*s
,
1383 struct vars
*v
, int rational
)
1388 space
= isl_space_wrap(isl_space_alloc(s
->ctx
, 0, v
->n
, 0));
1390 def
= accept_piecewise_affine(s
, space
, v
, rational
);
1391 def
= isl_pw_aff_domain_factor_domain(def
);
1396 /* Read a list of tuple elements by calling "read_el" on each of them and
1397 * return a space with the same number of set dimensions derived from
1398 * the parameter space "space" and possibly updated by "read_el".
1399 * The elements in the list are separated by either "," or "][".
1400 * If "comma" is set then only "," is allowed.
1402 static __isl_give isl_space
*read_tuple_list(__isl_keep isl_stream
*s
,
1403 struct vars
*v
, __isl_take isl_space
*space
, int rational
, int comma
,
1404 __isl_give isl_space
*(*read_el
)(__isl_keep isl_stream
*s
,
1405 struct vars
*v
, __isl_take isl_space
*space
, int rational
,
1412 space
= isl_space_set_from_params(space
);
1414 if (isl_stream_next_token_is(s
, ']'))
1418 struct isl_token
*tok
;
1420 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1422 space
= read_el(s
, v
, space
, rational
, user
);
1426 tok
= isl_stream_next_token(s
);
1427 if (!comma
&& tok
&& tok
->type
== ']' &&
1428 isl_stream_next_token_is(s
, '[')) {
1429 isl_token_free(tok
);
1430 tok
= isl_stream_next_token(s
);
1431 } else if (!tok
|| tok
->type
!= ',') {
1433 isl_stream_push_token(s
, tok
);
1437 isl_token_free(tok
);
1443 /* Read a tuple space from "s" derived from the parameter space "space".
1444 * Call "read_el" on each element in the tuples.
1446 static __isl_give isl_space
*read_tuple_space(__isl_keep isl_stream
*s
,
1447 struct vars
*v
, __isl_take isl_space
*space
, int rational
, int comma
,
1448 __isl_give isl_space
*(*read_el
)(__isl_keep isl_stream
*s
,
1449 struct vars
*v
, __isl_take isl_space
*space
, int rational
,
1453 struct isl_token
*tok
;
1455 isl_space
*res
= NULL
;
1457 tok
= isl_stream_next_token(s
);
1460 if (tok
->type
== ISL_TOKEN_IDENT
|| tok
->is_keyword
) {
1461 name
= strdup(tok
->u
.s
);
1462 isl_token_free(tok
);
1466 isl_stream_push_token(s
, tok
);
1467 if (isl_stream_eat(s
, '['))
1469 if (next_is_tuple(s
)) {
1471 res
= read_tuple_space(s
, v
, isl_space_copy(space
),
1472 rational
, comma
, read_el
, user
);
1473 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
1475 out
= read_tuple_space(s
, v
, isl_space_copy(space
),
1476 rational
, comma
, read_el
, user
);
1477 res
= isl_space_product(res
, out
);
1479 res
= read_tuple_list(s
, v
, isl_space_copy(space
),
1480 rational
, comma
, read_el
, user
);
1481 if (isl_stream_eat(s
, ']'))
1485 res
= isl_space_set_tuple_name(res
, isl_dim_set
, name
);
1489 isl_space_free(space
);
1493 isl_space_free(res
);
1494 isl_space_free(space
);
1498 /* Construct an isl_pw_aff defined on a space with v->n variables
1499 * that is equal to the last of those variables.
1501 static __isl_give isl_pw_aff
*identity_tuple_el(struct vars
*v
)
1505 space
= isl_space_set_alloc(v
->ctx
, 0, v
->n
);
1506 return identity_tuple_el_on_space(space
, v
);
1509 /* This function is called for each element in a tuple inside read_tuple.
1510 * Add a new variable to "v" and construct a corresponding isl_pw_aff defined
1511 * over a space containing all variables in "v" defined so far.
1512 * The isl_pw_aff expresses the new variable in terms of earlier variables
1513 * if a definition is provided. Otherwise, it is represented as being
1515 * Add the isl_pw_aff to *list.
1516 * If the new variable was named, then adjust "space" accordingly and
1517 * return the updated space.
1519 static __isl_give isl_space
*read_tuple_pw_aff_el(__isl_keep isl_stream
*s
,
1520 struct vars
*v
, __isl_take isl_space
*space
, int rational
, void *user
)
1522 isl_pw_aff_list
**list
= (isl_pw_aff_list
**) user
;
1524 struct isl_token
*tok
;
1527 tok
= next_token(s
);
1529 isl_stream_error(s
, NULL
, "unexpected EOF");
1530 return isl_space_free(space
);
1533 if (tok
->type
== ISL_TOKEN_IDENT
) {
1535 int p
= vars_pos(v
, tok
->u
.s
, -1);
1541 if (tok
->type
== '*') {
1542 if (vars_add_anon(v
) < 0)
1544 isl_token_free(tok
);
1545 pa
= identity_tuple_el(v
);
1546 } else if (new_name
) {
1547 isl_size pos
= isl_space_dim(space
, isl_dim_out
);
1551 space
= space_set_dim_name(space
, pos
, v
->v
->name
);
1552 isl_token_free(tok
);
1553 if (isl_stream_eat_if_available(s
, '='))
1554 pa
= read_tuple_var_def(s
, v
, rational
);
1556 pa
= identity_tuple_el(v
);
1558 isl_stream_push_token(s
, tok
);
1560 if (vars_add_anon(v
) < 0)
1562 pa
= read_tuple_var_def(s
, v
, rational
);
1565 *list
= isl_pw_aff_list_add(*list
, pa
);
1567 return isl_space_free(space
);
1571 isl_token_free(tok
);
1572 return isl_space_free(space
);
1575 /* Read a tuple and represent it as an isl_multi_pw_aff.
1576 * The range space of the isl_multi_pw_aff is the space of the tuple.
1577 * The domain space is an anonymous space
1578 * with a dimension for each variable in the set of variables in "v",
1579 * including the variables in the range.
1580 * If a given dimension is not defined in terms of earlier dimensions in
1581 * the input, then the corresponding isl_pw_aff is set equal to one time
1582 * the variable corresponding to the dimension being defined.
1584 * The elements in the tuple are collected in a list by read_tuple_pw_aff_el.
1585 * Each element in this list is defined over a space representing
1586 * the variables defined so far. We need to adjust the earlier
1587 * elements to have as many variables in the domain as the final
1588 * element in the list.
1590 static __isl_give isl_multi_pw_aff
*read_tuple(__isl_keep isl_stream
*s
,
1591 struct vars
*v
, int rational
, int comma
)
1596 isl_pw_aff_list
*list
;
1598 space
= isl_space_params_alloc(v
->ctx
, 0);
1599 list
= isl_pw_aff_list_alloc(s
->ctx
, 0);
1600 space
= read_tuple_space(s
, v
, space
, rational
, comma
,
1601 &read_tuple_pw_aff_el
, &list
);
1602 n
= isl_space_dim(space
, isl_dim_set
);
1604 space
= isl_space_free(space
);
1605 for (i
= 0; i
+ 1 < n
; ++i
) {
1608 pa
= isl_pw_aff_list_get_pw_aff(list
, i
);
1609 pa
= isl_pw_aff_add_dims(pa
, isl_dim_in
, n
- (i
+ 1));
1610 list
= isl_pw_aff_list_set_pw_aff(list
, i
, pa
);
1613 space
= isl_space_from_range(space
);
1614 space
= isl_space_add_dims(space
, isl_dim_in
, v
->n
);
1615 return isl_multi_pw_aff_from_pw_aff_list(space
, list
);
1618 /* Add the tuple represented by the isl_multi_pw_aff "tuple" to "map".
1619 * We first create the appropriate space in "map" based on the range
1620 * space of this isl_multi_pw_aff. Then, we add equalities based
1621 * on the affine expressions. These live in an anonymous space,
1622 * however, so we first need to reset the space to that of "map".
1624 static __isl_give isl_map
*map_from_tuple(__isl_take isl_multi_pw_aff
*tuple
,
1625 __isl_take isl_map
*map
, enum isl_dim_type type
, struct vars
*v
,
1631 isl_space
*space
= NULL
;
1633 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
1636 ctx
= isl_multi_pw_aff_get_ctx(tuple
);
1637 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
1641 if (type
== isl_dim_param
) {
1642 if (isl_space_has_tuple_name(space
, isl_dim_set
) ||
1643 isl_space_is_wrapping(space
)) {
1644 isl_die(ctx
, isl_error_invalid
,
1645 "parameter tuples cannot be named or nested",
1648 map
= isl_map_add_dims(map
, type
, n
);
1649 for (i
= 0; i
< n
; ++i
) {
1651 if (!isl_space_has_dim_name(space
, isl_dim_set
, i
))
1652 isl_die(ctx
, isl_error_invalid
,
1653 "parameters must be named",
1655 id
= isl_space_get_dim_id(space
, isl_dim_set
, i
);
1656 map
= isl_map_set_dim_id(map
, isl_dim_param
, i
, id
);
1658 } else if (type
== isl_dim_in
) {
1661 set
= isl_set_universe(isl_space_copy(space
));
1663 set
= isl_set_set_rational(set
);
1664 set
= isl_set_intersect_params(set
, isl_map_params(map
));
1665 map
= isl_map_from_domain(set
);
1669 set
= isl_set_universe(isl_space_copy(space
));
1671 set
= isl_set_set_rational(set
);
1672 map
= isl_map_from_domain_and_range(isl_map_domain(map
), set
);
1675 for (i
= 0; i
< n
; ++i
) {
1682 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
1683 space
= isl_pw_aff_get_domain_space(pa
);
1684 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
1685 aff
= isl_aff_add_coefficient_si(aff
,
1686 isl_dim_in
, v
->n
- n
+ i
, -1);
1687 pa
= isl_pw_aff_add(pa
, isl_pw_aff_from_aff(aff
));
1689 pa
= isl_pw_aff_set_rational(pa
);
1690 set
= isl_pw_aff_zero_set(pa
);
1691 map_i
= isl_map_from_range(set
);
1692 map_i
= isl_map_reset_space(map_i
, isl_map_get_space(map
));
1693 map
= isl_map_intersect(map
, map_i
);
1696 isl_space_free(space
);
1697 isl_multi_pw_aff_free(tuple
);
1700 isl_space_free(space
);
1701 isl_multi_pw_aff_free(tuple
);
1706 /* Read a tuple from "s" and add it to "map".
1707 * The tuple is initially represented as an isl_multi_pw_aff and
1708 * then added to "map".
1710 static __isl_give isl_map
*read_map_tuple(__isl_keep isl_stream
*s
,
1711 __isl_take isl_map
*map
, enum isl_dim_type type
, struct vars
*v
,
1712 int rational
, int comma
)
1714 isl_multi_pw_aff
*tuple
;
1716 tuple
= read_tuple(s
, v
, rational
, comma
);
1718 return isl_map_free(map
);
1720 return map_from_tuple(tuple
, map
, type
, v
, rational
);
1723 /* Given two equal-length lists of piecewise affine expression with the space
1724 * of "set" as domain, construct a set in the same space that expresses
1725 * that "left" and "right" satisfy the comparison "type".
1727 * A space is constructed of the same dimension as the number of elements
1728 * in the two lists. The comparison is then expressed in a map from
1729 * this space to itself and wrapped into a set. Finally the two lists
1730 * of piecewise affine expressions are plugged into this set.
1732 * Let S be the space of "set" and T the constructed space.
1733 * The lists are first changed into two isl_multi_pw_affs in S -> T and
1734 * then combined into an isl_multi_pw_aff in S -> [T -> T],
1735 * while the comparison is first expressed in T -> T, then [T -> T]
1738 static __isl_give isl_set
*list_cmp(__isl_keep isl_set
*set
, int type
,
1739 __isl_take isl_pw_aff_list
*left
, __isl_take isl_pw_aff_list
*right
)
1743 isl_multi_pw_aff
*mpa1
, *mpa2
;
1745 n
= isl_pw_aff_list_n_pw_aff(left
);
1746 if (!set
|| n
< 0 || !right
)
1749 space
= isl_set_get_space(set
);
1750 space
= isl_space_from_domain(space
);
1751 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
1752 mpa1
= isl_multi_pw_aff_from_pw_aff_list(isl_space_copy(space
), left
);
1753 mpa2
= isl_multi_pw_aff_from_pw_aff_list(isl_space_copy(space
), right
);
1754 mpa1
= isl_multi_pw_aff_range_product(mpa1
, mpa2
);
1756 space
= isl_space_range(space
);
1758 case ISL_TOKEN_LEX_LT
:
1759 set
= isl_map_wrap(isl_map_lex_lt(space
));
1761 case ISL_TOKEN_LEX_GT
:
1762 set
= isl_map_wrap(isl_map_lex_gt(space
));
1764 case ISL_TOKEN_LEX_LE
:
1765 set
= isl_map_wrap(isl_map_lex_le(space
));
1767 case ISL_TOKEN_LEX_GE
:
1768 set
= isl_map_wrap(isl_map_lex_ge(space
));
1771 isl_multi_pw_aff_free(mpa1
);
1772 isl_space_free(space
);
1773 isl_die(isl_set_get_ctx(set
), isl_error_internal
,
1774 "unhandled list comparison type", return NULL
);
1776 set
= isl_set_preimage_multi_pw_aff(set
, mpa1
);
1779 isl_pw_aff_list_free(left
);
1780 isl_pw_aff_list_free(right
);
1784 /* Construct constraints of the form
1788 * where a is an element in "left", op is an operator of type "type" and
1789 * b is an element in "right", add the constraints to "set" and return
1791 * "rational" is set if the constraints should be treated as
1792 * a rational constraints.
1794 * If "type" is the type of a comparison operator between lists
1795 * of affine expressions, then a single (compound) constraint
1796 * is constructed by list_cmp instead.
1798 static __isl_give isl_set
*construct_constraints(
1799 __isl_take isl_set
*set
, int type
,
1800 __isl_keep isl_pw_aff_list
*left
, __isl_keep isl_pw_aff_list
*right
,
1805 left
= isl_pw_aff_list_copy(left
);
1806 right
= isl_pw_aff_list_copy(right
);
1808 left
= isl_pw_aff_list_set_rational(left
);
1809 right
= isl_pw_aff_list_set_rational(right
);
1811 if (is_list_comparator_type(type
))
1812 cond
= list_cmp(set
, type
, left
, right
);
1813 else if (type
== ISL_TOKEN_LE
)
1814 cond
= isl_pw_aff_list_le_set(left
, right
);
1815 else if (type
== ISL_TOKEN_GE
)
1816 cond
= isl_pw_aff_list_ge_set(left
, right
);
1817 else if (type
== ISL_TOKEN_LT
)
1818 cond
= isl_pw_aff_list_lt_set(left
, right
);
1819 else if (type
== ISL_TOKEN_GT
)
1820 cond
= isl_pw_aff_list_gt_set(left
, right
);
1821 else if (type
== ISL_TOKEN_NE
)
1822 cond
= isl_pw_aff_list_ne_set(left
, right
);
1824 cond
= isl_pw_aff_list_eq_set(left
, right
);
1826 return isl_set_intersect(set
, cond
);
1829 /* Read a constraint from "s", add it to "map" and return the result.
1830 * "v" contains a description of the identifiers parsed so far.
1831 * "rational" is set if the constraint should be treated as
1832 * a rational constraint.
1833 * The constraint read from "s" may be applied to multiple pairs
1834 * of affine expressions and may be chained.
1835 * In particular, a list of affine expressions is read, followed
1836 * by a comparison operator and another list of affine expressions.
1837 * The comparison operator is then applied to each pair of elements
1838 * in the two lists and the results are added to "map".
1839 * However, if the operator expects two lists of affine expressions,
1840 * then it is applied directly to those lists and the two lists
1841 * are required to have the same length.
1842 * If the next token is another comparison operator, then another
1843 * list of affine expressions is read and the process repeats.
1845 * The processing is performed on a wrapped copy of "map" because
1846 * an affine expression cannot have a binary relation as domain.
1848 static __isl_give isl_map
*add_constraint(__isl_keep isl_stream
*s
,
1849 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
1851 struct isl_token
*tok
;
1853 isl_pw_aff_list
*list1
= NULL
, *list2
= NULL
;
1857 set
= isl_map_wrap(map
);
1858 list1
= accept_affine_list(s
, isl_set_get_space(set
), v
);
1861 tok
= isl_stream_next_token(s
);
1862 if (!is_comparator(tok
)) {
1863 isl_stream_error(s
, tok
, "missing operator");
1865 isl_stream_push_token(s
, tok
);
1869 isl_token_free(tok
);
1871 list2
= accept_affine_list(s
, isl_set_get_space(set
), v
);
1872 n1
= isl_pw_aff_list_n_pw_aff(list1
);
1873 n2
= isl_pw_aff_list_n_pw_aff(list2
);
1874 if (n1
< 0 || n2
< 0)
1876 if (is_list_comparator_type(type
) && n1
!= n2
) {
1877 isl_stream_error(s
, NULL
,
1878 "list arguments not of same size");
1882 set
= construct_constraints(set
, type
, list1
, list2
, rational
);
1883 isl_pw_aff_list_free(list1
);
1886 if (!next_is_comparator(s
))
1888 tok
= isl_stream_next_token(s
);
1890 isl_token_free(tok
);
1892 isl_pw_aff_list_free(list1
);
1894 return isl_set_unwrap(set
);
1896 isl_pw_aff_list_free(list1
);
1897 isl_pw_aff_list_free(list2
);
1902 static __isl_give isl_map
*read_exists(__isl_keep isl_stream
*s
,
1903 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
1906 int seen_paren
= isl_stream_eat_if_available(s
, '(');
1908 map
= isl_map_from_domain(isl_map_wrap(map
));
1909 map
= read_defined_var_list(s
, v
, map
, rational
);
1911 if (isl_stream_eat(s
, ':'))
1914 map
= read_formula(s
, v
, map
, rational
);
1915 map
= isl_set_unwrap(isl_map_domain(map
));
1917 vars_drop(v
, v
->n
- n
);
1918 if (seen_paren
&& isl_stream_eat(s
, ')'))
1927 /* Parse an expression between parentheses and push the result
1928 * back on the stream.
1930 * The parsed expression may be either an affine expression
1931 * or a condition. The first type is pushed onto the stream
1932 * as an isl_pw_aff, while the second is pushed as an isl_map.
1934 * If the initial token indicates the start of a condition,
1935 * we parse it as such.
1936 * Otherwise, we first parse an affine expression and push
1937 * that onto the stream. If the affine expression covers the
1938 * entire expression between parentheses, we return.
1939 * Otherwise, we assume that the affine expression is the
1940 * start of a condition and continue parsing.
1942 static int resolve_paren_expr(__isl_keep isl_stream
*s
,
1943 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
1945 struct isl_token
*tok
, *tok2
;
1950 tok
= isl_stream_next_token(s
);
1951 if (!tok
|| tok
->type
!= '(')
1954 if (isl_stream_next_token_is(s
, '('))
1955 if (resolve_paren_expr(s
, v
, isl_map_copy(map
), rational
))
1958 if (next_is_condition_start(s
)) {
1959 map
= read_formula(s
, v
, map
, rational
);
1960 if (isl_stream_eat(s
, ')'))
1962 tok
->type
= ISL_TOKEN_MAP
;
1964 isl_stream_push_token(s
, tok
);
1968 tok2
= isl_stream_next_token(s
);
1973 isl_stream_push_token(s
, tok2
);
1975 pwaff
= accept_affine(s
, isl_space_wrap(isl_map_get_space(map
)), v
);
1979 has_paren
= isl_stream_eat_if_available(s
, ')');
1981 if (push_aff(s
, line
, col
, pwaff
) < 0)
1985 isl_token_free(tok
);
1990 map
= read_formula(s
, v
, map
, rational
);
1991 if (isl_stream_eat(s
, ')'))
1994 tok
->type
= ISL_TOKEN_MAP
;
1996 isl_stream_push_token(s
, tok
);
2000 isl_token_free(tok
);
2005 static __isl_give isl_map
*read_conjunct(__isl_keep isl_stream
*s
,
2006 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2008 if (isl_stream_next_token_is(s
, '('))
2009 if (resolve_paren_expr(s
, v
, isl_map_copy(map
), rational
))
2012 if (isl_stream_next_token_is(s
, ISL_TOKEN_MAP
)) {
2013 struct isl_token
*tok
;
2014 tok
= isl_stream_next_token(s
);
2018 map
= isl_map_copy(tok
->u
.map
);
2019 isl_token_free(tok
);
2023 if (isl_stream_eat_if_available(s
, ISL_TOKEN_EXISTS
))
2024 return read_exists(s
, v
, map
, rational
);
2026 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TRUE
))
2029 if (isl_stream_eat_if_available(s
, ISL_TOKEN_FALSE
)) {
2030 isl_space
*space
= isl_map_get_space(map
);
2032 return isl_map_empty(space
);
2035 return add_constraint(s
, v
, map
, rational
);
2041 static __isl_give isl_map
*read_conjuncts(__isl_keep isl_stream
*s
,
2042 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2047 negate
= isl_stream_eat_if_available(s
, ISL_TOKEN_NOT
);
2048 res
= read_conjunct(s
, v
, isl_map_copy(map
), rational
);
2050 res
= isl_map_subtract(isl_map_copy(map
), res
);
2052 while (res
&& isl_stream_eat_if_available(s
, ISL_TOKEN_AND
)) {
2055 negate
= isl_stream_eat_if_available(s
, ISL_TOKEN_NOT
);
2056 res_i
= read_conjunct(s
, v
, isl_map_copy(map
), rational
);
2058 res
= isl_map_subtract(res
, res_i
);
2060 res
= isl_map_intersect(res
, res_i
);
2067 static __isl_give isl_map
*read_disjuncts(__isl_keep isl_stream
*s
,
2068 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2072 if (isl_stream_next_token_is(s
, '}'))
2075 res
= read_conjuncts(s
, v
, isl_map_copy(map
), rational
);
2076 while (isl_stream_eat_if_available(s
, ISL_TOKEN_OR
)) {
2079 res_i
= read_conjuncts(s
, v
, isl_map_copy(map
), rational
);
2080 res
= isl_map_union(res
, res_i
);
2087 /* Read a first order formula from "s", add the corresponding
2088 * constraints to "map" and return the result.
2090 * In particular, read a formula of the form
2098 * where a and b are disjunctions.
2100 * In the first case, map is replaced by
2102 * map \cap { [..] : a }
2104 * In the second case, it is replaced by
2106 * (map \setminus { [..] : a}) \cup (map \cap { [..] : b })
2108 static __isl_give isl_map
*read_formula(__isl_keep isl_stream
*s
,
2109 struct vars
*v
, __isl_take isl_map
*map
, int rational
)
2113 res
= read_disjuncts(s
, v
, isl_map_copy(map
), rational
);
2115 if (isl_stream_eat_if_available(s
, ISL_TOKEN_IMPLIES
)) {
2118 res
= isl_map_subtract(isl_map_copy(map
), res
);
2119 res2
= read_disjuncts(s
, v
, map
, rational
);
2120 res
= isl_map_union(res
, res2
);
2127 static isl_size
polylib_pos_to_isl_pos(__isl_keep isl_basic_map
*bmap
, int pos
)
2129 isl_size n_out
, n_in
, n_param
, n_div
;
2131 n_param
= isl_basic_map_dim(bmap
, isl_dim_param
);
2132 n_in
= isl_basic_map_dim(bmap
, isl_dim_in
);
2133 n_out
= isl_basic_map_dim(bmap
, isl_dim_out
);
2134 n_div
= isl_basic_map_dim(bmap
, isl_dim_div
);
2135 if (n_param
< 0 || n_in
< 0 || n_out
< 0 || n_div
< 0)
2136 return isl_size_error
;
2139 return 1 + n_param
+ n_in
+ pos
;
2143 return 1 + n_param
+ pos
;
2147 return 1 + n_param
+ n_in
+ n_out
+ pos
;
2156 static __isl_give isl_basic_map
*basic_map_read_polylib_constraint(
2157 __isl_keep isl_stream
*s
, __isl_take isl_basic_map
*bmap
)
2160 struct isl_token
*tok
;
2169 tok
= isl_stream_next_token(s
);
2170 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2171 isl_stream_error(s
, tok
, "expecting coefficient");
2173 isl_stream_push_token(s
, tok
);
2176 if (!tok
->on_new_line
) {
2177 isl_stream_error(s
, tok
, "coefficient should appear on new line");
2178 isl_stream_push_token(s
, tok
);
2182 type
= isl_int_get_si(tok
->u
.v
);
2183 isl_token_free(tok
);
2185 isl_assert(s
->ctx
, type
== 0 || type
== 1, goto error
);
2187 k
= isl_basic_map_alloc_equality(bmap
);
2190 k
= isl_basic_map_alloc_inequality(bmap
);
2196 total
= isl_basic_map_dim(bmap
, isl_dim_all
);
2198 return isl_basic_map_free(bmap
);
2199 for (j
= 0; j
< 1 + total
; ++j
) {
2201 tok
= isl_stream_next_token(s
);
2202 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2203 isl_stream_error(s
, tok
, "expecting coefficient");
2205 isl_stream_push_token(s
, tok
);
2208 if (tok
->on_new_line
) {
2209 isl_stream_error(s
, tok
,
2210 "coefficient should not appear on new line");
2211 isl_stream_push_token(s
, tok
);
2214 pos
= polylib_pos_to_isl_pos(bmap
, j
);
2216 isl_int_set(c
[pos
], tok
->u
.v
);
2217 isl_token_free(tok
);
2219 return isl_basic_map_free(bmap
);
2224 isl_basic_map_free(bmap
);
2228 static __isl_give isl_basic_map
*basic_map_read_polylib(
2229 __isl_keep isl_stream
*s
)
2232 struct isl_token
*tok
;
2233 struct isl_token
*tok2
;
2236 unsigned in
= 0, out
, local
= 0;
2237 struct isl_basic_map
*bmap
= NULL
;
2240 tok
= isl_stream_next_token(s
);
2242 isl_stream_error(s
, NULL
, "unexpected EOF");
2245 tok2
= isl_stream_next_token(s
);
2247 isl_token_free(tok
);
2248 isl_stream_error(s
, NULL
, "unexpected EOF");
2251 if (tok
->type
!= ISL_TOKEN_VALUE
|| tok2
->type
!= ISL_TOKEN_VALUE
) {
2252 isl_stream_push_token(s
, tok2
);
2253 isl_stream_push_token(s
, tok
);
2254 isl_stream_error(s
, NULL
,
2255 "expecting constraint matrix dimensions");
2258 n_row
= isl_int_get_si(tok
->u
.v
);
2259 n_col
= isl_int_get_si(tok2
->u
.v
);
2260 on_new_line
= tok2
->on_new_line
;
2261 isl_token_free(tok2
);
2262 isl_token_free(tok
);
2263 isl_assert(s
->ctx
, !on_new_line
, return NULL
);
2264 isl_assert(s
->ctx
, n_row
>= 0, return NULL
);
2265 isl_assert(s
->ctx
, n_col
>= 2 + nparam
, return NULL
);
2266 tok
= isl_stream_next_token_on_same_line(s
);
2268 if (tok
->type
!= ISL_TOKEN_VALUE
) {
2269 isl_stream_error(s
, tok
,
2270 "expecting number of output dimensions");
2271 isl_stream_push_token(s
, tok
);
2274 out
= isl_int_get_si(tok
->u
.v
);
2275 isl_token_free(tok
);
2277 tok
= isl_stream_next_token_on_same_line(s
);
2278 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2279 isl_stream_error(s
, tok
,
2280 "expecting number of input dimensions");
2282 isl_stream_push_token(s
, tok
);
2285 in
= isl_int_get_si(tok
->u
.v
);
2286 isl_token_free(tok
);
2288 tok
= isl_stream_next_token_on_same_line(s
);
2289 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2290 isl_stream_error(s
, tok
,
2291 "expecting number of existentials");
2293 isl_stream_push_token(s
, tok
);
2296 local
= isl_int_get_si(tok
->u
.v
);
2297 isl_token_free(tok
);
2299 tok
= isl_stream_next_token_on_same_line(s
);
2300 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2301 isl_stream_error(s
, tok
,
2302 "expecting number of parameters");
2304 isl_stream_push_token(s
, tok
);
2307 nparam
= isl_int_get_si(tok
->u
.v
);
2308 isl_token_free(tok
);
2309 if (n_col
!= 1 + out
+ in
+ local
+ nparam
+ 1) {
2310 isl_stream_error(s
, NULL
,
2311 "dimensions don't match");
2315 out
= n_col
- 2 - nparam
;
2316 bmap
= isl_basic_map_alloc(s
->ctx
, nparam
, in
, out
, local
, n_row
, n_row
);
2320 for (i
= 0; i
< local
; ++i
) {
2321 int k
= isl_basic_map_alloc_div(bmap
);
2324 isl_seq_clr(bmap
->div
[k
], 1 + 1 + nparam
+ in
+ out
+ local
);
2327 for (i
= 0; i
< n_row
; ++i
)
2328 bmap
= basic_map_read_polylib_constraint(s
, bmap
);
2330 tok
= isl_stream_next_token_on_same_line(s
);
2332 isl_stream_error(s
, tok
, "unexpected extra token on line");
2333 isl_stream_push_token(s
, tok
);
2337 bmap
= isl_basic_map_simplify(bmap
);
2338 bmap
= isl_basic_map_finalize(bmap
);
2341 isl_basic_map_free(bmap
);
2345 static __isl_give isl_map
*map_read_polylib(__isl_keep isl_stream
*s
)
2347 struct isl_token
*tok
;
2348 struct isl_token
*tok2
;
2350 struct isl_map
*map
;
2352 tok
= isl_stream_next_token(s
);
2354 isl_stream_error(s
, NULL
, "unexpected EOF");
2357 tok2
= isl_stream_next_token_on_same_line(s
);
2358 if (tok2
&& tok2
->type
== ISL_TOKEN_VALUE
) {
2359 isl_stream_push_token(s
, tok2
);
2360 isl_stream_push_token(s
, tok
);
2361 return isl_map_from_basic_map(basic_map_read_polylib(s
));
2364 isl_stream_error(s
, tok2
, "unexpected token");
2365 isl_stream_push_token(s
, tok2
);
2366 isl_stream_push_token(s
, tok
);
2369 n
= isl_int_get_si(tok
->u
.v
);
2370 isl_token_free(tok
);
2372 isl_assert(s
->ctx
, n
>= 1, return NULL
);
2374 map
= isl_map_from_basic_map(basic_map_read_polylib(s
));
2376 for (i
= 1; map
&& i
< n
; ++i
)
2377 map
= isl_map_union(map
,
2378 isl_map_from_basic_map(basic_map_read_polylib(s
)));
2383 static int optional_power(__isl_keep isl_stream
*s
)
2386 struct isl_token
*tok
;
2388 tok
= isl_stream_next_token(s
);
2391 if (tok
->type
!= '^') {
2392 isl_stream_push_token(s
, tok
);
2395 isl_token_free(tok
);
2396 tok
= isl_stream_next_token(s
);
2397 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2398 isl_stream_error(s
, tok
, "expecting exponent");
2400 isl_stream_push_token(s
, tok
);
2403 pow
= isl_int_get_si(tok
->u
.v
);
2404 isl_token_free(tok
);
2408 static __isl_give isl_pw_qpolynomial
*read_term(__isl_keep isl_stream
*s
,
2409 __isl_keep isl_map
*map
, struct vars
*v
);
2411 static __isl_give isl_pw_qpolynomial
*read_factor(__isl_keep isl_stream
*s
,
2412 __isl_keep isl_map
*map
, struct vars
*v
)
2414 isl_pw_qpolynomial
*pwqp
;
2415 struct isl_token
*tok
;
2417 tok
= next_token(s
);
2419 isl_stream_error(s
, NULL
, "unexpected EOF");
2422 if (tok
->type
== '(') {
2425 isl_token_free(tok
);
2426 pwqp
= read_term(s
, map
, v
);
2429 if (isl_stream_eat(s
, ')'))
2431 pow
= optional_power(s
);
2432 pwqp
= isl_pw_qpolynomial_pow(pwqp
, pow
);
2433 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
2434 struct isl_token
*tok2
;
2435 isl_qpolynomial
*qp
;
2437 tok2
= isl_stream_next_token(s
);
2438 if (tok2
&& tok2
->type
== '/') {
2439 isl_token_free(tok2
);
2440 tok2
= next_token(s
);
2441 if (!tok2
|| tok2
->type
!= ISL_TOKEN_VALUE
) {
2442 isl_stream_error(s
, tok2
, "expected denominator");
2443 isl_token_free(tok
);
2444 isl_token_free(tok2
);
2447 qp
= isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map
),
2448 tok
->u
.v
, tok2
->u
.v
);
2449 isl_token_free(tok2
);
2451 isl_stream_push_token(s
, tok2
);
2452 qp
= isl_qpolynomial_cst_on_domain(isl_map_get_space(map
),
2455 isl_token_free(tok
);
2456 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2457 } else if (tok
->type
== ISL_TOKEN_INFTY
) {
2458 isl_qpolynomial
*qp
;
2459 isl_token_free(tok
);
2460 qp
= isl_qpolynomial_infty_on_domain(isl_map_get_space(map
));
2461 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2462 } else if (tok
->type
== ISL_TOKEN_NAN
) {
2463 isl_qpolynomial
*qp
;
2464 isl_token_free(tok
);
2465 qp
= isl_qpolynomial_nan_on_domain(isl_map_get_space(map
));
2466 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2467 } else if (tok
->type
== ISL_TOKEN_IDENT
) {
2469 int pos
= vars_pos(v
, tok
->u
.s
, -1);
2471 isl_qpolynomial
*qp
;
2473 isl_token_free(tok
);
2477 vars_drop(v
, v
->n
- n
);
2478 isl_stream_error(s
, tok
, "unknown identifier");
2479 isl_token_free(tok
);
2482 isl_token_free(tok
);
2483 pow
= optional_power(s
);
2484 qp
= isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map
), pos
, pow
);
2485 pwqp
= isl_pw_qpolynomial_from_qpolynomial(qp
);
2486 } else if (is_start_of_div(tok
)) {
2490 isl_stream_push_token(s
, tok
);
2491 pwaff
= accept_div(s
, isl_map_get_space(map
), v
);
2492 pow
= optional_power(s
);
2493 pwqp
= isl_pw_qpolynomial_from_pw_aff(pwaff
);
2494 pwqp
= isl_pw_qpolynomial_pow(pwqp
, pow
);
2495 } else if (tok
->type
== '-') {
2496 isl_token_free(tok
);
2497 pwqp
= read_factor(s
, map
, v
);
2498 pwqp
= isl_pw_qpolynomial_neg(pwqp
);
2500 isl_stream_error(s
, tok
, "unexpected isl_token");
2501 isl_stream_push_token(s
, tok
);
2505 if (isl_stream_eat_if_available(s
, '*') ||
2506 isl_stream_next_token_is(s
, ISL_TOKEN_IDENT
)) {
2507 isl_pw_qpolynomial
*pwqp2
;
2509 pwqp2
= read_factor(s
, map
, v
);
2510 pwqp
= isl_pw_qpolynomial_mul(pwqp
, pwqp2
);
2515 isl_pw_qpolynomial_free(pwqp
);
2519 static __isl_give isl_pw_qpolynomial
*read_term(__isl_keep isl_stream
*s
,
2520 __isl_keep isl_map
*map
, struct vars
*v
)
2522 struct isl_token
*tok
;
2523 isl_pw_qpolynomial
*pwqp
;
2525 pwqp
= read_factor(s
, map
, v
);
2528 tok
= next_token(s
);
2532 if (tok
->type
== '+') {
2533 isl_pw_qpolynomial
*pwqp2
;
2535 isl_token_free(tok
);
2536 pwqp2
= read_factor(s
, map
, v
);
2537 pwqp
= isl_pw_qpolynomial_add(pwqp
, pwqp2
);
2538 } else if (tok
->type
== '-') {
2539 isl_pw_qpolynomial
*pwqp2
;
2541 isl_token_free(tok
);
2542 pwqp2
= read_factor(s
, map
, v
);
2543 pwqp
= isl_pw_qpolynomial_sub(pwqp
, pwqp2
);
2544 } else if (tok
->type
== ISL_TOKEN_VALUE
&&
2545 isl_int_is_neg(tok
->u
.v
)) {
2546 isl_pw_qpolynomial
*pwqp2
;
2548 isl_stream_push_token(s
, tok
);
2549 pwqp2
= read_factor(s
, map
, v
);
2550 pwqp
= isl_pw_qpolynomial_add(pwqp
, pwqp2
);
2552 isl_stream_push_token(s
, tok
);
2560 static __isl_give isl_map
*read_optional_formula(__isl_keep isl_stream
*s
,
2561 __isl_take isl_map
*map
, struct vars
*v
, int rational
)
2563 struct isl_token
*tok
;
2565 tok
= isl_stream_next_token(s
);
2567 isl_stream_error(s
, NULL
, "unexpected EOF");
2570 if (tok
->type
== ':' ||
2571 (tok
->type
== ISL_TOKEN_OR
&& !strcmp(tok
->u
.s
, "|"))) {
2572 isl_token_free(tok
);
2573 map
= read_formula(s
, v
, map
, rational
);
2575 isl_stream_push_token(s
, tok
);
2583 static struct isl_obj
obj_read_poly(__isl_keep isl_stream
*s
,
2584 __isl_take isl_map
*map
, struct vars
*v
, int n
)
2586 struct isl_obj obj
= { isl_obj_pw_qpolynomial
, NULL
};
2587 isl_pw_qpolynomial
*pwqp
;
2588 struct isl_set
*set
;
2590 pwqp
= read_term(s
, map
, v
);
2591 map
= read_optional_formula(s
, map
, v
, 0);
2592 set
= isl_map_range(map
);
2594 pwqp
= isl_pw_qpolynomial_intersect_domain(pwqp
, set
);
2596 vars_drop(v
, v
->n
- n
);
2602 static struct isl_obj
obj_read_poly_or_fold(__isl_keep isl_stream
*s
,
2603 __isl_take isl_set
*set
, struct vars
*v
, int n
)
2605 struct isl_obj obj
= { isl_obj_pw_qpolynomial_fold
, NULL
};
2606 isl_pw_qpolynomial
*pwqp
;
2607 isl_pw_qpolynomial_fold
*pwf
= NULL
;
2609 if (!isl_stream_eat_if_available(s
, ISL_TOKEN_MAX
))
2610 return obj_read_poly(s
, set
, v
, n
);
2612 if (isl_stream_eat(s
, '('))
2615 pwqp
= read_term(s
, set
, v
);
2616 pwf
= isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max
, pwqp
);
2618 while (isl_stream_eat_if_available(s
, ',')) {
2619 isl_pw_qpolynomial_fold
*pwf_i
;
2620 pwqp
= read_term(s
, set
, v
);
2621 pwf_i
= isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max
,
2623 pwf
= isl_pw_qpolynomial_fold_fold(pwf
, pwf_i
);
2626 if (isl_stream_eat(s
, ')'))
2629 set
= read_optional_formula(s
, set
, v
, 0);
2630 pwf
= isl_pw_qpolynomial_fold_intersect_domain(pwf
, set
);
2632 vars_drop(v
, v
->n
- n
);
2638 isl_pw_qpolynomial_fold_free(pwf
);
2639 obj
.type
= isl_obj_none
;
2643 static int is_rational(__isl_keep isl_stream
*s
)
2645 struct isl_token
*tok
;
2647 tok
= isl_stream_next_token(s
);
2650 if (tok
->type
== ISL_TOKEN_RAT
&& isl_stream_next_token_is(s
, ':')) {
2651 isl_token_free(tok
);
2652 isl_stream_eat(s
, ':');
2656 isl_stream_push_token(s
, tok
);
2661 static struct isl_obj
obj_read_body(__isl_keep isl_stream
*s
,
2662 __isl_take isl_map
*map
, struct vars
*v
)
2664 struct isl_token
*tok
;
2665 struct isl_obj obj
= { isl_obj_set
, NULL
};
2669 rational
= is_rational(s
);
2671 map
= isl_map_set_rational(map
);
2673 if (isl_stream_next_token_is(s
, ':')) {
2674 obj
.type
= isl_obj_set
;
2675 obj
.v
= read_optional_formula(s
, map
, v
, rational
);
2679 if (!next_is_tuple(s
))
2680 return obj_read_poly_or_fold(s
, map
, v
, n
);
2682 map
= read_map_tuple(s
, map
, isl_dim_in
, v
, rational
, 0);
2685 tok
= isl_stream_next_token(s
);
2688 if (tok
->type
== ISL_TOKEN_TO
) {
2689 obj
.type
= isl_obj_map
;
2690 isl_token_free(tok
);
2691 if (!next_is_tuple(s
)) {
2692 isl_set
*set
= isl_map_domain(map
);
2693 return obj_read_poly_or_fold(s
, set
, v
, n
);
2695 map
= read_map_tuple(s
, map
, isl_dim_out
, v
, rational
, 0);
2699 map
= isl_map_domain(map
);
2700 isl_stream_push_token(s
, tok
);
2703 map
= read_optional_formula(s
, map
, v
, rational
);
2705 vars_drop(v
, v
->n
- n
);
2711 obj
.type
= isl_obj_none
;
2715 static struct isl_obj
to_union(isl_ctx
*ctx
, struct isl_obj obj
)
2717 if (obj
.type
== isl_obj_map
) {
2718 obj
.v
= isl_union_map_from_map(obj
.v
);
2719 obj
.type
= isl_obj_union_map
;
2720 } else if (obj
.type
== isl_obj_set
) {
2721 obj
.v
= isl_union_set_from_set(obj
.v
);
2722 obj
.type
= isl_obj_union_set
;
2723 } else if (obj
.type
== isl_obj_pw_qpolynomial
) {
2724 obj
.v
= isl_union_pw_qpolynomial_from_pw_qpolynomial(obj
.v
);
2725 obj
.type
= isl_obj_union_pw_qpolynomial
;
2726 } else if (obj
.type
== isl_obj_pw_qpolynomial_fold
) {
2727 obj
.v
= isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj
.v
);
2728 obj
.type
= isl_obj_union_pw_qpolynomial_fold
;
2730 isl_assert(ctx
, 0, goto error
);
2733 obj
.type
->free(obj
.v
);
2734 obj
.type
= isl_obj_none
;
2738 static struct isl_obj
obj_add(__isl_keep isl_stream
*s
,
2739 struct isl_obj obj1
, struct isl_obj obj2
)
2741 if (obj2
.type
== isl_obj_none
|| !obj2
.v
)
2743 if (obj1
.type
== isl_obj_set
&& obj2
.type
== isl_obj_union_set
)
2744 obj1
= to_union(s
->ctx
, obj1
);
2745 if (obj1
.type
== isl_obj_union_set
&& obj2
.type
== isl_obj_set
)
2746 obj2
= to_union(s
->ctx
, obj2
);
2747 if (obj1
.type
== isl_obj_map
&& obj2
.type
== isl_obj_union_map
)
2748 obj1
= to_union(s
->ctx
, obj1
);
2749 if (obj1
.type
== isl_obj_union_map
&& obj2
.type
== isl_obj_map
)
2750 obj2
= to_union(s
->ctx
, obj2
);
2751 if (obj1
.type
== isl_obj_pw_qpolynomial
&&
2752 obj2
.type
== isl_obj_union_pw_qpolynomial
)
2753 obj1
= to_union(s
->ctx
, obj1
);
2754 if (obj1
.type
== isl_obj_union_pw_qpolynomial
&&
2755 obj2
.type
== isl_obj_pw_qpolynomial
)
2756 obj2
= to_union(s
->ctx
, obj2
);
2757 if (obj1
.type
== isl_obj_pw_qpolynomial_fold
&&
2758 obj2
.type
== isl_obj_union_pw_qpolynomial_fold
)
2759 obj1
= to_union(s
->ctx
, obj1
);
2760 if (obj1
.type
== isl_obj_union_pw_qpolynomial_fold
&&
2761 obj2
.type
== isl_obj_pw_qpolynomial_fold
)
2762 obj2
= to_union(s
->ctx
, obj2
);
2763 if (obj1
.type
!= obj2
.type
) {
2764 isl_stream_error(s
, NULL
,
2765 "attempt to combine incompatible objects");
2768 if (!obj1
.type
->add
)
2769 isl_die(s
->ctx
, isl_error_internal
,
2770 "combination not supported on object type", goto error
);
2771 if (obj1
.type
== isl_obj_map
&& !isl_map_has_equal_space(obj1
.v
, obj2
.v
)) {
2772 obj1
= to_union(s
->ctx
, obj1
);
2773 obj2
= to_union(s
->ctx
, obj2
);
2775 if (obj1
.type
== isl_obj_set
&& !isl_set_has_equal_space(obj1
.v
, obj2
.v
)) {
2776 obj1
= to_union(s
->ctx
, obj1
);
2777 obj2
= to_union(s
->ctx
, obj2
);
2779 if (obj1
.type
== isl_obj_pw_qpolynomial
&&
2780 !isl_pw_qpolynomial_has_equal_space(obj1
.v
, obj2
.v
)) {
2781 obj1
= to_union(s
->ctx
, obj1
);
2782 obj2
= to_union(s
->ctx
, obj2
);
2784 if (obj1
.type
== isl_obj_pw_qpolynomial_fold
&&
2785 !isl_pw_qpolynomial_fold_has_equal_space(obj1
.v
, obj2
.v
)) {
2786 obj1
= to_union(s
->ctx
, obj1
);
2787 obj2
= to_union(s
->ctx
, obj2
);
2789 obj1
.v
= obj1
.type
->add(obj1
.v
, obj2
.v
);
2792 obj1
.type
->free(obj1
.v
);
2793 obj2
.type
->free(obj2
.v
);
2794 obj1
.type
= isl_obj_none
;
2799 /* Are the first two tokens on "s", "domain" (either as a string
2800 * or as an identifier) followed by ":"?
2802 static int next_is_domain_colon(__isl_keep isl_stream
*s
)
2804 struct isl_token
*tok
;
2808 tok
= isl_stream_next_token(s
);
2811 if (tok
->type
!= ISL_TOKEN_IDENT
&& tok
->type
!= ISL_TOKEN_STRING
) {
2812 isl_stream_push_token(s
, tok
);
2816 name
= isl_token_get_str(s
->ctx
, tok
);
2817 res
= !strcmp(name
, "domain") && isl_stream_next_token_is(s
, ':');
2820 isl_stream_push_token(s
, tok
);
2825 /* Do the first tokens on "s" look like a schedule?
2827 * The root of a schedule is always a domain node, so the first thing
2828 * we expect in the stream is a domain key, i.e., "domain" followed
2829 * by ":". If the schedule was printed in YAML flow style, then
2830 * we additionally expect a "{" to open the outer mapping.
2832 static int next_is_schedule(__isl_keep isl_stream
*s
)
2834 struct isl_token
*tok
;
2837 tok
= isl_stream_next_token(s
);
2840 if (tok
->type
!= '{') {
2841 isl_stream_push_token(s
, tok
);
2842 return next_is_domain_colon(s
);
2845 is_schedule
= next_is_domain_colon(s
);
2846 isl_stream_push_token(s
, tok
);
2851 /* Read an isl_schedule from "s" and store it in an isl_obj.
2853 static struct isl_obj
schedule_read(__isl_keep isl_stream
*s
)
2857 obj
.type
= isl_obj_schedule
;
2858 obj
.v
= isl_stream_read_schedule(s
);
2863 /* Read a disjunction of object bodies from "s".
2864 * That is, read the inside of the braces, but not the braces themselves.
2865 * "v" contains a description of the identifiers parsed so far.
2866 * "map" contains information about the parameters.
2868 static struct isl_obj
obj_read_disjuncts(__isl_keep isl_stream
*s
,
2869 struct vars
*v
, __isl_keep isl_map
*map
)
2871 struct isl_obj obj
= { isl_obj_set
, NULL
};
2873 if (isl_stream_next_token_is(s
, '}')) {
2874 obj
.type
= isl_obj_union_set
;
2875 obj
.v
= isl_union_set_empty(isl_map_get_space(map
));
2881 o
= obj_read_body(s
, isl_map_copy(map
), v
);
2885 obj
= obj_add(s
, obj
, o
);
2886 if (obj
.type
== isl_obj_none
|| !obj
.v
)
2888 if (!isl_stream_eat_if_available(s
, ';'))
2890 if (isl_stream_next_token_is(s
, '}'))
2897 static struct isl_obj
obj_read(__isl_keep isl_stream
*s
)
2899 isl_map
*map
= NULL
;
2900 struct isl_token
*tok
;
2901 struct vars
*v
= NULL
;
2902 struct isl_obj obj
= { isl_obj_set
, NULL
};
2904 if (next_is_schedule(s
))
2905 return schedule_read(s
);
2907 tok
= next_token(s
);
2909 isl_stream_error(s
, NULL
, "unexpected EOF");
2912 if (tok
->type
== ISL_TOKEN_VALUE
) {
2913 struct isl_token
*tok2
;
2914 struct isl_map
*map
;
2916 tok2
= isl_stream_next_token(s
);
2917 if (!tok2
|| tok2
->type
!= ISL_TOKEN_VALUE
||
2918 isl_int_is_neg(tok2
->u
.v
)) {
2920 isl_stream_push_token(s
, tok2
);
2921 obj
.type
= isl_obj_val
;
2922 obj
.v
= isl_val_int_from_isl_int(s
->ctx
, tok
->u
.v
);
2923 isl_token_free(tok
);
2926 isl_stream_push_token(s
, tok2
);
2927 isl_stream_push_token(s
, tok
);
2928 map
= map_read_polylib(s
);
2931 if (isl_map_may_be_set(map
))
2932 obj
.v
= isl_map_range(map
);
2934 obj
.type
= isl_obj_map
;
2939 v
= vars_new(s
->ctx
);
2941 isl_stream_push_token(s
, tok
);
2944 map
= isl_map_universe(isl_space_params_alloc(s
->ctx
, 0));
2945 if (tok
->type
== '[') {
2946 isl_stream_push_token(s
, tok
);
2947 map
= read_map_tuple(s
, map
, isl_dim_param
, v
, 0, 0);
2950 tok
= isl_stream_next_token(s
);
2951 if (!tok
|| tok
->type
!= ISL_TOKEN_TO
) {
2952 isl_stream_error(s
, tok
, "expecting '->'");
2954 isl_stream_push_token(s
, tok
);
2957 isl_token_free(tok
);
2958 tok
= isl_stream_next_token(s
);
2960 if (!tok
|| tok
->type
!= '{') {
2961 isl_stream_error(s
, tok
, "expecting '{'");
2963 isl_stream_push_token(s
, tok
);
2966 isl_token_free(tok
);
2968 tok
= isl_stream_next_token(s
);
2971 else if (tok
->type
== ISL_TOKEN_IDENT
&& !strcmp(tok
->u
.s
, "Sym")) {
2972 isl_token_free(tok
);
2973 if (isl_stream_eat(s
, '='))
2975 map
= read_map_tuple(s
, map
, isl_dim_param
, v
, 0, 1);
2979 isl_stream_push_token(s
, tok
);
2981 obj
= obj_read_disjuncts(s
, v
, map
);
2982 if (obj
.type
== isl_obj_none
|| !obj
.v
)
2985 tok
= isl_stream_next_token(s
);
2986 if (tok
&& tok
->type
== '}') {
2987 isl_token_free(tok
);
2989 isl_stream_error(s
, tok
, "unexpected isl_token");
2991 isl_token_free(tok
);
3001 obj
.type
->free(obj
.v
);
3008 struct isl_obj
isl_stream_read_obj(__isl_keep isl_stream
*s
)
3013 __isl_give isl_map
*isl_stream_read_map(__isl_keep isl_stream
*s
)
3019 isl_assert(s
->ctx
, obj
.type
== isl_obj_map
||
3020 obj
.type
== isl_obj_set
, goto error
);
3022 if (obj
.type
== isl_obj_set
)
3023 obj
.v
= isl_map_from_range(obj
.v
);
3027 obj
.type
->free(obj
.v
);
3031 __isl_give isl_set
*isl_stream_read_set(__isl_keep isl_stream
*s
)
3037 if (obj
.type
== isl_obj_map
&& isl_map_may_be_set(obj
.v
)) {
3038 obj
.v
= isl_map_range(obj
.v
);
3039 obj
.type
= isl_obj_set
;
3041 isl_assert(s
->ctx
, obj
.type
== isl_obj_set
, goto error
);
3046 obj
.type
->free(obj
.v
);
3050 __isl_give isl_union_map
*isl_stream_read_union_map(__isl_keep isl_stream
*s
)
3055 if (obj
.type
== isl_obj_map
) {
3056 obj
.type
= isl_obj_union_map
;
3057 obj
.v
= isl_union_map_from_map(obj
.v
);
3059 if (obj
.type
== isl_obj_set
) {
3060 obj
.type
= isl_obj_union_set
;
3061 obj
.v
= isl_union_set_from_set(obj
.v
);
3063 if (obj
.v
&& obj
.type
== isl_obj_union_set
&&
3064 isl_union_set_is_empty(obj
.v
))
3065 obj
.type
= isl_obj_union_map
;
3066 if (obj
.v
&& obj
.type
!= isl_obj_union_map
)
3067 isl_die(s
->ctx
, isl_error_invalid
, "invalid input", goto error
);
3071 obj
.type
->free(obj
.v
);
3075 /* Extract an isl_union_set from "obj".
3076 * This only works if the object was detected as either a set
3077 * (in which case it is converted to a union set) or a union set.
3079 static __isl_give isl_union_set
*extract_union_set(isl_ctx
*ctx
,
3082 if (obj
.type
== isl_obj_set
) {
3083 obj
.type
= isl_obj_union_set
;
3084 obj
.v
= isl_union_set_from_set(obj
.v
);
3087 isl_assert(ctx
, obj
.type
== isl_obj_union_set
, goto error
);
3091 obj
.type
->free(obj
.v
);
3095 /* Read an isl_union_set from "s".
3096 * First read a generic object and then try and extract
3097 * an isl_union_set from that.
3099 __isl_give isl_union_set
*isl_stream_read_union_set(__isl_keep isl_stream
*s
)
3104 return extract_union_set(s
->ctx
, obj
);
3107 static __isl_give isl_basic_map
*basic_map_read(__isl_keep isl_stream
*s
)
3110 struct isl_map
*map
;
3111 struct isl_basic_map
*bmap
;
3114 if (obj
.v
&& (obj
.type
!= isl_obj_map
&& obj
.type
!= isl_obj_set
))
3115 isl_die(s
->ctx
, isl_error_invalid
, "not a (basic) set or map",
3122 isl_die(s
->ctx
, isl_error_invalid
,
3123 "set or map description involves "
3124 "more than one disjunct", goto error
);
3127 bmap
= isl_basic_map_empty(isl_map_get_space(map
));
3129 bmap
= isl_basic_map_copy(map
->p
[0]);
3135 obj
.type
->free(obj
.v
);
3139 static __isl_give isl_basic_set
*basic_set_read(__isl_keep isl_stream
*s
)
3141 isl_basic_map
*bmap
;
3142 bmap
= basic_map_read(s
);
3145 if (!isl_basic_map_may_be_set(bmap
))
3146 isl_die(s
->ctx
, isl_error_invalid
,
3147 "input is not a set", goto error
);
3148 return isl_basic_map_range(bmap
);
3150 isl_basic_map_free(bmap
);
3154 __isl_give isl_basic_map
*isl_basic_map_read_from_file(isl_ctx
*ctx
,
3157 struct isl_basic_map
*bmap
;
3158 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3161 bmap
= basic_map_read(s
);
3166 __isl_give isl_basic_set
*isl_basic_set_read_from_file(isl_ctx
*ctx
,
3169 isl_basic_set
*bset
;
3170 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3173 bset
= basic_set_read(s
);
3178 __isl_give isl_basic_map
*isl_basic_map_read_from_str(isl_ctx
*ctx
,
3181 struct isl_basic_map
*bmap
;
3182 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3185 bmap
= basic_map_read(s
);
3190 __isl_give isl_basic_set
*isl_basic_set_read_from_str(isl_ctx
*ctx
,
3193 isl_basic_set
*bset
;
3194 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3197 bset
= basic_set_read(s
);
3202 __isl_give isl_map
*isl_map_read_from_file(struct isl_ctx
*ctx
,
3205 struct isl_map
*map
;
3206 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3209 map
= isl_stream_read_map(s
);
3214 __isl_give isl_map
*isl_map_read_from_str(struct isl_ctx
*ctx
,
3217 struct isl_map
*map
;
3218 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3221 map
= isl_stream_read_map(s
);
3226 __isl_give isl_set
*isl_set_read_from_file(struct isl_ctx
*ctx
,
3230 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3233 set
= isl_stream_read_set(s
);
3238 __isl_give isl_set
*isl_set_read_from_str(isl_ctx
*ctx
, const char *str
)
3241 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3244 set
= isl_stream_read_set(s
);
3249 __isl_give isl_union_map
*isl_union_map_read_from_file(isl_ctx
*ctx
,
3252 isl_union_map
*umap
;
3253 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3256 umap
= isl_stream_read_union_map(s
);
3261 __isl_give isl_union_map
*isl_union_map_read_from_str(struct isl_ctx
*ctx
,
3264 isl_union_map
*umap
;
3265 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3268 umap
= isl_stream_read_union_map(s
);
3273 __isl_give isl_union_set
*isl_union_set_read_from_file(isl_ctx
*ctx
,
3276 isl_union_set
*uset
;
3277 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3280 uset
= isl_stream_read_union_set(s
);
3285 __isl_give isl_union_set
*isl_union_set_read_from_str(struct isl_ctx
*ctx
,
3288 isl_union_set
*uset
;
3289 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3292 uset
= isl_stream_read_union_set(s
);
3297 static __isl_give isl_vec
*isl_vec_read_polylib(__isl_keep isl_stream
*s
)
3299 struct isl_vec
*vec
= NULL
;
3300 struct isl_token
*tok
;
3304 tok
= isl_stream_next_token(s
);
3305 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
3306 isl_stream_error(s
, tok
, "expecting vector length");
3310 size
= isl_int_get_si(tok
->u
.v
);
3311 isl_token_free(tok
);
3313 vec
= isl_vec_alloc(s
->ctx
, size
);
3315 for (j
= 0; j
< size
; ++j
) {
3316 tok
= isl_stream_next_token(s
);
3317 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
3318 isl_stream_error(s
, tok
, "expecting constant value");
3321 isl_int_set(vec
->el
[j
], tok
->u
.v
);
3322 isl_token_free(tok
);
3327 isl_token_free(tok
);
3332 static __isl_give isl_vec
*vec_read(__isl_keep isl_stream
*s
)
3334 return isl_vec_read_polylib(s
);
3337 __isl_give isl_vec
*isl_vec_read_from_file(isl_ctx
*ctx
, FILE *input
)
3340 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3348 __isl_give isl_pw_qpolynomial
*isl_stream_read_pw_qpolynomial(
3349 __isl_keep isl_stream
*s
)
3355 isl_assert(s
->ctx
, obj
.type
== isl_obj_pw_qpolynomial
,
3360 obj
.type
->free(obj
.v
);
3364 __isl_give isl_pw_qpolynomial
*isl_pw_qpolynomial_read_from_str(isl_ctx
*ctx
,
3367 isl_pw_qpolynomial
*pwqp
;
3368 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3371 pwqp
= isl_stream_read_pw_qpolynomial(s
);
3376 __isl_give isl_pw_qpolynomial
*isl_pw_qpolynomial_read_from_file(isl_ctx
*ctx
,
3379 isl_pw_qpolynomial
*pwqp
;
3380 isl_stream
*s
= isl_stream_new_file(ctx
, input
);
3383 pwqp
= isl_stream_read_pw_qpolynomial(s
);
3388 /* Is the next token an identifer not in "v"?
3390 static int next_is_fresh_ident(__isl_keep isl_stream
*s
, struct vars
*v
)
3394 struct isl_token
*tok
;
3396 tok
= isl_stream_next_token(s
);
3399 fresh
= tok
->type
== ISL_TOKEN_IDENT
&& vars_pos(v
, tok
->u
.s
, -1) >= n
;
3400 isl_stream_push_token(s
, tok
);
3402 vars_drop(v
, v
->n
- n
);
3407 /* First read the domain of the affine expression, which may be
3408 * a parameter space or a set.
3409 * The tricky part is that we don't know if the domain is a set or not,
3410 * so when we are trying to read the domain, we may actually be reading
3411 * the affine expression itself (defined on a parameter domains)
3412 * If the tuple we are reading is named, we assume it's the domain.
3413 * Also, if inside the tuple, the first thing we find is a nested tuple
3414 * or a new identifier, we again assume it's the domain.
3415 * Finally, if the tuple is empty, then it must be the domain
3416 * since it does not contain an affine expression.
3417 * Otherwise, we assume we are reading an affine expression.
3419 static __isl_give isl_set
*read_aff_domain(__isl_keep isl_stream
*s
,
3420 __isl_take isl_set
*dom
, struct vars
*v
)
3422 struct isl_token
*tok
, *tok2
;
3425 tok
= isl_stream_next_token(s
);
3426 if (tok
&& (tok
->type
== ISL_TOKEN_IDENT
|| tok
->is_keyword
)) {
3427 isl_stream_push_token(s
, tok
);
3428 return read_map_tuple(s
, dom
, isl_dim_set
, v
, 0, 0);
3430 if (!tok
|| tok
->type
!= '[') {
3431 isl_stream_error(s
, tok
, "expecting '['");
3434 tok2
= isl_stream_next_token(s
);
3435 is_empty
= tok2
&& tok2
->type
== ']';
3437 isl_stream_push_token(s
, tok2
);
3438 if (is_empty
|| next_is_tuple(s
) || next_is_fresh_ident(s
, v
)) {
3439 isl_stream_push_token(s
, tok
);
3440 dom
= read_map_tuple(s
, dom
, isl_dim_set
, v
, 0, 0);
3442 isl_stream_push_token(s
, tok
);
3447 isl_stream_push_token(s
, tok
);
3452 /* Read an affine expression from "s".
3454 __isl_give isl_aff
*isl_stream_read_aff(__isl_keep isl_stream
*s
)
3460 ma
= isl_stream_read_multi_aff(s
);
3461 dim
= isl_multi_aff_dim(ma
, isl_dim_out
);
3465 isl_die(s
->ctx
, isl_error_invalid
,
3466 "expecting single affine expression",
3469 aff
= isl_multi_aff_get_aff(ma
, 0);
3470 isl_multi_aff_free(ma
);
3473 isl_multi_aff_free(ma
);
3477 /* Read a piecewise affine expression from "s" with domain (space) "dom".
3479 static __isl_give isl_pw_aff
*read_pw_aff_with_dom(__isl_keep isl_stream
*s
,
3480 __isl_take isl_set
*dom
, struct vars
*v
)
3482 isl_pw_aff
*pwaff
= NULL
;
3484 if (!isl_set_is_params(dom
) && isl_stream_eat(s
, ISL_TOKEN_TO
))
3487 if (isl_stream_eat(s
, '['))
3490 pwaff
= accept_affine(s
, isl_set_get_space(dom
), v
);
3492 if (isl_stream_eat(s
, ']'))
3495 dom
= read_optional_formula(s
, dom
, v
, 0);
3496 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
3501 isl_pw_aff_free(pwaff
);
3505 __isl_give isl_pw_aff
*isl_stream_read_pw_aff(__isl_keep isl_stream
*s
)
3508 isl_set
*dom
= NULL
;
3510 isl_pw_aff
*pa
= NULL
;
3513 v
= vars_new(s
->ctx
);
3517 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
3518 if (next_is_tuple(s
)) {
3519 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
3520 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
3523 if (isl_stream_eat(s
, '{'))
3527 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
3528 pa
= read_pw_aff_with_dom(s
, aff_dom
, v
);
3529 vars_drop(v
, v
->n
- n
);
3531 while (isl_stream_eat_if_available(s
, ';')) {
3535 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
3536 pa_i
= read_pw_aff_with_dom(s
, aff_dom
, v
);
3537 vars_drop(v
, v
->n
- n
);
3539 pa
= isl_pw_aff_union_add(pa
, pa_i
);
3542 if (isl_stream_eat(s
, '}'))
3551 isl_pw_aff_free(pa
);
3555 __isl_give isl_aff
*isl_aff_read_from_str(isl_ctx
*ctx
, const char *str
)
3558 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3561 aff
= isl_stream_read_aff(s
);
3566 __isl_give isl_pw_aff
*isl_pw_aff_read_from_str(isl_ctx
*ctx
, const char *str
)
3569 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3572 pa
= isl_stream_read_pw_aff(s
);
3577 /* Extract an isl_multi_pw_aff with domain space "dom_space"
3578 * from a tuple "tuple" read by read_tuple.
3580 * Note that the function read_tuple accepts tuples where some output or
3581 * set dimensions are defined in terms of other output or set dimensions
3582 * since this function is also used to read maps. As a special case,
3583 * read_tuple also accept dimensions that are defined in terms of themselves
3584 * (i.e., that are not defined).
3585 * These cases are not allowed when extracting an isl_multi_pw_aff so check
3586 * that the definitions of the output/set dimensions do not involve any
3587 * output/set dimensions.
3588 * Finally, drop the output dimensions from the domain of the result
3589 * of read_tuple (which is of the form [input, output] -> [output],
3590 * with anonymous domain) and reset the space.
3592 static __isl_give isl_multi_pw_aff
*extract_mpa_from_tuple(
3593 __isl_take isl_space
*dom_space
, __isl_keep isl_multi_pw_aff
*tuple
)
3598 isl_multi_pw_aff
*mpa
;
3600 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
3601 dim
= isl_space_dim(dom_space
, isl_dim_all
);
3602 if (n
< 0 || dim
< 0)
3603 dom_space
= isl_space_free(dom_space
);
3604 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
3605 space
= isl_space_align_params(space
, isl_space_copy(dom_space
));
3606 if (!isl_space_is_params(dom_space
))
3607 space
= isl_space_map_from_domain_and_range(
3608 isl_space_copy(dom_space
), space
);
3609 isl_space_free(dom_space
);
3610 mpa
= isl_multi_pw_aff_alloc(space
);
3612 for (i
= 0; i
< n
; ++i
) {
3614 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
3616 return isl_multi_pw_aff_free(mpa
);
3617 if (isl_pw_aff_involves_dims(pa
, isl_dim_in
, dim
, i
+ 1)) {
3618 isl_ctx
*ctx
= isl_pw_aff_get_ctx(pa
);
3619 isl_pw_aff_free(pa
);
3620 isl_die(ctx
, isl_error_invalid
,
3621 "not an affine expression",
3622 return isl_multi_pw_aff_free(mpa
));
3624 pa
= isl_pw_aff_drop_dims(pa
, isl_dim_in
, dim
, n
);
3625 space
= isl_multi_pw_aff_get_domain_space(mpa
);
3626 pa
= isl_pw_aff_reset_domain_space(pa
, space
);
3627 mpa
= isl_multi_pw_aff_set_pw_aff(mpa
, i
, pa
);
3633 /* Read a tuple of affine expressions, together with optional constraints
3634 * on the domain from "s". "dom" represents the initial constraints
3637 * The isl_multi_aff may live in either a set or a map space.
3638 * First read the first tuple and check if it is followed by a "->".
3639 * If so, convert the tuple into the domain of the isl_multi_pw_aff and
3640 * read in the next tuple. This tuple (or the first tuple if it was
3641 * not followed by a "->") is then converted into an isl_multi_pw_aff
3642 * through a call to extract_mpa_from_tuple.
3643 * The result is converted to an isl_pw_multi_aff and
3644 * its domain is intersected with the domain.
3646 static __isl_give isl_pw_multi_aff
*read_conditional_multi_aff(
3647 __isl_keep isl_stream
*s
, __isl_take isl_set
*dom
, struct vars
*v
)
3649 isl_multi_pw_aff
*tuple
;
3650 isl_multi_pw_aff
*mpa
;
3651 isl_pw_multi_aff
*pma
;
3654 tuple
= read_tuple(s
, v
, 0, 0);
3657 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TO
)) {
3658 isl_map
*map
= map_from_tuple(tuple
, dom
, isl_dim_in
, v
, 0);
3659 dom
= isl_map_domain(map
);
3660 tuple
= read_tuple(s
, v
, 0, 0);
3664 mpa
= extract_mpa_from_tuple(isl_set_get_space(dom
), tuple
);
3665 isl_multi_pw_aff_free(tuple
);
3667 dom
= isl_set_free(dom
);
3669 dom
= read_optional_formula(s
, dom
, v
, 0);
3671 vars_drop(v
, v
->n
- n
);
3673 pma
= isl_pw_multi_aff_from_multi_pw_aff(mpa
);
3674 pma
= isl_pw_multi_aff_intersect_domain(pma
, dom
);
3682 /* Read an isl_union_pw_multi_aff from "s".
3684 * In particular, first read the parameters and then read a sequence
3685 * of zero or more tuples of affine expressions with optional conditions and
3688 __isl_give isl_union_pw_multi_aff
*isl_stream_read_union_pw_multi_aff(
3689 __isl_keep isl_stream
*s
)
3693 isl_union_pw_multi_aff
*upma
= NULL
;
3695 v
= vars_new(s
->ctx
);
3699 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
3700 if (next_is_tuple(s
)) {
3701 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
3702 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
3705 if (isl_stream_eat(s
, '{'))
3708 upma
= isl_union_pw_multi_aff_empty(isl_set_get_space(dom
));
3711 isl_pw_multi_aff
*pma
;
3712 isl_union_pw_multi_aff
*upma2
;
3714 if (isl_stream_next_token_is(s
, '}'))
3717 pma
= read_conditional_multi_aff(s
, isl_set_copy(dom
), v
);
3718 upma2
= isl_union_pw_multi_aff_from_pw_multi_aff(pma
);
3719 upma
= isl_union_pw_multi_aff_union_add(upma
, upma2
);
3722 } while (isl_stream_eat_if_available(s
, ';'));
3724 if (isl_stream_eat(s
, '}'))
3731 isl_union_pw_multi_aff_free(upma
);
3737 /* Read an isl_pw_multi_aff from "s".
3739 * Read a more generic isl_union_pw_multi_aff first and
3740 * then check that the result lives in a single space.
3742 __isl_give isl_pw_multi_aff
*isl_stream_read_pw_multi_aff(
3743 __isl_keep isl_stream
*s
)
3745 isl_bool single_space
;
3746 isl_union_pw_multi_aff
*upma
;
3748 upma
= isl_stream_read_union_pw_multi_aff(s
);
3749 single_space
= isl_union_pw_multi_aff_isa_pw_multi_aff(upma
);
3750 if (single_space
< 0)
3751 upma
= isl_union_pw_multi_aff_free(upma
);
3752 else if (!single_space
)
3753 isl_die(s
->ctx
, isl_error_invalid
,
3754 "expecting expression in single space",
3755 upma
= isl_union_pw_multi_aff_free(upma
));
3756 return isl_union_pw_multi_aff_as_pw_multi_aff(upma
);
3759 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_read_from_str(isl_ctx
*ctx
,
3762 isl_pw_multi_aff
*pma
;
3763 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3766 pma
= isl_stream_read_pw_multi_aff(s
);
3771 /* Read an isl_union_pw_multi_aff from "str".
3773 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_read_from_str(
3774 isl_ctx
*ctx
, const char *str
)
3776 isl_union_pw_multi_aff
*upma
;
3777 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3780 upma
= isl_stream_read_union_pw_multi_aff(s
);
3785 /* Assuming "pa" represents a single affine expression defined on a universe
3786 * domain, extract this affine expression.
3788 static __isl_give isl_aff
*aff_from_pw_aff(__isl_take isl_pw_aff
*pa
)
3795 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
3796 "expecting single affine expression",
3798 if (!isl_set_plain_is_universe(pa
->p
[0].set
))
3799 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
3800 "expecting universe domain",
3803 aff
= isl_aff_copy(pa
->p
[0].aff
);
3804 isl_pw_aff_free(pa
);
3807 isl_pw_aff_free(pa
);
3814 #include <isl_multi_read_no_explicit_domain_templ.c>
3819 #include <isl_multi_read_no_explicit_domain_templ.c>
3821 /* Read a multi-affine expression from "s".
3822 * If the multi-affine expression has a domain, then the tuple
3823 * representing this domain cannot involve any affine expressions.
3824 * The tuple representing the actual expressions needs to consist
3825 * of only affine expressions. Moreover, these expressions can
3826 * only depend on parameters and input dimensions and not on other
3827 * output dimensions.
3829 __isl_give isl_multi_aff
*isl_stream_read_multi_aff(__isl_keep isl_stream
*s
)
3832 isl_set
*dom
= NULL
;
3833 isl_multi_pw_aff
*tuple
= NULL
;
3836 isl_space
*space
, *dom_space
;
3837 isl_multi_aff
*ma
= NULL
;
3839 v
= vars_new(s
->ctx
);
3843 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
3844 if (next_is_tuple(s
)) {
3845 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
3846 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
3849 if (!isl_set_plain_is_universe(dom
))
3850 isl_die(s
->ctx
, isl_error_invalid
,
3851 "expecting universe parameter domain", goto error
);
3852 if (isl_stream_eat(s
, '{'))
3855 tuple
= read_tuple(s
, v
, 0, 0);
3858 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TO
)) {
3863 has_expr
= tuple_has_expr(tuple
);
3867 isl_die(s
->ctx
, isl_error_invalid
,
3868 "expecting universe domain", goto error
);
3869 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
3870 set
= isl_set_universe(space
);
3871 dom
= isl_set_intersect_params(set
, dom
);
3872 isl_multi_pw_aff_free(tuple
);
3873 tuple
= read_tuple(s
, v
, 0, 0);
3878 if (isl_stream_eat(s
, '}'))
3881 n
= isl_multi_pw_aff_dim(tuple
, isl_dim_out
);
3882 dim
= isl_set_dim(dom
, isl_dim_all
);
3883 if (n
< 0 || dim
< 0)
3885 dom_space
= isl_set_get_space(dom
);
3886 space
= isl_space_range(isl_multi_pw_aff_get_space(tuple
));
3887 space
= isl_space_align_params(space
, isl_space_copy(dom_space
));
3888 if (!isl_space_is_params(dom_space
))
3889 space
= isl_space_map_from_domain_and_range(
3890 isl_space_copy(dom_space
), space
);
3891 isl_space_free(dom_space
);
3892 ma
= isl_multi_aff_alloc(space
);
3894 for (i
= 0; i
< n
; ++i
) {
3897 pa
= isl_multi_pw_aff_get_pw_aff(tuple
, i
);
3898 aff
= aff_from_pw_aff(pa
);
3901 if (isl_aff_involves_dims(aff
, isl_dim_in
, dim
, i
+ 1)) {
3903 isl_die(s
->ctx
, isl_error_invalid
,
3904 "not an affine expression", goto error
);
3906 aff
= isl_aff_drop_dims(aff
, isl_dim_in
, dim
, n
);
3907 space
= isl_multi_aff_get_domain_space(ma
);
3908 aff
= isl_aff_reset_domain_space(aff
, space
);
3909 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3912 isl_multi_pw_aff_free(tuple
);
3917 isl_multi_pw_aff_free(tuple
);
3920 isl_multi_aff_free(ma
);
3924 __isl_give isl_multi_aff
*isl_multi_aff_read_from_str(isl_ctx
*ctx
,
3927 isl_multi_aff
*maff
;
3928 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
3931 maff
= isl_stream_read_multi_aff(s
);
3936 /* Read an isl_multi_pw_aff from "s".
3938 * The input format is similar to that of map, except that any conditions
3939 * on the domains should be specified inside the tuple since each
3940 * piecewise affine expression may have a different domain.
3941 * However, additional, shared conditions can also be specified.
3942 * This is especially useful for setting the explicit domain
3943 * of a zero-dimensional isl_multi_pw_aff.
3945 * Since we do not know in advance if the isl_multi_pw_aff lives
3946 * in a set or a map space, we first read the first tuple and check
3947 * if it is followed by a "->". If so, we convert the tuple into
3948 * the domain of the isl_multi_pw_aff and read in the next tuple.
3949 * This tuple (or the first tuple if it was not followed by a "->")
3950 * is then converted into the isl_multi_pw_aff through a call
3951 * to extract_mpa_from_tuple and the domain of the result
3952 * is intersected with the domain.
3954 __isl_give isl_multi_pw_aff
*isl_stream_read_multi_pw_aff(
3955 __isl_keep isl_stream
*s
)
3958 isl_set
*dom
= NULL
;
3959 isl_multi_pw_aff
*tuple
= NULL
;
3960 isl_multi_pw_aff
*mpa
= NULL
;
3962 v
= vars_new(s
->ctx
);
3966 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
3967 if (next_is_tuple(s
)) {
3968 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
3969 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
3972 if (isl_stream_eat(s
, '{'))
3975 tuple
= read_tuple(s
, v
, 0, 0);
3978 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TO
)) {
3979 isl_map
*map
= map_from_tuple(tuple
, dom
, isl_dim_in
, v
, 0);
3980 dom
= isl_map_domain(map
);
3981 tuple
= read_tuple(s
, v
, 0, 0);
3986 if (isl_stream_eat_if_available(s
, ':'))
3987 dom
= read_formula(s
, v
, dom
, 0);
3989 if (isl_stream_eat(s
, '}'))
3992 mpa
= extract_mpa_from_tuple(isl_set_get_space(dom
), tuple
);
3994 isl_multi_pw_aff_free(tuple
);
3996 mpa
= isl_multi_pw_aff_intersect_domain(mpa
, dom
);
3999 isl_multi_pw_aff_free(tuple
);
4002 isl_multi_pw_aff_free(mpa
);
4006 /* Read an isl_multi_pw_aff from "str".
4008 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_read_from_str(isl_ctx
*ctx
,
4011 isl_multi_pw_aff
*mpa
;
4012 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
4015 mpa
= isl_stream_read_multi_pw_aff(s
);
4020 /* Read the body of an isl_union_pw_aff from "s" with parameter domain "dom".
4022 static __isl_give isl_union_pw_aff
*read_union_pw_aff_with_dom(
4023 __isl_keep isl_stream
*s
, __isl_take isl_set
*dom
, struct vars
*v
)
4026 isl_union_pw_aff
*upa
= NULL
;
4031 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
4032 pa
= read_pw_aff_with_dom(s
, aff_dom
, v
);
4033 vars_drop(v
, v
->n
- n
);
4035 upa
= isl_union_pw_aff_from_pw_aff(pa
);
4037 while (isl_stream_eat_if_available(s
, ';')) {
4039 isl_union_pw_aff
*upa_i
;
4042 aff_dom
= read_aff_domain(s
, isl_set_copy(dom
), v
);
4043 pa_i
= read_pw_aff_with_dom(s
, aff_dom
, v
);
4044 vars_drop(v
, v
->n
- n
);
4046 upa_i
= isl_union_pw_aff_from_pw_aff(pa_i
);
4047 upa
= isl_union_pw_aff_union_add(upa
, upa_i
);
4054 /* Read an isl_union_pw_aff from "s".
4056 * First check if there are any paramters, then read in the opening brace
4057 * and use read_union_pw_aff_with_dom to read in the body of
4058 * the isl_union_pw_aff. Finally, read the closing brace.
4060 __isl_give isl_union_pw_aff
*isl_stream_read_union_pw_aff(
4061 __isl_keep isl_stream
*s
)
4065 isl_union_pw_aff
*upa
= NULL
;
4067 v
= vars_new(s
->ctx
);
4071 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
4072 if (next_is_tuple(s
)) {
4073 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
4074 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
4077 if (isl_stream_eat(s
, '{'))
4080 upa
= read_union_pw_aff_with_dom(s
, isl_set_copy(dom
), v
);
4082 if (isl_stream_eat(s
, '}'))
4091 isl_union_pw_aff_free(upa
);
4095 /* Read an isl_union_pw_aff from "str".
4097 __isl_give isl_union_pw_aff
*isl_union_pw_aff_read_from_str(isl_ctx
*ctx
,
4100 isl_union_pw_aff
*upa
;
4101 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
4104 upa
= isl_stream_read_union_pw_aff(s
);
4109 /* This function is called for each element in a tuple inside
4110 * isl_stream_read_multi_union_pw_aff.
4112 * Read a '{', the union piecewise affine expression body and a '}' and
4113 * add the isl_union_pw_aff to *list.
4115 static __isl_give isl_space
*read_union_pw_aff_el(__isl_keep isl_stream
*s
,
4116 struct vars
*v
, __isl_take isl_space
*space
, int rational
, void *user
)
4119 isl_union_pw_aff
*upa
;
4120 isl_union_pw_aff_list
**list
= (isl_union_pw_aff_list
**) user
;
4122 dom
= isl_set_universe(isl_space_params(isl_space_copy(space
)));
4123 if (isl_stream_eat(s
, '{'))
4125 upa
= read_union_pw_aff_with_dom(s
, dom
, v
);
4126 *list
= isl_union_pw_aff_list_add(*list
, upa
);
4127 if (isl_stream_eat(s
, '}'))
4128 return isl_space_free(space
);
4130 return isl_space_free(space
);
4134 return isl_space_free(space
);
4137 /* Do the next tokens in "s" correspond to an empty tuple?
4138 * In particular, does the stream start with a '[', followed by a ']',
4139 * not followed by a "->"?
4141 static int next_is_empty_tuple(__isl_keep isl_stream
*s
)
4143 struct isl_token
*tok
, *tok2
, *tok3
;
4144 int is_empty_tuple
= 0;
4146 tok
= isl_stream_next_token(s
);
4149 if (tok
->type
!= '[') {
4150 isl_stream_push_token(s
, tok
);
4154 tok2
= isl_stream_next_token(s
);
4155 if (tok2
&& tok2
->type
== ']') {
4156 tok3
= isl_stream_next_token(s
);
4157 is_empty_tuple
= !tok
|| tok
->type
!= ISL_TOKEN_TO
;
4159 isl_stream_push_token(s
, tok3
);
4162 isl_stream_push_token(s
, tok2
);
4163 isl_stream_push_token(s
, tok
);
4165 return is_empty_tuple
;
4168 /* Do the next tokens in "s" correspond to a tuple of parameters?
4169 * In particular, does the stream start with a '[' that is not
4170 * followed by a '{' or a nested tuple?
4172 static int next_is_param_tuple(__isl_keep isl_stream
*s
)
4174 struct isl_token
*tok
, *tok2
;
4177 tok
= isl_stream_next_token(s
);
4180 if (tok
->type
!= '[' || next_is_tuple(s
)) {
4181 isl_stream_push_token(s
, tok
);
4185 tok2
= isl_stream_next_token(s
);
4186 is_tuple
= tok2
&& tok2
->type
!= '{';
4188 isl_stream_push_token(s
, tok2
);
4189 isl_stream_push_token(s
, tok
);
4194 /* Read the core of a body of an isl_multi_union_pw_aff from "s",
4195 * i.e., everything except the parameter specification and
4196 * without shared domain constraints.
4197 * "v" contains a description of the identifiers parsed so far.
4198 * The parameters, if any, are specified by "space".
4200 * The body is of the form
4202 * [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4204 * Read the tuple, collecting the individual isl_union_pw_aff
4205 * elements in a list and construct the result from the tuple space and
4208 static __isl_give isl_multi_union_pw_aff
*read_multi_union_pw_aff_body_core(
4209 __isl_keep isl_stream
*s
, struct vars
*v
, __isl_take isl_space
*space
)
4211 isl_union_pw_aff_list
*list
;
4212 isl_multi_union_pw_aff
*mupa
;
4214 list
= isl_union_pw_aff_list_alloc(s
->ctx
, 0);
4215 space
= read_tuple_space(s
, v
, space
, 1, 0,
4216 &read_union_pw_aff_el
, &list
);
4217 mupa
= isl_multi_union_pw_aff_from_union_pw_aff_list(space
, list
);
4222 /* Read the body of an isl_union_set from "s",
4223 * i.e., everything except the parameter specification.
4224 * "v" contains a description of the identifiers parsed so far.
4225 * The parameters, if any, are specified by "space".
4227 * First read a generic disjunction of object bodies and then try and extract
4228 * an isl_union_set from that.
4230 static __isl_give isl_union_set
*read_union_set_body(__isl_keep isl_stream
*s
,
4231 struct vars
*v
, __isl_take isl_space
*space
)
4233 struct isl_obj obj
= { isl_obj_set
, NULL
};
4236 map
= isl_set_universe(space
);
4237 if (isl_stream_eat(s
, '{') < 0)
4239 obj
= obj_read_disjuncts(s
, v
, map
);
4240 if (isl_stream_eat(s
, '}') < 0)
4244 return extract_union_set(s
->ctx
, obj
);
4246 obj
.type
->free(obj
.v
);
4251 /* Read the body of an isl_multi_union_pw_aff from "s",
4252 * i.e., everything except the parameter specification.
4253 * "v" contains a description of the identifiers parsed so far.
4254 * The parameters, if any, are specified by "space".
4256 * In particular, handle the special case with shared domain constraints.
4257 * These are specified as
4261 * and are especially useful for setting the explicit domain
4262 * of a zero-dimensional isl_multi_union_pw_aff.
4263 * The core isl_multi_union_pw_aff body ([...]) is read by
4264 * read_multi_union_pw_aff_body_core.
4266 static __isl_give isl_multi_union_pw_aff
*read_multi_union_pw_aff_body(
4267 __isl_keep isl_stream
*s
, struct vars
*v
, __isl_take isl_space
*space
)
4269 isl_multi_union_pw_aff
*mupa
;
4271 if (!isl_stream_next_token_is(s
, '('))
4272 return read_multi_union_pw_aff_body_core(s
, v
, space
);
4274 if (isl_stream_eat(s
, '(') < 0)
4276 mupa
= read_multi_union_pw_aff_body_core(s
, v
, isl_space_copy(space
));
4277 if (isl_stream_eat_if_available(s
, ':')) {
4280 dom
= read_union_set_body(s
, v
, space
);
4281 mupa
= isl_multi_union_pw_aff_intersect_domain(mupa
, dom
);
4283 isl_space_free(space
);
4285 if (isl_stream_eat(s
, ')') < 0)
4286 return isl_multi_union_pw_aff_free(mupa
);
4290 isl_space_free(space
);
4294 /* Read an isl_multi_union_pw_aff from "s".
4296 * The input has the form
4298 * [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4302 * [..] -> [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4304 * Additionally, a shared domain may be specified as
4310 * [..] -> ([..] : ...)
4312 * The first case is handled by the caller, the second case
4313 * is handled by read_multi_union_pw_aff_body.
4315 * We first check for the special case of an empty tuple "[]".
4316 * Then we check if there are any parameters.
4317 * Finally, read the tuple and construct the result.
4319 static __isl_give isl_multi_union_pw_aff
*read_multi_union_pw_aff_core(
4320 __isl_keep isl_stream
*s
)
4323 isl_set
*dom
= NULL
;
4325 isl_multi_union_pw_aff
*mupa
= NULL
;
4327 if (next_is_empty_tuple(s
)) {
4328 if (isl_stream_eat(s
, '['))
4330 if (isl_stream_eat(s
, ']'))
4332 space
= isl_space_set_alloc(s
->ctx
, 0, 0);
4333 return isl_multi_union_pw_aff_zero(space
);
4336 v
= vars_new(s
->ctx
);
4340 dom
= isl_set_universe(isl_space_params_alloc(s
->ctx
, 0));
4341 if (next_is_param_tuple(s
)) {
4342 dom
= read_map_tuple(s
, dom
, isl_dim_param
, v
, 1, 0);
4343 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
4346 space
= isl_set_get_space(dom
);
4348 mupa
= read_multi_union_pw_aff_body(s
, v
, space
);
4356 isl_multi_union_pw_aff_free(mupa
);
4360 /* Read an isl_multi_union_pw_aff from "s".
4362 * In particular, handle the special case with shared domain constraints.
4363 * These are specified as
4367 * and are especially useful for setting the explicit domain
4368 * of a zero-dimensional isl_multi_union_pw_aff.
4369 * The core isl_multi_union_pw_aff ([...]) is read by
4370 * read_multi_union_pw_aff_core.
4372 __isl_give isl_multi_union_pw_aff
*isl_stream_read_multi_union_pw_aff(
4373 __isl_keep isl_stream
*s
)
4375 isl_multi_union_pw_aff
*mupa
;
4377 if (!isl_stream_next_token_is(s
, '('))
4378 return read_multi_union_pw_aff_core(s
);
4380 if (isl_stream_eat(s
, '(') < 0)
4382 mupa
= read_multi_union_pw_aff_core(s
);
4383 if (isl_stream_eat_if_available(s
, ':')) {
4386 dom
= isl_stream_read_union_set(s
);
4387 mupa
= isl_multi_union_pw_aff_intersect_domain(mupa
, dom
);
4389 if (isl_stream_eat(s
, ')') < 0)
4390 return isl_multi_union_pw_aff_free(mupa
);
4394 /* Read an isl_multi_union_pw_aff from "str".
4396 __isl_give isl_multi_union_pw_aff
*isl_multi_union_pw_aff_read_from_str(
4397 isl_ctx
*ctx
, const char *str
)
4399 isl_multi_union_pw_aff
*mupa
;
4400 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
4403 mupa
= isl_stream_read_multi_union_pw_aff(s
);
4408 __isl_give isl_union_pw_qpolynomial
*isl_stream_read_union_pw_qpolynomial(
4409 __isl_keep isl_stream
*s
)
4414 if (obj
.type
== isl_obj_pw_qpolynomial
) {
4415 obj
.type
= isl_obj_union_pw_qpolynomial
;
4416 obj
.v
= isl_union_pw_qpolynomial_from_pw_qpolynomial(obj
.v
);
4419 isl_assert(s
->ctx
, obj
.type
== isl_obj_union_pw_qpolynomial
,
4424 obj
.type
->free(obj
.v
);
4428 __isl_give isl_union_pw_qpolynomial
*isl_union_pw_qpolynomial_read_from_str(
4429 isl_ctx
*ctx
, const char *str
)
4431 isl_union_pw_qpolynomial
*upwqp
;
4432 isl_stream
*s
= isl_stream_new_str(ctx
, str
);
4435 upwqp
= isl_stream_read_union_pw_qpolynomial(s
);