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