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