?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_ast_build_{access,call}_from_multi_pw_aff
[isl.git] / isl_input.c
blob463b8d23bcad10779da51575e8c1f6bbe5b3c9c9
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 /* Add the tuple represented by the isl_multi_pw_aff "tuple" to "map".
1245 * We first create the appropriate space in "map" based on the range
1246 * space of this isl_multi_pw_aff. Then, we add equalities based
1247 * on the affine expressions. These live in an anonymous space,
1248 * however, so we first need to reset the space to that of "map".
1249 */
1250 static __isl_give isl_map *map_from_tuple(__isl_take isl_multi_pw_aff *tuple,
1251 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
1252 int rational)
1253 {
1254 int i, n;
1255 isl_ctx *ctx;
1256 isl_space *space = NULL;
1257
1258 if (!map || !tuple)
1259 goto error;
1260 ctx = isl_multi_pw_aff_get_ctx(tuple);
1261 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
1262 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
1263 if (!space)
1264 goto error;
1265
1266 if (type == isl_dim_param) {
1267 if (isl_space_has_tuple_name(space, isl_dim_set) ||
1268 isl_space_is_wrapping(space)) {
1269 isl_die(ctx, isl_error_invalid,
1270 "parameter tuples cannot be named or nested",
1271 goto error);
1272 }
1273 map = isl_map_add_dims(map, type, n);
1274 for (i = 0; i < n; ++i) {
1275 isl_id *id;
1276 if (!isl_space_has_dim_name(space, isl_dim_set, i))
1277 isl_die(ctx, isl_error_invalid,
1278 "parameters must be named",
1279 goto error);
1280 id = isl_space_get_dim_id(space, isl_dim_set, i);
1281 map = isl_map_set_dim_id(map, isl_dim_param, i, id);
1282 }
1283 } else if (type == isl_dim_in) {
1284 isl_set *set;
1285
1286 set = isl_set_universe(isl_space_copy(space));
1287 if (rational)
1288 set = isl_set_set_rational(set);
1289 set = isl_set_intersect_params(set, isl_map_params(map));
1290 map = isl_map_from_domain(set);
1291 } else {
1292 isl_set *set;
1293
1294 set = isl_set_universe(isl_space_copy(space));
1295 if (rational)
1296 set = isl_set_set_rational(set);
1297 map = isl_map_from_domain_and_range(isl_map_domain(map), set);
1298 }
1299
1300 for (i = 0; i < n; ++i) {
1301 isl_pw_aff *pa;
1302 isl_space *space;
1303 isl_aff *aff;
1304 isl_set *set;
1305 isl_map *map_i;
1306
1307 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
1308 space = isl_pw_aff_get_domain_space(pa);
1309 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1310 aff = isl_aff_add_coefficient_si(aff,
1311 isl_dim_in, v->n - n + i, -1);
1312 pa = isl_pw_aff_add(pa, isl_pw_aff_from_aff(aff));
1313 if (rational)
1314 pa = isl_pw_aff_set_rational(pa);
1315 set = isl_pw_aff_zero_set(pa);
1316 map_i = isl_map_from_range(set);
1317 map_i = isl_map_reset_space(map_i, isl_map_get_space(map));
1318 map = isl_map_intersect(map, map_i);
1319 }
1320
1321 isl_space_free(space);
1322 isl_multi_pw_aff_free(tuple);
1323 return map;
1324 error:
1325 isl_space_free(space);
1326 isl_multi_pw_aff_free(tuple);
1327 isl_map_free(map);
1328 return NULL;
1329 }
1330
1331 /* Read a tuple from "s" and add it to "map".
1332 * The tuple is initially represented as an isl_multi_pw_aff and
1333 * then added to "map".
1334 */
1335 static __isl_give isl_map *read_map_tuple(struct isl_stream *s,
1336 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
1337 int rational, int comma)
1338 {
1339 isl_multi_pw_aff *tuple;
1340
1341 tuple = read_tuple(s, v, rational, comma);
1342 if (!tuple)
1343 return isl_map_free(map);
1344
1345 return map_from_tuple(tuple, map, type, v, rational);
1346 }
1347
1348 static __isl_give isl_set *construct_constraints(
1349 __isl_take isl_set *set, int type,
1350 __isl_keep isl_pw_aff_list *left, __isl_keep isl_pw_aff_list *right,
1351 int rational)
1352 {
1353 isl_set *cond;
1354
1355 left = isl_pw_aff_list_copy(left);
1356 right = isl_pw_aff_list_copy(right);
1357 if (rational) {
1358 left = isl_pw_aff_list_set_rational(left);
1359 right = isl_pw_aff_list_set_rational(right);
1360 }
1361 if (type == ISL_TOKEN_LE)
1362 cond = isl_pw_aff_list_le_set(left, right);
1363 else if (type == ISL_TOKEN_GE)
1364 cond = isl_pw_aff_list_ge_set(left, right);
1365 else if (type == ISL_TOKEN_LT)
1366 cond = isl_pw_aff_list_lt_set(left, right);
1367 else if (type == ISL_TOKEN_GT)
1368 cond = isl_pw_aff_list_gt_set(left, right);
1369 else if (type == ISL_TOKEN_NE)
1370 cond = isl_pw_aff_list_ne_set(left, right);
1371 else
1372 cond = isl_pw_aff_list_eq_set(left, right);
1373
1374 return isl_set_intersect(set, cond);
1375 }
1376
1377 static __isl_give isl_map *add_constraint(struct isl_stream *s,
1378 struct vars *v, __isl_take isl_map *map, int rational)
1379 {
1380 struct isl_token *tok = NULL;
1381 isl_pw_aff_list *list1 = NULL, *list2 = NULL;
1382 isl_set *set;
1383
1384 set = isl_map_wrap(map);
1385 list1 = accept_affine_list(s, isl_set_get_space(set), v);
1386 if (!list1)
1387 goto error;
1388 tok = isl_stream_next_token(s);
1389 if (!is_comparator(tok)) {
1390 isl_stream_error(s, tok, "missing operator");
1391 if (tok)
1392 isl_stream_push_token(s, tok);
1393 tok = NULL;
1394 goto error;
1395 }
1396 for (;;) {
1397 list2 = accept_affine_list(s, isl_set_get_space(set), v);
1398 if (!list2)
1399 goto error;
1400
1401 set = construct_constraints(set, tok->type, list1, list2,
1402 rational);
1403 isl_token_free(tok);
1404 isl_pw_aff_list_free(list1);
1405 list1 = list2;
1406
1407 tok = isl_stream_next_token(s);
1408 if (!is_comparator(tok)) {
1409 if (tok)
1410 isl_stream_push_token(s, tok);
1411 break;
1412 }
1413 }
1414 isl_pw_aff_list_free(list1);
1415
1416 return isl_set_unwrap(set);
1417 error:
1418 if (tok)
1419 isl_token_free(tok);
1420 isl_pw_aff_list_free(list1);
1421 isl_pw_aff_list_free(list2);
1422 isl_set_free(set);
1423 return NULL;
1424 }
1425
1426 static __isl_give isl_map *read_exists(struct isl_stream *s,
1427 struct vars *v, __isl_take isl_map *map, int rational)
1428 {
1429 int n = v->n;
1430 int seen_paren = isl_stream_eat_if_available(s, '(');
1431
1432 map = isl_map_from_domain(isl_map_wrap(map));
1433 map = read_defined_var_list(s, v, map, rational);
1434
1435 if (isl_stream_eat(s, ':'))
1436 goto error;
1437
1438 map = read_formula(s, v, map, rational);
1439 map = isl_set_unwrap(isl_map_domain(map));
1440
1441 vars_drop(v, v->n - n);
1442 if (seen_paren && isl_stream_eat(s, ')'))
1443 goto error;
1444
1445 return map;
1446 error:
1447 isl_map_free(map);
1448 return NULL;
1449 }
1450
1451 /* Parse an expression between parentheses and push the result
1452 * back on the stream.
1453 *
1454 * The parsed expression may be either an affine expression
1455 * or a condition. The first type is pushed onto the stream
1456 * as an isl_pw_aff, while the second is pushed as an isl_map.
1457 *
1458 * If the initial token indicates the start of a condition,
1459 * we parse it as such.
1460 * Otherwise, we first parse an affine expression and push
1461 * that onto the stream. If the affine expression covers the
1462 * entire expression between parentheses, we return.
1463 * Otherwise, we assume that the affine expression is the
1464 * start of a condition and continue parsing.
1465 */
1466 static int resolve_paren_expr(struct isl_stream *s,
1467 struct vars *v, __isl_take isl_map *map, int rational)
1468 {
1469 struct isl_token *tok, *tok2;
1470 int line, col;
1471 isl_pw_aff *pwaff;
1472
1473 tok = isl_stream_next_token(s);
1474 if (!tok || tok->type != '(')
1475 goto error;
1476
1477 if (isl_stream_next_token_is(s, '('))
1478 if (resolve_paren_expr(s, v, isl_map_copy(map), rational))
1479 goto error;
1480
1481 if (isl_stream_next_token_is(s, ISL_TOKEN_EXISTS) ||
1482 isl_stream_next_token_is(s, ISL_TOKEN_NOT) ||
1483 isl_stream_next_token_is(s, ISL_TOKEN_TRUE) ||
1484 isl_stream_next_token_is(s, ISL_TOKEN_FALSE) ||
1485 isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1486 map = read_formula(s, v, map, rational);
1487 if (isl_stream_eat(s, ')'))
1488 goto error;
1489 tok->type = ISL_TOKEN_MAP;
1490 tok->u.map = map;
1491 isl_stream_push_token(s, tok);
1492 return 0;
1493 }
1494
1495 tok2 = isl_stream_next_token(s);
1496 if (!tok2)
1497 goto error;
1498 line = tok2->line;
1499 col = tok2->col;
1500 isl_stream_push_token(s, tok2);
1501
1502 pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v);
1503 if (!pwaff)
1504 goto error;
1505
1506 tok2 = isl_token_new(s->ctx, line, col, 0);
1507 if (!tok2)
1508 goto error2;
1509 tok2->type = ISL_TOKEN_AFF;
1510 tok2->u.pwaff = pwaff;
1511
1512 if (isl_stream_eat_if_available(s, ')')) {
1513 isl_stream_push_token(s, tok2);
1514 isl_token_free(tok);
1515 isl_map_free(map);
1516 return 0;
1517 }
1518
1519 isl_stream_push_token(s, tok2);
1520
1521 map = read_formula(s, v, map, rational);
1522 if (isl_stream_eat(s, ')'))
1523 goto error;
1524
1525 tok->type = ISL_TOKEN_MAP;
1526 tok->u.map = map;
1527 isl_stream_push_token(s, tok);
1528
1529 return 0;
1530 error2:
1531 isl_pw_aff_free(pwaff);
1532 error:
1533 isl_token_free(tok);
1534 isl_map_free(map);
1535 return -1;
1536 }
1537
1538 static __isl_give isl_map *read_conjunct(struct isl_stream *s,
1539 struct vars *v, __isl_take isl_map *map, int rational)
1540 {
1541 if (isl_stream_next_token_is(s, '('))
1542 if (resolve_paren_expr(s, v, isl_map_copy(map), rational))
1543 goto error;
1544
1545 if (isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1546 struct isl_token *tok;
1547 tok = isl_stream_next_token(s);
1548 if (!tok)
1549 goto error;
1550 isl_map_free(map);
1551 map = isl_map_copy(tok->u.map);
1552 isl_token_free(tok);
1553 return map;
1554 }
1555
1556 if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))
1557 return read_exists(s, v, map, rational);
1558
1559 if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))
1560 return map;
1561
1562 if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) {
1563 isl_space *dim = isl_map_get_space(map);
1564 isl_map_free(map);
1565 return isl_map_empty(dim);
1566 }
1567
1568 return add_constraint(s, v, map, rational);
1569 error:
1570 isl_map_free(map);
1571 return NULL;
1572 }
1573
1574 static __isl_give isl_map *read_conjuncts(struct isl_stream *s,
1575 struct vars *v, __isl_take isl_map *map, int rational)
1576 {
1577 isl_map *res;
1578 int negate;
1579
1580 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1581 res = read_conjunct(s, v, isl_map_copy(map), rational);
1582 if (negate)
1583 res = isl_map_subtract(isl_map_copy(map), res);
1584
1585 while (res && isl_stream_eat_if_available(s, ISL_TOKEN_AND)) {
1586 isl_map *res_i;
1587
1588 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1589 res_i = read_conjunct(s, v, isl_map_copy(map), rational);
1590 if (negate)
1591 res = isl_map_subtract(res, res_i);
1592 else
1593 res = isl_map_intersect(res, res_i);
1594 }
1595
1596 isl_map_free(map);
1597 return res;
1598 }
1599
1600 static struct isl_map *read_disjuncts(struct isl_stream *s,
1601 struct vars *v, __isl_take isl_map *map, int rational)
1602 {
1603 isl_map *res;
1604
1605 if (isl_stream_next_token_is(s, '}')) {
1606 isl_space *dim = isl_map_get_space(map);
1607 isl_map_free(map);
1608 return isl_map_universe(dim);
1609 }
1610
1611 res = read_conjuncts(s, v, isl_map_copy(map), rational);
1612 while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
1613 isl_map *res_i;
1614
1615 res_i = read_conjuncts(s, v, isl_map_copy(map), rational);
1616 res = isl_map_union(res, res_i);
1617 }
1618
1619 isl_map_free(map);
1620 return res;
1621 }
1622
1623 /* Read a first order formula from "s", add the corresponding
1624 * constraints to "map" and return the result.
1625 *
1626 * In particular, read a formula of the form
1627 *
1628 * a
1629 *
1630 * or
1631 *
1632 * a implies b
1633 *
1634 * where a and b are disjunctions.
1635 *
1636 * In the first case, map is replaced by
1637 *
1638 * map \cap { [..] : a }
1639 *
1640 * In the second case, it is replaced by
1641 *
1642 * (map \setminus { [..] : a}) \cup (map \cap { [..] : b })
1643 */
1644 static __isl_give isl_map *read_formula(struct isl_stream *s,
1645 struct vars *v, __isl_take isl_map *map, int rational)
1646 {
1647 isl_map *res;
1648
1649 res = read_disjuncts(s, v, isl_map_copy(map), rational);
1650
1651 if (isl_stream_eat_if_available(s, ISL_TOKEN_IMPLIES)) {
1652 isl_map *res2;
1653
1654 res = isl_map_subtract(isl_map_copy(map), res);
1655 res2 = read_disjuncts(s, v, map, rational);
1656 res = isl_map_union(res, res2);
1657 } else
1658 isl_map_free(map);
1659
1660 return res;
1661 }
1662
1663 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1664 {
1665 if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1666 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1667 isl_basic_map_dim(bmap, isl_dim_in) + pos;
1668 pos -= isl_basic_map_dim(bmap, isl_dim_out);
1669
1670 if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1671 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1672 pos -= isl_basic_map_dim(bmap, isl_dim_in);
1673
1674 if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1675 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1676 isl_basic_map_dim(bmap, isl_dim_in) +
1677 isl_basic_map_dim(bmap, isl_dim_out) + pos;
1678 pos -= isl_basic_map_dim(bmap, isl_dim_div);
1679
1680 if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1681 return 1 + pos;
1682
1683 return 0;
1684 }
1685
1686 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1687 struct isl_stream *s, __isl_take isl_basic_map *bmap)
1688 {
1689 int j;
1690 struct isl_token *tok;
1691 int type;
1692 int k;
1693 isl_int *c;
1694 unsigned nparam;
1695 unsigned dim;
1696
1697 if (!bmap)
1698 return NULL;
1699
1700 nparam = isl_basic_map_dim(bmap, isl_dim_param);
1701 dim = isl_basic_map_dim(bmap, isl_dim_out);
1702
1703 tok = isl_stream_next_token(s);
1704 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1705 isl_stream_error(s, tok, "expecting coefficient");
1706 if (tok)
1707 isl_stream_push_token(s, tok);
1708 goto error;
1709 }
1710 if (!tok->on_new_line) {
1711 isl_stream_error(s, tok, "coefficient should appear on new line");
1712 isl_stream_push_token(s, tok);
1713 goto error;
1714 }
1715
1716 type = isl_int_get_si(tok->u.v);
1717 isl_token_free(tok);
1718
1719 isl_assert(s->ctx, type == 0 || type == 1, goto error);
1720 if (type == 0) {
1721 k = isl_basic_map_alloc_equality(bmap);
1722 c = bmap->eq[k];
1723 } else {
1724 k = isl_basic_map_alloc_inequality(bmap);
1725 c = bmap->ineq[k];
1726 }
1727 if (k < 0)
1728 goto error;
1729
1730 for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1731 int pos;
1732 tok = isl_stream_next_token(s);
1733 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1734 isl_stream_error(s, tok, "expecting coefficient");
1735 if (tok)
1736 isl_stream_push_token(s, tok);
1737 goto error;
1738 }
1739 if (tok->on_new_line) {
1740 isl_stream_error(s, tok,
1741 "coefficient should not appear on new line");
1742 isl_stream_push_token(s, tok);
1743 goto error;
1744 }
1745 pos = polylib_pos_to_isl_pos(bmap, j);
1746 isl_int_set(c[pos], tok->u.v);
1747 isl_token_free(tok);
1748 }
1749
1750 return bmap;
1751 error:
1752 isl_basic_map_free(bmap);
1753 return NULL;
1754 }
1755
1756 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s)
1757 {
1758 int i;
1759 struct isl_token *tok;
1760 struct isl_token *tok2;
1761 int n_row, n_col;
1762 int on_new_line;
1763 unsigned in = 0, out, local = 0;
1764 struct isl_basic_map *bmap = NULL;
1765 int nparam = 0;
1766
1767 tok = isl_stream_next_token(s);
1768 if (!tok) {
1769 isl_stream_error(s, NULL, "unexpected EOF");
1770 return NULL;
1771 }
1772 tok2 = isl_stream_next_token(s);
1773 if (!tok2) {
1774 isl_token_free(tok);
1775 isl_stream_error(s, NULL, "unexpected EOF");
1776 return NULL;
1777 }
1778 if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1779 isl_stream_push_token(s, tok2);
1780 isl_stream_push_token(s, tok);
1781 isl_stream_error(s, NULL,
1782 "expecting constraint matrix dimensions");
1783 return NULL;
1784 }
1785 n_row = isl_int_get_si(tok->u.v);
1786 n_col = isl_int_get_si(tok2->u.v);
1787 on_new_line = tok2->on_new_line;
1788 isl_token_free(tok2);
1789 isl_token_free(tok);
1790 isl_assert(s->ctx, !on_new_line, return NULL);
1791 isl_assert(s->ctx, n_row >= 0, return NULL);
1792 isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1793 tok = isl_stream_next_token_on_same_line(s);
1794 if (tok) {
1795 if (tok->type != ISL_TOKEN_VALUE) {
1796 isl_stream_error(s, tok,
1797 "expecting number of output dimensions");
1798 isl_stream_push_token(s, tok);
1799 goto error;
1800 }
1801 out = isl_int_get_si(tok->u.v);
1802 isl_token_free(tok);
1803
1804 tok = isl_stream_next_token_on_same_line(s);
1805 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1806 isl_stream_error(s, tok,
1807 "expecting number of input dimensions");
1808 if (tok)
1809 isl_stream_push_token(s, tok);
1810 goto error;
1811 }
1812 in = isl_int_get_si(tok->u.v);
1813 isl_token_free(tok);
1814
1815 tok = isl_stream_next_token_on_same_line(s);
1816 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1817 isl_stream_error(s, tok,
1818 "expecting number of existentials");
1819 if (tok)
1820 isl_stream_push_token(s, tok);
1821 goto error;
1822 }
1823 local = isl_int_get_si(tok->u.v);
1824 isl_token_free(tok);
1825
1826 tok = isl_stream_next_token_on_same_line(s);
1827 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1828 isl_stream_error(s, tok,
1829 "expecting number of parameters");
1830 if (tok)
1831 isl_stream_push_token(s, tok);
1832 goto error;
1833 }
1834 nparam = isl_int_get_si(tok->u.v);
1835 isl_token_free(tok);
1836 if (n_col != 1 + out + in + local + nparam + 1) {
1837 isl_stream_error(s, NULL,
1838 "dimensions don't match");
1839 goto error;
1840 }
1841 } else
1842 out = n_col - 2 - nparam;
1843 bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1844 if (!bmap)
1845 return NULL;
1846
1847 for (i = 0; i < local; ++i) {
1848 int k = isl_basic_map_alloc_div(bmap);
1849 if (k < 0)
1850 goto error;
1851 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1852 }
1853
1854 for (i = 0; i < n_row; ++i)
1855 bmap = basic_map_read_polylib_constraint(s, bmap);
1856
1857 tok = isl_stream_next_token_on_same_line(s);
1858 if (tok) {
1859 isl_stream_error(s, tok, "unexpected extra token on line");
1860 isl_stream_push_token(s, tok);
1861 goto error;
1862 }
1863
1864 bmap = isl_basic_map_simplify(bmap);
1865 bmap = isl_basic_map_finalize(bmap);
1866 return bmap;
1867 error:
1868 isl_basic_map_free(bmap);
1869 return NULL;
1870 }
1871
1872 static struct isl_map *map_read_polylib(struct isl_stream *s)
1873 {
1874 struct isl_token *tok;
1875 struct isl_token *tok2;
1876 int i, n;
1877 struct isl_map *map;
1878
1879 tok = isl_stream_next_token(s);
1880 if (!tok) {
1881 isl_stream_error(s, NULL, "unexpected EOF");
1882 return NULL;
1883 }
1884 tok2 = isl_stream_next_token_on_same_line(s);
1885 if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
1886 isl_stream_push_token(s, tok2);
1887 isl_stream_push_token(s, tok);
1888 return isl_map_from_basic_map(basic_map_read_polylib(s));
1889 }
1890 if (tok2) {
1891 isl_stream_error(s, tok2, "unexpected token");
1892 isl_stream_push_token(s, tok2);
1893 isl_stream_push_token(s, tok);
1894 return NULL;
1895 }
1896 n = isl_int_get_si(tok->u.v);
1897 isl_token_free(tok);
1898
1899 isl_assert(s->ctx, n >= 1, return NULL);
1900
1901 map = isl_map_from_basic_map(basic_map_read_polylib(s));
1902
1903 for (i = 1; map && i < n; ++i)
1904 map = isl_map_union(map,
1905 isl_map_from_basic_map(basic_map_read_polylib(s)));
1906
1907 return map;
1908 }
1909
1910 static int optional_power(struct isl_stream *s)
1911 {
1912 int pow;
1913 struct isl_token *tok;
1914
1915 tok = isl_stream_next_token(s);
1916 if (!tok)
1917 return 1;
1918 if (tok->type != '^') {
1919 isl_stream_push_token(s, tok);
1920 return 1;
1921 }
1922 isl_token_free(tok);
1923 tok = isl_stream_next_token(s);
1924 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1925 isl_stream_error(s, tok, "expecting exponent");
1926 if (tok)
1927 isl_stream_push_token(s, tok);
1928 return 1;
1929 }
1930 pow = isl_int_get_si(tok->u.v);
1931 isl_token_free(tok);
1932 return pow;
1933 }
1934
1935 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1936 __isl_keep isl_map *map, struct vars *v);
1937
1938 static __isl_give isl_pw_qpolynomial *read_factor(struct isl_stream *s,
1939 __isl_keep isl_map *map, struct vars *v)
1940 {
1941 isl_pw_qpolynomial *pwqp;
1942 struct isl_token *tok;
1943
1944 tok = next_token(s);
1945 if (!tok) {
1946 isl_stream_error(s, NULL, "unexpected EOF");
1947 return NULL;
1948 }
1949 if (tok->type == '(') {
1950 int pow;
1951
1952 isl_token_free(tok);
1953 pwqp = read_term(s, map, v);
1954 if (!pwqp)
1955 return NULL;
1956 if (isl_stream_eat(s, ')'))
1957 goto error;
1958 pow = optional_power(s);
1959 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1960 } else if (tok->type == ISL_TOKEN_VALUE) {
1961 struct isl_token *tok2;
1962 isl_qpolynomial *qp;
1963
1964 tok2 = isl_stream_next_token(s);
1965 if (tok2 && tok2->type == '/') {
1966 isl_token_free(tok2);
1967 tok2 = next_token(s);
1968 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1969 isl_stream_error(s, tok2, "expected denominator");
1970 isl_token_free(tok);
1971 isl_token_free(tok2);
1972 return NULL;
1973 }
1974 qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map),
1975 tok->u.v, tok2->u.v);
1976 isl_token_free(tok2);
1977 } else {
1978 isl_stream_push_token(s, tok2);
1979 qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map),
1980 tok->u.v);
1981 }
1982 isl_token_free(tok);
1983 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1984 } else if (tok->type == ISL_TOKEN_INFTY) {
1985 isl_qpolynomial *qp;
1986 isl_token_free(tok);
1987 qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map));
1988 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1989 } else if (tok->type == ISL_TOKEN_NAN) {
1990 isl_qpolynomial *qp;
1991 isl_token_free(tok);
1992 qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map));
1993 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1994 } else if (tok->type == ISL_TOKEN_IDENT) {
1995 int n = v->n;
1996 int pos = vars_pos(v, tok->u.s, -1);
1997 int pow;
1998 isl_qpolynomial *qp;
1999 if (pos < 0) {
2000 isl_token_free(tok);
2001 return NULL;
2002 }
2003 if (pos >= n) {
2004 vars_drop(v, v->n - n);
2005 isl_stream_error(s, tok, "unknown identifier");
2006 isl_token_free(tok);
2007 return NULL;
2008 }
2009 isl_token_free(tok);
2010 pow = optional_power(s);
2011 qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow);
2012 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2013 } else if (is_start_of_div(tok)) {
2014 isl_pw_aff *pwaff;
2015 int pow;
2016
2017 isl_stream_push_token(s, tok);
2018 pwaff = accept_div(s, isl_map_get_space(map), v);
2019 pow = optional_power(s);
2020 pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff);
2021 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
2022 } else if (tok->type == '-') {
2023 isl_token_free(tok);
2024 pwqp = read_factor(s, map, v);
2025 pwqp = isl_pw_qpolynomial_neg(pwqp);
2026 } else {
2027 isl_stream_error(s, tok, "unexpected isl_token");
2028 isl_stream_push_token(s, tok);
2029 return NULL;
2030 }
2031
2032 if (isl_stream_eat_if_available(s, '*') ||
2033 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
2034 isl_pw_qpolynomial *pwqp2;
2035
2036 pwqp2 = read_factor(s, map, v);
2037 pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2);
2038 }
2039
2040 return pwqp;
2041 error:
2042 isl_pw_qpolynomial_free(pwqp);
2043 return NULL;
2044 }
2045
2046 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
2047 __isl_keep isl_map *map, struct vars *v)
2048 {
2049 struct isl_token *tok;
2050 isl_pw_qpolynomial *pwqp;
2051
2052 pwqp = read_factor(s, map, v);
2053
2054 for (;;) {
2055 tok = next_token(s);
2056 if (!tok)
2057 return pwqp;
2058
2059 if (tok->type == '+') {
2060 isl_pw_qpolynomial *pwqp2;
2061
2062 isl_token_free(tok);
2063 pwqp2 = read_factor(s, map, v);
2064 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
2065 } else if (tok->type == '-') {
2066 isl_pw_qpolynomial *pwqp2;
2067
2068 isl_token_free(tok);
2069 pwqp2 = read_factor(s, map, v);
2070 pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2);
2071 } else if (tok->type == ISL_TOKEN_VALUE &&
2072 isl_int_is_neg(tok->u.v)) {
2073 isl_pw_qpolynomial *pwqp2;
2074
2075 isl_stream_push_token(s, tok);
2076 pwqp2 = read_factor(s, map, v);
2077 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
2078 } else {
2079 isl_stream_push_token(s, tok);
2080 break;
2081 }
2082 }
2083
2084 return pwqp;
2085 }
2086
2087 static __isl_give isl_map *read_optional_formula(struct isl_stream *s,
2088 __isl_take isl_map *map, struct vars *v, int rational)
2089 {
2090 struct isl_token *tok;
2091
2092 tok = isl_stream_next_token(s);
2093 if (!tok) {
2094 isl_stream_error(s, NULL, "unexpected EOF");
2095 goto error;
2096 }
2097 if (tok->type == ':' ||
2098 (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {
2099 isl_token_free(tok);
2100 map = read_formula(s, v, map, rational);
2101 } else
2102 isl_stream_push_token(s, tok);
2103
2104 return map;
2105 error:
2106 isl_map_free(map);
2107 return NULL;
2108 }
2109
2110 static struct isl_obj obj_read_poly(struct isl_stream *s,
2111 __isl_take isl_map *map, struct vars *v, int n)
2112 {
2113 struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
2114 isl_pw_qpolynomial *pwqp;
2115 struct isl_set *set;
2116
2117 pwqp = read_term(s, map, v);
2118 map = read_optional_formula(s, map, v, 0);
2119 set = isl_map_range(map);
2120
2121 pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set);
2122
2123 vars_drop(v, v->n - n);
2124
2125 obj.v = pwqp;
2126 return obj;
2127 }
2128
2129 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
2130 __isl_take isl_set *set, struct vars *v, int n)
2131 {
2132 struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
2133 isl_pw_qpolynomial *pwqp;
2134 isl_pw_qpolynomial_fold *pwf = NULL;
2135
2136 if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
2137 return obj_read_poly(s, set, v, n);
2138
2139 if (isl_stream_eat(s, '('))
2140 goto error;
2141
2142 pwqp = read_term(s, set, v);
2143 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, pwqp);
2144
2145 while (isl_stream_eat_if_available(s, ',')) {
2146 isl_pw_qpolynomial_fold *pwf_i;
2147 pwqp = read_term(s, set, v);
2148 pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max,
2149 pwqp);
2150 pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i);
2151 }
2152
2153 if (isl_stream_eat(s, ')'))
2154 goto error;
2155
2156 set = read_optional_formula(s, set, v, 0);
2157 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set);
2158
2159 vars_drop(v, v->n - n);
2160
2161 obj.v = pwf;
2162 return obj;
2163 error:
2164 isl_set_free(set);
2165 isl_pw_qpolynomial_fold_free(pwf);
2166 obj.type = isl_obj_none;
2167 return obj;
2168 }
2169
2170 static int is_rational(struct isl_stream *s)
2171 {
2172 struct isl_token *tok;
2173
2174 tok = isl_stream_next_token(s);
2175 if (!tok)
2176 return 0;
2177 if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) {
2178 isl_token_free(tok);
2179 isl_stream_eat(s, ':');
2180 return 1;
2181 }
2182
2183 isl_stream_push_token(s, tok);
2184
2185 return 0;
2186 }
2187
2188 static struct isl_obj obj_read_body(struct isl_stream *s,
2189 __isl_take isl_map *map, struct vars *v)
2190 {
2191 struct isl_token *tok;
2192 struct isl_obj obj = { isl_obj_set, NULL };
2193 int n = v->n;
2194 int rational;
2195
2196 rational = is_rational(s);
2197 if (rational)
2198 map = isl_map_set_rational(map);
2199
2200 if (isl_stream_next_token_is(s, ':')) {
2201 obj.type = isl_obj_set;
2202 obj.v = read_optional_formula(s, map, v, rational);
2203 return obj;
2204 }
2205
2206 if (!next_is_tuple(s))
2207 return obj_read_poly_or_fold(s, map, v, n);
2208
2209 map = read_map_tuple(s, map, isl_dim_in, v, rational, 0);
2210 if (!map)
2211 goto error;
2212 tok = isl_stream_next_token(s);
2213 if (!tok)
2214 goto error;
2215 if (tok->type == ISL_TOKEN_TO) {
2216 obj.type = isl_obj_map;
2217 isl_token_free(tok);
2218 if (!next_is_tuple(s)) {
2219 isl_set *set = isl_map_domain(map);
2220 return obj_read_poly_or_fold(s, set, v, n);
2221 }
2222 map = read_map_tuple(s, map, isl_dim_out, v, rational, 0);
2223 if (!map)
2224 goto error;
2225 } else {
2226 map = isl_map_domain(map);
2227 isl_stream_push_token(s, tok);
2228 }
2229
2230 map = read_optional_formula(s, map, v, rational);
2231
2232 vars_drop(v, v->n - n);
2233
2234 obj.v = map;
2235 return obj;
2236 error:
2237 isl_map_free(map);
2238 obj.type = isl_obj_none;
2239 return obj;
2240 }
2241
2242 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
2243 {
2244 if (obj.type == isl_obj_map) {
2245 obj.v = isl_union_map_from_map(obj.v);
2246 obj.type = isl_obj_union_map;
2247 } else if (obj.type == isl_obj_set) {
2248 obj.v = isl_union_set_from_set(obj.v);
2249 obj.type = isl_obj_union_set;
2250 } else if (obj.type == isl_obj_pw_qpolynomial) {
2251 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2252 obj.type = isl_obj_union_pw_qpolynomial;
2253 } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
2254 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
2255 obj.type = isl_obj_union_pw_qpolynomial_fold;
2256 } else
2257 isl_assert(ctx, 0, goto error);
2258 return obj;
2259 error:
2260 obj.type->free(obj.v);
2261 obj.type = isl_obj_none;
2262 return obj;
2263 }
2264
2265 static struct isl_obj obj_add(struct isl_ctx *ctx,
2266 struct isl_obj obj1, struct isl_obj obj2)
2267 {
2268 if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
2269 obj1 = to_union(ctx, obj1);
2270 if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
2271 obj2 = to_union(ctx, obj2);
2272 if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
2273 obj1 = to_union(ctx, obj1);
2274 if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
2275 obj2 = to_union(ctx, obj2);
2276 if (obj1.type == isl_obj_pw_qpolynomial &&
2277 obj2.type == isl_obj_union_pw_qpolynomial)
2278 obj1 = to_union(ctx, obj1);
2279 if (obj1.type == isl_obj_union_pw_qpolynomial &&
2280 obj2.type == isl_obj_pw_qpolynomial)
2281 obj2 = to_union(ctx, obj2);
2282 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2283 obj2.type == isl_obj_union_pw_qpolynomial_fold)
2284 obj1 = to_union(ctx, obj1);
2285 if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
2286 obj2.type == isl_obj_pw_qpolynomial_fold)
2287 obj2 = to_union(ctx, obj2);
2288 isl_assert(ctx, obj1.type == obj2.type, goto error);
2289 if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) {
2290 obj1 = to_union(ctx, obj1);
2291 obj2 = to_union(ctx, obj2);
2292 }
2293 if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) {
2294 obj1 = to_union(ctx, obj1);
2295 obj2 = to_union(ctx, obj2);
2296 }
2297 if (obj1.type == isl_obj_pw_qpolynomial &&
2298 !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) {
2299 obj1 = to_union(ctx, obj1);
2300 obj2 = to_union(ctx, obj2);
2301 }
2302 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2303 !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) {
2304 obj1 = to_union(ctx, obj1);
2305 obj2 = to_union(ctx, obj2);
2306 }
2307 obj1.v = obj1.type->add(obj1.v, obj2.v);
2308 return obj1;
2309 error:
2310 obj1.type->free(obj1.v);
2311 obj2.type->free(obj2.v);
2312 obj1.type = isl_obj_none;
2313 obj1.v = NULL;
2314 return obj1;
2315 }
2316
2317 static struct isl_obj obj_read(struct isl_stream *s)
2318 {
2319 isl_map *map = NULL;
2320 struct isl_token *tok;
2321 struct vars *v = NULL;
2322 struct isl_obj obj = { isl_obj_set, NULL };
2323
2324 tok = next_token(s);
2325 if (!tok) {
2326 isl_stream_error(s, NULL, "unexpected EOF");
2327 goto error;
2328 }
2329 if (tok->type == ISL_TOKEN_VALUE) {
2330 struct isl_token *tok2;
2331 struct isl_map *map;
2332
2333 tok2 = isl_stream_next_token(s);
2334 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
2335 isl_int_is_neg(tok2->u.v)) {
2336 if (tok2)
2337 isl_stream_push_token(s, tok2);
2338 obj.type = isl_obj_val;
2339 obj.v = isl_val_int_from_isl_int(s->ctx, tok->u.v);
2340 isl_token_free(tok);
2341 return obj;
2342 }
2343 isl_stream_push_token(s, tok2);
2344 isl_stream_push_token(s, tok);
2345 map = map_read_polylib(s);
2346 if (!map)
2347 goto error;
2348 if (isl_map_may_be_set(map))
2349 obj.v = isl_map_range(map);
2350 else {
2351 obj.type = isl_obj_map;
2352 obj.v = map;
2353 }
2354 return obj;
2355 }
2356 v = vars_new(s->ctx);
2357 if (!v) {
2358 isl_stream_push_token(s, tok);
2359 goto error;
2360 }
2361 map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));
2362 if (tok->type == '[') {
2363 isl_stream_push_token(s, tok);
2364 map = read_map_tuple(s, map, isl_dim_param, v, 0, 0);
2365 if (!map)
2366 goto error;
2367 tok = isl_stream_next_token(s);
2368 if (!tok || tok->type != ISL_TOKEN_TO) {
2369 isl_stream_error(s, tok, "expecting '->'");
2370 if (tok)
2371 isl_stream_push_token(s, tok);
2372 goto error;
2373 }
2374 isl_token_free(tok);
2375 tok = isl_stream_next_token(s);
2376 }
2377 if (!tok || tok->type != '{') {
2378 isl_stream_error(s, tok, "expecting '{'");
2379 if (tok)
2380 isl_stream_push_token(s, tok);
2381 goto error;
2382 }
2383 isl_token_free(tok);
2384
2385 tok = isl_stream_next_token(s);
2386 if (!tok)
2387 ;
2388 else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
2389 isl_token_free(tok);
2390 if (isl_stream_eat(s, '='))
2391 goto error;
2392 map = read_map_tuple(s, map, isl_dim_param, v, 0, 1);
2393 if (!map)
2394 goto error;
2395 } else if (tok->type == '}') {
2396 obj.type = isl_obj_union_set;
2397 obj.v = isl_union_set_empty(isl_map_get_space(map));
2398 isl_token_free(tok);
2399 goto done;
2400 } else
2401 isl_stream_push_token(s, tok);
2402
2403 for (;;) {
2404 struct isl_obj o;
2405 tok = NULL;
2406 o = obj_read_body(s, isl_map_copy(map), v);
2407 if (o.type == isl_obj_none || !o.v)
2408 goto error;
2409 if (!obj.v)
2410 obj = o;
2411 else {
2412 obj = obj_add(s->ctx, obj, o);
2413 if (obj.type == isl_obj_none || !obj.v)
2414 goto error;
2415 }
2416 tok = isl_stream_next_token(s);
2417 if (!tok || tok->type != ';')
2418 break;
2419 isl_token_free(tok);
2420 if (isl_stream_next_token_is(s, '}')) {
2421 tok = isl_stream_next_token(s);
2422 break;
2423 }
2424 }
2425
2426 if (tok && tok->type == '}') {
2427 isl_token_free(tok);
2428 } else {
2429 isl_stream_error(s, tok, "unexpected isl_token");
2430 if (tok)
2431 isl_token_free(tok);
2432 goto error;
2433 }
2434 done:
2435 vars_free(v);
2436 isl_map_free(map);
2437
2438 return obj;
2439 error:
2440 isl_map_free(map);
2441 obj.type->free(obj.v);
2442 if (v)
2443 vars_free(v);
2444 obj.v = NULL;
2445 return obj;
2446 }
2447
2448 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
2449 {
2450 return obj_read(s);
2451 }
2452
2453 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s)
2454 {
2455 struct isl_obj obj;
2456
2457 obj = obj_read(s);
2458 if (obj.v)
2459 isl_assert(s->ctx, obj.type == isl_obj_map ||
2460 obj.type == isl_obj_set, goto error);
2461
2462 if (obj.type == isl_obj_set)
2463 obj.v = isl_map_from_range(obj.v);
2464
2465 return obj.v;
2466 error:
2467 obj.type->free(obj.v);
2468 return NULL;
2469 }
2470
2471 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s)
2472 {
2473 struct isl_obj obj;
2474
2475 obj = obj_read(s);
2476 if (obj.v) {
2477 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) {
2478 obj.v = isl_map_range(obj.v);
2479 obj.type = isl_obj_set;
2480 }
2481 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2482 }
2483
2484 return obj.v;
2485 error:
2486 obj.type->free(obj.v);
2487 return NULL;
2488 }
2489
2490 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2491 {
2492 struct isl_obj obj;
2493
2494 obj = obj_read(s);
2495 if (obj.type == isl_obj_map) {
2496 obj.type = isl_obj_union_map;
2497 obj.v = isl_union_map_from_map(obj.v);
2498 }
2499 if (obj.type == isl_obj_set) {
2500 obj.type = isl_obj_union_set;
2501 obj.v = isl_union_set_from_set(obj.v);
2502 }
2503 if (obj.v && obj.type == isl_obj_union_set &&
2504 isl_union_set_is_empty(obj.v))
2505 obj.type = isl_obj_union_map;
2506 if (obj.v && obj.type != isl_obj_union_map)
2507 isl_die(s->ctx, isl_error_invalid, "invalid input", goto error);
2508
2509 return obj.v;
2510 error:
2511 obj.type->free(obj.v);
2512 return NULL;
2513 }
2514
2515 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2516 {
2517 struct isl_obj obj;
2518
2519 obj = obj_read(s);
2520 if (obj.type == isl_obj_set) {
2521 obj.type = isl_obj_union_set;
2522 obj.v = isl_union_set_from_set(obj.v);
2523 }
2524 if (obj.v)
2525 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2526
2527 return obj.v;
2528 error:
2529 obj.type->free(obj.v);
2530 return NULL;
2531 }
2532
2533 static __isl_give isl_basic_map *basic_map_read(struct isl_stream *s)
2534 {
2535 struct isl_obj obj;
2536 struct isl_map *map;
2537 struct isl_basic_map *bmap;
2538
2539 obj = obj_read(s);
2540 map = obj.v;
2541 if (!map)
2542 return NULL;
2543
2544 isl_assert(map->ctx, map->n <= 1, goto error);
2545
2546 if (map->n == 0)
2547 bmap = isl_basic_map_empty_like_map(map);
2548 else
2549 bmap = isl_basic_map_copy(map->p[0]);
2550
2551 isl_map_free(map);
2552
2553 return bmap;
2554 error:
2555 isl_map_free(map);
2556 return NULL;
2557 }
2558
2559 static __isl_give isl_basic_set *basic_set_read(struct isl_stream *s)
2560 {
2561 isl_basic_map *bmap;
2562 bmap = basic_map_read(s);
2563 if (!bmap)
2564 return NULL;
2565 if (!isl_basic_map_may_be_set(bmap))
2566 isl_die(s->ctx, isl_error_invalid,
2567 "input is not a set", goto error);
2568 return isl_basic_map_range(bmap);
2569 error:
2570 isl_basic_map_free(bmap);
2571 return NULL;
2572 }
2573
2574 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2575 FILE *input)
2576 {
2577 struct isl_basic_map *bmap;
2578 struct isl_stream *s = isl_stream_new_file(ctx, input);
2579 if (!s)
2580 return NULL;
2581 bmap = basic_map_read(s);
2582 isl_stream_free(s);
2583 return bmap;
2584 }
2585
2586 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2587 FILE *input)
2588 {
2589 isl_basic_set *bset;
2590 struct isl_stream *s = isl_stream_new_file(ctx, input);
2591 if (!s)
2592 return NULL;
2593 bset = basic_set_read(s);
2594 isl_stream_free(s);
2595 return bset;
2596 }
2597
2598 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2599 const char *str)
2600 {
2601 struct isl_basic_map *bmap;
2602 struct isl_stream *s = isl_stream_new_str(ctx, str);
2603 if (!s)
2604 return NULL;
2605 bmap = basic_map_read(s);
2606 isl_stream_free(s);
2607 return bmap;
2608 }
2609
2610 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2611 const char *str)
2612 {
2613 isl_basic_set *bset;
2614 struct isl_stream *s = isl_stream_new_str(ctx, str);
2615 if (!s)
2616 return NULL;
2617 bset = basic_set_read(s);
2618 isl_stream_free(s);
2619 return bset;
2620 }
2621
2622 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2623 FILE *input)
2624 {
2625 struct isl_map *map;
2626 struct isl_stream *s = isl_stream_new_file(ctx, input);
2627 if (!s)
2628 return NULL;
2629 map = isl_stream_read_map(s);
2630 isl_stream_free(s);
2631 return map;
2632 }
2633
2634 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2635 const char *str)
2636 {
2637 struct isl_map *map;
2638 struct isl_stream *s = isl_stream_new_str(ctx, str);
2639 if (!s)
2640 return NULL;
2641 map = isl_stream_read_map(s);
2642 isl_stream_free(s);
2643 return map;
2644 }
2645
2646 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2647 FILE *input)
2648 {
2649 isl_set *set;
2650 struct isl_stream *s = isl_stream_new_file(ctx, input);
2651 if (!s)
2652 return NULL;
2653 set = isl_stream_read_set(s);
2654 isl_stream_free(s);
2655 return set;
2656 }
2657
2658 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2659 const char *str)
2660 {
2661 isl_set *set;
2662 struct isl_stream *s = isl_stream_new_str(ctx, str);
2663 if (!s)
2664 return NULL;
2665 set = isl_stream_read_set(s);
2666 isl_stream_free(s);
2667 return set;
2668 }
2669
2670 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2671 FILE *input)
2672 {
2673 isl_union_map *umap;
2674 struct isl_stream *s = isl_stream_new_file(ctx, input);
2675 if (!s)
2676 return NULL;
2677 umap = isl_stream_read_union_map(s);
2678 isl_stream_free(s);
2679 return umap;
2680 }
2681
2682 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2683 const char *str)
2684 {
2685 isl_union_map *umap;
2686 struct isl_stream *s = isl_stream_new_str(ctx, str);
2687 if (!s)
2688 return NULL;
2689 umap = isl_stream_read_union_map(s);
2690 isl_stream_free(s);
2691 return umap;
2692 }
2693
2694 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2695 FILE *input)
2696 {
2697 isl_union_set *uset;
2698 struct isl_stream *s = isl_stream_new_file(ctx, input);
2699 if (!s)
2700 return NULL;
2701 uset = isl_stream_read_union_set(s);
2702 isl_stream_free(s);
2703 return uset;
2704 }
2705
2706 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2707 const char *str)
2708 {
2709 isl_union_set *uset;
2710 struct isl_stream *s = isl_stream_new_str(ctx, str);
2711 if (!s)
2712 return NULL;
2713 uset = isl_stream_read_union_set(s);
2714 isl_stream_free(s);
2715 return uset;
2716 }
2717
2718 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2719 {
2720 struct isl_vec *vec = NULL;
2721 struct isl_token *tok;
2722 unsigned size;
2723 int j;
2724
2725 tok = isl_stream_next_token(s);
2726 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2727 isl_stream_error(s, tok, "expecting vector length");
2728 goto error;
2729 }
2730
2731 size = isl_int_get_si(tok->u.v);
2732 isl_token_free(tok);
2733
2734 vec = isl_vec_alloc(s->ctx, size);
2735
2736 for (j = 0; j < size; ++j) {
2737 tok = isl_stream_next_token(s);
2738 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2739 isl_stream_error(s, tok, "expecting constant value");
2740 goto error;
2741 }
2742 isl_int_set(vec->el[j], tok->u.v);
2743 isl_token_free(tok);
2744 }
2745
2746 return vec;
2747 error:
2748 isl_token_free(tok);
2749 isl_vec_free(vec);
2750 return NULL;
2751 }
2752
2753 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2754 {
2755 return isl_vec_read_polylib(s);
2756 }
2757
2758 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2759 {
2760 isl_vec *v;
2761 struct isl_stream *s = isl_stream_new_file(ctx, input);
2762 if (!s)
2763 return NULL;
2764 v = vec_read(s);
2765 isl_stream_free(s);
2766 return v;
2767 }
2768
2769 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2770 struct isl_stream *s)
2771 {
2772 struct isl_obj obj;
2773
2774 obj = obj_read(s);
2775 if (obj.v)
2776 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2777 goto error);
2778
2779 return obj.v;
2780 error:
2781 obj.type->free(obj.v);
2782 return NULL;
2783 }
2784
2785 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2786 const char *str)
2787 {
2788 isl_pw_qpolynomial *pwqp;
2789 struct isl_stream *s = isl_stream_new_str(ctx, str);
2790 if (!s)
2791 return NULL;
2792 pwqp = isl_stream_read_pw_qpolynomial(s);
2793 isl_stream_free(s);
2794 return pwqp;
2795 }
2796
2797 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
2798 FILE *input)
2799 {
2800 isl_pw_qpolynomial *pwqp;
2801 struct isl_stream *s = isl_stream_new_file(ctx, input);
2802 if (!s)
2803 return NULL;
2804 pwqp = isl_stream_read_pw_qpolynomial(s);
2805 isl_stream_free(s);
2806 return pwqp;
2807 }
2808
2809 /* Is the next token an identifer not in "v"?
2810 */
2811 static int next_is_fresh_ident(struct isl_stream *s, struct vars *v)
2812 {
2813 int n = v->n;
2814 int fresh;
2815 struct isl_token *tok;
2816
2817 tok = isl_stream_next_token(s);
2818 if (!tok)
2819 return 0;
2820 fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n;
2821 isl_stream_push_token(s, tok);
2822
2823 vars_drop(v, v->n - n);
2824
2825 return fresh;
2826 }
2827
2828 /* First read the domain of the affine expression, which may be
2829 * a parameter space or a set.
2830 * The tricky part is that we don't know if the domain is a set or not,
2831 * so when we are trying to read the domain, we may actually be reading
2832 * the affine expression itself (defined on a parameter domains)
2833 * If the tuple we are reading is named, we assume it's the domain.
2834 * Also, if inside the tuple, the first thing we find is a nested tuple
2835 * or a new identifier, we again assume it's the domain.
2836 * Otherwise, we assume we are reading an affine expression.
2837 */
2838 static __isl_give isl_set *read_aff_domain(struct isl_stream *s,
2839 __isl_take isl_set *dom, struct vars *v)
2840 {
2841 struct isl_token *tok;
2842
2843 tok = isl_stream_next_token(s);
2844 if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
2845 isl_stream_push_token(s, tok);
2846 return read_map_tuple(s, dom, isl_dim_set, v, 1, 0);
2847 }
2848 if (!tok || tok->type != '[') {
2849 isl_stream_error(s, tok, "expecting '['");
2850 goto error;
2851 }
2852 if (next_is_tuple(s) || next_is_fresh_ident(s, v)) {
2853 isl_stream_push_token(s, tok);
2854 dom = read_map_tuple(s, dom, isl_dim_set, v, 1, 0);
2855 } else
2856 isl_stream_push_token(s, tok);
2857
2858 return dom;
2859 error:
2860 if (tok)
2861 isl_stream_push_token(s, tok);
2862 isl_set_free(dom);
2863 return NULL;
2864 }
2865
2866 /* Read an affine expression from "s".
2867 */
2868 __isl_give isl_aff *isl_stream_read_aff(struct isl_stream *s)
2869 {
2870 isl_aff *aff;
2871 isl_multi_aff *ma;
2872
2873 ma = isl_stream_read_multi_aff(s);
2874 if (!ma)
2875 return NULL;
2876 if (isl_multi_aff_dim(ma, isl_dim_out) != 1)
2877 isl_die(s->ctx, isl_error_invalid,
2878 "expecting single affine expression",
2879 goto error);
2880
2881 aff = isl_multi_aff_get_aff(ma, 0);
2882 isl_multi_aff_free(ma);
2883 return aff;
2884 error:
2885 isl_multi_aff_free(ma);
2886 return NULL;
2887 }
2888
2889 /* Read a piecewise affine expression from "s" with domain (space) "dom".
2890 */
2891 static __isl_give isl_pw_aff *read_pw_aff_with_dom(struct isl_stream *s,
2892 __isl_take isl_set *dom, struct vars *v)
2893 {
2894 isl_pw_aff *pwaff = NULL;
2895
2896 if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2897 goto error;
2898
2899 if (isl_stream_eat(s, '['))
2900 goto error;
2901
2902 pwaff = accept_affine(s, isl_set_get_space(dom), v);
2903
2904 if (isl_stream_eat(s, ']'))
2905 goto error;
2906
2907 dom = read_optional_formula(s, dom, v, 0);
2908 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2909
2910 return pwaff;
2911 error:
2912 isl_set_free(dom);
2913 isl_pw_aff_free(pwaff);
2914 return NULL;
2915 }
2916
2917 __isl_give isl_pw_aff *isl_stream_read_pw_aff(struct isl_stream *s)
2918 {
2919 struct vars *v;
2920 isl_set *dom = NULL;
2921 isl_set *aff_dom;
2922 isl_pw_aff *pa = NULL;
2923 int n;
2924
2925 v = vars_new(s->ctx);
2926 if (!v)
2927 return NULL;
2928
2929 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2930 if (next_is_tuple(s)) {
2931 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
2932 if (isl_stream_eat(s, ISL_TOKEN_TO))
2933 goto error;
2934 }
2935 if (isl_stream_eat(s, '{'))
2936 goto error;
2937
2938 n = v->n;
2939 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2940 pa = read_pw_aff_with_dom(s, aff_dom, v);
2941 vars_drop(v, v->n - n);
2942
2943 while (isl_stream_eat_if_available(s, ';')) {
2944 isl_pw_aff *pa_i;
2945
2946 n = v->n;
2947 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2948 pa_i = read_pw_aff_with_dom(s, aff_dom, v);
2949 vars_drop(v, v->n - n);
2950
2951 pa = isl_pw_aff_union_add(pa, pa_i);
2952 }
2953
2954 if (isl_stream_eat(s, '}'))
2955 goto error;
2956
2957 vars_free(v);
2958 isl_set_free(dom);
2959 return pa;
2960 error:
2961 vars_free(v);
2962 isl_set_free(dom);
2963 isl_pw_aff_free(pa);
2964 return NULL;
2965 }
2966
2967 __isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str)
2968 {
2969 isl_aff *aff;
2970 struct isl_stream *s = isl_stream_new_str(ctx, str);
2971 if (!s)
2972 return NULL;
2973 aff = isl_stream_read_aff(s);
2974 isl_stream_free(s);
2975 return aff;
2976 }
2977
2978 __isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str)
2979 {
2980 isl_pw_aff *pa;
2981 struct isl_stream *s = isl_stream_new_str(ctx, str);
2982 if (!s)
2983 return NULL;
2984 pa = isl_stream_read_pw_aff(s);
2985 isl_stream_free(s);
2986 return pa;
2987 }
2988
2989 /* Read an isl_pw_multi_aff from "s".
2990 * We currently read a generic object and if it turns out to be a set or
2991 * a map, we convert that to an isl_pw_multi_aff.
2992 * It would be more efficient if we were to construct the isl_pw_multi_aff
2993 * directly.
2994 */
2995 __isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(struct isl_stream *s)
2996 {
2997 struct isl_obj obj;
2998
2999 obj = obj_read(s);
3000 if (!obj.v)
3001 return NULL;
3002
3003 if (obj.type == isl_obj_map)
3004 return isl_pw_multi_aff_from_map(obj.v);
3005 if (obj.type == isl_obj_set)
3006 return isl_pw_multi_aff_from_set(obj.v);
3007
3008 obj.type->free(obj.v);
3009 isl_die(s->ctx, isl_error_invalid, "unexpected object type",
3010 return NULL);
3011 }
3012
3013 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx,
3014 const char *str)
3015 {
3016 isl_pw_multi_aff *pma;
3017 struct isl_stream *s = isl_stream_new_str(ctx, str);
3018 if (!s)
3019 return NULL;
3020 pma = isl_stream_read_pw_multi_aff(s);
3021 isl_stream_free(s);
3022 return pma;
3023 }
3024
3025 /* Read an isl_union_pw_multi_aff from "s".
3026 * We currently read a generic object and if it turns out to be a set or
3027 * a map, we convert that to an isl_union_pw_multi_aff.
3028 * It would be more efficient if we were to construct
3029 * the isl_union_pw_multi_aff directly.
3030 */
3031 __isl_give isl_union_pw_multi_aff *isl_stream_read_union_pw_multi_aff(
3032 struct isl_stream *s)
3033 {
3034 struct isl_obj obj;
3035
3036 obj = obj_read(s);
3037 if (!obj.v)
3038 return NULL;
3039
3040 if (obj.type == isl_obj_map || obj.type == isl_obj_set)
3041 obj = to_union(s->ctx, obj);
3042 if (obj.type == isl_obj_union_map)
3043 return isl_union_pw_multi_aff_from_union_map(obj.v);
3044 if (obj.type == isl_obj_union_set)
3045 return isl_union_pw_multi_aff_from_union_set(obj.v);
3046
3047 obj.type->free(obj.v);
3048 isl_die(s->ctx, isl_error_invalid, "unexpected object type",
3049 return NULL);
3050 }
3051
3052 /* Read an isl_union_pw_multi_aff from "str".
3053 */
3054 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_read_from_str(
3055 isl_ctx *ctx, const char *str)
3056 {
3057 isl_union_pw_multi_aff *upma;
3058 struct isl_stream *s = isl_stream_new_str(ctx, str);
3059 if (!s)
3060 return NULL;
3061 upma = isl_stream_read_union_pw_multi_aff(s);
3062 isl_stream_free(s);
3063 return upma;
3064 }
3065
3066 /* Assuming "pa" represents a single affine expression defined on a universe
3067 * domain, extract this affine expression.
3068 */
3069 static __isl_give isl_aff *aff_from_pw_aff(__isl_take isl_pw_aff *pa)
3070 {
3071 isl_aff *aff;
3072
3073 if (!pa)
3074 return NULL;
3075 if (pa->n != 1)
3076 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
3077 "expecting single affine expression",
3078 goto error);
3079 if (!isl_set_plain_is_universe(pa->p[0].set))
3080 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
3081 "expecting universe domain",
3082 goto error);
3083
3084 aff = isl_aff_copy(pa->p[0].aff);
3085 isl_pw_aff_free(pa);
3086 return aff;
3087 error:
3088 isl_pw_aff_free(pa);
3089 return NULL;
3090 }
3091
3092 /* Read a multi-affine expression from "s".
3093 * If the multi-affine expression has a domain, then then tuple
3094 * representing this domain cannot involve any affine expressions.
3095 * The tuple representing the actual expressions needs to consist
3096 * of only affine expressions. Moreover, these expressions can
3097 * only depend on parameters and input dimensions and not on other
3098 * output dimensions.
3099 */
3100 __isl_give isl_multi_aff *isl_stream_read_multi_aff(struct isl_stream *s)
3101 {
3102 struct vars *v;
3103 isl_set *dom = NULL;
3104 isl_multi_pw_aff *tuple = NULL;
3105 int dim, i, n;
3106 isl_space *space, *dom_space;
3107 isl_multi_aff *ma = NULL;
3108
3109 v = vars_new(s->ctx);
3110 if (!v)
3111 return NULL;
3112
3113 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3114 if (next_is_tuple(s)) {
3115 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3116 if (isl_stream_eat(s, ISL_TOKEN_TO))
3117 goto error;
3118 }
3119 if (!isl_set_plain_is_universe(dom))
3120 isl_die(s->ctx, isl_error_invalid,
3121 "expecting universe parameter domain", goto error);
3122 if (isl_stream_eat(s, '{'))
3123 goto error;
3124
3125 tuple = read_tuple(s, v, 0, 0);
3126 if (!tuple)
3127 goto error;
3128 if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {
3129 isl_set *set;
3130 isl_space *space;
3131 int has_expr;
3132
3133 has_expr = tuple_has_expr(tuple);
3134 if (has_expr < 0)
3135 goto error;
3136 if (has_expr)
3137 isl_die(s->ctx, isl_error_invalid,
3138 "expecting universe domain", goto error);
3139 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3140 set = isl_set_universe(space);
3141 dom = isl_set_intersect_params(set, dom);
3142 isl_multi_pw_aff_free(tuple);
3143 tuple = read_tuple(s, v, 0, 0);
3144 if (!tuple)
3145 goto error;
3146 }
3147
3148 if (isl_stream_eat(s, '}'))
3149 goto error;
3150
3151 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
3152 dim = isl_set_dim(dom, isl_dim_all);
3153 dom_space = isl_set_get_space(dom);
3154 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3155 space = isl_space_align_params(space, isl_space_copy(dom_space));
3156 if (!isl_space_is_params(dom_space))
3157 space = isl_space_map_from_domain_and_range(
3158 isl_space_copy(dom_space), space);
3159 isl_space_free(dom_space);
3160 ma = isl_multi_aff_alloc(space);
3161
3162 for (i = 0; i < n; ++i) {
3163 isl_pw_aff *pa;
3164 isl_aff *aff;
3165 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
3166 aff = aff_from_pw_aff(pa);
3167 if (!aff)
3168 goto error;
3169 if (isl_aff_involves_dims(aff, isl_dim_in, dim, i + 1)) {
3170 isl_aff_free(aff);
3171 isl_die(s->ctx, isl_error_invalid,
3172 "not an affine expression", goto error);
3173 }
3174 aff = isl_aff_drop_dims(aff, isl_dim_in, dim, n);
3175 space = isl_multi_aff_get_domain_space(ma);
3176 aff = isl_aff_reset_domain_space(aff, space);
3177 ma = isl_multi_aff_set_aff(ma, i, aff);
3178 }
3179
3180 isl_multi_pw_aff_free(tuple);
3181 vars_free(v);
3182 isl_set_free(dom);
3183 return ma;
3184 error:
3185 isl_multi_pw_aff_free(tuple);
3186 vars_free(v);
3187 isl_set_free(dom);
3188 isl_multi_aff_free(ma);
3189 return NULL;
3190 }
3191
3192 __isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx,
3193 const char *str)
3194 {
3195 isl_multi_aff *maff;
3196 struct isl_stream *s = isl_stream_new_str(ctx, str);
3197 if (!s)
3198 return NULL;
3199 maff = isl_stream_read_multi_aff(s);
3200 isl_stream_free(s);
3201 return maff;
3202 }
3203
3204 /* Read an isl_multi_pw_aff from "s".
3205 *
3206 * The input format is similar to that of map, except that any conditions
3207 * on the domains should be specified inside the tuple since each
3208 * piecewise affine expression may have a different domain.
3209 *
3210 * Since we do not know in advance if the isl_multi_pw_aff lives
3211 * in a set or a map space, we first read the first tuple and check
3212 * if it is followed by a "->". If so, we convert the tuple into
3213 * the domain of the isl_multi_pw_aff and read in the next tuple.
3214 * This tuple (or the first tuple if it was not followed by a "->")
3215 * is then converted into the isl_multi_pw_aff.
3216 *
3217 * Note that the function read_tuple accepts tuples where some output or
3218 * set dimensions are defined in terms of other output or set dimensions
3219 * since this function is also used to read maps. As a special case,
3220 * read_tuple also accept dimensions that are defined in terms of themselves
3221 * (i.e., that are not defined).
3222 * These cases are not allowed when reading am isl_multi_pw_aff so we check
3223 * that the definition of the output/set dimensions does not involve any
3224 * output/set dimensions.
3225 * We then drop the output dimensions from the domain of the result
3226 * of read_tuple (which is of the form [input, output] -> [output],
3227 * with anonymous domain) and reset the space.
3228 */
3229 __isl_give isl_multi_pw_aff *isl_stream_read_multi_pw_aff(struct isl_stream *s)
3230 {
3231 struct vars *v;
3232 isl_set *dom = NULL;
3233 isl_multi_pw_aff *tuple = NULL;
3234 int dim, i, n;
3235 isl_space *space, *dom_space;
3236 isl_multi_pw_aff *mpa = NULL;
3237
3238 v = vars_new(s->ctx);
3239 if (!v)
3240 return NULL;
3241
3242 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3243 if (next_is_tuple(s)) {
3244 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3245 if (isl_stream_eat(s, ISL_TOKEN_TO))
3246 goto error;
3247 }
3248 if (isl_stream_eat(s, '{'))
3249 goto error;
3250
3251 tuple = read_tuple(s, v, 0, 0);
3252 if (!tuple)
3253 goto error;
3254 if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {
3255 isl_map *map = map_from_tuple(tuple, dom, isl_dim_in, v, 0);
3256 dom = isl_map_domain(map);
3257 tuple = read_tuple(s, v, 0, 0);
3258 if (!tuple)
3259 goto error;
3260 }
3261
3262 if (isl_stream_eat(s, '}'))
3263 goto error;
3264
3265 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
3266 dim = isl_set_dim(dom, isl_dim_all);
3267 dom_space = isl_set_get_space(dom);
3268 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3269 space = isl_space_align_params(space, isl_space_copy(dom_space));
3270 if (!isl_space_is_params(dom_space))
3271 space = isl_space_map_from_domain_and_range(
3272 isl_space_copy(dom_space), space);
3273 isl_space_free(dom_space);
3274 mpa = isl_multi_pw_aff_alloc(space);
3275
3276 for (i = 0; i < n; ++i) {
3277 isl_pw_aff *pa;
3278 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
3279 if (!pa)
3280 goto error;
3281 if (isl_pw_aff_involves_dims(pa, isl_dim_in, dim, i + 1)) {
3282 isl_pw_aff_free(pa);
3283 isl_die(s->ctx, isl_error_invalid,
3284 "not an affine expression", goto error);
3285 }
3286 pa = isl_pw_aff_drop_dims(pa, isl_dim_in, dim, n);
3287 space = isl_multi_pw_aff_get_domain_space(mpa);
3288 pa = isl_pw_aff_reset_domain_space(pa, space);
3289 mpa = isl_multi_pw_aff_set_pw_aff(mpa, i, pa);
3290 }
3291
3292 isl_multi_pw_aff_free(tuple);
3293 vars_free(v);
3294 mpa = isl_multi_pw_aff_intersect_domain(mpa, dom);
3295 return mpa;
3296 error:
3297 isl_multi_pw_aff_free(tuple);
3298 vars_free(v);
3299 isl_set_free(dom);
3300 isl_multi_pw_aff_free(mpa);
3301 return NULL;
3302 }
3303
3304 /* Read an isl_multi_pw_aff from "str".
3305 */
3306 __isl_give isl_multi_pw_aff *isl_multi_pw_aff_read_from_str(isl_ctx *ctx,
3307 const char *str)
3308 {
3309 isl_multi_pw_aff *mpa;
3310 struct isl_stream *s = isl_stream_new_str(ctx, str);
3311 if (!s)
3312 return NULL;
3313 mpa = isl_stream_read_multi_pw_aff(s);
3314 isl_stream_free(s);
3315 return mpa;
3316 }
3317
3318 __isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial(
3319 struct isl_stream *s)
3320 {
3321 struct isl_obj obj;
3322
3323 obj = obj_read(s);
3324 if (obj.type == isl_obj_pw_qpolynomial) {
3325 obj.type = isl_obj_union_pw_qpolynomial;
3326 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
3327 }
3328 if (obj.v)
3329 isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial,
3330 goto error);
3331
3332 return obj.v;
3333 error:
3334 obj.type->free(obj.v);
3335 return NULL;
3336 }
3337
3338 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str(
3339 isl_ctx *ctx, const char *str)
3340 {
3341 isl_union_pw_qpolynomial *upwqp;
3342 struct isl_stream *s = isl_stream_new_str(ctx, str);
3343 if (!s)
3344 return NULL;
3345 upwqp = isl_stream_read_union_pw_qpolynomial(s);
3346 isl_stream_free(s);
3347 return upwqp;
3348 }
Integer set library