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