2 * Copyright 2008-2009 Katholieke Universiteit Leuven
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
14 #include "isl_stream.h"
15 #include "isl_map_private.h"
16 #include "isl_input_omega.h"
21 struct variable
*next
;
30 static struct vars
*vars_new(struct isl_ctx
*ctx
)
33 v
= isl_alloc_type(ctx
, struct vars
);
42 static void variable_free(struct variable
*var
)
45 struct variable
*next
= var
->next
;
52 static void vars_free(struct vars
*v
)
60 static struct variable
*variable_new(struct vars
*v
, const char *name
, int len
,
64 var
= isl_alloc_type(v
->ctx
, struct variable
);
67 var
->name
= strdup(name
);
68 var
->name
[len
] = '\0';
77 static int vars_pos(struct vars
*v
, const char *s
, int len
)
84 for (q
= v
->v
; q
; q
= q
->next
) {
85 if (strncmp(q
->name
, s
, len
) == 0 && q
->name
[len
] == '\0')
92 v
->v
= variable_new(v
, s
, len
, v
->n
);
100 static struct vars
*read_var_list(struct isl_stream
*s
, struct vars
*v
)
102 struct isl_token
*tok
;
104 while ((tok
= isl_stream_next_token(s
)) != NULL
) {
108 if (tok
->type
!= ISL_TOKEN_IDENT
)
111 p
= vars_pos(v
, tok
->u
.s
, -1);
115 isl_stream_error(s
, tok
, "expecting unique identifier");
119 tok
= isl_stream_next_token(s
);
120 if (!tok
|| tok
->type
!= ',')
126 isl_stream_push_token(s
, tok
);
135 static struct vars
*read_tuple(struct isl_stream
*s
, struct vars
*v
)
137 struct isl_token
*tok
;
139 tok
= isl_stream_next_token(s
);
140 if (!tok
|| tok
->type
!= '[') {
141 isl_stream_error(s
, tok
, "expecting '['");
145 v
= read_var_list(s
, v
);
146 tok
= isl_stream_next_token(s
);
147 if (!tok
|| tok
->type
!= ']') {
148 isl_stream_error(s
, tok
, "expecting ']'");
161 static struct isl_basic_map
*add_constraints(struct isl_stream
*s
,
162 struct vars
**v
, struct isl_basic_map
*bmap
);
164 static struct isl_basic_map
*add_exists(struct isl_stream
*s
,
165 struct vars
**v
, struct isl_basic_map
*bmap
)
167 struct isl_token
*tok
;
174 tok
= isl_stream_next_token(s
);
177 if (tok
->type
== '(') {
181 isl_stream_push_token(s
, tok
);
182 *v
= read_var_list(s
, *v
);
186 bmap
= isl_basic_map_cow(bmap
);
187 bmap
= isl_basic_map_extend_dim(bmap
, isl_dim_copy(bmap
->dim
),
189 total
= isl_basic_map_total_dim(bmap
);
190 for (i
= 0; i
< extra
; ++i
) {
192 if ((k
= isl_basic_map_alloc_div(bmap
)) < 0)
194 isl_seq_clr(bmap
->div
[k
], 1+1+total
);
198 if (isl_stream_eat(s
, ':'))
200 bmap
= add_constraints(s
, v
, bmap
);
201 if (seen_paren
&& isl_stream_eat(s
, ')'))
205 isl_basic_map_free(bmap
);
209 static struct isl_basic_map
*add_constraint(struct isl_stream
*s
,
210 struct vars
**v
, struct isl_basic_map
*bmap
)
212 unsigned total
= isl_basic_map_total_dim(bmap
);
217 struct isl_token
*tok
= NULL
;
219 tok
= isl_stream_next_token(s
);
222 if (tok
->type
== ISL_TOKEN_EXISTS
) {
224 return add_exists(s
, v
, bmap
);
226 isl_stream_push_token(s
, tok
);
228 bmap
= isl_basic_map_cow(bmap
);
229 bmap
= isl_basic_map_extend_constraints(bmap
, 0, 1);
230 k
= isl_basic_map_alloc_inequality(bmap
);
233 isl_seq_clr(bmap
->ineq
[k
], 1+total
);
236 tok
= isl_stream_next_token(s
);
238 isl_stream_error(s
, NULL
, "unexpected EOF");
241 if (tok
->type
== ISL_TOKEN_IDENT
) {
243 int pos
= vars_pos(*v
, tok
->u
.s
, -1);
247 isl_stream_error(s
, tok
, "unknown identifier");
251 isl_int_add_ui(bmap
->ineq
[k
][1+pos
],
252 bmap
->ineq
[k
][1+pos
], 1);
254 isl_int_sub_ui(bmap
->ineq
[k
][1+pos
],
255 bmap
->ineq
[k
][1+pos
], 1);
256 } else if (tok
->type
== ISL_TOKEN_VALUE
) {
257 struct isl_token
*tok2
;
260 tok2
= isl_stream_next_token(s
);
261 if (tok2
&& tok2
->type
== ISL_TOKEN_IDENT
) {
262 pos
= vars_pos(*v
, tok2
->u
.s
, -1);
266 isl_stream_error(s
, tok2
,
267 "unknown identifier");
268 isl_token_free(tok2
);
271 isl_token_free(tok2
);
273 isl_stream_push_token(s
, tok2
);
275 isl_int_neg(tok
->u
.v
, tok
->u
.v
);
276 isl_int_add(bmap
->ineq
[k
][1+pos
],
277 bmap
->ineq
[k
][1+pos
], tok
->u
.v
);
278 } else if (tok
->type
== '+') {
280 } else if (tok
->type
== ISL_TOKEN_LE
) {
282 isl_seq_neg(bmap
->ineq
[k
], bmap
->ineq
[k
], 1+total
);
283 } else if (tok
->type
== ISL_TOKEN_GE
) {
286 } else if (tok
->type
== '=') {
288 isl_stream_error(s
, tok
, "too many operators");
295 isl_stream_push_token(s
, tok
);
302 isl_stream_error(s
, tok
, "missing operator");
306 isl_basic_map_inequality_to_equality(bmap
, k
);
311 isl_basic_map_free(bmap
);
315 static struct isl_basic_map
*add_constraints(struct isl_stream
*s
,
316 struct vars
**v
, struct isl_basic_map
*bmap
)
318 struct isl_token
*tok
;
321 bmap
= add_constraint(s
, v
, bmap
);
324 tok
= isl_stream_next_token(s
);
326 isl_stream_error(s
, NULL
, "unexpected EOF");
329 if (tok
->type
!= ISL_TOKEN_AND
)
333 isl_stream_push_token(s
, tok
);
339 isl_basic_map_free(bmap
);
343 static struct isl_basic_map
*basic_map_read(struct isl_stream
*s
)
345 struct isl_basic_map
*bmap
= NULL
;
346 struct isl_token
*tok
;
347 struct vars
*v
= NULL
;
351 tok
= isl_stream_next_token(s
);
352 if (!tok
|| tok
->type
!= '{') {
353 isl_stream_error(s
, tok
, "expecting '{'");
355 isl_stream_push_token(s
, tok
);
359 v
= vars_new(s
->ctx
);
360 v
= read_tuple(s
, v
);
364 tok
= isl_stream_next_token(s
);
365 if (tok
&& tok
->type
== ISL_TOKEN_TO
) {
367 v
= read_tuple(s
, v
);
373 isl_stream_push_token(s
, tok
);
377 bmap
= isl_basic_map_alloc(s
->ctx
, 0, n1
, n2
, 0, 0,0);
380 tok
= isl_stream_next_token(s
);
381 if (tok
&& tok
->type
== ':') {
383 bmap
= add_constraints(s
, &v
, bmap
);
384 tok
= isl_stream_next_token(s
);
386 if (tok
&& tok
->type
== '}') {
389 isl_stream_error(s
, tok
, "unexpected isl_token");
398 isl_basic_map_free(bmap
);
404 struct isl_basic_map
*isl_basic_map_read_from_file_omega(
405 struct isl_ctx
*ctx
, FILE *input
)
407 struct isl_basic_map
*bmap
;
408 struct isl_stream
*s
= isl_stream_new_file(ctx
, input
);
411 bmap
= basic_map_read(s
);
416 struct isl_basic_set
*isl_basic_set_read_from_file_omega(
417 struct isl_ctx
*ctx
, FILE *input
)
419 struct isl_basic_map
*bmap
;
420 bmap
= isl_basic_map_read_from_file_omega(ctx
, input
);
423 isl_assert(ctx
, isl_basic_map_n_in(bmap
) == 0, goto error
);
424 return (struct isl_basic_set
*)bmap
;
426 isl_basic_map_free(bmap
);
430 struct isl_basic_map
*isl_basic_map_read_from_str_omega(
431 struct isl_ctx
*ctx
, const char *str
)
433 struct isl_basic_map
*bmap
;
434 struct isl_stream
*s
= isl_stream_new_str(ctx
, str
);
437 bmap
= basic_map_read(s
);
442 struct isl_basic_set
*isl_basic_set_read_from_str_omega(
443 struct isl_ctx
*ctx
, const char *str
)
445 struct isl_basic_map
*bmap
;
446 bmap
= isl_basic_map_read_from_str_omega(ctx
, str
);
449 isl_assert(ctx
, isl_basic_map_n_in(bmap
) == 0, goto error
);
450 return (struct isl_basic_set
*)bmap
;
452 isl_basic_map_free(bmap
);