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