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