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

source code of polly/lib/External/isl/isl_input.c