2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
5 * Use of this software is governed by the GNU LGPLv2.1 license
7 * Written by Sven Verdoolaege, K.U.Leuven, Departement
8 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
9 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
10 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
17 #include <isl_ctx_private.h>
18 #include <isl_map_private.h>
22 #include <isl/stream.h>
24 #include "isl_polynomial_private.h"
25 #include <isl/union_map.h>
26 #include <isl_mat_private.h>
32 struct variable
*next
;
41 static struct vars
*vars_new(struct isl_ctx
*ctx
)
44 v
= isl_alloc_type(ctx
, struct vars
);
53 static void variable_free(struct variable
*var
)
56 struct variable
*next
= var
->next
;
57 isl_vec_free(var
->def
);
64 static void vars_free(struct vars
*v
)
72 static void vars_drop(struct vars
*v
, int n
)
83 struct variable
*next
= var
->next
;
84 isl_vec_free(var
->def
);
92 static struct variable
*variable_new(struct vars
*v
, const char *name
, int len
,
96 var
= isl_alloc_type(v
->ctx
, struct variable
);
99 var
->name
= strdup(name
);
100 var
->name
[len
] = '\0';
110 static int vars_pos(struct vars
*v
, const char *s
, int len
)
117 for (q
= v
->v
; q
; q
= q
->next
) {
118 if (strncmp(q
->name
, s
, len
) == 0 && q
->name
[len
] == '\0')
125 v
->v
= variable_new(v
, s
, len
, v
->n
);
133 static int vars_add_anon(struct vars
*v
)
135 v
->v
= variable_new(v
, "", 0, v
->n
);
144 static __isl_give isl_basic_map
*set_name(__isl_take isl_basic_map
*bmap
,
145 enum isl_dim_type type
, unsigned pos
, char *name
)
154 prime
= strchr(name
, '\'');
157 bmap
= isl_basic_map_set_dim_name(bmap
, type
, pos
, name
);
164 /* Obtain next token, with some preprocessing.
165 * In particular, evaluate expressions of the form x^y,
166 * with x and y values.
168 static struct isl_token
*next_token(struct isl_stream
*s
)
170 struct isl_token
*tok
, *tok2
;
172 tok
= isl_stream_next_token(s
);
173 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
)
175 if (!isl_stream_eat_if_available(s
, '^'))
177 tok2
= isl_stream_next_token(s
);
178 if (!tok2
|| tok2
->type
!= ISL_TOKEN_VALUE
) {
179 isl_stream_error(s
, tok2
, "expecting constant value");
183 isl_int_pow_ui(tok
->u
.v
, tok
->u
.v
, isl_int_get_ui(tok2
->u
.v
));
185 isl_token_free(tok2
);
189 isl_token_free(tok2
);
193 static int accept_cst_factor(struct isl_stream
*s
, isl_int
*f
)
195 struct isl_token
*tok
;
198 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
199 isl_stream_error(s
, tok
, "expecting constant value");
203 isl_int_mul(*f
, *f
, tok
->u
.v
);
207 if (isl_stream_eat_if_available(s
, '*'))
208 return accept_cst_factor(s
, f
);
216 /* Given an affine expression aff, return an affine expression
217 * for aff % d, with d the next token on the stream, which is
218 * assumed to be a constant.
220 * We introduce an integer division q = [aff/d] and the result
221 * is set to aff - d q.
223 static __isl_give isl_vec
*affine_mod(struct isl_stream
*s
,
224 struct vars
*v
, __isl_take isl_vec
*aff
)
226 struct isl_token
*tok
;
227 struct variable
*var
;
231 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
232 isl_stream_error(s
, tok
, "expecting constant value");
236 if (vars_add_anon(v
) < 0)
241 var
->def
= isl_vec_alloc(s
->ctx
, 2 + v
->n
);
244 isl_seq_cpy(var
->def
->el
+ 1, aff
->el
, aff
->size
);
245 isl_int_set_si(var
->def
->el
[1 + aff
->size
], 0);
246 isl_int_set(var
->def
->el
[0], tok
->u
.v
);
248 mod
= isl_vec_alloc(v
->ctx
, 1 + v
->n
);
252 isl_seq_cpy(mod
->el
, aff
->el
, aff
->size
);
253 isl_int_neg(mod
->el
[aff
->size
], tok
->u
.v
);
264 static struct isl_vec
*accept_affine(struct isl_stream
*s
, struct vars
*v
);
265 static int read_div_definition(struct isl_stream
*s
, struct vars
*v
);
267 static __isl_give isl_vec
*accept_affine_factor(struct isl_stream
*s
,
270 struct isl_token
*tok
= NULL
;
275 isl_stream_error(s
, NULL
, "unexpected EOF");
278 if (tok
->type
== ISL_TOKEN_IDENT
) {
280 int pos
= vars_pos(v
, tok
->u
.s
, -1);
284 isl_stream_error(s
, tok
, "unknown identifier");
288 aff
= isl_vec_alloc(v
->ctx
, 1 + v
->n
);
291 isl_seq_clr(aff
->el
, aff
->size
);
292 isl_int_set_si(aff
->el
[1 + pos
], 1);
294 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
295 if (isl_stream_eat_if_available(s
, '*')) {
296 aff
= accept_affine_factor(s
, v
);
297 aff
= isl_vec_scale(aff
, tok
->u
.v
);
299 aff
= isl_vec_alloc(v
->ctx
, 1 + v
->n
);
302 isl_seq_clr(aff
->el
, aff
->size
);
303 isl_int_set(aff
->el
[0], tok
->u
.v
);
306 } else if (tok
->type
== '(') {
309 aff
= accept_affine(s
, v
);
312 if (isl_stream_eat(s
, ')'))
314 } else if (tok
->type
== '[') {
315 if (vars_add_anon(v
) < 0)
317 aff
= isl_vec_alloc(v
->ctx
, 1 + v
->n
);
320 isl_seq_clr(aff
->el
, aff
->size
);
321 isl_int_set_si(aff
->el
[1 + v
->n
- 1], 1);
322 isl_stream_push_token(s
, tok
);
324 if (read_div_definition(s
, v
) < 0)
326 aff
= isl_vec_zero_extend(aff
, 1 + v
->n
);
328 isl_stream_error(s
, tok
, "expecting factor");
331 if (isl_stream_eat_if_available(s
, '%'))
332 return affine_mod(s
, v
, aff
);
333 if (isl_stream_eat_if_available(s
, '*')) {
336 isl_int_set_si(f
, 1);
337 if (accept_cst_factor(s
, &f
) < 0) {
341 aff
= isl_vec_scale(aff
, f
);
353 static struct isl_vec
*accept_affine(struct isl_stream
*s
, struct vars
*v
)
355 struct isl_token
*tok
= NULL
;
359 aff
= isl_vec_alloc(v
->ctx
, 1 + v
->n
);
362 isl_seq_clr(aff
->el
, aff
->size
);
367 isl_stream_error(s
, NULL
, "unexpected EOF");
370 if (tok
->type
== '-') {
375 if (tok
->type
== '(' || tok
->type
== '[' ||
376 tok
->type
== ISL_TOKEN_IDENT
) {
378 isl_stream_push_token(s
, tok
);
380 aff2
= accept_affine_factor(s
, v
);
382 aff2
= isl_vec_scale(aff2
, s
->ctx
->negone
);
383 aff
= isl_vec_zero_extend(aff
, 1 + v
->n
);
384 aff
= isl_vec_add(aff
, aff2
);
388 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
390 isl_int_neg(tok
->u
.v
, tok
->u
.v
);
391 if (isl_stream_eat_if_available(s
, '*') ||
392 isl_stream_next_token_is(s
, ISL_TOKEN_IDENT
)) {
394 aff2
= accept_affine_factor(s
, v
);
395 aff2
= isl_vec_scale(aff2
, tok
->u
.v
);
396 aff
= isl_vec_zero_extend(aff
, 1 + v
->n
);
397 aff
= isl_vec_add(aff
, aff2
);
401 isl_int_add(aff
->el
[0], aff
->el
[0], tok
->u
.v
);
405 isl_stream_error(s
, tok
, "unexpected isl_token");
406 isl_stream_push_token(s
, tok
);
413 if (tok
&& tok
->type
== '-') {
416 } else if (tok
&& tok
->type
== '+') {
419 } else if (tok
&& tok
->type
== ISL_TOKEN_VALUE
&&
420 isl_int_is_neg(tok
->u
.v
)) {
421 isl_stream_push_token(s
, tok
);
424 isl_stream_push_token(s
, tok
);
436 /* Add any variables in the variable list "v" that are not already in "bmap"
437 * as existentially quantified variables in "bmap".
439 static __isl_give isl_basic_map
*add_divs(__isl_take isl_basic_map
*bmap
,
444 struct variable
*var
;
446 extra
= v
->n
- isl_basic_map_total_dim(bmap
);
451 bmap
= isl_basic_map_extend_dim(bmap
, isl_basic_map_get_dim(bmap
),
452 extra
, 0, 2 * extra
);
454 for (i
= 0; i
< extra
; ++i
)
455 if (isl_basic_map_alloc_div(bmap
) < 0)
458 for (i
= 0, var
= v
->v
; i
< extra
; ++i
, var
= var
->next
) {
459 int k
= bmap
->n_div
- 1 - i
;
461 isl_seq_cpy(bmap
->div
[k
], var
->def
->el
, var
->def
->size
);
462 isl_seq_clr(bmap
->div
[k
] + var
->def
->size
,
463 2 + v
->n
- var
->def
->size
);
465 if (isl_basic_map_add_div_constraints(bmap
, k
) < 0)
471 isl_basic_map_free(bmap
);
475 static __isl_give isl_basic_map
*read_var_def(struct isl_stream
*s
,
476 __isl_take isl_basic_map
*bmap
, enum isl_dim_type type
, struct vars
*v
)
479 isl_basic_map
*def
= NULL
;
484 if (vars_add_anon(v
) < 0)
488 vec
= accept_affine(s
, v
);
492 dim
= isl_basic_map_get_dim(bmap
);
493 def
= isl_basic_map_universe(dim
);
494 def
= add_divs(def
, v
);
495 def
= isl_basic_map_extend_constraints(def
, 1, 0);
496 k
= isl_basic_map_alloc_equality(def
);
498 isl_seq_cpy(def
->eq
[k
], vec
->el
, vec
->size
);
499 isl_int_set_si(def
->eq
[k
][1 + n
- 1], -1);
505 vars_drop(v
, v
->n
- n
);
507 def
= isl_basic_map_simplify(def
);
508 def
= isl_basic_map_finalize(def
);
509 bmap
= isl_basic_map_intersect(bmap
, def
);
512 isl_basic_map_free(bmap
);
513 isl_basic_map_free(def
);
517 static __isl_give isl_basic_map
*read_var_list(struct isl_stream
*s
,
518 __isl_take isl_basic_map
*bmap
, enum isl_dim_type type
, struct vars
*v
)
521 struct isl_token
*tok
;
523 while ((tok
= next_token(s
)) != NULL
) {
526 if (tok
->type
== ISL_TOKEN_IDENT
) {
528 int p
= vars_pos(v
, tok
->u
.s
, -1);
535 bmap
= isl_basic_map_add(bmap
, type
, 1);
536 bmap
= set_name(bmap
, type
, i
, v
->v
->name
);
538 } else if (tok
->type
== ISL_TOKEN_IDENT
||
539 tok
->type
== ISL_TOKEN_VALUE
||
542 if (type
== isl_dim_param
) {
543 isl_stream_error(s
, tok
,
544 "expecting unique identifier");
547 isl_stream_push_token(s
, tok
);
549 bmap
= isl_basic_map_add(bmap
, type
, 1);
550 bmap
= read_var_def(s
, bmap
, type
, v
);
554 tok
= isl_stream_next_token(s
);
555 if (!tok
|| tok
->type
!= ',')
562 isl_stream_push_token(s
, tok
);
567 isl_basic_map_free(bmap
);
571 static __isl_give isl_mat
*accept_affine_list(struct isl_stream
*s
,
576 struct isl_token
*tok
= NULL
;
578 vec
= accept_affine(s
, v
);
579 mat
= isl_mat_from_row_vec(vec
);
584 tok
= isl_stream_next_token(s
);
586 isl_stream_error(s
, NULL
, "unexpected EOF");
589 if (tok
->type
!= ',') {
590 isl_stream_push_token(s
, tok
);
595 vec
= accept_affine(s
, v
);
596 mat
= isl_mat_add_zero_cols(mat
, 1 + v
->n
- isl_mat_cols(mat
));
597 mat
= isl_mat_vec_concat(mat
, vec
);
608 static int read_div_definition(struct isl_stream
*s
, struct vars
*v
)
610 struct isl_token
*tok
;
613 struct variable
*var
;
615 if (isl_stream_eat(s
, '['))
618 tok
= isl_stream_next_token(s
);
621 if (tok
->type
== '(') {
625 isl_stream_push_token(s
, tok
);
629 aff
= accept_affine(s
, v
);
633 var
->def
= isl_vec_alloc(s
->ctx
, 2 + v
->n
);
639 isl_seq_cpy(var
->def
->el
+ 1, aff
->el
, aff
->size
);
643 if (seen_paren
&& isl_stream_eat(s
, ')'))
645 if (isl_stream_eat(s
, '/'))
651 if (tok
->type
!= ISL_TOKEN_VALUE
) {
652 isl_stream_error(s
, tok
, "expected denominator");
653 isl_stream_push_token(s
, tok
);
656 isl_int_set(var
->def
->el
[0], tok
->u
.v
);
659 if (isl_stream_eat(s
, ']'))
665 static struct isl_basic_map
*add_div_definition(struct isl_stream
*s
,
666 struct vars
*v
, struct isl_basic_map
*bmap
, int pos
)
668 struct variable
*var
= v
->v
;
669 unsigned o_out
= isl_basic_map_offset(bmap
, isl_dim_out
) - 1;
671 if (read_div_definition(s
, v
) < 0)
674 if (isl_basic_map_add_div_constraints_var(bmap
, o_out
+ pos
,
680 isl_basic_map_free(bmap
);
684 static struct isl_basic_map
*read_defined_var_list(struct isl_stream
*s
,
685 struct vars
*v
, struct isl_basic_map
*bmap
)
687 struct isl_token
*tok
;
689 while ((tok
= isl_stream_next_token(s
)) != NULL
) {
692 unsigned n_out
= isl_basic_map_dim(bmap
, isl_dim_out
);
694 if (tok
->type
!= ISL_TOKEN_IDENT
)
697 p
= vars_pos(v
, tok
->u
.s
, -1);
701 isl_stream_error(s
, tok
, "expecting unique identifier");
705 bmap
= isl_basic_map_cow(bmap
);
706 bmap
= isl_basic_map_add(bmap
, isl_dim_out
, 1);
707 bmap
= isl_basic_map_extend_dim(bmap
, isl_dim_copy(bmap
->dim
),
711 tok
= isl_stream_next_token(s
);
712 if (tok
&& tok
->type
== '=') {
714 bmap
= add_div_definition(s
, v
, bmap
, n_out
);
715 tok
= isl_stream_next_token(s
);
718 if (!tok
|| tok
->type
!= ',')
724 isl_stream_push_token(s
, tok
);
729 isl_basic_map_free(bmap
);
733 static int next_is_tuple(struct isl_stream
*s
)
735 struct isl_token
*tok
;
738 tok
= isl_stream_next_token(s
);
741 if (tok
->type
== '[') {
742 isl_stream_push_token(s
, tok
);
745 if (tok
->type
!= ISL_TOKEN_IDENT
&& !tok
->is_keyword
) {
746 isl_stream_push_token(s
, tok
);
750 is_tuple
= isl_stream_next_token_is(s
, '[');
752 isl_stream_push_token(s
, tok
);
757 static __isl_give isl_basic_map
*read_tuple(struct isl_stream
*s
,
758 __isl_take isl_basic_map
*bmap
, enum isl_dim_type type
, struct vars
*v
);
760 static __isl_give isl_basic_map
*read_nested_tuple(struct isl_stream
*s
,
761 __isl_take isl_basic_map
*bmap
, struct vars
*v
)
763 bmap
= read_tuple(s
, bmap
, isl_dim_in
, v
);
764 if (isl_stream_eat(s
, ISL_TOKEN_TO
))
766 bmap
= read_tuple(s
, bmap
, isl_dim_out
, v
);
767 bmap
= isl_basic_map_from_range(isl_basic_map_wrap(bmap
));
770 isl_basic_map_free(bmap
);
774 static __isl_give isl_basic_map
*read_tuple(struct isl_stream
*s
,
775 __isl_take isl_basic_map
*bmap
, enum isl_dim_type type
, struct vars
*v
)
777 struct isl_token
*tok
;
780 tok
= isl_stream_next_token(s
);
781 if (tok
&& (tok
->type
== ISL_TOKEN_IDENT
|| tok
->is_keyword
)) {
782 name
= strdup(tok
->u
.s
);
786 tok
= isl_stream_next_token(s
);
788 if (!tok
|| tok
->type
!= '[') {
789 isl_stream_error(s
, tok
, "expecting '['");
793 if (type
!= isl_dim_param
&& next_is_tuple(s
)) {
794 isl_dim
*dim
= isl_basic_map_get_dim(bmap
);
795 int nparam
= isl_dim_size(dim
, isl_dim_param
);
796 int n_in
= isl_dim_size(dim
, isl_dim_in
);
797 isl_basic_map
*nested
;
798 if (type
== isl_dim_out
)
799 dim
= isl_dim_move(dim
, isl_dim_param
, nparam
,
800 isl_dim_in
, 0, n_in
);
801 nested
= isl_basic_map_alloc_dim(dim
, 0, 0, 0);
802 nested
= read_nested_tuple(s
, nested
, v
);
803 if (type
== isl_dim_in
) {
804 nested
= isl_basic_map_reverse(nested
);
805 bmap
= isl_basic_map_intersect(nested
, bmap
);
808 dim
= isl_dim_range(isl_basic_map_get_dim(nested
));
809 dim
= isl_dim_drop(dim
, isl_dim_param
, nparam
, n_in
);
810 dim
= isl_dim_join(isl_basic_map_get_dim(bmap
), dim
);
811 bset
= isl_basic_map_domain(bmap
);
812 nested
= isl_basic_map_reset_dim(nested
, dim
);
813 bmap
= isl_basic_map_intersect_domain(nested
, bset
);
816 bmap
= read_var_list(s
, bmap
, type
, v
);
817 tok
= isl_stream_next_token(s
);
818 if (!tok
|| tok
->type
!= ']') {
819 isl_stream_error(s
, tok
, "expecting ']'");
825 bmap
= isl_basic_map_set_tuple_name(bmap
, type
, name
);
833 isl_basic_map_free(bmap
);
837 static __isl_give isl_basic_map
*construct_constraint(
838 __isl_take isl_basic_map
*bmap
, enum isl_token_type type
,
839 isl_int
*left
, isl_int
*right
)
847 len
= 1 + isl_basic_map_total_dim(bmap
);
850 k
= isl_basic_map_alloc_inequality(bmap
);
853 if (type
== ISL_TOKEN_LE
)
854 isl_seq_combine(bmap
->ineq
[k
], ctx
->negone
, left
,
857 else if (type
== ISL_TOKEN_GE
)
858 isl_seq_combine(bmap
->ineq
[k
], ctx
->one
, left
,
861 else if (type
== ISL_TOKEN_LT
) {
862 isl_seq_combine(bmap
->ineq
[k
], ctx
->negone
, left
,
865 isl_int_sub_ui(bmap
->ineq
[k
][0], bmap
->ineq
[k
][0], 1);
866 } else if (type
== ISL_TOKEN_GT
) {
867 isl_seq_combine(bmap
->ineq
[k
], ctx
->one
, left
,
870 isl_int_sub_ui(bmap
->ineq
[k
][0], bmap
->ineq
[k
][0], 1);
872 isl_seq_combine(bmap
->ineq
[k
], ctx
->one
, left
,
875 isl_basic_map_inequality_to_equality(bmap
, k
);
880 isl_basic_map_free(bmap
);
884 static int is_comparator(struct isl_token
*tok
)
901 /* Add any variables in the variable list "v" that are not already in "bmap"
902 * as output variables in "bmap".
904 static __isl_give isl_basic_map
*add_lifted_divs(__isl_take isl_basic_map
*bmap
,
909 struct variable
*var
;
911 extra
= v
->n
- isl_basic_map_total_dim(bmap
);
916 bmap
= isl_basic_map_add(bmap
, isl_dim_out
, extra
);
917 bmap
= isl_basic_map_extend_dim(bmap
, isl_basic_map_get_dim(bmap
),
920 for (i
= 0, var
= v
->v
; i
< extra
; ++i
, var
= var
->next
) {
921 var
->def
= isl_vec_zero_extend(var
->def
, 2 + v
->n
);
924 if (isl_basic_map_add_div_constraints_var(bmap
, var
->pos
,
931 isl_basic_map_free(bmap
);
935 static struct isl_basic_map
*add_constraint(struct isl_stream
*s
,
936 struct vars
*v
, struct isl_basic_map
*bmap
)
939 struct isl_token
*tok
= NULL
;
940 struct isl_mat
*aff1
= NULL
, *aff2
= NULL
;
942 bmap
= isl_basic_map_cow(bmap
);
944 aff1
= accept_affine_list(s
, v
);
947 tok
= isl_stream_next_token(s
);
948 if (!is_comparator(tok
)) {
949 isl_stream_error(s
, tok
, "missing operator");
951 isl_stream_push_token(s
, tok
);
956 aff2
= accept_affine_list(s
, v
);
960 aff1
= isl_mat_add_zero_cols(aff1
, aff2
->n_col
- aff1
->n_col
);
963 bmap
= add_lifted_divs(bmap
, v
);
964 bmap
= isl_basic_map_extend_constraints(bmap
, 0,
965 aff1
->n_row
* aff2
->n_row
);
966 for (i
= 0; i
< aff1
->n_row
; ++i
)
967 for (j
= 0; j
< aff2
->n_row
; ++j
)
968 bmap
= construct_constraint(bmap
, tok
->type
,
969 aff1
->row
[i
], aff2
->row
[j
]);
974 tok
= isl_stream_next_token(s
);
975 if (!is_comparator(tok
)) {
977 isl_stream_push_token(s
, tok
);
989 isl_basic_map_free(bmap
);
993 static isl_map
*read_constraint(struct isl_stream
*s
,
994 struct vars
*v
, __isl_take isl_basic_map
*bmap
)
1001 bmap
= isl_basic_set_unwrap(isl_basic_set_lift(isl_basic_map_wrap(bmap
)));
1003 bmap
= add_constraint(s
, v
, bmap
);
1004 bmap
= isl_basic_map_simplify(bmap
);
1005 bmap
= isl_basic_map_finalize(bmap
);
1007 bmap
= isl_basic_set_unwrap(isl_basic_map_domain(bmap
));
1009 vars_drop(v
, v
->n
- n
);
1011 return isl_map_from_basic_map(bmap
);
1014 static struct isl_map
*read_disjuncts(struct isl_stream
*s
,
1015 struct vars
*v
, __isl_take isl_basic_map
*bmap
);
1017 static __isl_give isl_map
*read_exists(struct isl_stream
*s
,
1018 struct vars
*v
, __isl_take isl_basic_map
*bmap
)
1021 int seen_paren
= isl_stream_eat_if_available(s
, '(');
1022 isl_map
*map
= NULL
;
1024 bmap
= isl_basic_map_from_domain(isl_basic_map_wrap(bmap
));
1025 bmap
= read_defined_var_list(s
, v
, bmap
);
1027 if (isl_stream_eat(s
, ':'))
1030 map
= read_disjuncts(s
, v
, bmap
);
1031 map
= isl_set_unwrap(isl_map_domain(map
));
1034 vars_drop(v
, v
->n
- n
);
1035 if (seen_paren
&& isl_stream_eat(s
, ')'))
1040 isl_basic_map_free(bmap
);
1045 static __isl_give isl_map
*read_conjunct(struct isl_stream
*s
,
1046 struct vars
*v
, __isl_take isl_basic_map
*bmap
)
1050 if (isl_stream_eat_if_available(s
, '(')) {
1051 map
= read_disjuncts(s
, v
, bmap
);
1052 if (isl_stream_eat(s
, ')'))
1057 if (isl_stream_eat_if_available(s
, ISL_TOKEN_EXISTS
))
1058 return read_exists(s
, v
, bmap
);
1060 if (isl_stream_eat_if_available(s
, ISL_TOKEN_TRUE
))
1061 return isl_map_from_basic_map(bmap
);
1063 if (isl_stream_eat_if_available(s
, ISL_TOKEN_FALSE
)) {
1064 isl_dim
*dim
= isl_basic_map_get_dim(bmap
);
1065 isl_basic_map_free(bmap
);
1066 return isl_map_empty(dim
);
1069 return read_constraint(s
, v
, bmap
);
1075 static __isl_give isl_map
*read_conjuncts(struct isl_stream
*s
,
1076 struct vars
*v
, __isl_take isl_basic_map
*bmap
)
1081 negate
= isl_stream_eat_if_available(s
, ISL_TOKEN_NOT
);
1082 map
= read_conjunct(s
, v
, isl_basic_map_copy(bmap
));
1085 t
= isl_map_from_basic_map(isl_basic_map_copy(bmap
));
1086 map
= isl_map_subtract(t
, map
);
1089 while (isl_stream_eat_if_available(s
, ISL_TOKEN_AND
)) {
1092 negate
= isl_stream_eat_if_available(s
, ISL_TOKEN_NOT
);
1093 map_i
= read_conjunct(s
, v
, isl_basic_map_copy(bmap
));
1095 map
= isl_map_subtract(map
, map_i
);
1097 map
= isl_map_intersect(map
, map_i
);
1100 isl_basic_map_free(bmap
);
1104 static struct isl_map
*read_disjuncts(struct isl_stream
*s
,
1105 struct vars
*v
, __isl_take isl_basic_map
*bmap
)
1107 struct isl_map
*map
;
1109 if (isl_stream_next_token_is(s
, '}')) {
1110 isl_dim
*dim
= isl_basic_map_get_dim(bmap
);
1111 isl_basic_map_free(bmap
);
1112 return isl_map_universe(dim
);
1115 map
= read_conjuncts(s
, v
, isl_basic_map_copy(bmap
));
1116 while (isl_stream_eat_if_available(s
, ISL_TOKEN_OR
)) {
1119 map_i
= read_conjuncts(s
, v
, isl_basic_map_copy(bmap
));
1120 map
= isl_map_union(map
, map_i
);
1123 isl_basic_map_free(bmap
);
1127 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map
*bmap
, int pos
)
1129 if (pos
< isl_basic_map_dim(bmap
, isl_dim_out
))
1130 return 1 + isl_basic_map_dim(bmap
, isl_dim_param
) +
1131 isl_basic_map_dim(bmap
, isl_dim_in
) + pos
;
1132 pos
-= isl_basic_map_dim(bmap
, isl_dim_out
);
1134 if (pos
< isl_basic_map_dim(bmap
, isl_dim_in
))
1135 return 1 + isl_basic_map_dim(bmap
, isl_dim_param
) + pos
;
1136 pos
-= isl_basic_map_dim(bmap
, isl_dim_in
);
1138 if (pos
< isl_basic_map_dim(bmap
, isl_dim_div
))
1139 return 1 + isl_basic_map_dim(bmap
, isl_dim_param
) +
1140 isl_basic_map_dim(bmap
, isl_dim_in
) +
1141 isl_basic_map_dim(bmap
, isl_dim_out
) + pos
;
1142 pos
-= isl_basic_map_dim(bmap
, isl_dim_div
);
1144 if (pos
< isl_basic_map_dim(bmap
, isl_dim_param
))
1150 static __isl_give isl_basic_map
*basic_map_read_polylib_constraint(
1151 struct isl_stream
*s
, __isl_take isl_basic_map
*bmap
)
1154 struct isl_token
*tok
;
1164 nparam
= isl_basic_map_dim(bmap
, isl_dim_param
);
1165 dim
= isl_basic_map_dim(bmap
, isl_dim_out
);
1167 tok
= isl_stream_next_token(s
);
1168 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
1169 isl_stream_error(s
, tok
, "expecting coefficient");
1171 isl_stream_push_token(s
, tok
);
1174 if (!tok
->on_new_line
) {
1175 isl_stream_error(s
, tok
, "coefficient should appear on new line");
1176 isl_stream_push_token(s
, tok
);
1180 type
= isl_int_get_si(tok
->u
.v
);
1181 isl_token_free(tok
);
1183 isl_assert(s
->ctx
, type
== 0 || type
== 1, goto error
);
1185 k
= isl_basic_map_alloc_equality(bmap
);
1188 k
= isl_basic_map_alloc_inequality(bmap
);
1194 for (j
= 0; j
< 1 + isl_basic_map_total_dim(bmap
); ++j
) {
1196 tok
= isl_stream_next_token(s
);
1197 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
1198 isl_stream_error(s
, tok
, "expecting coefficient");
1200 isl_stream_push_token(s
, tok
);
1203 if (tok
->on_new_line
) {
1204 isl_stream_error(s
, tok
,
1205 "coefficient should not appear on new line");
1206 isl_stream_push_token(s
, tok
);
1209 pos
= polylib_pos_to_isl_pos(bmap
, j
);
1210 isl_int_set(c
[pos
], tok
->u
.v
);
1211 isl_token_free(tok
);
1216 isl_basic_map_free(bmap
);
1220 static __isl_give isl_basic_map
*basic_map_read_polylib(struct isl_stream
*s
,
1224 struct isl_token
*tok
;
1225 struct isl_token
*tok2
;
1228 unsigned in
= 0, out
, local
= 0;
1229 struct isl_basic_map
*bmap
= NULL
;
1234 tok
= isl_stream_next_token(s
);
1236 isl_stream_error(s
, NULL
, "unexpected EOF");
1239 tok2
= isl_stream_next_token(s
);
1241 isl_token_free(tok
);
1242 isl_stream_error(s
, NULL
, "unexpected EOF");
1245 if (tok
->type
!= ISL_TOKEN_VALUE
|| tok2
->type
!= ISL_TOKEN_VALUE
) {
1246 isl_stream_push_token(s
, tok2
);
1247 isl_stream_push_token(s
, tok
);
1248 isl_stream_error(s
, NULL
,
1249 "expecting constraint matrix dimensions");
1252 n_row
= isl_int_get_si(tok
->u
.v
);
1253 n_col
= isl_int_get_si(tok2
->u
.v
);
1254 on_new_line
= tok2
->on_new_line
;
1255 isl_token_free(tok2
);
1256 isl_token_free(tok
);
1257 isl_assert(s
->ctx
, !on_new_line
, return NULL
);
1258 isl_assert(s
->ctx
, n_row
>= 0, return NULL
);
1259 isl_assert(s
->ctx
, n_col
>= 2 + nparam
, return NULL
);
1260 tok
= isl_stream_next_token_on_same_line(s
);
1262 if (tok
->type
!= ISL_TOKEN_VALUE
) {
1263 isl_stream_error(s
, tok
,
1264 "expecting number of output dimensions");
1265 isl_stream_push_token(s
, tok
);
1268 out
= isl_int_get_si(tok
->u
.v
);
1269 isl_token_free(tok
);
1271 tok
= isl_stream_next_token_on_same_line(s
);
1272 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
1273 isl_stream_error(s
, tok
,
1274 "expecting number of input dimensions");
1276 isl_stream_push_token(s
, tok
);
1279 in
= isl_int_get_si(tok
->u
.v
);
1280 isl_token_free(tok
);
1282 tok
= isl_stream_next_token_on_same_line(s
);
1283 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
1284 isl_stream_error(s
, tok
,
1285 "expecting number of existentials");
1287 isl_stream_push_token(s
, tok
);
1290 local
= isl_int_get_si(tok
->u
.v
);
1291 isl_token_free(tok
);
1293 tok
= isl_stream_next_token_on_same_line(s
);
1294 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
1295 isl_stream_error(s
, tok
,
1296 "expecting number of parameters");
1298 isl_stream_push_token(s
, tok
);
1301 nparam
= isl_int_get_si(tok
->u
.v
);
1302 isl_token_free(tok
);
1303 if (n_col
!= 1 + out
+ in
+ local
+ nparam
+ 1) {
1304 isl_stream_error(s
, NULL
,
1305 "dimensions don't match");
1309 out
= n_col
- 2 - nparam
;
1310 bmap
= isl_basic_map_alloc(s
->ctx
, nparam
, in
, out
, local
, n_row
, n_row
);
1314 for (i
= 0; i
< local
; ++i
) {
1315 int k
= isl_basic_map_alloc_div(bmap
);
1318 isl_seq_clr(bmap
->div
[k
], 1 + 1 + nparam
+ in
+ out
+ local
);
1321 for (i
= 0; i
< n_row
; ++i
)
1322 bmap
= basic_map_read_polylib_constraint(s
, bmap
);
1324 tok
= isl_stream_next_token_on_same_line(s
);
1326 isl_stream_error(s
, tok
, "unexpected extra token on line");
1327 isl_stream_push_token(s
, tok
);
1331 bmap
= isl_basic_map_simplify(bmap
);
1332 bmap
= isl_basic_map_finalize(bmap
);
1335 isl_basic_map_free(bmap
);
1339 static struct isl_map
*map_read_polylib(struct isl_stream
*s
, int nparam
)
1341 struct isl_token
*tok
;
1342 struct isl_token
*tok2
;
1344 struct isl_map
*map
;
1346 tok
= isl_stream_next_token(s
);
1348 isl_stream_error(s
, NULL
, "unexpected EOF");
1351 tok2
= isl_stream_next_token_on_same_line(s
);
1352 if (tok2
&& tok2
->type
== ISL_TOKEN_VALUE
) {
1353 isl_stream_push_token(s
, tok2
);
1354 isl_stream_push_token(s
, tok
);
1355 return isl_map_from_basic_map(basic_map_read_polylib(s
, nparam
));
1358 isl_stream_error(s
, tok2
, "unexpected token");
1359 isl_stream_push_token(s
, tok2
);
1360 isl_stream_push_token(s
, tok
);
1363 n
= isl_int_get_si(tok
->u
.v
);
1364 isl_token_free(tok
);
1366 isl_assert(s
->ctx
, n
>= 1, return NULL
);
1368 map
= isl_map_from_basic_map(basic_map_read_polylib(s
, nparam
));
1370 for (i
= 1; map
&& i
< n
; ++i
)
1371 map
= isl_map_union(map
,
1372 isl_map_from_basic_map(basic_map_read_polylib(s
, nparam
)));
1377 static int optional_power(struct isl_stream
*s
)
1380 struct isl_token
*tok
;
1382 tok
= isl_stream_next_token(s
);
1385 if (tok
->type
!= '^') {
1386 isl_stream_push_token(s
, tok
);
1389 isl_token_free(tok
);
1390 tok
= isl_stream_next_token(s
);
1391 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
1392 isl_stream_error(s
, tok
, "expecting exponent");
1394 isl_stream_push_token(s
, tok
);
1397 pow
= isl_int_get_si(tok
->u
.v
);
1398 isl_token_free(tok
);
1402 static __isl_give isl_div
*read_div(struct isl_stream
*s
,
1403 __isl_take isl_dim
*dim
, struct vars
*v
)
1406 isl_basic_map
*bmap
;
1409 bmap
= isl_basic_map_universe(dim
);
1411 if (vars_add_anon(v
) < 0)
1413 if (read_div_definition(s
, v
) < 0)
1415 bmap
= add_divs(bmap
, v
);
1416 bmap
= isl_basic_map_order_divs(bmap
);
1419 vars_drop(v
, v
->n
- n
);
1421 return isl_basic_map_div(bmap
, bmap
->n_div
- 1);
1423 isl_basic_map_free(bmap
);
1427 static __isl_give isl_qpolynomial
*read_term(struct isl_stream
*s
,
1428 __isl_keep isl_basic_map
*bmap
, struct vars
*v
);
1430 static __isl_give isl_qpolynomial
*read_factor(struct isl_stream
*s
,
1431 __isl_keep isl_basic_map
*bmap
, struct vars
*v
)
1433 struct isl_qpolynomial
*qp
;
1434 struct isl_token
*tok
;
1436 tok
= next_token(s
);
1438 isl_stream_error(s
, NULL
, "unexpected EOF");
1441 if (tok
->type
== '(') {
1444 isl_token_free(tok
);
1445 qp
= read_term(s
, bmap
, v
);
1448 if (isl_stream_eat(s
, ')'))
1450 pow
= optional_power(s
);
1451 qp
= isl_qpolynomial_pow(qp
, pow
);
1452 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
1453 struct isl_token
*tok2
;
1454 tok2
= isl_stream_next_token(s
);
1455 if (tok2
&& tok2
->type
== '/') {
1456 isl_token_free(tok2
);
1457 tok2
= next_token(s
);
1458 if (!tok2
|| tok2
->type
!= ISL_TOKEN_VALUE
) {
1459 isl_stream_error(s
, tok2
, "expected denominator");
1460 isl_token_free(tok
);
1461 isl_token_free(tok2
);
1464 qp
= isl_qpolynomial_rat_cst(isl_basic_map_get_dim(bmap
),
1465 tok
->u
.v
, tok2
->u
.v
);
1466 isl_token_free(tok2
);
1468 isl_stream_push_token(s
, tok2
);
1469 qp
= isl_qpolynomial_cst(isl_basic_map_get_dim(bmap
),
1472 isl_token_free(tok
);
1473 } else if (tok
->type
== ISL_TOKEN_INFTY
) {
1474 isl_token_free(tok
);
1475 qp
= isl_qpolynomial_infty(isl_basic_map_get_dim(bmap
));
1476 } else if (tok
->type
== ISL_TOKEN_NAN
) {
1477 isl_token_free(tok
);
1478 qp
= isl_qpolynomial_nan(isl_basic_map_get_dim(bmap
));
1479 } else if (tok
->type
== ISL_TOKEN_IDENT
) {
1481 int pos
= vars_pos(v
, tok
->u
.s
, -1);
1484 isl_token_free(tok
);
1488 vars_drop(v
, v
->n
- n
);
1489 isl_stream_error(s
, tok
, "unknown identifier");
1490 isl_token_free(tok
);
1493 isl_token_free(tok
);
1494 pow
= optional_power(s
);
1495 qp
= isl_qpolynomial_var_pow(isl_basic_map_get_dim(bmap
), pos
, pow
);
1496 } else if (tok
->type
== '[') {
1500 isl_stream_push_token(s
, tok
);
1501 div
= read_div(s
, isl_basic_map_get_dim(bmap
), v
);
1502 pow
= optional_power(s
);
1503 qp
= isl_qpolynomial_div_pow(div
, pow
);
1504 } else if (tok
->type
== '-') {
1505 struct isl_qpolynomial
*qp2
;
1507 isl_token_free(tok
);
1508 qp
= isl_qpolynomial_cst(isl_basic_map_get_dim(bmap
),
1510 qp2
= read_factor(s
, bmap
, v
);
1511 qp
= isl_qpolynomial_mul(qp
, qp2
);
1513 isl_stream_error(s
, tok
, "unexpected isl_token");
1514 isl_stream_push_token(s
, tok
);
1518 if (isl_stream_eat_if_available(s
, '*') ||
1519 isl_stream_next_token_is(s
, ISL_TOKEN_IDENT
)) {
1520 struct isl_qpolynomial
*qp2
;
1522 qp2
= read_factor(s
, bmap
, v
);
1523 qp
= isl_qpolynomial_mul(qp
, qp2
);
1528 isl_qpolynomial_free(qp
);
1532 static __isl_give isl_qpolynomial
*read_term(struct isl_stream
*s
,
1533 __isl_keep isl_basic_map
*bmap
, struct vars
*v
)
1535 struct isl_token
*tok
;
1536 struct isl_qpolynomial
*qp
;
1538 qp
= read_factor(s
, bmap
, v
);
1541 tok
= next_token(s
);
1545 if (tok
->type
== '+') {
1546 struct isl_qpolynomial
*qp2
;
1548 isl_token_free(tok
);
1549 qp2
= read_factor(s
, bmap
, v
);
1550 qp
= isl_qpolynomial_add(qp
, qp2
);
1551 } else if (tok
->type
== '-') {
1552 struct isl_qpolynomial
*qp2
;
1554 isl_token_free(tok
);
1555 qp2
= read_factor(s
, bmap
, v
);
1556 qp
= isl_qpolynomial_sub(qp
, qp2
);
1557 } else if (tok
->type
== ISL_TOKEN_VALUE
&&
1558 isl_int_is_neg(tok
->u
.v
)) {
1559 struct isl_qpolynomial
*qp2
;
1561 isl_stream_push_token(s
, tok
);
1562 qp2
= read_factor(s
, bmap
, v
);
1563 qp
= isl_qpolynomial_add(qp
, qp2
);
1565 isl_stream_push_token(s
, tok
);
1573 static __isl_give isl_map
*read_optional_disjuncts(struct isl_stream
*s
,
1574 __isl_take isl_basic_map
*bmap
, struct vars
*v
)
1576 struct isl_token
*tok
;
1577 struct isl_map
*map
;
1579 tok
= isl_stream_next_token(s
);
1581 isl_stream_error(s
, NULL
, "unexpected EOF");
1584 map
= isl_map_from_basic_map(isl_basic_map_copy(bmap
));
1585 if (tok
->type
== ':' ||
1586 (tok
->type
== ISL_TOKEN_OR
&& !strcmp(tok
->u
.s
, "|"))) {
1587 isl_token_free(tok
);
1588 map
= isl_map_intersect(map
,
1589 read_disjuncts(s
, v
, isl_basic_map_copy(bmap
)));
1591 isl_stream_push_token(s
, tok
);
1593 isl_basic_map_free(bmap
);
1597 isl_basic_map_free(bmap
);
1601 static struct isl_obj
obj_read_poly(struct isl_stream
*s
,
1602 __isl_take isl_basic_map
*bmap
, struct vars
*v
, int n
)
1604 struct isl_obj obj
= { isl_obj_pw_qpolynomial
, NULL
};
1605 struct isl_pw_qpolynomial
*pwqp
;
1606 struct isl_qpolynomial
*qp
;
1607 struct isl_map
*map
;
1608 struct isl_set
*set
;
1610 qp
= read_term(s
, bmap
, v
);
1611 map
= read_optional_disjuncts(s
, bmap
, v
);
1612 set
= isl_map_range(map
);
1614 pwqp
= isl_pw_qpolynomial_alloc(set
, qp
);
1616 vars_drop(v
, v
->n
- n
);
1622 static struct isl_obj
obj_read_poly_or_fold(struct isl_stream
*s
,
1623 __isl_take isl_basic_map
*bmap
, struct vars
*v
, int n
)
1625 struct isl_obj obj
= { isl_obj_pw_qpolynomial_fold
, NULL
};
1626 struct isl_obj obj_p
;
1627 isl_qpolynomial
*qp
;
1628 isl_qpolynomial_fold
*fold
= NULL
;
1629 isl_pw_qpolynomial_fold
*pwf
;
1633 if (!isl_stream_eat_if_available(s
, ISL_TOKEN_MAX
))
1634 return obj_read_poly(s
, bmap
, v
, n
);
1636 if (isl_stream_eat(s
, '('))
1639 qp
= read_term(s
, bmap
, v
);
1640 fold
= isl_qpolynomial_fold_alloc(isl_fold_max
, qp
);
1642 while (isl_stream_eat_if_available(s
, ',')) {
1643 isl_qpolynomial_fold
*fold_i
;
1644 qp
= read_term(s
, bmap
, v
);
1645 fold_i
= isl_qpolynomial_fold_alloc(isl_fold_max
, qp
);
1646 fold
= isl_qpolynomial_fold_fold(fold
, fold_i
);
1649 if (isl_stream_eat(s
, ')'))
1652 map
= read_optional_disjuncts(s
, bmap
, v
);
1653 set
= isl_map_range(map
);
1654 pwf
= isl_pw_qpolynomial_fold_alloc(isl_fold_max
, set
, fold
);
1656 vars_drop(v
, v
->n
- n
);
1661 isl_basic_map_free(bmap
);
1662 isl_qpolynomial_fold_free(fold
);
1663 obj
.type
= isl_obj_none
;
1667 static int is_rational(struct isl_stream
*s
)
1669 struct isl_token
*tok
;
1671 tok
= isl_stream_next_token(s
);
1674 if (tok
->type
== ISL_TOKEN_RAT
&& isl_stream_next_token_is(s
, ':')) {
1675 isl_token_free(tok
);
1676 isl_stream_eat(s
, ':');
1680 isl_stream_push_token(s
, tok
);
1685 static struct isl_obj
obj_read_body(struct isl_stream
*s
,
1686 __isl_take isl_basic_map
*bmap
, struct vars
*v
)
1688 struct isl_map
*map
= NULL
;
1689 struct isl_token
*tok
;
1690 struct isl_obj obj
= { isl_obj_set
, NULL
};
1694 bmap
= isl_basic_map_set_rational(bmap
);
1696 if (!next_is_tuple(s
))
1697 return obj_read_poly_or_fold(s
, bmap
, v
, n
);
1699 bmap
= read_tuple(s
, bmap
, isl_dim_in
, v
);
1702 tok
= isl_stream_next_token(s
);
1703 if (tok
&& tok
->type
== ISL_TOKEN_TO
) {
1704 obj
.type
= isl_obj_map
;
1705 isl_token_free(tok
);
1706 if (!next_is_tuple(s
)) {
1707 bmap
= isl_basic_map_reverse(bmap
);
1708 return obj_read_poly_or_fold(s
, bmap
, v
, n
);
1710 bmap
= read_tuple(s
, bmap
, isl_dim_out
, v
);
1714 bmap
= isl_basic_map_reverse(bmap
);
1716 isl_stream_push_token(s
, tok
);
1719 map
= read_optional_disjuncts(s
, bmap
, v
);
1721 vars_drop(v
, v
->n
- n
);
1726 isl_basic_map_free(bmap
);
1727 obj
.type
= isl_obj_none
;
1731 static struct isl_obj
to_union(isl_ctx
*ctx
, struct isl_obj obj
)
1733 if (obj
.type
== isl_obj_map
) {
1734 obj
.v
= isl_union_map_from_map(obj
.v
);
1735 obj
.type
= isl_obj_union_map
;
1736 } else if (obj
.type
== isl_obj_set
) {
1737 obj
.v
= isl_union_set_from_set(obj
.v
);
1738 obj
.type
= isl_obj_union_set
;
1739 } else if (obj
.type
== isl_obj_pw_qpolynomial
) {
1740 obj
.v
= isl_union_pw_qpolynomial_from_pw_qpolynomial(obj
.v
);
1741 obj
.type
= isl_obj_union_pw_qpolynomial
;
1742 } else if (obj
.type
== isl_obj_pw_qpolynomial_fold
) {
1743 obj
.v
= isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj
.v
);
1744 obj
.type
= isl_obj_union_pw_qpolynomial_fold
;
1746 isl_assert(ctx
, 0, goto error
);
1749 obj
.type
->free(obj
.v
);
1750 obj
.type
= isl_obj_none
;
1754 static struct isl_obj
obj_add(struct isl_ctx
*ctx
,
1755 struct isl_obj obj1
, struct isl_obj obj2
)
1757 if (obj1
.type
== isl_obj_set
&& obj2
.type
== isl_obj_union_set
)
1758 obj1
= to_union(ctx
, obj1
);
1759 if (obj1
.type
== isl_obj_union_set
&& obj2
.type
== isl_obj_set
)
1760 obj2
= to_union(ctx
, obj2
);
1761 if (obj1
.type
== isl_obj_map
&& obj2
.type
== isl_obj_union_map
)
1762 obj1
= to_union(ctx
, obj1
);
1763 if (obj1
.type
== isl_obj_union_map
&& obj2
.type
== isl_obj_map
)
1764 obj2
= to_union(ctx
, obj2
);
1765 if (obj1
.type
== isl_obj_pw_qpolynomial
&&
1766 obj2
.type
== isl_obj_union_pw_qpolynomial
)
1767 obj1
= to_union(ctx
, obj1
);
1768 if (obj1
.type
== isl_obj_union_pw_qpolynomial
&&
1769 obj2
.type
== isl_obj_pw_qpolynomial
)
1770 obj2
= to_union(ctx
, obj2
);
1771 if (obj1
.type
== isl_obj_pw_qpolynomial_fold
&&
1772 obj2
.type
== isl_obj_union_pw_qpolynomial_fold
)
1773 obj1
= to_union(ctx
, obj1
);
1774 if (obj1
.type
== isl_obj_union_pw_qpolynomial_fold
&&
1775 obj2
.type
== isl_obj_pw_qpolynomial_fold
)
1776 obj2
= to_union(ctx
, obj2
);
1777 isl_assert(ctx
, obj1
.type
== obj2
.type
, goto error
);
1778 if (obj1
.type
== isl_obj_map
&& !isl_map_has_equal_dim(obj1
.v
, obj2
.v
)) {
1779 obj1
= to_union(ctx
, obj1
);
1780 obj2
= to_union(ctx
, obj2
);
1782 if (obj1
.type
== isl_obj_set
&& !isl_set_has_equal_dim(obj1
.v
, obj2
.v
)) {
1783 obj1
= to_union(ctx
, obj1
);
1784 obj2
= to_union(ctx
, obj2
);
1786 if (obj1
.type
== isl_obj_pw_qpolynomial
&&
1787 !isl_pw_qpolynomial_has_equal_dim(obj1
.v
, obj2
.v
)) {
1788 obj1
= to_union(ctx
, obj1
);
1789 obj2
= to_union(ctx
, obj2
);
1791 if (obj1
.type
== isl_obj_pw_qpolynomial_fold
&&
1792 !isl_pw_qpolynomial_fold_has_equal_dim(obj1
.v
, obj2
.v
)) {
1793 obj1
= to_union(ctx
, obj1
);
1794 obj2
= to_union(ctx
, obj2
);
1796 obj1
.v
= obj1
.type
->add(obj1
.v
, obj2
.v
);
1799 obj1
.type
->free(obj1
.v
);
1800 obj2
.type
->free(obj2
.v
);
1801 obj1
.type
= isl_obj_none
;
1806 static struct isl_obj
obj_read(struct isl_stream
*s
, int nparam
)
1808 isl_basic_map
*bmap
= NULL
;
1809 struct isl_token
*tok
;
1810 struct vars
*v
= NULL
;
1811 struct isl_obj obj
= { isl_obj_set
, NULL
};
1813 tok
= next_token(s
);
1815 isl_stream_error(s
, NULL
, "unexpected EOF");
1818 if (tok
->type
== ISL_TOKEN_VALUE
) {
1819 struct isl_token
*tok2
;
1820 struct isl_map
*map
;
1822 tok2
= isl_stream_next_token(s
);
1823 if (!tok2
|| tok2
->type
!= ISL_TOKEN_VALUE
||
1824 isl_int_is_neg(tok2
->u
.v
)) {
1826 isl_stream_push_token(s
, tok2
);
1827 obj
.type
= isl_obj_int
;
1828 obj
.v
= isl_int_obj_alloc(s
->ctx
, tok
->u
.v
);
1829 isl_token_free(tok
);
1832 isl_stream_push_token(s
, tok2
);
1833 isl_stream_push_token(s
, tok
);
1834 map
= map_read_polylib(s
, nparam
);
1837 if (isl_map_dim(map
, isl_dim_in
) > 0)
1838 obj
.type
= isl_obj_map
;
1842 v
= vars_new(s
->ctx
);
1844 isl_stream_push_token(s
, tok
);
1847 bmap
= isl_basic_map_alloc(s
->ctx
, 0, 0, 0, 0, 0, 0);
1848 if (tok
->type
== '[') {
1849 isl_stream_push_token(s
, tok
);
1850 bmap
= read_tuple(s
, bmap
, isl_dim_param
, v
);
1854 isl_assert(s
->ctx
, nparam
== v
->n
, goto error
);
1855 tok
= isl_stream_next_token(s
);
1856 if (!tok
|| tok
->type
!= ISL_TOKEN_TO
) {
1857 isl_stream_error(s
, tok
, "expecting '->'");
1859 isl_stream_push_token(s
, tok
);
1862 isl_token_free(tok
);
1863 tok
= isl_stream_next_token(s
);
1864 } else if (nparam
> 0)
1865 bmap
= isl_basic_map_add(bmap
, isl_dim_param
, nparam
);
1866 if (!tok
|| tok
->type
!= '{') {
1867 isl_stream_error(s
, tok
, "expecting '{'");
1869 isl_stream_push_token(s
, tok
);
1872 isl_token_free(tok
);
1874 tok
= isl_stream_next_token(s
);
1877 else if (tok
->type
== ISL_TOKEN_IDENT
&& !strcmp(tok
->u
.s
, "Sym")) {
1878 isl_token_free(tok
);
1879 if (isl_stream_eat(s
, '='))
1881 bmap
= read_tuple(s
, bmap
, isl_dim_param
, v
);
1885 isl_assert(s
->ctx
, nparam
== v
->n
, goto error
);
1886 } else if (tok
->type
== '}') {
1887 obj
.type
= isl_obj_union_set
;
1888 obj
.v
= isl_union_set_empty(isl_basic_map_get_dim(bmap
));
1889 isl_token_free(tok
);
1892 isl_stream_push_token(s
, tok
);
1897 o
= obj_read_body(s
, isl_basic_map_copy(bmap
), v
);
1898 if (o
.type
== isl_obj_none
|| !o
.v
)
1903 obj
= obj_add(s
->ctx
, obj
, o
);
1904 if (obj
.type
== isl_obj_none
|| !obj
.v
)
1907 tok
= isl_stream_next_token(s
);
1908 if (!tok
|| tok
->type
!= ';')
1910 isl_token_free(tok
);
1911 if (isl_stream_next_token_is(s
, '}')) {
1912 tok
= isl_stream_next_token(s
);
1917 if (tok
&& tok
->type
== '}') {
1918 isl_token_free(tok
);
1920 isl_stream_error(s
, tok
, "unexpected isl_token");
1922 isl_token_free(tok
);
1927 isl_basic_map_free(bmap
);
1931 isl_basic_map_free(bmap
);
1932 obj
.type
->free(obj
.v
);
1939 struct isl_obj
isl_stream_read_obj(struct isl_stream
*s
)
1941 return obj_read(s
, -1);
1944 __isl_give isl_map
*isl_stream_read_map(struct isl_stream
*s
, int nparam
)
1947 struct isl_map
*map
;
1949 obj
= obj_read(s
, nparam
);
1951 isl_assert(s
->ctx
, obj
.type
== isl_obj_map
||
1952 obj
.type
== isl_obj_set
, goto error
);
1956 obj
.type
->free(obj
.v
);
1960 __isl_give isl_set
*isl_stream_read_set(struct isl_stream
*s
, int nparam
)
1963 struct isl_set
*set
;
1965 obj
= obj_read(s
, nparam
);
1967 isl_assert(s
->ctx
, obj
.type
== isl_obj_set
, goto error
);
1971 obj
.type
->free(obj
.v
);
1975 __isl_give isl_union_map
*isl_stream_read_union_map(struct isl_stream
*s
)
1978 isl_union_map
*umap
;
1980 obj
= obj_read(s
, -1);
1981 if (obj
.type
== isl_obj_map
) {
1982 obj
.type
= isl_obj_union_map
;
1983 obj
.v
= isl_union_map_from_map(obj
.v
);
1985 if (obj
.type
== isl_obj_set
) {
1986 obj
.type
= isl_obj_union_set
;
1987 obj
.v
= isl_union_set_from_set(obj
.v
);
1990 isl_assert(s
->ctx
, obj
.type
== isl_obj_union_map
||
1991 obj
.type
== isl_obj_union_set
, goto error
);
1995 obj
.type
->free(obj
.v
);
1999 __isl_give isl_union_set
*isl_stream_read_union_set(struct isl_stream
*s
)
2002 isl_union_set
*uset
;
2004 obj
= obj_read(s
, -1);
2005 if (obj
.type
== isl_obj_set
) {
2006 obj
.type
= isl_obj_union_set
;
2007 obj
.v
= isl_union_set_from_set(obj
.v
);
2010 isl_assert(s
->ctx
, obj
.type
== isl_obj_union_set
, goto error
);
2014 obj
.type
->free(obj
.v
);
2018 static struct isl_basic_map
*basic_map_read(struct isl_stream
*s
, int nparam
)
2021 struct isl_map
*map
;
2022 struct isl_basic_map
*bmap
;
2024 obj
= obj_read(s
, nparam
);
2029 isl_assert(map
->ctx
, map
->n
<= 1, goto error
);
2032 bmap
= isl_basic_map_empty_like_map(map
);
2034 bmap
= isl_basic_map_copy(map
->p
[0]);
2044 __isl_give isl_basic_map
*isl_basic_map_read_from_file(isl_ctx
*ctx
,
2045 FILE *input
, int nparam
)
2047 struct isl_basic_map
*bmap
;
2048 struct isl_stream
*s
= isl_stream_new_file(ctx
, input
);
2051 bmap
= basic_map_read(s
, nparam
);
2056 __isl_give isl_basic_set
*isl_basic_set_read_from_file(isl_ctx
*ctx
,
2057 FILE *input
, int nparam
)
2059 struct isl_basic_map
*bmap
;
2060 bmap
= isl_basic_map_read_from_file(ctx
, input
, nparam
);
2063 isl_assert(ctx
, isl_basic_map_n_in(bmap
) == 0, goto error
);
2064 return (struct isl_basic_set
*)bmap
;
2066 isl_basic_map_free(bmap
);
2070 struct isl_basic_map
*isl_basic_map_read_from_str(struct isl_ctx
*ctx
,
2071 const char *str
, int nparam
)
2073 struct isl_basic_map
*bmap
;
2074 struct isl_stream
*s
= isl_stream_new_str(ctx
, str
);
2077 bmap
= basic_map_read(s
, nparam
);
2082 struct isl_basic_set
*isl_basic_set_read_from_str(struct isl_ctx
*ctx
,
2083 const char *str
, int nparam
)
2085 struct isl_basic_map
*bmap
;
2086 bmap
= isl_basic_map_read_from_str(ctx
, str
, nparam
);
2089 isl_assert(ctx
, isl_basic_map_n_in(bmap
) == 0, goto error
);
2090 return (struct isl_basic_set
*)bmap
;
2092 isl_basic_map_free(bmap
);
2096 __isl_give isl_map
*isl_map_read_from_file(struct isl_ctx
*ctx
,
2097 FILE *input
, int nparam
)
2099 struct isl_map
*map
;
2100 struct isl_stream
*s
= isl_stream_new_file(ctx
, input
);
2103 map
= isl_stream_read_map(s
, nparam
);
2108 __isl_give isl_map
*isl_map_read_from_str(struct isl_ctx
*ctx
,
2109 const char *str
, int nparam
)
2111 struct isl_map
*map
;
2112 struct isl_stream
*s
= isl_stream_new_str(ctx
, str
);
2115 map
= isl_stream_read_map(s
, nparam
);
2120 __isl_give isl_set
*isl_set_read_from_file(struct isl_ctx
*ctx
,
2121 FILE *input
, int nparam
)
2123 struct isl_map
*map
;
2124 map
= isl_map_read_from_file(ctx
, input
, nparam
);
2127 isl_assert(ctx
, isl_map_n_in(map
) == 0, goto error
);
2128 return (struct isl_set
*)map
;
2134 struct isl_set
*isl_set_read_from_str(struct isl_ctx
*ctx
,
2135 const char *str
, int nparam
)
2137 struct isl_map
*map
;
2138 map
= isl_map_read_from_str(ctx
, str
, nparam
);
2141 isl_assert(ctx
, isl_map_n_in(map
) == 0, goto error
);
2142 return (struct isl_set
*)map
;
2148 __isl_give isl_union_map
*isl_union_map_read_from_file(isl_ctx
*ctx
,
2151 isl_union_map
*umap
;
2152 struct isl_stream
*s
= isl_stream_new_file(ctx
, input
);
2155 umap
= isl_stream_read_union_map(s
);
2160 __isl_give isl_union_map
*isl_union_map_read_from_str(struct isl_ctx
*ctx
,
2163 isl_union_map
*umap
;
2164 struct isl_stream
*s
= isl_stream_new_str(ctx
, str
);
2167 umap
= isl_stream_read_union_map(s
);
2172 __isl_give isl_union_set
*isl_union_set_read_from_file(isl_ctx
*ctx
,
2175 isl_union_set
*uset
;
2176 struct isl_stream
*s
= isl_stream_new_file(ctx
, input
);
2179 uset
= isl_stream_read_union_set(s
);
2184 __isl_give isl_union_set
*isl_union_set_read_from_str(struct isl_ctx
*ctx
,
2187 isl_union_set
*uset
;
2188 struct isl_stream
*s
= isl_stream_new_str(ctx
, str
);
2191 uset
= isl_stream_read_union_set(s
);
2196 static __isl_give isl_vec
*isl_vec_read_polylib(struct isl_stream
*s
)
2198 struct isl_vec
*vec
= NULL
;
2199 struct isl_token
*tok
;
2203 tok
= isl_stream_next_token(s
);
2204 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2205 isl_stream_error(s
, tok
, "expecting vector length");
2209 size
= isl_int_get_si(tok
->u
.v
);
2210 isl_token_free(tok
);
2212 vec
= isl_vec_alloc(s
->ctx
, size
);
2214 for (j
= 0; j
< size
; ++j
) {
2215 tok
= isl_stream_next_token(s
);
2216 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
2217 isl_stream_error(s
, tok
, "expecting constant value");
2220 isl_int_set(vec
->el
[j
], tok
->u
.v
);
2221 isl_token_free(tok
);
2226 isl_token_free(tok
);
2231 static __isl_give isl_vec
*vec_read(struct isl_stream
*s
)
2233 return isl_vec_read_polylib(s
);
2236 __isl_give isl_vec
*isl_vec_read_from_file(isl_ctx
*ctx
, FILE *input
)
2239 struct isl_stream
*s
= isl_stream_new_file(ctx
, input
);
2247 __isl_give isl_pw_qpolynomial
*isl_stream_read_pw_qpolynomial(
2248 struct isl_stream
*s
)
2251 struct isl_pw_qpolynomial
*pwqp
;
2253 obj
= obj_read(s
, -1);
2255 isl_assert(s
->ctx
, obj
.type
== isl_obj_pw_qpolynomial
,
2260 obj
.type
->free(obj
.v
);
2264 __isl_give isl_pw_qpolynomial
*isl_pw_qpolynomial_read_from_str(isl_ctx
*ctx
,
2267 isl_pw_qpolynomial
*pwqp
;
2268 struct isl_stream
*s
= isl_stream_new_str(ctx
, str
);
2271 pwqp
= isl_stream_read_pw_qpolynomial(s
);