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