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
20 #include "isl_stream.h"
21 #include "isl_map_private.h"
23 #include "isl_polynomial_private.h"
24 #include <isl_union_map.h>
29 struct variable
*next
;
38 static struct vars
*vars_new(struct isl_ctx
*ctx
)
41 v
= isl_alloc_type(ctx
, struct vars
);
50 static void variable_free(struct variable
*var
)
53 struct variable
*next
= var
->next
;
60 static void vars_free(struct vars
*v
)
68 static void vars_drop(struct vars
*v
, int n
)
79 struct variable
*next
= var
->next
;
87 static struct variable
*variable_new(struct vars
*v
, const char *name
, int len
,
91 var
= isl_alloc_type(v
->ctx
, struct variable
);
94 var
->name
= strdup(name
);
95 var
->name
[len
] = '\0';
104 static int vars_pos(struct vars
*v
, const char *s
, int len
)
111 for (q
= v
->v
; q
; q
= q
->next
) {
112 if (strncmp(q
->name
, s
, len
) == 0 && q
->name
[len
] == '\0')
119 v
->v
= variable_new(v
, s
, len
, v
->n
);
127 static __isl_give isl_basic_map
*set_name(__isl_take isl_basic_map
*bmap
,
128 enum isl_dim_type type
, unsigned pos
, char *name
)
137 prime
= strchr(name
, '\'');
140 bmap
->dim
= isl_dim_set_name(bmap
->dim
, type
, pos
, name
);
149 isl_basic_map_free(bmap
);
153 static int accept_cst_factor(struct isl_stream
*s
, isl_int
*f
)
155 struct isl_token
*tok
;
157 tok
= isl_stream_next_token(s
);
158 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
159 isl_stream_error(s
, tok
, "expecting constant value");
163 isl_int_mul(*f
, *f
, tok
->u
.v
);
167 if (isl_stream_eat_if_available(s
, '*'))
168 return accept_cst_factor(s
, f
);
176 static struct isl_vec
*accept_affine(struct isl_stream
*s
, struct vars
*v
);
178 static __isl_give isl_vec
*accept_affine_factor(struct isl_stream
*s
,
181 struct isl_token
*tok
= NULL
;
184 tok
= isl_stream_next_token(s
);
186 isl_stream_error(s
, NULL
, "unexpected EOF");
189 if (tok
->type
== ISL_TOKEN_IDENT
) {
191 int pos
= vars_pos(v
, tok
->u
.s
, -1);
195 isl_stream_error(s
, tok
, "unknown identifier");
199 aff
= isl_vec_alloc(v
->ctx
, 1 + v
->n
);
202 isl_seq_clr(aff
->el
, aff
->size
);
203 isl_int_set_si(aff
->el
[1 + pos
], 1);
205 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
206 if (isl_stream_eat_if_available(s
, '*')) {
207 aff
= accept_affine_factor(s
, v
);
208 aff
= isl_vec_scale(aff
, tok
->u
.v
);
210 aff
= isl_vec_alloc(v
->ctx
, 1 + v
->n
);
213 isl_seq_clr(aff
->el
, aff
->size
);
214 isl_int_set(aff
->el
[0], tok
->u
.v
);
217 } else if (tok
->type
== '(') {
220 aff
= accept_affine(s
, v
);
223 if (isl_stream_eat(s
, ')'))
226 isl_stream_error(s
, tok
, "expecting factor");
229 if (isl_stream_eat_if_available(s
, '*')) {
232 isl_int_set_si(f
, 1);
233 if (accept_cst_factor(s
, &f
) < 0) {
237 aff
= isl_vec_scale(aff
, f
);
248 static struct isl_vec
*accept_affine(struct isl_stream
*s
, struct vars
*v
)
250 struct isl_token
*tok
= NULL
;
254 aff
= isl_vec_alloc(v
->ctx
, 1 + v
->n
);
257 isl_seq_clr(aff
->el
, aff
->size
);
260 tok
= isl_stream_next_token(s
);
262 isl_stream_error(s
, NULL
, "unexpected EOF");
265 if (tok
->type
== '-') {
270 if (tok
->type
== '(' || tok
->type
== ISL_TOKEN_IDENT
) {
272 isl_stream_push_token(s
, tok
);
274 aff2
= accept_affine_factor(s
, v
);
276 aff2
= isl_vec_scale(aff2
, s
->ctx
->negone
);
277 aff
= isl_vec_add(aff
, aff2
);
281 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
283 isl_int_neg(tok
->u
.v
, tok
->u
.v
);
284 if (isl_stream_eat_if_available(s
, '*') ||
285 isl_stream_next_token_is(s
, ISL_TOKEN_IDENT
)) {
287 aff2
= accept_affine_factor(s
, v
);
288 aff2
= isl_vec_scale(aff2
, tok
->u
.v
);
289 aff
= isl_vec_add(aff
, aff2
);
293 isl_int_add(aff
->el
[0], aff
->el
[0], tok
->u
.v
);
299 tok
= isl_stream_next_token(s
);
300 if (tok
&& tok
->type
== '-') {
303 } else if (tok
&& tok
->type
== '+') {
306 } else if (tok
&& tok
->type
== ISL_TOKEN_VALUE
&&
307 isl_int_is_neg(tok
->u
.v
)) {
308 isl_stream_push_token(s
, tok
);
311 isl_stream_push_token(s
, tok
);
323 static __isl_give isl_basic_map
*read_var_def(struct isl_stream
*s
,
324 __isl_take isl_basic_map
*bmap
, enum isl_dim_type type
, struct vars
*v
)
329 vec
= accept_affine(s
, v
);
332 v
->v
= variable_new(v
, "", 0, v
->n
);
336 bmap
= isl_basic_map_extend_constraints(bmap
, 1, 0);
337 k
= isl_basic_map_alloc_equality(bmap
);
339 isl_seq_cpy(bmap
->eq
[k
], vec
->el
, vec
->size
);
340 isl_int_set_si(bmap
->eq
[k
][vec
->size
], -1);
348 isl_basic_map_free(bmap
);
352 static __isl_give isl_basic_map
*read_var_list(struct isl_stream
*s
,
353 __isl_take isl_basic_map
*bmap
, enum isl_dim_type type
, struct vars
*v
)
356 struct isl_token
*tok
;
358 while ((tok
= isl_stream_next_token(s
)) != NULL
) {
361 if (tok
->type
== ISL_TOKEN_IDENT
) {
363 int p
= vars_pos(v
, tok
->u
.s
, -1);
370 bmap
= isl_basic_map_add(bmap
, type
, 1);
371 bmap
= set_name(bmap
, type
, i
, v
->v
->name
);
373 } else if (tok
->type
== ISL_TOKEN_IDENT
||
374 tok
->type
== ISL_TOKEN_VALUE
) {
375 if (type
== isl_dim_param
) {
376 isl_stream_error(s
, tok
,
377 "expecting unique identifier");
380 isl_stream_push_token(s
, tok
);
382 bmap
= isl_basic_map_add(bmap
, type
, 1);
383 bmap
= read_var_def(s
, bmap
, type
, v
);
387 tok
= isl_stream_next_token(s
);
388 if (!tok
|| tok
->type
!= ',')
395 isl_stream_push_token(s
, tok
);
400 isl_basic_map_free(bmap
);
404 static __isl_give isl_mat
*accept_affine_list(struct isl_stream
*s
,
409 struct isl_token
*tok
= NULL
;
411 vec
= accept_affine(s
, v
);
412 mat
= isl_mat_from_row_vec(vec
);
417 tok
= isl_stream_next_token(s
);
419 isl_stream_error(s
, NULL
, "unexpected EOF");
422 if (tok
->type
!= ',') {
423 isl_stream_push_token(s
, tok
);
428 vec
= accept_affine(s
, v
);
429 mat
= isl_mat_vec_concat(mat
, vec
);
440 static struct isl_basic_map
*add_div_definition(struct isl_stream
*s
,
441 struct vars
*v
, struct isl_basic_map
*bmap
, int k
)
443 struct isl_token
*tok
;
447 if (isl_stream_eat(s
, '['))
450 tok
= isl_stream_next_token(s
);
453 if (tok
->type
== '(') {
457 isl_stream_push_token(s
, tok
);
459 aff
= accept_affine(s
, v
);
463 isl_seq_cpy(bmap
->div
[k
] + 1, aff
->el
, aff
->size
);
467 if (seen_paren
&& isl_stream_eat(s
, ')'))
469 if (isl_stream_eat(s
, '/'))
472 tok
= isl_stream_next_token(s
);
475 if (tok
->type
!= ISL_TOKEN_VALUE
) {
476 isl_stream_error(s
, tok
, "expected denominator");
477 isl_stream_push_token(s
, tok
);
480 isl_int_set(bmap
->div
[k
][0], tok
->u
.v
);
483 if (isl_stream_eat(s
, ']'))
486 if (isl_basic_map_add_div_constraints(bmap
, k
) < 0)
491 isl_basic_map_free(bmap
);
495 static struct isl_basic_map
*read_defined_var_list(struct isl_stream
*s
,
496 struct vars
*v
, struct isl_basic_map
*bmap
)
498 struct isl_token
*tok
;
500 while ((tok
= isl_stream_next_token(s
)) != NULL
) {
504 unsigned total
= isl_basic_map_total_dim(bmap
);
506 if (tok
->type
!= ISL_TOKEN_IDENT
)
509 p
= vars_pos(v
, tok
->u
.s
, -1);
513 isl_stream_error(s
, tok
, "expecting unique identifier");
517 bmap
= isl_basic_map_cow(bmap
);
518 bmap
= isl_basic_map_extend_dim(bmap
, isl_dim_copy(bmap
->dim
),
521 if ((k
= isl_basic_map_alloc_div(bmap
)) < 0)
523 isl_seq_clr(bmap
->div
[k
], 1 + 1 + total
);
526 tok
= isl_stream_next_token(s
);
527 if (tok
&& tok
->type
== '=') {
529 bmap
= add_div_definition(s
, v
, bmap
, k
);
530 tok
= isl_stream_next_token(s
);
533 if (!tok
|| tok
->type
!= ',')
539 isl_stream_push_token(s
, tok
);
544 isl_basic_map_free(bmap
);
548 static __isl_give isl_basic_map
*read_tuple(struct isl_stream
*s
,
549 __isl_take isl_basic_map
*bmap
, enum isl_dim_type type
, struct vars
*v
)
551 struct isl_token
*tok
;
554 tok
= isl_stream_next_token(s
);
555 if (tok
&& tok
->type
== ISL_TOKEN_IDENT
) {
556 name
= strdup(tok
->u
.s
);
560 tok
= isl_stream_next_token(s
);
562 if (!tok
|| tok
->type
!= '[') {
563 isl_stream_error(s
, tok
, "expecting '['");
567 bmap
= read_var_list(s
, bmap
, type
, v
);
568 tok
= isl_stream_next_token(s
);
569 if (!tok
|| tok
->type
!= ']') {
570 isl_stream_error(s
, tok
, "expecting ']'");
576 bmap
= isl_basic_map_set_tuple_name(bmap
, type
, name
);
584 isl_basic_map_free(bmap
);
588 static struct isl_basic_map
*add_constraints(struct isl_stream
*s
,
589 struct vars
*v
, struct isl_basic_map
*bmap
);
591 static struct isl_basic_map
*add_exists(struct isl_stream
*s
,
592 struct vars
*v
, struct isl_basic_map
*bmap
)
594 struct isl_token
*tok
;
601 tok
= isl_stream_next_token(s
);
604 if (tok
->type
== '(') {
608 isl_stream_push_token(s
, tok
);
610 bmap
= read_defined_var_list(s
, v
, bmap
);
614 if (isl_stream_eat(s
, ':'))
616 bmap
= add_constraints(s
, v
, bmap
);
617 if (seen_paren
&& isl_stream_eat(s
, ')'))
621 isl_basic_map_free(bmap
);
625 static __isl_give isl_basic_map
*construct_constraint(
626 __isl_take isl_basic_map
*bmap
, enum isl_token_type type
,
627 isl_int
*left
, isl_int
*right
)
635 len
= 1 + isl_basic_map_total_dim(bmap
);
638 k
= isl_basic_map_alloc_inequality(bmap
);
641 if (type
== ISL_TOKEN_LE
)
642 isl_seq_combine(bmap
->ineq
[k
], ctx
->negone
, left
,
645 else if (type
== ISL_TOKEN_GE
)
646 isl_seq_combine(bmap
->ineq
[k
], ctx
->one
, left
,
649 else if (type
== ISL_TOKEN_LT
) {
650 isl_seq_combine(bmap
->ineq
[k
], ctx
->negone
, left
,
653 isl_int_sub_ui(bmap
->ineq
[k
][0], bmap
->ineq
[k
][0], 1);
654 } else if (type
== ISL_TOKEN_GT
) {
655 isl_seq_combine(bmap
->ineq
[k
], ctx
->one
, left
,
658 isl_int_sub_ui(bmap
->ineq
[k
][0], bmap
->ineq
[k
][0], 1);
660 isl_seq_combine(bmap
->ineq
[k
], ctx
->one
, left
,
663 isl_basic_map_inequality_to_equality(bmap
, k
);
668 isl_basic_map_free(bmap
);
672 static int is_comparator(struct isl_token
*tok
)
689 static struct isl_basic_map
*add_constraint(struct isl_stream
*s
,
690 struct vars
*v
, struct isl_basic_map
*bmap
)
693 unsigned total
= isl_basic_map_total_dim(bmap
);
694 struct isl_token
*tok
= NULL
;
695 struct isl_mat
*aff1
= NULL
, *aff2
= NULL
;
697 tok
= isl_stream_next_token(s
);
700 if (tok
->type
== ISL_TOKEN_EXISTS
) {
702 return add_exists(s
, v
, bmap
);
704 isl_stream_push_token(s
, tok
);
707 bmap
= isl_basic_map_cow(bmap
);
709 aff1
= accept_affine_list(s
, v
);
712 tok
= isl_stream_next_token(s
);
713 if (!is_comparator(tok
)) {
714 isl_stream_error(s
, tok
, "missing operator");
716 isl_stream_push_token(s
, tok
);
720 isl_assert(aff1
->ctx
, aff1
->n_col
== 1 + total
, goto error
);
722 aff2
= accept_affine_list(s
, v
);
725 isl_assert(aff2
->ctx
, aff2
->n_col
== 1 + total
, goto error
);
727 bmap
= isl_basic_map_extend_constraints(bmap
, 0,
728 aff1
->n_row
* aff2
->n_row
);
729 for (i
= 0; i
< aff1
->n_row
; ++i
)
730 for (j
= 0; j
< aff2
->n_row
; ++j
)
731 bmap
= construct_constraint(bmap
, tok
->type
,
732 aff1
->row
[i
], aff2
->row
[j
]);
737 tok
= isl_stream_next_token(s
);
738 if (!is_comparator(tok
)) {
740 isl_stream_push_token(s
, tok
);
752 isl_basic_map_free(bmap
);
756 static struct isl_basic_map
*add_constraints(struct isl_stream
*s
,
757 struct vars
*v
, struct isl_basic_map
*bmap
)
759 struct isl_token
*tok
;
762 bmap
= add_constraint(s
, v
, bmap
);
765 tok
= isl_stream_next_token(s
);
767 isl_stream_error(s
, NULL
, "unexpected EOF");
770 if (tok
->type
!= ISL_TOKEN_AND
)
774 isl_stream_push_token(s
, tok
);
780 isl_basic_map_free(bmap
);
784 static struct isl_basic_map
*read_disjunct(struct isl_stream
*s
,
785 struct vars
*v
, __isl_take isl_dim
*dim
)
788 struct isl_token
*tok
;
789 struct isl_basic_map
*bmap
;
791 bmap
= isl_basic_map_alloc_dim(dim
, 0, 0, 0);
795 tok
= isl_stream_next_token(s
);
798 if (tok
->type
== '(') {
802 isl_stream_push_token(s
, tok
);
804 bmap
= add_constraints(s
, v
, bmap
);
805 bmap
= isl_basic_map_simplify(bmap
);
806 bmap
= isl_basic_map_finalize(bmap
);
808 if (seen_paren
&& isl_stream_eat(s
, ')'))
813 isl_basic_map_free(bmap
);
817 static struct isl_map
*read_disjuncts(struct isl_stream
*s
,
818 struct vars
*v
, __isl_take isl_dim
*dim
)
820 struct isl_token
*tok
;
823 tok
= isl_stream_next_token(s
);
825 isl_stream_error(s
, NULL
, "unexpected EOF");
828 if (tok
->type
== '}') {
829 isl_stream_push_token(s
, tok
);
830 return isl_map_universe(dim
);
832 isl_stream_push_token(s
, tok
);
834 map
= isl_map_empty(isl_dim_copy(dim
));
836 struct isl_basic_map
*bmap
;
839 bmap
= read_disjunct(s
, v
, isl_dim_copy(dim
));
840 map
= isl_map_union(map
, isl_map_from_basic_map(bmap
));
842 vars_drop(v
, v
->n
- n
);
844 tok
= isl_stream_next_token(s
);
845 if (!tok
|| tok
->type
!= ISL_TOKEN_OR
)
850 isl_stream_push_token(s
, tok
);
859 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map
*bmap
, int pos
)
861 if (pos
< isl_basic_map_dim(bmap
, isl_dim_out
))
862 return 1 + isl_basic_map_dim(bmap
, isl_dim_param
) +
863 isl_basic_map_dim(bmap
, isl_dim_in
) + pos
;
864 pos
-= isl_basic_map_dim(bmap
, isl_dim_out
);
866 if (pos
< isl_basic_map_dim(bmap
, isl_dim_in
))
867 return 1 + isl_basic_map_dim(bmap
, isl_dim_param
) + pos
;
868 pos
-= isl_basic_map_dim(bmap
, isl_dim_in
);
870 if (pos
< isl_basic_map_dim(bmap
, isl_dim_div
))
871 return 1 + isl_basic_map_dim(bmap
, isl_dim_param
) +
872 isl_basic_map_dim(bmap
, isl_dim_in
) +
873 isl_basic_map_dim(bmap
, isl_dim_out
) + pos
;
874 pos
-= isl_basic_map_dim(bmap
, isl_dim_div
);
876 if (pos
< isl_basic_map_dim(bmap
, isl_dim_param
))
882 static __isl_give isl_basic_map
*basic_map_read_polylib_constraint(
883 struct isl_stream
*s
, __isl_take isl_basic_map
*bmap
)
886 struct isl_token
*tok
;
896 nparam
= isl_basic_map_dim(bmap
, isl_dim_param
);
897 dim
= isl_basic_map_dim(bmap
, isl_dim_out
);
899 tok
= isl_stream_next_token(s
);
900 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
901 isl_stream_error(s
, tok
, "expecting coefficient");
903 isl_stream_push_token(s
, tok
);
906 if (!tok
->on_new_line
) {
907 isl_stream_error(s
, tok
, "coefficient should appear on new line");
908 isl_stream_push_token(s
, tok
);
912 type
= isl_int_get_si(tok
->u
.v
);
915 isl_assert(s
->ctx
, type
== 0 || type
== 1, goto error
);
917 k
= isl_basic_map_alloc_equality(bmap
);
920 k
= isl_basic_map_alloc_inequality(bmap
);
926 for (j
= 0; j
< 1 + isl_basic_map_total_dim(bmap
); ++j
) {
928 tok
= isl_stream_next_token(s
);
929 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
930 isl_stream_error(s
, tok
, "expecting coefficient");
932 isl_stream_push_token(s
, tok
);
935 if (tok
->on_new_line
) {
936 isl_stream_error(s
, tok
,
937 "coefficient should not appear on new line");
938 isl_stream_push_token(s
, tok
);
941 pos
= polylib_pos_to_isl_pos(bmap
, j
);
942 isl_int_set(c
[pos
], tok
->u
.v
);
948 isl_basic_map_free(bmap
);
952 static __isl_give isl_basic_map
*basic_map_read_polylib(struct isl_stream
*s
,
956 struct isl_token
*tok
;
957 struct isl_token
*tok2
;
960 unsigned in
= 0, out
, local
= 0;
961 struct isl_basic_map
*bmap
= NULL
;
966 tok
= isl_stream_next_token(s
);
968 isl_stream_error(s
, NULL
, "unexpected EOF");
971 tok2
= isl_stream_next_token(s
);
974 isl_stream_error(s
, NULL
, "unexpected EOF");
977 n_row
= isl_int_get_si(tok
->u
.v
);
978 n_col
= isl_int_get_si(tok2
->u
.v
);
979 on_new_line
= tok2
->on_new_line
;
980 isl_token_free(tok2
);
982 isl_assert(s
->ctx
, !on_new_line
, return NULL
);
983 isl_assert(s
->ctx
, n_row
>= 0, return NULL
);
984 isl_assert(s
->ctx
, n_col
>= 2 + nparam
, return NULL
);
985 tok
= isl_stream_next_token_on_same_line(s
);
987 if (tok
->type
!= ISL_TOKEN_VALUE
) {
988 isl_stream_error(s
, tok
,
989 "expecting number of output dimensions");
990 isl_stream_push_token(s
, tok
);
993 out
= isl_int_get_si(tok
->u
.v
);
996 tok
= isl_stream_next_token_on_same_line(s
);
997 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
998 isl_stream_error(s
, tok
,
999 "expecting number of input dimensions");
1001 isl_stream_push_token(s
, tok
);
1004 in
= isl_int_get_si(tok
->u
.v
);
1005 isl_token_free(tok
);
1007 tok
= isl_stream_next_token_on_same_line(s
);
1008 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
1009 isl_stream_error(s
, tok
,
1010 "expecting number of existentials");
1012 isl_stream_push_token(s
, tok
);
1015 local
= isl_int_get_si(tok
->u
.v
);
1016 isl_token_free(tok
);
1018 tok
= isl_stream_next_token_on_same_line(s
);
1019 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
1020 isl_stream_error(s
, tok
,
1021 "expecting number of parameters");
1023 isl_stream_push_token(s
, tok
);
1026 nparam
= isl_int_get_si(tok
->u
.v
);
1027 isl_token_free(tok
);
1028 if (n_col
!= 1 + out
+ in
+ local
+ nparam
+ 1) {
1029 isl_stream_error(s
, NULL
,
1030 "dimensions don't match");
1034 out
= n_col
- 2 - nparam
;
1035 bmap
= isl_basic_map_alloc(s
->ctx
, nparam
, in
, out
, local
, n_row
, n_row
);
1039 for (i
= 0; i
< local
; ++i
) {
1040 int k
= isl_basic_map_alloc_div(bmap
);
1045 for (i
= 0; i
< n_row
; ++i
)
1046 bmap
= basic_map_read_polylib_constraint(s
, bmap
);
1048 tok
= isl_stream_next_token_on_same_line(s
);
1050 isl_stream_error(s
, tok
, "unexpected extra token on line");
1051 isl_stream_push_token(s
, tok
);
1055 bmap
= isl_basic_map_simplify(bmap
);
1056 bmap
= isl_basic_map_finalize(bmap
);
1059 isl_basic_map_free(bmap
);
1063 static struct isl_map
*map_read_polylib(struct isl_stream
*s
, int nparam
)
1065 struct isl_token
*tok
;
1066 struct isl_token
*tok2
;
1068 struct isl_map
*map
;
1070 tok
= isl_stream_next_token(s
);
1072 isl_stream_error(s
, NULL
, "unexpected EOF");
1075 tok2
= isl_stream_next_token_on_same_line(s
);
1077 isl_stream_push_token(s
, tok2
);
1078 isl_stream_push_token(s
, tok
);
1079 return isl_map_from_basic_map(basic_map_read_polylib(s
, nparam
));
1081 n
= isl_int_get_si(tok
->u
.v
);
1082 isl_token_free(tok
);
1084 isl_assert(s
->ctx
, n
>= 1, return NULL
);
1086 map
= isl_map_from_basic_map(basic_map_read_polylib(s
, nparam
));
1088 for (i
= 1; i
< n
; ++i
)
1089 map
= isl_map_union(map
,
1090 isl_map_from_basic_map(basic_map_read_polylib(s
, nparam
)));
1095 static int optional_power(struct isl_stream
*s
)
1098 struct isl_token
*tok
;
1100 tok
= isl_stream_next_token(s
);
1103 if (tok
->type
!= '^') {
1104 isl_stream_push_token(s
, tok
);
1107 isl_token_free(tok
);
1108 tok
= isl_stream_next_token(s
);
1109 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
1110 isl_stream_error(s
, tok
, "expecting exponent");
1112 isl_stream_push_token(s
, tok
);
1115 pow
= isl_int_get_si(tok
->u
.v
);
1116 isl_token_free(tok
);
1120 static __isl_give isl_div
*read_div(struct isl_stream
*s
,
1121 __isl_keep isl_basic_map
*bmap
, struct vars
*v
)
1123 unsigned total
= isl_basic_map_total_dim(bmap
);
1126 bmap
= isl_basic_map_copy(bmap
);
1127 bmap
= isl_basic_map_cow(bmap
);
1128 bmap
= isl_basic_map_extend_dim(bmap
, isl_dim_copy(bmap
->dim
),
1131 if ((k
= isl_basic_map_alloc_div(bmap
)) < 0)
1133 isl_seq_clr(bmap
->div
[k
], 1 + 1 + total
);
1134 bmap
= add_div_definition(s
, v
, bmap
, k
);
1136 return isl_basic_map_div(bmap
, k
);
1138 isl_basic_map_free(bmap
);
1142 static __isl_give isl_qpolynomial
*read_term(struct isl_stream
*s
,
1143 __isl_keep isl_basic_map
*bmap
, struct vars
*v
);
1145 static __isl_give isl_qpolynomial
*read_factor(struct isl_stream
*s
,
1146 __isl_keep isl_basic_map
*bmap
, struct vars
*v
)
1148 struct isl_qpolynomial
*qp
;
1149 struct isl_token
*tok
;
1151 tok
= isl_stream_next_token(s
);
1153 isl_stream_error(s
, NULL
, "unexpected EOF");
1156 if (tok
->type
== '(') {
1157 isl_token_free(tok
);
1158 qp
= read_term(s
, bmap
, v
);
1161 if (isl_stream_eat(s
, ')'))
1163 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
1164 struct isl_token
*tok2
;
1165 tok2
= isl_stream_next_token(s
);
1166 if (tok2
&& tok2
->type
== '/') {
1167 isl_token_free(tok2
);
1168 tok2
= isl_stream_next_token(s
);
1169 if (!tok2
|| tok2
->type
!= ISL_TOKEN_VALUE
) {
1170 isl_stream_error(s
, tok2
, "expected denominator");
1171 isl_token_free(tok
);
1172 isl_token_free(tok2
);
1175 qp
= isl_qpolynomial_rat_cst(isl_basic_map_get_dim(bmap
),
1176 tok
->u
.v
, tok2
->u
.v
);
1177 isl_token_free(tok2
);
1179 isl_stream_push_token(s
, tok2
);
1180 qp
= isl_qpolynomial_cst(isl_basic_map_get_dim(bmap
),
1183 isl_token_free(tok
);
1184 } else if (tok
->type
== ISL_TOKEN_INFTY
) {
1185 isl_token_free(tok
);
1186 qp
= isl_qpolynomial_infty(isl_basic_map_get_dim(bmap
));
1187 } else if (tok
->type
== ISL_TOKEN_NAN
) {
1188 isl_token_free(tok
);
1189 qp
= isl_qpolynomial_nan(isl_basic_map_get_dim(bmap
));
1190 } else if (tok
->type
== ISL_TOKEN_IDENT
) {
1192 int pos
= vars_pos(v
, tok
->u
.s
, -1);
1194 isl_token_free(tok
);
1198 isl_stream_error(s
, tok
, "unknown identifier");
1201 pow
= optional_power(s
);
1202 qp
= isl_qpolynomial_pow(isl_basic_map_get_dim(bmap
), pos
, pow
);
1203 } else if (tok
->type
== '[') {
1207 isl_stream_push_token(s
, tok
);
1208 div
= read_div(s
, bmap
, v
);
1209 pow
= optional_power(s
);
1210 qp
= isl_qpolynomial_div_pow(div
, pow
);
1211 } else if (tok
->type
== '-') {
1212 struct isl_qpolynomial
*qp2
;
1214 isl_token_free(tok
);
1215 qp
= isl_qpolynomial_cst(isl_basic_map_get_dim(bmap
),
1217 qp2
= read_factor(s
, bmap
, v
);
1218 qp
= isl_qpolynomial_mul(qp
, qp2
);
1220 isl_stream_error(s
, tok
, "unexpected isl_token");
1221 isl_stream_push_token(s
, tok
);
1225 if (isl_stream_eat_if_available(s
, '*') ||
1226 isl_stream_next_token_is(s
, ISL_TOKEN_IDENT
)) {
1227 struct isl_qpolynomial
*qp2
;
1229 qp2
= read_factor(s
, bmap
, v
);
1230 qp
= isl_qpolynomial_mul(qp
, qp2
);
1235 isl_qpolynomial_free(qp
);
1239 static __isl_give isl_qpolynomial
*read_term(struct isl_stream
*s
,
1240 __isl_keep isl_basic_map
*bmap
, struct vars
*v
)
1242 struct isl_token
*tok
;
1243 struct isl_qpolynomial
*qp
;
1245 qp
= read_factor(s
, bmap
, v
);
1248 tok
= isl_stream_next_token(s
);
1252 if (tok
->type
== '+') {
1253 struct isl_qpolynomial
*qp2
;
1255 isl_token_free(tok
);
1256 qp2
= read_factor(s
, bmap
, v
);
1257 qp
= isl_qpolynomial_add(qp
, qp2
);
1258 } else if (tok
->type
== '-') {
1259 struct isl_qpolynomial
*qp2
;
1261 isl_token_free(tok
);
1262 qp2
= read_factor(s
, bmap
, v
);
1263 qp
= isl_qpolynomial_sub(qp
, qp2
);
1264 } else if (tok
->type
== ISL_TOKEN_VALUE
&&
1265 isl_int_is_neg(tok
->u
.v
)) {
1266 struct isl_qpolynomial
*qp2
;
1268 qp2
= isl_qpolynomial_cst(isl_basic_map_get_dim(bmap
),
1270 isl_token_free(tok
);
1271 qp
= isl_qpolynomial_add(qp
, qp2
);
1273 isl_stream_push_token(s
, tok
);
1281 static __isl_give isl_map
*read_optional_disjuncts(struct isl_stream
*s
,
1282 __isl_take isl_basic_map
*bmap
, struct vars
*v
)
1284 struct isl_token
*tok
;
1285 struct isl_map
*map
;
1287 tok
= isl_stream_next_token(s
);
1289 isl_stream_error(s
, NULL
, "unexpected EOF");
1292 map
= isl_map_from_basic_map(isl_basic_map_copy(bmap
));
1293 if (tok
->type
== ':') {
1294 isl_token_free(tok
);
1295 map
= isl_map_intersect(map
,
1296 read_disjuncts(s
, v
, isl_basic_map_get_dim(bmap
)));
1298 isl_stream_push_token(s
, tok
);
1300 isl_basic_map_free(bmap
);
1304 isl_basic_map_free(bmap
);
1308 static struct isl_obj
obj_read_poly(struct isl_stream
*s
,
1309 __isl_take isl_basic_map
*bmap
, struct vars
*v
, int n
)
1311 struct isl_obj obj
= { isl_obj_pw_qpolynomial
, NULL
};
1312 struct isl_pw_qpolynomial
*pwqp
;
1313 struct isl_qpolynomial
*qp
;
1314 struct isl_map
*map
;
1315 struct isl_set
*set
;
1317 bmap
= isl_basic_map_reverse(bmap
);
1319 qp
= read_term(s
, bmap
, v
);
1320 map
= read_optional_disjuncts(s
, bmap
, v
);
1321 set
= isl_map_range(map
);
1323 pwqp
= isl_pw_qpolynomial_alloc(set
, qp
);
1325 vars_drop(v
, v
->n
- n
);
1331 static int next_is_tuple(struct isl_stream
*s
)
1333 struct isl_token
*tok
;
1336 tok
= isl_stream_next_token(s
);
1339 if (tok
->type
== '[') {
1340 isl_stream_push_token(s
, tok
);
1343 if (tok
->type
!= ISL_TOKEN_IDENT
) {
1344 isl_stream_push_token(s
, tok
);
1348 is_tuple
= isl_stream_next_token_is(s
, '[');
1350 isl_stream_push_token(s
, tok
);
1355 static struct isl_obj
obj_read_body(struct isl_stream
*s
,
1356 __isl_take isl_basic_map
*bmap
, struct vars
*v
)
1358 struct isl_map
*map
= NULL
;
1359 struct isl_token
*tok
;
1360 struct isl_obj obj
= { isl_obj_set
, NULL
};
1363 if (!next_is_tuple(s
))
1364 return obj_read_poly(s
, bmap
, v
, n
);
1366 bmap
= read_tuple(s
, bmap
, isl_dim_in
, v
);
1369 tok
= isl_stream_next_token(s
);
1370 if (tok
&& tok
->type
== ISL_TOKEN_TO
) {
1371 obj
.type
= isl_obj_map
;
1372 isl_token_free(tok
);
1373 if (!next_is_tuple(s
))
1374 return obj_read_poly(s
, bmap
, v
, n
);
1375 bmap
= read_tuple(s
, bmap
, isl_dim_out
, v
);
1379 bmap
= isl_basic_map_reverse(bmap
);
1381 isl_stream_push_token(s
, tok
);
1384 map
= read_optional_disjuncts(s
, bmap
, v
);
1386 vars_drop(v
, v
->n
- n
);
1391 isl_basic_map_free(bmap
);
1392 obj
.type
= isl_obj_none
;
1396 static struct isl_obj
to_union(isl_ctx
*ctx
, struct isl_obj obj
)
1398 if (obj
.type
== isl_obj_map
) {
1399 obj
.v
= isl_union_map_from_map(obj
.v
);
1400 obj
.type
= isl_obj_union_map
;
1401 } else if (obj
.type
== isl_obj_set
) {
1402 obj
.v
= isl_union_set_from_set(obj
.v
);
1403 obj
.type
= isl_obj_union_set
;
1404 } else if (obj
.type
== isl_obj_pw_qpolynomial
) {
1405 obj
.v
= isl_union_pw_qpolynomial_from_pw_qpolynomial(obj
.v
);
1406 obj
.type
= isl_obj_union_pw_qpolynomial
;
1407 } else if (obj
.type
== isl_obj_pw_qpolynomial_fold
) {
1408 obj
.v
= isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj
.v
);
1409 obj
.type
= isl_obj_union_pw_qpolynomial_fold
;
1411 isl_assert(ctx
, 0, goto error
);
1414 obj
.type
->free(obj
.v
);
1415 obj
.type
= isl_obj_none
;
1419 static struct isl_obj
obj_add(struct isl_ctx
*ctx
,
1420 struct isl_obj obj1
, struct isl_obj obj2
)
1422 if (obj1
.type
== isl_obj_set
&& obj2
.type
== isl_obj_union_set
)
1423 obj1
= to_union(ctx
, obj1
);
1424 if (obj1
.type
== isl_obj_union_set
&& obj2
.type
== isl_obj_set
)
1425 obj2
= to_union(ctx
, obj2
);
1426 if (obj1
.type
== isl_obj_map
&& obj2
.type
== isl_obj_union_map
)
1427 obj1
= to_union(ctx
, obj1
);
1428 if (obj1
.type
== isl_obj_union_map
&& obj2
.type
== isl_obj_map
)
1429 obj2
= to_union(ctx
, obj2
);
1430 if (obj1
.type
== isl_obj_pw_qpolynomial
&&
1431 obj2
.type
== isl_obj_union_pw_qpolynomial
)
1432 obj1
= to_union(ctx
, obj1
);
1433 if (obj1
.type
== isl_obj_union_pw_qpolynomial
&&
1434 obj2
.type
== isl_obj_pw_qpolynomial
)
1435 obj2
= to_union(ctx
, obj2
);
1436 if (obj1
.type
== isl_obj_pw_qpolynomial_fold
&&
1437 obj2
.type
== isl_obj_union_pw_qpolynomial_fold
)
1438 obj1
= to_union(ctx
, obj1
);
1439 if (obj1
.type
== isl_obj_union_pw_qpolynomial_fold
&&
1440 obj2
.type
== isl_obj_pw_qpolynomial_fold
)
1441 obj2
= to_union(ctx
, obj2
);
1442 isl_assert(ctx
, obj1
.type
== obj2
.type
, goto error
);
1443 if (obj1
.type
== isl_obj_map
&& !isl_map_has_equal_dim(obj1
.v
, obj2
.v
)) {
1444 obj1
= to_union(ctx
, obj1
);
1445 obj2
= to_union(ctx
, obj2
);
1447 if (obj1
.type
== isl_obj_set
&& !isl_set_has_equal_dim(obj1
.v
, obj2
.v
)) {
1448 obj1
= to_union(ctx
, obj1
);
1449 obj2
= to_union(ctx
, obj2
);
1451 if (obj1
.type
== isl_obj_pw_qpolynomial
&&
1452 !isl_pw_qpolynomial_has_equal_dim(obj1
.v
, obj2
.v
)) {
1453 obj1
= to_union(ctx
, obj1
);
1454 obj2
= to_union(ctx
, obj2
);
1456 if (obj1
.type
== isl_obj_pw_qpolynomial_fold
&&
1457 !isl_pw_qpolynomial_fold_has_equal_dim(obj1
.v
, obj2
.v
)) {
1458 obj1
= to_union(ctx
, obj1
);
1459 obj2
= to_union(ctx
, obj2
);
1461 obj1
.v
= obj1
.type
->add(obj1
.v
, obj2
.v
);
1464 obj1
.type
->free(obj1
.v
);
1465 obj2
.type
->free(obj2
.v
);
1466 obj1
.type
= isl_obj_none
;
1471 static struct isl_obj
obj_read(struct isl_stream
*s
, int nparam
)
1473 struct isl_basic_map
*bmap
= NULL
;
1474 struct isl_token
*tok
;
1475 struct vars
*v
= NULL
;
1476 struct isl_obj obj
= { isl_obj_set
, NULL
};
1478 tok
= isl_stream_next_token(s
);
1480 isl_stream_error(s
, NULL
, "unexpected EOF");
1483 if (tok
->type
== ISL_TOKEN_VALUE
) {
1484 struct isl_map
*map
;
1485 isl_stream_push_token(s
, tok
);
1486 map
= map_read_polylib(s
, nparam
);
1489 if (isl_map_dim(map
, isl_dim_in
) > 0)
1490 obj
.type
= isl_obj_map
;
1494 v
= vars_new(s
->ctx
);
1496 isl_stream_push_token(s
, tok
);
1499 bmap
= isl_basic_map_alloc(s
->ctx
, 0, 0, 0, 0, 0, 0);
1500 if (tok
->type
== '[') {
1501 isl_stream_push_token(s
, tok
);
1502 bmap
= read_tuple(s
, bmap
, isl_dim_param
, v
);
1506 isl_assert(s
->ctx
, nparam
== v
->n
, goto error
);
1507 tok
= isl_stream_next_token(s
);
1508 if (!tok
|| tok
->type
!= ISL_TOKEN_TO
) {
1509 isl_stream_error(s
, tok
, "expecting '->'");
1511 isl_stream_push_token(s
, tok
);
1514 isl_token_free(tok
);
1515 tok
= isl_stream_next_token(s
);
1516 } else if (nparam
> 0)
1517 bmap
= isl_basic_map_add(bmap
, isl_dim_param
, nparam
);
1518 if (!tok
|| tok
->type
!= '{') {
1519 isl_stream_error(s
, tok
, "expecting '{'");
1521 isl_stream_push_token(s
, tok
);
1524 isl_token_free(tok
);
1526 tok
= isl_stream_next_token(s
);
1529 else if (tok
->type
== ISL_TOKEN_IDENT
&& !strcmp(tok
->u
.s
, "Sym")) {
1530 isl_token_free(tok
);
1531 if (isl_stream_eat(s
, '='))
1533 bmap
= read_tuple(s
, bmap
, isl_dim_param
, v
);
1537 isl_assert(s
->ctx
, nparam
== v
->n
, goto error
);
1538 } else if (tok
->type
== '}') {
1539 obj
.type
= isl_obj_union_set
;
1540 obj
.v
= isl_union_set_empty(isl_basic_map_get_dim(bmap
));
1541 isl_token_free(tok
);
1544 isl_stream_push_token(s
, tok
);
1549 o
= obj_read_body(s
, isl_basic_map_copy(bmap
), v
);
1550 if (o
.type
== isl_obj_none
)
1555 obj
= obj_add(s
->ctx
, obj
, o
);
1556 if (obj
.type
== isl_obj_none
)
1559 tok
= isl_stream_next_token(s
);
1560 if (!tok
|| tok
->type
!= ';')
1562 isl_token_free(tok
);
1565 if (tok
&& tok
->type
== '}') {
1566 isl_token_free(tok
);
1568 isl_stream_error(s
, tok
, "unexpected isl_token");
1570 isl_token_free(tok
);
1575 isl_basic_map_free(bmap
);
1579 isl_basic_map_free(bmap
);
1580 obj
.type
->free(obj
.v
);
1587 struct isl_obj
isl_stream_read_obj(struct isl_stream
*s
)
1589 return obj_read(s
, -1);
1592 __isl_give isl_map
*isl_stream_read_map(struct isl_stream
*s
, int nparam
)
1595 struct isl_map
*map
;
1597 obj
= obj_read(s
, nparam
);
1599 isl_assert(s
->ctx
, obj
.type
== isl_obj_map
||
1600 obj
.type
== isl_obj_set
, goto error
);
1604 obj
.type
->free(obj
.v
);
1608 __isl_give isl_set
*isl_stream_read_set(struct isl_stream
*s
, int nparam
)
1611 struct isl_set
*set
;
1613 obj
= obj_read(s
, nparam
);
1615 isl_assert(s
->ctx
, obj
.type
== isl_obj_set
, goto error
);
1619 obj
.type
->free(obj
.v
);
1623 static struct isl_basic_map
*basic_map_read(struct isl_stream
*s
, int nparam
)
1626 struct isl_map
*map
;
1627 struct isl_basic_map
*bmap
;
1629 obj
= obj_read(s
, nparam
);
1634 isl_assert(map
->ctx
, map
->n
<= 1, goto error
);
1637 bmap
= isl_basic_map_empty_like_map(map
);
1639 bmap
= isl_basic_map_copy(map
->p
[0]);
1649 __isl_give isl_basic_map
*isl_basic_map_read_from_file(isl_ctx
*ctx
,
1650 FILE *input
, int nparam
)
1652 struct isl_basic_map
*bmap
;
1653 struct isl_stream
*s
= isl_stream_new_file(ctx
, input
);
1656 bmap
= basic_map_read(s
, nparam
);
1661 __isl_give isl_basic_set
*isl_basic_set_read_from_file(isl_ctx
*ctx
,
1662 FILE *input
, int nparam
)
1664 struct isl_basic_map
*bmap
;
1665 bmap
= isl_basic_map_read_from_file(ctx
, input
, nparam
);
1668 isl_assert(ctx
, isl_basic_map_n_in(bmap
) == 0, goto error
);
1669 return (struct isl_basic_set
*)bmap
;
1671 isl_basic_map_free(bmap
);
1675 struct isl_basic_map
*isl_basic_map_read_from_str(struct isl_ctx
*ctx
,
1676 const char *str
, int nparam
)
1678 struct isl_basic_map
*bmap
;
1679 struct isl_stream
*s
= isl_stream_new_str(ctx
, str
);
1682 bmap
= basic_map_read(s
, nparam
);
1687 struct isl_basic_set
*isl_basic_set_read_from_str(struct isl_ctx
*ctx
,
1688 const char *str
, int nparam
)
1690 struct isl_basic_map
*bmap
;
1691 bmap
= isl_basic_map_read_from_str(ctx
, str
, nparam
);
1694 isl_assert(ctx
, isl_basic_map_n_in(bmap
) == 0, goto error
);
1695 return (struct isl_basic_set
*)bmap
;
1697 isl_basic_map_free(bmap
);
1701 __isl_give isl_map
*isl_map_read_from_file(struct isl_ctx
*ctx
,
1702 FILE *input
, int nparam
)
1704 struct isl_map
*map
;
1705 struct isl_stream
*s
= isl_stream_new_file(ctx
, input
);
1708 map
= isl_stream_read_map(s
, nparam
);
1713 __isl_give isl_map
*isl_map_read_from_str(struct isl_ctx
*ctx
,
1714 const char *str
, int nparam
)
1716 struct isl_map
*map
;
1717 struct isl_stream
*s
= isl_stream_new_str(ctx
, str
);
1720 map
= isl_stream_read_map(s
, nparam
);
1725 __isl_give isl_set
*isl_set_read_from_file(struct isl_ctx
*ctx
,
1726 FILE *input
, int nparam
)
1728 struct isl_map
*map
;
1729 map
= isl_map_read_from_file(ctx
, input
, nparam
);
1732 isl_assert(ctx
, isl_map_n_in(map
) == 0, goto error
);
1733 return (struct isl_set
*)map
;
1739 struct isl_set
*isl_set_read_from_str(struct isl_ctx
*ctx
,
1740 const char *str
, int nparam
)
1742 struct isl_map
*map
;
1743 map
= isl_map_read_from_str(ctx
, str
, nparam
);
1746 isl_assert(ctx
, isl_map_n_in(map
) == 0, goto error
);
1747 return (struct isl_set
*)map
;
1753 static char *next_line(FILE *input
, char *line
, unsigned len
)
1758 if (!(p
= fgets(line
, len
, input
)))
1760 while (isspace(*p
) && *p
!= '\n')
1762 } while (*p
== '#' || *p
== '\n');
1767 static struct isl_vec
*isl_vec_read_from_file_polylib(struct isl_ctx
*ctx
,
1770 struct isl_vec
*vec
= NULL
;
1779 isl_assert(ctx
, next_line(input
, line
, sizeof(line
)), return NULL
);
1780 isl_assert(ctx
, sscanf(line
, "%u", &size
) == 1, return NULL
);
1782 vec
= isl_vec_alloc(ctx
, size
);
1784 p
= next_line(input
, line
, sizeof(line
));
1785 isl_assert(ctx
, p
, goto error
);
1787 for (j
= 0; j
< size
; ++j
) {
1788 n
= sscanf(p
, "%s%n", val
, &offset
);
1789 isl_assert(ctx
, n
!= 0, goto error
);
1790 isl_int_read(vec
->el
[j
], val
);
1800 struct isl_vec
*isl_vec_read_from_file(struct isl_ctx
*ctx
,
1801 FILE *input
, unsigned input_format
)
1803 if (input_format
== ISL_FORMAT_POLYLIB
)
1804 return isl_vec_read_from_file_polylib(ctx
, input
);
1806 isl_assert(ctx
, 0, return NULL
);
1809 __isl_give isl_pw_qpolynomial
*isl_stream_read_pw_qpolynomial(
1810 struct isl_stream
*s
)
1813 struct isl_pw_qpolynomial
*pwqp
;
1815 obj
= obj_read(s
, -1);
1817 isl_assert(s
->ctx
, obj
.type
== isl_obj_pw_qpolynomial
,
1822 obj
.type
->free(obj
.v
);