?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_set_upper_bound_si
[isl.git] / isl_input.c
blob320703a667dc9e6668174aaf70430ad996cfe67f
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 *
5 * Use of this software is governed by the GNU LGPLv2.1 license
6 *
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
11 */
12
13 #include <ctype.h>
14 #include <stdio.h>
15 #include <string.h>
16 #include <isl_ctx_private.h>
17 #include <isl_map_private.h>
18 #include <isl/set.h>
19 #include <isl/seq.h>
20 #include <isl_stream_private.h>
21 #include <isl/obj.h>
22 #include "isl_polynomial_private.h"
23 #include <isl/union_map.h>
24 #include <isl_mat_private.h>
25 #include <isl_aff_private.h>
26 #include <isl/list.h>
27
28 struct variable {
29 char *name;
30 int pos;
31 struct variable *next;
32 };
33
34 struct vars {
35 struct isl_ctx *ctx;
36 int n;
37 struct variable *v;
38 };
39
40 static struct vars *vars_new(struct isl_ctx *ctx)
41 {
42 struct vars *v;
43 v = isl_alloc_type(ctx, struct vars);
44 if (!v)
45 return NULL;
46 v->ctx = ctx;
47 v->n = 0;
48 v->v = NULL;
49 return v;
50 }
51
52 static void variable_free(struct variable *var)
53 {
54 while (var) {
55 struct variable *next = var->next;
56 free(var->name);
57 free(var);
58 var = next;
59 }
60 }
61
62 static void vars_free(struct vars *v)
63 {
64 if (!v)
65 return;
66 variable_free(v->v);
67 free(v);
68 }
69
70 static void vars_drop(struct vars *v, int n)
71 {
72 struct variable *var;
73
74 if (!v || !v->v)
75 return;
76
77 v->n -= n;
78
79 var = v->v;
80 while (--n >= 0) {
81 struct variable *next = var->next;
82 free(var->name);
83 free(var);
84 var = next;
85 }
86 v->v = var;
87 }
88
89 static struct variable *variable_new(struct vars *v, const char *name, int len,
90 int pos)
91 {
92 struct variable *var;
93 var = isl_calloc_type(v->ctx, struct variable);
94 if (!var)
95 goto error;
96 var->name = strdup(name);
97 var->name[len] = '\0';
98 var->pos = pos;
99 var->next = v->v;
100 return var;
101 error:
102 variable_free(v->v);
103 return NULL;
104 }
105
106 static int vars_pos(struct vars *v, const char *s, int len)
107 {
108 int pos;
109 struct variable *q;
110
111 if (len == -1)
112 len = strlen(s);
113 for (q = v->v; q; q = q->next) {
114 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
115 break;
116 }
117 if (q)
118 pos = q->pos;
119 else {
120 pos = v->n;
121 v->v = variable_new(v, s, len, v->n);
122 if (!v->v)
123 return -1;
124 v->n++;
125 }
126 return pos;
127 }
128
129 static int vars_add_anon(struct vars *v)
130 {
131 v->v = variable_new(v, "", 0, v->n);
132
133 if (!v->v)
134 return -1;
135 v->n++;
136
137 return 0;
138 }
139
140 static __isl_give isl_map *set_name(__isl_take isl_map *map,
141 enum isl_dim_type type, unsigned pos, char *name)
142 {
143 char *prime;
144
145 if (!map)
146 return NULL;
147 if (!name)
148 return map;
149
150 prime = strchr(name, '\'');
151 if (prime)
152 *prime = '\0';
153 map = isl_map_set_dim_name(map, type, pos, name);
154 if (prime)
155 *prime = '\'';
156
157 return map;
158 }
159
160 /* Obtain next token, with some preprocessing.
161 * In particular, evaluate expressions of the form x^y,
162 * with x and y values.
163 */
164 static struct isl_token *next_token(struct isl_stream *s)
165 {
166 struct isl_token *tok, *tok2;
167
168 tok = isl_stream_next_token(s);
169 if (!tok || tok->type != ISL_TOKEN_VALUE)
170 return tok;
171 if (!isl_stream_eat_if_available(s, '^'))
172 return tok;
173 tok2 = isl_stream_next_token(s);
174 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
175 isl_stream_error(s, tok2, "expecting constant value");
176 goto error;
177 }
178
179 isl_int_pow_ui(tok->u.v, tok->u.v, isl_int_get_ui(tok2->u.v));
180
181 isl_token_free(tok2);
182 return tok;
183 error:
184 isl_token_free(tok);
185 isl_token_free(tok2);
186 return NULL;
187 }
188
189 static int accept_cst_factor(struct isl_stream *s, isl_int *f)
190 {
191 struct isl_token *tok;
192
193 tok = next_token(s);
194 if (!tok || tok->type != ISL_TOKEN_VALUE) {
195 isl_stream_error(s, tok, "expecting constant value");
196 goto error;
197 }
198
199 isl_int_mul(*f, *f, tok->u.v);
200
201 isl_token_free(tok);
202
203 if (isl_stream_eat_if_available(s, '*'))
204 return accept_cst_factor(s, f);
205
206 return 0;
207 error:
208 isl_token_free(tok);
209 return -1;
210 }
211
212 /* Given an affine expression aff, return an affine expression
213 * for aff % d, with d the next token on the stream, which is
214 * assumed to be a constant.
215 *
216 * We introduce an integer division q = [aff/d] and the result
217 * is set to aff - d q.
218 */
219 static __isl_give isl_pw_aff *affine_mod(struct isl_stream *s,
220 struct vars *v, __isl_take isl_pw_aff *aff)
221 {
222 struct isl_token *tok;
223 isl_pw_aff *q;
224
225 tok = next_token(s);
226 if (!tok || tok->type != ISL_TOKEN_VALUE) {
227 isl_stream_error(s, tok, "expecting constant value");
228 goto error;
229 }
230
231 q = isl_pw_aff_copy(aff);
232 q = isl_pw_aff_scale_down(q, tok->u.v);
233 q = isl_pw_aff_floor(q);
234 q = isl_pw_aff_scale(q, tok->u.v);
235
236 aff = isl_pw_aff_sub(aff, q);
237
238 isl_token_free(tok);
239 return aff;
240 error:
241 isl_pw_aff_free(aff);
242 isl_token_free(tok);
243 return NULL;
244 }
245
246 static __isl_give isl_pw_aff *accept_affine(struct isl_stream *s,
247 __isl_take isl_space *dim, struct vars *v);
248 static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s,
249 __isl_take isl_space *dim, struct vars *v);
250
251 static __isl_give isl_pw_aff *accept_minmax(struct isl_stream *s,
252 __isl_take isl_space *dim, struct vars *v)
253 {
254 struct isl_token *tok;
255 isl_pw_aff_list *list = NULL;
256 int min;
257
258 tok = isl_stream_next_token(s);
259 if (!tok)
260 goto error;
261 min = tok->type == ISL_TOKEN_MIN;
262 isl_token_free(tok);
263
264 if (isl_stream_eat(s, '('))
265 goto error;
266
267 list = accept_affine_list(s, isl_space_copy(dim), v);
268 if (!list)
269 goto error;
270
271 if (isl_stream_eat(s, ')'))
272 goto error;
273
274 isl_space_free(dim);
275 return min ? isl_pw_aff_list_min(list) : isl_pw_aff_list_max(list);
276 error:
277 isl_space_free(dim);
278 isl_pw_aff_list_free(list);
279 return NULL;
280 }
281
282 static __isl_give isl_pw_aff *accept_div(struct isl_stream *s,
283 __isl_take isl_space *dim, struct vars *v)
284 {
285 struct isl_token *tok;
286 int seen_paren = 0;
287 int f = 0;
288 int c = 0;
289 isl_pw_aff *pwaff = NULL;
290
291 if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOORD))
292 f = 1;
293 else if (isl_stream_eat_if_available(s, ISL_TOKEN_CEILD))
294 c = 1;
295 if (f || c) {
296 if (isl_stream_eat(s, '('))
297 goto error;
298 } else {
299 if (isl_stream_eat(s, '['))
300 goto error;
301 if (isl_stream_eat_if_available(s, '('))
302 seen_paren = 1;
303 }
304
305 pwaff = accept_affine(s, isl_space_copy(dim), v);
306
307 if (f || c) {
308 if (isl_stream_eat(s, ','))
309 goto error;
310 } else {
311 if (seen_paren && isl_stream_eat(s, ')'))
312 goto error;
313 if (isl_stream_eat(s, '/'))
314 goto error;
315 }
316
317 tok = next_token(s);
318 if (!tok)
319 goto error;
320 if (tok->type != ISL_TOKEN_VALUE) {
321 isl_stream_error(s, tok, "expected denominator");
322 isl_stream_push_token(s, tok);
323 goto error;
324 }
325 isl_pw_aff_scale_down(pwaff, tok->u.v);
326 isl_token_free(tok);
327
328 if (c)
329 pwaff = isl_pw_aff_ceil(pwaff);
330 else
331 pwaff = isl_pw_aff_floor(pwaff);
332
333 if (f || c) {
334 if (isl_stream_eat(s, ')'))
335 goto error;
336 } else {
337 if (isl_stream_eat(s, ']'))
338 goto error;
339 }
340
341 isl_space_free(dim);
342 return pwaff;
343 error:
344 isl_space_free(dim);
345 isl_pw_aff_free(pwaff);
346 return NULL;
347 }
348
349 static __isl_give isl_pw_aff *accept_affine_factor(struct isl_stream *s,
350 __isl_take isl_space *dim, struct vars *v)
351 {
352 struct isl_token *tok = NULL;
353 isl_pw_aff *res = NULL;
354
355 tok = next_token(s);
356 if (!tok) {
357 isl_stream_error(s, NULL, "unexpected EOF");
358 goto error;
359 }
360
361 if (tok->type == ISL_TOKEN_AFF) {
362 res = isl_pw_aff_copy(tok->u.pwaff);
363 isl_token_free(tok);
364 } else if (tok->type == ISL_TOKEN_IDENT) {
365 int n = v->n;
366 int pos = vars_pos(v, tok->u.s, -1);
367 isl_aff *aff;
368
369 if (pos < 0)
370 goto error;
371 if (pos >= n) {
372 isl_stream_error(s, tok, "unknown identifier");
373 goto error;
374 }
375
376 aff = isl_aff_zero_on_domain(isl_local_space_from_space(isl_space_copy(dim)));
377 if (!aff)
378 goto error;
379 isl_int_set_si(aff->v->el[2 + pos], 1);
380 res = isl_pw_aff_from_aff(aff);
381 isl_token_free(tok);
382 } else if (tok->type == ISL_TOKEN_VALUE) {
383 if (isl_stream_eat_if_available(s, '*')) {
384 res = accept_affine_factor(s, isl_space_copy(dim), v);
385 res = isl_pw_aff_scale(res, tok->u.v);
386 } else {
387 isl_local_space *ls;
388 isl_aff *aff;
389 ls = isl_local_space_from_space(isl_space_copy(dim));
390 aff = isl_aff_zero_on_domain(ls);
391 aff = isl_aff_add_constant(aff, tok->u.v);
392 res = isl_pw_aff_from_aff(aff);
393 }
394 isl_token_free(tok);
395 } else if (tok->type == '(') {
396 isl_token_free(tok);
397 tok = NULL;
398 res = accept_affine(s, isl_space_copy(dim), v);
399 if (!res)
400 goto error;
401 if (isl_stream_eat(s, ')'))
402 goto error;
403 } else if (tok->type == '[' ||
404 tok->type == ISL_TOKEN_FLOORD ||
405 tok->type == ISL_TOKEN_CEILD) {
406 isl_stream_push_token(s, tok);
407 tok = NULL;
408 res = accept_div(s, isl_space_copy(dim), v);
409 } else if (tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX) {
410 isl_stream_push_token(s, tok);
411 tok = NULL;
412 res = accept_minmax(s, isl_space_copy(dim), v);
413 } else {
414 isl_stream_error(s, tok, "expecting factor");
415 goto error;
416 }
417 if (isl_stream_eat_if_available(s, '%') ||
418 isl_stream_eat_if_available(s, ISL_TOKEN_MOD)) {
419 isl_space_free(dim);
420 return affine_mod(s, v, res);
421 }
422 if (isl_stream_eat_if_available(s, '*')) {
423 isl_int f;
424 isl_int_init(f);
425 isl_int_set_si(f, 1);
426 if (accept_cst_factor(s, &f) < 0) {
427 isl_int_clear(f);
428 goto error2;
429 }
430 res = isl_pw_aff_scale(res, f);
431 isl_int_clear(f);
432 }
433
434 isl_space_free(dim);
435 return res;
436 error:
437 isl_token_free(tok);
438 error2:
439 isl_pw_aff_free(res);
440 isl_space_free(dim);
441 return NULL;
442 }
443
444 static __isl_give isl_pw_aff *add_cst(__isl_take isl_pw_aff *pwaff, isl_int v)
445 {
446 isl_aff *aff;
447 isl_space *space;
448
449 space = isl_pw_aff_get_domain_space(pwaff);
450 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
451 aff = isl_aff_add_constant(aff, v);
452
453 return isl_pw_aff_add(pwaff, isl_pw_aff_from_aff(aff));
454 }
455
456 static __isl_give isl_pw_aff *accept_affine(struct isl_stream *s,
457 __isl_take isl_space *dim, struct vars *v)
458 {
459 struct isl_token *tok = NULL;
460 isl_local_space *ls;
461 isl_pw_aff *res;
462 int sign = 1;
463
464 ls = isl_local_space_from_space(isl_space_copy(dim));
465 res = isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls));
466 if (!res)
467 goto error;
468
469 for (;;) {
470 tok = next_token(s);
471 if (!tok) {
472 isl_stream_error(s, NULL, "unexpected EOF");
473 goto error;
474 }
475 if (tok->type == '-') {
476 sign = -sign;
477 isl_token_free(tok);
478 continue;
479 }
480 if (tok->type == '(' || tok->type == '[' ||
481 tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX ||
482 tok->type == ISL_TOKEN_FLOORD ||
483 tok->type == ISL_TOKEN_CEILD ||
484 tok->type == ISL_TOKEN_IDENT ||
485 tok->type == ISL_TOKEN_AFF) {
486 isl_pw_aff *term;
487 isl_stream_push_token(s, tok);
488 tok = NULL;
489 term = accept_affine_factor(s, isl_space_copy(dim), v);
490 if (sign < 0)
491 res = isl_pw_aff_sub(res, term);
492 else
493 res = isl_pw_aff_add(res, term);
494 if (!res)
495 goto error;
496 sign = 1;
497 } else if (tok->type == ISL_TOKEN_VALUE) {
498 if (sign < 0)
499 isl_int_neg(tok->u.v, tok->u.v);
500 if (isl_stream_eat_if_available(s, '*') ||
501 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
502 isl_pw_aff *term;
503 term = accept_affine_factor(s,
504 isl_space_copy(dim), v);
505 term = isl_pw_aff_scale(term, tok->u.v);
506 res = isl_pw_aff_add(res, term);
507 if (!res)
508 goto error;
509 } else {
510 res = add_cst(res, tok->u.v);
511 }
512 sign = 1;
513 } else {
514 isl_stream_error(s, tok, "unexpected isl_token");
515 isl_stream_push_token(s, tok);
516 isl_pw_aff_free(res);
517 isl_space_free(dim);
518 return NULL;
519 }
520 isl_token_free(tok);
521
522 tok = next_token(s);
523 if (tok && tok->type == '-') {
524 sign = -sign;
525 isl_token_free(tok);
526 } else if (tok && tok->type == '+') {
527 /* nothing */
528 isl_token_free(tok);
529 } else if (tok && tok->type == ISL_TOKEN_VALUE &&
530 isl_int_is_neg(tok->u.v)) {
531 isl_stream_push_token(s, tok);
532 } else {
533 if (tok)
534 isl_stream_push_token(s, tok);
535 break;
536 }
537 }
538
539 isl_space_free(dim);
540 return res;
541 error:
542 isl_space_free(dim);
543 isl_token_free(tok);
544 isl_pw_aff_free(res);
545 return NULL;
546 }
547
548 static int is_comparator(struct isl_token *tok)
549 {
550 if (!tok)
551 return 0;
552
553 switch (tok->type) {
554 case ISL_TOKEN_LT:
555 case ISL_TOKEN_GT:
556 case ISL_TOKEN_LE:
557 case ISL_TOKEN_GE:
558 case ISL_TOKEN_NE:
559 case '=':
560 return 1;
561 default:
562 return 0;
563 }
564 }
565
566 static struct isl_map *read_disjuncts(struct isl_stream *s,
567 struct vars *v, __isl_take isl_map *map);
568 static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s,
569 __isl_take isl_space *dim, struct vars *v);
570
571 /* Accept a ternary operator, given the first argument.
572 */
573 static __isl_give isl_pw_aff *accept_ternary(struct isl_stream *s,
574 __isl_take isl_map *cond, struct vars *v)
575 {
576 isl_space *dim;
577 isl_pw_aff *pwaff1 = NULL, *pwaff2 = NULL;
578
579 if (!cond)
580 return NULL;
581
582 if (isl_stream_eat(s, '?'))
583 goto error;
584
585 dim = isl_space_wrap(isl_map_get_space(cond));
586 pwaff1 = accept_extended_affine(s, dim, v);
587 if (!pwaff1)
588 goto error;
589
590 if (isl_stream_eat(s, ':'))
591 goto error;
592
593 dim = isl_pw_aff_get_domain_space(pwaff1);
594 pwaff2 = accept_extended_affine(s, dim, v);
595 if (!pwaff1)
596 goto error;
597
598 return isl_pw_aff_cond(isl_map_wrap(cond), pwaff1, pwaff2);
599 error:
600 isl_map_free(cond);
601 isl_pw_aff_free(pwaff1);
602 isl_pw_aff_free(pwaff2);
603 return NULL;
604 }
605
606 /* Accept an affine expression that may involve ternary operators.
607 * We first read an affine expression.
608 * If it is not followed by a comparison operator, we simply return it.
609 * Otherwise, we assume the affine epxression is part of the first
610 * argument of a ternary operator and try to parse that.
611 */
612 static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s,
613 __isl_take isl_space *dim, struct vars *v)
614 {
615 isl_space *space;
616 isl_map *cond;
617 isl_pw_aff *pwaff;
618 struct isl_token *tok;
619 int line = -1, col = -1;
620 int is_comp;
621
622 tok = isl_stream_next_token(s);
623 if (tok) {
624 line = tok->line;
625 col = tok->col;
626 isl_stream_push_token(s, tok);
627 }
628
629 pwaff = accept_affine(s, dim, v);
630 if (!pwaff)
631 return NULL;
632
633 tok = isl_stream_next_token(s);
634 if (!tok)
635 return isl_pw_aff_free(pwaff);
636
637 is_comp = is_comparator(tok);
638 isl_stream_push_token(s, tok);
639 if (!is_comp)
640 return pwaff;
641
642 tok = isl_token_new(s->ctx, line, col, 0);
643 if (!tok)
644 return isl_pw_aff_free(pwaff);
645 tok->type = ISL_TOKEN_AFF;
646 tok->u.pwaff = pwaff;
647
648 space = isl_pw_aff_get_domain_space(pwaff);
649 cond = isl_map_universe(isl_space_unwrap(space));
650
651 isl_stream_push_token(s, tok);
652
653 cond = read_disjuncts(s, v, cond);
654
655 return accept_ternary(s, cond, v);
656 }
657
658 static __isl_give isl_map *read_var_def(struct isl_stream *s,
659 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v)
660 {
661 isl_pw_aff *def;
662 int pos;
663 isl_map *def_map;
664
665 if (type == isl_dim_param)
666 pos = isl_map_dim(map, isl_dim_param);
667 else {
668 pos = isl_map_dim(map, isl_dim_in);
669 if (type == isl_dim_out)
670 pos += isl_map_dim(map, isl_dim_out);
671 type = isl_dim_in;
672 }
673 --pos;
674
675 def = accept_extended_affine(s, isl_space_wrap(isl_map_get_space(map)), v);
676 def_map = isl_map_from_pw_aff(def);
677 def_map = isl_map_equate(def_map, type, pos, isl_dim_out, 0);
678 def_map = isl_set_unwrap(isl_map_domain(def_map));
679
680 map = isl_map_intersect(map, def_map);
681
682 return map;
683 }
684
685 static __isl_give isl_map *read_var_list(struct isl_stream *s,
686 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v)
687 {
688 int i = 0;
689 struct isl_token *tok;
690
691 if (isl_stream_next_token_is(s, ']'))
692 return isl_map_add_dims(map, type, 0);
693
694 while ((tok = next_token(s)) != NULL) {
695 int new_name = 0;
696
697 if (tok->type == ISL_TOKEN_IDENT) {
698 int n = v->n;
699 int p = vars_pos(v, tok->u.s, -1);
700 if (p < 0)
701 goto error;
702 new_name = p >= n;
703 }
704
705 if (new_name) {
706 map = isl_map_add_dims(map, type, 1);
707 map = set_name(map, type, i, v->v->name);
708 isl_token_free(tok);
709 if (isl_stream_eat_if_available(s, '='))
710 map = read_var_def(s, map, type, v);
711 } else {
712 if (type == isl_dim_param) {
713 isl_stream_error(s, tok,
714 "expecting unique identifier");
715 goto error;
716 }
717 isl_stream_push_token(s, tok);
718 tok = NULL;
719 if (vars_add_anon(v) < 0)
720 goto error;
721 map = isl_map_add_dims(map, type, 1);
722 map = read_var_def(s, map, type, v);
723 }
724
725 tok = isl_stream_next_token(s);
726 if (tok && tok->type == ']' &&
727 isl_stream_next_token_is(s, '[')) {
728 isl_token_free(tok);
729 tok = isl_stream_next_token(s);
730 } else if (!tok || tok->type != ',')
731 break;
732
733 isl_token_free(tok);
734 i++;
735 }
736 if (tok)
737 isl_stream_push_token(s, tok);
738
739 return map;
740 error:
741 isl_token_free(tok);
742 isl_map_free(map);
743 return NULL;
744 }
745
746 static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s,
747 __isl_take isl_space *dim, struct vars *v)
748 {
749 isl_pw_aff *pwaff;
750 isl_pw_aff_list *list;
751 struct isl_token *tok = NULL;
752
753 pwaff = accept_affine(s, isl_space_copy(dim), v);
754 list = isl_pw_aff_list_from_pw_aff(pwaff);
755 if (!list)
756 goto error;
757
758 for (;;) {
759 tok = isl_stream_next_token(s);
760 if (!tok) {
761 isl_stream_error(s, NULL, "unexpected EOF");
762 goto error;
763 }
764 if (tok->type != ',') {
765 isl_stream_push_token(s, tok);
766 break;
767 }
768 isl_token_free(tok);
769
770 pwaff = accept_affine(s, isl_space_copy(dim), v);
771 list = isl_pw_aff_list_concat(list,
772 isl_pw_aff_list_from_pw_aff(pwaff));
773 if (!list)
774 return NULL;
775 }
776
777 isl_space_free(dim);
778 return list;
779 error:
780 isl_space_free(dim);
781 isl_pw_aff_list_free(list);
782 return NULL;
783 }
784
785 static __isl_give isl_map *read_defined_var_list(struct isl_stream *s,
786 struct vars *v, __isl_take isl_map *map)
787 {
788 struct isl_token *tok;
789
790 while ((tok = isl_stream_next_token(s)) != NULL) {
791 int p;
792 int n = v->n;
793
794 if (tok->type != ISL_TOKEN_IDENT)
795 break;
796
797 p = vars_pos(v, tok->u.s, -1);
798 if (p < 0)
799 goto error;
800 if (p < n) {
801 isl_stream_error(s, tok, "expecting unique identifier");
802 goto error;
803 }
804
805 map = isl_map_add_dims(map, isl_dim_out, 1);
806
807 isl_token_free(tok);
808 tok = isl_stream_next_token(s);
809 if (tok && tok->type == '=') {
810 isl_token_free(tok);
811 map = read_var_def(s, map, isl_dim_out, v);
812 tok = isl_stream_next_token(s);
813 }
814
815 if (!tok || tok->type != ',')
816 break;
817
818 isl_token_free(tok);
819 }
820 if (tok)
821 isl_stream_push_token(s, tok);
822
823 return map;
824 error:
825 isl_token_free(tok);
826 isl_map_free(map);
827 return NULL;
828 }
829
830 static int next_is_tuple(struct isl_stream *s)
831 {
832 struct isl_token *tok;
833 int is_tuple;
834
835 tok = isl_stream_next_token(s);
836 if (!tok)
837 return 0;
838 if (tok->type == '[') {
839 isl_stream_push_token(s, tok);
840 return 1;
841 }
842 if (tok->type != ISL_TOKEN_IDENT && !tok->is_keyword) {
843 isl_stream_push_token(s, tok);
844 return 0;
845 }
846
847 is_tuple = isl_stream_next_token_is(s, '[');
848
849 isl_stream_push_token(s, tok);
850
851 return is_tuple;
852 }
853
854 static __isl_give isl_map *read_tuple(struct isl_stream *s,
855 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v);
856
857 static __isl_give isl_set *read_nested_tuple(struct isl_stream *s,
858 __isl_take isl_map *map, struct vars *v)
859 {
860 map = read_tuple(s, map, isl_dim_in, v);
861 if (isl_stream_eat(s, ISL_TOKEN_TO))
862 goto error;
863 map = read_tuple(s, map, isl_dim_out, v);
864 return isl_map_wrap(map);
865 error:
866 isl_map_free(map);
867 return NULL;
868 }
869
870 static __isl_give isl_map *read_tuple(struct isl_stream *s,
871 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v)
872 {
873 struct isl_token *tok;
874 char *name = NULL;
875
876 tok = isl_stream_next_token(s);
877 if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
878 name = strdup(tok->u.s);
879 if (!name)
880 goto error;
881 isl_token_free(tok);
882 tok = isl_stream_next_token(s);
883 }
884 if (!tok || tok->type != '[') {
885 isl_stream_error(s, tok, "expecting '['");
886 goto error;
887 }
888 isl_token_free(tok);
889 if (type != isl_dim_param && next_is_tuple(s)) {
890 isl_space *dim = isl_map_get_space(map);
891 int nparam = isl_space_dim(dim, isl_dim_param);
892 int n_in = isl_space_dim(dim, isl_dim_in);
893 isl_set *nested;
894 if (type == isl_dim_out) {
895 dim = isl_space_move_dims(dim, isl_dim_param, nparam,
896 isl_dim_in, 0, n_in);
897 dim = isl_space_params(dim);
898 }
899 nested = read_nested_tuple(s, isl_map_universe(dim), v);
900 if (type == isl_dim_in) {
901 nested = isl_map_reverse(nested);
902 map = isl_map_intersect_params(nested, map);
903 } else {
904 isl_set *set;
905 dim = isl_set_get_space(nested);
906 dim = isl_space_drop_dims(dim, isl_dim_param, nparam, n_in);
907 dim = isl_space_join(isl_map_get_space(map), dim);
908 set = isl_map_domain(map);
909 nested = isl_map_reset_space(nested, dim);
910 map = isl_map_intersect_domain(nested, set);
911 }
912 } else
913 map = read_var_list(s, map, type, v);
914 tok = isl_stream_next_token(s);
915 if (!tok || tok->type != ']') {
916 isl_stream_error(s, tok, "expecting ']'");
917 goto error;
918 }
919 isl_token_free(tok);
920
921 if (name) {
922 map = isl_map_set_tuple_name(map, type, name);
923 free(name);
924 }
925
926 return map;
927 error:
928 if (tok)
929 isl_token_free(tok);
930 isl_map_free(map);
931 return NULL;
932 }
933
934 static __isl_give isl_set *construct_constraints(
935 __isl_take isl_set *set, enum isl_token_type type,
936 __isl_keep isl_pw_aff_list *left, __isl_keep isl_pw_aff_list *right)
937 {
938 isl_set *cond;
939
940 if (type == ISL_TOKEN_LE)
941 cond = isl_pw_aff_list_le_set(isl_pw_aff_list_copy(left),
942 isl_pw_aff_list_copy(right));
943 else if (type == ISL_TOKEN_GE)
944 cond = isl_pw_aff_list_ge_set(isl_pw_aff_list_copy(left),
945 isl_pw_aff_list_copy(right));
946 else if (type == ISL_TOKEN_LT)
947 cond = isl_pw_aff_list_lt_set(isl_pw_aff_list_copy(left),
948 isl_pw_aff_list_copy(right));
949 else if (type == ISL_TOKEN_GT)
950 cond = isl_pw_aff_list_gt_set(isl_pw_aff_list_copy(left),
951 isl_pw_aff_list_copy(right));
952 else if (type == ISL_TOKEN_NE)
953 cond = isl_pw_aff_list_ne_set(isl_pw_aff_list_copy(left),
954 isl_pw_aff_list_copy(right));
955 else
956 cond = isl_pw_aff_list_eq_set(isl_pw_aff_list_copy(left),
957 isl_pw_aff_list_copy(right));
958
959 return isl_set_intersect(set, cond);
960 }
961
962 static __isl_give isl_map *add_constraint(struct isl_stream *s,
963 struct vars *v, __isl_take isl_map *map)
964 {
965 struct isl_token *tok = NULL;
966 isl_pw_aff_list *list1 = NULL, *list2 = NULL;
967 isl_set *set;
968
969 set = isl_map_wrap(map);
970 list1 = accept_affine_list(s, isl_set_get_space(set), v);
971 if (!list1)
972 goto error;
973 tok = isl_stream_next_token(s);
974 if (!is_comparator(tok)) {
975 isl_stream_error(s, tok, "missing operator");
976 if (tok)
977 isl_stream_push_token(s, tok);
978 tok = NULL;
979 goto error;
980 }
981 for (;;) {
982 list2 = accept_affine_list(s, isl_set_get_space(set), v);
983 if (!list2)
984 goto error;
985
986 set = construct_constraints(set, tok->type, list1, list2);
987 isl_token_free(tok);
988 isl_pw_aff_list_free(list1);
989 list1 = list2;
990
991 tok = isl_stream_next_token(s);
992 if (!is_comparator(tok)) {
993 if (tok)
994 isl_stream_push_token(s, tok);
995 break;
996 }
997 }
998 isl_pw_aff_list_free(list1);
999
1000 return isl_set_unwrap(set);
1001 error:
1002 if (tok)
1003 isl_token_free(tok);
1004 isl_pw_aff_list_free(list1);
1005 isl_pw_aff_list_free(list2);
1006 isl_set_free(set);
1007 return NULL;
1008 }
1009
1010 static __isl_give isl_map *read_exists(struct isl_stream *s,
1011 struct vars *v, __isl_take isl_map *map)
1012 {
1013 int n = v->n;
1014 int seen_paren = isl_stream_eat_if_available(s, '(');
1015
1016 map = isl_map_from_domain(isl_map_wrap(map));
1017 map = read_defined_var_list(s, v, map);
1018
1019 if (isl_stream_eat(s, ':'))
1020 goto error;
1021
1022 map = read_disjuncts(s, v, map);
1023 map = isl_set_unwrap(isl_map_domain(map));
1024
1025 vars_drop(v, v->n - n);
1026 if (seen_paren && isl_stream_eat(s, ')'))
1027 goto error;
1028
1029 return map;
1030 error:
1031 isl_map_free(map);
1032 return NULL;
1033 }
1034
1035 /* Parse an expression between parentheses and push the result
1036 * back on the stream.
1037 *
1038 * The parsed expression may be either an affine expression
1039 * or a condition. The first type is pushed onto the stream
1040 * as an isl_pw_aff, while the second is pushed as an isl_map.
1041 *
1042 * If the initial token indicates the start of a condition,
1043 * we parse it as such.
1044 * Otherwise, we first parse an affine expression and push
1045 * that onto the stream. If the affine expression covers the
1046 * entire expression between parentheses, we return.
1047 * Otherwise, we assume that the affine expression is the
1048 * start of a condition and continue parsing.
1049 */
1050 static int resolve_paren_expr(struct isl_stream *s,
1051 struct vars *v, __isl_take isl_map *map)
1052 {
1053 struct isl_token *tok, *tok2;
1054 int line, col;
1055 isl_pw_aff *pwaff;
1056
1057 tok = isl_stream_next_token(s);
1058 if (!tok || tok->type != '(')
1059 goto error;
1060
1061 if (isl_stream_next_token_is(s, '('))
1062 if (resolve_paren_expr(s, v, isl_map_copy(map)))
1063 goto error;
1064
1065 if (isl_stream_next_token_is(s, ISL_TOKEN_EXISTS) ||
1066 isl_stream_next_token_is(s, ISL_TOKEN_TRUE) ||
1067 isl_stream_next_token_is(s, ISL_TOKEN_FALSE) ||
1068 isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1069 map = read_disjuncts(s, v, map);
1070 if (isl_stream_eat(s, ')'))
1071 goto error;
1072 tok->type = ISL_TOKEN_MAP;
1073 tok->u.map = map;
1074 isl_stream_push_token(s, tok);
1075 return 0;
1076 }
1077
1078 tok2 = isl_stream_next_token(s);
1079 if (!tok2)
1080 goto error;
1081 line = tok2->line;
1082 col = tok2->col;
1083 isl_stream_push_token(s, tok2);
1084
1085 pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v);
1086 if (!pwaff)
1087 goto error;
1088
1089 tok2 = isl_token_new(s->ctx, line, col, 0);
1090 if (!tok2)
1091 goto error2;
1092 tok2->type = ISL_TOKEN_AFF;
1093 tok2->u.pwaff = pwaff;
1094
1095 if (isl_stream_eat_if_available(s, ')')) {
1096 isl_stream_push_token(s, tok2);
1097 isl_token_free(tok);
1098 isl_map_free(map);
1099 return 0;
1100 }
1101
1102 isl_stream_push_token(s, tok2);
1103
1104 map = read_disjuncts(s, v, map);
1105 if (isl_stream_eat(s, ')'))
1106 goto error;
1107
1108 tok->type = ISL_TOKEN_MAP;
1109 tok->u.map = map;
1110 isl_stream_push_token(s, tok);
1111
1112 return 0;
1113 error2:
1114 isl_pw_aff_free(pwaff);
1115 error:
1116 isl_token_free(tok);
1117 isl_map_free(map);
1118 return -1;
1119 }
1120
1121 static __isl_give isl_map *read_conjunct(struct isl_stream *s,
1122 struct vars *v, __isl_take isl_map *map)
1123 {
1124 if (isl_stream_next_token_is(s, '('))
1125 if (resolve_paren_expr(s, v, isl_map_copy(map)))
1126 goto error;
1127
1128 if (isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1129 struct isl_token *tok;
1130 tok = isl_stream_next_token(s);
1131 if (!tok)
1132 goto error;
1133 isl_map_free(map);
1134 map = isl_map_copy(tok->u.map);
1135 isl_token_free(tok);
1136 return map;
1137 }
1138
1139 if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))
1140 return read_exists(s, v, map);
1141
1142 if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))
1143 return map;
1144
1145 if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) {
1146 isl_space *dim = isl_map_get_space(map);
1147 isl_map_free(map);
1148 return isl_map_empty(dim);
1149 }
1150
1151 return add_constraint(s, v, map);
1152 error:
1153 isl_map_free(map);
1154 return NULL;
1155 }
1156
1157 static __isl_give isl_map *read_conjuncts(struct isl_stream *s,
1158 struct vars *v, __isl_take isl_map *map)
1159 {
1160 isl_map *res;
1161 int negate;
1162
1163 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1164 res = read_conjunct(s, v, isl_map_copy(map));
1165 if (negate)
1166 res = isl_map_subtract(isl_map_copy(map), res);
1167
1168 while (isl_stream_eat_if_available(s, ISL_TOKEN_AND)) {
1169 isl_map *res_i;
1170
1171 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1172 res_i = read_conjunct(s, v, isl_map_copy(map));
1173 if (negate)
1174 res = isl_map_subtract(res, res_i);
1175 else
1176 res = isl_map_intersect(res, res_i);
1177 }
1178
1179 isl_map_free(map);
1180 return res;
1181 }
1182
1183 static struct isl_map *read_disjuncts(struct isl_stream *s,
1184 struct vars *v, __isl_take isl_map *map)
1185 {
1186 isl_map *res;
1187
1188 if (isl_stream_next_token_is(s, '}')) {
1189 isl_space *dim = isl_map_get_space(map);
1190 isl_map_free(map);
1191 return isl_map_universe(dim);
1192 }
1193
1194 res = read_conjuncts(s, v, isl_map_copy(map));
1195 while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
1196 isl_map *res_i;
1197
1198 res_i = read_conjuncts(s, v, isl_map_copy(map));
1199 res = isl_map_union(res, res_i);
1200 }
1201
1202 isl_map_free(map);
1203 return res;
1204 }
1205
1206 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1207 {
1208 if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1209 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1210 isl_basic_map_dim(bmap, isl_dim_in) + pos;
1211 pos -= isl_basic_map_dim(bmap, isl_dim_out);
1212
1213 if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1214 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1215 pos -= isl_basic_map_dim(bmap, isl_dim_in);
1216
1217 if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1218 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1219 isl_basic_map_dim(bmap, isl_dim_in) +
1220 isl_basic_map_dim(bmap, isl_dim_out) + pos;
1221 pos -= isl_basic_map_dim(bmap, isl_dim_div);
1222
1223 if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1224 return 1 + pos;
1225
1226 return 0;
1227 }
1228
1229 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1230 struct isl_stream *s, __isl_take isl_basic_map *bmap)
1231 {
1232 int j;
1233 struct isl_token *tok;
1234 int type;
1235 int k;
1236 isl_int *c;
1237 unsigned nparam;
1238 unsigned dim;
1239
1240 if (!bmap)
1241 return NULL;
1242
1243 nparam = isl_basic_map_dim(bmap, isl_dim_param);
1244 dim = isl_basic_map_dim(bmap, isl_dim_out);
1245
1246 tok = isl_stream_next_token(s);
1247 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1248 isl_stream_error(s, tok, "expecting coefficient");
1249 if (tok)
1250 isl_stream_push_token(s, tok);
1251 goto error;
1252 }
1253 if (!tok->on_new_line) {
1254 isl_stream_error(s, tok, "coefficient should appear on new line");
1255 isl_stream_push_token(s, tok);
1256 goto error;
1257 }
1258
1259 type = isl_int_get_si(tok->u.v);
1260 isl_token_free(tok);
1261
1262 isl_assert(s->ctx, type == 0 || type == 1, goto error);
1263 if (type == 0) {
1264 k = isl_basic_map_alloc_equality(bmap);
1265 c = bmap->eq[k];
1266 } else {
1267 k = isl_basic_map_alloc_inequality(bmap);
1268 c = bmap->ineq[k];
1269 }
1270 if (k < 0)
1271 goto error;
1272
1273 for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1274 int pos;
1275 tok = isl_stream_next_token(s);
1276 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1277 isl_stream_error(s, tok, "expecting coefficient");
1278 if (tok)
1279 isl_stream_push_token(s, tok);
1280 goto error;
1281 }
1282 if (tok->on_new_line) {
1283 isl_stream_error(s, tok,
1284 "coefficient should not appear on new line");
1285 isl_stream_push_token(s, tok);
1286 goto error;
1287 }
1288 pos = polylib_pos_to_isl_pos(bmap, j);
1289 isl_int_set(c[pos], tok->u.v);
1290 isl_token_free(tok);
1291 }
1292
1293 return bmap;
1294 error:
1295 isl_basic_map_free(bmap);
1296 return NULL;
1297 }
1298
1299 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s)
1300 {
1301 int i;
1302 struct isl_token *tok;
1303 struct isl_token *tok2;
1304 int n_row, n_col;
1305 int on_new_line;
1306 unsigned in = 0, out, local = 0;
1307 struct isl_basic_map *bmap = NULL;
1308 int nparam = 0;
1309
1310 tok = isl_stream_next_token(s);
1311 if (!tok) {
1312 isl_stream_error(s, NULL, "unexpected EOF");
1313 return NULL;
1314 }
1315 tok2 = isl_stream_next_token(s);
1316 if (!tok2) {
1317 isl_token_free(tok);
1318 isl_stream_error(s, NULL, "unexpected EOF");
1319 return NULL;
1320 }
1321 if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1322 isl_stream_push_token(s, tok2);
1323 isl_stream_push_token(s, tok);
1324 isl_stream_error(s, NULL,
1325 "expecting constraint matrix dimensions");
1326 return NULL;
1327 }
1328 n_row = isl_int_get_si(tok->u.v);
1329 n_col = isl_int_get_si(tok2->u.v);
1330 on_new_line = tok2->on_new_line;
1331 isl_token_free(tok2);
1332 isl_token_free(tok);
1333 isl_assert(s->ctx, !on_new_line, return NULL);
1334 isl_assert(s->ctx, n_row >= 0, return NULL);
1335 isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1336 tok = isl_stream_next_token_on_same_line(s);
1337 if (tok) {
1338 if (tok->type != ISL_TOKEN_VALUE) {
1339 isl_stream_error(s, tok,
1340 "expecting number of output dimensions");
1341 isl_stream_push_token(s, tok);
1342 goto error;
1343 }
1344 out = isl_int_get_si(tok->u.v);
1345 isl_token_free(tok);
1346
1347 tok = isl_stream_next_token_on_same_line(s);
1348 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1349 isl_stream_error(s, tok,
1350 "expecting number of input dimensions");
1351 if (tok)
1352 isl_stream_push_token(s, tok);
1353 goto error;
1354 }
1355 in = isl_int_get_si(tok->u.v);
1356 isl_token_free(tok);
1357
1358 tok = isl_stream_next_token_on_same_line(s);
1359 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1360 isl_stream_error(s, tok,
1361 "expecting number of existentials");
1362 if (tok)
1363 isl_stream_push_token(s, tok);
1364 goto error;
1365 }
1366 local = isl_int_get_si(tok->u.v);
1367 isl_token_free(tok);
1368
1369 tok = isl_stream_next_token_on_same_line(s);
1370 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1371 isl_stream_error(s, tok,
1372 "expecting number of parameters");
1373 if (tok)
1374 isl_stream_push_token(s, tok);
1375 goto error;
1376 }
1377 nparam = isl_int_get_si(tok->u.v);
1378 isl_token_free(tok);
1379 if (n_col != 1 + out + in + local + nparam + 1) {
1380 isl_stream_error(s, NULL,
1381 "dimensions don't match");
1382 goto error;
1383 }
1384 } else
1385 out = n_col - 2 - nparam;
1386 bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1387 if (!bmap)
1388 return NULL;
1389
1390 for (i = 0; i < local; ++i) {
1391 int k = isl_basic_map_alloc_div(bmap);
1392 if (k < 0)
1393 goto error;
1394 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1395 }
1396
1397 for (i = 0; i < n_row; ++i)
1398 bmap = basic_map_read_polylib_constraint(s, bmap);
1399
1400 tok = isl_stream_next_token_on_same_line(s);
1401 if (tok) {
1402 isl_stream_error(s, tok, "unexpected extra token on line");
1403 isl_stream_push_token(s, tok);
1404 goto error;
1405 }
1406
1407 bmap = isl_basic_map_simplify(bmap);
1408 bmap = isl_basic_map_finalize(bmap);
1409 return bmap;
1410 error:
1411 isl_basic_map_free(bmap);
1412 return NULL;
1413 }
1414
1415 static struct isl_map *map_read_polylib(struct isl_stream *s)
1416 {
1417 struct isl_token *tok;
1418 struct isl_token *tok2;
1419 int i, n;
1420 struct isl_map *map;
1421
1422 tok = isl_stream_next_token(s);
1423 if (!tok) {
1424 isl_stream_error(s, NULL, "unexpected EOF");
1425 return NULL;
1426 }
1427 tok2 = isl_stream_next_token_on_same_line(s);
1428 if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
1429 isl_stream_push_token(s, tok2);
1430 isl_stream_push_token(s, tok);
1431 return isl_map_from_basic_map(basic_map_read_polylib(s));
1432 }
1433 if (tok2) {
1434 isl_stream_error(s, tok2, "unexpected token");
1435 isl_stream_push_token(s, tok2);
1436 isl_stream_push_token(s, tok);
1437 return NULL;
1438 }
1439 n = isl_int_get_si(tok->u.v);
1440 isl_token_free(tok);
1441
1442 isl_assert(s->ctx, n >= 1, return NULL);
1443
1444 map = isl_map_from_basic_map(basic_map_read_polylib(s));
1445
1446 for (i = 1; map && i < n; ++i)
1447 map = isl_map_union(map,
1448 isl_map_from_basic_map(basic_map_read_polylib(s)));
1449
1450 return map;
1451 }
1452
1453 static int optional_power(struct isl_stream *s)
1454 {
1455 int pow;
1456 struct isl_token *tok;
1457
1458 tok = isl_stream_next_token(s);
1459 if (!tok)
1460 return 1;
1461 if (tok->type != '^') {
1462 isl_stream_push_token(s, tok);
1463 return 1;
1464 }
1465 isl_token_free(tok);
1466 tok = isl_stream_next_token(s);
1467 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1468 isl_stream_error(s, tok, "expecting exponent");
1469 if (tok)
1470 isl_stream_push_token(s, tok);
1471 return 1;
1472 }
1473 pow = isl_int_get_si(tok->u.v);
1474 isl_token_free(tok);
1475 return pow;
1476 }
1477
1478 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1479 __isl_keep isl_map *map, struct vars *v);
1480
1481 static __isl_give isl_pw_qpolynomial *read_factor(struct isl_stream *s,
1482 __isl_keep isl_map *map, struct vars *v)
1483 {
1484 isl_pw_qpolynomial *pwqp;
1485 struct isl_token *tok;
1486
1487 tok = next_token(s);
1488 if (!tok) {
1489 isl_stream_error(s, NULL, "unexpected EOF");
1490 return NULL;
1491 }
1492 if (tok->type == '(') {
1493 int pow;
1494
1495 isl_token_free(tok);
1496 pwqp = read_term(s, map, v);
1497 if (!pwqp)
1498 return NULL;
1499 if (isl_stream_eat(s, ')'))
1500 goto error;
1501 pow = optional_power(s);
1502 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1503 } else if (tok->type == ISL_TOKEN_VALUE) {
1504 struct isl_token *tok2;
1505 tok2 = isl_stream_next_token(s);
1506 isl_qpolynomial *qp;
1507 if (tok2 && tok2->type == '/') {
1508 isl_token_free(tok2);
1509 tok2 = next_token(s);
1510 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1511 isl_stream_error(s, tok2, "expected denominator");
1512 isl_token_free(tok);
1513 isl_token_free(tok2);
1514 return NULL;
1515 }
1516 qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map),
1517 tok->u.v, tok2->u.v);
1518 isl_token_free(tok2);
1519 } else {
1520 isl_stream_push_token(s, tok2);
1521 qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map),
1522 tok->u.v);
1523 }
1524 isl_token_free(tok);
1525 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1526 } else if (tok->type == ISL_TOKEN_INFTY) {
1527 isl_qpolynomial *qp;
1528 isl_token_free(tok);
1529 qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map));
1530 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1531 } else if (tok->type == ISL_TOKEN_NAN) {
1532 isl_qpolynomial *qp;
1533 isl_token_free(tok);
1534 qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map));
1535 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1536 } else if (tok->type == ISL_TOKEN_IDENT) {
1537 int n = v->n;
1538 int pos = vars_pos(v, tok->u.s, -1);
1539 int pow;
1540 isl_qpolynomial *qp;
1541 if (pos < 0) {
1542 isl_token_free(tok);
1543 return NULL;
1544 }
1545 if (pos >= n) {
1546 vars_drop(v, v->n - n);
1547 isl_stream_error(s, tok, "unknown identifier");
1548 isl_token_free(tok);
1549 return NULL;
1550 }
1551 isl_token_free(tok);
1552 pow = optional_power(s);
1553 qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow);
1554 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1555 } else if (tok->type == '[') {
1556 isl_pw_aff *pwaff;
1557 int pow;
1558
1559 isl_stream_push_token(s, tok);
1560 pwaff = accept_affine(s, isl_map_get_space(map), v);
1561 pow = optional_power(s);
1562 pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff);
1563 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1564 } else if (tok->type == '-') {
1565 isl_token_free(tok);
1566 pwqp = read_factor(s, map, v);
1567 pwqp = isl_pw_qpolynomial_neg(pwqp);
1568 } else {
1569 isl_stream_error(s, tok, "unexpected isl_token");
1570 isl_stream_push_token(s, tok);
1571 return NULL;
1572 }
1573
1574 if (isl_stream_eat_if_available(s, '*') ||
1575 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
1576 isl_pw_qpolynomial *pwqp2;
1577
1578 pwqp2 = read_factor(s, map, v);
1579 pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2);
1580 }
1581
1582 return pwqp;
1583 error:
1584 isl_pw_qpolynomial_free(pwqp);
1585 return NULL;
1586 }
1587
1588 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1589 __isl_keep isl_map *map, struct vars *v)
1590 {
1591 struct isl_token *tok;
1592 isl_pw_qpolynomial *pwqp;
1593
1594 pwqp = read_factor(s, map, v);
1595
1596 for (;;) {
1597 tok = next_token(s);
1598 if (!tok)
1599 return pwqp;
1600
1601 if (tok->type == '+') {
1602 isl_pw_qpolynomial *pwqp2;
1603
1604 isl_token_free(tok);
1605 pwqp2 = read_factor(s, map, v);
1606 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
1607 } else if (tok->type == '-') {
1608 isl_pw_qpolynomial *pwqp2;
1609
1610 isl_token_free(tok);
1611 pwqp2 = read_factor(s, map, v);
1612 pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2);
1613 } else if (tok->type == ISL_TOKEN_VALUE &&
1614 isl_int_is_neg(tok->u.v)) {
1615 isl_pw_qpolynomial *pwqp2;
1616
1617 isl_stream_push_token(s, tok);
1618 pwqp2 = read_factor(s, map, v);
1619 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
1620 } else {
1621 isl_stream_push_token(s, tok);
1622 break;
1623 }
1624 }
1625
1626 return pwqp;
1627 }
1628
1629 static __isl_give isl_map *read_optional_disjuncts(struct isl_stream *s,
1630 __isl_take isl_map *map, struct vars *v)
1631 {
1632 struct isl_token *tok;
1633
1634 tok = isl_stream_next_token(s);
1635 if (!tok) {
1636 isl_stream_error(s, NULL, "unexpected EOF");
1637 goto error;
1638 }
1639 if (tok->type == ':' ||
1640 (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {
1641 isl_token_free(tok);
1642 map = read_disjuncts(s, v, map);
1643 } else
1644 isl_stream_push_token(s, tok);
1645
1646 return map;
1647 error:
1648 isl_map_free(map);
1649 return NULL;
1650 }
1651
1652 static struct isl_obj obj_read_poly(struct isl_stream *s,
1653 __isl_take isl_map *map, struct vars *v, int n)
1654 {
1655 struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
1656 isl_pw_qpolynomial *pwqp;
1657 struct isl_set *set;
1658
1659 pwqp = read_term(s, map, v);
1660 map = read_optional_disjuncts(s, map, v);
1661 set = isl_map_range(map);
1662
1663 pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set);
1664
1665 vars_drop(v, v->n - n);
1666
1667 obj.v = pwqp;
1668 return obj;
1669 }
1670
1671 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
1672 __isl_take isl_set *set, struct vars *v, int n)
1673 {
1674 struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
1675 isl_pw_qpolynomial *pwqp;
1676 isl_pw_qpolynomial_fold *pwf = NULL;
1677
1678 if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
1679 return obj_read_poly(s, set, v, n);
1680
1681 if (isl_stream_eat(s, '('))
1682 goto error;
1683
1684 pwqp = read_term(s, set, v);
1685 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, pwqp);
1686
1687 while (isl_stream_eat_if_available(s, ',')) {
1688 isl_pw_qpolynomial_fold *pwf_i;
1689 pwqp = read_term(s, set, v);
1690 pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max,
1691 pwqp);
1692 pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i);
1693 }
1694
1695 if (isl_stream_eat(s, ')'))
1696 goto error;
1697
1698 set = read_optional_disjuncts(s, set, v);
1699 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set);
1700
1701 vars_drop(v, v->n - n);
1702
1703 obj.v = pwf;
1704 return obj;
1705 error:
1706 isl_set_free(set);
1707 isl_pw_qpolynomial_fold_free(pwf);
1708 obj.type = isl_obj_none;
1709 return obj;
1710 }
1711
1712 static int is_rational(struct isl_stream *s)
1713 {
1714 struct isl_token *tok;
1715
1716 tok = isl_stream_next_token(s);
1717 if (!tok)
1718 return 0;
1719 if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) {
1720 isl_token_free(tok);
1721 isl_stream_eat(s, ':');
1722 return 1;
1723 }
1724
1725 isl_stream_push_token(s, tok);
1726
1727 return 0;
1728 }
1729
1730 static struct isl_obj obj_read_body(struct isl_stream *s,
1731 __isl_take isl_map *map, struct vars *v)
1732 {
1733 struct isl_token *tok;
1734 struct isl_obj obj = { isl_obj_set, NULL };
1735 int n = v->n;
1736
1737 if (is_rational(s))
1738 map = isl_map_set_rational(map);
1739
1740 if (isl_stream_next_token_is(s, ':')) {
1741 obj.type = isl_obj_set;
1742 obj.v = read_optional_disjuncts(s, map, v);
1743 return obj;
1744 }
1745
1746 if (!next_is_tuple(s))
1747 return obj_read_poly_or_fold(s, map, v, n);
1748
1749 map = read_tuple(s, map, isl_dim_in, v);
1750 if (!map)
1751 goto error;
1752 tok = isl_stream_next_token(s);
1753 if (tok && tok->type == ISL_TOKEN_TO) {
1754 obj.type = isl_obj_map;
1755 isl_token_free(tok);
1756 if (!next_is_tuple(s)) {
1757 isl_set *set = isl_map_domain(map);
1758 return obj_read_poly_or_fold(s, set, v, n);
1759 }
1760 map = read_tuple(s, map, isl_dim_out, v);
1761 if (!map)
1762 goto error;
1763 } else {
1764 map = isl_map_reverse(map);
1765 if (tok)
1766 isl_stream_push_token(s, tok);
1767 }
1768
1769 map = read_optional_disjuncts(s, map, v);
1770
1771 vars_drop(v, v->n - n);
1772
1773 obj.v = map;
1774 return obj;
1775 error:
1776 isl_map_free(map);
1777 obj.type = isl_obj_none;
1778 return obj;
1779 }
1780
1781 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
1782 {
1783 if (obj.type == isl_obj_map) {
1784 obj.v = isl_union_map_from_map(obj.v);
1785 obj.type = isl_obj_union_map;
1786 } else if (obj.type == isl_obj_set) {
1787 obj.v = isl_union_set_from_set(obj.v);
1788 obj.type = isl_obj_union_set;
1789 } else if (obj.type == isl_obj_pw_qpolynomial) {
1790 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
1791 obj.type = isl_obj_union_pw_qpolynomial;
1792 } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
1793 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
1794 obj.type = isl_obj_union_pw_qpolynomial_fold;
1795 } else
1796 isl_assert(ctx, 0, goto error);
1797 return obj;
1798 error:
1799 obj.type->free(obj.v);
1800 obj.type = isl_obj_none;
1801 return obj;
1802 }
1803
1804 static struct isl_obj obj_add(struct isl_ctx *ctx,
1805 struct isl_obj obj1, struct isl_obj obj2)
1806 {
1807 if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
1808 obj1 = to_union(ctx, obj1);
1809 if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
1810 obj2 = to_union(ctx, obj2);
1811 if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
1812 obj1 = to_union(ctx, obj1);
1813 if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
1814 obj2 = to_union(ctx, obj2);
1815 if (obj1.type == isl_obj_pw_qpolynomial &&
1816 obj2.type == isl_obj_union_pw_qpolynomial)
1817 obj1 = to_union(ctx, obj1);
1818 if (obj1.type == isl_obj_union_pw_qpolynomial &&
1819 obj2.type == isl_obj_pw_qpolynomial)
1820 obj2 = to_union(ctx, obj2);
1821 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1822 obj2.type == isl_obj_union_pw_qpolynomial_fold)
1823 obj1 = to_union(ctx, obj1);
1824 if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
1825 obj2.type == isl_obj_pw_qpolynomial_fold)
1826 obj2 = to_union(ctx, obj2);
1827 isl_assert(ctx, obj1.type == obj2.type, goto error);
1828 if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) {
1829 obj1 = to_union(ctx, obj1);
1830 obj2 = to_union(ctx, obj2);
1831 }
1832 if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) {
1833 obj1 = to_union(ctx, obj1);
1834 obj2 = to_union(ctx, obj2);
1835 }
1836 if (obj1.type == isl_obj_pw_qpolynomial &&
1837 !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) {
1838 obj1 = to_union(ctx, obj1);
1839 obj2 = to_union(ctx, obj2);
1840 }
1841 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1842 !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) {
1843 obj1 = to_union(ctx, obj1);
1844 obj2 = to_union(ctx, obj2);
1845 }
1846 obj1.v = obj1.type->add(obj1.v, obj2.v);
1847 return obj1;
1848 error:
1849 obj1.type->free(obj1.v);
1850 obj2.type->free(obj2.v);
1851 obj1.type = isl_obj_none;
1852 obj1.v = NULL;
1853 return obj1;
1854 }
1855
1856 static struct isl_obj obj_read(struct isl_stream *s)
1857 {
1858 isl_map *map = NULL;
1859 struct isl_token *tok;
1860 struct vars *v = NULL;
1861 struct isl_obj obj = { isl_obj_set, NULL };
1862
1863 tok = next_token(s);
1864 if (!tok) {
1865 isl_stream_error(s, NULL, "unexpected EOF");
1866 goto error;
1867 }
1868 if (tok->type == ISL_TOKEN_VALUE) {
1869 struct isl_token *tok2;
1870 struct isl_map *map;
1871
1872 tok2 = isl_stream_next_token(s);
1873 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
1874 isl_int_is_neg(tok2->u.v)) {
1875 if (tok2)
1876 isl_stream_push_token(s, tok2);
1877 obj.type = isl_obj_int;
1878 obj.v = isl_int_obj_alloc(s->ctx, tok->u.v);
1879 isl_token_free(tok);
1880 return obj;
1881 }
1882 isl_stream_push_token(s, tok2);
1883 isl_stream_push_token(s, tok);
1884 map = map_read_polylib(s);
1885 if (!map)
1886 goto error;
1887 if (isl_map_may_be_set(map))
1888 obj.v = isl_map_range(map);
1889 else {
1890 obj.type = isl_obj_map;
1891 obj.v = map;
1892 }
1893 return obj;
1894 }
1895 v = vars_new(s->ctx);
1896 if (!v) {
1897 isl_stream_push_token(s, tok);
1898 goto error;
1899 }
1900 map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));
1901 if (tok->type == '[') {
1902 isl_stream_push_token(s, tok);
1903 map = read_tuple(s, map, isl_dim_param, v);
1904 if (!map)
1905 goto error;
1906 tok = isl_stream_next_token(s);
1907 if (!tok || tok->type != ISL_TOKEN_TO) {
1908 isl_stream_error(s, tok, "expecting '->'");
1909 if (tok)
1910 isl_stream_push_token(s, tok);
1911 goto error;
1912 }
1913 isl_token_free(tok);
1914 tok = isl_stream_next_token(s);
1915 }
1916 if (!tok || tok->type != '{') {
1917 isl_stream_error(s, tok, "expecting '{'");
1918 if (tok)
1919 isl_stream_push_token(s, tok);
1920 goto error;
1921 }
1922 isl_token_free(tok);
1923
1924 tok = isl_stream_next_token(s);
1925 if (!tok)
1926 ;
1927 else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
1928 isl_token_free(tok);
1929 if (isl_stream_eat(s, '='))
1930 goto error;
1931 map = read_tuple(s, map, isl_dim_param, v);
1932 if (!map)
1933 goto error;
1934 } else if (tok->type == '}') {
1935 obj.type = isl_obj_union_set;
1936 obj.v = isl_union_set_empty(isl_map_get_space(map));
1937 isl_token_free(tok);
1938 goto done;
1939 } else
1940 isl_stream_push_token(s, tok);
1941
1942 for (;;) {
1943 struct isl_obj o;
1944 tok = NULL;
1945 o = obj_read_body(s, isl_map_copy(map), v);
1946 if (o.type == isl_obj_none || !o.v)
1947 goto error;
1948 if (!obj.v)
1949 obj = o;
1950 else {
1951 obj = obj_add(s->ctx, obj, o);
1952 if (obj.type == isl_obj_none || !obj.v)
1953 goto error;
1954 }
1955 tok = isl_stream_next_token(s);
1956 if (!tok || tok->type != ';')
1957 break;
1958 isl_token_free(tok);
1959 if (isl_stream_next_token_is(s, '}')) {
1960 tok = isl_stream_next_token(s);
1961 break;
1962 }
1963 }
1964
1965 if (tok && tok->type == '}') {
1966 isl_token_free(tok);
1967 } else {
1968 isl_stream_error(s, tok, "unexpected isl_token");
1969 if (tok)
1970 isl_token_free(tok);
1971 goto error;
1972 }
1973 done:
1974 vars_free(v);
1975 isl_map_free(map);
1976
1977 return obj;
1978 error:
1979 isl_map_free(map);
1980 obj.type->free(obj.v);
1981 if (v)
1982 vars_free(v);
1983 obj.v = NULL;
1984 return obj;
1985 }
1986
1987 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
1988 {
1989 return obj_read(s);
1990 }
1991
1992 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s)
1993 {
1994 struct isl_obj obj;
1995
1996 obj = obj_read(s);
1997 if (obj.v)
1998 isl_assert(s->ctx, obj.type == isl_obj_map ||
1999 obj.type == isl_obj_set, goto error);
2000
2001 return obj.v;
2002 error:
2003 obj.type->free(obj.v);
2004 return NULL;
2005 }
2006
2007 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s)
2008 {
2009 struct isl_obj obj;
2010
2011 obj = obj_read(s);
2012 if (obj.v) {
2013 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) {
2014 obj.v = isl_map_range(obj.v);
2015 obj.type = isl_obj_set;
2016 }
2017 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2018 }
2019
2020 return obj.v;
2021 error:
2022 obj.type->free(obj.v);
2023 return NULL;
2024 }
2025
2026 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2027 {
2028 struct isl_obj obj;
2029
2030 obj = obj_read(s);
2031 if (obj.type == isl_obj_map) {
2032 obj.type = isl_obj_union_map;
2033 obj.v = isl_union_map_from_map(obj.v);
2034 }
2035 if (obj.type == isl_obj_set) {
2036 obj.type = isl_obj_union_set;
2037 obj.v = isl_union_set_from_set(obj.v);
2038 }
2039 if (obj.v)
2040 isl_assert(s->ctx, obj.type == isl_obj_union_map ||
2041 obj.type == isl_obj_union_set, goto error);
2042
2043 return obj.v;
2044 error:
2045 obj.type->free(obj.v);
2046 return NULL;
2047 }
2048
2049 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2050 {
2051 struct isl_obj obj;
2052
2053 obj = obj_read(s);
2054 if (obj.type == isl_obj_set) {
2055 obj.type = isl_obj_union_set;
2056 obj.v = isl_union_set_from_set(obj.v);
2057 }
2058 if (obj.v)
2059 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2060
2061 return obj.v;
2062 error:
2063 obj.type->free(obj.v);
2064 return NULL;
2065 }
2066
2067 static __isl_give isl_basic_map *basic_map_read(struct isl_stream *s)
2068 {
2069 struct isl_obj obj;
2070 struct isl_map *map;
2071 struct isl_basic_map *bmap;
2072
2073 obj = obj_read(s);
2074 map = obj.v;
2075 if (!map)
2076 return NULL;
2077
2078 isl_assert(map->ctx, map->n <= 1, goto error);
2079
2080 if (map->n == 0)
2081 bmap = isl_basic_map_empty_like_map(map);
2082 else
2083 bmap = isl_basic_map_copy(map->p[0]);
2084
2085 isl_map_free(map);
2086
2087 return bmap;
2088 error:
2089 isl_map_free(map);
2090 return NULL;
2091 }
2092
2093 static __isl_give isl_basic_set *basic_set_read(struct isl_stream *s)
2094 {
2095 isl_basic_map *bmap;
2096 bmap = basic_map_read(s);
2097 if (!bmap)
2098 return NULL;
2099 if (!isl_basic_map_may_be_set(bmap))
2100 isl_die(s->ctx, isl_error_invalid,
2101 "input is not a set", goto error);
2102 return isl_basic_map_range(bmap);
2103 error:
2104 isl_basic_map_free(bmap);
2105 return NULL;
2106 }
2107
2108 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2109 FILE *input)
2110 {
2111 struct isl_basic_map *bmap;
2112 struct isl_stream *s = isl_stream_new_file(ctx, input);
2113 if (!s)
2114 return NULL;
2115 bmap = basic_map_read(s);
2116 isl_stream_free(s);
2117 return bmap;
2118 }
2119
2120 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2121 FILE *input)
2122 {
2123 isl_basic_set *bset;
2124 struct isl_stream *s = isl_stream_new_file(ctx, input);
2125 if (!s)
2126 return NULL;
2127 bset = basic_set_read(s);
2128 isl_stream_free(s);
2129 return bset;
2130 }
2131
2132 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2133 const char *str)
2134 {
2135 struct isl_basic_map *bmap;
2136 struct isl_stream *s = isl_stream_new_str(ctx, str);
2137 if (!s)
2138 return NULL;
2139 bmap = basic_map_read(s);
2140 isl_stream_free(s);
2141 return bmap;
2142 }
2143
2144 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2145 const char *str)
2146 {
2147 isl_basic_set *bset;
2148 struct isl_stream *s = isl_stream_new_str(ctx, str);
2149 if (!s)
2150 return NULL;
2151 bset = basic_set_read(s);
2152 isl_stream_free(s);
2153 return bset;
2154 }
2155
2156 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2157 FILE *input)
2158 {
2159 struct isl_map *map;
2160 struct isl_stream *s = isl_stream_new_file(ctx, input);
2161 if (!s)
2162 return NULL;
2163 map = isl_stream_read_map(s);
2164 isl_stream_free(s);
2165 return map;
2166 }
2167
2168 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2169 const char *str)
2170 {
2171 struct isl_map *map;
2172 struct isl_stream *s = isl_stream_new_str(ctx, str);
2173 if (!s)
2174 return NULL;
2175 map = isl_stream_read_map(s);
2176 isl_stream_free(s);
2177 return map;
2178 }
2179
2180 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2181 FILE *input)
2182 {
2183 isl_set *set;
2184 struct isl_stream *s = isl_stream_new_file(ctx, input);
2185 if (!s)
2186 return NULL;
2187 set = isl_stream_read_set(s);
2188 isl_stream_free(s);
2189 return set;
2190 }
2191
2192 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2193 const char *str)
2194 {
2195 isl_set *set;
2196 struct isl_stream *s = isl_stream_new_str(ctx, str);
2197 if (!s)
2198 return NULL;
2199 set = isl_stream_read_set(s);
2200 isl_stream_free(s);
2201 return set;
2202 }
2203
2204 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2205 FILE *input)
2206 {
2207 isl_union_map *umap;
2208 struct isl_stream *s = isl_stream_new_file(ctx, input);
2209 if (!s)
2210 return NULL;
2211 umap = isl_stream_read_union_map(s);
2212 isl_stream_free(s);
2213 return umap;
2214 }
2215
2216 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2217 const char *str)
2218 {
2219 isl_union_map *umap;
2220 struct isl_stream *s = isl_stream_new_str(ctx, str);
2221 if (!s)
2222 return NULL;
2223 umap = isl_stream_read_union_map(s);
2224 isl_stream_free(s);
2225 return umap;
2226 }
2227
2228 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2229 FILE *input)
2230 {
2231 isl_union_set *uset;
2232 struct isl_stream *s = isl_stream_new_file(ctx, input);
2233 if (!s)
2234 return NULL;
2235 uset = isl_stream_read_union_set(s);
2236 isl_stream_free(s);
2237 return uset;
2238 }
2239
2240 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2241 const char *str)
2242 {
2243 isl_union_set *uset;
2244 struct isl_stream *s = isl_stream_new_str(ctx, str);
2245 if (!s)
2246 return NULL;
2247 uset = isl_stream_read_union_set(s);
2248 isl_stream_free(s);
2249 return uset;
2250 }
2251
2252 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2253 {
2254 struct isl_vec *vec = NULL;
2255 struct isl_token *tok;
2256 unsigned size;
2257 int j;
2258
2259 tok = isl_stream_next_token(s);
2260 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2261 isl_stream_error(s, tok, "expecting vector length");
2262 goto error;
2263 }
2264
2265 size = isl_int_get_si(tok->u.v);
2266 isl_token_free(tok);
2267
2268 vec = isl_vec_alloc(s->ctx, size);
2269
2270 for (j = 0; j < size; ++j) {
2271 tok = isl_stream_next_token(s);
2272 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2273 isl_stream_error(s, tok, "expecting constant value");
2274 goto error;
2275 }
2276 isl_int_set(vec->el[j], tok->u.v);
2277 isl_token_free(tok);
2278 }
2279
2280 return vec;
2281 error:
2282 isl_token_free(tok);
2283 isl_vec_free(vec);
2284 return NULL;
2285 }
2286
2287 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2288 {
2289 return isl_vec_read_polylib(s);
2290 }
2291
2292 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2293 {
2294 isl_vec *v;
2295 struct isl_stream *s = isl_stream_new_file(ctx, input);
2296 if (!s)
2297 return NULL;
2298 v = vec_read(s);
2299 isl_stream_free(s);
2300 return v;
2301 }
2302
2303 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2304 struct isl_stream *s)
2305 {
2306 struct isl_obj obj;
2307
2308 obj = obj_read(s);
2309 if (obj.v)
2310 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2311 goto error);
2312
2313 return obj.v;
2314 error:
2315 obj.type->free(obj.v);
2316 return NULL;
2317 }
2318
2319 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2320 const char *str)
2321 {
2322 isl_pw_qpolynomial *pwqp;
2323 struct isl_stream *s = isl_stream_new_str(ctx, str);
2324 if (!s)
2325 return NULL;
2326 pwqp = isl_stream_read_pw_qpolynomial(s);
2327 isl_stream_free(s);
2328 return pwqp;
2329 }
2330
2331 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
2332 FILE *input)
2333 {
2334 isl_pw_qpolynomial *pwqp;
2335 struct isl_stream *s = isl_stream_new_file(ctx, input);
2336 if (!s)
2337 return NULL;
2338 pwqp = isl_stream_read_pw_qpolynomial(s);
2339 isl_stream_free(s);
2340 return pwqp;
2341 }
2342
2343 /* Read an affine expression from "s" with domain (space) "dom".
2344 * We call accept_affine to parse a possibly piecewise affine expression
2345 * and then check that the result is a single affine expression on
2346 * a universe domain.
2347 */
2348 static __isl_give isl_aff *read_aff_with_dom(struct isl_stream *s,
2349 __isl_take isl_set *dom, struct vars *v)
2350 {
2351 isl_aff *aff = NULL;
2352 isl_pw_aff *pwaff = NULL;
2353
2354 if (!isl_set_plain_is_universe(dom))
2355 isl_die(s->ctx, isl_error_invalid,
2356 "expecting universe domain", goto error);
2357
2358 if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2359 goto error;
2360
2361 if (isl_stream_eat(s, '['))
2362 goto error;
2363
2364 pwaff = accept_affine(s, isl_set_get_space(dom), v);
2365
2366 if (isl_stream_eat(s, ']'))
2367 goto error;
2368 if (isl_stream_eat(s, '}'))
2369 goto error;
2370
2371 if (!pwaff)
2372 goto error;
2373
2374 if (pwaff->n != 1)
2375 isl_die(s->ctx, isl_error_invalid,
2376 "expecting single affine expression", goto error);
2377 if (!isl_set_plain_is_universe(pwaff->p[0].set))
2378 isl_die(s->ctx, isl_error_invalid,
2379 "expecting universe domain", goto error);
2380
2381 aff = isl_aff_copy(pwaff->p[0].aff);
2382
2383 vars_free(v);
2384 isl_pw_aff_free(pwaff);
2385 isl_set_free(dom);
2386 return aff;
2387 error:
2388 vars_free(v);
2389 isl_pw_aff_free(pwaff);
2390 isl_set_free(dom);
2391 return NULL;
2392 }
2393
2394 /* Is the next token an identifer not in "v"?
2395 */
2396 static int next_is_fresh_ident(struct isl_stream *s, struct vars *v)
2397 {
2398 int n = v->n;
2399 int fresh;
2400 struct isl_token *tok;
2401
2402 tok = isl_stream_next_token(s);
2403 if (!tok)
2404 return 0;
2405 fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n;
2406 isl_stream_push_token(s, tok);
2407
2408 vars_drop(v, v->n - n);
2409
2410 return fresh;
2411 }
2412
2413 /* First read the domain of the affine expression, which may be
2414 * a parameter space or a set.
2415 * The tricky part is that we don't know if the domain is a set or not,
2416 * so when we are trying to read the domain, we may actually be reading
2417 * the affine expression itself (defined on a parameter domains)
2418 * If the tuple we are reading is named, we assume it's the domain.
2419 * Also, if inside the tuple, the first thing we find is a nested tuple
2420 * or a new identifier, we again assume it's the domain.
2421 * Otherwise, we assume we are reading an affine expression.
2422 */
2423 static __isl_give isl_set *read_aff_domain(struct isl_stream *s,
2424 __isl_take isl_set *dom, struct vars *v)
2425 {
2426 struct isl_token *tok;
2427
2428 tok = isl_stream_next_token(s);
2429 if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
2430 isl_stream_push_token(s, tok);
2431 return read_tuple(s, dom, isl_dim_set, v);
2432 }
2433 if (!tok || tok->type != '[') {
2434 isl_stream_error(s, tok, "expecting '['");
2435 goto error;
2436 }
2437 if (next_is_tuple(s) || next_is_fresh_ident(s, v)) {
2438 isl_stream_push_token(s, tok);
2439 dom = read_tuple(s, dom, isl_dim_set, v);
2440 } else
2441 isl_stream_push_token(s, tok);
2442
2443 return dom;
2444 error:
2445 if (tok)
2446 isl_stream_push_token(s, tok);
2447 vars_free(v);
2448 isl_set_free(dom);
2449 return NULL;
2450 }
2451
2452 /* Read an affine expression from "s".
2453 * We first read the domain of the affine expression, which may be
2454 * a parameter space or a set, and then call read_aff_with_dom.
2455 */
2456 __isl_give isl_aff *isl_stream_read_aff(struct isl_stream *s)
2457 {
2458 struct vars *v;
2459 isl_set *dom = NULL;
2460
2461 v = vars_new(s->ctx);
2462 if (!v)
2463 return NULL;
2464
2465 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2466 if (next_is_tuple(s)) {
2467 dom = read_tuple(s, dom, isl_dim_param, v);
2468 if (isl_stream_eat(s, ISL_TOKEN_TO))
2469 goto error;
2470 }
2471 if (isl_stream_eat(s, '{'))
2472 goto error;
2473
2474 dom = read_aff_domain(s, dom, v);
2475 return read_aff_with_dom(s, dom, v);
2476 error:
2477 vars_free(v);
2478 isl_set_free(dom);
2479 return NULL;
2480 }
2481
2482 /* Read a piecewise affine expression from "s" with domain (space) "dom".
2483 */
2484 static __isl_give isl_pw_aff *read_pw_aff_with_dom(struct isl_stream *s,
2485 __isl_take isl_set *dom, struct vars *v)
2486 {
2487 isl_pw_aff *pwaff = NULL;
2488
2489 if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2490 goto error;
2491
2492 if (isl_stream_eat(s, '['))
2493 goto error;
2494
2495 pwaff = accept_affine(s, isl_set_get_space(dom), v);
2496
2497 if (isl_stream_eat(s, ']'))
2498 goto error;
2499
2500 dom = read_optional_disjuncts(s, dom, v);
2501 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2502
2503 return pwaff;
2504 error:
2505 isl_set_free(dom);
2506 isl_pw_aff_free(pwaff);
2507 return NULL;
2508 }
2509
2510 __isl_give isl_pw_aff *isl_stream_read_pw_aff(struct isl_stream *s)
2511 {
2512 struct vars *v;
2513 isl_set *dom = NULL;
2514 isl_set *aff_dom;
2515 isl_pw_aff *pa = NULL;
2516 int n;
2517
2518 v = vars_new(s->ctx);
2519 if (!v)
2520 return NULL;
2521
2522 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2523 if (next_is_tuple(s)) {
2524 dom = read_tuple(s, dom, isl_dim_param, v);
2525 if (isl_stream_eat(s, ISL_TOKEN_TO))
2526 goto error;
2527 }
2528 if (isl_stream_eat(s, '{'))
2529 goto error;
2530
2531 n = v->n;
2532 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2533 pa = read_pw_aff_with_dom(s, aff_dom, v);
2534 vars_drop(v, v->n - n);
2535
2536 while (isl_stream_eat_if_available(s, ';')) {
2537 isl_pw_aff *pa_i;
2538
2539 n = v->n;
2540 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2541 pa_i = read_pw_aff_with_dom(s, aff_dom, v);
2542 vars_drop(v, v->n - n);
2543
2544 pa = isl_pw_aff_add(pa, pa_i);
2545 }
2546
2547 if (isl_stream_eat(s, '}'))
2548 goto error;
2549
2550 vars_free(v);
2551 isl_set_free(dom);
2552 return pa;
2553 error:
2554 vars_free(v);
2555 isl_set_free(dom);
2556 isl_pw_aff_free(pa);
2557 return NULL;
2558 }
2559
2560 __isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str)
2561 {
2562 isl_aff *aff;
2563 struct isl_stream *s = isl_stream_new_str(ctx, str);
2564 if (!s)
2565 return NULL;
2566 aff = isl_stream_read_aff(s);
2567 isl_stream_free(s);
2568 return aff;
2569 }
2570
2571 __isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str)
2572 {
2573 isl_pw_aff *pa;
2574 struct isl_stream *s = isl_stream_new_str(ctx, str);
2575 if (!s)
2576 return NULL;
2577 pa = isl_stream_read_pw_aff(s);
2578 isl_stream_free(s);
2579 return pa;
2580 }
2581
2582 /* Read an isl_pw_multi_aff from "s".
2583 * We currently read a generic object and if it turns out to be a set or
2584 * a map, we convert that to an isl_pw_multi_aff.
2585 * It would be more efficient if we were to construct the isl_pw_multi_aff
2586 * directly.
2587 */
2588 __isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(struct isl_stream *s)
2589 {
2590 struct isl_obj obj;
2591
2592 obj = obj_read(s);
2593 if (!obj.v)
2594 return NULL;
2595
2596 if (obj.type == isl_obj_map)
2597 return isl_pw_multi_aff_from_map(obj.v);
2598 if (obj.type == isl_obj_set)
2599 return isl_pw_multi_aff_from_set(obj.v);
2600
2601 obj.type->free(obj.v);
2602 isl_die(s->ctx, isl_error_invalid, "unexpected object type",
2603 return NULL);
2604 }
2605
2606 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx,
2607 const char *str)
2608 {
2609 isl_pw_multi_aff *pma;
2610 struct isl_stream *s = isl_stream_new_str(ctx, str);
2611 if (!s)
2612 return NULL;
2613 pma = isl_stream_read_pw_multi_aff(s);
2614 isl_stream_free(s);
2615 return pma;
2616 }
2617
2618 /* Read a multi-affine expression from "s".
2619 * We call isl_stream_read_pw_multi_aff to parse a possibly piecewise
2620 * multi-affine expression and then check that the result is
2621 * a single multi-affine expression on a universe domain.
2622 */
2623 __isl_give isl_multi_aff *isl_stream_read_multi_aff(struct isl_stream *s)
2624 {
2625 isl_pw_multi_aff *pma;
2626 isl_multi_aff *maff;
2627
2628 pma = isl_stream_read_pw_multi_aff(s);
2629 if (!pma)
2630 return NULL;
2631 if (pma->n != 1)
2632 isl_die(s->ctx, isl_error_invalid,
2633 "expecting single list of affine expressions",
2634 return isl_pw_multi_aff_free(pma));
2635 if (!isl_set_plain_is_universe(pma->p[0].set))
2636 isl_die(s->ctx, isl_error_invalid, "expecting universe domain",
2637 return isl_pw_multi_aff_free(pma));
2638 maff = isl_multi_aff_copy(pma->p[0].maff);
2639 isl_pw_multi_aff_free(pma);
2640 return maff;
2641 }
2642
2643 __isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx,
2644 const char *str)
2645 {
2646 isl_multi_aff *maff;
2647 struct isl_stream *s = isl_stream_new_str(ctx, str);
2648 if (!s)
2649 return NULL;
2650 maff = isl_stream_read_multi_aff(s);
2651 isl_stream_free(s);
2652 return maff;
2653 }
2654
2655 __isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial(
2656 struct isl_stream *s)
2657 {
2658 struct isl_obj obj;
2659
2660 obj = obj_read(s);
2661 if (obj.type == isl_obj_pw_qpolynomial) {
2662 obj.type = isl_obj_union_pw_qpolynomial;
2663 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2664 }
2665 if (obj.v)
2666 isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial,
2667 goto error);
2668
2669 return obj.v;
2670 error:
2671 obj.type->free(obj.v);
2672 return NULL;
2673 }
2674
2675 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str(
2676 isl_ctx *ctx, const char *str)
2677 {
2678 isl_union_pw_qpolynomial *upwqp;
2679 struct isl_stream *s = isl_stream_new_str(ctx, str);
2680 if (!s)
2681 return NULL;
2682 upwqp = isl_stream_read_union_pw_qpolynomial(s);
2683 isl_stream_free(s);
2684 return upwqp;
2685 }
Integer set library