?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_stream_read_map: accept piecewise affine expressions inside tuples
[isl.git] / isl_input.c
blob9f035886e592b7d260f0f4a9854bcc94c22aa085
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 * Copyright 2012-2013 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 /* Set *line and *col to those of the next token, if any.
706 */
707 static void set_current_line_col(struct isl_stream *s, int *line, int *col)
708 {
709 struct isl_token *tok;
710
711 tok = isl_stream_next_token(s);
712 if (!tok)
713 return;
714
715 *line = tok->line;
716 *col = tok->col;
717 isl_stream_push_token(s, tok);
718 }
719
720 /* Push a token encapsulating "pa" onto "s", with the given
721 * line and column.
722 */
723 static int push_aff(struct isl_stream *s, int line, int col,
724 __isl_take isl_pw_aff *pa)
725 {
726 struct isl_token *tok;
727
728 tok = isl_token_new(s->ctx, line, col, 0);
729 if (!tok)
730 goto error;
731 tok->type = ISL_TOKEN_AFF;
732 tok->u.pwaff = pa;
733 isl_stream_push_token(s, tok);
734
735 return 0;
736 error:
737 isl_pw_aff_free(pa);
738 return -1;
739 }
740
741 /* Accept an affine expression that may involve ternary operators.
742 * We first read an affine expression.
743 * If it is not followed by a comparison operator, we simply return it.
744 * Otherwise, we assume the affine expression is part of the first
745 * argument of a ternary operator and try to parse that.
746 */
747 static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s,
748 __isl_take isl_space *dim, struct vars *v, int rational)
749 {
750 isl_space *space;
751 isl_map *cond;
752 isl_pw_aff *pwaff;
753 struct isl_token *tok;
754 int line = -1, col = -1;
755 int is_comp;
756
757 set_current_line_col(s, &line, &col);
758
759 pwaff = accept_affine(s, dim, v);
760 if (rational)
761 pwaff = isl_pw_aff_set_rational(pwaff);
762 if (!pwaff)
763 return NULL;
764
765 tok = isl_stream_next_token(s);
766 if (!tok)
767 return isl_pw_aff_free(pwaff);
768
769 is_comp = is_comparator(tok);
770 isl_stream_push_token(s, tok);
771 if (!is_comp)
772 return pwaff;
773
774 space = isl_pw_aff_get_domain_space(pwaff);
775 cond = isl_map_universe(isl_space_unwrap(space));
776
777 if (push_aff(s, line, col, pwaff) < 0)
778 return NULL;
779
780 cond = read_formula(s, v, cond, rational);
781
782 return accept_ternary(s, cond, v, rational);
783 }
784
785 static __isl_give isl_map *read_var_def(struct isl_stream *s,
786 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
787 int rational)
788 {
789 isl_pw_aff *def;
790 int pos;
791 isl_map *def_map;
792
793 if (type == isl_dim_param)
794 pos = isl_map_dim(map, isl_dim_param);
795 else {
796 pos = isl_map_dim(map, isl_dim_in);
797 if (type == isl_dim_out)
798 pos += isl_map_dim(map, isl_dim_out);
799 type = isl_dim_in;
800 }
801 --pos;
802
803 def = accept_extended_affine(s, isl_space_wrap(isl_map_get_space(map)),
804 v, rational);
805 def_map = isl_map_from_pw_aff(def);
806 def_map = isl_map_equate(def_map, type, pos, isl_dim_out, 0);
807 def_map = isl_set_unwrap(isl_map_domain(def_map));
808
809 map = isl_map_intersect(map, def_map);
810
811 return map;
812 }
813
814 static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s,
815 __isl_take isl_space *dim, struct vars *v)
816 {
817 isl_pw_aff *pwaff;
818 isl_pw_aff_list *list;
819 struct isl_token *tok = NULL;
820
821 pwaff = accept_affine(s, isl_space_copy(dim), v);
822 list = isl_pw_aff_list_from_pw_aff(pwaff);
823 if (!list)
824 goto error;
825
826 for (;;) {
827 tok = isl_stream_next_token(s);
828 if (!tok) {
829 isl_stream_error(s, NULL, "unexpected EOF");
830 goto error;
831 }
832 if (tok->type != ',') {
833 isl_stream_push_token(s, tok);
834 break;
835 }
836 isl_token_free(tok);
837
838 pwaff = accept_affine(s, isl_space_copy(dim), v);
839 list = isl_pw_aff_list_concat(list,
840 isl_pw_aff_list_from_pw_aff(pwaff));
841 if (!list)
842 goto error;
843 }
844
845 isl_space_free(dim);
846 return list;
847 error:
848 isl_space_free(dim);
849 isl_pw_aff_list_free(list);
850 return NULL;
851 }
852
853 static __isl_give isl_map *read_defined_var_list(struct isl_stream *s,
854 struct vars *v, __isl_take isl_map *map, int rational)
855 {
856 struct isl_token *tok;
857
858 while ((tok = isl_stream_next_token(s)) != NULL) {
859 int p;
860 int n = v->n;
861
862 if (tok->type != ISL_TOKEN_IDENT)
863 break;
864
865 p = vars_pos(v, tok->u.s, -1);
866 if (p < 0)
867 goto error;
868 if (p < n) {
869 isl_stream_error(s, tok, "expecting unique identifier");
870 goto error;
871 }
872
873 map = isl_map_add_dims(map, isl_dim_out, 1);
874
875 isl_token_free(tok);
876 tok = isl_stream_next_token(s);
877 if (tok && tok->type == '=') {
878 isl_token_free(tok);
879 map = read_var_def(s, map, isl_dim_out, v, rational);
880 tok = isl_stream_next_token(s);
881 }
882
883 if (!tok || tok->type != ',')
884 break;
885
886 isl_token_free(tok);
887 }
888 if (tok)
889 isl_stream_push_token(s, tok);
890
891 return map;
892 error:
893 isl_token_free(tok);
894 isl_map_free(map);
895 return NULL;
896 }
897
898 static int next_is_tuple(struct isl_stream *s)
899 {
900 struct isl_token *tok;
901 int is_tuple;
902
903 tok = isl_stream_next_token(s);
904 if (!tok)
905 return 0;
906 if (tok->type == '[') {
907 isl_stream_push_token(s, tok);
908 return 1;
909 }
910 if (tok->type != ISL_TOKEN_IDENT && !tok->is_keyword) {
911 isl_stream_push_token(s, tok);
912 return 0;
913 }
914
915 is_tuple = isl_stream_next_token_is(s, '[');
916
917 isl_stream_push_token(s, tok);
918
919 return is_tuple;
920 }
921
922 /* Allocate an initial tuple with zero dimensions and an anonymous,
923 * unstructured space.
924 * A tuple is represented as an isl_multi_pw_aff.
925 * The range space is the space of the tuple.
926 * The domain space is an anonymous space
927 * with a dimension for each variable in the set of variables in "v".
928 * If a given dimension is not defined in terms of earlier dimensions in
929 * the input, then the corresponding isl_pw_aff is set equal to one time
930 * the variable corresponding to the dimension being defined.
931 */
932 static __isl_give isl_multi_pw_aff *tuple_alloc(struct vars *v)
933 {
934 return isl_multi_pw_aff_alloc(isl_space_alloc(v->ctx, 0, v->n, 0));
935 }
936
937 /* Is "pa" an expression in term of earlier dimensions?
938 * The alternative is that the dimension is defined to be equal to itself,
939 * meaning that it has a universe domain and an expression that depends
940 * on itself. "i" is the position of the expression in a sequence
941 * of "n" expressions. The final dimensions of "pa" correspond to
942 * these "n" expressions.
943 */
944 static int pw_aff_is_expr(__isl_keep isl_pw_aff *pa, int i, int n)
945 {
946 isl_aff *aff;
947
948 if (!pa)
949 return -1;
950 if (pa->n != 1)
951 return 1;
952 if (!isl_set_plain_is_universe(pa->p[0].set))
953 return 1;
954
955 aff = pa->p[0].aff;
956 if (isl_int_is_zero(aff->v->el[aff->v->size - n + i]))
957 return 1;
958 return 0;
959 }
960
961 /* Does the tuple contain any dimensions that are defined
962 * in terms of earlier dimensions?
963 */
964 static int tuple_has_expr(__isl_keep isl_multi_pw_aff *tuple)
965 {
966 int i, n;
967 int has_expr = 0;
968 isl_pw_aff *pa;
969
970 if (!tuple)
971 return -1;
972 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
973 for (i = 0; i < n; ++i) {
974 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
975 has_expr = pw_aff_is_expr(pa, i, n);
976 isl_pw_aff_free(pa);
977 if (has_expr < 0 || has_expr)
978 break;
979 }
980
981 return has_expr;
982 }
983
984 /* Add a dimension to the given tuple.
985 * The dimension is initially undefined, so it is encoded
986 * as one times itself.
987 */
988 static __isl_give isl_multi_pw_aff *tuple_add_dim(
989 __isl_take isl_multi_pw_aff *tuple, struct vars *v)
990 {
991 isl_space *space;
992 isl_aff *aff;
993 isl_pw_aff *pa;
994
995 tuple = isl_multi_pw_aff_add_dims(tuple, isl_dim_in, 1);
996 space = isl_multi_pw_aff_get_domain_space(tuple);
997 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
998 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, v->n, 1);
999 pa = isl_pw_aff_from_aff(aff);
1000 tuple = isl_multi_pw_aff_flat_range_product(tuple,
1001 isl_multi_pw_aff_from_pw_aff(pa));
1002
1003 return tuple;
1004 }
1005
1006 /* Set the name of dimension "pos" in "tuple" to "name".
1007 * During printing, we add primes if the same name appears more than once
1008 * to distinguish the occurrences. Here, we remove those primes from "name"
1009 * before setting the name of the dimension.
1010 */
1011 static __isl_give isl_multi_pw_aff *tuple_set_dim_name(
1012 __isl_take isl_multi_pw_aff *tuple, int pos, char *name)
1013 {
1014 char *prime;
1015
1016 if (!name)
1017 return tuple;
1018
1019 prime = strchr(name, '\'');
1020 if (prime)
1021 *prime = '\0';
1022 tuple = isl_multi_pw_aff_set_dim_name(tuple, isl_dim_set, pos, name);
1023 if (prime)
1024 *prime = '\'';
1025
1026 return tuple;
1027 }
1028
1029 /* Accept a piecewise affine expression.
1030 *
1031 * At the outer level, the piecewise affine expression may be of the form
1032 *
1033 * aff1 : condition1; aff2 : conditions2; ...
1034 *
1035 * or simply
1036 *
1037 * aff
1038 *
1039 * each of the affine expressions may in turn include ternary operators.
1040 *
1041 * There may be parentheses around some subexpression of "aff1"
1042 * around "aff1" itself, around "aff1 : condition1" and/or
1043 * around the entire piecewise affine expression.
1044 * We therefore remove the opening parenthesis (if any) from the stream
1045 * in case the closing parenthesis follows the colon, but if the closing
1046 * parenthesis is the first thing in the stream after the parsed affine
1047 * expression, we push the parsed expression onto the stream and parse
1048 * again in case the parentheses enclose some subexpression of "aff1".
1049 */
1050 static __isl_give isl_pw_aff *accept_piecewise_affine(struct isl_stream *s,
1051 __isl_take isl_space *space, struct vars *v, int rational)
1052 {
1053 isl_pw_aff *res;
1054 isl_space *res_space;
1055
1056 res_space = isl_space_from_domain(isl_space_copy(space));
1057 res_space = isl_space_add_dims(res_space, isl_dim_out, 1);
1058 res = isl_pw_aff_empty(res_space);
1059 do {
1060 isl_pw_aff *pa;
1061 int seen_paren;
1062 int line = -1, col = -1;
1063
1064 set_current_line_col(s, &line, &col);
1065 seen_paren = isl_stream_eat_if_available(s, '(');
1066 if (seen_paren)
1067 pa = accept_piecewise_affine(s, isl_space_copy(space),
1068 v, rational);
1069 else
1070 pa = accept_extended_affine(s, isl_space_copy(space),
1071 v, rational);
1072 if (seen_paren && isl_stream_eat_if_available(s, ')')) {
1073 seen_paren = 0;
1074 if (push_aff(s, line, col, pa) < 0)
1075 goto error;
1076 pa = accept_extended_affine(s, isl_space_copy(space),
1077 v, rational);
1078 }
1079 if (isl_stream_eat_if_available(s, ':')) {
1080 isl_space *dom_space;
1081 isl_set *dom;
1082
1083 dom_space = isl_pw_aff_get_domain_space(pa);
1084 dom = isl_set_universe(dom_space);
1085 dom = read_formula(s, v, dom, rational);
1086 pa = isl_pw_aff_intersect_domain(pa, dom);
1087 }
1088
1089 res = isl_pw_aff_union_add(res, pa);
1090
1091 if (seen_paren && isl_stream_eat(s, ')'))
1092 goto error;
1093 } while (isl_stream_eat_if_available(s, ';'));
1094
1095 isl_space_free(space);
1096
1097 return res;
1098 error:
1099 isl_space_free(space);
1100 return isl_pw_aff_free(res);
1101 }
1102
1103 /* Read an affine expression from "s" and replace the definition
1104 * of dimension "pos" in "tuple" by this expression.
1105 *
1106 * accept_extended_affine requires a wrapped space as input.
1107 * The domain space of "tuple", on the other hand is an anonymous space,
1108 * so we have to adjust the space of the isl_pw_aff before adding it
1109 * to "tuple".
1110 */
1111 static __isl_give isl_multi_pw_aff *read_tuple_var_def(struct isl_stream *s,
1112 __isl_take isl_multi_pw_aff *tuple, int pos, struct vars *v,
1113 int rational)
1114 {
1115 isl_space *space;
1116 isl_pw_aff *def;
1117
1118 space = isl_space_wrap(isl_space_alloc(s->ctx, 0, v->n, 0));
1119
1120 def = accept_piecewise_affine(s, space, v, rational);
1121
1122 space = isl_space_set_alloc(s->ctx, 0, v->n);
1123 def = isl_pw_aff_reset_domain_space(def, space);
1124 tuple = isl_multi_pw_aff_set_pw_aff(tuple, pos, def);
1125
1126 return tuple;
1127 }
1128
1129 /* Read a list of variables and/or affine expressions and return the list
1130 * as an isl_multi_pw_aff.
1131 * The elements in the list are separated by either "," or "][".
1132 * If "comma" is set then only "," is allowed.
1133 */
1134 static __isl_give isl_multi_pw_aff *read_tuple_var_list(struct isl_stream *s,
1135 struct vars *v, int rational, int comma)
1136 {
1137 int i = 0;
1138 struct isl_token *tok;
1139 isl_multi_pw_aff *res;
1140
1141 res = tuple_alloc(v);
1142
1143 if (isl_stream_next_token_is(s, ']'))
1144 return res;
1145
1146 while ((tok = next_token(s)) != NULL) {
1147 int new_name = 0;
1148
1149 res = tuple_add_dim(res, v);
1150
1151 if (tok->type == ISL_TOKEN_IDENT) {
1152 int n = v->n;
1153 int p = vars_pos(v, tok->u.s, -1);
1154 if (p < 0)
1155 goto error;
1156 new_name = p >= n;
1157 }
1158
1159 if (tok->type == '*') {
1160 if (vars_add_anon(v) < 0)
1161 goto error;
1162 isl_token_free(tok);
1163 } else if (new_name) {
1164 res = tuple_set_dim_name(res, i, v->v->name);
1165 isl_token_free(tok);
1166 if (isl_stream_eat_if_available(s, '='))
1167 res = read_tuple_var_def(s, res, i, v,
1168 rational);
1169 } else {
1170 isl_stream_push_token(s, tok);
1171 tok = NULL;
1172 if (vars_add_anon(v) < 0)
1173 goto error;
1174 res = read_tuple_var_def(s, res, i, v, rational);
1175 }
1176
1177 tok = isl_stream_next_token(s);
1178 if (!comma && tok && tok->type == ']' &&
1179 isl_stream_next_token_is(s, '[')) {
1180 isl_token_free(tok);
1181 tok = isl_stream_next_token(s);
1182 } else if (!tok || tok->type != ',')
1183 break;
1184
1185 isl_token_free(tok);
1186 i++;
1187 }
1188 if (tok)
1189 isl_stream_push_token(s, tok);
1190
1191 return res;
1192 error:
1193 isl_token_free(tok);
1194 return isl_multi_pw_aff_free(res);
1195 }
1196
1197 /* Read a tuple and represent it as an isl_multi_pw_aff. See tuple_alloc.
1198 */
1199 static __isl_give isl_multi_pw_aff *read_tuple(struct isl_stream *s,
1200 struct vars *v, int rational, int comma)
1201 {
1202 struct isl_token *tok;
1203 char *name = NULL;
1204 isl_multi_pw_aff *res = NULL;
1205
1206 tok = isl_stream_next_token(s);
1207 if (!tok)
1208 goto error;
1209 if (tok->type == ISL_TOKEN_IDENT || tok->is_keyword) {
1210 name = strdup(tok->u.s);
1211 isl_token_free(tok);
1212 if (!name)
1213 goto error;
1214 } else
1215 isl_stream_push_token(s, tok);
1216 if (isl_stream_eat(s, '['))
1217 goto error;
1218 if (next_is_tuple(s)) {
1219 isl_multi_pw_aff *out;
1220 int n;
1221 res = read_tuple(s, v, rational, comma);
1222 if (isl_stream_eat(s, ISL_TOKEN_TO))
1223 goto error;
1224 out = read_tuple(s, v, rational, comma);
1225 n = isl_multi_pw_aff_dim(out, isl_dim_out);
1226 res = isl_multi_pw_aff_add_dims(res, isl_dim_in, n);
1227 res = isl_multi_pw_aff_range_product(res, out);
1228 } else
1229 res = read_tuple_var_list(s, v, rational, comma);
1230 if (isl_stream_eat(s, ']'))
1231 goto error;
1232
1233 if (name) {
1234 res = isl_multi_pw_aff_set_tuple_name(res, isl_dim_out, name);
1235 free(name);
1236 }
1237
1238 return res;
1239 error:
1240 free(name);
1241 return isl_multi_pw_aff_free(res);
1242 }
1243
1244 /* Read a tuple from "s" and add it to "map".
1245 * The tuple is initially represented as an isl_multi_pw_aff.
1246 * We first create the appropriate space in "map" based on the range
1247 * space of this isl_multi_pw_aff. Then, we add equalities based
1248 * on the affine expressions. These live in an anonymous space,
1249 * however, so we first need to reset the space to that of "map".
1250 */
1251 static __isl_give isl_map *read_map_tuple(struct isl_stream *s,
1252 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
1253 int rational, int comma)
1254 {
1255 int i, n;
1256 isl_multi_pw_aff *tuple;
1257 isl_space *space = NULL;
1258
1259 tuple = read_tuple(s, v, rational, comma);
1260 if (!tuple)
1261 goto error;
1262
1263 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
1264 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
1265 if (!space)
1266 goto error;
1267
1268 if (type == isl_dim_param) {
1269 if (isl_space_has_tuple_name(space, isl_dim_set) ||
1270 isl_space_is_wrapping(space)) {
1271 isl_die(s->ctx, isl_error_invalid,
1272 "parameter tuples cannot be named or nested",
1273 goto error);
1274 }
1275 map = isl_map_add_dims(map, type, n);
1276 for (i = 0; i < n; ++i) {
1277 isl_id *id;
1278 if (!isl_space_has_dim_name(space, isl_dim_set, i))
1279 isl_die(s->ctx, isl_error_invalid,
1280 "parameters must be named",
1281 goto error);
1282 id = isl_space_get_dim_id(space, isl_dim_set, i);
1283 map = isl_map_set_dim_id(map, isl_dim_param, i, id);
1284 }
1285 } else if (type == isl_dim_in) {
1286 isl_set *set;
1287
1288 set = isl_set_universe(isl_space_copy(space));
1289 if (rational)
1290 set = isl_set_set_rational(set);
1291 set = isl_set_intersect_params(set, isl_map_params(map));
1292 map = isl_map_from_domain(set);
1293 } else {
1294 isl_set *set;
1295
1296 set = isl_set_universe(isl_space_copy(space));
1297 if (rational)
1298 set = isl_set_set_rational(set);
1299 map = isl_map_from_domain_and_range(isl_map_domain(map), set);
1300 }
1301
1302 for (i = 0; i < n; ++i) {
1303 isl_pw_aff *pa;
1304 isl_space *space;
1305 isl_aff *aff;
1306 isl_set *set;
1307 isl_map *map_i;
1308
1309 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
1310 space = isl_pw_aff_get_domain_space(pa);
1311 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1312 aff = isl_aff_add_coefficient_si(aff,
1313 isl_dim_in, v->n - n + i, -1);
1314 pa = isl_pw_aff_add(pa, isl_pw_aff_from_aff(aff));
1315 if (rational)
1316 pa = isl_pw_aff_set_rational(pa);
1317 set = isl_pw_aff_zero_set(pa);
1318 map_i = isl_map_from_range(set);
1319 map_i = isl_map_reset_space(map_i, isl_map_get_space(map));
1320 map = isl_map_intersect(map, map_i);
1321 }
1322
1323 isl_space_free(space);
1324 isl_multi_pw_aff_free(tuple);
1325 return map;
1326 error:
1327 isl_space_free(space);
1328 isl_multi_pw_aff_free(tuple);
1329 isl_map_free(map);
1330 return NULL;
1331 }
1332
1333 static __isl_give isl_set *construct_constraints(
1334 __isl_take isl_set *set, int type,
1335 __isl_keep isl_pw_aff_list *left, __isl_keep isl_pw_aff_list *right,
1336 int rational)
1337 {
1338 isl_set *cond;
1339
1340 left = isl_pw_aff_list_copy(left);
1341 right = isl_pw_aff_list_copy(right);
1342 if (rational) {
1343 left = isl_pw_aff_list_set_rational(left);
1344 right = isl_pw_aff_list_set_rational(right);
1345 }
1346 if (type == ISL_TOKEN_LE)
1347 cond = isl_pw_aff_list_le_set(left, right);
1348 else if (type == ISL_TOKEN_GE)
1349 cond = isl_pw_aff_list_ge_set(left, right);
1350 else if (type == ISL_TOKEN_LT)
1351 cond = isl_pw_aff_list_lt_set(left, right);
1352 else if (type == ISL_TOKEN_GT)
1353 cond = isl_pw_aff_list_gt_set(left, right);
1354 else if (type == ISL_TOKEN_NE)
1355 cond = isl_pw_aff_list_ne_set(left, right);
1356 else
1357 cond = isl_pw_aff_list_eq_set(left, right);
1358
1359 return isl_set_intersect(set, cond);
1360 }
1361
1362 static __isl_give isl_map *add_constraint(struct isl_stream *s,
1363 struct vars *v, __isl_take isl_map *map, int rational)
1364 {
1365 struct isl_token *tok = NULL;
1366 isl_pw_aff_list *list1 = NULL, *list2 = NULL;
1367 isl_set *set;
1368
1369 set = isl_map_wrap(map);
1370 list1 = accept_affine_list(s, isl_set_get_space(set), v);
1371 if (!list1)
1372 goto error;
1373 tok = isl_stream_next_token(s);
1374 if (!is_comparator(tok)) {
1375 isl_stream_error(s, tok, "missing operator");
1376 if (tok)
1377 isl_stream_push_token(s, tok);
1378 tok = NULL;
1379 goto error;
1380 }
1381 for (;;) {
1382 list2 = accept_affine_list(s, isl_set_get_space(set), v);
1383 if (!list2)
1384 goto error;
1385
1386 set = construct_constraints(set, tok->type, list1, list2,
1387 rational);
1388 isl_token_free(tok);
1389 isl_pw_aff_list_free(list1);
1390 list1 = list2;
1391
1392 tok = isl_stream_next_token(s);
1393 if (!is_comparator(tok)) {
1394 if (tok)
1395 isl_stream_push_token(s, tok);
1396 break;
1397 }
1398 }
1399 isl_pw_aff_list_free(list1);
1400
1401 return isl_set_unwrap(set);
1402 error:
1403 if (tok)
1404 isl_token_free(tok);
1405 isl_pw_aff_list_free(list1);
1406 isl_pw_aff_list_free(list2);
1407 isl_set_free(set);
1408 return NULL;
1409 }
1410
1411 static __isl_give isl_map *read_exists(struct isl_stream *s,
1412 struct vars *v, __isl_take isl_map *map, int rational)
1413 {
1414 int n = v->n;
1415 int seen_paren = isl_stream_eat_if_available(s, '(');
1416
1417 map = isl_map_from_domain(isl_map_wrap(map));
1418 map = read_defined_var_list(s, v, map, rational);
1419
1420 if (isl_stream_eat(s, ':'))
1421 goto error;
1422
1423 map = read_formula(s, v, map, rational);
1424 map = isl_set_unwrap(isl_map_domain(map));
1425
1426 vars_drop(v, v->n - n);
1427 if (seen_paren && isl_stream_eat(s, ')'))
1428 goto error;
1429
1430 return map;
1431 error:
1432 isl_map_free(map);
1433 return NULL;
1434 }
1435
1436 /* Parse an expression between parentheses and push the result
1437 * back on the stream.
1438 *
1439 * The parsed expression may be either an affine expression
1440 * or a condition. The first type is pushed onto the stream
1441 * as an isl_pw_aff, while the second is pushed as an isl_map.
1442 *
1443 * If the initial token indicates the start of a condition,
1444 * we parse it as such.
1445 * Otherwise, we first parse an affine expression and push
1446 * that onto the stream. If the affine expression covers the
1447 * entire expression between parentheses, we return.
1448 * Otherwise, we assume that the affine expression is the
1449 * start of a condition and continue parsing.
1450 */
1451 static int resolve_paren_expr(struct isl_stream *s,
1452 struct vars *v, __isl_take isl_map *map, int rational)
1453 {
1454 struct isl_token *tok, *tok2;
1455 int line, col;
1456 isl_pw_aff *pwaff;
1457
1458 tok = isl_stream_next_token(s);
1459 if (!tok || tok->type != '(')
1460 goto error;
1461
1462 if (isl_stream_next_token_is(s, '('))
1463 if (resolve_paren_expr(s, v, isl_map_copy(map), rational))
1464 goto error;
1465
1466 if (isl_stream_next_token_is(s, ISL_TOKEN_EXISTS) ||
1467 isl_stream_next_token_is(s, ISL_TOKEN_NOT) ||
1468 isl_stream_next_token_is(s, ISL_TOKEN_TRUE) ||
1469 isl_stream_next_token_is(s, ISL_TOKEN_FALSE) ||
1470 isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1471 map = read_formula(s, v, map, rational);
1472 if (isl_stream_eat(s, ')'))
1473 goto error;
1474 tok->type = ISL_TOKEN_MAP;
1475 tok->u.map = map;
1476 isl_stream_push_token(s, tok);
1477 return 0;
1478 }
1479
1480 tok2 = isl_stream_next_token(s);
1481 if (!tok2)
1482 goto error;
1483 line = tok2->line;
1484 col = tok2->col;
1485 isl_stream_push_token(s, tok2);
1486
1487 pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v);
1488 if (!pwaff)
1489 goto error;
1490
1491 tok2 = isl_token_new(s->ctx, line, col, 0);
1492 if (!tok2)
1493 goto error2;
1494 tok2->type = ISL_TOKEN_AFF;
1495 tok2->u.pwaff = pwaff;
1496
1497 if (isl_stream_eat_if_available(s, ')')) {
1498 isl_stream_push_token(s, tok2);
1499 isl_token_free(tok);
1500 isl_map_free(map);
1501 return 0;
1502 }
1503
1504 isl_stream_push_token(s, tok2);
1505
1506 map = read_formula(s, v, map, rational);
1507 if (isl_stream_eat(s, ')'))
1508 goto error;
1509
1510 tok->type = ISL_TOKEN_MAP;
1511 tok->u.map = map;
1512 isl_stream_push_token(s, tok);
1513
1514 return 0;
1515 error2:
1516 isl_pw_aff_free(pwaff);
1517 error:
1518 isl_token_free(tok);
1519 isl_map_free(map);
1520 return -1;
1521 }
1522
1523 static __isl_give isl_map *read_conjunct(struct isl_stream *s,
1524 struct vars *v, __isl_take isl_map *map, int rational)
1525 {
1526 if (isl_stream_next_token_is(s, '('))
1527 if (resolve_paren_expr(s, v, isl_map_copy(map), rational))
1528 goto error;
1529
1530 if (isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1531 struct isl_token *tok;
1532 tok = isl_stream_next_token(s);
1533 if (!tok)
1534 goto error;
1535 isl_map_free(map);
1536 map = isl_map_copy(tok->u.map);
1537 isl_token_free(tok);
1538 return map;
1539 }
1540
1541 if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))
1542 return read_exists(s, v, map, rational);
1543
1544 if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))
1545 return map;
1546
1547 if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) {
1548 isl_space *dim = isl_map_get_space(map);
1549 isl_map_free(map);
1550 return isl_map_empty(dim);
1551 }
1552
1553 return add_constraint(s, v, map, rational);
1554 error:
1555 isl_map_free(map);
1556 return NULL;
1557 }
1558
1559 static __isl_give isl_map *read_conjuncts(struct isl_stream *s,
1560 struct vars *v, __isl_take isl_map *map, int rational)
1561 {
1562 isl_map *res;
1563 int negate;
1564
1565 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1566 res = read_conjunct(s, v, isl_map_copy(map), rational);
1567 if (negate)
1568 res = isl_map_subtract(isl_map_copy(map), res);
1569
1570 while (res && isl_stream_eat_if_available(s, ISL_TOKEN_AND)) {
1571 isl_map *res_i;
1572
1573 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1574 res_i = read_conjunct(s, v, isl_map_copy(map), rational);
1575 if (negate)
1576 res = isl_map_subtract(res, res_i);
1577 else
1578 res = isl_map_intersect(res, res_i);
1579 }
1580
1581 isl_map_free(map);
1582 return res;
1583 }
1584
1585 static struct isl_map *read_disjuncts(struct isl_stream *s,
1586 struct vars *v, __isl_take isl_map *map, int rational)
1587 {
1588 isl_map *res;
1589
1590 if (isl_stream_next_token_is(s, '}')) {
1591 isl_space *dim = isl_map_get_space(map);
1592 isl_map_free(map);
1593 return isl_map_universe(dim);
1594 }
1595
1596 res = read_conjuncts(s, v, isl_map_copy(map), rational);
1597 while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
1598 isl_map *res_i;
1599
1600 res_i = read_conjuncts(s, v, isl_map_copy(map), rational);
1601 res = isl_map_union(res, res_i);
1602 }
1603
1604 isl_map_free(map);
1605 return res;
1606 }
1607
1608 /* Read a first order formula from "s", add the corresponding
1609 * constraints to "map" and return the result.
1610 *
1611 * In particular, read a formula of the form
1612 *
1613 * a
1614 *
1615 * or
1616 *
1617 * a implies b
1618 *
1619 * where a and b are disjunctions.
1620 *
1621 * In the first case, map is replaced by
1622 *
1623 * map \cap { [..] : a }
1624 *
1625 * In the second case, it is replaced by
1626 *
1627 * (map \setminus { [..] : a}) \cup (map \cap { [..] : b })
1628 */
1629 static __isl_give isl_map *read_formula(struct isl_stream *s,
1630 struct vars *v, __isl_take isl_map *map, int rational)
1631 {
1632 isl_map *res;
1633
1634 res = read_disjuncts(s, v, isl_map_copy(map), rational);
1635
1636 if (isl_stream_eat_if_available(s, ISL_TOKEN_IMPLIES)) {
1637 isl_map *res2;
1638
1639 res = isl_map_subtract(isl_map_copy(map), res);
1640 res2 = read_disjuncts(s, v, map, rational);
1641 res = isl_map_union(res, res2);
1642 } else
1643 isl_map_free(map);
1644
1645 return res;
1646 }
1647
1648 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1649 {
1650 if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1651 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1652 isl_basic_map_dim(bmap, isl_dim_in) + pos;
1653 pos -= isl_basic_map_dim(bmap, isl_dim_out);
1654
1655 if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1656 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1657 pos -= isl_basic_map_dim(bmap, isl_dim_in);
1658
1659 if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1660 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1661 isl_basic_map_dim(bmap, isl_dim_in) +
1662 isl_basic_map_dim(bmap, isl_dim_out) + pos;
1663 pos -= isl_basic_map_dim(bmap, isl_dim_div);
1664
1665 if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1666 return 1 + pos;
1667
1668 return 0;
1669 }
1670
1671 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1672 struct isl_stream *s, __isl_take isl_basic_map *bmap)
1673 {
1674 int j;
1675 struct isl_token *tok;
1676 int type;
1677 int k;
1678 isl_int *c;
1679 unsigned nparam;
1680 unsigned dim;
1681
1682 if (!bmap)
1683 return NULL;
1684
1685 nparam = isl_basic_map_dim(bmap, isl_dim_param);
1686 dim = isl_basic_map_dim(bmap, isl_dim_out);
1687
1688 tok = isl_stream_next_token(s);
1689 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1690 isl_stream_error(s, tok, "expecting coefficient");
1691 if (tok)
1692 isl_stream_push_token(s, tok);
1693 goto error;
1694 }
1695 if (!tok->on_new_line) {
1696 isl_stream_error(s, tok, "coefficient should appear on new line");
1697 isl_stream_push_token(s, tok);
1698 goto error;
1699 }
1700
1701 type = isl_int_get_si(tok->u.v);
1702 isl_token_free(tok);
1703
1704 isl_assert(s->ctx, type == 0 || type == 1, goto error);
1705 if (type == 0) {
1706 k = isl_basic_map_alloc_equality(bmap);
1707 c = bmap->eq[k];
1708 } else {
1709 k = isl_basic_map_alloc_inequality(bmap);
1710 c = bmap->ineq[k];
1711 }
1712 if (k < 0)
1713 goto error;
1714
1715 for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1716 int pos;
1717 tok = isl_stream_next_token(s);
1718 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1719 isl_stream_error(s, tok, "expecting coefficient");
1720 if (tok)
1721 isl_stream_push_token(s, tok);
1722 goto error;
1723 }
1724 if (tok->on_new_line) {
1725 isl_stream_error(s, tok,
1726 "coefficient should not appear on new line");
1727 isl_stream_push_token(s, tok);
1728 goto error;
1729 }
1730 pos = polylib_pos_to_isl_pos(bmap, j);
1731 isl_int_set(c[pos], tok->u.v);
1732 isl_token_free(tok);
1733 }
1734
1735 return bmap;
1736 error:
1737 isl_basic_map_free(bmap);
1738 return NULL;
1739 }
1740
1741 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s)
1742 {
1743 int i;
1744 struct isl_token *tok;
1745 struct isl_token *tok2;
1746 int n_row, n_col;
1747 int on_new_line;
1748 unsigned in = 0, out, local = 0;
1749 struct isl_basic_map *bmap = NULL;
1750 int nparam = 0;
1751
1752 tok = isl_stream_next_token(s);
1753 if (!tok) {
1754 isl_stream_error(s, NULL, "unexpected EOF");
1755 return NULL;
1756 }
1757 tok2 = isl_stream_next_token(s);
1758 if (!tok2) {
1759 isl_token_free(tok);
1760 isl_stream_error(s, NULL, "unexpected EOF");
1761 return NULL;
1762 }
1763 if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1764 isl_stream_push_token(s, tok2);
1765 isl_stream_push_token(s, tok);
1766 isl_stream_error(s, NULL,
1767 "expecting constraint matrix dimensions");
1768 return NULL;
1769 }
1770 n_row = isl_int_get_si(tok->u.v);
1771 n_col = isl_int_get_si(tok2->u.v);
1772 on_new_line = tok2->on_new_line;
1773 isl_token_free(tok2);
1774 isl_token_free(tok);
1775 isl_assert(s->ctx, !on_new_line, return NULL);
1776 isl_assert(s->ctx, n_row >= 0, return NULL);
1777 isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1778 tok = isl_stream_next_token_on_same_line(s);
1779 if (tok) {
1780 if (tok->type != ISL_TOKEN_VALUE) {
1781 isl_stream_error(s, tok,
1782 "expecting number of output dimensions");
1783 isl_stream_push_token(s, tok);
1784 goto error;
1785 }
1786 out = isl_int_get_si(tok->u.v);
1787 isl_token_free(tok);
1788
1789 tok = isl_stream_next_token_on_same_line(s);
1790 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1791 isl_stream_error(s, tok,
1792 "expecting number of input dimensions");
1793 if (tok)
1794 isl_stream_push_token(s, tok);
1795 goto error;
1796 }
1797 in = isl_int_get_si(tok->u.v);
1798 isl_token_free(tok);
1799
1800 tok = isl_stream_next_token_on_same_line(s);
1801 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1802 isl_stream_error(s, tok,
1803 "expecting number of existentials");
1804 if (tok)
1805 isl_stream_push_token(s, tok);
1806 goto error;
1807 }
1808 local = isl_int_get_si(tok->u.v);
1809 isl_token_free(tok);
1810
1811 tok = isl_stream_next_token_on_same_line(s);
1812 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1813 isl_stream_error(s, tok,
1814 "expecting number of parameters");
1815 if (tok)
1816 isl_stream_push_token(s, tok);
1817 goto error;
1818 }
1819 nparam = isl_int_get_si(tok->u.v);
1820 isl_token_free(tok);
1821 if (n_col != 1 + out + in + local + nparam + 1) {
1822 isl_stream_error(s, NULL,
1823 "dimensions don't match");
1824 goto error;
1825 }
1826 } else
1827 out = n_col - 2 - nparam;
1828 bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1829 if (!bmap)
1830 return NULL;
1831
1832 for (i = 0; i < local; ++i) {
1833 int k = isl_basic_map_alloc_div(bmap);
1834 if (k < 0)
1835 goto error;
1836 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1837 }
1838
1839 for (i = 0; i < n_row; ++i)
1840 bmap = basic_map_read_polylib_constraint(s, bmap);
1841
1842 tok = isl_stream_next_token_on_same_line(s);
1843 if (tok) {
1844 isl_stream_error(s, tok, "unexpected extra token on line");
1845 isl_stream_push_token(s, tok);
1846 goto error;
1847 }
1848
1849 bmap = isl_basic_map_simplify(bmap);
1850 bmap = isl_basic_map_finalize(bmap);
1851 return bmap;
1852 error:
1853 isl_basic_map_free(bmap);
1854 return NULL;
1855 }
1856
1857 static struct isl_map *map_read_polylib(struct isl_stream *s)
1858 {
1859 struct isl_token *tok;
1860 struct isl_token *tok2;
1861 int i, n;
1862 struct isl_map *map;
1863
1864 tok = isl_stream_next_token(s);
1865 if (!tok) {
1866 isl_stream_error(s, NULL, "unexpected EOF");
1867 return NULL;
1868 }
1869 tok2 = isl_stream_next_token_on_same_line(s);
1870 if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
1871 isl_stream_push_token(s, tok2);
1872 isl_stream_push_token(s, tok);
1873 return isl_map_from_basic_map(basic_map_read_polylib(s));
1874 }
1875 if (tok2) {
1876 isl_stream_error(s, tok2, "unexpected token");
1877 isl_stream_push_token(s, tok2);
1878 isl_stream_push_token(s, tok);
1879 return NULL;
1880 }
1881 n = isl_int_get_si(tok->u.v);
1882 isl_token_free(tok);
1883
1884 isl_assert(s->ctx, n >= 1, return NULL);
1885
1886 map = isl_map_from_basic_map(basic_map_read_polylib(s));
1887
1888 for (i = 1; map && i < n; ++i)
1889 map = isl_map_union(map,
1890 isl_map_from_basic_map(basic_map_read_polylib(s)));
1891
1892 return map;
1893 }
1894
1895 static int optional_power(struct isl_stream *s)
1896 {
1897 int pow;
1898 struct isl_token *tok;
1899
1900 tok = isl_stream_next_token(s);
1901 if (!tok)
1902 return 1;
1903 if (tok->type != '^') {
1904 isl_stream_push_token(s, tok);
1905 return 1;
1906 }
1907 isl_token_free(tok);
1908 tok = isl_stream_next_token(s);
1909 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1910 isl_stream_error(s, tok, "expecting exponent");
1911 if (tok)
1912 isl_stream_push_token(s, tok);
1913 return 1;
1914 }
1915 pow = isl_int_get_si(tok->u.v);
1916 isl_token_free(tok);
1917 return pow;
1918 }
1919
1920 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1921 __isl_keep isl_map *map, struct vars *v);
1922
1923 static __isl_give isl_pw_qpolynomial *read_factor(struct isl_stream *s,
1924 __isl_keep isl_map *map, struct vars *v)
1925 {
1926 isl_pw_qpolynomial *pwqp;
1927 struct isl_token *tok;
1928
1929 tok = next_token(s);
1930 if (!tok) {
1931 isl_stream_error(s, NULL, "unexpected EOF");
1932 return NULL;
1933 }
1934 if (tok->type == '(') {
1935 int pow;
1936
1937 isl_token_free(tok);
1938 pwqp = read_term(s, map, v);
1939 if (!pwqp)
1940 return NULL;
1941 if (isl_stream_eat(s, ')'))
1942 goto error;
1943 pow = optional_power(s);
1944 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1945 } else if (tok->type == ISL_TOKEN_VALUE) {
1946 struct isl_token *tok2;
1947 isl_qpolynomial *qp;
1948
1949 tok2 = isl_stream_next_token(s);
1950 if (tok2 && tok2->type == '/') {
1951 isl_token_free(tok2);
1952 tok2 = next_token(s);
1953 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1954 isl_stream_error(s, tok2, "expected denominator");
1955 isl_token_free(tok);
1956 isl_token_free(tok2);
1957 return NULL;
1958 }
1959 qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map),
1960 tok->u.v, tok2->u.v);
1961 isl_token_free(tok2);
1962 } else {
1963 isl_stream_push_token(s, tok2);
1964 qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map),
1965 tok->u.v);
1966 }
1967 isl_token_free(tok);
1968 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1969 } else if (tok->type == ISL_TOKEN_INFTY) {
1970 isl_qpolynomial *qp;
1971 isl_token_free(tok);
1972 qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map));
1973 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1974 } else if (tok->type == ISL_TOKEN_NAN) {
1975 isl_qpolynomial *qp;
1976 isl_token_free(tok);
1977 qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map));
1978 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1979 } else if (tok->type == ISL_TOKEN_IDENT) {
1980 int n = v->n;
1981 int pos = vars_pos(v, tok->u.s, -1);
1982 int pow;
1983 isl_qpolynomial *qp;
1984 if (pos < 0) {
1985 isl_token_free(tok);
1986 return NULL;
1987 }
1988 if (pos >= n) {
1989 vars_drop(v, v->n - n);
1990 isl_stream_error(s, tok, "unknown identifier");
1991 isl_token_free(tok);
1992 return NULL;
1993 }
1994 isl_token_free(tok);
1995 pow = optional_power(s);
1996 qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow);
1997 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1998 } else if (is_start_of_div(tok)) {
1999 isl_pw_aff *pwaff;
2000 int pow;
2001
2002 isl_stream_push_token(s, tok);
2003 pwaff = accept_div(s, isl_map_get_space(map), v);
2004 pow = optional_power(s);
2005 pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff);
2006 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
2007 } else if (tok->type == '-') {
2008 isl_token_free(tok);
2009 pwqp = read_factor(s, map, v);
2010 pwqp = isl_pw_qpolynomial_neg(pwqp);
2011 } else {
2012 isl_stream_error(s, tok, "unexpected isl_token");
2013 isl_stream_push_token(s, tok);
2014 return NULL;
2015 }
2016
2017 if (isl_stream_eat_if_available(s, '*') ||
2018 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
2019 isl_pw_qpolynomial *pwqp2;
2020
2021 pwqp2 = read_factor(s, map, v);
2022 pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2);
2023 }
2024
2025 return pwqp;
2026 error:
2027 isl_pw_qpolynomial_free(pwqp);
2028 return NULL;
2029 }
2030
2031 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
2032 __isl_keep isl_map *map, struct vars *v)
2033 {
2034 struct isl_token *tok;
2035 isl_pw_qpolynomial *pwqp;
2036
2037 pwqp = read_factor(s, map, v);
2038
2039 for (;;) {
2040 tok = next_token(s);
2041 if (!tok)
2042 return pwqp;
2043
2044 if (tok->type == '+') {
2045 isl_pw_qpolynomial *pwqp2;
2046
2047 isl_token_free(tok);
2048 pwqp2 = read_factor(s, map, v);
2049 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
2050 } else if (tok->type == '-') {
2051 isl_pw_qpolynomial *pwqp2;
2052
2053 isl_token_free(tok);
2054 pwqp2 = read_factor(s, map, v);
2055 pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2);
2056 } else if (tok->type == ISL_TOKEN_VALUE &&
2057 isl_int_is_neg(tok->u.v)) {
2058 isl_pw_qpolynomial *pwqp2;
2059
2060 isl_stream_push_token(s, tok);
2061 pwqp2 = read_factor(s, map, v);
2062 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
2063 } else {
2064 isl_stream_push_token(s, tok);
2065 break;
2066 }
2067 }
2068
2069 return pwqp;
2070 }
2071
2072 static __isl_give isl_map *read_optional_formula(struct isl_stream *s,
2073 __isl_take isl_map *map, struct vars *v, int rational)
2074 {
2075 struct isl_token *tok;
2076
2077 tok = isl_stream_next_token(s);
2078 if (!tok) {
2079 isl_stream_error(s, NULL, "unexpected EOF");
2080 goto error;
2081 }
2082 if (tok->type == ':' ||
2083 (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {
2084 isl_token_free(tok);
2085 map = read_formula(s, v, map, rational);
2086 } else
2087 isl_stream_push_token(s, tok);
2088
2089 return map;
2090 error:
2091 isl_map_free(map);
2092 return NULL;
2093 }
2094
2095 static struct isl_obj obj_read_poly(struct isl_stream *s,
2096 __isl_take isl_map *map, struct vars *v, int n)
2097 {
2098 struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
2099 isl_pw_qpolynomial *pwqp;
2100 struct isl_set *set;
2101
2102 pwqp = read_term(s, map, v);
2103 map = read_optional_formula(s, map, v, 0);
2104 set = isl_map_range(map);
2105
2106 pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set);
2107
2108 vars_drop(v, v->n - n);
2109
2110 obj.v = pwqp;
2111 return obj;
2112 }
2113
2114 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
2115 __isl_take isl_set *set, struct vars *v, int n)
2116 {
2117 struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
2118 isl_pw_qpolynomial *pwqp;
2119 isl_pw_qpolynomial_fold *pwf = NULL;
2120
2121 if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
2122 return obj_read_poly(s, set, v, n);
2123
2124 if (isl_stream_eat(s, '('))
2125 goto error;
2126
2127 pwqp = read_term(s, set, v);
2128 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, pwqp);
2129
2130 while (isl_stream_eat_if_available(s, ',')) {
2131 isl_pw_qpolynomial_fold *pwf_i;
2132 pwqp = read_term(s, set, v);
2133 pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max,
2134 pwqp);
2135 pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i);
2136 }
2137
2138 if (isl_stream_eat(s, ')'))
2139 goto error;
2140
2141 set = read_optional_formula(s, set, v, 0);
2142 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set);
2143
2144 vars_drop(v, v->n - n);
2145
2146 obj.v = pwf;
2147 return obj;
2148 error:
2149 isl_set_free(set);
2150 isl_pw_qpolynomial_fold_free(pwf);
2151 obj.type = isl_obj_none;
2152 return obj;
2153 }
2154
2155 static int is_rational(struct isl_stream *s)
2156 {
2157 struct isl_token *tok;
2158
2159 tok = isl_stream_next_token(s);
2160 if (!tok)
2161 return 0;
2162 if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) {
2163 isl_token_free(tok);
2164 isl_stream_eat(s, ':');
2165 return 1;
2166 }
2167
2168 isl_stream_push_token(s, tok);
2169
2170 return 0;
2171 }
2172
2173 static struct isl_obj obj_read_body(struct isl_stream *s,
2174 __isl_take isl_map *map, struct vars *v)
2175 {
2176 struct isl_token *tok;
2177 struct isl_obj obj = { isl_obj_set, NULL };
2178 int n = v->n;
2179 int rational;
2180
2181 rational = is_rational(s);
2182 if (rational)
2183 map = isl_map_set_rational(map);
2184
2185 if (isl_stream_next_token_is(s, ':')) {
2186 obj.type = isl_obj_set;
2187 obj.v = read_optional_formula(s, map, v, rational);
2188 return obj;
2189 }
2190
2191 if (!next_is_tuple(s))
2192 return obj_read_poly_or_fold(s, map, v, n);
2193
2194 map = read_map_tuple(s, map, isl_dim_in, v, rational, 0);
2195 if (!map)
2196 goto error;
2197 tok = isl_stream_next_token(s);
2198 if (!tok)
2199 goto error;
2200 if (tok->type == ISL_TOKEN_TO) {
2201 obj.type = isl_obj_map;
2202 isl_token_free(tok);
2203 if (!next_is_tuple(s)) {
2204 isl_set *set = isl_map_domain(map);
2205 return obj_read_poly_or_fold(s, set, v, n);
2206 }
2207 map = read_map_tuple(s, map, isl_dim_out, v, rational, 0);
2208 if (!map)
2209 goto error;
2210 } else {
2211 map = isl_map_domain(map);
2212 isl_stream_push_token(s, tok);
2213 }
2214
2215 map = read_optional_formula(s, map, v, rational);
2216
2217 vars_drop(v, v->n - n);
2218
2219 obj.v = map;
2220 return obj;
2221 error:
2222 isl_map_free(map);
2223 obj.type = isl_obj_none;
2224 return obj;
2225 }
2226
2227 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
2228 {
2229 if (obj.type == isl_obj_map) {
2230 obj.v = isl_union_map_from_map(obj.v);
2231 obj.type = isl_obj_union_map;
2232 } else if (obj.type == isl_obj_set) {
2233 obj.v = isl_union_set_from_set(obj.v);
2234 obj.type = isl_obj_union_set;
2235 } else if (obj.type == isl_obj_pw_qpolynomial) {
2236 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2237 obj.type = isl_obj_union_pw_qpolynomial;
2238 } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
2239 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
2240 obj.type = isl_obj_union_pw_qpolynomial_fold;
2241 } else
2242 isl_assert(ctx, 0, goto error);
2243 return obj;
2244 error:
2245 obj.type->free(obj.v);
2246 obj.type = isl_obj_none;
2247 return obj;
2248 }
2249
2250 static struct isl_obj obj_add(struct isl_ctx *ctx,
2251 struct isl_obj obj1, struct isl_obj obj2)
2252 {
2253 if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
2254 obj1 = to_union(ctx, obj1);
2255 if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
2256 obj2 = to_union(ctx, obj2);
2257 if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
2258 obj1 = to_union(ctx, obj1);
2259 if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
2260 obj2 = to_union(ctx, obj2);
2261 if (obj1.type == isl_obj_pw_qpolynomial &&
2262 obj2.type == isl_obj_union_pw_qpolynomial)
2263 obj1 = to_union(ctx, obj1);
2264 if (obj1.type == isl_obj_union_pw_qpolynomial &&
2265 obj2.type == isl_obj_pw_qpolynomial)
2266 obj2 = to_union(ctx, obj2);
2267 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2268 obj2.type == isl_obj_union_pw_qpolynomial_fold)
2269 obj1 = to_union(ctx, obj1);
2270 if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
2271 obj2.type == isl_obj_pw_qpolynomial_fold)
2272 obj2 = to_union(ctx, obj2);
2273 isl_assert(ctx, obj1.type == obj2.type, goto error);
2274 if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) {
2275 obj1 = to_union(ctx, obj1);
2276 obj2 = to_union(ctx, obj2);
2277 }
2278 if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) {
2279 obj1 = to_union(ctx, obj1);
2280 obj2 = to_union(ctx, obj2);
2281 }
2282 if (obj1.type == isl_obj_pw_qpolynomial &&
2283 !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) {
2284 obj1 = to_union(ctx, obj1);
2285 obj2 = to_union(ctx, obj2);
2286 }
2287 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2288 !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) {
2289 obj1 = to_union(ctx, obj1);
2290 obj2 = to_union(ctx, obj2);
2291 }
2292 obj1.v = obj1.type->add(obj1.v, obj2.v);
2293 return obj1;
2294 error:
2295 obj1.type->free(obj1.v);
2296 obj2.type->free(obj2.v);
2297 obj1.type = isl_obj_none;
2298 obj1.v = NULL;
2299 return obj1;
2300 }
2301
2302 static struct isl_obj obj_read(struct isl_stream *s)
2303 {
2304 isl_map *map = NULL;
2305 struct isl_token *tok;
2306 struct vars *v = NULL;
2307 struct isl_obj obj = { isl_obj_set, NULL };
2308
2309 tok = next_token(s);
2310 if (!tok) {
2311 isl_stream_error(s, NULL, "unexpected EOF");
2312 goto error;
2313 }
2314 if (tok->type == ISL_TOKEN_VALUE) {
2315 struct isl_token *tok2;
2316 struct isl_map *map;
2317
2318 tok2 = isl_stream_next_token(s);
2319 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
2320 isl_int_is_neg(tok2->u.v)) {
2321 if (tok2)
2322 isl_stream_push_token(s, tok2);
2323 obj.type = isl_obj_val;
2324 obj.v = isl_val_int_from_isl_int(s->ctx, tok->u.v);
2325 isl_token_free(tok);
2326 return obj;
2327 }
2328 isl_stream_push_token(s, tok2);
2329 isl_stream_push_token(s, tok);
2330 map = map_read_polylib(s);
2331 if (!map)
2332 goto error;
2333 if (isl_map_may_be_set(map))
2334 obj.v = isl_map_range(map);
2335 else {
2336 obj.type = isl_obj_map;
2337 obj.v = map;
2338 }
2339 return obj;
2340 }
2341 v = vars_new(s->ctx);
2342 if (!v) {
2343 isl_stream_push_token(s, tok);
2344 goto error;
2345 }
2346 map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));
2347 if (tok->type == '[') {
2348 isl_stream_push_token(s, tok);
2349 map = read_map_tuple(s, map, isl_dim_param, v, 0, 0);
2350 if (!map)
2351 goto error;
2352 tok = isl_stream_next_token(s);
2353 if (!tok || tok->type != ISL_TOKEN_TO) {
2354 isl_stream_error(s, tok, "expecting '->'");
2355 if (tok)
2356 isl_stream_push_token(s, tok);
2357 goto error;
2358 }
2359 isl_token_free(tok);
2360 tok = isl_stream_next_token(s);
2361 }
2362 if (!tok || tok->type != '{') {
2363 isl_stream_error(s, tok, "expecting '{'");
2364 if (tok)
2365 isl_stream_push_token(s, tok);
2366 goto error;
2367 }
2368 isl_token_free(tok);
2369
2370 tok = isl_stream_next_token(s);
2371 if (!tok)
2372 ;
2373 else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
2374 isl_token_free(tok);
2375 if (isl_stream_eat(s, '='))
2376 goto error;
2377 map = read_map_tuple(s, map, isl_dim_param, v, 0, 1);
2378 if (!map)
2379 goto error;
2380 } else if (tok->type == '}') {
2381 obj.type = isl_obj_union_set;
2382 obj.v = isl_union_set_empty(isl_map_get_space(map));
2383 isl_token_free(tok);
2384 goto done;
2385 } else
2386 isl_stream_push_token(s, tok);
2387
2388 for (;;) {
2389 struct isl_obj o;
2390 tok = NULL;
2391 o = obj_read_body(s, isl_map_copy(map), v);
2392 if (o.type == isl_obj_none || !o.v)
2393 goto error;
2394 if (!obj.v)
2395 obj = o;
2396 else {
2397 obj = obj_add(s->ctx, obj, o);
2398 if (obj.type == isl_obj_none || !obj.v)
2399 goto error;
2400 }
2401 tok = isl_stream_next_token(s);
2402 if (!tok || tok->type != ';')
2403 break;
2404 isl_token_free(tok);
2405 if (isl_stream_next_token_is(s, '}')) {
2406 tok = isl_stream_next_token(s);
2407 break;
2408 }
2409 }
2410
2411 if (tok && tok->type == '}') {
2412 isl_token_free(tok);
2413 } else {
2414 isl_stream_error(s, tok, "unexpected isl_token");
2415 if (tok)
2416 isl_token_free(tok);
2417 goto error;
2418 }
2419 done:
2420 vars_free(v);
2421 isl_map_free(map);
2422
2423 return obj;
2424 error:
2425 isl_map_free(map);
2426 obj.type->free(obj.v);
2427 if (v)
2428 vars_free(v);
2429 obj.v = NULL;
2430 return obj;
2431 }
2432
2433 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
2434 {
2435 return obj_read(s);
2436 }
2437
2438 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s)
2439 {
2440 struct isl_obj obj;
2441
2442 obj = obj_read(s);
2443 if (obj.v)
2444 isl_assert(s->ctx, obj.type == isl_obj_map ||
2445 obj.type == isl_obj_set, goto error);
2446
2447 if (obj.type == isl_obj_set)
2448 obj.v = isl_map_from_range(obj.v);
2449
2450 return obj.v;
2451 error:
2452 obj.type->free(obj.v);
2453 return NULL;
2454 }
2455
2456 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s)
2457 {
2458 struct isl_obj obj;
2459
2460 obj = obj_read(s);
2461 if (obj.v) {
2462 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) {
2463 obj.v = isl_map_range(obj.v);
2464 obj.type = isl_obj_set;
2465 }
2466 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2467 }
2468
2469 return obj.v;
2470 error:
2471 obj.type->free(obj.v);
2472 return NULL;
2473 }
2474
2475 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2476 {
2477 struct isl_obj obj;
2478
2479 obj = obj_read(s);
2480 if (obj.type == isl_obj_map) {
2481 obj.type = isl_obj_union_map;
2482 obj.v = isl_union_map_from_map(obj.v);
2483 }
2484 if (obj.type == isl_obj_set) {
2485 obj.type = isl_obj_union_set;
2486 obj.v = isl_union_set_from_set(obj.v);
2487 }
2488 if (obj.v && obj.type == isl_obj_union_set &&
2489 isl_union_set_is_empty(obj.v))
2490 obj.type = isl_obj_union_map;
2491 if (obj.v && obj.type != isl_obj_union_map)
2492 isl_die(s->ctx, isl_error_invalid, "invalid input", goto error);
2493
2494 return obj.v;
2495 error:
2496 obj.type->free(obj.v);
2497 return NULL;
2498 }
2499
2500 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2501 {
2502 struct isl_obj obj;
2503
2504 obj = obj_read(s);
2505 if (obj.type == isl_obj_set) {
2506 obj.type = isl_obj_union_set;
2507 obj.v = isl_union_set_from_set(obj.v);
2508 }
2509 if (obj.v)
2510 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2511
2512 return obj.v;
2513 error:
2514 obj.type->free(obj.v);
2515 return NULL;
2516 }
2517
2518 static __isl_give isl_basic_map *basic_map_read(struct isl_stream *s)
2519 {
2520 struct isl_obj obj;
2521 struct isl_map *map;
2522 struct isl_basic_map *bmap;
2523
2524 obj = obj_read(s);
2525 map = obj.v;
2526 if (!map)
2527 return NULL;
2528
2529 isl_assert(map->ctx, map->n <= 1, goto error);
2530
2531 if (map->n == 0)
2532 bmap = isl_basic_map_empty_like_map(map);
2533 else
2534 bmap = isl_basic_map_copy(map->p[0]);
2535
2536 isl_map_free(map);
2537
2538 return bmap;
2539 error:
2540 isl_map_free(map);
2541 return NULL;
2542 }
2543
2544 static __isl_give isl_basic_set *basic_set_read(struct isl_stream *s)
2545 {
2546 isl_basic_map *bmap;
2547 bmap = basic_map_read(s);
2548 if (!bmap)
2549 return NULL;
2550 if (!isl_basic_map_may_be_set(bmap))
2551 isl_die(s->ctx, isl_error_invalid,
2552 "input is not a set", goto error);
2553 return isl_basic_map_range(bmap);
2554 error:
2555 isl_basic_map_free(bmap);
2556 return NULL;
2557 }
2558
2559 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2560 FILE *input)
2561 {
2562 struct isl_basic_map *bmap;
2563 struct isl_stream *s = isl_stream_new_file(ctx, input);
2564 if (!s)
2565 return NULL;
2566 bmap = basic_map_read(s);
2567 isl_stream_free(s);
2568 return bmap;
2569 }
2570
2571 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2572 FILE *input)
2573 {
2574 isl_basic_set *bset;
2575 struct isl_stream *s = isl_stream_new_file(ctx, input);
2576 if (!s)
2577 return NULL;
2578 bset = basic_set_read(s);
2579 isl_stream_free(s);
2580 return bset;
2581 }
2582
2583 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2584 const char *str)
2585 {
2586 struct isl_basic_map *bmap;
2587 struct isl_stream *s = isl_stream_new_str(ctx, str);
2588 if (!s)
2589 return NULL;
2590 bmap = basic_map_read(s);
2591 isl_stream_free(s);
2592 return bmap;
2593 }
2594
2595 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2596 const char *str)
2597 {
2598 isl_basic_set *bset;
2599 struct isl_stream *s = isl_stream_new_str(ctx, str);
2600 if (!s)
2601 return NULL;
2602 bset = basic_set_read(s);
2603 isl_stream_free(s);
2604 return bset;
2605 }
2606
2607 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2608 FILE *input)
2609 {
2610 struct isl_map *map;
2611 struct isl_stream *s = isl_stream_new_file(ctx, input);
2612 if (!s)
2613 return NULL;
2614 map = isl_stream_read_map(s);
2615 isl_stream_free(s);
2616 return map;
2617 }
2618
2619 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2620 const char *str)
2621 {
2622 struct isl_map *map;
2623 struct isl_stream *s = isl_stream_new_str(ctx, str);
2624 if (!s)
2625 return NULL;
2626 map = isl_stream_read_map(s);
2627 isl_stream_free(s);
2628 return map;
2629 }
2630
2631 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2632 FILE *input)
2633 {
2634 isl_set *set;
2635 struct isl_stream *s = isl_stream_new_file(ctx, input);
2636 if (!s)
2637 return NULL;
2638 set = isl_stream_read_set(s);
2639 isl_stream_free(s);
2640 return set;
2641 }
2642
2643 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2644 const char *str)
2645 {
2646 isl_set *set;
2647 struct isl_stream *s = isl_stream_new_str(ctx, str);
2648 if (!s)
2649 return NULL;
2650 set = isl_stream_read_set(s);
2651 isl_stream_free(s);
2652 return set;
2653 }
2654
2655 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2656 FILE *input)
2657 {
2658 isl_union_map *umap;
2659 struct isl_stream *s = isl_stream_new_file(ctx, input);
2660 if (!s)
2661 return NULL;
2662 umap = isl_stream_read_union_map(s);
2663 isl_stream_free(s);
2664 return umap;
2665 }
2666
2667 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2668 const char *str)
2669 {
2670 isl_union_map *umap;
2671 struct isl_stream *s = isl_stream_new_str(ctx, str);
2672 if (!s)
2673 return NULL;
2674 umap = isl_stream_read_union_map(s);
2675 isl_stream_free(s);
2676 return umap;
2677 }
2678
2679 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2680 FILE *input)
2681 {
2682 isl_union_set *uset;
2683 struct isl_stream *s = isl_stream_new_file(ctx, input);
2684 if (!s)
2685 return NULL;
2686 uset = isl_stream_read_union_set(s);
2687 isl_stream_free(s);
2688 return uset;
2689 }
2690
2691 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2692 const char *str)
2693 {
2694 isl_union_set *uset;
2695 struct isl_stream *s = isl_stream_new_str(ctx, str);
2696 if (!s)
2697 return NULL;
2698 uset = isl_stream_read_union_set(s);
2699 isl_stream_free(s);
2700 return uset;
2701 }
2702
2703 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2704 {
2705 struct isl_vec *vec = NULL;
2706 struct isl_token *tok;
2707 unsigned size;
2708 int j;
2709
2710 tok = isl_stream_next_token(s);
2711 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2712 isl_stream_error(s, tok, "expecting vector length");
2713 goto error;
2714 }
2715
2716 size = isl_int_get_si(tok->u.v);
2717 isl_token_free(tok);
2718
2719 vec = isl_vec_alloc(s->ctx, size);
2720
2721 for (j = 0; j < size; ++j) {
2722 tok = isl_stream_next_token(s);
2723 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2724 isl_stream_error(s, tok, "expecting constant value");
2725 goto error;
2726 }
2727 isl_int_set(vec->el[j], tok->u.v);
2728 isl_token_free(tok);
2729 }
2730
2731 return vec;
2732 error:
2733 isl_token_free(tok);
2734 isl_vec_free(vec);
2735 return NULL;
2736 }
2737
2738 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2739 {
2740 return isl_vec_read_polylib(s);
2741 }
2742
2743 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2744 {
2745 isl_vec *v;
2746 struct isl_stream *s = isl_stream_new_file(ctx, input);
2747 if (!s)
2748 return NULL;
2749 v = vec_read(s);
2750 isl_stream_free(s);
2751 return v;
2752 }
2753
2754 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2755 struct isl_stream *s)
2756 {
2757 struct isl_obj obj;
2758
2759 obj = obj_read(s);
2760 if (obj.v)
2761 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2762 goto error);
2763
2764 return obj.v;
2765 error:
2766 obj.type->free(obj.v);
2767 return NULL;
2768 }
2769
2770 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2771 const char *str)
2772 {
2773 isl_pw_qpolynomial *pwqp;
2774 struct isl_stream *s = isl_stream_new_str(ctx, str);
2775 if (!s)
2776 return NULL;
2777 pwqp = isl_stream_read_pw_qpolynomial(s);
2778 isl_stream_free(s);
2779 return pwqp;
2780 }
2781
2782 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
2783 FILE *input)
2784 {
2785 isl_pw_qpolynomial *pwqp;
2786 struct isl_stream *s = isl_stream_new_file(ctx, input);
2787 if (!s)
2788 return NULL;
2789 pwqp = isl_stream_read_pw_qpolynomial(s);
2790 isl_stream_free(s);
2791 return pwqp;
2792 }
2793
2794 /* Is the next token an identifer not in "v"?
2795 */
2796 static int next_is_fresh_ident(struct isl_stream *s, struct vars *v)
2797 {
2798 int n = v->n;
2799 int fresh;
2800 struct isl_token *tok;
2801
2802 tok = isl_stream_next_token(s);
2803 if (!tok)
2804 return 0;
2805 fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n;
2806 isl_stream_push_token(s, tok);
2807
2808 vars_drop(v, v->n - n);
2809
2810 return fresh;
2811 }
2812
2813 /* First read the domain of the affine expression, which may be
2814 * a parameter space or a set.
2815 * The tricky part is that we don't know if the domain is a set or not,
2816 * so when we are trying to read the domain, we may actually be reading
2817 * the affine expression itself (defined on a parameter domains)
2818 * If the tuple we are reading is named, we assume it's the domain.
2819 * Also, if inside the tuple, the first thing we find is a nested tuple
2820 * or a new identifier, we again assume it's the domain.
2821 * Otherwise, we assume we are reading an affine expression.
2822 */
2823 static __isl_give isl_set *read_aff_domain(struct isl_stream *s,
2824 __isl_take isl_set *dom, struct vars *v)
2825 {
2826 struct isl_token *tok;
2827
2828 tok = isl_stream_next_token(s);
2829 if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
2830 isl_stream_push_token(s, tok);
2831 return read_map_tuple(s, dom, isl_dim_set, v, 1, 0);
2832 }
2833 if (!tok || tok->type != '[') {
2834 isl_stream_error(s, tok, "expecting '['");
2835 goto error;
2836 }
2837 if (next_is_tuple(s) || next_is_fresh_ident(s, v)) {
2838 isl_stream_push_token(s, tok);
2839 dom = read_map_tuple(s, dom, isl_dim_set, v, 1, 0);
2840 } else
2841 isl_stream_push_token(s, tok);
2842
2843 return dom;
2844 error:
2845 if (tok)
2846 isl_stream_push_token(s, tok);
2847 isl_set_free(dom);
2848 return NULL;
2849 }
2850
2851 /* Read an affine expression from "s".
2852 */
2853 __isl_give isl_aff *isl_stream_read_aff(struct isl_stream *s)
2854 {
2855 isl_aff *aff;
2856 isl_multi_aff *ma;
2857
2858 ma = isl_stream_read_multi_aff(s);
2859 if (!ma)
2860 return NULL;
2861 if (isl_multi_aff_dim(ma, isl_dim_out) != 1)
2862 isl_die(s->ctx, isl_error_invalid,
2863 "expecting single affine expression",
2864 goto error);
2865
2866 aff = isl_multi_aff_get_aff(ma, 0);
2867 isl_multi_aff_free(ma);
2868 return aff;
2869 error:
2870 isl_multi_aff_free(ma);
2871 return NULL;
2872 }
2873
2874 /* Read a piecewise affine expression from "s" with domain (space) "dom".
2875 */
2876 static __isl_give isl_pw_aff *read_pw_aff_with_dom(struct isl_stream *s,
2877 __isl_take isl_set *dom, struct vars *v)
2878 {
2879 isl_pw_aff *pwaff = NULL;
2880
2881 if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2882 goto error;
2883
2884 if (isl_stream_eat(s, '['))
2885 goto error;
2886
2887 pwaff = accept_affine(s, isl_set_get_space(dom), v);
2888
2889 if (isl_stream_eat(s, ']'))
2890 goto error;
2891
2892 dom = read_optional_formula(s, dom, v, 0);
2893 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2894
2895 return pwaff;
2896 error:
2897 isl_set_free(dom);
2898 isl_pw_aff_free(pwaff);
2899 return NULL;
2900 }
2901
2902 __isl_give isl_pw_aff *isl_stream_read_pw_aff(struct isl_stream *s)
2903 {
2904 struct vars *v;
2905 isl_set *dom = NULL;
2906 isl_set *aff_dom;
2907 isl_pw_aff *pa = NULL;
2908 int n;
2909
2910 v = vars_new(s->ctx);
2911 if (!v)
2912 return NULL;
2913
2914 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2915 if (next_is_tuple(s)) {
2916 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
2917 if (isl_stream_eat(s, ISL_TOKEN_TO))
2918 goto error;
2919 }
2920 if (isl_stream_eat(s, '{'))
2921 goto error;
2922
2923 n = v->n;
2924 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2925 pa = read_pw_aff_with_dom(s, aff_dom, v);
2926 vars_drop(v, v->n - n);
2927
2928 while (isl_stream_eat_if_available(s, ';')) {
2929 isl_pw_aff *pa_i;
2930
2931 n = v->n;
2932 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2933 pa_i = read_pw_aff_with_dom(s, aff_dom, v);
2934 vars_drop(v, v->n - n);
2935
2936 pa = isl_pw_aff_union_add(pa, pa_i);
2937 }
2938
2939 if (isl_stream_eat(s, '}'))
2940 goto error;
2941
2942 vars_free(v);
2943 isl_set_free(dom);
2944 return pa;
2945 error:
2946 vars_free(v);
2947 isl_set_free(dom);
2948 isl_pw_aff_free(pa);
2949 return NULL;
2950 }
2951
2952 __isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str)
2953 {
2954 isl_aff *aff;
2955 struct isl_stream *s = isl_stream_new_str(ctx, str);
2956 if (!s)
2957 return NULL;
2958 aff = isl_stream_read_aff(s);
2959 isl_stream_free(s);
2960 return aff;
2961 }
2962
2963 __isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str)
2964 {
2965 isl_pw_aff *pa;
2966 struct isl_stream *s = isl_stream_new_str(ctx, str);
2967 if (!s)
2968 return NULL;
2969 pa = isl_stream_read_pw_aff(s);
2970 isl_stream_free(s);
2971 return pa;
2972 }
2973
2974 /* Read an isl_pw_multi_aff from "s".
2975 * We currently read a generic object and if it turns out to be a set or
2976 * a map, we convert that to an isl_pw_multi_aff.
2977 * It would be more efficient if we were to construct the isl_pw_multi_aff
2978 * directly.
2979 */
2980 __isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(struct isl_stream *s)
2981 {
2982 struct isl_obj obj;
2983
2984 obj = obj_read(s);
2985 if (!obj.v)
2986 return NULL;
2987
2988 if (obj.type == isl_obj_map)
2989 return isl_pw_multi_aff_from_map(obj.v);
2990 if (obj.type == isl_obj_set)
2991 return isl_pw_multi_aff_from_set(obj.v);
2992
2993 obj.type->free(obj.v);
2994 isl_die(s->ctx, isl_error_invalid, "unexpected object type",
2995 return NULL);
2996 }
2997
2998 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx,
2999 const char *str)
3000 {
3001 isl_pw_multi_aff *pma;
3002 struct isl_stream *s = isl_stream_new_str(ctx, str);
3003 if (!s)
3004 return NULL;
3005 pma = isl_stream_read_pw_multi_aff(s);
3006 isl_stream_free(s);
3007 return pma;
3008 }
3009
3010 /* Read an isl_union_pw_multi_aff from "s".
3011 * We currently read a generic object and if it turns out to be a set or
3012 * a map, we convert that to an isl_union_pw_multi_aff.
3013 * It would be more efficient if we were to construct
3014 * the isl_union_pw_multi_aff directly.
3015 */
3016 __isl_give isl_union_pw_multi_aff *isl_stream_read_union_pw_multi_aff(
3017 struct isl_stream *s)
3018 {
3019 struct isl_obj obj;
3020
3021 obj = obj_read(s);
3022 if (!obj.v)
3023 return NULL;
3024
3025 if (obj.type == isl_obj_map || obj.type == isl_obj_set)
3026 obj = to_union(s->ctx, obj);
3027 if (obj.type == isl_obj_union_map)
3028 return isl_union_pw_multi_aff_from_union_map(obj.v);
3029 if (obj.type == isl_obj_union_set)
3030 return isl_union_pw_multi_aff_from_union_set(obj.v);
3031
3032 obj.type->free(obj.v);
3033 isl_die(s->ctx, isl_error_invalid, "unexpected object type",
3034 return NULL);
3035 }
3036
3037 /* Read an isl_union_pw_multi_aff from "str".
3038 */
3039 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_read_from_str(
3040 isl_ctx *ctx, const char *str)
3041 {
3042 isl_union_pw_multi_aff *upma;
3043 struct isl_stream *s = isl_stream_new_str(ctx, str);
3044 if (!s)
3045 return NULL;
3046 upma = isl_stream_read_union_pw_multi_aff(s);
3047 isl_stream_free(s);
3048 return upma;
3049 }
3050
3051 /* Assuming "pa" represents a single affine expression defined on a universe
3052 * domain, extract this affine expression.
3053 */
3054 static __isl_give isl_aff *aff_from_pw_aff(__isl_take isl_pw_aff *pa)
3055 {
3056 isl_aff *aff;
3057
3058 if (!pa)
3059 return NULL;
3060 if (pa->n != 1)
3061 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
3062 "expecting single affine expression",
3063 goto error);
3064 if (!isl_set_plain_is_universe(pa->p[0].set))
3065 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
3066 "expecting universe domain",
3067 goto error);
3068
3069 aff = isl_aff_copy(pa->p[0].aff);
3070 isl_pw_aff_free(pa);
3071 return aff;
3072 error:
3073 isl_pw_aff_free(pa);
3074 return NULL;
3075 }
3076
3077 /* Read a multi-affine expression from "s".
3078 * If the multi-affine expression has a domain, then then tuple
3079 * representing this domain cannot involve any affine expressions.
3080 * The tuple representing the actual expressions needs to consist
3081 * of only affine expressions. Moreover, these expressions can
3082 * only depend on parameters and input dimensions and not on other
3083 * output dimensions.
3084 */
3085 __isl_give isl_multi_aff *isl_stream_read_multi_aff(struct isl_stream *s)
3086 {
3087 struct vars *v;
3088 isl_set *dom = NULL;
3089 isl_multi_pw_aff *tuple = NULL;
3090 int dim, i, n;
3091 isl_space *space, *dom_space;
3092 isl_multi_aff *ma = NULL;
3093
3094 v = vars_new(s->ctx);
3095 if (!v)
3096 return NULL;
3097
3098 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3099 if (next_is_tuple(s)) {
3100 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3101 if (isl_stream_eat(s, ISL_TOKEN_TO))
3102 goto error;
3103 }
3104 if (!isl_set_plain_is_universe(dom))
3105 isl_die(s->ctx, isl_error_invalid,
3106 "expecting universe parameter domain", goto error);
3107 if (isl_stream_eat(s, '{'))
3108 goto error;
3109
3110 tuple = read_tuple(s, v, 0, 0);
3111 if (!tuple)
3112 goto error;
3113 if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {
3114 isl_set *set;
3115 isl_space *space;
3116 int has_expr;
3117
3118 has_expr = tuple_has_expr(tuple);
3119 if (has_expr < 0)
3120 goto error;
3121 if (has_expr)
3122 isl_die(s->ctx, isl_error_invalid,
3123 "expecting universe domain", goto error);
3124 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3125 set = isl_set_universe(space);
3126 dom = isl_set_intersect_params(set, dom);
3127 isl_multi_pw_aff_free(tuple);
3128 tuple = read_tuple(s, v, 0, 0);
3129 if (!tuple)
3130 goto error;
3131 }
3132
3133 if (isl_stream_eat(s, '}'))
3134 goto error;
3135
3136 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
3137 dim = isl_set_dim(dom, isl_dim_all);
3138 dom_space = isl_set_get_space(dom);
3139 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3140 space = isl_space_align_params(space, isl_space_copy(dom_space));
3141 if (!isl_space_is_params(dom_space))
3142 space = isl_space_map_from_domain_and_range(
3143 isl_space_copy(dom_space), space);
3144 isl_space_free(dom_space);
3145 ma = isl_multi_aff_alloc(space);
3146
3147 for (i = 0; i < n; ++i) {
3148 isl_pw_aff *pa;
3149 isl_aff *aff;
3150 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
3151 aff = aff_from_pw_aff(pa);
3152 if (!aff)
3153 goto error;
3154 if (isl_aff_involves_dims(aff, isl_dim_in, dim, i + 1)) {
3155 isl_aff_free(aff);
3156 isl_die(s->ctx, isl_error_invalid,
3157 "not an affine expression", goto error);
3158 }
3159 aff = isl_aff_drop_dims(aff, isl_dim_in, dim, n);
3160 space = isl_multi_aff_get_domain_space(ma);
3161 aff = isl_aff_reset_domain_space(aff, space);
3162 ma = isl_multi_aff_set_aff(ma, i, aff);
3163 }
3164
3165 isl_multi_pw_aff_free(tuple);
3166 vars_free(v);
3167 isl_set_free(dom);
3168 return ma;
3169 error:
3170 isl_multi_pw_aff_free(tuple);
3171 vars_free(v);
3172 isl_set_free(dom);
3173 isl_multi_aff_free(ma);
3174 return NULL;
3175 }
3176
3177 __isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx,
3178 const char *str)
3179 {
3180 isl_multi_aff *maff;
3181 struct isl_stream *s = isl_stream_new_str(ctx, str);
3182 if (!s)
3183 return NULL;
3184 maff = isl_stream_read_multi_aff(s);
3185 isl_stream_free(s);
3186 return maff;
3187 }
3188
3189 __isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial(
3190 struct isl_stream *s)
3191 {
3192 struct isl_obj obj;
3193
3194 obj = obj_read(s);
3195 if (obj.type == isl_obj_pw_qpolynomial) {
3196 obj.type = isl_obj_union_pw_qpolynomial;
3197 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
3198 }
3199 if (obj.v)
3200 isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial,
3201 goto error);
3202
3203 return obj.v;
3204 error:
3205 obj.type->free(obj.v);
3206 return NULL;
3207 }
3208
3209 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str(
3210 isl_ctx *ctx, const char *str)
3211 {
3212 isl_union_pw_qpolynomial *upwqp;
3213 struct isl_stream *s = isl_stream_new_str(ctx, str);
3214 if (!s)
3215 return NULL;
3216 upwqp = isl_stream_read_union_pw_qpolynomial(s);
3217 isl_stream_free(s);
3218 return upwqp;
3219 }
Integer set library