?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_schedule_intersect_domain
[isl.git] / isl_input.c
blobb6073deaeda8ad7a9fd042637155939c81804d00
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(__isl_keep 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(__isl_keep 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 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(__isl_keep 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(__isl_keep 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(__isl_keep isl_stream *s,
311 __isl_take isl_space *space, struct vars *v);
312 static __isl_give isl_pw_aff_list *accept_affine_list(__isl_keep isl_stream *s,
313 __isl_take isl_space *dim, struct vars *v);
314
315 static __isl_give isl_pw_aff *accept_minmax(__isl_keep 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(__isl_keep 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(__isl_keep 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(__isl_keep 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(__isl_keep isl_stream *s,
679 struct vars *v, __isl_take isl_map *map, int rational);
680 static __isl_give isl_pw_aff *accept_extended_affine(__isl_keep 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(__isl_keep 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(__isl_keep 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(__isl_keep 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(__isl_keep 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(__isl_keep 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(__isl_keep 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(__isl_keep 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(__isl_keep 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 /* Is "pa" an expression in term of earlier dimensions?
939 * The alternative is that the dimension is defined to be equal to itself,
940 * meaning that it has a universe domain and an expression that depends
941 * on itself. "i" is the position of the expression in a sequence
942 * of "n" expressions. The final dimensions of "pa" correspond to
943 * these "n" expressions.
944 */
945 static int pw_aff_is_expr(__isl_keep isl_pw_aff *pa, int i, int n)
946 {
947 isl_aff *aff;
948
949 if (!pa)
950 return -1;
951 if (pa->n != 1)
952 return 1;
953 if (!isl_set_plain_is_universe(pa->p[0].set))
954 return 1;
955
956 aff = pa->p[0].aff;
957 if (isl_int_is_zero(aff->v->el[aff->v->size - n + i]))
958 return 1;
959 return 0;
960 }
961
962 /* Does the tuple contain any dimensions that are defined
963 * in terms of earlier dimensions?
964 */
965 static int tuple_has_expr(__isl_keep isl_multi_pw_aff *tuple)
966 {
967 int i, n;
968 int has_expr = 0;
969 isl_pw_aff *pa;
970
971 if (!tuple)
972 return -1;
973 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
974 for (i = 0; i < n; ++i) {
975 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
976 has_expr = pw_aff_is_expr(pa, i, n);
977 isl_pw_aff_free(pa);
978 if (has_expr < 0 || has_expr)
979 break;
980 }
981
982 return has_expr;
983 }
984
985 /* Set the name of dimension "pos" in "space" to "name".
986 * During printing, we add primes if the same name appears more than once
987 * to distinguish the occurrences. Here, we remove those primes from "name"
988 * before setting the name of the dimension.
989 */
990 static __isl_give isl_space *space_set_dim_name(__isl_take isl_space *space,
991 int pos, char *name)
992 {
993 char *prime;
994
995 if (!name)
996 return space;
997
998 prime = strchr(name, '\'');
999 if (prime)
1000 *prime = '\0';
1001 space = isl_space_set_dim_name(space, isl_dim_out, pos, name);
1002 if (prime)
1003 *prime = '\'';
1004
1005 return space;
1006 }
1007
1008 /* Accept a piecewise affine expression.
1009 *
1010 * At the outer level, the piecewise affine expression may be of the form
1011 *
1012 * aff1 : condition1; aff2 : conditions2; ...
1013 *
1014 * or simply
1015 *
1016 * aff
1017 *
1018 * each of the affine expressions may in turn include ternary operators.
1019 *
1020 * There may be parentheses around some subexpression of "aff1"
1021 * around "aff1" itself, around "aff1 : condition1" and/or
1022 * around the entire piecewise affine expression.
1023 * We therefore remove the opening parenthesis (if any) from the stream
1024 * in case the closing parenthesis follows the colon, but if the closing
1025 * parenthesis is the first thing in the stream after the parsed affine
1026 * expression, we push the parsed expression onto the stream and parse
1027 * again in case the parentheses enclose some subexpression of "aff1".
1028 */
1029 static __isl_give isl_pw_aff *accept_piecewise_affine(__isl_keep isl_stream *s,
1030 __isl_take isl_space *space, struct vars *v, int rational)
1031 {
1032 isl_pw_aff *res;
1033 isl_space *res_space;
1034
1035 res_space = isl_space_from_domain(isl_space_copy(space));
1036 res_space = isl_space_add_dims(res_space, isl_dim_out, 1);
1037 res = isl_pw_aff_empty(res_space);
1038 do {
1039 isl_pw_aff *pa;
1040 int seen_paren;
1041 int line = -1, col = -1;
1042
1043 set_current_line_col(s, &line, &col);
1044 seen_paren = isl_stream_eat_if_available(s, '(');
1045 if (seen_paren)
1046 pa = accept_piecewise_affine(s, isl_space_copy(space),
1047 v, rational);
1048 else
1049 pa = accept_extended_affine(s, isl_space_copy(space),
1050 v, rational);
1051 if (seen_paren && isl_stream_eat_if_available(s, ')')) {
1052 seen_paren = 0;
1053 if (push_aff(s, line, col, pa) < 0)
1054 goto error;
1055 pa = accept_extended_affine(s, isl_space_copy(space),
1056 v, rational);
1057 }
1058 if (isl_stream_eat_if_available(s, ':')) {
1059 isl_space *dom_space;
1060 isl_set *dom;
1061
1062 dom_space = isl_pw_aff_get_domain_space(pa);
1063 dom = isl_set_universe(dom_space);
1064 dom = read_formula(s, v, dom, rational);
1065 pa = isl_pw_aff_intersect_domain(pa, dom);
1066 }
1067
1068 res = isl_pw_aff_union_add(res, pa);
1069
1070 if (seen_paren && isl_stream_eat(s, ')'))
1071 goto error;
1072 } while (isl_stream_eat_if_available(s, ';'));
1073
1074 isl_space_free(space);
1075
1076 return res;
1077 error:
1078 isl_space_free(space);
1079 return isl_pw_aff_free(res);
1080 }
1081
1082 /* Read an affine expression from "s" for use in read_tuple.
1083 *
1084 * accept_extended_affine requires a wrapped space as input.
1085 * read_tuple on the other hand expects each isl_pw_aff
1086 * to have an anonymous space. We therefore adjust the space
1087 * of the isl_pw_aff before returning it.
1088 */
1089 static __isl_give isl_pw_aff *read_tuple_var_def(__isl_keep isl_stream *s,
1090 struct vars *v, int rational)
1091 {
1092 isl_space *space;
1093 isl_pw_aff *def;
1094
1095 space = isl_space_wrap(isl_space_alloc(s->ctx, 0, v->n, 0));
1096
1097 def = accept_piecewise_affine(s, space, v, rational);
1098
1099 space = isl_space_set_alloc(s->ctx, 0, v->n);
1100 def = isl_pw_aff_reset_domain_space(def, space);
1101
1102 return def;
1103 }
1104
1105 /* Read a list of tuple elements by calling "read_el" on each of them and
1106 * return a space with the same number of set dimensions derived from
1107 * the parameter space "space" and possibly updated by "read_el".
1108 * The elements in the list are separated by either "," or "][".
1109 * If "comma" is set then only "," is allowed.
1110 */
1111 static __isl_give isl_space *read_tuple_list(__isl_keep isl_stream *s,
1112 struct vars *v, __isl_take isl_space *space, int rational, int comma,
1113 __isl_give isl_space *(*read_el)(__isl_keep isl_stream *s,
1114 struct vars *v, __isl_take isl_space *space, int rational,
1115 void *user),
1116 void *user)
1117 {
1118 if (!space)
1119 return NULL;
1120
1121 space = isl_space_set_from_params(space);
1122
1123 if (isl_stream_next_token_is(s, ']'))
1124 return space;
1125
1126 for (;;) {
1127 struct isl_token *tok;
1128
1129 space = isl_space_add_dims(space, isl_dim_set, 1);
1130
1131 space = read_el(s, v, space, rational, user);
1132 if (!space)
1133 return NULL;
1134
1135 tok = isl_stream_next_token(s);
1136 if (!comma && tok && tok->type == ']' &&
1137 isl_stream_next_token_is(s, '[')) {
1138 isl_token_free(tok);
1139 tok = isl_stream_next_token(s);
1140 } else if (!tok || tok->type != ',') {
1141 if (tok)
1142 isl_stream_push_token(s, tok);
1143 break;
1144 }
1145
1146 isl_token_free(tok);
1147 }
1148
1149 return space;
1150 }
1151
1152 /* Read a tuple space from "s" derived from the parameter space "space".
1153 * Call "read_el" on each element in the tuples.
1154 */
1155 static __isl_give isl_space *read_tuple_space(__isl_keep isl_stream *s,
1156 struct vars *v, __isl_take isl_space *space, int rational, int comma,
1157 __isl_give isl_space *(*read_el)(__isl_keep isl_stream *s,
1158 struct vars *v, __isl_take isl_space *space, int rational,
1159 void *user),
1160 void *user)
1161 {
1162 struct isl_token *tok;
1163 char *name = NULL;
1164 isl_space *res = NULL;
1165
1166 tok = isl_stream_next_token(s);
1167 if (!tok)
1168 goto error;
1169 if (tok->type == ISL_TOKEN_IDENT || tok->is_keyword) {
1170 name = strdup(tok->u.s);
1171 isl_token_free(tok);
1172 if (!name)
1173 goto error;
1174 } else
1175 isl_stream_push_token(s, tok);
1176 if (isl_stream_eat(s, '['))
1177 goto error;
1178 if (next_is_tuple(s)) {
1179 isl_space *out;
1180 res = read_tuple_space(s, v, isl_space_copy(space),
1181 rational, comma, read_el, user);
1182 if (isl_stream_eat(s, ISL_TOKEN_TO))
1183 goto error;
1184 out = read_tuple_space(s, v, isl_space_copy(space),
1185 rational, comma, read_el, user);
1186 res = isl_space_range_product(res, out);
1187 } else
1188 res = read_tuple_list(s, v, isl_space_copy(space),
1189 rational, comma, read_el, user);
1190 if (isl_stream_eat(s, ']'))
1191 goto error;
1192
1193 if (name) {
1194 res = isl_space_set_tuple_name(res, isl_dim_set, name);
1195 free(name);
1196 }
1197
1198 isl_space_free(space);
1199 return res;
1200 error:
1201 free(name);
1202 isl_space_free(res);
1203 isl_space_free(space);
1204 return NULL;
1205 }
1206
1207 /* Construct an isl_pw_aff defined on a space with v->n variables
1208 * that is equal to the last of those variables.
1209 */
1210 static __isl_give isl_pw_aff *identity_tuple_el(struct vars *v)
1211 {
1212 isl_space *space;
1213 isl_aff *aff;
1214
1215 space = isl_space_set_alloc(v->ctx, 0, v->n);
1216 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1217 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, v->n - 1, 1);
1218 return isl_pw_aff_from_aff(aff);
1219 }
1220
1221 /* This function is called for each element in a tuple inside read_tuple.
1222 * Add a new variable to "v" and construct a corresponding isl_pw_aff defined
1223 * over a space containing all variables in "v" defined so far.
1224 * The isl_pw_aff expresses the new variable in terms of earlier variables
1225 * if a definition is provided. Otherwise, it is represented as being
1226 * equal to itself.
1227 * Add the isl_pw_aff to *list.
1228 * If the new variable was named, then adjust "space" accordingly and
1229 * return the updated space.
1230 */
1231 static __isl_give isl_space *read_tuple_pw_aff_el(__isl_keep isl_stream *s,
1232 struct vars *v, __isl_take isl_space *space, int rational, void *user)
1233 {
1234 isl_pw_aff_list **list = (isl_pw_aff_list **) user;
1235 isl_pw_aff *pa;
1236 struct isl_token *tok;
1237 int new_name = 0;
1238
1239 tok = next_token(s);
1240 if (!tok) {
1241 isl_stream_error(s, NULL, "unexpected EOF");
1242 return isl_space_free(space);
1243 }
1244
1245 if (tok->type == ISL_TOKEN_IDENT) {
1246 int n = v->n;
1247 int p = vars_pos(v, tok->u.s, -1);
1248 if (p < 0)
1249 goto error;
1250 new_name = p >= n;
1251 }
1252
1253 if (tok->type == '*') {
1254 if (vars_add_anon(v) < 0)
1255 goto error;
1256 isl_token_free(tok);
1257 pa = identity_tuple_el(v);
1258 } else if (new_name) {
1259 int pos = isl_space_dim(space, isl_dim_out) - 1;
1260 space = space_set_dim_name(space, pos, v->v->name);
1261 isl_token_free(tok);
1262 if (isl_stream_eat_if_available(s, '='))
1263 pa = read_tuple_var_def(s, v, rational);
1264 else
1265 pa = identity_tuple_el(v);
1266 } else {
1267 isl_stream_push_token(s, tok);
1268 tok = NULL;
1269 if (vars_add_anon(v) < 0)
1270 goto error;
1271 pa = read_tuple_var_def(s, v, rational);
1272 }
1273
1274 *list = isl_pw_aff_list_add(*list, pa);
1275 if (!*list)
1276 return isl_space_free(space);
1277
1278 return space;
1279 error:
1280 isl_token_free(tok);
1281 return isl_space_free(space);
1282 }
1283
1284 /* Read a tuple and represent it as an isl_multi_pw_aff.
1285 * The range space of the isl_multi_pw_aff is the space of the tuple.
1286 * The domain space is an anonymous space
1287 * with a dimension for each variable in the set of variables in "v",
1288 * including the variables in the range.
1289 * If a given dimension is not defined in terms of earlier dimensions in
1290 * the input, then the corresponding isl_pw_aff is set equal to one time
1291 * the variable corresponding to the dimension being defined.
1292 *
1293 * The elements in the tuple are collected in a list by read_tuple_pw_aff_el.
1294 * Each element in this list is defined over a space representing
1295 * the variables defined so far. We need to adjust the earlier
1296 * elements to have as many variables in the domain as the final
1297 * element in the list.
1298 */
1299 static __isl_give isl_multi_pw_aff *read_tuple(__isl_keep isl_stream *s,
1300 struct vars *v, int rational, int comma)
1301 {
1302 int i, n;
1303 isl_space *space;
1304 isl_pw_aff_list *list;
1305
1306 space = isl_space_params_alloc(v->ctx, 0);
1307 list = isl_pw_aff_list_alloc(s->ctx, 0);
1308 space = read_tuple_space(s, v, space, rational, comma,
1309 &read_tuple_pw_aff_el, &list);
1310 n = isl_space_dim(space, isl_dim_set);
1311 for (i = 0; i + 1 < n; ++i) {
1312 isl_pw_aff *pa;
1313
1314 pa = isl_pw_aff_list_get_pw_aff(list, i);
1315 pa = isl_pw_aff_add_dims(pa, isl_dim_in, n - (i + 1));
1316 list = isl_pw_aff_list_set_pw_aff(list, i, pa);
1317 }
1318
1319 space = isl_space_from_range(space);
1320 space = isl_space_add_dims(space, isl_dim_in, v->n);
1321 return isl_multi_pw_aff_from_pw_aff_list(space, list);
1322 }
1323
1324 /* Add the tuple represented by the isl_multi_pw_aff "tuple" to "map".
1325 * We first create the appropriate space in "map" based on the range
1326 * space of this isl_multi_pw_aff. Then, we add equalities based
1327 * on the affine expressions. These live in an anonymous space,
1328 * however, so we first need to reset the space to that of "map".
1329 */
1330 static __isl_give isl_map *map_from_tuple(__isl_take isl_multi_pw_aff *tuple,
1331 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
1332 int rational)
1333 {
1334 int i, n;
1335 isl_ctx *ctx;
1336 isl_space *space = NULL;
1337
1338 if (!map || !tuple)
1339 goto error;
1340 ctx = isl_multi_pw_aff_get_ctx(tuple);
1341 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
1342 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
1343 if (!space)
1344 goto error;
1345
1346 if (type == isl_dim_param) {
1347 if (isl_space_has_tuple_name(space, isl_dim_set) ||
1348 isl_space_is_wrapping(space)) {
1349 isl_die(ctx, isl_error_invalid,
1350 "parameter tuples cannot be named or nested",
1351 goto error);
1352 }
1353 map = isl_map_add_dims(map, type, n);
1354 for (i = 0; i < n; ++i) {
1355 isl_id *id;
1356 if (!isl_space_has_dim_name(space, isl_dim_set, i))
1357 isl_die(ctx, isl_error_invalid,
1358 "parameters must be named",
1359 goto error);
1360 id = isl_space_get_dim_id(space, isl_dim_set, i);
1361 map = isl_map_set_dim_id(map, isl_dim_param, i, id);
1362 }
1363 } else if (type == isl_dim_in) {
1364 isl_set *set;
1365
1366 set = isl_set_universe(isl_space_copy(space));
1367 if (rational)
1368 set = isl_set_set_rational(set);
1369 set = isl_set_intersect_params(set, isl_map_params(map));
1370 map = isl_map_from_domain(set);
1371 } else {
1372 isl_set *set;
1373
1374 set = isl_set_universe(isl_space_copy(space));
1375 if (rational)
1376 set = isl_set_set_rational(set);
1377 map = isl_map_from_domain_and_range(isl_map_domain(map), set);
1378 }
1379
1380 for (i = 0; i < n; ++i) {
1381 isl_pw_aff *pa;
1382 isl_space *space;
1383 isl_aff *aff;
1384 isl_set *set;
1385 isl_map *map_i;
1386
1387 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
1388 space = isl_pw_aff_get_domain_space(pa);
1389 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1390 aff = isl_aff_add_coefficient_si(aff,
1391 isl_dim_in, v->n - n + i, -1);
1392 pa = isl_pw_aff_add(pa, isl_pw_aff_from_aff(aff));
1393 if (rational)
1394 pa = isl_pw_aff_set_rational(pa);
1395 set = isl_pw_aff_zero_set(pa);
1396 map_i = isl_map_from_range(set);
1397 map_i = isl_map_reset_space(map_i, isl_map_get_space(map));
1398 map = isl_map_intersect(map, map_i);
1399 }
1400
1401 isl_space_free(space);
1402 isl_multi_pw_aff_free(tuple);
1403 return map;
1404 error:
1405 isl_space_free(space);
1406 isl_multi_pw_aff_free(tuple);
1407 isl_map_free(map);
1408 return NULL;
1409 }
1410
1411 /* Read a tuple from "s" and add it to "map".
1412 * The tuple is initially represented as an isl_multi_pw_aff and
1413 * then added to "map".
1414 */
1415 static __isl_give isl_map *read_map_tuple(__isl_keep isl_stream *s,
1416 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
1417 int rational, int comma)
1418 {
1419 isl_multi_pw_aff *tuple;
1420
1421 tuple = read_tuple(s, v, rational, comma);
1422 if (!tuple)
1423 return isl_map_free(map);
1424
1425 return map_from_tuple(tuple, map, type, v, rational);
1426 }
1427
1428 static __isl_give isl_set *construct_constraints(
1429 __isl_take isl_set *set, int type,
1430 __isl_keep isl_pw_aff_list *left, __isl_keep isl_pw_aff_list *right,
1431 int rational)
1432 {
1433 isl_set *cond;
1434
1435 left = isl_pw_aff_list_copy(left);
1436 right = isl_pw_aff_list_copy(right);
1437 if (rational) {
1438 left = isl_pw_aff_list_set_rational(left);
1439 right = isl_pw_aff_list_set_rational(right);
1440 }
1441 if (type == ISL_TOKEN_LE)
1442 cond = isl_pw_aff_list_le_set(left, right);
1443 else if (type == ISL_TOKEN_GE)
1444 cond = isl_pw_aff_list_ge_set(left, right);
1445 else if (type == ISL_TOKEN_LT)
1446 cond = isl_pw_aff_list_lt_set(left, right);
1447 else if (type == ISL_TOKEN_GT)
1448 cond = isl_pw_aff_list_gt_set(left, right);
1449 else if (type == ISL_TOKEN_NE)
1450 cond = isl_pw_aff_list_ne_set(left, right);
1451 else
1452 cond = isl_pw_aff_list_eq_set(left, right);
1453
1454 return isl_set_intersect(set, cond);
1455 }
1456
1457 static __isl_give isl_map *add_constraint(__isl_keep isl_stream *s,
1458 struct vars *v, __isl_take isl_map *map, int rational)
1459 {
1460 struct isl_token *tok = NULL;
1461 isl_pw_aff_list *list1 = NULL, *list2 = NULL;
1462 isl_set *set;
1463
1464 set = isl_map_wrap(map);
1465 list1 = accept_affine_list(s, isl_set_get_space(set), v);
1466 if (!list1)
1467 goto error;
1468 tok = isl_stream_next_token(s);
1469 if (!is_comparator(tok)) {
1470 isl_stream_error(s, tok, "missing operator");
1471 if (tok)
1472 isl_stream_push_token(s, tok);
1473 tok = NULL;
1474 goto error;
1475 }
1476 for (;;) {
1477 list2 = accept_affine_list(s, isl_set_get_space(set), v);
1478 if (!list2)
1479 goto error;
1480
1481 set = construct_constraints(set, tok->type, list1, list2,
1482 rational);
1483 isl_token_free(tok);
1484 isl_pw_aff_list_free(list1);
1485 list1 = list2;
1486
1487 tok = isl_stream_next_token(s);
1488 if (!is_comparator(tok)) {
1489 if (tok)
1490 isl_stream_push_token(s, tok);
1491 break;
1492 }
1493 }
1494 isl_pw_aff_list_free(list1);
1495
1496 return isl_set_unwrap(set);
1497 error:
1498 if (tok)
1499 isl_token_free(tok);
1500 isl_pw_aff_list_free(list1);
1501 isl_pw_aff_list_free(list2);
1502 isl_set_free(set);
1503 return NULL;
1504 }
1505
1506 static __isl_give isl_map *read_exists(__isl_keep isl_stream *s,
1507 struct vars *v, __isl_take isl_map *map, int rational)
1508 {
1509 int n = v->n;
1510 int seen_paren = isl_stream_eat_if_available(s, '(');
1511
1512 map = isl_map_from_domain(isl_map_wrap(map));
1513 map = read_defined_var_list(s, v, map, rational);
1514
1515 if (isl_stream_eat(s, ':'))
1516 goto error;
1517
1518 map = read_formula(s, v, map, rational);
1519 map = isl_set_unwrap(isl_map_domain(map));
1520
1521 vars_drop(v, v->n - n);
1522 if (seen_paren && isl_stream_eat(s, ')'))
1523 goto error;
1524
1525 return map;
1526 error:
1527 isl_map_free(map);
1528 return NULL;
1529 }
1530
1531 /* Parse an expression between parentheses and push the result
1532 * back on the stream.
1533 *
1534 * The parsed expression may be either an affine expression
1535 * or a condition. The first type is pushed onto the stream
1536 * as an isl_pw_aff, while the second is pushed as an isl_map.
1537 *
1538 * If the initial token indicates the start of a condition,
1539 * we parse it as such.
1540 * Otherwise, we first parse an affine expression and push
1541 * that onto the stream. If the affine expression covers the
1542 * entire expression between parentheses, we return.
1543 * Otherwise, we assume that the affine expression is the
1544 * start of a condition and continue parsing.
1545 */
1546 static int resolve_paren_expr(__isl_keep isl_stream *s,
1547 struct vars *v, __isl_take isl_map *map, int rational)
1548 {
1549 struct isl_token *tok, *tok2;
1550 int line, col;
1551 isl_pw_aff *pwaff;
1552
1553 tok = isl_stream_next_token(s);
1554 if (!tok || tok->type != '(')
1555 goto error;
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_EXISTS) ||
1562 isl_stream_next_token_is(s, ISL_TOKEN_NOT) ||
1563 isl_stream_next_token_is(s, ISL_TOKEN_TRUE) ||
1564 isl_stream_next_token_is(s, ISL_TOKEN_FALSE) ||
1565 isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1566 map = read_formula(s, v, map, rational);
1567 if (isl_stream_eat(s, ')'))
1568 goto error;
1569 tok->type = ISL_TOKEN_MAP;
1570 tok->u.map = map;
1571 isl_stream_push_token(s, tok);
1572 return 0;
1573 }
1574
1575 tok2 = isl_stream_next_token(s);
1576 if (!tok2)
1577 goto error;
1578 line = tok2->line;
1579 col = tok2->col;
1580 isl_stream_push_token(s, tok2);
1581
1582 pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v);
1583 if (!pwaff)
1584 goto error;
1585
1586 tok2 = isl_token_new(s->ctx, line, col, 0);
1587 if (!tok2)
1588 goto error2;
1589 tok2->type = ISL_TOKEN_AFF;
1590 tok2->u.pwaff = pwaff;
1591
1592 if (isl_stream_eat_if_available(s, ')')) {
1593 isl_stream_push_token(s, tok2);
1594 isl_token_free(tok);
1595 isl_map_free(map);
1596 return 0;
1597 }
1598
1599 isl_stream_push_token(s, tok2);
1600
1601 map = read_formula(s, v, map, rational);
1602 if (isl_stream_eat(s, ')'))
1603 goto error;
1604
1605 tok->type = ISL_TOKEN_MAP;
1606 tok->u.map = map;
1607 isl_stream_push_token(s, tok);
1608
1609 return 0;
1610 error2:
1611 isl_pw_aff_free(pwaff);
1612 error:
1613 isl_token_free(tok);
1614 isl_map_free(map);
1615 return -1;
1616 }
1617
1618 static __isl_give isl_map *read_conjunct(__isl_keep isl_stream *s,
1619 struct vars *v, __isl_take isl_map *map, int rational)
1620 {
1621 if (isl_stream_next_token_is(s, '('))
1622 if (resolve_paren_expr(s, v, isl_map_copy(map), rational))
1623 goto error;
1624
1625 if (isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1626 struct isl_token *tok;
1627 tok = isl_stream_next_token(s);
1628 if (!tok)
1629 goto error;
1630 isl_map_free(map);
1631 map = isl_map_copy(tok->u.map);
1632 isl_token_free(tok);
1633 return map;
1634 }
1635
1636 if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))
1637 return read_exists(s, v, map, rational);
1638
1639 if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))
1640 return map;
1641
1642 if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) {
1643 isl_space *dim = isl_map_get_space(map);
1644 isl_map_free(map);
1645 return isl_map_empty(dim);
1646 }
1647
1648 return add_constraint(s, v, map, rational);
1649 error:
1650 isl_map_free(map);
1651 return NULL;
1652 }
1653
1654 static __isl_give isl_map *read_conjuncts(__isl_keep isl_stream *s,
1655 struct vars *v, __isl_take isl_map *map, int rational)
1656 {
1657 isl_map *res;
1658 int negate;
1659
1660 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1661 res = read_conjunct(s, v, isl_map_copy(map), rational);
1662 if (negate)
1663 res = isl_map_subtract(isl_map_copy(map), res);
1664
1665 while (res && isl_stream_eat_if_available(s, ISL_TOKEN_AND)) {
1666 isl_map *res_i;
1667
1668 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1669 res_i = read_conjunct(s, v, isl_map_copy(map), rational);
1670 if (negate)
1671 res = isl_map_subtract(res, res_i);
1672 else
1673 res = isl_map_intersect(res, res_i);
1674 }
1675
1676 isl_map_free(map);
1677 return res;
1678 }
1679
1680 static struct isl_map *read_disjuncts(__isl_keep isl_stream *s,
1681 struct vars *v, __isl_take isl_map *map, int rational)
1682 {
1683 isl_map *res;
1684
1685 if (isl_stream_next_token_is(s, '}')) {
1686 isl_space *dim = isl_map_get_space(map);
1687 isl_map_free(map);
1688 return isl_map_universe(dim);
1689 }
1690
1691 res = read_conjuncts(s, v, isl_map_copy(map), rational);
1692 while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
1693 isl_map *res_i;
1694
1695 res_i = read_conjuncts(s, v, isl_map_copy(map), rational);
1696 res = isl_map_union(res, res_i);
1697 }
1698
1699 isl_map_free(map);
1700 return res;
1701 }
1702
1703 /* Read a first order formula from "s", add the corresponding
1704 * constraints to "map" and return the result.
1705 *
1706 * In particular, read a formula of the form
1707 *
1708 * a
1709 *
1710 * or
1711 *
1712 * a implies b
1713 *
1714 * where a and b are disjunctions.
1715 *
1716 * In the first case, map is replaced by
1717 *
1718 * map \cap { [..] : a }
1719 *
1720 * In the second case, it is replaced by
1721 *
1722 * (map \setminus { [..] : a}) \cup (map \cap { [..] : b })
1723 */
1724 static __isl_give isl_map *read_formula(__isl_keep isl_stream *s,
1725 struct vars *v, __isl_take isl_map *map, int rational)
1726 {
1727 isl_map *res;
1728
1729 res = read_disjuncts(s, v, isl_map_copy(map), rational);
1730
1731 if (isl_stream_eat_if_available(s, ISL_TOKEN_IMPLIES)) {
1732 isl_map *res2;
1733
1734 res = isl_map_subtract(isl_map_copy(map), res);
1735 res2 = read_disjuncts(s, v, map, rational);
1736 res = isl_map_union(res, res2);
1737 } else
1738 isl_map_free(map);
1739
1740 return res;
1741 }
1742
1743 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1744 {
1745 if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1746 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1747 isl_basic_map_dim(bmap, isl_dim_in) + pos;
1748 pos -= isl_basic_map_dim(bmap, isl_dim_out);
1749
1750 if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1751 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1752 pos -= isl_basic_map_dim(bmap, isl_dim_in);
1753
1754 if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1755 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1756 isl_basic_map_dim(bmap, isl_dim_in) +
1757 isl_basic_map_dim(bmap, isl_dim_out) + pos;
1758 pos -= isl_basic_map_dim(bmap, isl_dim_div);
1759
1760 if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1761 return 1 + pos;
1762
1763 return 0;
1764 }
1765
1766 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1767 __isl_keep isl_stream *s, __isl_take isl_basic_map *bmap)
1768 {
1769 int j;
1770 struct isl_token *tok;
1771 int type;
1772 int k;
1773 isl_int *c;
1774 unsigned nparam;
1775 unsigned dim;
1776
1777 if (!bmap)
1778 return NULL;
1779
1780 nparam = isl_basic_map_dim(bmap, isl_dim_param);
1781 dim = isl_basic_map_dim(bmap, isl_dim_out);
1782
1783 tok = isl_stream_next_token(s);
1784 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1785 isl_stream_error(s, tok, "expecting coefficient");
1786 if (tok)
1787 isl_stream_push_token(s, tok);
1788 goto error;
1789 }
1790 if (!tok->on_new_line) {
1791 isl_stream_error(s, tok, "coefficient should appear on new line");
1792 isl_stream_push_token(s, tok);
1793 goto error;
1794 }
1795
1796 type = isl_int_get_si(tok->u.v);
1797 isl_token_free(tok);
1798
1799 isl_assert(s->ctx, type == 0 || type == 1, goto error);
1800 if (type == 0) {
1801 k = isl_basic_map_alloc_equality(bmap);
1802 c = bmap->eq[k];
1803 } else {
1804 k = isl_basic_map_alloc_inequality(bmap);
1805 c = bmap->ineq[k];
1806 }
1807 if (k < 0)
1808 goto error;
1809
1810 for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1811 int pos;
1812 tok = isl_stream_next_token(s);
1813 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1814 isl_stream_error(s, tok, "expecting coefficient");
1815 if (tok)
1816 isl_stream_push_token(s, tok);
1817 goto error;
1818 }
1819 if (tok->on_new_line) {
1820 isl_stream_error(s, tok,
1821 "coefficient should not appear on new line");
1822 isl_stream_push_token(s, tok);
1823 goto error;
1824 }
1825 pos = polylib_pos_to_isl_pos(bmap, j);
1826 isl_int_set(c[pos], tok->u.v);
1827 isl_token_free(tok);
1828 }
1829
1830 return bmap;
1831 error:
1832 isl_basic_map_free(bmap);
1833 return NULL;
1834 }
1835
1836 static __isl_give isl_basic_map *basic_map_read_polylib(
1837 __isl_keep isl_stream *s)
1838 {
1839 int i;
1840 struct isl_token *tok;
1841 struct isl_token *tok2;
1842 int n_row, n_col;
1843 int on_new_line;
1844 unsigned in = 0, out, local = 0;
1845 struct isl_basic_map *bmap = NULL;
1846 int nparam = 0;
1847
1848 tok = isl_stream_next_token(s);
1849 if (!tok) {
1850 isl_stream_error(s, NULL, "unexpected EOF");
1851 return NULL;
1852 }
1853 tok2 = isl_stream_next_token(s);
1854 if (!tok2) {
1855 isl_token_free(tok);
1856 isl_stream_error(s, NULL, "unexpected EOF");
1857 return NULL;
1858 }
1859 if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1860 isl_stream_push_token(s, tok2);
1861 isl_stream_push_token(s, tok);
1862 isl_stream_error(s, NULL,
1863 "expecting constraint matrix dimensions");
1864 return NULL;
1865 }
1866 n_row = isl_int_get_si(tok->u.v);
1867 n_col = isl_int_get_si(tok2->u.v);
1868 on_new_line = tok2->on_new_line;
1869 isl_token_free(tok2);
1870 isl_token_free(tok);
1871 isl_assert(s->ctx, !on_new_line, return NULL);
1872 isl_assert(s->ctx, n_row >= 0, return NULL);
1873 isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1874 tok = isl_stream_next_token_on_same_line(s);
1875 if (tok) {
1876 if (tok->type != ISL_TOKEN_VALUE) {
1877 isl_stream_error(s, tok,
1878 "expecting number of output dimensions");
1879 isl_stream_push_token(s, tok);
1880 goto error;
1881 }
1882 out = isl_int_get_si(tok->u.v);
1883 isl_token_free(tok);
1884
1885 tok = isl_stream_next_token_on_same_line(s);
1886 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1887 isl_stream_error(s, tok,
1888 "expecting number of input dimensions");
1889 if (tok)
1890 isl_stream_push_token(s, tok);
1891 goto error;
1892 }
1893 in = isl_int_get_si(tok->u.v);
1894 isl_token_free(tok);
1895
1896 tok = isl_stream_next_token_on_same_line(s);
1897 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1898 isl_stream_error(s, tok,
1899 "expecting number of existentials");
1900 if (tok)
1901 isl_stream_push_token(s, tok);
1902 goto error;
1903 }
1904 local = isl_int_get_si(tok->u.v);
1905 isl_token_free(tok);
1906
1907 tok = isl_stream_next_token_on_same_line(s);
1908 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1909 isl_stream_error(s, tok,
1910 "expecting number of parameters");
1911 if (tok)
1912 isl_stream_push_token(s, tok);
1913 goto error;
1914 }
1915 nparam = isl_int_get_si(tok->u.v);
1916 isl_token_free(tok);
1917 if (n_col != 1 + out + in + local + nparam + 1) {
1918 isl_stream_error(s, NULL,
1919 "dimensions don't match");
1920 goto error;
1921 }
1922 } else
1923 out = n_col - 2 - nparam;
1924 bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1925 if (!bmap)
1926 return NULL;
1927
1928 for (i = 0; i < local; ++i) {
1929 int k = isl_basic_map_alloc_div(bmap);
1930 if (k < 0)
1931 goto error;
1932 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1933 }
1934
1935 for (i = 0; i < n_row; ++i)
1936 bmap = basic_map_read_polylib_constraint(s, bmap);
1937
1938 tok = isl_stream_next_token_on_same_line(s);
1939 if (tok) {
1940 isl_stream_error(s, tok, "unexpected extra token on line");
1941 isl_stream_push_token(s, tok);
1942 goto error;
1943 }
1944
1945 bmap = isl_basic_map_simplify(bmap);
1946 bmap = isl_basic_map_finalize(bmap);
1947 return bmap;
1948 error:
1949 isl_basic_map_free(bmap);
1950 return NULL;
1951 }
1952
1953 static struct isl_map *map_read_polylib(__isl_keep isl_stream *s)
1954 {
1955 struct isl_token *tok;
1956 struct isl_token *tok2;
1957 int i, n;
1958 struct isl_map *map;
1959
1960 tok = isl_stream_next_token(s);
1961 if (!tok) {
1962 isl_stream_error(s, NULL, "unexpected EOF");
1963 return NULL;
1964 }
1965 tok2 = isl_stream_next_token_on_same_line(s);
1966 if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
1967 isl_stream_push_token(s, tok2);
1968 isl_stream_push_token(s, tok);
1969 return isl_map_from_basic_map(basic_map_read_polylib(s));
1970 }
1971 if (tok2) {
1972 isl_stream_error(s, tok2, "unexpected token");
1973 isl_stream_push_token(s, tok2);
1974 isl_stream_push_token(s, tok);
1975 return NULL;
1976 }
1977 n = isl_int_get_si(tok->u.v);
1978 isl_token_free(tok);
1979
1980 isl_assert(s->ctx, n >= 1, return NULL);
1981
1982 map = isl_map_from_basic_map(basic_map_read_polylib(s));
1983
1984 for (i = 1; map && i < n; ++i)
1985 map = isl_map_union(map,
1986 isl_map_from_basic_map(basic_map_read_polylib(s)));
1987
1988 return map;
1989 }
1990
1991 static int optional_power(__isl_keep isl_stream *s)
1992 {
1993 int pow;
1994 struct isl_token *tok;
1995
1996 tok = isl_stream_next_token(s);
1997 if (!tok)
1998 return 1;
1999 if (tok->type != '^') {
2000 isl_stream_push_token(s, tok);
2001 return 1;
2002 }
2003 isl_token_free(tok);
2004 tok = isl_stream_next_token(s);
2005 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2006 isl_stream_error(s, tok, "expecting exponent");
2007 if (tok)
2008 isl_stream_push_token(s, tok);
2009 return 1;
2010 }
2011 pow = isl_int_get_si(tok->u.v);
2012 isl_token_free(tok);
2013 return pow;
2014 }
2015
2016 static __isl_give isl_pw_qpolynomial *read_term(__isl_keep isl_stream *s,
2017 __isl_keep isl_map *map, struct vars *v);
2018
2019 static __isl_give isl_pw_qpolynomial *read_factor(__isl_keep isl_stream *s,
2020 __isl_keep isl_map *map, struct vars *v)
2021 {
2022 isl_pw_qpolynomial *pwqp;
2023 struct isl_token *tok;
2024
2025 tok = next_token(s);
2026 if (!tok) {
2027 isl_stream_error(s, NULL, "unexpected EOF");
2028 return NULL;
2029 }
2030 if (tok->type == '(') {
2031 int pow;
2032
2033 isl_token_free(tok);
2034 pwqp = read_term(s, map, v);
2035 if (!pwqp)
2036 return NULL;
2037 if (isl_stream_eat(s, ')'))
2038 goto error;
2039 pow = optional_power(s);
2040 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
2041 } else if (tok->type == ISL_TOKEN_VALUE) {
2042 struct isl_token *tok2;
2043 isl_qpolynomial *qp;
2044
2045 tok2 = isl_stream_next_token(s);
2046 if (tok2 && tok2->type == '/') {
2047 isl_token_free(tok2);
2048 tok2 = next_token(s);
2049 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
2050 isl_stream_error(s, tok2, "expected denominator");
2051 isl_token_free(tok);
2052 isl_token_free(tok2);
2053 return NULL;
2054 }
2055 qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map),
2056 tok->u.v, tok2->u.v);
2057 isl_token_free(tok2);
2058 } else {
2059 isl_stream_push_token(s, tok2);
2060 qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map),
2061 tok->u.v);
2062 }
2063 isl_token_free(tok);
2064 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2065 } else if (tok->type == ISL_TOKEN_INFTY) {
2066 isl_qpolynomial *qp;
2067 isl_token_free(tok);
2068 qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map));
2069 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2070 } else if (tok->type == ISL_TOKEN_NAN) {
2071 isl_qpolynomial *qp;
2072 isl_token_free(tok);
2073 qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map));
2074 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2075 } else if (tok->type == ISL_TOKEN_IDENT) {
2076 int n = v->n;
2077 int pos = vars_pos(v, tok->u.s, -1);
2078 int pow;
2079 isl_qpolynomial *qp;
2080 if (pos < 0) {
2081 isl_token_free(tok);
2082 return NULL;
2083 }
2084 if (pos >= n) {
2085 vars_drop(v, v->n - n);
2086 isl_stream_error(s, tok, "unknown identifier");
2087 isl_token_free(tok);
2088 return NULL;
2089 }
2090 isl_token_free(tok);
2091 pow = optional_power(s);
2092 qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow);
2093 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2094 } else if (is_start_of_div(tok)) {
2095 isl_pw_aff *pwaff;
2096 int pow;
2097
2098 isl_stream_push_token(s, tok);
2099 pwaff = accept_div(s, isl_map_get_space(map), v);
2100 pow = optional_power(s);
2101 pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff);
2102 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
2103 } else if (tok->type == '-') {
2104 isl_token_free(tok);
2105 pwqp = read_factor(s, map, v);
2106 pwqp = isl_pw_qpolynomial_neg(pwqp);
2107 } else {
2108 isl_stream_error(s, tok, "unexpected isl_token");
2109 isl_stream_push_token(s, tok);
2110 return NULL;
2111 }
2112
2113 if (isl_stream_eat_if_available(s, '*') ||
2114 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
2115 isl_pw_qpolynomial *pwqp2;
2116
2117 pwqp2 = read_factor(s, map, v);
2118 pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2);
2119 }
2120
2121 return pwqp;
2122 error:
2123 isl_pw_qpolynomial_free(pwqp);
2124 return NULL;
2125 }
2126
2127 static __isl_give isl_pw_qpolynomial *read_term(__isl_keep isl_stream *s,
2128 __isl_keep isl_map *map, struct vars *v)
2129 {
2130 struct isl_token *tok;
2131 isl_pw_qpolynomial *pwqp;
2132
2133 pwqp = read_factor(s, map, v);
2134
2135 for (;;) {
2136 tok = next_token(s);
2137 if (!tok)
2138 return pwqp;
2139
2140 if (tok->type == '+') {
2141 isl_pw_qpolynomial *pwqp2;
2142
2143 isl_token_free(tok);
2144 pwqp2 = read_factor(s, map, v);
2145 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
2146 } else if (tok->type == '-') {
2147 isl_pw_qpolynomial *pwqp2;
2148
2149 isl_token_free(tok);
2150 pwqp2 = read_factor(s, map, v);
2151 pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2);
2152 } else if (tok->type == ISL_TOKEN_VALUE &&
2153 isl_int_is_neg(tok->u.v)) {
2154 isl_pw_qpolynomial *pwqp2;
2155
2156 isl_stream_push_token(s, tok);
2157 pwqp2 = read_factor(s, map, v);
2158 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
2159 } else {
2160 isl_stream_push_token(s, tok);
2161 break;
2162 }
2163 }
2164
2165 return pwqp;
2166 }
2167
2168 static __isl_give isl_map *read_optional_formula(__isl_keep isl_stream *s,
2169 __isl_take isl_map *map, struct vars *v, int rational)
2170 {
2171 struct isl_token *tok;
2172
2173 tok = isl_stream_next_token(s);
2174 if (!tok) {
2175 isl_stream_error(s, NULL, "unexpected EOF");
2176 goto error;
2177 }
2178 if (tok->type == ':' ||
2179 (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {
2180 isl_token_free(tok);
2181 map = read_formula(s, v, map, rational);
2182 } else
2183 isl_stream_push_token(s, tok);
2184
2185 return map;
2186 error:
2187 isl_map_free(map);
2188 return NULL;
2189 }
2190
2191 static struct isl_obj obj_read_poly(__isl_keep isl_stream *s,
2192 __isl_take isl_map *map, struct vars *v, int n)
2193 {
2194 struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
2195 isl_pw_qpolynomial *pwqp;
2196 struct isl_set *set;
2197
2198 pwqp = read_term(s, map, v);
2199 map = read_optional_formula(s, map, v, 0);
2200 set = isl_map_range(map);
2201
2202 pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set);
2203
2204 vars_drop(v, v->n - n);
2205
2206 obj.v = pwqp;
2207 return obj;
2208 }
2209
2210 static struct isl_obj obj_read_poly_or_fold(__isl_keep isl_stream *s,
2211 __isl_take isl_set *set, struct vars *v, int n)
2212 {
2213 struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
2214 isl_pw_qpolynomial *pwqp;
2215 isl_pw_qpolynomial_fold *pwf = NULL;
2216
2217 if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
2218 return obj_read_poly(s, set, v, n);
2219
2220 if (isl_stream_eat(s, '('))
2221 goto error;
2222
2223 pwqp = read_term(s, set, v);
2224 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, pwqp);
2225
2226 while (isl_stream_eat_if_available(s, ',')) {
2227 isl_pw_qpolynomial_fold *pwf_i;
2228 pwqp = read_term(s, set, v);
2229 pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max,
2230 pwqp);
2231 pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i);
2232 }
2233
2234 if (isl_stream_eat(s, ')'))
2235 goto error;
2236
2237 set = read_optional_formula(s, set, v, 0);
2238 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set);
2239
2240 vars_drop(v, v->n - n);
2241
2242 obj.v = pwf;
2243 return obj;
2244 error:
2245 isl_set_free(set);
2246 isl_pw_qpolynomial_fold_free(pwf);
2247 obj.type = isl_obj_none;
2248 return obj;
2249 }
2250
2251 static int is_rational(__isl_keep isl_stream *s)
2252 {
2253 struct isl_token *tok;
2254
2255 tok = isl_stream_next_token(s);
2256 if (!tok)
2257 return 0;
2258 if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) {
2259 isl_token_free(tok);
2260 isl_stream_eat(s, ':');
2261 return 1;
2262 }
2263
2264 isl_stream_push_token(s, tok);
2265
2266 return 0;
2267 }
2268
2269 static struct isl_obj obj_read_body(__isl_keep isl_stream *s,
2270 __isl_take isl_map *map, struct vars *v)
2271 {
2272 struct isl_token *tok;
2273 struct isl_obj obj = { isl_obj_set, NULL };
2274 int n = v->n;
2275 int rational;
2276
2277 rational = is_rational(s);
2278 if (rational)
2279 map = isl_map_set_rational(map);
2280
2281 if (isl_stream_next_token_is(s, ':')) {
2282 obj.type = isl_obj_set;
2283 obj.v = read_optional_formula(s, map, v, rational);
2284 return obj;
2285 }
2286
2287 if (!next_is_tuple(s))
2288 return obj_read_poly_or_fold(s, map, v, n);
2289
2290 map = read_map_tuple(s, map, isl_dim_in, v, rational, 0);
2291 if (!map)
2292 goto error;
2293 tok = isl_stream_next_token(s);
2294 if (!tok)
2295 goto error;
2296 if (tok->type == ISL_TOKEN_TO) {
2297 obj.type = isl_obj_map;
2298 isl_token_free(tok);
2299 if (!next_is_tuple(s)) {
2300 isl_set *set = isl_map_domain(map);
2301 return obj_read_poly_or_fold(s, set, v, n);
2302 }
2303 map = read_map_tuple(s, map, isl_dim_out, v, rational, 0);
2304 if (!map)
2305 goto error;
2306 } else {
2307 map = isl_map_domain(map);
2308 isl_stream_push_token(s, tok);
2309 }
2310
2311 map = read_optional_formula(s, map, v, rational);
2312
2313 vars_drop(v, v->n - n);
2314
2315 obj.v = map;
2316 return obj;
2317 error:
2318 isl_map_free(map);
2319 obj.type = isl_obj_none;
2320 return obj;
2321 }
2322
2323 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
2324 {
2325 if (obj.type == isl_obj_map) {
2326 obj.v = isl_union_map_from_map(obj.v);
2327 obj.type = isl_obj_union_map;
2328 } else if (obj.type == isl_obj_set) {
2329 obj.v = isl_union_set_from_set(obj.v);
2330 obj.type = isl_obj_union_set;
2331 } else if (obj.type == isl_obj_pw_qpolynomial) {
2332 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2333 obj.type = isl_obj_union_pw_qpolynomial;
2334 } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
2335 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
2336 obj.type = isl_obj_union_pw_qpolynomial_fold;
2337 } else
2338 isl_assert(ctx, 0, goto error);
2339 return obj;
2340 error:
2341 obj.type->free(obj.v);
2342 obj.type = isl_obj_none;
2343 return obj;
2344 }
2345
2346 static struct isl_obj obj_add(__isl_keep isl_stream *s,
2347 struct isl_obj obj1, struct isl_obj obj2)
2348 {
2349 if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
2350 obj1 = to_union(s->ctx, obj1);
2351 if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
2352 obj2 = to_union(s->ctx, obj2);
2353 if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
2354 obj1 = to_union(s->ctx, obj1);
2355 if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
2356 obj2 = to_union(s->ctx, obj2);
2357 if (obj1.type == isl_obj_pw_qpolynomial &&
2358 obj2.type == isl_obj_union_pw_qpolynomial)
2359 obj1 = to_union(s->ctx, obj1);
2360 if (obj1.type == isl_obj_union_pw_qpolynomial &&
2361 obj2.type == isl_obj_pw_qpolynomial)
2362 obj2 = to_union(s->ctx, obj2);
2363 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2364 obj2.type == isl_obj_union_pw_qpolynomial_fold)
2365 obj1 = to_union(s->ctx, obj1);
2366 if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
2367 obj2.type == isl_obj_pw_qpolynomial_fold)
2368 obj2 = to_union(s->ctx, obj2);
2369 if (obj1.type != obj2.type) {
2370 isl_stream_error(s, NULL,
2371 "attempt to combine incompatible objects");
2372 goto error;
2373 }
2374 if (!obj1.type->add)
2375 isl_die(s->ctx, isl_error_internal,
2376 "combination not supported on object type", goto error);
2377 if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) {
2378 obj1 = to_union(s->ctx, obj1);
2379 obj2 = to_union(s->ctx, obj2);
2380 }
2381 if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) {
2382 obj1 = to_union(s->ctx, obj1);
2383 obj2 = to_union(s->ctx, obj2);
2384 }
2385 if (obj1.type == isl_obj_pw_qpolynomial &&
2386 !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) {
2387 obj1 = to_union(s->ctx, obj1);
2388 obj2 = to_union(s->ctx, obj2);
2389 }
2390 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2391 !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) {
2392 obj1 = to_union(s->ctx, obj1);
2393 obj2 = to_union(s->ctx, obj2);
2394 }
2395 obj1.v = obj1.type->add(obj1.v, obj2.v);
2396 return obj1;
2397 error:
2398 obj1.type->free(obj1.v);
2399 obj2.type->free(obj2.v);
2400 obj1.type = isl_obj_none;
2401 obj1.v = NULL;
2402 return obj1;
2403 }
2404
2405 /* Are the first two tokens on "s", "domain" (either as a string
2406 * or as an identifier) followed by ":"?
2407 */
2408 static int next_is_domain_colon(__isl_keep isl_stream *s)
2409 {
2410 struct isl_token *tok;
2411 char *name;
2412 int res;
2413
2414 tok = isl_stream_next_token(s);
2415 if (!tok)
2416 return 0;
2417 if (tok->type != ISL_TOKEN_IDENT && tok->type != ISL_TOKEN_STRING) {
2418 isl_stream_push_token(s, tok);
2419 return 0;
2420 }
2421
2422 name = isl_token_get_str(s->ctx, tok);
2423 res = !strcmp(name, "domain") && isl_stream_next_token_is(s, ':');
2424 free(name);
2425
2426 isl_stream_push_token(s, tok);
2427
2428 return res;
2429 }
2430
2431 /* Do the first tokens on "s" look like a schedule?
2432 *
2433 * The root of a schedule is always a domain node, so the first thing
2434 * we expect in the stream is a domain key, i.e., "domain" followed
2435 * by ":". If the schedule was printed in YAML flow style, then
2436 * we additionally expect a "{" to open the outer mapping.
2437 */
2438 static int next_is_schedule(__isl_keep isl_stream *s)
2439 {
2440 struct isl_token *tok;
2441 int is_schedule;
2442
2443 tok = isl_stream_next_token(s);
2444 if (!tok)
2445 return 0;
2446 if (tok->type != '{') {
2447 isl_stream_push_token(s, tok);
2448 return next_is_domain_colon(s);
2449 }
2450
2451 is_schedule = next_is_domain_colon(s);
2452 isl_stream_push_token(s, tok);
2453
2454 return is_schedule;
2455 }
2456
2457 /* Read an isl_schedule from "s" and store it in an isl_obj.
2458 */
2459 static struct isl_obj schedule_read(__isl_keep isl_stream *s)
2460 {
2461 struct isl_obj obj;
2462
2463 obj.type = isl_obj_schedule;
2464 obj.v = isl_stream_read_schedule(s);
2465
2466 return obj;
2467 }
2468
2469 static struct isl_obj obj_read(__isl_keep isl_stream *s)
2470 {
2471 isl_map *map = NULL;
2472 struct isl_token *tok;
2473 struct vars *v = NULL;
2474 struct isl_obj obj = { isl_obj_set, NULL };
2475
2476 if (next_is_schedule(s))
2477 return schedule_read(s);
2478
2479 tok = next_token(s);
2480 if (!tok) {
2481 isl_stream_error(s, NULL, "unexpected EOF");
2482 goto error;
2483 }
2484 if (tok->type == ISL_TOKEN_VALUE) {
2485 struct isl_token *tok2;
2486 struct isl_map *map;
2487
2488 tok2 = isl_stream_next_token(s);
2489 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
2490 isl_int_is_neg(tok2->u.v)) {
2491 if (tok2)
2492 isl_stream_push_token(s, tok2);
2493 obj.type = isl_obj_val;
2494 obj.v = isl_val_int_from_isl_int(s->ctx, tok->u.v);
2495 isl_token_free(tok);
2496 return obj;
2497 }
2498 isl_stream_push_token(s, tok2);
2499 isl_stream_push_token(s, tok);
2500 map = map_read_polylib(s);
2501 if (!map)
2502 goto error;
2503 if (isl_map_may_be_set(map))
2504 obj.v = isl_map_range(map);
2505 else {
2506 obj.type = isl_obj_map;
2507 obj.v = map;
2508 }
2509 return obj;
2510 }
2511 v = vars_new(s->ctx);
2512 if (!v) {
2513 isl_stream_push_token(s, tok);
2514 goto error;
2515 }
2516 map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));
2517 if (tok->type == '[') {
2518 isl_stream_push_token(s, tok);
2519 map = read_map_tuple(s, map, isl_dim_param, v, 0, 0);
2520 if (!map)
2521 goto error;
2522 tok = isl_stream_next_token(s);
2523 if (!tok || tok->type != ISL_TOKEN_TO) {
2524 isl_stream_error(s, tok, "expecting '->'");
2525 if (tok)
2526 isl_stream_push_token(s, tok);
2527 goto error;
2528 }
2529 isl_token_free(tok);
2530 tok = isl_stream_next_token(s);
2531 }
2532 if (!tok || tok->type != '{') {
2533 isl_stream_error(s, tok, "expecting '{'");
2534 if (tok)
2535 isl_stream_push_token(s, tok);
2536 goto error;
2537 }
2538 isl_token_free(tok);
2539
2540 tok = isl_stream_next_token(s);
2541 if (!tok)
2542 ;
2543 else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
2544 isl_token_free(tok);
2545 if (isl_stream_eat(s, '='))
2546 goto error;
2547 map = read_map_tuple(s, map, isl_dim_param, v, 0, 1);
2548 if (!map)
2549 goto error;
2550 } else if (tok->type == '}') {
2551 obj.type = isl_obj_union_set;
2552 obj.v = isl_union_set_empty(isl_map_get_space(map));
2553 isl_token_free(tok);
2554 goto done;
2555 } else
2556 isl_stream_push_token(s, tok);
2557
2558 for (;;) {
2559 struct isl_obj o;
2560 tok = NULL;
2561 o = obj_read_body(s, isl_map_copy(map), v);
2562 if (o.type == isl_obj_none || !o.v)
2563 goto error;
2564 if (!obj.v)
2565 obj = o;
2566 else {
2567 obj = obj_add(s, obj, o);
2568 if (obj.type == isl_obj_none || !obj.v)
2569 goto error;
2570 }
2571 tok = isl_stream_next_token(s);
2572 if (!tok || tok->type != ';')
2573 break;
2574 isl_token_free(tok);
2575 if (isl_stream_next_token_is(s, '}')) {
2576 tok = isl_stream_next_token(s);
2577 break;
2578 }
2579 }
2580
2581 if (tok && tok->type == '}') {
2582 isl_token_free(tok);
2583 } else {
2584 isl_stream_error(s, tok, "unexpected isl_token");
2585 if (tok)
2586 isl_token_free(tok);
2587 goto error;
2588 }
2589 done:
2590 vars_free(v);
2591 isl_map_free(map);
2592
2593 return obj;
2594 error:
2595 isl_map_free(map);
2596 obj.type->free(obj.v);
2597 if (v)
2598 vars_free(v);
2599 obj.v = NULL;
2600 return obj;
2601 }
2602
2603 struct isl_obj isl_stream_read_obj(__isl_keep isl_stream *s)
2604 {
2605 return obj_read(s);
2606 }
2607
2608 __isl_give isl_map *isl_stream_read_map(__isl_keep isl_stream *s)
2609 {
2610 struct isl_obj obj;
2611
2612 obj = obj_read(s);
2613 if (obj.v)
2614 isl_assert(s->ctx, obj.type == isl_obj_map ||
2615 obj.type == isl_obj_set, goto error);
2616
2617 if (obj.type == isl_obj_set)
2618 obj.v = isl_map_from_range(obj.v);
2619
2620 return obj.v;
2621 error:
2622 obj.type->free(obj.v);
2623 return NULL;
2624 }
2625
2626 __isl_give isl_set *isl_stream_read_set(__isl_keep isl_stream *s)
2627 {
2628 struct isl_obj obj;
2629
2630 obj = obj_read(s);
2631 if (obj.v) {
2632 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) {
2633 obj.v = isl_map_range(obj.v);
2634 obj.type = isl_obj_set;
2635 }
2636 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2637 }
2638
2639 return obj.v;
2640 error:
2641 obj.type->free(obj.v);
2642 return NULL;
2643 }
2644
2645 __isl_give isl_union_map *isl_stream_read_union_map(__isl_keep isl_stream *s)
2646 {
2647 struct isl_obj obj;
2648
2649 obj = obj_read(s);
2650 if (obj.type == isl_obj_map) {
2651 obj.type = isl_obj_union_map;
2652 obj.v = isl_union_map_from_map(obj.v);
2653 }
2654 if (obj.type == isl_obj_set) {
2655 obj.type = isl_obj_union_set;
2656 obj.v = isl_union_set_from_set(obj.v);
2657 }
2658 if (obj.v && obj.type == isl_obj_union_set &&
2659 isl_union_set_is_empty(obj.v))
2660 obj.type = isl_obj_union_map;
2661 if (obj.v && obj.type != isl_obj_union_map)
2662 isl_die(s->ctx, isl_error_invalid, "invalid input", goto error);
2663
2664 return obj.v;
2665 error:
2666 obj.type->free(obj.v);
2667 return NULL;
2668 }
2669
2670 __isl_give isl_union_set *isl_stream_read_union_set(__isl_keep isl_stream *s)
2671 {
2672 struct isl_obj obj;
2673
2674 obj = obj_read(s);
2675 if (obj.type == isl_obj_set) {
2676 obj.type = isl_obj_union_set;
2677 obj.v = isl_union_set_from_set(obj.v);
2678 }
2679 if (obj.v)
2680 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2681
2682 return obj.v;
2683 error:
2684 obj.type->free(obj.v);
2685 return NULL;
2686 }
2687
2688 static __isl_give isl_basic_map *basic_map_read(__isl_keep isl_stream *s)
2689 {
2690 struct isl_obj obj;
2691 struct isl_map *map;
2692 struct isl_basic_map *bmap;
2693
2694 obj = obj_read(s);
2695 if (obj.v && (obj.type != isl_obj_map && obj.type != isl_obj_set))
2696 isl_die(s->ctx, isl_error_invalid, "not a (basic) set or map",
2697 goto error);
2698 map = obj.v;
2699 if (!map)
2700 return NULL;
2701
2702 if (map->n > 1)
2703 isl_die(s->ctx, isl_error_invalid,
2704 "set or map description involves "
2705 "more than one disjunct", goto error);
2706
2707 if (map->n == 0)
2708 bmap = isl_basic_map_empty_like_map(map);
2709 else
2710 bmap = isl_basic_map_copy(map->p[0]);
2711
2712 isl_map_free(map);
2713
2714 return bmap;
2715 error:
2716 obj.type->free(obj.v);
2717 return NULL;
2718 }
2719
2720 static __isl_give isl_basic_set *basic_set_read(__isl_keep isl_stream *s)
2721 {
2722 isl_basic_map *bmap;
2723 bmap = basic_map_read(s);
2724 if (!bmap)
2725 return NULL;
2726 if (!isl_basic_map_may_be_set(bmap))
2727 isl_die(s->ctx, isl_error_invalid,
2728 "input is not a set", goto error);
2729 return isl_basic_map_range(bmap);
2730 error:
2731 isl_basic_map_free(bmap);
2732 return NULL;
2733 }
2734
2735 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2736 FILE *input)
2737 {
2738 struct isl_basic_map *bmap;
2739 isl_stream *s = isl_stream_new_file(ctx, input);
2740 if (!s)
2741 return NULL;
2742 bmap = basic_map_read(s);
2743 isl_stream_free(s);
2744 return bmap;
2745 }
2746
2747 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2748 FILE *input)
2749 {
2750 isl_basic_set *bset;
2751 isl_stream *s = isl_stream_new_file(ctx, input);
2752 if (!s)
2753 return NULL;
2754 bset = basic_set_read(s);
2755 isl_stream_free(s);
2756 return bset;
2757 }
2758
2759 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2760 const char *str)
2761 {
2762 struct isl_basic_map *bmap;
2763 isl_stream *s = isl_stream_new_str(ctx, str);
2764 if (!s)
2765 return NULL;
2766 bmap = basic_map_read(s);
2767 isl_stream_free(s);
2768 return bmap;
2769 }
2770
2771 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2772 const char *str)
2773 {
2774 isl_basic_set *bset;
2775 isl_stream *s = isl_stream_new_str(ctx, str);
2776 if (!s)
2777 return NULL;
2778 bset = basic_set_read(s);
2779 isl_stream_free(s);
2780 return bset;
2781 }
2782
2783 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2784 FILE *input)
2785 {
2786 struct isl_map *map;
2787 isl_stream *s = isl_stream_new_file(ctx, input);
2788 if (!s)
2789 return NULL;
2790 map = isl_stream_read_map(s);
2791 isl_stream_free(s);
2792 return map;
2793 }
2794
2795 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2796 const char *str)
2797 {
2798 struct isl_map *map;
2799 isl_stream *s = isl_stream_new_str(ctx, str);
2800 if (!s)
2801 return NULL;
2802 map = isl_stream_read_map(s);
2803 isl_stream_free(s);
2804 return map;
2805 }
2806
2807 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2808 FILE *input)
2809 {
2810 isl_set *set;
2811 isl_stream *s = isl_stream_new_file(ctx, input);
2812 if (!s)
2813 return NULL;
2814 set = isl_stream_read_set(s);
2815 isl_stream_free(s);
2816 return set;
2817 }
2818
2819 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2820 const char *str)
2821 {
2822 isl_set *set;
2823 isl_stream *s = isl_stream_new_str(ctx, str);
2824 if (!s)
2825 return NULL;
2826 set = isl_stream_read_set(s);
2827 isl_stream_free(s);
2828 return set;
2829 }
2830
2831 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2832 FILE *input)
2833 {
2834 isl_union_map *umap;
2835 isl_stream *s = isl_stream_new_file(ctx, input);
2836 if (!s)
2837 return NULL;
2838 umap = isl_stream_read_union_map(s);
2839 isl_stream_free(s);
2840 return umap;
2841 }
2842
2843 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2844 const char *str)
2845 {
2846 isl_union_map *umap;
2847 isl_stream *s = isl_stream_new_str(ctx, str);
2848 if (!s)
2849 return NULL;
2850 umap = isl_stream_read_union_map(s);
2851 isl_stream_free(s);
2852 return umap;
2853 }
2854
2855 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2856 FILE *input)
2857 {
2858 isl_union_set *uset;
2859 isl_stream *s = isl_stream_new_file(ctx, input);
2860 if (!s)
2861 return NULL;
2862 uset = isl_stream_read_union_set(s);
2863 isl_stream_free(s);
2864 return uset;
2865 }
2866
2867 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2868 const char *str)
2869 {
2870 isl_union_set *uset;
2871 isl_stream *s = isl_stream_new_str(ctx, str);
2872 if (!s)
2873 return NULL;
2874 uset = isl_stream_read_union_set(s);
2875 isl_stream_free(s);
2876 return uset;
2877 }
2878
2879 static __isl_give isl_vec *isl_vec_read_polylib(__isl_keep isl_stream *s)
2880 {
2881 struct isl_vec *vec = NULL;
2882 struct isl_token *tok;
2883 unsigned size;
2884 int j;
2885
2886 tok = isl_stream_next_token(s);
2887 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2888 isl_stream_error(s, tok, "expecting vector length");
2889 goto error;
2890 }
2891
2892 size = isl_int_get_si(tok->u.v);
2893 isl_token_free(tok);
2894
2895 vec = isl_vec_alloc(s->ctx, size);
2896
2897 for (j = 0; j < size; ++j) {
2898 tok = isl_stream_next_token(s);
2899 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2900 isl_stream_error(s, tok, "expecting constant value");
2901 goto error;
2902 }
2903 isl_int_set(vec->el[j], tok->u.v);
2904 isl_token_free(tok);
2905 }
2906
2907 return vec;
2908 error:
2909 isl_token_free(tok);
2910 isl_vec_free(vec);
2911 return NULL;
2912 }
2913
2914 static __isl_give isl_vec *vec_read(__isl_keep isl_stream *s)
2915 {
2916 return isl_vec_read_polylib(s);
2917 }
2918
2919 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2920 {
2921 isl_vec *v;
2922 isl_stream *s = isl_stream_new_file(ctx, input);
2923 if (!s)
2924 return NULL;
2925 v = vec_read(s);
2926 isl_stream_free(s);
2927 return v;
2928 }
2929
2930 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2931 __isl_keep isl_stream *s)
2932 {
2933 struct isl_obj obj;
2934
2935 obj = obj_read(s);
2936 if (obj.v)
2937 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2938 goto error);
2939
2940 return obj.v;
2941 error:
2942 obj.type->free(obj.v);
2943 return NULL;
2944 }
2945
2946 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2947 const char *str)
2948 {
2949 isl_pw_qpolynomial *pwqp;
2950 isl_stream *s = isl_stream_new_str(ctx, str);
2951 if (!s)
2952 return NULL;
2953 pwqp = isl_stream_read_pw_qpolynomial(s);
2954 isl_stream_free(s);
2955 return pwqp;
2956 }
2957
2958 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
2959 FILE *input)
2960 {
2961 isl_pw_qpolynomial *pwqp;
2962 isl_stream *s = isl_stream_new_file(ctx, input);
2963 if (!s)
2964 return NULL;
2965 pwqp = isl_stream_read_pw_qpolynomial(s);
2966 isl_stream_free(s);
2967 return pwqp;
2968 }
2969
2970 /* Is the next token an identifer not in "v"?
2971 */
2972 static int next_is_fresh_ident(__isl_keep isl_stream *s, struct vars *v)
2973 {
2974 int n = v->n;
2975 int fresh;
2976 struct isl_token *tok;
2977
2978 tok = isl_stream_next_token(s);
2979 if (!tok)
2980 return 0;
2981 fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n;
2982 isl_stream_push_token(s, tok);
2983
2984 vars_drop(v, v->n - n);
2985
2986 return fresh;
2987 }
2988
2989 /* First read the domain of the affine expression, which may be
2990 * a parameter space or a set.
2991 * The tricky part is that we don't know if the domain is a set or not,
2992 * so when we are trying to read the domain, we may actually be reading
2993 * the affine expression itself (defined on a parameter domains)
2994 * If the tuple we are reading is named, we assume it's the domain.
2995 * Also, if inside the tuple, the first thing we find is a nested tuple
2996 * or a new identifier, we again assume it's the domain.
2997 * Otherwise, we assume we are reading an affine expression.
2998 */
2999 static __isl_give isl_set *read_aff_domain(__isl_keep isl_stream *s,
3000 __isl_take isl_set *dom, struct vars *v)
3001 {
3002 struct isl_token *tok;
3003
3004 tok = isl_stream_next_token(s);
3005 if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
3006 isl_stream_push_token(s, tok);
3007 return read_map_tuple(s, dom, isl_dim_set, v, 1, 0);
3008 }
3009 if (!tok || tok->type != '[') {
3010 isl_stream_error(s, tok, "expecting '['");
3011 goto error;
3012 }
3013 if (next_is_tuple(s) || next_is_fresh_ident(s, v)) {
3014 isl_stream_push_token(s, tok);
3015 dom = read_map_tuple(s, dom, isl_dim_set, v, 1, 0);
3016 } else
3017 isl_stream_push_token(s, tok);
3018
3019 return dom;
3020 error:
3021 if (tok)
3022 isl_stream_push_token(s, tok);
3023 isl_set_free(dom);
3024 return NULL;
3025 }
3026
3027 /* Read an affine expression from "s".
3028 */
3029 __isl_give isl_aff *isl_stream_read_aff(__isl_keep isl_stream *s)
3030 {
3031 isl_aff *aff;
3032 isl_multi_aff *ma;
3033
3034 ma = isl_stream_read_multi_aff(s);
3035 if (!ma)
3036 return NULL;
3037 if (isl_multi_aff_dim(ma, isl_dim_out) != 1)
3038 isl_die(s->ctx, isl_error_invalid,
3039 "expecting single affine expression",
3040 goto error);
3041
3042 aff = isl_multi_aff_get_aff(ma, 0);
3043 isl_multi_aff_free(ma);
3044 return aff;
3045 error:
3046 isl_multi_aff_free(ma);
3047 return NULL;
3048 }
3049
3050 /* Read a piecewise affine expression from "s" with domain (space) "dom".
3051 */
3052 static __isl_give isl_pw_aff *read_pw_aff_with_dom(__isl_keep isl_stream *s,
3053 __isl_take isl_set *dom, struct vars *v)
3054 {
3055 isl_pw_aff *pwaff = NULL;
3056
3057 if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
3058 goto error;
3059
3060 if (isl_stream_eat(s, '['))
3061 goto error;
3062
3063 pwaff = accept_affine(s, isl_set_get_space(dom), v);
3064
3065 if (isl_stream_eat(s, ']'))
3066 goto error;
3067
3068 dom = read_optional_formula(s, dom, v, 0);
3069 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
3070
3071 return pwaff;
3072 error:
3073 isl_set_free(dom);
3074 isl_pw_aff_free(pwaff);
3075 return NULL;
3076 }
3077
3078 __isl_give isl_pw_aff *isl_stream_read_pw_aff(__isl_keep isl_stream *s)
3079 {
3080 struct vars *v;
3081 isl_set *dom = NULL;
3082 isl_set *aff_dom;
3083 isl_pw_aff *pa = NULL;
3084 int n;
3085
3086 v = vars_new(s->ctx);
3087 if (!v)
3088 return NULL;
3089
3090 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3091 if (next_is_tuple(s)) {
3092 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3093 if (isl_stream_eat(s, ISL_TOKEN_TO))
3094 goto error;
3095 }
3096 if (isl_stream_eat(s, '{'))
3097 goto error;
3098
3099 n = v->n;
3100 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
3101 pa = read_pw_aff_with_dom(s, aff_dom, v);
3102 vars_drop(v, v->n - n);
3103
3104 while (isl_stream_eat_if_available(s, ';')) {
3105 isl_pw_aff *pa_i;
3106
3107 n = v->n;
3108 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
3109 pa_i = read_pw_aff_with_dom(s, aff_dom, v);
3110 vars_drop(v, v->n - n);
3111
3112 pa = isl_pw_aff_union_add(pa, pa_i);
3113 }
3114
3115 if (isl_stream_eat(s, '}'))
3116 goto error;
3117
3118 vars_free(v);
3119 isl_set_free(dom);
3120 return pa;
3121 error:
3122 vars_free(v);
3123 isl_set_free(dom);
3124 isl_pw_aff_free(pa);
3125 return NULL;
3126 }
3127
3128 __isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str)
3129 {
3130 isl_aff *aff;
3131 isl_stream *s = isl_stream_new_str(ctx, str);
3132 if (!s)
3133 return NULL;
3134 aff = isl_stream_read_aff(s);
3135 isl_stream_free(s);
3136 return aff;
3137 }
3138
3139 __isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str)
3140 {
3141 isl_pw_aff *pa;
3142 isl_stream *s = isl_stream_new_str(ctx, str);
3143 if (!s)
3144 return NULL;
3145 pa = isl_stream_read_pw_aff(s);
3146 isl_stream_free(s);
3147 return pa;
3148 }
3149
3150 /* Read an isl_pw_multi_aff from "s".
3151 * We currently read a generic object and if it turns out to be a set or
3152 * a map, we convert that to an isl_pw_multi_aff.
3153 * It would be more efficient if we were to construct the isl_pw_multi_aff
3154 * directly.
3155 */
3156 __isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(
3157 __isl_keep isl_stream *s)
3158 {
3159 struct isl_obj obj;
3160
3161 obj = obj_read(s);
3162 if (!obj.v)
3163 return NULL;
3164
3165 if (obj.type == isl_obj_map)
3166 return isl_pw_multi_aff_from_map(obj.v);
3167 if (obj.type == isl_obj_set)
3168 return isl_pw_multi_aff_from_set(obj.v);
3169
3170 obj.type->free(obj.v);
3171 isl_die(s->ctx, isl_error_invalid, "unexpected object type",
3172 return NULL);
3173 }
3174
3175 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx,
3176 const char *str)
3177 {
3178 isl_pw_multi_aff *pma;
3179 isl_stream *s = isl_stream_new_str(ctx, str);
3180 if (!s)
3181 return NULL;
3182 pma = isl_stream_read_pw_multi_aff(s);
3183 isl_stream_free(s);
3184 return pma;
3185 }
3186
3187 /* Read an isl_union_pw_multi_aff from "s".
3188 * We currently read a generic object and if it turns out to be a set or
3189 * a map, we convert that to an isl_union_pw_multi_aff.
3190 * It would be more efficient if we were to construct
3191 * the isl_union_pw_multi_aff directly.
3192 */
3193 __isl_give isl_union_pw_multi_aff *isl_stream_read_union_pw_multi_aff(
3194 __isl_keep isl_stream *s)
3195 {
3196 struct isl_obj obj;
3197
3198 obj = obj_read(s);
3199 if (!obj.v)
3200 return NULL;
3201
3202 if (obj.type == isl_obj_map || obj.type == isl_obj_set)
3203 obj = to_union(s->ctx, obj);
3204 if (obj.type == isl_obj_union_map)
3205 return isl_union_pw_multi_aff_from_union_map(obj.v);
3206 if (obj.type == isl_obj_union_set)
3207 return isl_union_pw_multi_aff_from_union_set(obj.v);
3208
3209 obj.type->free(obj.v);
3210 isl_die(s->ctx, isl_error_invalid, "unexpected object type",
3211 return NULL);
3212 }
3213
3214 /* Read an isl_union_pw_multi_aff from "str".
3215 */
3216 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_read_from_str(
3217 isl_ctx *ctx, const char *str)
3218 {
3219 isl_union_pw_multi_aff *upma;
3220 isl_stream *s = isl_stream_new_str(ctx, str);
3221 if (!s)
3222 return NULL;
3223 upma = isl_stream_read_union_pw_multi_aff(s);
3224 isl_stream_free(s);
3225 return upma;
3226 }
3227
3228 /* Assuming "pa" represents a single affine expression defined on a universe
3229 * domain, extract this affine expression.
3230 */
3231 static __isl_give isl_aff *aff_from_pw_aff(__isl_take isl_pw_aff *pa)
3232 {
3233 isl_aff *aff;
3234
3235 if (!pa)
3236 return NULL;
3237 if (pa->n != 1)
3238 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
3239 "expecting single affine expression",
3240 goto error);
3241 if (!isl_set_plain_is_universe(pa->p[0].set))
3242 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
3243 "expecting universe domain",
3244 goto error);
3245
3246 aff = isl_aff_copy(pa->p[0].aff);
3247 isl_pw_aff_free(pa);
3248 return aff;
3249 error:
3250 isl_pw_aff_free(pa);
3251 return NULL;
3252 }
3253
3254 /* This function is called for each element in a tuple inside
3255 * isl_stream_read_multi_val.
3256 * Read an isl_val from "s" and add it to *list.
3257 */
3258 static __isl_give isl_space *read_val_el(__isl_keep isl_stream *s,
3259 struct vars *v, __isl_take isl_space *space, int rational, void *user)
3260 {
3261 isl_val_list **list = (isl_val_list **) user;
3262 isl_val *val;
3263
3264 val = isl_stream_read_val(s);
3265 *list = isl_val_list_add(*list, val);
3266 if (!*list)
3267 return isl_space_free(space);
3268
3269 return space;
3270 }
3271
3272 /* Read an isl_multi_val from "s".
3273 *
3274 * We first read a tuple space, collecting the element values in a list.
3275 * Then we create an isl_multi_val from the space and the isl_val_list.
3276 */
3277 __isl_give isl_multi_val *isl_stream_read_multi_val(__isl_keep isl_stream *s)
3278 {
3279 struct vars *v;
3280 isl_set *dom = NULL;
3281 isl_space *space;
3282 isl_multi_val *mv = NULL;
3283 isl_val_list *list;
3284
3285 v = vars_new(s->ctx);
3286 if (!v)
3287 return NULL;
3288
3289 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3290 if (next_is_tuple(s)) {
3291 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3292 if (isl_stream_eat(s, ISL_TOKEN_TO))
3293 goto error;
3294 }
3295 if (!isl_set_plain_is_universe(dom))
3296 isl_die(s->ctx, isl_error_invalid,
3297 "expecting universe parameter domain", goto error);
3298 if (isl_stream_eat(s, '{'))
3299 goto error;
3300
3301 space = isl_set_get_space(dom);
3302
3303 list = isl_val_list_alloc(s->ctx, 0);
3304 space = read_tuple_space(s, v, space, 1, 0, &read_val_el, &list);
3305 mv = isl_multi_val_from_val_list(space, list);
3306
3307 if (isl_stream_eat(s, '}'))
3308 goto error;
3309
3310 vars_free(v);
3311 isl_set_free(dom);
3312 return mv;
3313 error:
3314 vars_free(v);
3315 isl_set_free(dom);
3316 isl_multi_val_free(mv);
3317 return NULL;
3318 }
3319
3320 /* Read an isl_multi_val from "str".
3321 */
3322 __isl_give isl_multi_val *isl_multi_val_read_from_str(isl_ctx *ctx,
3323 const char *str)
3324 {
3325 isl_multi_val *mv;
3326 isl_stream *s = isl_stream_new_str(ctx, str);
3327 if (!s)
3328 return NULL;
3329 mv = isl_stream_read_multi_val(s);
3330 isl_stream_free(s);
3331 return mv;
3332 }
3333
3334 /* Read a multi-affine expression from "s".
3335 * If the multi-affine expression has a domain, then the tuple
3336 * representing this domain cannot involve any affine expressions.
3337 * The tuple representing the actual expressions needs to consist
3338 * of only affine expressions. Moreover, these expressions can
3339 * only depend on parameters and input dimensions and not on other
3340 * output dimensions.
3341 */
3342 __isl_give isl_multi_aff *isl_stream_read_multi_aff(__isl_keep isl_stream *s)
3343 {
3344 struct vars *v;
3345 isl_set *dom = NULL;
3346 isl_multi_pw_aff *tuple = NULL;
3347 int dim, i, n;
3348 isl_space *space, *dom_space;
3349 isl_multi_aff *ma = NULL;
3350
3351 v = vars_new(s->ctx);
3352 if (!v)
3353 return NULL;
3354
3355 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3356 if (next_is_tuple(s)) {
3357 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3358 if (isl_stream_eat(s, ISL_TOKEN_TO))
3359 goto error;
3360 }
3361 if (!isl_set_plain_is_universe(dom))
3362 isl_die(s->ctx, isl_error_invalid,
3363 "expecting universe parameter domain", goto error);
3364 if (isl_stream_eat(s, '{'))
3365 goto error;
3366
3367 tuple = read_tuple(s, v, 0, 0);
3368 if (!tuple)
3369 goto error;
3370 if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {
3371 isl_set *set;
3372 isl_space *space;
3373 int has_expr;
3374
3375 has_expr = tuple_has_expr(tuple);
3376 if (has_expr < 0)
3377 goto error;
3378 if (has_expr)
3379 isl_die(s->ctx, isl_error_invalid,
3380 "expecting universe domain", goto error);
3381 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3382 set = isl_set_universe(space);
3383 dom = isl_set_intersect_params(set, dom);
3384 isl_multi_pw_aff_free(tuple);
3385 tuple = read_tuple(s, v, 0, 0);
3386 if (!tuple)
3387 goto error;
3388 }
3389
3390 if (isl_stream_eat(s, '}'))
3391 goto error;
3392
3393 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
3394 dim = isl_set_dim(dom, isl_dim_all);
3395 dom_space = isl_set_get_space(dom);
3396 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3397 space = isl_space_align_params(space, isl_space_copy(dom_space));
3398 if (!isl_space_is_params(dom_space))
3399 space = isl_space_map_from_domain_and_range(
3400 isl_space_copy(dom_space), space);
3401 isl_space_free(dom_space);
3402 ma = isl_multi_aff_alloc(space);
3403
3404 for (i = 0; i < n; ++i) {
3405 isl_pw_aff *pa;
3406 isl_aff *aff;
3407 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
3408 aff = aff_from_pw_aff(pa);
3409 if (!aff)
3410 goto error;
3411 if (isl_aff_involves_dims(aff, isl_dim_in, dim, i + 1)) {
3412 isl_aff_free(aff);
3413 isl_die(s->ctx, isl_error_invalid,
3414 "not an affine expression", goto error);
3415 }
3416 aff = isl_aff_drop_dims(aff, isl_dim_in, dim, n);
3417 space = isl_multi_aff_get_domain_space(ma);
3418 aff = isl_aff_reset_domain_space(aff, space);
3419 ma = isl_multi_aff_set_aff(ma, i, aff);
3420 }
3421
3422 isl_multi_pw_aff_free(tuple);
3423 vars_free(v);
3424 isl_set_free(dom);
3425 return ma;
3426 error:
3427 isl_multi_pw_aff_free(tuple);
3428 vars_free(v);
3429 isl_set_free(dom);
3430 isl_multi_aff_free(ma);
3431 return NULL;
3432 }
3433
3434 __isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx,
3435 const char *str)
3436 {
3437 isl_multi_aff *maff;
3438 isl_stream *s = isl_stream_new_str(ctx, str);
3439 if (!s)
3440 return NULL;
3441 maff = isl_stream_read_multi_aff(s);
3442 isl_stream_free(s);
3443 return maff;
3444 }
3445
3446 /* Read an isl_multi_pw_aff from "s".
3447 *
3448 * The input format is similar to that of map, except that any conditions
3449 * on the domains should be specified inside the tuple since each
3450 * piecewise affine expression may have a different domain.
3451 *
3452 * Since we do not know in advance if the isl_multi_pw_aff lives
3453 * in a set or a map space, we first read the first tuple and check
3454 * if it is followed by a "->". If so, we convert the tuple into
3455 * the domain of the isl_multi_pw_aff and read in the next tuple.
3456 * This tuple (or the first tuple if it was not followed by a "->")
3457 * is then converted into the isl_multi_pw_aff.
3458 *
3459 * Note that the function read_tuple accepts tuples where some output or
3460 * set dimensions are defined in terms of other output or set dimensions
3461 * since this function is also used to read maps. As a special case,
3462 * read_tuple also accept dimensions that are defined in terms of themselves
3463 * (i.e., that are not defined).
3464 * These cases are not allowed when reading am isl_multi_pw_aff so we check
3465 * that the definition of the output/set dimensions does not involve any
3466 * output/set dimensions.
3467 * We then drop the output dimensions from the domain of the result
3468 * of read_tuple (which is of the form [input, output] -> [output],
3469 * with anonymous domain) and reset the space.
3470 */
3471 __isl_give isl_multi_pw_aff *isl_stream_read_multi_pw_aff(
3472 __isl_keep isl_stream *s)
3473 {
3474 struct vars *v;
3475 isl_set *dom = NULL;
3476 isl_multi_pw_aff *tuple = NULL;
3477 int dim, i, n;
3478 isl_space *space, *dom_space;
3479 isl_multi_pw_aff *mpa = NULL;
3480
3481 v = vars_new(s->ctx);
3482 if (!v)
3483 return NULL;
3484
3485 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3486 if (next_is_tuple(s)) {
3487 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3488 if (isl_stream_eat(s, ISL_TOKEN_TO))
3489 goto error;
3490 }
3491 if (isl_stream_eat(s, '{'))
3492 goto error;
3493
3494 tuple = read_tuple(s, v, 0, 0);
3495 if (!tuple)
3496 goto error;
3497 if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {
3498 isl_map *map = map_from_tuple(tuple, dom, isl_dim_in, v, 0);
3499 dom = isl_map_domain(map);
3500 tuple = read_tuple(s, v, 0, 0);
3501 if (!tuple)
3502 goto error;
3503 }
3504
3505 if (isl_stream_eat(s, '}'))
3506 goto error;
3507
3508 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
3509 dim = isl_set_dim(dom, isl_dim_all);
3510 dom_space = isl_set_get_space(dom);
3511 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3512 space = isl_space_align_params(space, isl_space_copy(dom_space));
3513 if (!isl_space_is_params(dom_space))
3514 space = isl_space_map_from_domain_and_range(
3515 isl_space_copy(dom_space), space);
3516 isl_space_free(dom_space);
3517 mpa = isl_multi_pw_aff_alloc(space);
3518
3519 for (i = 0; i < n; ++i) {
3520 isl_pw_aff *pa;
3521 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
3522 if (!pa)
3523 goto error;
3524 if (isl_pw_aff_involves_dims(pa, isl_dim_in, dim, i + 1)) {
3525 isl_pw_aff_free(pa);
3526 isl_die(s->ctx, isl_error_invalid,
3527 "not an affine expression", goto error);
3528 }
3529 pa = isl_pw_aff_drop_dims(pa, isl_dim_in, dim, n);
3530 space = isl_multi_pw_aff_get_domain_space(mpa);
3531 pa = isl_pw_aff_reset_domain_space(pa, space);
3532 mpa = isl_multi_pw_aff_set_pw_aff(mpa, i, pa);
3533 }
3534
3535 isl_multi_pw_aff_free(tuple);
3536 vars_free(v);
3537 mpa = isl_multi_pw_aff_intersect_domain(mpa, dom);
3538 return mpa;
3539 error:
3540 isl_multi_pw_aff_free(tuple);
3541 vars_free(v);
3542 isl_set_free(dom);
3543 isl_multi_pw_aff_free(mpa);
3544 return NULL;
3545 }
3546
3547 /* Read an isl_multi_pw_aff from "str".
3548 */
3549 __isl_give isl_multi_pw_aff *isl_multi_pw_aff_read_from_str(isl_ctx *ctx,
3550 const char *str)
3551 {
3552 isl_multi_pw_aff *mpa;
3553 isl_stream *s = isl_stream_new_str(ctx, str);
3554 if (!s)
3555 return NULL;
3556 mpa = isl_stream_read_multi_pw_aff(s);
3557 isl_stream_free(s);
3558 return mpa;
3559 }
3560
3561 /* Read the body of an isl_union_pw_aff from "s" with parameter domain "dom".
3562 */
3563 static __isl_give isl_union_pw_aff *read_union_pw_aff_with_dom(
3564 __isl_keep isl_stream *s, __isl_take isl_set *dom, struct vars *v)
3565 {
3566 isl_pw_aff *pa;
3567 isl_union_pw_aff *upa = NULL;
3568 isl_set *aff_dom;
3569 int n;
3570
3571 n = v->n;
3572 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
3573 pa = read_pw_aff_with_dom(s, aff_dom, v);
3574 vars_drop(v, v->n - n);
3575
3576 upa = isl_union_pw_aff_from_pw_aff(pa);
3577
3578 while (isl_stream_eat_if_available(s, ';')) {
3579 isl_pw_aff *pa_i;
3580 isl_union_pw_aff *upa_i;
3581
3582 n = v->n;
3583 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
3584 pa_i = read_pw_aff_with_dom(s, aff_dom, v);
3585 vars_drop(v, v->n - n);
3586
3587 upa_i = isl_union_pw_aff_from_pw_aff(pa_i);
3588 upa = isl_union_pw_aff_union_add(upa, upa_i);
3589 }
3590
3591 isl_set_free(dom);
3592 return upa;
3593 }
3594
3595 /* This function is called for each element in a tuple inside
3596 * isl_stream_read_multi_union_pw_aff.
3597 *
3598 * Read a '{', the union piecewise affine expression body and a '}' and
3599 * add the isl_union_pw_aff to *list.
3600 */
3601 static __isl_give isl_space *read_union_pw_aff_el(__isl_keep isl_stream *s,
3602 struct vars *v, __isl_take isl_space *space, int rational, void *user)
3603 {
3604 isl_set *dom;
3605 isl_union_pw_aff *upa;
3606 isl_union_pw_aff_list **list = (isl_union_pw_aff_list **) user;
3607
3608 dom = isl_set_universe(isl_space_params(isl_space_copy(space)));
3609 if (isl_stream_eat(s, '{'))
3610 goto error;
3611 upa = read_union_pw_aff_with_dom(s, dom, v);
3612 *list = isl_union_pw_aff_list_add(*list, upa);
3613 if (isl_stream_eat(s, '}'))
3614 return isl_space_free(space);
3615 if (!*list)
3616 return isl_space_free(space);
3617 return space;
3618 error:
3619 isl_set_free(dom);
3620 return isl_space_free(space);
3621 }
3622
3623 /* Do the next tokens in "s" correspond to an empty tuple?
3624 * In particular, does the stream start with a '[', followed by a ']',
3625 * not followed by a "->"?
3626 */
3627 static int next_is_empty_tuple(__isl_keep isl_stream *s)
3628 {
3629 struct isl_token *tok, *tok2, *tok3;
3630 int is_empty_tuple = 0;
3631
3632 tok = isl_stream_next_token(s);
3633 if (!tok)
3634 return 0;
3635 if (tok->type != '[') {
3636 isl_stream_push_token(s, tok);
3637 return 0;
3638 }
3639
3640 tok2 = isl_stream_next_token(s);
3641 if (tok2 && tok2->type == ']') {
3642 tok3 = isl_stream_next_token(s);
3643 is_empty_tuple = !tok || tok->type != ISL_TOKEN_TO;
3644 if (tok3)
3645 isl_stream_push_token(s, tok3);
3646 }
3647 if (tok2)
3648 isl_stream_push_token(s, tok2);
3649 isl_stream_push_token(s, tok);
3650
3651 return is_empty_tuple;
3652 }
3653
3654 /* Do the next tokens in "s" correspond to a tuple of parameters?
3655 * In particular, does the stream start with a '[' that is not
3656 * followed by a '{' or a nested tuple?
3657 */
3658 static int next_is_param_tuple(__isl_keep isl_stream *s)
3659 {
3660 struct isl_token *tok, *tok2;
3661 int is_tuple;
3662
3663 tok = isl_stream_next_token(s);
3664 if (!tok)
3665 return 0;
3666 if (tok->type != '[' || next_is_tuple(s)) {
3667 isl_stream_push_token(s, tok);
3668 return 0;
3669 }
3670
3671 tok2 = isl_stream_next_token(s);
3672 is_tuple = tok2 && tok2->type != '{';
3673 if (tok2)
3674 isl_stream_push_token(s, tok2);
3675 isl_stream_push_token(s, tok);
3676
3677 return is_tuple;
3678 }
3679
3680 /* Read an isl_multi_union_pw_aff from "s".
3681 *
3682 * The input has the form
3683 *
3684 * [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
3685 *
3686 * or
3687 *
3688 * [..] -> [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
3689 *
3690 * We first check for the special case of an empty tuple "[]".
3691 * Then we check if there are any parameters.
3692 * Finally, we read the tuple, collecting the individual isl_union_pw_aff
3693 * elements in a list and construct the result from the tuple space and
3694 * the list.
3695 */
3696 __isl_give isl_multi_union_pw_aff *isl_stream_read_multi_union_pw_aff(
3697 __isl_keep isl_stream *s)
3698 {
3699 struct vars *v;
3700 isl_set *dom = NULL;
3701 isl_space *space;
3702 isl_multi_union_pw_aff *mupa = NULL;
3703 isl_union_pw_aff_list *list;
3704
3705 if (next_is_empty_tuple(s)) {
3706 if (isl_stream_eat(s, '['))
3707 return NULL;
3708 if (isl_stream_eat(s, ']'))
3709 return NULL;
3710 space = isl_space_set_alloc(s->ctx, 0, 0);
3711 return isl_multi_union_pw_aff_zero(space);
3712 }
3713
3714 v = vars_new(s->ctx);
3715 if (!v)
3716 return NULL;
3717
3718 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3719 if (next_is_param_tuple(s)) {
3720 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3721 if (isl_stream_eat(s, ISL_TOKEN_TO))
3722 goto error;
3723 }
3724 space = isl_set_get_space(dom);
3725 isl_set_free(dom);
3726 list = isl_union_pw_aff_list_alloc(s->ctx, 0);
3727 space = read_tuple_space(s, v, space, 1, 0,
3728 &read_union_pw_aff_el, &list);
3729 mupa = isl_multi_union_pw_aff_from_union_pw_aff_list(space, list);
3730
3731 vars_free(v);
3732
3733 return mupa;
3734 error:
3735 vars_free(v);
3736 isl_set_free(dom);
3737 isl_multi_union_pw_aff_free(mupa);
3738 return NULL;
3739 }
3740
3741 /* Read an isl_multi_union_pw_aff from "str".
3742 */
3743 __isl_give isl_multi_union_pw_aff *isl_multi_union_pw_aff_read_from_str(
3744 isl_ctx *ctx, const char *str)
3745 {
3746 isl_multi_union_pw_aff *mupa;
3747 isl_stream *s = isl_stream_new_str(ctx, str);
3748 if (!s)
3749 return NULL;
3750 mupa = isl_stream_read_multi_union_pw_aff(s);
3751 isl_stream_free(s);
3752 return mupa;
3753 }
3754
3755 __isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial(
3756 __isl_keep isl_stream *s)
3757 {
3758 struct isl_obj obj;
3759
3760 obj = obj_read(s);
3761 if (obj.type == isl_obj_pw_qpolynomial) {
3762 obj.type = isl_obj_union_pw_qpolynomial;
3763 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
3764 }
3765 if (obj.v)
3766 isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial,
3767 goto error);
3768
3769 return obj.v;
3770 error:
3771 obj.type->free(obj.v);
3772 return NULL;
3773 }
3774
3775 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str(
3776 isl_ctx *ctx, const char *str)
3777 {
3778 isl_union_pw_qpolynomial *upwqp;
3779 isl_stream *s = isl_stream_new_str(ctx, str);
3780 if (!s)
3781 return NULL;
3782 upwqp = isl_stream_read_union_pw_qpolynomial(s);
3783 isl_stream_free(s);
3784 return upwqp;
3785 }
Integer set library