?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_input.c: extract out common is_start_of_div
[isl.git] / isl_input.c
blobba10ce89c50684f64f39b61c7acedf0bc3b3af6a
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 * Copyright 2012 Ecole Normale Superieure
5 *
6 * Use of this software is governed by the MIT license
7 *
8 * Written by Sven Verdoolaege, K.U.Leuven, Departement
9 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
10 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
11 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
12 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
13 */
14
15 #include <ctype.h>
16 #include <stdio.h>
17 #include <string.h>
18 #include <isl_ctx_private.h>
19 #include <isl_map_private.h>
20 #include <isl/set.h>
21 #include <isl/seq.h>
22 #include <isl_stream_private.h>
23 #include <isl/obj.h>
24 #include "isl_polynomial_private.h"
25 #include <isl/union_map.h>
26 #include <isl_mat_private.h>
27 #include <isl_aff_private.h>
28 #include <isl/list.h>
29 #include <isl_val_private.h>
30
31 struct variable {
32 char *name;
33 int pos;
34 struct variable *next;
35 };
36
37 struct vars {
38 struct isl_ctx *ctx;
39 int n;
40 struct variable *v;
41 };
42
43 static struct vars *vars_new(struct isl_ctx *ctx)
44 {
45 struct vars *v;
46 v = isl_alloc_type(ctx, struct vars);
47 if (!v)
48 return NULL;
49 v->ctx = ctx;
50 v->n = 0;
51 v->v = NULL;
52 return v;
53 }
54
55 static void variable_free(struct variable *var)
56 {
57 while (var) {
58 struct variable *next = var->next;
59 free(var->name);
60 free(var);
61 var = next;
62 }
63 }
64
65 static void vars_free(struct vars *v)
66 {
67 if (!v)
68 return;
69 variable_free(v->v);
70 free(v);
71 }
72
73 static void vars_drop(struct vars *v, int n)
74 {
75 struct variable *var;
76
77 if (!v || !v->v)
78 return;
79
80 v->n -= n;
81
82 var = v->v;
83 while (--n >= 0) {
84 struct variable *next = var->next;
85 free(var->name);
86 free(var);
87 var = next;
88 }
89 v->v = var;
90 }
91
92 static struct variable *variable_new(struct vars *v, const char *name, int len,
93 int pos)
94 {
95 struct variable *var;
96 var = isl_calloc_type(v->ctx, struct variable);
97 if (!var)
98 goto error;
99 var->name = strdup(name);
100 var->name[len] = '\0';
101 var->pos = pos;
102 var->next = v->v;
103 return var;
104 error:
105 variable_free(v->v);
106 return NULL;
107 }
108
109 static int vars_pos(struct vars *v, const char *s, int len)
110 {
111 int pos;
112 struct variable *q;
113
114 if (len == -1)
115 len = strlen(s);
116 for (q = v->v; q; q = q->next) {
117 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
118 break;
119 }
120 if (q)
121 pos = q->pos;
122 else {
123 pos = v->n;
124 v->v = variable_new(v, s, len, v->n);
125 if (!v->v)
126 return -1;
127 v->n++;
128 }
129 return pos;
130 }
131
132 static int vars_add_anon(struct vars *v)
133 {
134 v->v = variable_new(v, "", 0, v->n);
135
136 if (!v->v)
137 return -1;
138 v->n++;
139
140 return 0;
141 }
142
143 /* Obtain next token, with some preprocessing.
144 * In particular, evaluate expressions of the form x^y,
145 * with x and y values.
146 */
147 static struct isl_token *next_token(struct isl_stream *s)
148 {
149 struct isl_token *tok, *tok2;
150
151 tok = isl_stream_next_token(s);
152 if (!tok || tok->type != ISL_TOKEN_VALUE)
153 return tok;
154 if (!isl_stream_eat_if_available(s, '^'))
155 return tok;
156 tok2 = isl_stream_next_token(s);
157 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
158 isl_stream_error(s, tok2, "expecting constant value");
159 goto error;
160 }
161
162 isl_int_pow_ui(tok->u.v, tok->u.v, isl_int_get_ui(tok2->u.v));
163
164 isl_token_free(tok2);
165 return tok;
166 error:
167 isl_token_free(tok);
168 isl_token_free(tok2);
169 return NULL;
170 }
171
172 /* Read an isl_val from "s".
173 *
174 * The following token sequences are recognized
175 *
176 * "infty" -> infty
177 * "-" "infty" -> -infty
178 * "NaN" -> NaN
179 * n "/" d -> n/d
180 * v -> v
181 *
182 * where n, d and v are integer constants.
183 */
184 __isl_give isl_val *isl_stream_read_val(struct isl_stream *s)
185 {
186 struct isl_token *tok = NULL;
187 struct isl_token *tok2 = NULL;
188 isl_val *val;
189
190 tok = next_token(s);
191 if (!tok) {
192 isl_stream_error(s, NULL, "unexpected EOF");
193 goto error;
194 }
195 if (tok->type == ISL_TOKEN_INFTY) {
196 isl_token_free(tok);
197 return isl_val_infty(s->ctx);
198 }
199 if (tok->type == '-' &&
200 isl_stream_eat_if_available(s, ISL_TOKEN_INFTY)) {
201 isl_token_free(tok);
202 return isl_val_neginfty(s->ctx);
203 }
204 if (tok->type == ISL_TOKEN_NAN) {
205 isl_token_free(tok);
206 return isl_val_nan(s->ctx);
207 }
208 if (tok->type != ISL_TOKEN_VALUE) {
209 isl_stream_error(s, tok, "expecting value");
210 goto error;
211 }
212
213 if (isl_stream_eat_if_available(s, '/')) {
214 tok2 = next_token(s);
215 if (!tok2) {
216 isl_stream_error(s, NULL, "unexpected EOF");
217 goto error;
218 }
219 if (tok2->type != ISL_TOKEN_VALUE) {
220 isl_stream_error(s, tok2, "expecting value");
221 goto error;
222 }
223 val = isl_val_rat_from_isl_int(s->ctx, tok->u.v, tok2->u.v);
224 val = isl_val_normalize(val);
225 } else {
226 val = isl_val_int_from_isl_int(s->ctx, tok->u.v);
227 }
228
229 isl_token_free(tok);
230 isl_token_free(tok2);
231 return val;
232 error:
233 isl_token_free(tok);
234 isl_token_free(tok2);
235 return NULL;
236 }
237
238 /* Read an isl_val from "str".
239 */
240 struct isl_val *isl_val_read_from_str(struct isl_ctx *ctx,
241 const char *str)
242 {
243 isl_val *val;
244 struct isl_stream *s = isl_stream_new_str(ctx, str);
245 if (!s)
246 return NULL;
247 val = isl_stream_read_val(s);
248 isl_stream_free(s);
249 return val;
250 }
251
252 static int accept_cst_factor(struct isl_stream *s, isl_int *f)
253 {
254 struct isl_token *tok;
255
256 tok = next_token(s);
257 if (!tok || tok->type != ISL_TOKEN_VALUE) {
258 isl_stream_error(s, tok, "expecting constant value");
259 goto error;
260 }
261
262 isl_int_mul(*f, *f, tok->u.v);
263
264 isl_token_free(tok);
265
266 if (isl_stream_eat_if_available(s, '*'))
267 return accept_cst_factor(s, f);
268
269 return 0;
270 error:
271 isl_token_free(tok);
272 return -1;
273 }
274
275 /* Given an affine expression aff, return an affine expression
276 * for aff % d, with d the next token on the stream, which is
277 * assumed to be a constant.
278 *
279 * We introduce an integer division q = [aff/d] and the result
280 * is set to aff - d q.
281 */
282 static __isl_give isl_pw_aff *affine_mod(struct isl_stream *s,
283 struct vars *v, __isl_take isl_pw_aff *aff)
284 {
285 struct isl_token *tok;
286 isl_pw_aff *q;
287
288 tok = next_token(s);
289 if (!tok || tok->type != ISL_TOKEN_VALUE) {
290 isl_stream_error(s, tok, "expecting constant value");
291 goto error;
292 }
293
294 q = isl_pw_aff_copy(aff);
295 q = isl_pw_aff_scale_down(q, tok->u.v);
296 q = isl_pw_aff_floor(q);
297 q = isl_pw_aff_scale(q, tok->u.v);
298
299 aff = isl_pw_aff_sub(aff, q);
300
301 isl_token_free(tok);
302 return aff;
303 error:
304 isl_pw_aff_free(aff);
305 isl_token_free(tok);
306 return NULL;
307 }
308
309 static __isl_give isl_pw_aff *accept_affine(struct isl_stream *s,
310 __isl_take isl_space *dim, struct vars *v);
311 static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s,
312 __isl_take isl_space *dim, struct vars *v);
313
314 static __isl_give isl_pw_aff *accept_minmax(struct isl_stream *s,
315 __isl_take isl_space *dim, struct vars *v)
316 {
317 struct isl_token *tok;
318 isl_pw_aff_list *list = NULL;
319 int min;
320
321 tok = isl_stream_next_token(s);
322 if (!tok)
323 goto error;
324 min = tok->type == ISL_TOKEN_MIN;
325 isl_token_free(tok);
326
327 if (isl_stream_eat(s, '('))
328 goto error;
329
330 list = accept_affine_list(s, isl_space_copy(dim), v);
331 if (!list)
332 goto error;
333
334 if (isl_stream_eat(s, ')'))
335 goto error;
336
337 isl_space_free(dim);
338 return min ? isl_pw_aff_list_min(list) : isl_pw_aff_list_max(list);
339 error:
340 isl_space_free(dim);
341 isl_pw_aff_list_free(list);
342 return NULL;
343 }
344
345 /* Is "tok" the start of an integer division?
346 */
347 static int is_start_of_div(struct isl_token *tok)
348 {
349 if (!tok)
350 return 0;
351 if (tok->type == '[')
352 return 1;
353 if (tok->type == ISL_TOKEN_FLOORD)
354 return 1;
355 if (tok->type == ISL_TOKEN_CEILD)
356 return 1;
357 return 0;
358 }
359
360 static __isl_give isl_pw_aff *accept_div(struct isl_stream *s,
361 __isl_take isl_space *dim, struct vars *v)
362 {
363 struct isl_token *tok;
364 int f = 0;
365 int c = 0;
366 isl_pw_aff *pwaff = NULL;
367
368 if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOORD))
369 f = 1;
370 else if (isl_stream_eat_if_available(s, ISL_TOKEN_CEILD))
371 c = 1;
372 if (f || c) {
373 if (isl_stream_eat(s, '('))
374 goto error;
375 } else {
376 if (isl_stream_eat(s, '['))
377 goto error;
378 }
379
380 pwaff = accept_affine(s, isl_space_copy(dim), v);
381
382 if (f || c) {
383 if (isl_stream_eat(s, ','))
384 goto error;
385
386 tok = next_token(s);
387 if (!tok)
388 goto error;
389 if (tok->type != ISL_TOKEN_VALUE) {
390 isl_stream_error(s, tok, "expected denominator");
391 isl_stream_push_token(s, tok);
392 goto error;
393 }
394 isl_pw_aff_scale_down(pwaff, tok->u.v);
395 isl_token_free(tok);
396 }
397
398 if (c)
399 pwaff = isl_pw_aff_ceil(pwaff);
400 else
401 pwaff = isl_pw_aff_floor(pwaff);
402
403 if (f || c) {
404 if (isl_stream_eat(s, ')'))
405 goto error;
406 } else {
407 if (isl_stream_eat(s, ']'))
408 goto error;
409 }
410
411 isl_space_free(dim);
412 return pwaff;
413 error:
414 isl_space_free(dim);
415 isl_pw_aff_free(pwaff);
416 return NULL;
417 }
418
419 static __isl_give isl_pw_aff *accept_affine_factor(struct isl_stream *s,
420 __isl_take isl_space *dim, struct vars *v)
421 {
422 struct isl_token *tok = NULL;
423 isl_pw_aff *res = NULL;
424
425 tok = next_token(s);
426 if (!tok) {
427 isl_stream_error(s, NULL, "unexpected EOF");
428 goto error;
429 }
430
431 if (tok->type == ISL_TOKEN_AFF) {
432 res = isl_pw_aff_copy(tok->u.pwaff);
433 isl_token_free(tok);
434 } else if (tok->type == ISL_TOKEN_IDENT) {
435 int n = v->n;
436 int pos = vars_pos(v, tok->u.s, -1);
437 isl_aff *aff;
438
439 if (pos < 0)
440 goto error;
441 if (pos >= n) {
442 vars_drop(v, v->n - n);
443 isl_stream_error(s, tok, "unknown identifier");
444 goto error;
445 }
446
447 aff = isl_aff_zero_on_domain(isl_local_space_from_space(isl_space_copy(dim)));
448 if (!aff)
449 goto error;
450 isl_int_set_si(aff->v->el[2 + pos], 1);
451 res = isl_pw_aff_from_aff(aff);
452 isl_token_free(tok);
453 } else if (tok->type == ISL_TOKEN_VALUE) {
454 if (isl_stream_eat_if_available(s, '*')) {
455 res = accept_affine_factor(s, isl_space_copy(dim), v);
456 res = isl_pw_aff_scale(res, tok->u.v);
457 } else {
458 isl_local_space *ls;
459 isl_aff *aff;
460 ls = isl_local_space_from_space(isl_space_copy(dim));
461 aff = isl_aff_zero_on_domain(ls);
462 aff = isl_aff_add_constant(aff, tok->u.v);
463 res = isl_pw_aff_from_aff(aff);
464 }
465 isl_token_free(tok);
466 } else if (tok->type == '(') {
467 isl_token_free(tok);
468 tok = NULL;
469 res = accept_affine(s, isl_space_copy(dim), v);
470 if (!res)
471 goto error;
472 if (isl_stream_eat(s, ')'))
473 goto error;
474 } else if (is_start_of_div(tok)) {
475 isl_stream_push_token(s, tok);
476 tok = NULL;
477 res = accept_div(s, isl_space_copy(dim), v);
478 } else if (tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX) {
479 isl_stream_push_token(s, tok);
480 tok = NULL;
481 res = accept_minmax(s, isl_space_copy(dim), v);
482 } else {
483 isl_stream_error(s, tok, "expecting factor");
484 goto error;
485 }
486 if (isl_stream_eat_if_available(s, '%') ||
487 isl_stream_eat_if_available(s, ISL_TOKEN_MOD)) {
488 isl_space_free(dim);
489 return affine_mod(s, v, res);
490 }
491 if (isl_stream_eat_if_available(s, '*')) {
492 isl_int f;
493 isl_int_init(f);
494 isl_int_set_si(f, 1);
495 if (accept_cst_factor(s, &f) < 0) {
496 isl_int_clear(f);
497 goto error2;
498 }
499 res = isl_pw_aff_scale(res, f);
500 isl_int_clear(f);
501 }
502 if (isl_stream_eat_if_available(s, '/')) {
503 isl_int f;
504 isl_int_init(f);
505 isl_int_set_si(f, 1);
506 if (accept_cst_factor(s, &f) < 0) {
507 isl_int_clear(f);
508 goto error2;
509 }
510 res = isl_pw_aff_scale_down(res, f);
511 isl_int_clear(f);
512 }
513
514 isl_space_free(dim);
515 return res;
516 error:
517 isl_token_free(tok);
518 error2:
519 isl_pw_aff_free(res);
520 isl_space_free(dim);
521 return NULL;
522 }
523
524 static __isl_give isl_pw_aff *add_cst(__isl_take isl_pw_aff *pwaff, isl_int v)
525 {
526 isl_aff *aff;
527 isl_space *space;
528
529 space = isl_pw_aff_get_domain_space(pwaff);
530 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
531 aff = isl_aff_add_constant(aff, v);
532
533 return isl_pw_aff_add(pwaff, isl_pw_aff_from_aff(aff));
534 }
535
536 static __isl_give isl_pw_aff *accept_affine(struct isl_stream *s,
537 __isl_take isl_space *dim, struct vars *v)
538 {
539 struct isl_token *tok = NULL;
540 isl_local_space *ls;
541 isl_pw_aff *res;
542 int sign = 1;
543
544 ls = isl_local_space_from_space(isl_space_copy(dim));
545 res = isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls));
546 if (!res)
547 goto error;
548
549 for (;;) {
550 tok = next_token(s);
551 if (!tok) {
552 isl_stream_error(s, NULL, "unexpected EOF");
553 goto error;
554 }
555 if (tok->type == '-') {
556 sign = -sign;
557 isl_token_free(tok);
558 continue;
559 }
560 if (tok->type == '(' || is_start_of_div(tok) ||
561 tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX ||
562 tok->type == ISL_TOKEN_IDENT ||
563 tok->type == ISL_TOKEN_AFF) {
564 isl_pw_aff *term;
565 isl_stream_push_token(s, tok);
566 tok = NULL;
567 term = accept_affine_factor(s, isl_space_copy(dim), v);
568 if (sign < 0)
569 res = isl_pw_aff_sub(res, term);
570 else
571 res = isl_pw_aff_add(res, term);
572 if (!res)
573 goto error;
574 sign = 1;
575 } else if (tok->type == ISL_TOKEN_VALUE) {
576 if (sign < 0)
577 isl_int_neg(tok->u.v, tok->u.v);
578 if (isl_stream_eat_if_available(s, '*') ||
579 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
580 isl_pw_aff *term;
581 term = accept_affine_factor(s,
582 isl_space_copy(dim), v);
583 term = isl_pw_aff_scale(term, tok->u.v);
584 res = isl_pw_aff_add(res, term);
585 if (!res)
586 goto error;
587 } else {
588 res = add_cst(res, tok->u.v);
589 }
590 sign = 1;
591 } else {
592 isl_stream_error(s, tok, "unexpected isl_token");
593 isl_stream_push_token(s, tok);
594 isl_pw_aff_free(res);
595 isl_space_free(dim);
596 return NULL;
597 }
598 isl_token_free(tok);
599
600 tok = next_token(s);
601 if (tok && tok->type == '-') {
602 sign = -sign;
603 isl_token_free(tok);
604 } else if (tok && tok->type == '+') {
605 /* nothing */
606 isl_token_free(tok);
607 } else if (tok && tok->type == ISL_TOKEN_VALUE &&
608 isl_int_is_neg(tok->u.v)) {
609 isl_stream_push_token(s, tok);
610 } else {
611 if (tok)
612 isl_stream_push_token(s, tok);
613 break;
614 }
615 }
616
617 isl_space_free(dim);
618 return res;
619 error:
620 isl_space_free(dim);
621 isl_token_free(tok);
622 isl_pw_aff_free(res);
623 return NULL;
624 }
625
626 static int is_comparator(struct isl_token *tok)
627 {
628 if (!tok)
629 return 0;
630
631 switch (tok->type) {
632 case ISL_TOKEN_LT:
633 case ISL_TOKEN_GT:
634 case ISL_TOKEN_LE:
635 case ISL_TOKEN_GE:
636 case ISL_TOKEN_NE:
637 case '=':
638 return 1;
639 default:
640 return 0;
641 }
642 }
643
644 static struct isl_map *read_disjuncts(struct isl_stream *s,
645 struct vars *v, __isl_take isl_map *map, int rational);
646 static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s,
647 __isl_take isl_space *dim, struct vars *v, int rational);
648
649 /* Accept a ternary operator, given the first argument.
650 */
651 static __isl_give isl_pw_aff *accept_ternary(struct isl_stream *s,
652 __isl_take isl_map *cond, struct vars *v, int rational)
653 {
654 isl_space *dim;
655 isl_pw_aff *pwaff1 = NULL, *pwaff2 = NULL, *pa_cond;
656
657 if (!cond)
658 return NULL;
659
660 if (isl_stream_eat(s, '?'))
661 goto error;
662
663 dim = isl_space_wrap(isl_map_get_space(cond));
664 pwaff1 = accept_extended_affine(s, dim, v, rational);
665 if (!pwaff1)
666 goto error;
667
668 if (isl_stream_eat(s, ':'))
669 goto error;
670
671 dim = isl_pw_aff_get_domain_space(pwaff1);
672 pwaff2 = accept_extended_affine(s, dim, v, rational);
673 if (!pwaff1)
674 goto error;
675
676 pa_cond = isl_set_indicator_function(isl_map_wrap(cond));
677 return isl_pw_aff_cond(pa_cond, pwaff1, pwaff2);
678 error:
679 isl_map_free(cond);
680 isl_pw_aff_free(pwaff1);
681 isl_pw_aff_free(pwaff2);
682 return NULL;
683 }
684
685 /* Accept an affine expression that may involve ternary operators.
686 * We first read an affine expression.
687 * If it is not followed by a comparison operator, we simply return it.
688 * Otherwise, we assume the affine epxression is part of the first
689 * argument of a ternary operator and try to parse that.
690 */
691 static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s,
692 __isl_take isl_space *dim, struct vars *v, int rational)
693 {
694 isl_space *space;
695 isl_map *cond;
696 isl_pw_aff *pwaff;
697 struct isl_token *tok;
698 int line = -1, col = -1;
699 int is_comp;
700
701 tok = isl_stream_next_token(s);
702 if (tok) {
703 line = tok->line;
704 col = tok->col;
705 isl_stream_push_token(s, tok);
706 }
707
708 pwaff = accept_affine(s, dim, v);
709 if (rational)
710 pwaff = isl_pw_aff_set_rational(pwaff);
711 if (!pwaff)
712 return NULL;
713
714 tok = isl_stream_next_token(s);
715 if (!tok)
716 return isl_pw_aff_free(pwaff);
717
718 is_comp = is_comparator(tok);
719 isl_stream_push_token(s, tok);
720 if (!is_comp)
721 return pwaff;
722
723 tok = isl_token_new(s->ctx, line, col, 0);
724 if (!tok)
725 return isl_pw_aff_free(pwaff);
726 tok->type = ISL_TOKEN_AFF;
727 tok->u.pwaff = pwaff;
728
729 space = isl_pw_aff_get_domain_space(pwaff);
730 cond = isl_map_universe(isl_space_unwrap(space));
731
732 isl_stream_push_token(s, tok);
733
734 cond = read_disjuncts(s, v, cond, rational);
735
736 return accept_ternary(s, cond, v, rational);
737 }
738
739 static __isl_give isl_map *read_var_def(struct isl_stream *s,
740 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
741 int rational)
742 {
743 isl_pw_aff *def;
744 int pos;
745 isl_map *def_map;
746
747 if (type == isl_dim_param)
748 pos = isl_map_dim(map, isl_dim_param);
749 else {
750 pos = isl_map_dim(map, isl_dim_in);
751 if (type == isl_dim_out)
752 pos += isl_map_dim(map, isl_dim_out);
753 type = isl_dim_in;
754 }
755 --pos;
756
757 def = accept_extended_affine(s, isl_space_wrap(isl_map_get_space(map)),
758 v, rational);
759 def_map = isl_map_from_pw_aff(def);
760 def_map = isl_map_equate(def_map, type, pos, isl_dim_out, 0);
761 def_map = isl_set_unwrap(isl_map_domain(def_map));
762
763 map = isl_map_intersect(map, def_map);
764
765 return map;
766 }
767
768 static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s,
769 __isl_take isl_space *dim, struct vars *v)
770 {
771 isl_pw_aff *pwaff;
772 isl_pw_aff_list *list;
773 struct isl_token *tok = NULL;
774
775 pwaff = accept_affine(s, isl_space_copy(dim), v);
776 list = isl_pw_aff_list_from_pw_aff(pwaff);
777 if (!list)
778 goto error;
779
780 for (;;) {
781 tok = isl_stream_next_token(s);
782 if (!tok) {
783 isl_stream_error(s, NULL, "unexpected EOF");
784 goto error;
785 }
786 if (tok->type != ',') {
787 isl_stream_push_token(s, tok);
788 break;
789 }
790 isl_token_free(tok);
791
792 pwaff = accept_affine(s, isl_space_copy(dim), v);
793 list = isl_pw_aff_list_concat(list,
794 isl_pw_aff_list_from_pw_aff(pwaff));
795 if (!list)
796 goto error;
797 }
798
799 isl_space_free(dim);
800 return list;
801 error:
802 isl_space_free(dim);
803 isl_pw_aff_list_free(list);
804 return NULL;
805 }
806
807 static __isl_give isl_map *read_defined_var_list(struct isl_stream *s,
808 struct vars *v, __isl_take isl_map *map, int rational)
809 {
810 struct isl_token *tok;
811
812 while ((tok = isl_stream_next_token(s)) != NULL) {
813 int p;
814 int n = v->n;
815
816 if (tok->type != ISL_TOKEN_IDENT)
817 break;
818
819 p = vars_pos(v, tok->u.s, -1);
820 if (p < 0)
821 goto error;
822 if (p < n) {
823 isl_stream_error(s, tok, "expecting unique identifier");
824 goto error;
825 }
826
827 map = isl_map_add_dims(map, isl_dim_out, 1);
828
829 isl_token_free(tok);
830 tok = isl_stream_next_token(s);
831 if (tok && tok->type == '=') {
832 isl_token_free(tok);
833 map = read_var_def(s, map, isl_dim_out, v, rational);
834 tok = isl_stream_next_token(s);
835 }
836
837 if (!tok || tok->type != ',')
838 break;
839
840 isl_token_free(tok);
841 }
842 if (tok)
843 isl_stream_push_token(s, tok);
844
845 return map;
846 error:
847 isl_token_free(tok);
848 isl_map_free(map);
849 return NULL;
850 }
851
852 static int next_is_tuple(struct isl_stream *s)
853 {
854 struct isl_token *tok;
855 int is_tuple;
856
857 tok = isl_stream_next_token(s);
858 if (!tok)
859 return 0;
860 if (tok->type == '[') {
861 isl_stream_push_token(s, tok);
862 return 1;
863 }
864 if (tok->type != ISL_TOKEN_IDENT && !tok->is_keyword) {
865 isl_stream_push_token(s, tok);
866 return 0;
867 }
868
869 is_tuple = isl_stream_next_token_is(s, '[');
870
871 isl_stream_push_token(s, tok);
872
873 return is_tuple;
874 }
875
876 /* Allocate an initial tuple with zero dimensions and an anonymous,
877 * unstructured space.
878 * A tuple is represented as an isl_multi_pw_aff.
879 * The range space is the space of the tuple.
880 * The domain space is an anonymous space
881 * with a dimension for each variable in the set of variables in "v".
882 * If a given dimension is not defined in terms of earlier dimensions in
883 * the input, then the corresponding isl_pw_aff is set equal to one time
884 * the variable corresponding to the dimension being defined.
885 */
886 static __isl_give isl_multi_pw_aff *tuple_alloc(struct vars *v)
887 {
888 return isl_multi_pw_aff_alloc(isl_space_alloc(v->ctx, 0, v->n, 0));
889 }
890
891 /* Is "pa" an expression in term of earlier dimensions?
892 * The alternative is that the dimension is defined to be equal to itself,
893 * meaning that it has a universe domain and an expression that depends
894 * on itself. "i" is the position of the expression in a sequence
895 * of "n" expressions. The final dimensions of "pa" correspond to
896 * these "n" expressions.
897 */
898 static int pw_aff_is_expr(__isl_keep isl_pw_aff *pa, int i, int n)
899 {
900 isl_aff *aff;
901
902 if (!pa)
903 return -1;
904 if (pa->n != 1)
905 return 1;
906 if (!isl_set_plain_is_universe(pa->p[0].set))
907 return 1;
908
909 aff = pa->p[0].aff;
910 if (isl_int_is_zero(aff->v->el[aff->v->size - n + i]))
911 return 1;
912 return 0;
913 }
914
915 /* Does the tuple contain any dimensions that are defined
916 * in terms of earlier dimensions?
917 */
918 static int tuple_has_expr(__isl_keep isl_multi_pw_aff *tuple)
919 {
920 int i, n;
921 int has_expr = 0;
922 isl_pw_aff *pa;
923
924 if (!tuple)
925 return -1;
926 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
927 for (i = 0; i < n; ++i) {
928 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
929 has_expr = pw_aff_is_expr(pa, i, n);
930 isl_pw_aff_free(pa);
931 if (has_expr < 0 || has_expr)
932 break;
933 }
934
935 return has_expr;
936 }
937
938 /* Add a dimension to the given tuple.
939 * The dimension is initially undefined, so it is encoded
940 * as one times itself.
941 */
942 static __isl_give isl_multi_pw_aff *tuple_add_dim(
943 __isl_take isl_multi_pw_aff *tuple, struct vars *v)
944 {
945 isl_space *space;
946 isl_aff *aff;
947 isl_pw_aff *pa;
948
949 tuple = isl_multi_pw_aff_add_dims(tuple, isl_dim_in, 1);
950 space = isl_multi_pw_aff_get_domain_space(tuple);
951 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
952 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, v->n, 1);
953 pa = isl_pw_aff_from_aff(aff);
954 tuple = isl_multi_pw_aff_flat_range_product(tuple,
955 isl_multi_pw_aff_from_pw_aff(pa));
956
957 return tuple;
958 }
959
960 /* Set the name of dimension "pos" in "tuple" to "name".
961 * During printing, we add primes if the same name appears more than once
962 * to distinguish the occurrences. Here, we remove those primes from "name"
963 * before setting the name of the dimension.
964 */
965 static __isl_give isl_multi_pw_aff *tuple_set_dim_name(
966 __isl_take isl_multi_pw_aff *tuple, int pos, char *name)
967 {
968 char *prime;
969
970 if (!name)
971 return tuple;
972
973 prime = strchr(name, '\'');
974 if (prime)
975 *prime = '\0';
976 tuple = isl_multi_pw_aff_set_dim_name(tuple, isl_dim_set, pos, name);
977 if (prime)
978 *prime = '\'';
979
980 return tuple;
981 }
982
983 /* Read an affine expression from "s" and replace the definition
984 * of dimension "pos" in "tuple" by this expression.
985 *
986 * accept_extended_affine requires a wrapped space as input.
987 * The domain space of "tuple", on the other hand is an anonymous space,
988 * so we have to adjust the space of the isl_pw_aff before adding it
989 * to "tuple".
990 */
991 static __isl_give isl_multi_pw_aff *read_tuple_var_def(struct isl_stream *s,
992 __isl_take isl_multi_pw_aff *tuple, int pos, struct vars *v,
993 int rational)
994 {
995 isl_space *space;
996 isl_pw_aff *def;
997
998 space = isl_space_wrap(isl_space_alloc(s->ctx, 0, v->n, 0));
999 def = accept_extended_affine(s, space, v, rational);
1000 space = isl_space_set_alloc(s->ctx, 0, v->n);
1001 def = isl_pw_aff_reset_domain_space(def, space);
1002 tuple = isl_multi_pw_aff_set_pw_aff(tuple, pos, def);
1003
1004 return tuple;
1005 }
1006
1007 /* Read a list of variables and/or affine expressions and return the list
1008 * as an isl_multi_pw_aff.
1009 * The elements in the list are separated by either "," or "][".
1010 * If "comma" is set then only "," is allowed.
1011 */
1012 static __isl_give isl_multi_pw_aff *read_tuple_var_list(struct isl_stream *s,
1013 struct vars *v, int rational, int comma)
1014 {
1015 int i = 0;
1016 struct isl_token *tok;
1017 isl_multi_pw_aff *res;
1018
1019 res = tuple_alloc(v);
1020
1021 if (isl_stream_next_token_is(s, ']'))
1022 return res;
1023
1024 while ((tok = next_token(s)) != NULL) {
1025 int new_name = 0;
1026
1027 res = tuple_add_dim(res, v);
1028
1029 if (tok->type == ISL_TOKEN_IDENT) {
1030 int n = v->n;
1031 int p = vars_pos(v, tok->u.s, -1);
1032 if (p < 0)
1033 goto error;
1034 new_name = p >= n;
1035 }
1036
1037 if (tok->type == '*') {
1038 if (vars_add_anon(v) < 0)
1039 goto error;
1040 isl_token_free(tok);
1041 } else if (new_name) {
1042 res = tuple_set_dim_name(res, i, v->v->name);
1043 isl_token_free(tok);
1044 if (isl_stream_eat_if_available(s, '='))
1045 res = read_tuple_var_def(s, res, i, v,
1046 rational);
1047 } else {
1048 isl_stream_push_token(s, tok);
1049 tok = NULL;
1050 if (vars_add_anon(v) < 0)
1051 goto error;
1052 res = read_tuple_var_def(s, res, i, v, rational);
1053 }
1054
1055 tok = isl_stream_next_token(s);
1056 if (!comma && tok && tok->type == ']' &&
1057 isl_stream_next_token_is(s, '[')) {
1058 isl_token_free(tok);
1059 tok = isl_stream_next_token(s);
1060 } else if (!tok || tok->type != ',')
1061 break;
1062
1063 isl_token_free(tok);
1064 i++;
1065 }
1066 if (tok)
1067 isl_stream_push_token(s, tok);
1068
1069 return res;
1070 error:
1071 isl_token_free(tok);
1072 return isl_multi_pw_aff_free(res);
1073 }
1074
1075 /* Read a tuple and represent it as an isl_multi_pw_aff. See tuple_alloc.
1076 */
1077 static __isl_give isl_multi_pw_aff *read_tuple(struct isl_stream *s,
1078 struct vars *v, int rational, int comma)
1079 {
1080 struct isl_token *tok;
1081 char *name = NULL;
1082 isl_multi_pw_aff *res = NULL;
1083
1084 tok = isl_stream_next_token(s);
1085 if (!tok)
1086 goto error;
1087 if (tok->type == ISL_TOKEN_IDENT || tok->is_keyword) {
1088 name = strdup(tok->u.s);
1089 isl_token_free(tok);
1090 if (!name)
1091 goto error;
1092 } else
1093 isl_stream_push_token(s, tok);
1094 if (isl_stream_eat(s, '['))
1095 goto error;
1096 if (next_is_tuple(s)) {
1097 isl_multi_pw_aff *out;
1098 int n;
1099 res = read_tuple(s, v, rational, comma);
1100 if (isl_stream_eat(s, ISL_TOKEN_TO))
1101 goto error;
1102 out = read_tuple(s, v, rational, comma);
1103 n = isl_multi_pw_aff_dim(out, isl_dim_out);
1104 res = isl_multi_pw_aff_add_dims(res, isl_dim_in, n);
1105 res = isl_multi_pw_aff_range_product(res, out);
1106 } else
1107 res = read_tuple_var_list(s, v, rational, comma);
1108 if (isl_stream_eat(s, ']'))
1109 goto error;
1110
1111 if (name) {
1112 res = isl_multi_pw_aff_set_tuple_name(res, isl_dim_out, name);
1113 free(name);
1114 }
1115
1116 return res;
1117 error:
1118 free(name);
1119 return isl_multi_pw_aff_free(res);
1120 }
1121
1122 /* Read a tuple from "s" and add it to "map".
1123 * The tuple is initially represented as an isl_multi_pw_aff.
1124 * We first create the appropriate space in "map" based on the range
1125 * space of this isl_multi_pw_aff. Then, we add equalities based
1126 * on the affine expressions. These live in an anonymous space,
1127 * however, so we first need to reset the space to that of "map".
1128 */
1129 static __isl_give isl_map *read_map_tuple(struct isl_stream *s,
1130 __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
1131 int rational, int comma)
1132 {
1133 int i, n;
1134 isl_multi_pw_aff *tuple;
1135 isl_space *space = NULL;
1136
1137 tuple = read_tuple(s, v, rational, comma);
1138 if (!tuple)
1139 goto error;
1140
1141 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
1142 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
1143 if (!space)
1144 goto error;
1145
1146 if (type == isl_dim_param) {
1147 if (isl_space_has_tuple_name(space, isl_dim_set) ||
1148 isl_space_is_wrapping(space)) {
1149 isl_die(s->ctx, isl_error_invalid,
1150 "parameter tuples cannot be named or nested",
1151 goto error);
1152 }
1153 map = isl_map_add_dims(map, type, n);
1154 for (i = 0; i < n; ++i) {
1155 isl_id *id;
1156 if (!isl_space_has_dim_name(space, isl_dim_set, i))
1157 isl_die(s->ctx, isl_error_invalid,
1158 "parameters must be named",
1159 goto error);
1160 id = isl_space_get_dim_id(space, isl_dim_set, i);
1161 map = isl_map_set_dim_id(map, isl_dim_param, i, id);
1162 }
1163 } else if (type == isl_dim_in) {
1164 isl_set *set;
1165
1166 set = isl_set_universe(isl_space_copy(space));
1167 if (rational)
1168 set = isl_set_set_rational(set);
1169 set = isl_set_intersect_params(set, isl_map_params(map));
1170 map = isl_map_from_domain(set);
1171 } else {
1172 isl_set *set;
1173
1174 set = isl_set_universe(isl_space_copy(space));
1175 if (rational)
1176 set = isl_set_set_rational(set);
1177 map = isl_map_from_domain_and_range(isl_map_domain(map), set);
1178 }
1179
1180 for (i = 0; i < n; ++i) {
1181 isl_pw_aff *pa;
1182 isl_space *space;
1183 isl_aff *aff;
1184 isl_set *set;
1185 isl_map *map_i;
1186
1187 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
1188 space = isl_pw_aff_get_domain_space(pa);
1189 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1190 aff = isl_aff_add_coefficient_si(aff,
1191 isl_dim_in, v->n - n + i, -1);
1192 pa = isl_pw_aff_add(pa, isl_pw_aff_from_aff(aff));
1193 if (rational)
1194 pa = isl_pw_aff_set_rational(pa);
1195 set = isl_pw_aff_zero_set(pa);
1196 map_i = isl_map_from_range(set);
1197 map_i = isl_map_reset_space(map_i, isl_map_get_space(map));
1198 map = isl_map_intersect(map, map_i);
1199 }
1200
1201 isl_space_free(space);
1202 isl_multi_pw_aff_free(tuple);
1203 return map;
1204 error:
1205 isl_space_free(space);
1206 isl_multi_pw_aff_free(tuple);
1207 isl_map_free(map);
1208 return NULL;
1209 }
1210
1211 static __isl_give isl_set *construct_constraints(
1212 __isl_take isl_set *set, int type,
1213 __isl_keep isl_pw_aff_list *left, __isl_keep isl_pw_aff_list *right,
1214 int rational)
1215 {
1216 isl_set *cond;
1217
1218 left = isl_pw_aff_list_copy(left);
1219 right = isl_pw_aff_list_copy(right);
1220 if (rational) {
1221 left = isl_pw_aff_list_set_rational(left);
1222 right = isl_pw_aff_list_set_rational(right);
1223 }
1224 if (type == ISL_TOKEN_LE)
1225 cond = isl_pw_aff_list_le_set(left, right);
1226 else if (type == ISL_TOKEN_GE)
1227 cond = isl_pw_aff_list_ge_set(left, right);
1228 else if (type == ISL_TOKEN_LT)
1229 cond = isl_pw_aff_list_lt_set(left, right);
1230 else if (type == ISL_TOKEN_GT)
1231 cond = isl_pw_aff_list_gt_set(left, right);
1232 else if (type == ISL_TOKEN_NE)
1233 cond = isl_pw_aff_list_ne_set(left, right);
1234 else
1235 cond = isl_pw_aff_list_eq_set(left, right);
1236
1237 return isl_set_intersect(set, cond);
1238 }
1239
1240 static __isl_give isl_map *add_constraint(struct isl_stream *s,
1241 struct vars *v, __isl_take isl_map *map, int rational)
1242 {
1243 struct isl_token *tok = NULL;
1244 isl_pw_aff_list *list1 = NULL, *list2 = NULL;
1245 isl_set *set;
1246
1247 set = isl_map_wrap(map);
1248 list1 = accept_affine_list(s, isl_set_get_space(set), v);
1249 if (!list1)
1250 goto error;
1251 tok = isl_stream_next_token(s);
1252 if (!is_comparator(tok)) {
1253 isl_stream_error(s, tok, "missing operator");
1254 if (tok)
1255 isl_stream_push_token(s, tok);
1256 tok = NULL;
1257 goto error;
1258 }
1259 for (;;) {
1260 list2 = accept_affine_list(s, isl_set_get_space(set), v);
1261 if (!list2)
1262 goto error;
1263
1264 set = construct_constraints(set, tok->type, list1, list2,
1265 rational);
1266 isl_token_free(tok);
1267 isl_pw_aff_list_free(list1);
1268 list1 = list2;
1269
1270 tok = isl_stream_next_token(s);
1271 if (!is_comparator(tok)) {
1272 if (tok)
1273 isl_stream_push_token(s, tok);
1274 break;
1275 }
1276 }
1277 isl_pw_aff_list_free(list1);
1278
1279 return isl_set_unwrap(set);
1280 error:
1281 if (tok)
1282 isl_token_free(tok);
1283 isl_pw_aff_list_free(list1);
1284 isl_pw_aff_list_free(list2);
1285 isl_set_free(set);
1286 return NULL;
1287 }
1288
1289 static __isl_give isl_map *read_exists(struct isl_stream *s,
1290 struct vars *v, __isl_take isl_map *map, int rational)
1291 {
1292 int n = v->n;
1293 int seen_paren = isl_stream_eat_if_available(s, '(');
1294
1295 map = isl_map_from_domain(isl_map_wrap(map));
1296 map = read_defined_var_list(s, v, map, rational);
1297
1298 if (isl_stream_eat(s, ':'))
1299 goto error;
1300
1301 map = read_disjuncts(s, v, map, rational);
1302 map = isl_set_unwrap(isl_map_domain(map));
1303
1304 vars_drop(v, v->n - n);
1305 if (seen_paren && isl_stream_eat(s, ')'))
1306 goto error;
1307
1308 return map;
1309 error:
1310 isl_map_free(map);
1311 return NULL;
1312 }
1313
1314 /* Parse an expression between parentheses and push the result
1315 * back on the stream.
1316 *
1317 * The parsed expression may be either an affine expression
1318 * or a condition. The first type is pushed onto the stream
1319 * as an isl_pw_aff, while the second is pushed as an isl_map.
1320 *
1321 * If the initial token indicates the start of a condition,
1322 * we parse it as such.
1323 * Otherwise, we first parse an affine expression and push
1324 * that onto the stream. If the affine expression covers the
1325 * entire expression between parentheses, we return.
1326 * Otherwise, we assume that the affine expression is the
1327 * start of a condition and continue parsing.
1328 */
1329 static int resolve_paren_expr(struct isl_stream *s,
1330 struct vars *v, __isl_take isl_map *map, int rational)
1331 {
1332 struct isl_token *tok, *tok2;
1333 int line, col;
1334 isl_pw_aff *pwaff;
1335
1336 tok = isl_stream_next_token(s);
1337 if (!tok || tok->type != '(')
1338 goto error;
1339
1340 if (isl_stream_next_token_is(s, '('))
1341 if (resolve_paren_expr(s, v, isl_map_copy(map), rational))
1342 goto error;
1343
1344 if (isl_stream_next_token_is(s, ISL_TOKEN_EXISTS) ||
1345 isl_stream_next_token_is(s, ISL_TOKEN_NOT) ||
1346 isl_stream_next_token_is(s, ISL_TOKEN_TRUE) ||
1347 isl_stream_next_token_is(s, ISL_TOKEN_FALSE) ||
1348 isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1349 map = read_disjuncts(s, v, map, rational);
1350 if (isl_stream_eat(s, ')'))
1351 goto error;
1352 tok->type = ISL_TOKEN_MAP;
1353 tok->u.map = map;
1354 isl_stream_push_token(s, tok);
1355 return 0;
1356 }
1357
1358 tok2 = isl_stream_next_token(s);
1359 if (!tok2)
1360 goto error;
1361 line = tok2->line;
1362 col = tok2->col;
1363 isl_stream_push_token(s, tok2);
1364
1365 pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v);
1366 if (!pwaff)
1367 goto error;
1368
1369 tok2 = isl_token_new(s->ctx, line, col, 0);
1370 if (!tok2)
1371 goto error2;
1372 tok2->type = ISL_TOKEN_AFF;
1373 tok2->u.pwaff = pwaff;
1374
1375 if (isl_stream_eat_if_available(s, ')')) {
1376 isl_stream_push_token(s, tok2);
1377 isl_token_free(tok);
1378 isl_map_free(map);
1379 return 0;
1380 }
1381
1382 isl_stream_push_token(s, tok2);
1383
1384 map = read_disjuncts(s, v, map, rational);
1385 if (isl_stream_eat(s, ')'))
1386 goto error;
1387
1388 tok->type = ISL_TOKEN_MAP;
1389 tok->u.map = map;
1390 isl_stream_push_token(s, tok);
1391
1392 return 0;
1393 error2:
1394 isl_pw_aff_free(pwaff);
1395 error:
1396 isl_token_free(tok);
1397 isl_map_free(map);
1398 return -1;
1399 }
1400
1401 static __isl_give isl_map *read_conjunct(struct isl_stream *s,
1402 struct vars *v, __isl_take isl_map *map, int rational)
1403 {
1404 if (isl_stream_next_token_is(s, '('))
1405 if (resolve_paren_expr(s, v, isl_map_copy(map), rational))
1406 goto error;
1407
1408 if (isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1409 struct isl_token *tok;
1410 tok = isl_stream_next_token(s);
1411 if (!tok)
1412 goto error;
1413 isl_map_free(map);
1414 map = isl_map_copy(tok->u.map);
1415 isl_token_free(tok);
1416 return map;
1417 }
1418
1419 if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))
1420 return read_exists(s, v, map, rational);
1421
1422 if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))
1423 return map;
1424
1425 if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) {
1426 isl_space *dim = isl_map_get_space(map);
1427 isl_map_free(map);
1428 return isl_map_empty(dim);
1429 }
1430
1431 return add_constraint(s, v, map, rational);
1432 error:
1433 isl_map_free(map);
1434 return NULL;
1435 }
1436
1437 static __isl_give isl_map *read_conjuncts(struct isl_stream *s,
1438 struct vars *v, __isl_take isl_map *map, int rational)
1439 {
1440 isl_map *res;
1441 int negate;
1442
1443 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1444 res = read_conjunct(s, v, isl_map_copy(map), rational);
1445 if (negate)
1446 res = isl_map_subtract(isl_map_copy(map), res);
1447
1448 while (res && isl_stream_eat_if_available(s, ISL_TOKEN_AND)) {
1449 isl_map *res_i;
1450
1451 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1452 res_i = read_conjunct(s, v, isl_map_copy(map), rational);
1453 if (negate)
1454 res = isl_map_subtract(res, res_i);
1455 else
1456 res = isl_map_intersect(res, res_i);
1457 }
1458
1459 isl_map_free(map);
1460 return res;
1461 }
1462
1463 static struct isl_map *read_disjuncts(struct isl_stream *s,
1464 struct vars *v, __isl_take isl_map *map, int rational)
1465 {
1466 isl_map *res;
1467
1468 if (isl_stream_next_token_is(s, '}')) {
1469 isl_space *dim = isl_map_get_space(map);
1470 isl_map_free(map);
1471 return isl_map_universe(dim);
1472 }
1473
1474 res = read_conjuncts(s, v, isl_map_copy(map), rational);
1475 while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
1476 isl_map *res_i;
1477
1478 res_i = read_conjuncts(s, v, isl_map_copy(map), rational);
1479 res = isl_map_union(res, res_i);
1480 }
1481
1482 isl_map_free(map);
1483 return res;
1484 }
1485
1486 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1487 {
1488 if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1489 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1490 isl_basic_map_dim(bmap, isl_dim_in) + pos;
1491 pos -= isl_basic_map_dim(bmap, isl_dim_out);
1492
1493 if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1494 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1495 pos -= isl_basic_map_dim(bmap, isl_dim_in);
1496
1497 if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1498 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1499 isl_basic_map_dim(bmap, isl_dim_in) +
1500 isl_basic_map_dim(bmap, isl_dim_out) + pos;
1501 pos -= isl_basic_map_dim(bmap, isl_dim_div);
1502
1503 if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1504 return 1 + pos;
1505
1506 return 0;
1507 }
1508
1509 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1510 struct isl_stream *s, __isl_take isl_basic_map *bmap)
1511 {
1512 int j;
1513 struct isl_token *tok;
1514 int type;
1515 int k;
1516 isl_int *c;
1517 unsigned nparam;
1518 unsigned dim;
1519
1520 if (!bmap)
1521 return NULL;
1522
1523 nparam = isl_basic_map_dim(bmap, isl_dim_param);
1524 dim = isl_basic_map_dim(bmap, isl_dim_out);
1525
1526 tok = isl_stream_next_token(s);
1527 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1528 isl_stream_error(s, tok, "expecting coefficient");
1529 if (tok)
1530 isl_stream_push_token(s, tok);
1531 goto error;
1532 }
1533 if (!tok->on_new_line) {
1534 isl_stream_error(s, tok, "coefficient should appear on new line");
1535 isl_stream_push_token(s, tok);
1536 goto error;
1537 }
1538
1539 type = isl_int_get_si(tok->u.v);
1540 isl_token_free(tok);
1541
1542 isl_assert(s->ctx, type == 0 || type == 1, goto error);
1543 if (type == 0) {
1544 k = isl_basic_map_alloc_equality(bmap);
1545 c = bmap->eq[k];
1546 } else {
1547 k = isl_basic_map_alloc_inequality(bmap);
1548 c = bmap->ineq[k];
1549 }
1550 if (k < 0)
1551 goto error;
1552
1553 for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1554 int pos;
1555 tok = isl_stream_next_token(s);
1556 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1557 isl_stream_error(s, tok, "expecting coefficient");
1558 if (tok)
1559 isl_stream_push_token(s, tok);
1560 goto error;
1561 }
1562 if (tok->on_new_line) {
1563 isl_stream_error(s, tok,
1564 "coefficient should not appear on new line");
1565 isl_stream_push_token(s, tok);
1566 goto error;
1567 }
1568 pos = polylib_pos_to_isl_pos(bmap, j);
1569 isl_int_set(c[pos], tok->u.v);
1570 isl_token_free(tok);
1571 }
1572
1573 return bmap;
1574 error:
1575 isl_basic_map_free(bmap);
1576 return NULL;
1577 }
1578
1579 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s)
1580 {
1581 int i;
1582 struct isl_token *tok;
1583 struct isl_token *tok2;
1584 int n_row, n_col;
1585 int on_new_line;
1586 unsigned in = 0, out, local = 0;
1587 struct isl_basic_map *bmap = NULL;
1588 int nparam = 0;
1589
1590 tok = isl_stream_next_token(s);
1591 if (!tok) {
1592 isl_stream_error(s, NULL, "unexpected EOF");
1593 return NULL;
1594 }
1595 tok2 = isl_stream_next_token(s);
1596 if (!tok2) {
1597 isl_token_free(tok);
1598 isl_stream_error(s, NULL, "unexpected EOF");
1599 return NULL;
1600 }
1601 if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1602 isl_stream_push_token(s, tok2);
1603 isl_stream_push_token(s, tok);
1604 isl_stream_error(s, NULL,
1605 "expecting constraint matrix dimensions");
1606 return NULL;
1607 }
1608 n_row = isl_int_get_si(tok->u.v);
1609 n_col = isl_int_get_si(tok2->u.v);
1610 on_new_line = tok2->on_new_line;
1611 isl_token_free(tok2);
1612 isl_token_free(tok);
1613 isl_assert(s->ctx, !on_new_line, return NULL);
1614 isl_assert(s->ctx, n_row >= 0, return NULL);
1615 isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1616 tok = isl_stream_next_token_on_same_line(s);
1617 if (tok) {
1618 if (tok->type != ISL_TOKEN_VALUE) {
1619 isl_stream_error(s, tok,
1620 "expecting number of output dimensions");
1621 isl_stream_push_token(s, tok);
1622 goto error;
1623 }
1624 out = isl_int_get_si(tok->u.v);
1625 isl_token_free(tok);
1626
1627 tok = isl_stream_next_token_on_same_line(s);
1628 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1629 isl_stream_error(s, tok,
1630 "expecting number of input dimensions");
1631 if (tok)
1632 isl_stream_push_token(s, tok);
1633 goto error;
1634 }
1635 in = isl_int_get_si(tok->u.v);
1636 isl_token_free(tok);
1637
1638 tok = isl_stream_next_token_on_same_line(s);
1639 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1640 isl_stream_error(s, tok,
1641 "expecting number of existentials");
1642 if (tok)
1643 isl_stream_push_token(s, tok);
1644 goto error;
1645 }
1646 local = isl_int_get_si(tok->u.v);
1647 isl_token_free(tok);
1648
1649 tok = isl_stream_next_token_on_same_line(s);
1650 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1651 isl_stream_error(s, tok,
1652 "expecting number of parameters");
1653 if (tok)
1654 isl_stream_push_token(s, tok);
1655 goto error;
1656 }
1657 nparam = isl_int_get_si(tok->u.v);
1658 isl_token_free(tok);
1659 if (n_col != 1 + out + in + local + nparam + 1) {
1660 isl_stream_error(s, NULL,
1661 "dimensions don't match");
1662 goto error;
1663 }
1664 } else
1665 out = n_col - 2 - nparam;
1666 bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1667 if (!bmap)
1668 return NULL;
1669
1670 for (i = 0; i < local; ++i) {
1671 int k = isl_basic_map_alloc_div(bmap);
1672 if (k < 0)
1673 goto error;
1674 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1675 }
1676
1677 for (i = 0; i < n_row; ++i)
1678 bmap = basic_map_read_polylib_constraint(s, bmap);
1679
1680 tok = isl_stream_next_token_on_same_line(s);
1681 if (tok) {
1682 isl_stream_error(s, tok, "unexpected extra token on line");
1683 isl_stream_push_token(s, tok);
1684 goto error;
1685 }
1686
1687 bmap = isl_basic_map_simplify(bmap);
1688 bmap = isl_basic_map_finalize(bmap);
1689 return bmap;
1690 error:
1691 isl_basic_map_free(bmap);
1692 return NULL;
1693 }
1694
1695 static struct isl_map *map_read_polylib(struct isl_stream *s)
1696 {
1697 struct isl_token *tok;
1698 struct isl_token *tok2;
1699 int i, n;
1700 struct isl_map *map;
1701
1702 tok = isl_stream_next_token(s);
1703 if (!tok) {
1704 isl_stream_error(s, NULL, "unexpected EOF");
1705 return NULL;
1706 }
1707 tok2 = isl_stream_next_token_on_same_line(s);
1708 if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
1709 isl_stream_push_token(s, tok2);
1710 isl_stream_push_token(s, tok);
1711 return isl_map_from_basic_map(basic_map_read_polylib(s));
1712 }
1713 if (tok2) {
1714 isl_stream_error(s, tok2, "unexpected token");
1715 isl_stream_push_token(s, tok2);
1716 isl_stream_push_token(s, tok);
1717 return NULL;
1718 }
1719 n = isl_int_get_si(tok->u.v);
1720 isl_token_free(tok);
1721
1722 isl_assert(s->ctx, n >= 1, return NULL);
1723
1724 map = isl_map_from_basic_map(basic_map_read_polylib(s));
1725
1726 for (i = 1; map && i < n; ++i)
1727 map = isl_map_union(map,
1728 isl_map_from_basic_map(basic_map_read_polylib(s)));
1729
1730 return map;
1731 }
1732
1733 static int optional_power(struct isl_stream *s)
1734 {
1735 int pow;
1736 struct isl_token *tok;
1737
1738 tok = isl_stream_next_token(s);
1739 if (!tok)
1740 return 1;
1741 if (tok->type != '^') {
1742 isl_stream_push_token(s, tok);
1743 return 1;
1744 }
1745 isl_token_free(tok);
1746 tok = isl_stream_next_token(s);
1747 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1748 isl_stream_error(s, tok, "expecting exponent");
1749 if (tok)
1750 isl_stream_push_token(s, tok);
1751 return 1;
1752 }
1753 pow = isl_int_get_si(tok->u.v);
1754 isl_token_free(tok);
1755 return pow;
1756 }
1757
1758 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1759 __isl_keep isl_map *map, struct vars *v);
1760
1761 static __isl_give isl_pw_qpolynomial *read_factor(struct isl_stream *s,
1762 __isl_keep isl_map *map, struct vars *v)
1763 {
1764 isl_pw_qpolynomial *pwqp;
1765 struct isl_token *tok;
1766
1767 tok = next_token(s);
1768 if (!tok) {
1769 isl_stream_error(s, NULL, "unexpected EOF");
1770 return NULL;
1771 }
1772 if (tok->type == '(') {
1773 int pow;
1774
1775 isl_token_free(tok);
1776 pwqp = read_term(s, map, v);
1777 if (!pwqp)
1778 return NULL;
1779 if (isl_stream_eat(s, ')'))
1780 goto error;
1781 pow = optional_power(s);
1782 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1783 } else if (tok->type == ISL_TOKEN_VALUE) {
1784 struct isl_token *tok2;
1785 isl_qpolynomial *qp;
1786
1787 tok2 = isl_stream_next_token(s);
1788 if (tok2 && tok2->type == '/') {
1789 isl_token_free(tok2);
1790 tok2 = next_token(s);
1791 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1792 isl_stream_error(s, tok2, "expected denominator");
1793 isl_token_free(tok);
1794 isl_token_free(tok2);
1795 return NULL;
1796 }
1797 qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map),
1798 tok->u.v, tok2->u.v);
1799 isl_token_free(tok2);
1800 } else {
1801 isl_stream_push_token(s, tok2);
1802 qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map),
1803 tok->u.v);
1804 }
1805 isl_token_free(tok);
1806 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1807 } else if (tok->type == ISL_TOKEN_INFTY) {
1808 isl_qpolynomial *qp;
1809 isl_token_free(tok);
1810 qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map));
1811 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1812 } else if (tok->type == ISL_TOKEN_NAN) {
1813 isl_qpolynomial *qp;
1814 isl_token_free(tok);
1815 qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map));
1816 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1817 } else if (tok->type == ISL_TOKEN_IDENT) {
1818 int n = v->n;
1819 int pos = vars_pos(v, tok->u.s, -1);
1820 int pow;
1821 isl_qpolynomial *qp;
1822 if (pos < 0) {
1823 isl_token_free(tok);
1824 return NULL;
1825 }
1826 if (pos >= n) {
1827 vars_drop(v, v->n - n);
1828 isl_stream_error(s, tok, "unknown identifier");
1829 isl_token_free(tok);
1830 return NULL;
1831 }
1832 isl_token_free(tok);
1833 pow = optional_power(s);
1834 qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow);
1835 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1836 } else if (is_start_of_div(tok)) {
1837 isl_pw_aff *pwaff;
1838 int pow;
1839
1840 isl_stream_push_token(s, tok);
1841 pwaff = accept_div(s, isl_map_get_space(map), v);
1842 pow = optional_power(s);
1843 pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff);
1844 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1845 } else if (tok->type == '-') {
1846 isl_token_free(tok);
1847 pwqp = read_factor(s, map, v);
1848 pwqp = isl_pw_qpolynomial_neg(pwqp);
1849 } else {
1850 isl_stream_error(s, tok, "unexpected isl_token");
1851 isl_stream_push_token(s, tok);
1852 return NULL;
1853 }
1854
1855 if (isl_stream_eat_if_available(s, '*') ||
1856 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
1857 isl_pw_qpolynomial *pwqp2;
1858
1859 pwqp2 = read_factor(s, map, v);
1860 pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2);
1861 }
1862
1863 return pwqp;
1864 error:
1865 isl_pw_qpolynomial_free(pwqp);
1866 return NULL;
1867 }
1868
1869 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1870 __isl_keep isl_map *map, struct vars *v)
1871 {
1872 struct isl_token *tok;
1873 isl_pw_qpolynomial *pwqp;
1874
1875 pwqp = read_factor(s, map, v);
1876
1877 for (;;) {
1878 tok = next_token(s);
1879 if (!tok)
1880 return pwqp;
1881
1882 if (tok->type == '+') {
1883 isl_pw_qpolynomial *pwqp2;
1884
1885 isl_token_free(tok);
1886 pwqp2 = read_factor(s, map, v);
1887 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
1888 } else if (tok->type == '-') {
1889 isl_pw_qpolynomial *pwqp2;
1890
1891 isl_token_free(tok);
1892 pwqp2 = read_factor(s, map, v);
1893 pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2);
1894 } else if (tok->type == ISL_TOKEN_VALUE &&
1895 isl_int_is_neg(tok->u.v)) {
1896 isl_pw_qpolynomial *pwqp2;
1897
1898 isl_stream_push_token(s, tok);
1899 pwqp2 = read_factor(s, map, v);
1900 pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
1901 } else {
1902 isl_stream_push_token(s, tok);
1903 break;
1904 }
1905 }
1906
1907 return pwqp;
1908 }
1909
1910 static __isl_give isl_map *read_optional_disjuncts(struct isl_stream *s,
1911 __isl_take isl_map *map, struct vars *v, int rational)
1912 {
1913 struct isl_token *tok;
1914
1915 tok = isl_stream_next_token(s);
1916 if (!tok) {
1917 isl_stream_error(s, NULL, "unexpected EOF");
1918 goto error;
1919 }
1920 if (tok->type == ':' ||
1921 (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {
1922 isl_token_free(tok);
1923 map = read_disjuncts(s, v, map, rational);
1924 } else
1925 isl_stream_push_token(s, tok);
1926
1927 return map;
1928 error:
1929 isl_map_free(map);
1930 return NULL;
1931 }
1932
1933 static struct isl_obj obj_read_poly(struct isl_stream *s,
1934 __isl_take isl_map *map, struct vars *v, int n)
1935 {
1936 struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
1937 isl_pw_qpolynomial *pwqp;
1938 struct isl_set *set;
1939
1940 pwqp = read_term(s, map, v);
1941 map = read_optional_disjuncts(s, map, v, 0);
1942 set = isl_map_range(map);
1943
1944 pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set);
1945
1946 vars_drop(v, v->n - n);
1947
1948 obj.v = pwqp;
1949 return obj;
1950 }
1951
1952 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
1953 __isl_take isl_set *set, struct vars *v, int n)
1954 {
1955 struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
1956 isl_pw_qpolynomial *pwqp;
1957 isl_pw_qpolynomial_fold *pwf = NULL;
1958
1959 if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
1960 return obj_read_poly(s, set, v, n);
1961
1962 if (isl_stream_eat(s, '('))
1963 goto error;
1964
1965 pwqp = read_term(s, set, v);
1966 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, pwqp);
1967
1968 while (isl_stream_eat_if_available(s, ',')) {
1969 isl_pw_qpolynomial_fold *pwf_i;
1970 pwqp = read_term(s, set, v);
1971 pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max,
1972 pwqp);
1973 pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i);
1974 }
1975
1976 if (isl_stream_eat(s, ')'))
1977 goto error;
1978
1979 set = read_optional_disjuncts(s, set, v, 0);
1980 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set);
1981
1982 vars_drop(v, v->n - n);
1983
1984 obj.v = pwf;
1985 return obj;
1986 error:
1987 isl_set_free(set);
1988 isl_pw_qpolynomial_fold_free(pwf);
1989 obj.type = isl_obj_none;
1990 return obj;
1991 }
1992
1993 static int is_rational(struct isl_stream *s)
1994 {
1995 struct isl_token *tok;
1996
1997 tok = isl_stream_next_token(s);
1998 if (!tok)
1999 return 0;
2000 if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) {
2001 isl_token_free(tok);
2002 isl_stream_eat(s, ':');
2003 return 1;
2004 }
2005
2006 isl_stream_push_token(s, tok);
2007
2008 return 0;
2009 }
2010
2011 static struct isl_obj obj_read_body(struct isl_stream *s,
2012 __isl_take isl_map *map, struct vars *v)
2013 {
2014 struct isl_token *tok;
2015 struct isl_obj obj = { isl_obj_set, NULL };
2016 int n = v->n;
2017 int rational;
2018
2019 rational = is_rational(s);
2020 if (rational)
2021 map = isl_map_set_rational(map);
2022
2023 if (isl_stream_next_token_is(s, ':')) {
2024 obj.type = isl_obj_set;
2025 obj.v = read_optional_disjuncts(s, map, v, rational);
2026 return obj;
2027 }
2028
2029 if (!next_is_tuple(s))
2030 return obj_read_poly_or_fold(s, map, v, n);
2031
2032 map = read_map_tuple(s, map, isl_dim_in, v, rational, 0);
2033 if (!map)
2034 goto error;
2035 tok = isl_stream_next_token(s);
2036 if (!tok)
2037 goto error;
2038 if (tok->type == ISL_TOKEN_TO) {
2039 obj.type = isl_obj_map;
2040 isl_token_free(tok);
2041 if (!next_is_tuple(s)) {
2042 isl_set *set = isl_map_domain(map);
2043 return obj_read_poly_or_fold(s, set, v, n);
2044 }
2045 map = read_map_tuple(s, map, isl_dim_out, v, rational, 0);
2046 if (!map)
2047 goto error;
2048 } else {
2049 map = isl_map_domain(map);
2050 isl_stream_push_token(s, tok);
2051 }
2052
2053 map = read_optional_disjuncts(s, map, v, rational);
2054
2055 vars_drop(v, v->n - n);
2056
2057 obj.v = map;
2058 return obj;
2059 error:
2060 isl_map_free(map);
2061 obj.type = isl_obj_none;
2062 return obj;
2063 }
2064
2065 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
2066 {
2067 if (obj.type == isl_obj_map) {
2068 obj.v = isl_union_map_from_map(obj.v);
2069 obj.type = isl_obj_union_map;
2070 } else if (obj.type == isl_obj_set) {
2071 obj.v = isl_union_set_from_set(obj.v);
2072 obj.type = isl_obj_union_set;
2073 } else if (obj.type == isl_obj_pw_qpolynomial) {
2074 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2075 obj.type = isl_obj_union_pw_qpolynomial;
2076 } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
2077 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
2078 obj.type = isl_obj_union_pw_qpolynomial_fold;
2079 } else
2080 isl_assert(ctx, 0, goto error);
2081 return obj;
2082 error:
2083 obj.type->free(obj.v);
2084 obj.type = isl_obj_none;
2085 return obj;
2086 }
2087
2088 static struct isl_obj obj_add(struct isl_ctx *ctx,
2089 struct isl_obj obj1, struct isl_obj obj2)
2090 {
2091 if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
2092 obj1 = to_union(ctx, obj1);
2093 if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
2094 obj2 = to_union(ctx, obj2);
2095 if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
2096 obj1 = to_union(ctx, obj1);
2097 if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
2098 obj2 = to_union(ctx, obj2);
2099 if (obj1.type == isl_obj_pw_qpolynomial &&
2100 obj2.type == isl_obj_union_pw_qpolynomial)
2101 obj1 = to_union(ctx, obj1);
2102 if (obj1.type == isl_obj_union_pw_qpolynomial &&
2103 obj2.type == isl_obj_pw_qpolynomial)
2104 obj2 = to_union(ctx, obj2);
2105 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2106 obj2.type == isl_obj_union_pw_qpolynomial_fold)
2107 obj1 = to_union(ctx, obj1);
2108 if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
2109 obj2.type == isl_obj_pw_qpolynomial_fold)
2110 obj2 = to_union(ctx, obj2);
2111 isl_assert(ctx, obj1.type == obj2.type, goto error);
2112 if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) {
2113 obj1 = to_union(ctx, obj1);
2114 obj2 = to_union(ctx, obj2);
2115 }
2116 if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) {
2117 obj1 = to_union(ctx, obj1);
2118 obj2 = to_union(ctx, obj2);
2119 }
2120 if (obj1.type == isl_obj_pw_qpolynomial &&
2121 !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) {
2122 obj1 = to_union(ctx, obj1);
2123 obj2 = to_union(ctx, obj2);
2124 }
2125 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2126 !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) {
2127 obj1 = to_union(ctx, obj1);
2128 obj2 = to_union(ctx, obj2);
2129 }
2130 obj1.v = obj1.type->add(obj1.v, obj2.v);
2131 return obj1;
2132 error:
2133 obj1.type->free(obj1.v);
2134 obj2.type->free(obj2.v);
2135 obj1.type = isl_obj_none;
2136 obj1.v = NULL;
2137 return obj1;
2138 }
2139
2140 static struct isl_obj obj_read(struct isl_stream *s)
2141 {
2142 isl_map *map = NULL;
2143 struct isl_token *tok;
2144 struct vars *v = NULL;
2145 struct isl_obj obj = { isl_obj_set, NULL };
2146
2147 tok = next_token(s);
2148 if (!tok) {
2149 isl_stream_error(s, NULL, "unexpected EOF");
2150 goto error;
2151 }
2152 if (tok->type == ISL_TOKEN_VALUE) {
2153 struct isl_token *tok2;
2154 struct isl_map *map;
2155
2156 tok2 = isl_stream_next_token(s);
2157 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
2158 isl_int_is_neg(tok2->u.v)) {
2159 if (tok2)
2160 isl_stream_push_token(s, tok2);
2161 obj.type = isl_obj_int;
2162 obj.v = isl_int_obj_alloc(s->ctx, tok->u.v);
2163 isl_token_free(tok);
2164 return obj;
2165 }
2166 isl_stream_push_token(s, tok2);
2167 isl_stream_push_token(s, tok);
2168 map = map_read_polylib(s);
2169 if (!map)
2170 goto error;
2171 if (isl_map_may_be_set(map))
2172 obj.v = isl_map_range(map);
2173 else {
2174 obj.type = isl_obj_map;
2175 obj.v = map;
2176 }
2177 return obj;
2178 }
2179 v = vars_new(s->ctx);
2180 if (!v) {
2181 isl_stream_push_token(s, tok);
2182 goto error;
2183 }
2184 map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));
2185 if (tok->type == '[') {
2186 isl_stream_push_token(s, tok);
2187 map = read_map_tuple(s, map, isl_dim_param, v, 0, 0);
2188 if (!map)
2189 goto error;
2190 tok = isl_stream_next_token(s);
2191 if (!tok || tok->type != ISL_TOKEN_TO) {
2192 isl_stream_error(s, tok, "expecting '->'");
2193 if (tok)
2194 isl_stream_push_token(s, tok);
2195 goto error;
2196 }
2197 isl_token_free(tok);
2198 tok = isl_stream_next_token(s);
2199 }
2200 if (!tok || tok->type != '{') {
2201 isl_stream_error(s, tok, "expecting '{'");
2202 if (tok)
2203 isl_stream_push_token(s, tok);
2204 goto error;
2205 }
2206 isl_token_free(tok);
2207
2208 tok = isl_stream_next_token(s);
2209 if (!tok)
2210 ;
2211 else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
2212 isl_token_free(tok);
2213 if (isl_stream_eat(s, '='))
2214 goto error;
2215 map = read_map_tuple(s, map, isl_dim_param, v, 0, 1);
2216 if (!map)
2217 goto error;
2218 } else if (tok->type == '}') {
2219 obj.type = isl_obj_union_set;
2220 obj.v = isl_union_set_empty(isl_map_get_space(map));
2221 isl_token_free(tok);
2222 goto done;
2223 } else
2224 isl_stream_push_token(s, tok);
2225
2226 for (;;) {
2227 struct isl_obj o;
2228 tok = NULL;
2229 o = obj_read_body(s, isl_map_copy(map), v);
2230 if (o.type == isl_obj_none || !o.v)
2231 goto error;
2232 if (!obj.v)
2233 obj = o;
2234 else {
2235 obj = obj_add(s->ctx, obj, o);
2236 if (obj.type == isl_obj_none || !obj.v)
2237 goto error;
2238 }
2239 tok = isl_stream_next_token(s);
2240 if (!tok || tok->type != ';')
2241 break;
2242 isl_token_free(tok);
2243 if (isl_stream_next_token_is(s, '}')) {
2244 tok = isl_stream_next_token(s);
2245 break;
2246 }
2247 }
2248
2249 if (tok && tok->type == '}') {
2250 isl_token_free(tok);
2251 } else {
2252 isl_stream_error(s, tok, "unexpected isl_token");
2253 if (tok)
2254 isl_token_free(tok);
2255 goto error;
2256 }
2257 done:
2258 vars_free(v);
2259 isl_map_free(map);
2260
2261 return obj;
2262 error:
2263 isl_map_free(map);
2264 obj.type->free(obj.v);
2265 if (v)
2266 vars_free(v);
2267 obj.v = NULL;
2268 return obj;
2269 }
2270
2271 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
2272 {
2273 return obj_read(s);
2274 }
2275
2276 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s)
2277 {
2278 struct isl_obj obj;
2279
2280 obj = obj_read(s);
2281 if (obj.v)
2282 isl_assert(s->ctx, obj.type == isl_obj_map ||
2283 obj.type == isl_obj_set, goto error);
2284
2285 if (obj.type == isl_obj_set)
2286 obj.v = isl_map_from_range(obj.v);
2287
2288 return obj.v;
2289 error:
2290 obj.type->free(obj.v);
2291 return NULL;
2292 }
2293
2294 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s)
2295 {
2296 struct isl_obj obj;
2297
2298 obj = obj_read(s);
2299 if (obj.v) {
2300 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) {
2301 obj.v = isl_map_range(obj.v);
2302 obj.type = isl_obj_set;
2303 }
2304 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2305 }
2306
2307 return obj.v;
2308 error:
2309 obj.type->free(obj.v);
2310 return NULL;
2311 }
2312
2313 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2314 {
2315 struct isl_obj obj;
2316
2317 obj = obj_read(s);
2318 if (obj.type == isl_obj_map) {
2319 obj.type = isl_obj_union_map;
2320 obj.v = isl_union_map_from_map(obj.v);
2321 }
2322 if (obj.type == isl_obj_set) {
2323 obj.type = isl_obj_union_set;
2324 obj.v = isl_union_set_from_set(obj.v);
2325 }
2326 if (obj.v && obj.type == isl_obj_union_set &&
2327 isl_union_set_is_empty(obj.v))
2328 obj.type = isl_obj_union_map;
2329 if (obj.v && obj.type != isl_obj_union_map)
2330 isl_die(s->ctx, isl_error_invalid, "invalid input", goto error);
2331
2332 return obj.v;
2333 error:
2334 obj.type->free(obj.v);
2335 return NULL;
2336 }
2337
2338 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2339 {
2340 struct isl_obj obj;
2341
2342 obj = obj_read(s);
2343 if (obj.type == isl_obj_set) {
2344 obj.type = isl_obj_union_set;
2345 obj.v = isl_union_set_from_set(obj.v);
2346 }
2347 if (obj.v)
2348 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2349
2350 return obj.v;
2351 error:
2352 obj.type->free(obj.v);
2353 return NULL;
2354 }
2355
2356 static __isl_give isl_basic_map *basic_map_read(struct isl_stream *s)
2357 {
2358 struct isl_obj obj;
2359 struct isl_map *map;
2360 struct isl_basic_map *bmap;
2361
2362 obj = obj_read(s);
2363 map = obj.v;
2364 if (!map)
2365 return NULL;
2366
2367 isl_assert(map->ctx, map->n <= 1, goto error);
2368
2369 if (map->n == 0)
2370 bmap = isl_basic_map_empty_like_map(map);
2371 else
2372 bmap = isl_basic_map_copy(map->p[0]);
2373
2374 isl_map_free(map);
2375
2376 return bmap;
2377 error:
2378 isl_map_free(map);
2379 return NULL;
2380 }
2381
2382 static __isl_give isl_basic_set *basic_set_read(struct isl_stream *s)
2383 {
2384 isl_basic_map *bmap;
2385 bmap = basic_map_read(s);
2386 if (!bmap)
2387 return NULL;
2388 if (!isl_basic_map_may_be_set(bmap))
2389 isl_die(s->ctx, isl_error_invalid,
2390 "input is not a set", goto error);
2391 return isl_basic_map_range(bmap);
2392 error:
2393 isl_basic_map_free(bmap);
2394 return NULL;
2395 }
2396
2397 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2398 FILE *input)
2399 {
2400 struct isl_basic_map *bmap;
2401 struct isl_stream *s = isl_stream_new_file(ctx, input);
2402 if (!s)
2403 return NULL;
2404 bmap = basic_map_read(s);
2405 isl_stream_free(s);
2406 return bmap;
2407 }
2408
2409 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2410 FILE *input)
2411 {
2412 isl_basic_set *bset;
2413 struct isl_stream *s = isl_stream_new_file(ctx, input);
2414 if (!s)
2415 return NULL;
2416 bset = basic_set_read(s);
2417 isl_stream_free(s);
2418 return bset;
2419 }
2420
2421 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2422 const char *str)
2423 {
2424 struct isl_basic_map *bmap;
2425 struct isl_stream *s = isl_stream_new_str(ctx, str);
2426 if (!s)
2427 return NULL;
2428 bmap = basic_map_read(s);
2429 isl_stream_free(s);
2430 return bmap;
2431 }
2432
2433 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2434 const char *str)
2435 {
2436 isl_basic_set *bset;
2437 struct isl_stream *s = isl_stream_new_str(ctx, str);
2438 if (!s)
2439 return NULL;
2440 bset = basic_set_read(s);
2441 isl_stream_free(s);
2442 return bset;
2443 }
2444
2445 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2446 FILE *input)
2447 {
2448 struct isl_map *map;
2449 struct isl_stream *s = isl_stream_new_file(ctx, input);
2450 if (!s)
2451 return NULL;
2452 map = isl_stream_read_map(s);
2453 isl_stream_free(s);
2454 return map;
2455 }
2456
2457 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2458 const char *str)
2459 {
2460 struct isl_map *map;
2461 struct isl_stream *s = isl_stream_new_str(ctx, str);
2462 if (!s)
2463 return NULL;
2464 map = isl_stream_read_map(s);
2465 isl_stream_free(s);
2466 return map;
2467 }
2468
2469 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2470 FILE *input)
2471 {
2472 isl_set *set;
2473 struct isl_stream *s = isl_stream_new_file(ctx, input);
2474 if (!s)
2475 return NULL;
2476 set = isl_stream_read_set(s);
2477 isl_stream_free(s);
2478 return set;
2479 }
2480
2481 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2482 const char *str)
2483 {
2484 isl_set *set;
2485 struct isl_stream *s = isl_stream_new_str(ctx, str);
2486 if (!s)
2487 return NULL;
2488 set = isl_stream_read_set(s);
2489 isl_stream_free(s);
2490 return set;
2491 }
2492
2493 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2494 FILE *input)
2495 {
2496 isl_union_map *umap;
2497 struct isl_stream *s = isl_stream_new_file(ctx, input);
2498 if (!s)
2499 return NULL;
2500 umap = isl_stream_read_union_map(s);
2501 isl_stream_free(s);
2502 return umap;
2503 }
2504
2505 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2506 const char *str)
2507 {
2508 isl_union_map *umap;
2509 struct isl_stream *s = isl_stream_new_str(ctx, str);
2510 if (!s)
2511 return NULL;
2512 umap = isl_stream_read_union_map(s);
2513 isl_stream_free(s);
2514 return umap;
2515 }
2516
2517 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2518 FILE *input)
2519 {
2520 isl_union_set *uset;
2521 struct isl_stream *s = isl_stream_new_file(ctx, input);
2522 if (!s)
2523 return NULL;
2524 uset = isl_stream_read_union_set(s);
2525 isl_stream_free(s);
2526 return uset;
2527 }
2528
2529 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2530 const char *str)
2531 {
2532 isl_union_set *uset;
2533 struct isl_stream *s = isl_stream_new_str(ctx, str);
2534 if (!s)
2535 return NULL;
2536 uset = isl_stream_read_union_set(s);
2537 isl_stream_free(s);
2538 return uset;
2539 }
2540
2541 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2542 {
2543 struct isl_vec *vec = NULL;
2544 struct isl_token *tok;
2545 unsigned size;
2546 int j;
2547
2548 tok = isl_stream_next_token(s);
2549 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2550 isl_stream_error(s, tok, "expecting vector length");
2551 goto error;
2552 }
2553
2554 size = isl_int_get_si(tok->u.v);
2555 isl_token_free(tok);
2556
2557 vec = isl_vec_alloc(s->ctx, size);
2558
2559 for (j = 0; j < size; ++j) {
2560 tok = isl_stream_next_token(s);
2561 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2562 isl_stream_error(s, tok, "expecting constant value");
2563 goto error;
2564 }
2565 isl_int_set(vec->el[j], tok->u.v);
2566 isl_token_free(tok);
2567 }
2568
2569 return vec;
2570 error:
2571 isl_token_free(tok);
2572 isl_vec_free(vec);
2573 return NULL;
2574 }
2575
2576 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2577 {
2578 return isl_vec_read_polylib(s);
2579 }
2580
2581 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2582 {
2583 isl_vec *v;
2584 struct isl_stream *s = isl_stream_new_file(ctx, input);
2585 if (!s)
2586 return NULL;
2587 v = vec_read(s);
2588 isl_stream_free(s);
2589 return v;
2590 }
2591
2592 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2593 struct isl_stream *s)
2594 {
2595 struct isl_obj obj;
2596
2597 obj = obj_read(s);
2598 if (obj.v)
2599 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2600 goto error);
2601
2602 return obj.v;
2603 error:
2604 obj.type->free(obj.v);
2605 return NULL;
2606 }
2607
2608 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2609 const char *str)
2610 {
2611 isl_pw_qpolynomial *pwqp;
2612 struct isl_stream *s = isl_stream_new_str(ctx, str);
2613 if (!s)
2614 return NULL;
2615 pwqp = isl_stream_read_pw_qpolynomial(s);
2616 isl_stream_free(s);
2617 return pwqp;
2618 }
2619
2620 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
2621 FILE *input)
2622 {
2623 isl_pw_qpolynomial *pwqp;
2624 struct isl_stream *s = isl_stream_new_file(ctx, input);
2625 if (!s)
2626 return NULL;
2627 pwqp = isl_stream_read_pw_qpolynomial(s);
2628 isl_stream_free(s);
2629 return pwqp;
2630 }
2631
2632 /* Is the next token an identifer not in "v"?
2633 */
2634 static int next_is_fresh_ident(struct isl_stream *s, struct vars *v)
2635 {
2636 int n = v->n;
2637 int fresh;
2638 struct isl_token *tok;
2639
2640 tok = isl_stream_next_token(s);
2641 if (!tok)
2642 return 0;
2643 fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n;
2644 isl_stream_push_token(s, tok);
2645
2646 vars_drop(v, v->n - n);
2647
2648 return fresh;
2649 }
2650
2651 /* First read the domain of the affine expression, which may be
2652 * a parameter space or a set.
2653 * The tricky part is that we don't know if the domain is a set or not,
2654 * so when we are trying to read the domain, we may actually be reading
2655 * the affine expression itself (defined on a parameter domains)
2656 * If the tuple we are reading is named, we assume it's the domain.
2657 * Also, if inside the tuple, the first thing we find is a nested tuple
2658 * or a new identifier, we again assume it's the domain.
2659 * Otherwise, we assume we are reading an affine expression.
2660 */
2661 static __isl_give isl_set *read_aff_domain(struct isl_stream *s,
2662 __isl_take isl_set *dom, struct vars *v)
2663 {
2664 struct isl_token *tok;
2665
2666 tok = isl_stream_next_token(s);
2667 if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
2668 isl_stream_push_token(s, tok);
2669 return read_map_tuple(s, dom, isl_dim_set, v, 1, 0);
2670 }
2671 if (!tok || tok->type != '[') {
2672 isl_stream_error(s, tok, "expecting '['");
2673 goto error;
2674 }
2675 if (next_is_tuple(s) || next_is_fresh_ident(s, v)) {
2676 isl_stream_push_token(s, tok);
2677 dom = read_map_tuple(s, dom, isl_dim_set, v, 1, 0);
2678 } else
2679 isl_stream_push_token(s, tok);
2680
2681 return dom;
2682 error:
2683 if (tok)
2684 isl_stream_push_token(s, tok);
2685 isl_set_free(dom);
2686 return NULL;
2687 }
2688
2689 /* Read an affine expression from "s".
2690 */
2691 __isl_give isl_aff *isl_stream_read_aff(struct isl_stream *s)
2692 {
2693 isl_aff *aff;
2694 isl_multi_aff *ma;
2695
2696 ma = isl_stream_read_multi_aff(s);
2697 if (!ma)
2698 return NULL;
2699 if (isl_multi_aff_dim(ma, isl_dim_out) != 1)
2700 isl_die(s->ctx, isl_error_invalid,
2701 "expecting single affine expression",
2702 goto error);
2703
2704 aff = isl_multi_aff_get_aff(ma, 0);
2705 isl_multi_aff_free(ma);
2706 return aff;
2707 error:
2708 isl_multi_aff_free(ma);
2709 return NULL;
2710 }
2711
2712 /* Read a piecewise affine expression from "s" with domain (space) "dom".
2713 */
2714 static __isl_give isl_pw_aff *read_pw_aff_with_dom(struct isl_stream *s,
2715 __isl_take isl_set *dom, struct vars *v)
2716 {
2717 isl_pw_aff *pwaff = NULL;
2718
2719 if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2720 goto error;
2721
2722 if (isl_stream_eat(s, '['))
2723 goto error;
2724
2725 pwaff = accept_affine(s, isl_set_get_space(dom), v);
2726
2727 if (isl_stream_eat(s, ']'))
2728 goto error;
2729
2730 dom = read_optional_disjuncts(s, dom, v, 0);
2731 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2732
2733 return pwaff;
2734 error:
2735 isl_set_free(dom);
2736 isl_pw_aff_free(pwaff);
2737 return NULL;
2738 }
2739
2740 __isl_give isl_pw_aff *isl_stream_read_pw_aff(struct isl_stream *s)
2741 {
2742 struct vars *v;
2743 isl_set *dom = NULL;
2744 isl_set *aff_dom;
2745 isl_pw_aff *pa = NULL;
2746 int n;
2747
2748 v = vars_new(s->ctx);
2749 if (!v)
2750 return NULL;
2751
2752 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2753 if (next_is_tuple(s)) {
2754 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
2755 if (isl_stream_eat(s, ISL_TOKEN_TO))
2756 goto error;
2757 }
2758 if (isl_stream_eat(s, '{'))
2759 goto error;
2760
2761 n = v->n;
2762 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2763 pa = read_pw_aff_with_dom(s, aff_dom, v);
2764 vars_drop(v, v->n - n);
2765
2766 while (isl_stream_eat_if_available(s, ';')) {
2767 isl_pw_aff *pa_i;
2768
2769 n = v->n;
2770 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2771 pa_i = read_pw_aff_with_dom(s, aff_dom, v);
2772 vars_drop(v, v->n - n);
2773
2774 pa = isl_pw_aff_union_add(pa, pa_i);
2775 }
2776
2777 if (isl_stream_eat(s, '}'))
2778 goto error;
2779
2780 vars_free(v);
2781 isl_set_free(dom);
2782 return pa;
2783 error:
2784 vars_free(v);
2785 isl_set_free(dom);
2786 isl_pw_aff_free(pa);
2787 return NULL;
2788 }
2789
2790 __isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str)
2791 {
2792 isl_aff *aff;
2793 struct isl_stream *s = isl_stream_new_str(ctx, str);
2794 if (!s)
2795 return NULL;
2796 aff = isl_stream_read_aff(s);
2797 isl_stream_free(s);
2798 return aff;
2799 }
2800
2801 __isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str)
2802 {
2803 isl_pw_aff *pa;
2804 struct isl_stream *s = isl_stream_new_str(ctx, str);
2805 if (!s)
2806 return NULL;
2807 pa = isl_stream_read_pw_aff(s);
2808 isl_stream_free(s);
2809 return pa;
2810 }
2811
2812 /* Read an isl_pw_multi_aff from "s".
2813 * We currently read a generic object and if it turns out to be a set or
2814 * a map, we convert that to an isl_pw_multi_aff.
2815 * It would be more efficient if we were to construct the isl_pw_multi_aff
2816 * directly.
2817 */
2818 __isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(struct isl_stream *s)
2819 {
2820 struct isl_obj obj;
2821
2822 obj = obj_read(s);
2823 if (!obj.v)
2824 return NULL;
2825
2826 if (obj.type == isl_obj_map)
2827 return isl_pw_multi_aff_from_map(obj.v);
2828 if (obj.type == isl_obj_set)
2829 return isl_pw_multi_aff_from_set(obj.v);
2830
2831 obj.type->free(obj.v);
2832 isl_die(s->ctx, isl_error_invalid, "unexpected object type",
2833 return NULL);
2834 }
2835
2836 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx,
2837 const char *str)
2838 {
2839 isl_pw_multi_aff *pma;
2840 struct isl_stream *s = isl_stream_new_str(ctx, str);
2841 if (!s)
2842 return NULL;
2843 pma = isl_stream_read_pw_multi_aff(s);
2844 isl_stream_free(s);
2845 return pma;
2846 }
2847
2848 /* Read an isl_union_pw_multi_aff from "s".
2849 * We currently read a generic object and if it turns out to be a set or
2850 * a map, we convert that to an isl_union_pw_multi_aff.
2851 * It would be more efficient if we were to construct
2852 * the isl_union_pw_multi_aff directly.
2853 */
2854 __isl_give isl_union_pw_multi_aff *isl_stream_read_union_pw_multi_aff(
2855 struct isl_stream *s)
2856 {
2857 struct isl_obj obj;
2858
2859 obj = obj_read(s);
2860 if (!obj.v)
2861 return NULL;
2862
2863 if (obj.type == isl_obj_map || obj.type == isl_obj_set)
2864 obj = to_union(s->ctx, obj);
2865 if (obj.type == isl_obj_union_map)
2866 return isl_union_pw_multi_aff_from_union_map(obj.v);
2867 if (obj.type == isl_obj_union_set)
2868 return isl_union_pw_multi_aff_from_union_set(obj.v);
2869
2870 obj.type->free(obj.v);
2871 isl_die(s->ctx, isl_error_invalid, "unexpected object type",
2872 return NULL);
2873 }
2874
2875 /* Read an isl_union_pw_multi_aff from "str".
2876 */
2877 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_read_from_str(
2878 isl_ctx *ctx, const char *str)
2879 {
2880 isl_union_pw_multi_aff *upma;
2881 struct isl_stream *s = isl_stream_new_str(ctx, str);
2882 if (!s)
2883 return NULL;
2884 upma = isl_stream_read_union_pw_multi_aff(s);
2885 isl_stream_free(s);
2886 return upma;
2887 }
2888
2889 /* Assuming "pa" represents a single affine expression defined on a universe
2890 * domain, extract this affine expression.
2891 */
2892 static __isl_give isl_aff *aff_from_pw_aff(__isl_take isl_pw_aff *pa)
2893 {
2894 isl_aff *aff;
2895
2896 if (!pa)
2897 return NULL;
2898 if (pa->n != 1)
2899 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
2900 "expecting single affine expression",
2901 goto error);
2902 if (!isl_set_plain_is_universe(pa->p[0].set))
2903 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
2904 "expecting universe domain",
2905 goto error);
2906
2907 aff = isl_aff_copy(pa->p[0].aff);
2908 isl_pw_aff_free(pa);
2909 return aff;
2910 error:
2911 isl_pw_aff_free(pa);
2912 return NULL;
2913 }
2914
2915 /* Read a multi-affine expression from "s".
2916 * If the multi-affine expression has a domain, then then tuple
2917 * representing this domain cannot involve any affine expressions.
2918 * The tuple representing the actual expressions needs to consist
2919 * of only affine expressions. Moreover, these expressions can
2920 * only depend on parameters and input dimensions and not on other
2921 * output dimensions.
2922 */
2923 __isl_give isl_multi_aff *isl_stream_read_multi_aff(struct isl_stream *s)
2924 {
2925 struct vars *v;
2926 isl_set *dom = NULL;
2927 isl_multi_pw_aff *tuple = NULL;
2928 int dim, i, n;
2929 isl_space *space, *dom_space;
2930 isl_multi_aff *ma = NULL;
2931
2932 v = vars_new(s->ctx);
2933 if (!v)
2934 return NULL;
2935
2936 dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2937 if (next_is_tuple(s)) {
2938 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
2939 if (isl_stream_eat(s, ISL_TOKEN_TO))
2940 goto error;
2941 }
2942 if (!isl_set_plain_is_universe(dom))
2943 isl_die(s->ctx, isl_error_invalid,
2944 "expecting universe parameter domain", goto error);
2945 if (isl_stream_eat(s, '{'))
2946 goto error;
2947
2948 tuple = read_tuple(s, v, 0, 0);
2949 if (!tuple)
2950 goto error;
2951 if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {
2952 isl_set *set;
2953 isl_space *space;
2954 int has_expr;
2955
2956 has_expr = tuple_has_expr(tuple);
2957 if (has_expr < 0)
2958 goto error;
2959 if (has_expr)
2960 isl_die(s->ctx, isl_error_invalid,
2961 "expecting universe domain", goto error);
2962 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
2963 set = isl_set_universe(space);
2964 dom = isl_set_intersect_params(set, dom);
2965 isl_multi_pw_aff_free(tuple);
2966 tuple = read_tuple(s, v, 0, 0);
2967 if (!tuple)
2968 goto error;
2969 }
2970
2971 if (isl_stream_eat(s, '}'))
2972 goto error;
2973
2974 n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
2975 dim = isl_set_dim(dom, isl_dim_all);
2976 dom_space = isl_set_get_space(dom);
2977 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
2978 space = isl_space_align_params(space, isl_space_copy(dom_space));
2979 if (!isl_space_is_params(dom_space))
2980 space = isl_space_map_from_domain_and_range(
2981 isl_space_copy(dom_space), space);
2982 isl_space_free(dom_space);
2983 ma = isl_multi_aff_alloc(space);
2984
2985 for (i = 0; i < n; ++i) {
2986 isl_pw_aff *pa;
2987 isl_aff *aff;
2988 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
2989 aff = aff_from_pw_aff(pa);
2990 if (!aff)
2991 goto error;
2992 if (isl_aff_involves_dims(aff, isl_dim_in, dim, i + 1)) {
2993 isl_aff_free(aff);
2994 isl_die(s->ctx, isl_error_invalid,
2995 "not an affine expression", goto error);
2996 }
2997 aff = isl_aff_drop_dims(aff, isl_dim_in, dim, n);
2998 space = isl_multi_aff_get_domain_space(ma);
2999 aff = isl_aff_reset_domain_space(aff, space);
3000 ma = isl_multi_aff_set_aff(ma, i, aff);
3001 }
3002
3003 isl_multi_pw_aff_free(tuple);
3004 vars_free(v);
3005 isl_set_free(dom);
3006 return ma;
3007 error:
3008 isl_multi_pw_aff_free(tuple);
3009 vars_free(v);
3010 isl_set_free(dom);
3011 isl_multi_aff_free(ma);
3012 return NULL;
3013 }
3014
3015 __isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx,
3016 const char *str)
3017 {
3018 isl_multi_aff *maff;
3019 struct isl_stream *s = isl_stream_new_str(ctx, str);
3020 if (!s)
3021 return NULL;
3022 maff = isl_stream_read_multi_aff(s);
3023 isl_stream_free(s);
3024 return maff;
3025 }
3026
3027 __isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial(
3028 struct isl_stream *s)
3029 {
3030 struct isl_obj obj;
3031
3032 obj = obj_read(s);
3033 if (obj.type == isl_obj_pw_qpolynomial) {
3034 obj.type = isl_obj_union_pw_qpolynomial;
3035 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
3036 }
3037 if (obj.v)
3038 isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial,
3039 goto error);
3040
3041 return obj.v;
3042 error:
3043 obj.type->free(obj.v);
3044 return NULL;
3045 }
3046
3047 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str(
3048 isl_ctx *ctx, const char *str)
3049 {
3050 isl_union_pw_qpolynomial *upwqp;
3051 struct isl_stream *s = isl_stream_new_str(ctx, str);
3052 if (!s)
3053 return NULL;
3054 upwqp = isl_stream_read_union_pw_qpolynomial(s);
3055 isl_stream_free(s);
3056 return upwqp;
3057 }
Integer set library