?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_transitive_closure.c: union_components: avoid invalid access on error path
[isl.git] / isl_input.c
blobafc5277b4d37936d1de8178d3f09057f11f70bb2
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 && tok->type == ISL_TOKEN_TO) {
1759 obj.type = isl_obj_map;
1760 isl_token_free(tok);
1761 if (!next_is_tuple(s)) {
1762 isl_set *set = isl_map_domain(map);
1763 return obj_read_poly_or_fold(s, set, v, n);
1764 }
1765 map = read_tuple(s, map, isl_dim_out, v);
1766 if (!map)
1767 goto error;
1768 } else {
1769 map = isl_map_reverse(map);
1770 if (tok)
1771 isl_stream_push_token(s, tok);
1772 }
1773
1774 map = read_optional_disjuncts(s, map, v);
1775
1776 vars_drop(v, v->n - n);
1777
1778 obj.v = map;
1779 return obj;
1780 error:
1781 isl_map_free(map);
1782 obj.type = isl_obj_none;
1783 return obj;
1784 }
1785
1786 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
1787 {
1788 if (obj.type == isl_obj_map) {
1789 obj.v = isl_union_map_from_map(obj.v);
1790 obj.type = isl_obj_union_map;
1791 } else if (obj.type == isl_obj_set) {
1792 obj.v = isl_union_set_from_set(obj.v);
1793 obj.type = isl_obj_union_set;
1794 } else if (obj.type == isl_obj_pw_qpolynomial) {
1795 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
1796 obj.type = isl_obj_union_pw_qpolynomial;
1797 } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
1798 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
1799 obj.type = isl_obj_union_pw_qpolynomial_fold;
1800 } else
1801 isl_assert(ctx, 0, goto error);
1802 return obj;
1803 error:
1804 obj.type->free(obj.v);
1805 obj.type = isl_obj_none;
1806 return obj;
1807 }
1808
1809 static struct isl_obj obj_add(struct isl_ctx *ctx,
1810 struct isl_obj obj1, struct isl_obj obj2)
1811 {
1812 if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
1813 obj1 = to_union(ctx, obj1);
1814 if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
1815 obj2 = to_union(ctx, obj2);
1816 if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
1817 obj1 = to_union(ctx, obj1);
1818 if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
1819 obj2 = to_union(ctx, obj2);
1820 if (obj1.type == isl_obj_pw_qpolynomial &&
1821 obj2.type == isl_obj_union_pw_qpolynomial)
1822 obj1 = to_union(ctx, obj1);
1823 if (obj1.type == isl_obj_union_pw_qpolynomial &&
1824 obj2.type == isl_obj_pw_qpolynomial)
1825 obj2 = to_union(ctx, obj2);
1826 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1827 obj2.type == isl_obj_union_pw_qpolynomial_fold)
1828 obj1 = to_union(ctx, obj1);
1829 if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
1830 obj2.type == isl_obj_pw_qpolynomial_fold)
1831 obj2 = to_union(ctx, obj2);
1832 isl_assert(ctx, obj1.type == obj2.type, goto error);
1833 if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) {
1834 obj1 = to_union(ctx, obj1);
1835 obj2 = to_union(ctx, obj2);
1836 }
1837 if (obj1.type == isl_obj_set && !isl_set_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 &&
1842 !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) {
1843 obj1 = to_union(ctx, obj1);
1844 obj2 = to_union(ctx, obj2);
1845 }
1846 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1847 !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) {
1848 obj1 = to_union(ctx, obj1);
1849 obj2 = to_union(ctx, obj2);
1850 }
1851 obj1.v = obj1.type->add(obj1.v, obj2.v);
1852 return obj1;
1853 error:
1854 obj1.type->free(obj1.v);
1855 obj2.type->free(obj2.v);
1856 obj1.type = isl_obj_none;
1857 obj1.v = NULL;
1858 return obj1;
1859 }
1860
1861 static struct isl_obj obj_read(struct isl_stream *s)
1862 {
1863 isl_map *map = NULL;
1864 struct isl_token *tok;
1865 struct vars *v = NULL;
1866 struct isl_obj obj = { isl_obj_set, NULL };
1867
1868 tok = next_token(s);
1869 if (!tok) {
1870 isl_stream_error(s, NULL, "unexpected EOF");
1871 goto error;
1872 }
1873 if (tok->type == ISL_TOKEN_VALUE) {
1874 struct isl_token *tok2;
1875 struct isl_map *map;
1876
1877 tok2 = isl_stream_next_token(s);
1878 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
1879 isl_int_is_neg(tok2->u.v)) {
1880 if (tok2)
1881 isl_stream_push_token(s, tok2);
1882 obj.type = isl_obj_int;
1883 obj.v = isl_int_obj_alloc(s->ctx, tok->u.v);
1884 isl_token_free(tok);
1885 return obj;
1886 }
1887 isl_stream_push_token(s, tok2);
1888 isl_stream_push_token(s, tok);
1889 map = map_read_polylib(s);
1890 if (!map)
1891 goto error;
1892 if (isl_map_may_be_set(map))
1893 obj.v = isl_map_range(map);
1894 else {
1895 obj.type = isl_obj_map;
1896 obj.v = map;
1897 }
1898 return obj;
1899 }
1900 v = vars_new(s->ctx);
1901 if (!v) {
1902 isl_stream_push_token(s, tok);
1903 goto error;
1904 }
1905 map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));
1906 if (tok->type == '[') {
1907 isl_stream_push_token(s, tok);
1908 map = read_tuple(s, map, isl_dim_param, v);
1909 if (!map)
1910 goto error;
1911 tok = isl_stream_next_token(s);
1912 if (!tok || tok->type != ISL_TOKEN_TO) {
1913 isl_stream_error(s, tok, "expecting '->'");
1914 if (tok)
1915 isl_stream_push_token(s, tok);
1916 goto error;
1917 }
1918 isl_token_free(tok);
1919 tok = isl_stream_next_token(s);
1920 }
1921 if (!tok || tok->type != '{') {
1922 isl_stream_error(s, tok, "expecting '{'");
1923 if (tok)
1924 isl_stream_push_token(s, tok);
1925 goto error;
1926 }
1927 isl_token_free(tok);
1928
1929 tok = isl_stream_next_token(s);
1930 if (!tok)
1931 ;
1932 else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
1933 isl_token_free(tok);
1934 if (isl_stream_eat(s, '='))
1935 goto error;
1936 map = read_tuple(s, map, isl_dim_param, v);
1937 if (!map)
1938 goto error;
1939 } else if (tok->type == '}') {
1940 obj.type = isl_obj_union_set;
1941 obj.v = isl_union_set_empty(isl_map_get_space(map));
1942 isl_token_free(tok);
1943 goto done;
1944 } else
1945 isl_stream_push_token(s, tok);
1946
1947 for (;;) {
1948 struct isl_obj o;
1949 tok = NULL;
1950 o = obj_read_body(s, isl_map_copy(map), v);
1951 if (o.type == isl_obj_none || !o.v)
1952 goto error;
1953 if (!obj.v)
1954 obj = o;
1955 else {
1956 obj = obj_add(s->ctx, obj, o);
1957 if (obj.type == isl_obj_none || !obj.v)
1958 goto error;
1959 }
1960 tok = isl_stream_next_token(s);
1961 if (!tok || tok->type != ';')
1962 break;
1963 isl_token_free(tok);
1964 if (isl_stream_next_token_is(s, '}')) {
1965 tok = isl_stream_next_token(s);
1966 break;
1967 }
1968 }
1969
1970 if (tok && tok->type == '}') {
1971 isl_token_free(tok);
1972 } else {
1973 isl_stream_error(s, tok, "unexpected isl_token");
1974 if (tok)
1975 isl_token_free(tok);
1976 goto error;
1977 }
1978 done:
1979 vars_free(v);
1980 isl_map_free(map);
1981
1982 return obj;
1983 error:
1984 isl_map_free(map);
1985 obj.type->free(obj.v);
1986 if (v)
1987 vars_free(v);
1988 obj.v = NULL;
1989 return obj;
1990 }
1991
1992 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
1993 {
1994 return obj_read(s);
1995 }
1996
1997 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s)
1998 {
1999 struct isl_obj obj;
2000
2001 obj = obj_read(s);
2002 if (obj.v)
2003 isl_assert(s->ctx, obj.type == isl_obj_map ||
2004 obj.type == isl_obj_set, goto error);
2005
2006 if (obj.type == isl_obj_set)
2007 obj.v = isl_map_from_range(obj.v);
2008
2009 return obj.v;
2010 error:
2011 obj.type->free(obj.v);
2012 return NULL;
2013 }
2014
2015 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s)
2016 {
2017 struct isl_obj obj;
2018
2019 obj = obj_read(s);
2020 if (obj.v) {
2021 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) {
2022 obj.v = isl_map_range(obj.v);
2023 obj.type = isl_obj_set;
2024 }
2025 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2026 }
2027
2028 return obj.v;
2029 error:
2030 obj.type->free(obj.v);
2031 return NULL;
2032 }
2033
2034 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2035 {
2036 struct isl_obj obj;
2037
2038 obj = obj_read(s);
2039 if (obj.type == isl_obj_map) {
2040 obj.type = isl_obj_union_map;
2041 obj.v = isl_union_map_from_map(obj.v);
2042 }
2043 if (obj.type == isl_obj_set) {
2044 obj.type = isl_obj_union_set;
2045 obj.v = isl_union_set_from_set(obj.v);
2046 }
2047 if (obj.v)
2048 isl_assert(s->ctx, obj.type == isl_obj_union_map ||
2049 obj.type == isl_obj_union_set, goto error);
2050
2051 return obj.v;
2052 error:
2053 obj.type->free(obj.v);
2054 return NULL;
2055 }
2056
2057 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2058 {
2059 struct isl_obj obj;
2060
2061 obj = obj_read(s);
2062 if (obj.type == isl_obj_set) {
2063 obj.type = isl_obj_union_set;
2064 obj.v = isl_union_set_from_set(obj.v);
2065 }
2066 if (obj.v)
2067 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2068
2069 return obj.v;
2070 error:
2071 obj.type->free(obj.v);
2072 return NULL;
2073 }
2074
2075 static __isl_give isl_basic_map *basic_map_read(struct isl_stream *s)
2076 {
2077 struct isl_obj obj;
2078 struct isl_map *map;
2079 struct isl_basic_map *bmap;
2080
2081 obj = obj_read(s);
2082 map = obj.v;
2083 if (!map)
2084 return NULL;
2085
2086 isl_assert(map->ctx, map->n <= 1, goto error);
2087
2088 if (map->n == 0)
2089 bmap = isl_basic_map_empty_like_map(map);
2090 else
2091 bmap = isl_basic_map_copy(map->p[0]);
2092
2093 isl_map_free(map);
2094
2095 return bmap;
2096 error:
2097 isl_map_free(map);
2098 return NULL;
2099 }
2100
2101 static __isl_give isl_basic_set *basic_set_read(struct isl_stream *s)
2102 {
2103 isl_basic_map *bmap;
2104 bmap = basic_map_read(s);
2105 if (!bmap)
2106 return NULL;
2107 if (!isl_basic_map_may_be_set(bmap))
2108 isl_die(s->ctx, isl_error_invalid,
2109 "input is not a set", goto error);
2110 return isl_basic_map_range(bmap);
2111 error:
2112 isl_basic_map_free(bmap);
2113 return NULL;
2114 }
2115
2116 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2117 FILE *input)
2118 {
2119 struct isl_basic_map *bmap;
2120 struct isl_stream *s = isl_stream_new_file(ctx, input);
2121 if (!s)
2122 return NULL;
2123 bmap = basic_map_read(s);
2124 isl_stream_free(s);
2125 return bmap;
2126 }
2127
2128 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2129 FILE *input)
2130 {
2131 isl_basic_set *bset;
2132 struct isl_stream *s = isl_stream_new_file(ctx, input);
2133 if (!s)
2134 return NULL;
2135 bset = basic_set_read(s);
2136 isl_stream_free(s);
2137 return bset;
2138 }
2139
2140 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2141 const char *str)
2142 {
2143 struct isl_basic_map *bmap;
2144 struct isl_stream *s = isl_stream_new_str(ctx, str);
2145 if (!s)
2146 return NULL;
2147 bmap = basic_map_read(s);
2148 isl_stream_free(s);
2149 return bmap;
2150 }
2151
2152 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2153 const char *str)
2154 {
2155 isl_basic_set *bset;
2156 struct isl_stream *s = isl_stream_new_str(ctx, str);
2157 if (!s)
2158 return NULL;
2159 bset = basic_set_read(s);
2160 isl_stream_free(s);
2161 return bset;
2162 }
2163
2164 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2165 FILE *input)
2166 {
2167 struct isl_map *map;
2168 struct isl_stream *s = isl_stream_new_file(ctx, input);
2169 if (!s)
2170 return NULL;
2171 map = isl_stream_read_map(s);
2172 isl_stream_free(s);
2173 return map;
2174 }
2175
2176 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2177 const char *str)
2178 {
2179 struct isl_map *map;
2180 struct isl_stream *s = isl_stream_new_str(ctx, str);
2181 if (!s)
2182 return NULL;
2183 map = isl_stream_read_map(s);
2184 isl_stream_free(s);
2185 return map;
2186 }
2187
2188 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2189 FILE *input)
2190 {
2191 isl_set *set;
2192 struct isl_stream *s = isl_stream_new_file(ctx, input);
2193 if (!s)
2194 return NULL;
2195 set = isl_stream_read_set(s);
2196 isl_stream_free(s);
2197 return set;
2198 }
2199
2200 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2201 const char *str)
2202 {
2203 isl_set *set;
2204 struct isl_stream *s = isl_stream_new_str(ctx, str);
2205 if (!s)
2206 return NULL;
2207 set = isl_stream_read_set(s);
2208 isl_stream_free(s);
2209 return set;
2210 }
2211
2212 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2213 FILE *input)
2214 {
2215 isl_union_map *umap;
2216 struct isl_stream *s = isl_stream_new_file(ctx, input);
2217 if (!s)
2218 return NULL;
2219 umap = isl_stream_read_union_map(s);
2220 isl_stream_free(s);
2221 return umap;
2222 }
2223
2224 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2225 const char *str)
2226 {
2227 isl_union_map *umap;
2228 struct isl_stream *s = isl_stream_new_str(ctx, str);
2229 if (!s)
2230 return NULL;
2231 umap = isl_stream_read_union_map(s);
2232 isl_stream_free(s);
2233 return umap;
2234 }
2235
2236 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2237 FILE *input)
2238 {
2239 isl_union_set *uset;
2240 struct isl_stream *s = isl_stream_new_file(ctx, input);
2241 if (!s)
2242 return NULL;
2243 uset = isl_stream_read_union_set(s);
2244 isl_stream_free(s);
2245 return uset;
2246 }
2247
2248 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2249 const char *str)
2250 {
2251 isl_union_set *uset;
2252 struct isl_stream *s = isl_stream_new_str(ctx, str);
2253 if (!s)
2254 return NULL;
2255 uset = isl_stream_read_union_set(s);
2256 isl_stream_free(s);
2257 return uset;
2258 }
2259
2260 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2261 {
2262 struct isl_vec *vec = NULL;
2263 struct isl_token *tok;
2264 unsigned size;
2265 int j;
2266
2267 tok = isl_stream_next_token(s);
2268 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2269 isl_stream_error(s, tok, "expecting vector length");
2270 goto error;
2271 }
2272
2273 size = isl_int_get_si(tok->u.v);
2274 isl_token_free(tok);
2275
2276 vec = isl_vec_alloc(s->ctx, size);
2277
2278 for (j = 0; j < size; ++j) {
2279 tok = isl_stream_next_token(s);
2280 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2281 isl_stream_error(s, tok, "expecting constant value");
2282 goto error;
2283 }
2284 isl_int_set(vec->el[j], tok->u.v);
2285 isl_token_free(tok);
2286 }
2287
2288 return vec;
2289 error:
2290 isl_token_free(tok);
2291 isl_vec_free(vec);
2292 return NULL;
2293 }
2294
2295 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2296 {
2297 return isl_vec_read_polylib(s);
2298 }
2299
2300 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2301 {
2302 isl_vec *v;
2303 struct isl_stream *s = isl_stream_new_file(ctx, input);
2304 if (!s)
2305 return NULL;
2306 v = vec_read(s);
2307 isl_stream_free(s);
2308 return v;
2309 }
2310
2311 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2312 struct isl_stream *s)
2313 {
2314 struct isl_obj obj;
2315
2316 obj = obj_read(s);
2317 if (obj.v)
2318 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2319 goto error);
2320
2321 return obj.v;
2322 error:
2323 obj.type->free(obj.v);
2324 return NULL;
2325 }
2326
2327 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2328 const char *str)
2329 {
2330 isl_pw_qpolynomial *pwqp;
2331 struct isl_stream *s = isl_stream_new_str(ctx, str);
2332 if (!s)
2333 return NULL;
2334 pwqp = isl_stream_read_pw_qpolynomial(s);
2335 isl_stream_free(s);
2336 return pwqp;
2337 }
2338
2339 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
2340 FILE *input)
2341 {
2342 isl_pw_qpolynomial *pwqp;
2343 struct isl_stream *s = isl_stream_new_file(ctx, input);
2344 if (!s)
2345 return NULL;
2346 pwqp = isl_stream_read_pw_qpolynomial(s);
2347 isl_stream_free(s);
2348 return pwqp;
2349 }
2350
2351 /* Read an affine expression from "s" with domain (space) "dom".
2352 * We call accept_affine to parse a possibly piecewise affine expression
2353 * and then check that the result is a single affine expression on
2354 * a universe domain.
2355 */
2356 static __isl_give isl_aff *read_aff_with_dom(struct isl_stream *s,
2357 __isl_take isl_set *dom, struct vars *v)
2358 {
2359 isl_aff *aff = NULL;
2360 isl_pw_aff *pwaff = NULL;
2361
2362 if (!isl_set_plain_is_universe(dom))
2363 isl_die(s->ctx, isl_error_invalid,
2364 "expecting universe domain", goto error);
2365
2366 if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2367 goto error;
2368
2369 if (isl_stream_eat(s, '['))
2370 goto error;
2371
2372 pwaff = accept_affine(s, isl_set_get_space(dom), v);
2373
2374 if (isl_stream_eat(s, ']'))
2375 goto error;
2376 if (isl_stream_eat(s, '}'))
2377 goto error;
2378
2379 if (!pwaff)
2380 goto error;
2381
2382 if (pwaff->n != 1)
2383 isl_die(s->ctx, isl_error_invalid,
2384 "expecting single affine expression", goto error);
2385 if (!isl_set_plain_is_universe(pwaff->p[0].set))
2386 isl_die(s->ctx, isl_error_invalid,
2387 "expecting universe domain", goto error);
2388
2389 aff = isl_aff_copy(pwaff->p[0].aff);
2390
2391 vars_free(v);
2392 isl_pw_aff_free(pwaff);
2393 isl_set_free(dom);
2394 return aff;
2395 error:
2396 vars_free(v);
2397 isl_pw_aff_free(pwaff);
2398 isl_set_free(dom);
2399 return NULL;
2400 }
2401
2402 /* Is the next token an identifer not in "v"?
2403 */
2404 static int next_is_fresh_ident(struct isl_stream *s, struct vars *v)
2405 {
2406 int n = v->n;
2407 int fresh;
2408 struct isl_token *tok;
2409
2410 tok = isl_stream_next_token(s);
2411 if (!tok)
2412 return 0;
2413 fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n;
2414 isl_stream_push_token(s, tok);
2415
2416 vars_drop(v, v->n - n);
2417
2418 return fresh;
2419 }
2420
2421 /* First read the domain of the affine expression, which may be
2422 * a parameter space or a set.
2423 * The tricky part is that we don't know if the domain is a set or not,
2424 * so when we are trying to read the domain, we may actually be reading
2425 * the affine expression itself (defined on a parameter domains)
2426 * If the tuple we are reading is named, we assume it's the domain.
2427 * Also, if inside the tuple, the first thing we find is a nested tuple
2428 * or a new identifier, we again assume it's the domain.
2429 * Otherwise, we assume we are reading an affine expression.
2430 */
2431 static __isl_give isl_set *read_aff_domain(struct isl_stream *s,
2432 __isl_take isl_set *dom, struct vars *v)
2433 {
2434 struct isl_token *tok;
2435
2436 tok = isl_stream_next_token(s);
2437 if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
2438 isl_stream_push_token(s, tok);
2439 return read_tuple(s, dom, isl_dim_set, v);
2440 }
2441 if (!tok || tok->type != '[') {
2442 isl_stream_error(s, tok, "expecting '['");
2443 goto error;
2444 }
2445 if (next_is_tuple(s) || next_is_fresh_ident(s, v)) {
2446 isl_stream_push_token(s, tok);
2447 dom = read_tuple(s, dom, isl_dim_set, v);
2448 } else
2449 isl_stream_push_token(s, tok);
2450
2451 return dom;
2452 error:
2453 if (tok)
2454 isl_stream_push_token(s, tok);
2455 vars_free(v);
2456 isl_set_free(dom);
2457 return NULL;
2458 }
2459
2460 /* Read an affine expression from "s".
2461 * We first read the domain of the affine expression, which may be
2462 * a parameter space or a set, and then call read_aff_with_dom.
2463 */
2464 __isl_give isl_aff *isl_stream_read_aff(struct isl_stream *s)
2465 {
2466 struct vars *v;
2467 isl_set *dom = NULL;
2468
2469 v = vars_new(s->ctx);
2470 if (!v)
2471 return NULL;
2472
2473 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2474 if (next_is_tuple(s)) {
2475 dom = read_tuple(s, dom, isl_dim_param, v);
2476 if (isl_stream_eat(s, ISL_TOKEN_TO))
2477 goto error;
2478 }
2479 if (isl_stream_eat(s, '{'))
2480 goto error;
2481
2482 dom = read_aff_domain(s, dom, v);
2483 return read_aff_with_dom(s, dom, v);
2484 error:
2485 vars_free(v);
2486 isl_set_free(dom);
2487 return NULL;
2488 }
2489
2490 /* Read a piecewise affine expression from "s" with domain (space) "dom".
2491 */
2492 static __isl_give isl_pw_aff *read_pw_aff_with_dom(struct isl_stream *s,
2493 __isl_take isl_set *dom, struct vars *v)
2494 {
2495 isl_pw_aff *pwaff = NULL;
2496
2497 if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2498 goto error;
2499
2500 if (isl_stream_eat(s, '['))
2501 goto error;
2502
2503 pwaff = accept_affine(s, isl_set_get_space(dom), v);
2504
2505 if (isl_stream_eat(s, ']'))
2506 goto error;
2507
2508 dom = read_optional_disjuncts(s, dom, v);
2509 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2510
2511 return pwaff;
2512 error:
2513 isl_set_free(dom);
2514 isl_pw_aff_free(pwaff);
2515 return NULL;
2516 }
2517
2518 __isl_give isl_pw_aff *isl_stream_read_pw_aff(struct isl_stream *s)
2519 {
2520 struct vars *v;
2521 isl_set *dom = NULL;
2522 isl_set *aff_dom;
2523 isl_pw_aff *pa = NULL;
2524 int n;
2525
2526 v = vars_new(s->ctx);
2527 if (!v)
2528 return NULL;
2529
2530 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2531 if (next_is_tuple(s)) {
2532 dom = read_tuple(s, dom, isl_dim_param, v);
2533 if (isl_stream_eat(s, ISL_TOKEN_TO))
2534 goto error;
2535 }
2536 if (isl_stream_eat(s, '{'))
2537 goto error;
2538
2539 n = v->n;
2540 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2541 pa = read_pw_aff_with_dom(s, aff_dom, v);
2542 vars_drop(v, v->n - n);
2543
2544 while (isl_stream_eat_if_available(s, ';')) {
2545 isl_pw_aff *pa_i;
2546
2547 n = v->n;
2548 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2549 pa_i = read_pw_aff_with_dom(s, aff_dom, v);
2550 vars_drop(v, v->n - n);
2551
2552 pa = isl_pw_aff_union_add(pa, pa_i);
2553 }
2554
2555 if (isl_stream_eat(s, '}'))
2556 goto error;
2557
2558 vars_free(v);
2559 isl_set_free(dom);
2560 return pa;
2561 error:
2562 vars_free(v);
2563 isl_set_free(dom);
2564 isl_pw_aff_free(pa);
2565 return NULL;
2566 }
2567
2568 __isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str)
2569 {
2570 isl_aff *aff;
2571 struct isl_stream *s = isl_stream_new_str(ctx, str);
2572 if (!s)
2573 return NULL;
2574 aff = isl_stream_read_aff(s);
2575 isl_stream_free(s);
2576 return aff;
2577 }
2578
2579 __isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str)
2580 {
2581 isl_pw_aff *pa;
2582 struct isl_stream *s = isl_stream_new_str(ctx, str);
2583 if (!s)
2584 return NULL;
2585 pa = isl_stream_read_pw_aff(s);
2586 isl_stream_free(s);
2587 return pa;
2588 }
2589
2590 /* Read an isl_pw_multi_aff from "s".
2591 * We currently read a generic object and if it turns out to be a set or
2592 * a map, we convert that to an isl_pw_multi_aff.
2593 * It would be more efficient if we were to construct the isl_pw_multi_aff
2594 * directly.
2595 */
2596 __isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(struct isl_stream *s)
2597 {
2598 struct isl_obj obj;
2599
2600 obj = obj_read(s);
2601 if (!obj.v)
2602 return NULL;
2603
2604 if (obj.type == isl_obj_map)
2605 return isl_pw_multi_aff_from_map(obj.v);
2606 if (obj.type == isl_obj_set)
2607 return isl_pw_multi_aff_from_set(obj.v);
2608
2609 obj.type->free(obj.v);
2610 isl_die(s->ctx, isl_error_invalid, "unexpected object type",
2611 return NULL);
2612 }
2613
2614 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx,
2615 const char *str)
2616 {
2617 isl_pw_multi_aff *pma;
2618 struct isl_stream *s = isl_stream_new_str(ctx, str);
2619 if (!s)
2620 return NULL;
2621 pma = isl_stream_read_pw_multi_aff(s);
2622 isl_stream_free(s);
2623 return pma;
2624 }
2625
2626 /* Read a multi-affine expression from "s".
2627 * We call isl_stream_read_pw_multi_aff to parse a possibly piecewise
2628 * multi-affine expression and then check that the result is
2629 * a single multi-affine expression on a universe domain.
2630 */
2631 __isl_give isl_multi_aff *isl_stream_read_multi_aff(struct isl_stream *s)
2632 {
2633 isl_pw_multi_aff *pma;
2634 isl_multi_aff *maff;
2635
2636 pma = isl_stream_read_pw_multi_aff(s);
2637 if (!pma)
2638 return NULL;
2639 if (pma->n != 1)
2640 isl_die(s->ctx, isl_error_invalid,
2641 "expecting single list of affine expressions",
2642 return isl_pw_multi_aff_free(pma));
2643 if (!isl_set_plain_is_universe(pma->p[0].set))
2644 isl_die(s->ctx, isl_error_invalid, "expecting universe domain",
2645 return isl_pw_multi_aff_free(pma));
2646 maff = isl_multi_aff_copy(pma->p[0].maff);
2647 isl_pw_multi_aff_free(pma);
2648 return maff;
2649 }
2650
2651 __isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx,
2652 const char *str)
2653 {
2654 isl_multi_aff *maff;
2655 struct isl_stream *s = isl_stream_new_str(ctx, str);
2656 if (!s)
2657 return NULL;
2658 maff = isl_stream_read_multi_aff(s);
2659 isl_stream_free(s);
2660 return maff;
2661 }
2662
2663 __isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial(
2664 struct isl_stream *s)
2665 {
2666 struct isl_obj obj;
2667
2668 obj = obj_read(s);
2669 if (obj.type == isl_obj_pw_qpolynomial) {
2670 obj.type = isl_obj_union_pw_qpolynomial;
2671 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2672 }
2673 if (obj.v)
2674 isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial,
2675 goto error);
2676
2677 return obj.v;
2678 error:
2679 obj.type->free(obj.v);
2680 return NULL;
2681 }
2682
2683 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str(
2684 isl_ctx *ctx, const char *str)
2685 {
2686 isl_union_pw_qpolynomial *upwqp;
2687 struct isl_stream *s = isl_stream_new_str(ctx, str);
2688 if (!s)
2689 return NULL;
2690 upwqp = isl_stream_read_union_pw_qpolynomial(s);
2691 isl_stream_free(s);
2692 return upwqp;
2693 }
Integer set library