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