?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
doc: fix typo
[isl.git] / isl_input.c
bloba1cf268b36a4ae223b72ba45f7044858d57311ec
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 *
5 * Use of this software is governed by the GNU LGPLv2.1 license
6 *
7 * Written by Sven Verdoolaege, K.U.Leuven, Departement
8 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
9 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
10 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
11 */
12
13 #include <ctype.h>
14 #include <stdio.h>
15 #include <string.h>
16 #include <isl_ctx_private.h>
17 #include <isl_map_private.h>
18 #include <isl/set.h>
19 #include <isl/seq.h>
20 #include <isl/div.h>
21 #include <isl/stream.h>
22 #include <isl/obj.h>
23 #include "isl_polynomial_private.h"
24 #include <isl/union_map.h>
25 #include <isl_mat_private.h>
26
27 struct variable {
28 char *name;
29 int pos;
30 isl_vec *def;
31 /* non-zero if variable represents a min (-1) or a max (1) */
32 int sign;
33 isl_mat *list;
34 struct variable *next;
35 };
36
37 struct vars {
38 struct isl_ctx *ctx;
39 int n;
40 struct variable *v;
41 };
42
43 static struct vars *vars_new(struct isl_ctx *ctx)
44 {
45 struct vars *v;
46 v = isl_alloc_type(ctx, struct vars);
47 if (!v)
48 return NULL;
49 v->ctx = ctx;
50 v->n = 0;
51 v->v = NULL;
52 return v;
53 }
54
55 static void variable_free(struct variable *var)
56 {
57 while (var) {
58 struct variable *next = var->next;
59 isl_mat_free(var->list);
60 isl_vec_free(var->def);
61 free(var->name);
62 free(var);
63 var = next;
64 }
65 }
66
67 static void vars_free(struct vars *v)
68 {
69 if (!v)
70 return;
71 variable_free(v->v);
72 free(v);
73 }
74
75 static void vars_drop(struct vars *v, int n)
76 {
77 struct variable *var;
78
79 if (!v || !v->v)
80 return;
81
82 v->n -= n;
83
84 var = v->v;
85 while (--n >= 0) {
86 struct variable *next = var->next;
87 isl_mat_free(var->list);
88 isl_vec_free(var->def);
89 free(var->name);
90 free(var);
91 var = next;
92 }
93 v->v = var;
94 }
95
96 static struct variable *variable_new(struct vars *v, const char *name, int len,
97 int pos)
98 {
99 struct variable *var;
100 var = isl_calloc_type(v->ctx, struct variable);
101 if (!var)
102 goto error;
103 var->name = strdup(name);
104 var->name[len] = '\0';
105 var->pos = pos;
106 var->def = NULL;
107 var->next = v->v;
108 return var;
109 error:
110 variable_free(v->v);
111 return NULL;
112 }
113
114 static 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);
121 for (q = v->v; q; q = q->next) {
122 if (strncmp(q->name, s, 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, s, len, v->n);
130 if (!v->v)
131 return -1;
132 v->n++;
133 }
134 return pos;
135 }
136
137 static int vars_add_anon(struct vars *v)
138 {
139 v->v = variable_new(v, "", 0, v->n);
140
141 if (!v->v)
142 return -1;
143 v->n++;
144
145 return 0;
146 }
147
148 static __isl_give isl_basic_map *set_name(__isl_take isl_basic_map *bmap,
149 enum isl_dim_type type, unsigned pos, char *name)
150 {
151 char *prime;
152
153 if (!bmap)
154 return NULL;
155 if (!name)
156 return bmap;
157
158 prime = strchr(name, '\'');
159 if (prime)
160 *prime = '\0';
161 bmap = isl_basic_map_set_dim_name(bmap, type, pos, name);
162 if (prime)
163 *prime = '\'';
164
165 return bmap;
166 }
167
168 /* Obtain next token, with some preprocessing.
169 * In particular, evaluate expressions of the form x^y,
170 * with x and y values.
171 */
172 static struct isl_token *next_token(struct isl_stream *s)
173 {
174 struct isl_token *tok, *tok2;
175
176 tok = isl_stream_next_token(s);
177 if (!tok || tok->type != ISL_TOKEN_VALUE)
178 return tok;
179 if (!isl_stream_eat_if_available(s, '^'))
180 return tok;
181 tok2 = isl_stream_next_token(s);
182 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
183 isl_stream_error(s, tok2, "expecting constant value");
184 goto error;
185 }
186
187 isl_int_pow_ui(tok->u.v, tok->u.v, isl_int_get_ui(tok2->u.v));
188
189 isl_token_free(tok2);
190 return tok;
191 error:
192 isl_token_free(tok);
193 isl_token_free(tok2);
194 return NULL;
195 }
196
197 static int accept_cst_factor(struct isl_stream *s, isl_int *f)
198 {
199 struct isl_token *tok;
200
201 tok = next_token(s);
202 if (!tok || tok->type != ISL_TOKEN_VALUE) {
203 isl_stream_error(s, tok, "expecting constant value");
204 goto error;
205 }
206
207 isl_int_mul(*f, *f, tok->u.v);
208
209 isl_token_free(tok);
210
211 if (isl_stream_eat_if_available(s, '*'))
212 return accept_cst_factor(s, f);
213
214 return 0;
215 error:
216 isl_token_free(tok);
217 return -1;
218 }
219
220 /* Given an affine expression aff, return an affine expression
221 * for aff % d, with d the next token on the stream, which is
222 * assumed to be a constant.
223 *
224 * We introduce an integer division q = [aff/d] and the result
225 * is set to aff - d q.
226 */
227 static __isl_give isl_vec *affine_mod(struct isl_stream *s,
228 struct vars *v, __isl_take isl_vec *aff)
229 {
230 struct isl_token *tok;
231 struct variable *var;
232 isl_vec *mod;
233
234 tok = next_token(s);
235 if (!tok || tok->type != ISL_TOKEN_VALUE) {
236 isl_stream_error(s, tok, "expecting constant value");
237 goto error;
238 }
239
240 if (vars_add_anon(v) < 0)
241 goto error;
242
243 var = v->v;
244
245 var->def = isl_vec_alloc(s->ctx, 2 + v->n);
246 if (!var->def)
247 goto error;
248 isl_seq_cpy(var->def->el + 1, aff->el, aff->size);
249 isl_int_set_si(var->def->el[1 + aff->size], 0);
250 isl_int_set(var->def->el[0], tok->u.v);
251
252 mod = isl_vec_alloc(v->ctx, 1 + v->n);
253 if (!mod)
254 goto error;
255
256 isl_seq_cpy(mod->el, aff->el, aff->size);
257 isl_int_neg(mod->el[aff->size], tok->u.v);
258
259 isl_vec_free(aff);
260 isl_token_free(tok);
261 return mod;
262 error:
263 isl_vec_free(aff);
264 isl_token_free(tok);
265 return NULL;
266 }
267
268 static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v);
269 static int read_div_definition(struct isl_stream *s, struct vars *v);
270 static int read_minmax_definition(struct isl_stream *s, struct vars *v);
271
272 static __isl_give isl_vec *accept_affine_factor(struct isl_stream *s,
273 struct vars *v)
274 {
275 struct isl_token *tok = NULL;
276 isl_vec *aff = NULL;
277
278 tok = next_token(s);
279 if (!tok) {
280 isl_stream_error(s, NULL, "unexpected EOF");
281 goto error;
282 }
283 if (tok->type == ISL_TOKEN_IDENT) {
284 int n = v->n;
285 int pos = vars_pos(v, tok->u.s, -1);
286 if (pos < 0)
287 goto error;
288 if (pos >= n) {
289 isl_stream_error(s, tok, "unknown identifier");
290 goto error;
291 }
292
293 aff = isl_vec_alloc(v->ctx, 1 + v->n);
294 if (!aff)
295 goto error;
296 isl_seq_clr(aff->el, aff->size);
297 isl_int_set_si(aff->el[1 + pos], 1);
298 isl_token_free(tok);
299 } else if (tok->type == ISL_TOKEN_VALUE) {
300 if (isl_stream_eat_if_available(s, '*')) {
301 aff = accept_affine_factor(s, v);
302 aff = isl_vec_scale(aff, tok->u.v);
303 } else {
304 aff = isl_vec_alloc(v->ctx, 1 + v->n);
305 if (!aff)
306 goto error;
307 isl_seq_clr(aff->el, aff->size);
308 isl_int_set(aff->el[0], tok->u.v);
309 }
310 isl_token_free(tok);
311 } else if (tok->type == '(') {
312 isl_token_free(tok);
313 tok = NULL;
314 aff = accept_affine(s, v);
315 if (!aff)
316 goto error;
317 if (isl_stream_eat(s, ')'))
318 goto error;
319 } else if (tok->type == '[' ||
320 tok->type == ISL_TOKEN_FLOORD ||
321 tok->type == ISL_TOKEN_CEILD) {
322 int ceil = tok->type == ISL_TOKEN_CEILD;
323 struct variable *var;
324 if (vars_add_anon(v) < 0)
325 goto error;
326 var = v->v;
327 aff = isl_vec_alloc(v->ctx, 1 + v->n);
328 if (!aff)
329 goto error;
330 isl_seq_clr(aff->el, aff->size);
331 isl_int_set_si(aff->el[1 + v->n - 1], ceil ? -1 : 1);
332 isl_stream_push_token(s, tok);
333 tok = NULL;
334 if (read_div_definition(s, v) < 0)
335 goto error;
336 if (ceil)
337 isl_seq_neg(var->def->el + 1, var->def->el + 1,
338 var->def->size - 1);
339 aff = isl_vec_zero_extend(aff, 1 + v->n);
340 } else if (tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX) {
341 if (vars_add_anon(v) < 0)
342 goto error;
343 aff = isl_vec_alloc(v->ctx, 1 + v->n);
344 if (!aff)
345 goto error;
346 isl_seq_clr(aff->el, aff->size);
347 isl_int_set_si(aff->el[1 + v->n - 1], 1);
348 isl_stream_push_token(s, tok);
349 tok = NULL;
350 if (read_minmax_definition(s, v) < 0)
351 goto error;
352 aff = isl_vec_zero_extend(aff, 1 + v->n);
353 } else {
354 isl_stream_error(s, tok, "expecting factor");
355 goto error;
356 }
357 if (isl_stream_eat_if_available(s, '%'))
358 return affine_mod(s, v, aff);
359 if (isl_stream_eat_if_available(s, '*')) {
360 isl_int f;
361 isl_int_init(f);
362 isl_int_set_si(f, 1);
363 if (accept_cst_factor(s, &f) < 0) {
364 isl_int_clear(f);
365 goto error2;
366 }
367 aff = isl_vec_scale(aff, f);
368 isl_int_clear(f);
369 }
370
371 return aff;
372 error:
373 isl_token_free(tok);
374 error2:
375 isl_vec_free(aff);
376 return NULL;
377 }
378
379 static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v)
380 {
381 struct isl_token *tok = NULL;
382 struct isl_vec *aff;
383 int sign = 1;
384
385 aff = isl_vec_alloc(v->ctx, 1 + v->n);
386 if (!aff)
387 return NULL;
388 isl_seq_clr(aff->el, aff->size);
389
390 for (;;) {
391 tok = next_token(s);
392 if (!tok) {
393 isl_stream_error(s, NULL, "unexpected EOF");
394 goto error;
395 }
396 if (tok->type == '-') {
397 sign = -sign;
398 isl_token_free(tok);
399 continue;
400 }
401 if (tok->type == '(' || tok->type == '[' ||
402 tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX ||
403 tok->type == ISL_TOKEN_FLOORD ||
404 tok->type == ISL_TOKEN_CEILD ||
405 tok->type == ISL_TOKEN_IDENT) {
406 isl_vec *aff2;
407 isl_stream_push_token(s, tok);
408 tok = NULL;
409 aff2 = accept_affine_factor(s, v);
410 if (sign < 0)
411 aff2 = isl_vec_scale(aff2, s->ctx->negone);
412 aff = isl_vec_zero_extend(aff, 1 + v->n);
413 aff = isl_vec_add(aff, aff2);
414 if (!aff)
415 goto error;
416 sign = 1;
417 } else if (tok->type == ISL_TOKEN_VALUE) {
418 if (sign < 0)
419 isl_int_neg(tok->u.v, tok->u.v);
420 if (isl_stream_eat_if_available(s, '*') ||
421 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
422 isl_vec *aff2;
423 aff2 = accept_affine_factor(s, v);
424 aff2 = isl_vec_scale(aff2, tok->u.v);
425 aff = isl_vec_zero_extend(aff, 1 + v->n);
426 aff = isl_vec_add(aff, aff2);
427 if (!aff)
428 goto error;
429 } else {
430 isl_int_add(aff->el[0], aff->el[0], tok->u.v);
431 }
432 sign = 1;
433 } else {
434 isl_stream_error(s, tok, "unexpected isl_token");
435 isl_stream_push_token(s, tok);
436 isl_vec_free(aff);
437 return NULL;
438 }
439 isl_token_free(tok);
440
441 tok = next_token(s);
442 if (tok && tok->type == '-') {
443 sign = -sign;
444 isl_token_free(tok);
445 } else if (tok && tok->type == '+') {
446 /* nothing */
447 isl_token_free(tok);
448 } else if (tok && tok->type == ISL_TOKEN_VALUE &&
449 isl_int_is_neg(tok->u.v)) {
450 isl_stream_push_token(s, tok);
451 } else {
452 if (tok)
453 isl_stream_push_token(s, tok);
454 break;
455 }
456 }
457
458 return aff;
459 error:
460 isl_token_free(tok);
461 isl_vec_free(aff);
462 return NULL;
463 }
464
465 /* Add any variables in the variable list "v" that are not already in "bmap"
466 * as existentially quantified variables in "bmap".
467 */
468 static __isl_give isl_basic_map *add_divs(__isl_take isl_basic_map *bmap,
469 struct vars *v)
470 {
471 int i;
472 int extra;
473 struct variable *var;
474
475 extra = v->n - isl_basic_map_total_dim(bmap);
476
477 if (extra == 0)
478 return bmap;
479
480 bmap = isl_basic_map_extend_dim(bmap, isl_basic_map_get_dim(bmap),
481 extra, 0, 2 * extra);
482
483 for (i = 0; i < extra; ++i)
484 if (isl_basic_map_alloc_div(bmap) < 0)
485 goto error;
486
487 for (i = 0, var = v->v; i < extra; ++i, var = var->next) {
488 int k = bmap->n_div - 1 - i;
489
490 isl_seq_cpy(bmap->div[k], var->def->el, var->def->size);
491 isl_seq_clr(bmap->div[k] + var->def->size,
492 2 + v->n - var->def->size);
493
494 if (isl_basic_map_add_div_constraints(bmap, k) < 0)
495 goto error;
496 }
497
498 return bmap;
499 error:
500 isl_basic_map_free(bmap);
501 return NULL;
502 }
503
504 static __isl_give isl_basic_map *read_var_def(struct isl_stream *s,
505 __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
506 {
507 isl_dim *dim;
508 isl_basic_map *def = NULL;
509 struct isl_vec *vec;
510 int k;
511 int n;
512
513 if (vars_add_anon(v) < 0)
514 goto error;
515 n = v->n;
516
517 vec = accept_affine(s, v);
518 if (!vec)
519 goto error;
520
521 dim = isl_basic_map_get_dim(bmap);
522 def = isl_basic_map_universe(dim);
523 def = add_divs(def, v);
524 def = isl_basic_map_extend_constraints(def, 1, 0);
525 k = isl_basic_map_alloc_equality(def);
526 if (k >= 0) {
527 isl_seq_cpy(def->eq[k], vec->el, vec->size);
528 isl_int_set_si(def->eq[k][1 + n - 1], -1);
529 }
530 isl_vec_free(vec);
531 if (k < 0)
532 goto error;
533
534 vars_drop(v, v->n - n);
535
536 def = isl_basic_map_simplify(def);
537 def = isl_basic_map_finalize(def);
538 bmap = isl_basic_map_intersect(bmap, def);
539 return bmap;
540 error:
541 isl_basic_map_free(bmap);
542 isl_basic_map_free(def);
543 return NULL;
544 }
545
546 static __isl_give isl_basic_map *read_var_list(struct isl_stream *s,
547 __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
548 {
549 int i = 0;
550 struct isl_token *tok;
551
552 while ((tok = next_token(s)) != NULL) {
553 int new_name = 0;
554
555 if (tok->type == ISL_TOKEN_IDENT) {
556 int n = v->n;
557 int p = vars_pos(v, tok->u.s, -1);
558 if (p < 0)
559 goto error;
560 new_name = p >= n;
561 }
562
563 if (new_name) {
564 bmap = isl_basic_map_add(bmap, type, 1);
565 bmap = set_name(bmap, type, i, v->v->name);
566 isl_token_free(tok);
567 } else if (tok->type == ISL_TOKEN_IDENT ||
568 tok->type == ISL_TOKEN_VALUE ||
569 tok->type == '-' ||
570 tok->type == '(') {
571 if (type == isl_dim_param) {
572 isl_stream_error(s, tok,
573 "expecting unique identifier");
574 goto error;
575 }
576 isl_stream_push_token(s, tok);
577 tok = NULL;
578 bmap = isl_basic_map_add(bmap, type, 1);
579 bmap = read_var_def(s, bmap, type, v);
580 } else
581 break;
582
583 tok = isl_stream_next_token(s);
584 if (tok && tok->type == ']' &&
585 isl_stream_next_token_is(s, '[')) {
586 isl_token_free(tok);
587 tok = isl_stream_next_token(s);
588 } else if (!tok || tok->type != ',')
589 break;
590
591 isl_token_free(tok);
592 i++;
593 }
594 if (tok)
595 isl_stream_push_token(s, tok);
596
597 return bmap;
598 error:
599 isl_token_free(tok);
600 isl_basic_map_free(bmap);
601 return NULL;
602 }
603
604 static __isl_give isl_mat *accept_affine_list(struct isl_stream *s,
605 struct vars *v)
606 {
607 struct isl_vec *vec;
608 struct isl_mat *mat;
609 struct isl_token *tok = NULL;
610
611 vec = accept_affine(s, v);
612 mat = isl_mat_from_row_vec(vec);
613 if (!mat)
614 return NULL;
615
616 for (;;) {
617 tok = isl_stream_next_token(s);
618 if (!tok) {
619 isl_stream_error(s, NULL, "unexpected EOF");
620 goto error;
621 }
622 if (tok->type != ',') {
623 isl_stream_push_token(s, tok);
624 break;
625 }
626 isl_token_free(tok);
627
628 vec = accept_affine(s, v);
629 mat = isl_mat_add_zero_cols(mat, 1 + v->n - isl_mat_cols(mat));
630 mat = isl_mat_vec_concat(mat, vec);
631 if (!mat)
632 return NULL;
633 }
634
635 return mat;
636 error:
637 isl_mat_free(mat);
638 return NULL;
639 }
640
641 static int read_minmax_definition(struct isl_stream *s, struct vars *v)
642 {
643 struct isl_token *tok;
644 struct variable *var;
645
646 var = v->v;
647
648 tok = isl_stream_next_token(s);
649 if (!tok)
650 return -1;
651 var->sign = tok->type == ISL_TOKEN_MIN ? -1 : 1;
652 isl_token_free(tok);
653
654 if (isl_stream_eat(s, '('))
655 return -1;
656
657 var->list = accept_affine_list(s, v);
658 if (!var->list)
659 return -1;
660
661 if (isl_stream_eat(s, ')'))
662 return -1;
663
664 return 0;
665 }
666
667 static int read_div_definition(struct isl_stream *s, struct vars *v)
668 {
669 struct isl_token *tok;
670 int seen_paren = 0;
671 struct isl_vec *aff;
672 struct variable *var;
673 int fc = 0;
674
675 if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOORD) ||
676 isl_stream_eat_if_available(s, ISL_TOKEN_CEILD)) {
677 fc = 1;
678 if (isl_stream_eat(s, '('))
679 return -1;
680 } else {
681 if (isl_stream_eat(s, '['))
682 return -1;
683 if (isl_stream_eat_if_available(s, '('))
684 seen_paren = 1;
685 }
686
687 var = v->v;
688
689 aff = accept_affine(s, v);
690 if (!aff)
691 return -1;
692
693 var->def = isl_vec_alloc(s->ctx, 2 + v->n);
694 if (!var->def) {
695 isl_vec_free(aff);
696 return -1;
697 }
698
699 isl_seq_cpy(var->def->el + 1, aff->el, aff->size);
700
701 isl_vec_free(aff);
702
703 if (fc) {
704 if (isl_stream_eat(s, ','))
705 return -1;
706 } else {
707 if (seen_paren && isl_stream_eat(s, ')'))
708 return -1;
709 if (isl_stream_eat(s, '/'))
710 return -1;
711 }
712
713 tok = next_token(s);
714 if (!tok)
715 return -1;
716 if (tok->type != ISL_TOKEN_VALUE) {
717 isl_stream_error(s, tok, "expected denominator");
718 isl_stream_push_token(s, tok);
719 return -1;
720 }
721 isl_int_set(var->def->el[0], tok->u.v);
722 isl_token_free(tok);
723
724 if (fc) {
725 if (isl_stream_eat(s, ')'))
726 return -1;
727 } else {
728 if (isl_stream_eat(s, ']'))
729 return -1;
730 }
731
732 return 0;
733 }
734
735 static struct isl_basic_map *add_div_definition(struct isl_stream *s,
736 struct vars *v, struct isl_basic_map *bmap, int pos)
737 {
738 struct variable *var = v->v;
739 unsigned o_out = isl_basic_map_offset(bmap, isl_dim_out) - 1;
740
741 if (read_div_definition(s, v) < 0)
742 goto error;
743
744 if (isl_basic_map_add_div_constraints_var(bmap, o_out + pos,
745 var->def->el) < 0)
746 goto error;
747
748 return bmap;
749 error:
750 isl_basic_map_free(bmap);
751 return NULL;
752 }
753
754 static struct isl_basic_map *read_defined_var_list(struct isl_stream *s,
755 struct vars *v, struct isl_basic_map *bmap)
756 {
757 struct isl_token *tok;
758
759 while ((tok = isl_stream_next_token(s)) != NULL) {
760 int p;
761 int n = v->n;
762 unsigned n_out = isl_basic_map_dim(bmap, isl_dim_out);
763
764 if (tok->type != ISL_TOKEN_IDENT)
765 break;
766
767 p = vars_pos(v, tok->u.s, -1);
768 if (p < 0)
769 goto error;
770 if (p < n) {
771 isl_stream_error(s, tok, "expecting unique identifier");
772 goto error;
773 }
774
775 bmap = isl_basic_map_cow(bmap);
776 bmap = isl_basic_map_add(bmap, isl_dim_out, 1);
777 bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
778 0, 0, 2);
779
780 isl_token_free(tok);
781 tok = isl_stream_next_token(s);
782 if (tok && tok->type == '=') {
783 isl_token_free(tok);
784 bmap = add_div_definition(s, v, bmap, n_out);
785 tok = isl_stream_next_token(s);
786 }
787
788 if (!tok || tok->type != ',')
789 break;
790
791 isl_token_free(tok);
792 }
793 if (tok)
794 isl_stream_push_token(s, tok);
795
796 return bmap;
797 error:
798 isl_token_free(tok);
799 isl_basic_map_free(bmap);
800 return NULL;
801 }
802
803 static int next_is_tuple(struct isl_stream *s)
804 {
805 struct isl_token *tok;
806 int is_tuple;
807
808 tok = isl_stream_next_token(s);
809 if (!tok)
810 return 0;
811 if (tok->type == '[') {
812 isl_stream_push_token(s, tok);
813 return 1;
814 }
815 if (tok->type != ISL_TOKEN_IDENT && !tok->is_keyword) {
816 isl_stream_push_token(s, tok);
817 return 0;
818 }
819
820 is_tuple = isl_stream_next_token_is(s, '[');
821
822 isl_stream_push_token(s, tok);
823
824 return is_tuple;
825 }
826
827 static __isl_give isl_basic_map *read_tuple(struct isl_stream *s,
828 __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v);
829
830 static __isl_give isl_basic_map *read_nested_tuple(struct isl_stream *s,
831 __isl_take isl_basic_map *bmap, struct vars *v)
832 {
833 bmap = read_tuple(s, bmap, isl_dim_in, v);
834 if (isl_stream_eat(s, ISL_TOKEN_TO))
835 goto error;
836 bmap = read_tuple(s, bmap, isl_dim_out, v);
837 bmap = isl_basic_map_from_range(isl_basic_map_wrap(bmap));
838 return bmap;
839 error:
840 isl_basic_map_free(bmap);
841 return NULL;
842 }
843
844 static __isl_give isl_basic_map *read_tuple(struct isl_stream *s,
845 __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
846 {
847 struct isl_token *tok;
848 char *name = NULL;
849
850 tok = isl_stream_next_token(s);
851 if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
852 name = strdup(tok->u.s);
853 if (!name)
854 goto error;
855 isl_token_free(tok);
856 tok = isl_stream_next_token(s);
857 }
858 if (!tok || tok->type != '[') {
859 isl_stream_error(s, tok, "expecting '['");
860 goto error;
861 }
862 isl_token_free(tok);
863 if (type != isl_dim_param && next_is_tuple(s)) {
864 isl_dim *dim = isl_basic_map_get_dim(bmap);
865 int nparam = isl_dim_size(dim, isl_dim_param);
866 int n_in = isl_dim_size(dim, isl_dim_in);
867 isl_basic_map *nested;
868 if (type == isl_dim_out)
869 dim = isl_dim_move(dim, isl_dim_param, nparam,
870 isl_dim_in, 0, n_in);
871 nested = isl_basic_map_alloc_dim(dim, 0, 0, 0);
872 nested = read_nested_tuple(s, nested, v);
873 if (type == isl_dim_in) {
874 nested = isl_basic_map_reverse(nested);
875 bmap = isl_basic_map_intersect(nested, bmap);
876 } else {
877 isl_basic_set *bset;
878 dim = isl_dim_range(isl_basic_map_get_dim(nested));
879 dim = isl_dim_drop(dim, isl_dim_param, nparam, n_in);
880 dim = isl_dim_join(isl_basic_map_get_dim(bmap), dim);
881 bset = isl_basic_map_domain(bmap);
882 nested = isl_basic_map_reset_dim(nested, dim);
883 bmap = isl_basic_map_intersect_domain(nested, bset);
884 }
885 } else
886 bmap = read_var_list(s, bmap, type, v);
887 tok = isl_stream_next_token(s);
888 if (!tok || tok->type != ']') {
889 isl_stream_error(s, tok, "expecting ']'");
890 goto error;
891 }
892 isl_token_free(tok);
893
894 if (name) {
895 bmap = isl_basic_map_set_tuple_name(bmap, type, name);
896 free(name);
897 }
898
899 return bmap;
900 error:
901 if (tok)
902 isl_token_free(tok);
903 isl_basic_map_free(bmap);
904 return NULL;
905 }
906
907 static __isl_give isl_basic_map *construct_constraint(
908 __isl_take isl_basic_map *bmap, enum isl_token_type type,
909 isl_int *left, isl_int *right)
910 {
911 int k;
912 unsigned len;
913 struct isl_ctx *ctx;
914
915 if (!bmap)
916 return NULL;
917 len = 1 + isl_basic_map_total_dim(bmap);
918 ctx = bmap->ctx;
919
920 k = isl_basic_map_alloc_inequality(bmap);
921 if (k < 0)
922 goto error;
923 if (type == ISL_TOKEN_LE)
924 isl_seq_combine(bmap->ineq[k], ctx->negone, left,
925 ctx->one, right,
926 len);
927 else if (type == ISL_TOKEN_GE)
928 isl_seq_combine(bmap->ineq[k], ctx->one, left,
929 ctx->negone, right,
930 len);
931 else if (type == ISL_TOKEN_LT) {
932 isl_seq_combine(bmap->ineq[k], ctx->negone, left,
933 ctx->one, right,
934 len);
935 isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1);
936 } else if (type == ISL_TOKEN_GT) {
937 isl_seq_combine(bmap->ineq[k], ctx->one, left,
938 ctx->negone, right,
939 len);
940 isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1);
941 } else {
942 isl_seq_combine(bmap->ineq[k], ctx->one, left,
943 ctx->negone, right,
944 len);
945 isl_basic_map_inequality_to_equality(bmap, k);
946 }
947
948 return bmap;
949 error:
950 isl_basic_map_free(bmap);
951 return NULL;
952 }
953
954 static int is_comparator(struct isl_token *tok)
955 {
956 if (!tok)
957 return 0;
958
959 switch (tok->type) {
960 case ISL_TOKEN_LT:
961 case ISL_TOKEN_GT:
962 case ISL_TOKEN_LE:
963 case ISL_TOKEN_GE:
964 case '=':
965 return 1;
966 default:
967 return 0;
968 }
969 }
970
971 /* Add any variables in the variable list "v" that are not already in "bmap"
972 * as output variables in "bmap".
973 */
974 static __isl_give isl_basic_map *add_lifted_divs(__isl_take isl_basic_map *bmap,
975 struct vars *v)
976 {
977 int i;
978 int extra;
979 struct variable *var;
980
981 extra = v->n - isl_basic_map_total_dim(bmap);
982
983 if (extra == 0)
984 return bmap;
985
986 bmap = isl_basic_map_add(bmap, isl_dim_out, extra);
987 bmap = isl_basic_map_extend_dim(bmap, isl_basic_map_get_dim(bmap),
988 0, 0, 2 * extra);
989
990 for (i = 0, var = v->v; i < extra; ++i, var = var->next) {
991 if (!var->def)
992 continue;
993 var->def = isl_vec_zero_extend(var->def, 2 + v->n);
994 if (!var->def)
995 goto error;
996 if (isl_basic_map_add_div_constraints_var(bmap, var->pos,
997 var->def->el) < 0)
998 goto error;
999 }
1000
1001 return bmap;
1002 error:
1003 isl_basic_map_free(bmap);
1004 return NULL;
1005 }
1006
1007 static struct isl_basic_map *add_constraint(struct isl_stream *s,
1008 struct vars *v, struct isl_basic_map *bmap)
1009 {
1010 int i, j;
1011 struct isl_token *tok = NULL;
1012 struct isl_mat *aff1 = NULL, *aff2 = NULL;
1013
1014 bmap = isl_basic_map_cow(bmap);
1015
1016 aff1 = accept_affine_list(s, v);
1017 if (!aff1)
1018 goto error;
1019 tok = isl_stream_next_token(s);
1020 if (!is_comparator(tok)) {
1021 isl_stream_error(s, tok, "missing operator");
1022 if (tok)
1023 isl_stream_push_token(s, tok);
1024 tok = NULL;
1025 goto error;
1026 }
1027 for (;;) {
1028 aff2 = accept_affine_list(s, v);
1029 if (!aff2)
1030 goto error;
1031
1032 aff1 = isl_mat_add_zero_cols(aff1, aff2->n_col - aff1->n_col);
1033 if (!aff1)
1034 goto error;
1035 bmap = add_lifted_divs(bmap, v);
1036 bmap = isl_basic_map_extend_constraints(bmap, 0,
1037 aff1->n_row * aff2->n_row);
1038 for (i = 0; i < aff1->n_row; ++i)
1039 for (j = 0; j < aff2->n_row; ++j)
1040 bmap = construct_constraint(bmap, tok->type,
1041 aff1->row[i], aff2->row[j]);
1042 isl_token_free(tok);
1043 isl_mat_free(aff1);
1044 aff1 = aff2;
1045
1046 tok = isl_stream_next_token(s);
1047 if (!is_comparator(tok)) {
1048 if (tok)
1049 isl_stream_push_token(s, tok);
1050 break;
1051 }
1052 }
1053 isl_mat_free(aff1);
1054
1055 return bmap;
1056 error:
1057 if (tok)
1058 isl_token_free(tok);
1059 isl_mat_free(aff1);
1060 isl_mat_free(aff2);
1061 isl_basic_map_free(bmap);
1062 return NULL;
1063 }
1064
1065 /* Return first variable, starting at n, representing a min or max,
1066 * or NULL if there is no such variable.
1067 */
1068 static struct variable *first_minmax(struct vars *v, int n)
1069 {
1070 struct variable *first = NULL;
1071 struct variable *var;
1072
1073 for (var = v->v; var && var->pos >= n; var = var->next)
1074 if (var->list)
1075 first = var;
1076
1077 return first;
1078 }
1079
1080 /* Check whether the variable at the given position only occurs in
1081 * inequalities and only with the given sign.
1082 */
1083 static int all_coefficients_of_sign(__isl_keep isl_map *map, int pos, int sign)
1084 {
1085 int i, j;
1086
1087 if (!map)
1088 return -1;
1089
1090 for (i = 0; i < map->n; ++i) {
1091 isl_basic_map *bmap = map->p[i];
1092
1093 for (j = 0; j < bmap->n_eq; ++j)
1094 if (!isl_int_is_zero(bmap->eq[j][1 + pos]))
1095 return 0;
1096 for (j = 0; j < bmap->n_ineq; ++j) {
1097 int s = isl_int_sgn(bmap->ineq[j][1 + pos]);
1098 if (s == 0)
1099 continue;
1100 if (s != sign)
1101 return 0;
1102 }
1103 }
1104
1105 return 1;
1106 }
1107
1108 /* Given a variable m which represents a min or a max of n expressions
1109 * b_i, add the constraints
1110 *
1111 * m <= b_i
1112 *
1113 * in case of a min (var->sign < 0) and m >= b_i in case of a max.
1114 */
1115 static __isl_give isl_map *bound_minmax(__isl_take isl_map *map,
1116 struct variable *var)
1117 {
1118 int i, k;
1119 isl_basic_map *bound;
1120 int total;
1121
1122 total = isl_map_dim(map, isl_dim_all);
1123 bound = isl_basic_map_alloc_dim(isl_map_get_dim(map),
1124 0, 0, var->list->n_row);
1125
1126 for (i = 0; i < var->list->n_row; ++i) {
1127 k = isl_basic_map_alloc_inequality(bound);
1128 if (k < 0)
1129 goto error;
1130 if (var->sign < 0)
1131 isl_seq_cpy(bound->ineq[k], var->list->row[i],
1132 var->list->n_col);
1133 else
1134 isl_seq_neg(bound->ineq[k], var->list->row[i],
1135 var->list->n_col);
1136 isl_int_set_si(bound->ineq[k][1 + var->pos], var->sign);
1137 isl_seq_clr(bound->ineq[k] + var->list->n_col,
1138 1 + total - var->list->n_col);
1139 }
1140
1141 map = isl_map_intersect(map, isl_map_from_basic_map(bound));
1142
1143 return map;
1144 error:
1145 isl_basic_map_free(bound);
1146 isl_map_free(map);
1147 return NULL;
1148 }
1149
1150 /* Given a variable m which represents a min (or max) of n expressions
1151 * b_i, add constraints that assigns the minimal upper bound to m, i.e.,
1152 * divide the space into cells where one
1153 * of the upper bounds is smaller than all the others and assign
1154 * this upper bound to m.
1155 *
1156 * In particular, if there are n bounds b_i, then the input map
1157 * is split into n pieces, each with the extra constraints
1158 *
1159 * m = b_i
1160 * b_i <= b_j for j > i
1161 * b_i < b_j for j < i
1162 *
1163 * in case of a min (var->sign < 0) and similarly in case of a max.
1164 *
1165 * Note: this function is very similar to set_minimum in isl_tab_pip.c
1166 * Perhaps we should try to merge the two.
1167 */
1168 static __isl_give isl_map *set_minmax(__isl_take isl_map *map,
1169 struct variable *var)
1170 {
1171 int i, j, k;
1172 isl_basic_map *bmap = NULL;
1173 isl_ctx *ctx;
1174 isl_map *split = NULL;
1175 int total;
1176
1177 ctx = isl_map_get_ctx(map);
1178 total = isl_map_dim(map, isl_dim_all);
1179 split = isl_map_alloc_dim(isl_map_get_dim(map),
1180 var->list->n_row, ISL_SET_DISJOINT);
1181
1182 for (i = 0; i < var->list->n_row; ++i) {
1183 bmap = isl_basic_map_alloc_dim(isl_map_get_dim(map), 0,
1184 1, var->list->n_row - 1);
1185 k = isl_basic_map_alloc_equality(bmap);
1186 if (k < 0)
1187 goto error;
1188 isl_seq_cpy(bmap->eq[k], var->list->row[i], var->list->n_col);
1189 isl_int_set_si(bmap->eq[k][1 + var->pos], -1);
1190 for (j = 0; j < var->list->n_row; ++j) {
1191 if (j == i)
1192 continue;
1193 k = isl_basic_map_alloc_inequality(bmap);
1194 if (k < 0)
1195 goto error;
1196 if (var->sign < 0)
1197 isl_seq_combine(bmap->ineq[k],
1198 ctx->one, var->list->row[j],
1199 ctx->negone, var->list->row[i],
1200 var->list->n_col);
1201 else
1202 isl_seq_combine(bmap->ineq[k],
1203 ctx->negone, var->list->row[j],
1204 ctx->one, var->list->row[i],
1205 var->list->n_col);
1206 isl_seq_clr(bmap->ineq[k] + var->list->n_col,
1207 1 + total - var->list->n_col);
1208 if (j < i)
1209 isl_int_sub_ui(bmap->ineq[k][0],
1210 bmap->ineq[k][0], 1);
1211 }
1212 bmap = isl_basic_map_finalize(bmap);
1213 split = isl_map_add_basic_map(split, bmap);
1214 }
1215
1216 map = isl_map_intersect(map, split);
1217
1218 return map;
1219 error:
1220 isl_basic_map_free(bmap);
1221 isl_map_free(split);
1222 isl_map_free(map);
1223 return NULL;
1224 }
1225
1226 /* Plug in the definitions of all min and max expressions.
1227 * If a min expression only appears in inequalities and only
1228 * with a positive coefficient, then we can simply bound
1229 * the variable representing the min by its defining terms
1230 * and similarly for a max expression.
1231 * Otherwise, we have to assign the different terms to the
1232 * variable under the condition that the assigned term is smaller
1233 * than the other terms.
1234 */
1235 static __isl_give isl_map *add_minmax(__isl_take isl_map *map,
1236 struct vars *v, int n)
1237 {
1238 struct variable *var;
1239
1240 while (n < v->n) {
1241 var = first_minmax(v, n);
1242 if (!var)
1243 break;
1244 if (all_coefficients_of_sign(map, var->pos, -var->sign))
1245 map = bound_minmax(map, var);
1246 else
1247 map = set_minmax(map, var);
1248 n = var->pos + 1;
1249 }
1250
1251 return map;
1252 }
1253
1254 static isl_map *read_constraint(struct isl_stream *s,
1255 struct vars *v, __isl_take isl_basic_map *bmap)
1256 {
1257 int n = v->n;
1258 isl_map *map;
1259 unsigned total;
1260
1261 if (!bmap)
1262 return NULL;
1263
1264 bmap = isl_basic_set_unwrap(isl_basic_set_lift(isl_basic_map_wrap(bmap)));
1265 total = isl_basic_map_total_dim(bmap);
1266 while (v->n < total)
1267 if (vars_add_anon(v) < 0)
1268 goto error;
1269
1270 bmap = add_constraint(s, v, bmap);
1271 bmap = isl_basic_map_simplify(bmap);
1272 bmap = isl_basic_map_finalize(bmap);
1273
1274 map = isl_map_from_basic_map(bmap);
1275
1276 map = add_minmax(map, v, n);
1277
1278 map = isl_set_unwrap(isl_map_domain(map));
1279
1280 vars_drop(v, v->n - n);
1281
1282 return map;
1283 error:
1284 isl_basic_map_free(bmap);
1285 return NULL;
1286 }
1287
1288 static struct isl_map *read_disjuncts(struct isl_stream *s,
1289 struct vars *v, __isl_take isl_basic_map *bmap);
1290
1291 static __isl_give isl_map *read_exists(struct isl_stream *s,
1292 struct vars *v, __isl_take isl_basic_map *bmap)
1293 {
1294 int n = v->n;
1295 int seen_paren = isl_stream_eat_if_available(s, '(');
1296 isl_map *map = NULL;
1297
1298 bmap = isl_basic_map_from_domain(isl_basic_map_wrap(bmap));
1299 bmap = read_defined_var_list(s, v, bmap);
1300
1301 if (isl_stream_eat(s, ':'))
1302 goto error;
1303
1304 map = read_disjuncts(s, v, bmap);
1305 map = isl_set_unwrap(isl_map_domain(map));
1306 bmap = NULL;
1307
1308 vars_drop(v, v->n - n);
1309 if (seen_paren && isl_stream_eat(s, ')'))
1310 goto error;
1311
1312 return map;
1313 error:
1314 isl_basic_map_free(bmap);
1315 isl_map_free(map);
1316 return NULL;
1317 }
1318
1319 static __isl_give isl_map *read_conjunct(struct isl_stream *s,
1320 struct vars *v, __isl_take isl_basic_map *bmap)
1321 {
1322 isl_map *map;
1323
1324 if (isl_stream_eat_if_available(s, '(')) {
1325 map = read_disjuncts(s, v, bmap);
1326 if (isl_stream_eat(s, ')'))
1327 goto error;
1328 return map;
1329 }
1330
1331 if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))
1332 return read_exists(s, v, bmap);
1333
1334 if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))
1335 return isl_map_from_basic_map(bmap);
1336
1337 if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) {
1338 isl_dim *dim = isl_basic_map_get_dim(bmap);
1339 isl_basic_map_free(bmap);
1340 return isl_map_empty(dim);
1341 }
1342
1343 return read_constraint(s, v, bmap);
1344 error:
1345 isl_map_free(map);
1346 return NULL;
1347 }
1348
1349 static __isl_give isl_map *read_conjuncts(struct isl_stream *s,
1350 struct vars *v, __isl_take isl_basic_map *bmap)
1351 {
1352 isl_map *map;
1353 int negate;
1354
1355 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1356 map = read_conjunct(s, v, isl_basic_map_copy(bmap));
1357 if (negate) {
1358 isl_map *t;
1359 t = isl_map_from_basic_map(isl_basic_map_copy(bmap));
1360 map = isl_map_subtract(t, map);
1361 }
1362
1363 while (isl_stream_eat_if_available(s, ISL_TOKEN_AND)) {
1364 isl_map *map_i;
1365
1366 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1367 map_i = read_conjunct(s, v, isl_basic_map_copy(bmap));
1368 if (negate)
1369 map = isl_map_subtract(map, map_i);
1370 else
1371 map = isl_map_intersect(map, map_i);
1372 }
1373
1374 isl_basic_map_free(bmap);
1375 return map;
1376 }
1377
1378 static struct isl_map *read_disjuncts(struct isl_stream *s,
1379 struct vars *v, __isl_take isl_basic_map *bmap)
1380 {
1381 struct isl_map *map;
1382
1383 if (isl_stream_next_token_is(s, '}')) {
1384 isl_dim *dim = isl_basic_map_get_dim(bmap);
1385 isl_basic_map_free(bmap);
1386 return isl_map_universe(dim);
1387 }
1388
1389 map = read_conjuncts(s, v, isl_basic_map_copy(bmap));
1390 while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
1391 isl_map *map_i;
1392
1393 map_i = read_conjuncts(s, v, isl_basic_map_copy(bmap));
1394 map = isl_map_union(map, map_i);
1395 }
1396
1397 isl_basic_map_free(bmap);
1398 return map;
1399 }
1400
1401 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1402 {
1403 if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1404 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1405 isl_basic_map_dim(bmap, isl_dim_in) + pos;
1406 pos -= isl_basic_map_dim(bmap, isl_dim_out);
1407
1408 if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1409 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1410 pos -= isl_basic_map_dim(bmap, isl_dim_in);
1411
1412 if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1413 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1414 isl_basic_map_dim(bmap, isl_dim_in) +
1415 isl_basic_map_dim(bmap, isl_dim_out) + pos;
1416 pos -= isl_basic_map_dim(bmap, isl_dim_div);
1417
1418 if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1419 return 1 + pos;
1420
1421 return 0;
1422 }
1423
1424 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1425 struct isl_stream *s, __isl_take isl_basic_map *bmap)
1426 {
1427 int j;
1428 struct isl_token *tok;
1429 int type;
1430 int k;
1431 isl_int *c;
1432 unsigned nparam;
1433 unsigned dim;
1434
1435 if (!bmap)
1436 return NULL;
1437
1438 nparam = isl_basic_map_dim(bmap, isl_dim_param);
1439 dim = isl_basic_map_dim(bmap, isl_dim_out);
1440
1441 tok = isl_stream_next_token(s);
1442 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1443 isl_stream_error(s, tok, "expecting coefficient");
1444 if (tok)
1445 isl_stream_push_token(s, tok);
1446 goto error;
1447 }
1448 if (!tok->on_new_line) {
1449 isl_stream_error(s, tok, "coefficient should appear on new line");
1450 isl_stream_push_token(s, tok);
1451 goto error;
1452 }
1453
1454 type = isl_int_get_si(tok->u.v);
1455 isl_token_free(tok);
1456
1457 isl_assert(s->ctx, type == 0 || type == 1, goto error);
1458 if (type == 0) {
1459 k = isl_basic_map_alloc_equality(bmap);
1460 c = bmap->eq[k];
1461 } else {
1462 k = isl_basic_map_alloc_inequality(bmap);
1463 c = bmap->ineq[k];
1464 }
1465 if (k < 0)
1466 goto error;
1467
1468 for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1469 int pos;
1470 tok = isl_stream_next_token(s);
1471 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1472 isl_stream_error(s, tok, "expecting coefficient");
1473 if (tok)
1474 isl_stream_push_token(s, tok);
1475 goto error;
1476 }
1477 if (tok->on_new_line) {
1478 isl_stream_error(s, tok,
1479 "coefficient should not appear on new line");
1480 isl_stream_push_token(s, tok);
1481 goto error;
1482 }
1483 pos = polylib_pos_to_isl_pos(bmap, j);
1484 isl_int_set(c[pos], tok->u.v);
1485 isl_token_free(tok);
1486 }
1487
1488 return bmap;
1489 error:
1490 isl_basic_map_free(bmap);
1491 return NULL;
1492 }
1493
1494 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s,
1495 int nparam)
1496 {
1497 int i;
1498 struct isl_token *tok;
1499 struct isl_token *tok2;
1500 int n_row, n_col;
1501 int on_new_line;
1502 unsigned in = 0, out, local = 0;
1503 struct isl_basic_map *bmap = NULL;
1504
1505 if (nparam < 0)
1506 nparam = 0;
1507
1508 tok = isl_stream_next_token(s);
1509 if (!tok) {
1510 isl_stream_error(s, NULL, "unexpected EOF");
1511 return NULL;
1512 }
1513 tok2 = isl_stream_next_token(s);
1514 if (!tok2) {
1515 isl_token_free(tok);
1516 isl_stream_error(s, NULL, "unexpected EOF");
1517 return NULL;
1518 }
1519 if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1520 isl_stream_push_token(s, tok2);
1521 isl_stream_push_token(s, tok);
1522 isl_stream_error(s, NULL,
1523 "expecting constraint matrix dimensions");
1524 return NULL;
1525 }
1526 n_row = isl_int_get_si(tok->u.v);
1527 n_col = isl_int_get_si(tok2->u.v);
1528 on_new_line = tok2->on_new_line;
1529 isl_token_free(tok2);
1530 isl_token_free(tok);
1531 isl_assert(s->ctx, !on_new_line, return NULL);
1532 isl_assert(s->ctx, n_row >= 0, return NULL);
1533 isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1534 tok = isl_stream_next_token_on_same_line(s);
1535 if (tok) {
1536 if (tok->type != ISL_TOKEN_VALUE) {
1537 isl_stream_error(s, tok,
1538 "expecting number of output dimensions");
1539 isl_stream_push_token(s, tok);
1540 goto error;
1541 }
1542 out = isl_int_get_si(tok->u.v);
1543 isl_token_free(tok);
1544
1545 tok = isl_stream_next_token_on_same_line(s);
1546 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1547 isl_stream_error(s, tok,
1548 "expecting number of input dimensions");
1549 if (tok)
1550 isl_stream_push_token(s, tok);
1551 goto error;
1552 }
1553 in = isl_int_get_si(tok->u.v);
1554 isl_token_free(tok);
1555
1556 tok = isl_stream_next_token_on_same_line(s);
1557 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1558 isl_stream_error(s, tok,
1559 "expecting number of existentials");
1560 if (tok)
1561 isl_stream_push_token(s, tok);
1562 goto error;
1563 }
1564 local = isl_int_get_si(tok->u.v);
1565 isl_token_free(tok);
1566
1567 tok = isl_stream_next_token_on_same_line(s);
1568 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1569 isl_stream_error(s, tok,
1570 "expecting number of parameters");
1571 if (tok)
1572 isl_stream_push_token(s, tok);
1573 goto error;
1574 }
1575 nparam = isl_int_get_si(tok->u.v);
1576 isl_token_free(tok);
1577 if (n_col != 1 + out + in + local + nparam + 1) {
1578 isl_stream_error(s, NULL,
1579 "dimensions don't match");
1580 goto error;
1581 }
1582 } else
1583 out = n_col - 2 - nparam;
1584 bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1585 if (!bmap)
1586 return NULL;
1587
1588 for (i = 0; i < local; ++i) {
1589 int k = isl_basic_map_alloc_div(bmap);
1590 if (k < 0)
1591 goto error;
1592 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1593 }
1594
1595 for (i = 0; i < n_row; ++i)
1596 bmap = basic_map_read_polylib_constraint(s, bmap);
1597
1598 tok = isl_stream_next_token_on_same_line(s);
1599 if (tok) {
1600 isl_stream_error(s, tok, "unexpected extra token on line");
1601 isl_stream_push_token(s, tok);
1602 goto error;
1603 }
1604
1605 bmap = isl_basic_map_simplify(bmap);
1606 bmap = isl_basic_map_finalize(bmap);
1607 return bmap;
1608 error:
1609 isl_basic_map_free(bmap);
1610 return NULL;
1611 }
1612
1613 static struct isl_map *map_read_polylib(struct isl_stream *s, int nparam)
1614 {
1615 struct isl_token *tok;
1616 struct isl_token *tok2;
1617 int i, n;
1618 struct isl_map *map;
1619
1620 tok = isl_stream_next_token(s);
1621 if (!tok) {
1622 isl_stream_error(s, NULL, "unexpected EOF");
1623 return NULL;
1624 }
1625 tok2 = isl_stream_next_token_on_same_line(s);
1626 if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
1627 isl_stream_push_token(s, tok2);
1628 isl_stream_push_token(s, tok);
1629 return isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
1630 }
1631 if (tok2) {
1632 isl_stream_error(s, tok2, "unexpected token");
1633 isl_stream_push_token(s, tok2);
1634 isl_stream_push_token(s, tok);
1635 return NULL;
1636 }
1637 n = isl_int_get_si(tok->u.v);
1638 isl_token_free(tok);
1639
1640 isl_assert(s->ctx, n >= 1, return NULL);
1641
1642 map = isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
1643
1644 for (i = 1; map && i < n; ++i)
1645 map = isl_map_union(map,
1646 isl_map_from_basic_map(basic_map_read_polylib(s, nparam)));
1647
1648 return map;
1649 }
1650
1651 static int optional_power(struct isl_stream *s)
1652 {
1653 int pow;
1654 struct isl_token *tok;
1655
1656 tok = isl_stream_next_token(s);
1657 if (!tok)
1658 return 1;
1659 if (tok->type != '^') {
1660 isl_stream_push_token(s, tok);
1661 return 1;
1662 }
1663 isl_token_free(tok);
1664 tok = isl_stream_next_token(s);
1665 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1666 isl_stream_error(s, tok, "expecting exponent");
1667 if (tok)
1668 isl_stream_push_token(s, tok);
1669 return 1;
1670 }
1671 pow = isl_int_get_si(tok->u.v);
1672 isl_token_free(tok);
1673 return pow;
1674 }
1675
1676 static __isl_give isl_div *read_div(struct isl_stream *s,
1677 __isl_take isl_dim *dim, struct vars *v)
1678 {
1679 int n;
1680 isl_basic_map *bmap;
1681
1682 n = v->n;
1683 bmap = isl_basic_map_universe(dim);
1684
1685 if (vars_add_anon(v) < 0)
1686 goto error;
1687 if (read_div_definition(s, v) < 0)
1688 goto error;
1689 bmap = add_divs(bmap, v);
1690 bmap = isl_basic_map_order_divs(bmap);
1691 if (!bmap)
1692 goto error;
1693 vars_drop(v, v->n - n);
1694
1695 return isl_basic_map_div(bmap, bmap->n_div - 1);
1696 error:
1697 isl_basic_map_free(bmap);
1698 return NULL;
1699 }
1700
1701 static __isl_give isl_qpolynomial *read_term(struct isl_stream *s,
1702 __isl_keep isl_basic_map *bmap, struct vars *v);
1703
1704 static __isl_give isl_qpolynomial *read_factor(struct isl_stream *s,
1705 __isl_keep isl_basic_map *bmap, struct vars *v)
1706 {
1707 struct isl_qpolynomial *qp;
1708 struct isl_token *tok;
1709
1710 tok = next_token(s);
1711 if (!tok) {
1712 isl_stream_error(s, NULL, "unexpected EOF");
1713 return NULL;
1714 }
1715 if (tok->type == '(') {
1716 int pow;
1717
1718 isl_token_free(tok);
1719 qp = read_term(s, bmap, v);
1720 if (!qp)
1721 return NULL;
1722 if (isl_stream_eat(s, ')'))
1723 goto error;
1724 pow = optional_power(s);
1725 qp = isl_qpolynomial_pow(qp, pow);
1726 } else if (tok->type == ISL_TOKEN_VALUE) {
1727 struct isl_token *tok2;
1728 tok2 = isl_stream_next_token(s);
1729 if (tok2 && tok2->type == '/') {
1730 isl_token_free(tok2);
1731 tok2 = next_token(s);
1732 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1733 isl_stream_error(s, tok2, "expected denominator");
1734 isl_token_free(tok);
1735 isl_token_free(tok2);
1736 return NULL;
1737 }
1738 qp = isl_qpolynomial_rat_cst(isl_basic_map_get_dim(bmap),
1739 tok->u.v, tok2->u.v);
1740 isl_token_free(tok2);
1741 } else {
1742 isl_stream_push_token(s, tok2);
1743 qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap),
1744 tok->u.v);
1745 }
1746 isl_token_free(tok);
1747 } else if (tok->type == ISL_TOKEN_INFTY) {
1748 isl_token_free(tok);
1749 qp = isl_qpolynomial_infty(isl_basic_map_get_dim(bmap));
1750 } else if (tok->type == ISL_TOKEN_NAN) {
1751 isl_token_free(tok);
1752 qp = isl_qpolynomial_nan(isl_basic_map_get_dim(bmap));
1753 } else if (tok->type == ISL_TOKEN_IDENT) {
1754 int n = v->n;
1755 int pos = vars_pos(v, tok->u.s, -1);
1756 int pow;
1757 if (pos < 0) {
1758 isl_token_free(tok);
1759 return NULL;
1760 }
1761 if (pos >= n) {
1762 vars_drop(v, v->n - n);
1763 isl_stream_error(s, tok, "unknown identifier");
1764 isl_token_free(tok);
1765 return NULL;
1766 }
1767 isl_token_free(tok);
1768 pow = optional_power(s);
1769 qp = isl_qpolynomial_var_pow(isl_basic_map_get_dim(bmap), pos, pow);
1770 } else if (tok->type == '[') {
1771 isl_div *div;
1772 int pow;
1773
1774 isl_stream_push_token(s, tok);
1775 div = read_div(s, isl_basic_map_get_dim(bmap), v);
1776 pow = optional_power(s);
1777 qp = isl_qpolynomial_div_pow(div, pow);
1778 } else if (tok->type == '-') {
1779 struct isl_qpolynomial *qp2;
1780
1781 isl_token_free(tok);
1782 qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap),
1783 s->ctx->negone);
1784 qp2 = read_factor(s, bmap, v);
1785 qp = isl_qpolynomial_mul(qp, qp2);
1786 } else {
1787 isl_stream_error(s, tok, "unexpected isl_token");
1788 isl_stream_push_token(s, tok);
1789 return NULL;
1790 }
1791
1792 if (isl_stream_eat_if_available(s, '*') ||
1793 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
1794 struct isl_qpolynomial *qp2;
1795
1796 qp2 = read_factor(s, bmap, v);
1797 qp = isl_qpolynomial_mul(qp, qp2);
1798 }
1799
1800 return qp;
1801 error:
1802 isl_qpolynomial_free(qp);
1803 return NULL;
1804 }
1805
1806 static __isl_give isl_qpolynomial *read_term(struct isl_stream *s,
1807 __isl_keep isl_basic_map *bmap, struct vars *v)
1808 {
1809 struct isl_token *tok;
1810 struct isl_qpolynomial *qp;
1811
1812 qp = read_factor(s, bmap, v);
1813
1814 for (;;) {
1815 tok = next_token(s);
1816 if (!tok)
1817 return qp;
1818
1819 if (tok->type == '+') {
1820 struct isl_qpolynomial *qp2;
1821
1822 isl_token_free(tok);
1823 qp2 = read_factor(s, bmap, v);
1824 qp = isl_qpolynomial_add(qp, qp2);
1825 } else if (tok->type == '-') {
1826 struct isl_qpolynomial *qp2;
1827
1828 isl_token_free(tok);
1829 qp2 = read_factor(s, bmap, v);
1830 qp = isl_qpolynomial_sub(qp, qp2);
1831 } else if (tok->type == ISL_TOKEN_VALUE &&
1832 isl_int_is_neg(tok->u.v)) {
1833 struct isl_qpolynomial *qp2;
1834
1835 isl_stream_push_token(s, tok);
1836 qp2 = read_factor(s, bmap, v);
1837 qp = isl_qpolynomial_add(qp, qp2);
1838 } else {
1839 isl_stream_push_token(s, tok);
1840 break;
1841 }
1842 }
1843
1844 return qp;
1845 }
1846
1847 static __isl_give isl_map *read_optional_disjuncts(struct isl_stream *s,
1848 __isl_take isl_basic_map *bmap, struct vars *v)
1849 {
1850 struct isl_token *tok;
1851 struct isl_map *map;
1852
1853 tok = isl_stream_next_token(s);
1854 if (!tok) {
1855 isl_stream_error(s, NULL, "unexpected EOF");
1856 goto error;
1857 }
1858 map = isl_map_from_basic_map(isl_basic_map_copy(bmap));
1859 if (tok->type == ':' ||
1860 (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {
1861 isl_token_free(tok);
1862 map = isl_map_intersect(map,
1863 read_disjuncts(s, v, isl_basic_map_copy(bmap)));
1864 } else
1865 isl_stream_push_token(s, tok);
1866
1867 isl_basic_map_free(bmap);
1868
1869 return map;
1870 error:
1871 isl_basic_map_free(bmap);
1872 return NULL;
1873 }
1874
1875 static struct isl_obj obj_read_poly(struct isl_stream *s,
1876 __isl_take isl_basic_map *bmap, struct vars *v, int n)
1877 {
1878 struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
1879 struct isl_pw_qpolynomial *pwqp;
1880 struct isl_qpolynomial *qp;
1881 struct isl_map *map;
1882 struct isl_set *set;
1883
1884 qp = read_term(s, bmap, v);
1885 map = read_optional_disjuncts(s, bmap, v);
1886 set = isl_map_range(map);
1887
1888 pwqp = isl_pw_qpolynomial_alloc(set, qp);
1889
1890 vars_drop(v, v->n - n);
1891
1892 obj.v = pwqp;
1893 return obj;
1894 }
1895
1896 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
1897 __isl_take isl_basic_map *bmap, struct vars *v, int n)
1898 {
1899 struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
1900 isl_qpolynomial *qp;
1901 isl_qpolynomial_fold *fold = NULL;
1902 isl_pw_qpolynomial_fold *pwf;
1903 isl_map *map;
1904 isl_set *set;
1905
1906 if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
1907 return obj_read_poly(s, bmap, v, n);
1908
1909 if (isl_stream_eat(s, '('))
1910 goto error;
1911
1912 qp = read_term(s, bmap, v);
1913 fold = isl_qpolynomial_fold_alloc(isl_fold_max, qp);
1914
1915 while (isl_stream_eat_if_available(s, ',')) {
1916 isl_qpolynomial_fold *fold_i;
1917 qp = read_term(s, bmap, v);
1918 fold_i = isl_qpolynomial_fold_alloc(isl_fold_max, qp);
1919 fold = isl_qpolynomial_fold_fold(fold, fold_i);
1920 }
1921
1922 if (isl_stream_eat(s, ')'))
1923 goto error;
1924
1925 map = read_optional_disjuncts(s, bmap, v);
1926 set = isl_map_range(map);
1927 pwf = isl_pw_qpolynomial_fold_alloc(isl_fold_max, set, fold);
1928
1929 vars_drop(v, v->n - n);
1930
1931 obj.v = pwf;
1932 return obj;
1933 error:
1934 isl_basic_map_free(bmap);
1935 isl_qpolynomial_fold_free(fold);
1936 obj.type = isl_obj_none;
1937 return obj;
1938 }
1939
1940 static int is_rational(struct isl_stream *s)
1941 {
1942 struct isl_token *tok;
1943
1944 tok = isl_stream_next_token(s);
1945 if (!tok)
1946 return 0;
1947 if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) {
1948 isl_token_free(tok);
1949 isl_stream_eat(s, ':');
1950 return 1;
1951 }
1952
1953 isl_stream_push_token(s, tok);
1954
1955 return 0;
1956 }
1957
1958 static struct isl_obj obj_read_body(struct isl_stream *s,
1959 __isl_take isl_basic_map *bmap, struct vars *v)
1960 {
1961 struct isl_map *map = NULL;
1962 struct isl_token *tok;
1963 struct isl_obj obj = { isl_obj_set, NULL };
1964 int n = v->n;
1965
1966 if (is_rational(s))
1967 bmap = isl_basic_map_set_rational(bmap);
1968
1969 if (!next_is_tuple(s))
1970 return obj_read_poly_or_fold(s, bmap, v, n);
1971
1972 bmap = read_tuple(s, bmap, isl_dim_in, v);
1973 if (!bmap)
1974 goto error;
1975 tok = isl_stream_next_token(s);
1976 if (tok && tok->type == ISL_TOKEN_TO) {
1977 obj.type = isl_obj_map;
1978 isl_token_free(tok);
1979 if (!next_is_tuple(s)) {
1980 bmap = isl_basic_map_reverse(bmap);
1981 return obj_read_poly_or_fold(s, bmap, v, n);
1982 }
1983 bmap = read_tuple(s, bmap, isl_dim_out, v);
1984 if (!bmap)
1985 goto error;
1986 } else {
1987 bmap = isl_basic_map_reverse(bmap);
1988 if (tok)
1989 isl_stream_push_token(s, tok);
1990 }
1991
1992 map = read_optional_disjuncts(s, bmap, v);
1993
1994 vars_drop(v, v->n - n);
1995
1996 obj.v = map;
1997 return obj;
1998 error:
1999 isl_basic_map_free(bmap);
2000 obj.type = isl_obj_none;
2001 return obj;
2002 }
2003
2004 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
2005 {
2006 if (obj.type == isl_obj_map) {
2007 obj.v = isl_union_map_from_map(obj.v);
2008 obj.type = isl_obj_union_map;
2009 } else if (obj.type == isl_obj_set) {
2010 obj.v = isl_union_set_from_set(obj.v);
2011 obj.type = isl_obj_union_set;
2012 } else if (obj.type == isl_obj_pw_qpolynomial) {
2013 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2014 obj.type = isl_obj_union_pw_qpolynomial;
2015 } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
2016 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
2017 obj.type = isl_obj_union_pw_qpolynomial_fold;
2018 } else
2019 isl_assert(ctx, 0, goto error);
2020 return obj;
2021 error:
2022 obj.type->free(obj.v);
2023 obj.type = isl_obj_none;
2024 return obj;
2025 }
2026
2027 static struct isl_obj obj_add(struct isl_ctx *ctx,
2028 struct isl_obj obj1, struct isl_obj obj2)
2029 {
2030 if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
2031 obj1 = to_union(ctx, obj1);
2032 if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
2033 obj2 = to_union(ctx, obj2);
2034 if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
2035 obj1 = to_union(ctx, obj1);
2036 if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
2037 obj2 = to_union(ctx, obj2);
2038 if (obj1.type == isl_obj_pw_qpolynomial &&
2039 obj2.type == isl_obj_union_pw_qpolynomial)
2040 obj1 = to_union(ctx, obj1);
2041 if (obj1.type == isl_obj_union_pw_qpolynomial &&
2042 obj2.type == isl_obj_pw_qpolynomial)
2043 obj2 = to_union(ctx, obj2);
2044 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2045 obj2.type == isl_obj_union_pw_qpolynomial_fold)
2046 obj1 = to_union(ctx, obj1);
2047 if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
2048 obj2.type == isl_obj_pw_qpolynomial_fold)
2049 obj2 = to_union(ctx, obj2);
2050 isl_assert(ctx, obj1.type == obj2.type, goto error);
2051 if (obj1.type == isl_obj_map && !isl_map_has_equal_dim(obj1.v, obj2.v)) {
2052 obj1 = to_union(ctx, obj1);
2053 obj2 = to_union(ctx, obj2);
2054 }
2055 if (obj1.type == isl_obj_set && !isl_set_has_equal_dim(obj1.v, obj2.v)) {
2056 obj1 = to_union(ctx, obj1);
2057 obj2 = to_union(ctx, obj2);
2058 }
2059 if (obj1.type == isl_obj_pw_qpolynomial &&
2060 !isl_pw_qpolynomial_has_equal_dim(obj1.v, obj2.v)) {
2061 obj1 = to_union(ctx, obj1);
2062 obj2 = to_union(ctx, obj2);
2063 }
2064 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2065 !isl_pw_qpolynomial_fold_has_equal_dim(obj1.v, obj2.v)) {
2066 obj1 = to_union(ctx, obj1);
2067 obj2 = to_union(ctx, obj2);
2068 }
2069 obj1.v = obj1.type->add(obj1.v, obj2.v);
2070 return obj1;
2071 error:
2072 obj1.type->free(obj1.v);
2073 obj2.type->free(obj2.v);
2074 obj1.type = isl_obj_none;
2075 obj1.v = NULL;
2076 return obj1;
2077 }
2078
2079 static struct isl_obj obj_read(struct isl_stream *s, int nparam)
2080 {
2081 isl_basic_map *bmap = NULL;
2082 struct isl_token *tok;
2083 struct vars *v = NULL;
2084 struct isl_obj obj = { isl_obj_set, NULL };
2085
2086 tok = next_token(s);
2087 if (!tok) {
2088 isl_stream_error(s, NULL, "unexpected EOF");
2089 goto error;
2090 }
2091 if (tok->type == ISL_TOKEN_VALUE) {
2092 struct isl_token *tok2;
2093 struct isl_map *map;
2094
2095 tok2 = isl_stream_next_token(s);
2096 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
2097 isl_int_is_neg(tok2->u.v)) {
2098 if (tok2)
2099 isl_stream_push_token(s, tok2);
2100 obj.type = isl_obj_int;
2101 obj.v = isl_int_obj_alloc(s->ctx, tok->u.v);
2102 isl_token_free(tok);
2103 return obj;
2104 }
2105 isl_stream_push_token(s, tok2);
2106 isl_stream_push_token(s, tok);
2107 map = map_read_polylib(s, nparam);
2108 if (!map)
2109 goto error;
2110 if (isl_map_dim(map, isl_dim_in) > 0)
2111 obj.type = isl_obj_map;
2112 obj.v = map;
2113 return obj;
2114 }
2115 v = vars_new(s->ctx);
2116 if (!v) {
2117 isl_stream_push_token(s, tok);
2118 goto error;
2119 }
2120 bmap = isl_basic_map_alloc(s->ctx, 0, 0, 0, 0, 0, 0);
2121 if (tok->type == '[') {
2122 isl_stream_push_token(s, tok);
2123 bmap = read_tuple(s, bmap, isl_dim_param, v);
2124 if (!bmap)
2125 goto error;
2126 if (nparam >= 0)
2127 isl_assert(s->ctx, nparam == v->n, goto error);
2128 tok = isl_stream_next_token(s);
2129 if (!tok || tok->type != ISL_TOKEN_TO) {
2130 isl_stream_error(s, tok, "expecting '->'");
2131 if (tok)
2132 isl_stream_push_token(s, tok);
2133 goto error;
2134 }
2135 isl_token_free(tok);
2136 tok = isl_stream_next_token(s);
2137 } else if (nparam > 0)
2138 bmap = isl_basic_map_add(bmap, isl_dim_param, nparam);
2139 if (!tok || tok->type != '{') {
2140 isl_stream_error(s, tok, "expecting '{'");
2141 if (tok)
2142 isl_stream_push_token(s, tok);
2143 goto error;
2144 }
2145 isl_token_free(tok);
2146
2147 tok = isl_stream_next_token(s);
2148 if (!tok)
2149 ;
2150 else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
2151 isl_token_free(tok);
2152 if (isl_stream_eat(s, '='))
2153 goto error;
2154 bmap = read_tuple(s, bmap, isl_dim_param, v);
2155 if (!bmap)
2156 goto error;
2157 if (nparam >= 0)
2158 isl_assert(s->ctx, nparam == v->n, goto error);
2159 } else if (tok->type == '}') {
2160 obj.type = isl_obj_union_set;
2161 obj.v = isl_union_set_empty(isl_basic_map_get_dim(bmap));
2162 isl_token_free(tok);
2163 goto done;
2164 } else
2165 isl_stream_push_token(s, tok);
2166
2167 for (;;) {
2168 struct isl_obj o;
2169 tok = NULL;
2170 o = obj_read_body(s, isl_basic_map_copy(bmap), v);
2171 if (o.type == isl_obj_none || !o.v)
2172 goto error;
2173 if (!obj.v)
2174 obj = o;
2175 else {
2176 obj = obj_add(s->ctx, obj, o);
2177 if (obj.type == isl_obj_none || !obj.v)
2178 goto error;
2179 }
2180 tok = isl_stream_next_token(s);
2181 if (!tok || tok->type != ';')
2182 break;
2183 isl_token_free(tok);
2184 if (isl_stream_next_token_is(s, '}')) {
2185 tok = isl_stream_next_token(s);
2186 break;
2187 }
2188 }
2189
2190 if (tok && tok->type == '}') {
2191 isl_token_free(tok);
2192 } else {
2193 isl_stream_error(s, tok, "unexpected isl_token");
2194 if (tok)
2195 isl_token_free(tok);
2196 goto error;
2197 }
2198 done:
2199 vars_free(v);
2200 isl_basic_map_free(bmap);
2201
2202 return obj;
2203 error:
2204 isl_basic_map_free(bmap);
2205 obj.type->free(obj.v);
2206 if (v)
2207 vars_free(v);
2208 obj.v = NULL;
2209 return obj;
2210 }
2211
2212 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
2213 {
2214 return obj_read(s, -1);
2215 }
2216
2217 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s, int nparam)
2218 {
2219 struct isl_obj obj;
2220
2221 obj = obj_read(s, nparam);
2222 if (obj.v)
2223 isl_assert(s->ctx, obj.type == isl_obj_map ||
2224 obj.type == isl_obj_set, goto error);
2225
2226 return obj.v;
2227 error:
2228 obj.type->free(obj.v);
2229 return NULL;
2230 }
2231
2232 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s, int nparam)
2233 {
2234 struct isl_obj obj;
2235
2236 obj = obj_read(s, nparam);
2237 if (obj.v)
2238 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2239
2240 return obj.v;
2241 error:
2242 obj.type->free(obj.v);
2243 return NULL;
2244 }
2245
2246 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2247 {
2248 struct isl_obj obj;
2249
2250 obj = obj_read(s, -1);
2251 if (obj.type == isl_obj_map) {
2252 obj.type = isl_obj_union_map;
2253 obj.v = isl_union_map_from_map(obj.v);
2254 }
2255 if (obj.type == isl_obj_set) {
2256 obj.type = isl_obj_union_set;
2257 obj.v = isl_union_set_from_set(obj.v);
2258 }
2259 if (obj.v)
2260 isl_assert(s->ctx, obj.type == isl_obj_union_map ||
2261 obj.type == isl_obj_union_set, goto error);
2262
2263 return obj.v;
2264 error:
2265 obj.type->free(obj.v);
2266 return NULL;
2267 }
2268
2269 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2270 {
2271 struct isl_obj obj;
2272
2273 obj = obj_read(s, -1);
2274 if (obj.type == isl_obj_set) {
2275 obj.type = isl_obj_union_set;
2276 obj.v = isl_union_set_from_set(obj.v);
2277 }
2278 if (obj.v)
2279 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2280
2281 return obj.v;
2282 error:
2283 obj.type->free(obj.v);
2284 return NULL;
2285 }
2286
2287 static struct isl_basic_map *basic_map_read(struct isl_stream *s, int nparam)
2288 {
2289 struct isl_obj obj;
2290 struct isl_map *map;
2291 struct isl_basic_map *bmap;
2292
2293 obj = obj_read(s, nparam);
2294 map = obj.v;
2295 if (!map)
2296 return NULL;
2297
2298 isl_assert(map->ctx, map->n <= 1, goto error);
2299
2300 if (map->n == 0)
2301 bmap = isl_basic_map_empty_like_map(map);
2302 else
2303 bmap = isl_basic_map_copy(map->p[0]);
2304
2305 isl_map_free(map);
2306
2307 return bmap;
2308 error:
2309 isl_map_free(map);
2310 return NULL;
2311 }
2312
2313 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2314 FILE *input, int nparam)
2315 {
2316 struct isl_basic_map *bmap;
2317 struct isl_stream *s = isl_stream_new_file(ctx, input);
2318 if (!s)
2319 return NULL;
2320 bmap = basic_map_read(s, nparam);
2321 isl_stream_free(s);
2322 return bmap;
2323 }
2324
2325 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2326 FILE *input, int nparam)
2327 {
2328 struct isl_basic_map *bmap;
2329 bmap = isl_basic_map_read_from_file(ctx, input, nparam);
2330 if (!bmap)
2331 return NULL;
2332 isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
2333 return (struct isl_basic_set *)bmap;
2334 error:
2335 isl_basic_map_free(bmap);
2336 return NULL;
2337 }
2338
2339 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2340 const char *str, int nparam)
2341 {
2342 struct isl_basic_map *bmap;
2343 struct isl_stream *s = isl_stream_new_str(ctx, str);
2344 if (!s)
2345 return NULL;
2346 bmap = basic_map_read(s, nparam);
2347 isl_stream_free(s);
2348 return bmap;
2349 }
2350
2351 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2352 const char *str, int nparam)
2353 {
2354 struct isl_basic_map *bmap;
2355 bmap = isl_basic_map_read_from_str(ctx, str, nparam);
2356 if (!bmap)
2357 return NULL;
2358 isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
2359 return (struct isl_basic_set *)bmap;
2360 error:
2361 isl_basic_map_free(bmap);
2362 return NULL;
2363 }
2364
2365 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2366 FILE *input, int nparam)
2367 {
2368 struct isl_map *map;
2369 struct isl_stream *s = isl_stream_new_file(ctx, input);
2370 if (!s)
2371 return NULL;
2372 map = isl_stream_read_map(s, nparam);
2373 isl_stream_free(s);
2374 return map;
2375 }
2376
2377 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2378 const char *str, int nparam)
2379 {
2380 struct isl_map *map;
2381 struct isl_stream *s = isl_stream_new_str(ctx, str);
2382 if (!s)
2383 return NULL;
2384 map = isl_stream_read_map(s, nparam);
2385 isl_stream_free(s);
2386 return map;
2387 }
2388
2389 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2390 FILE *input, int nparam)
2391 {
2392 struct isl_map *map;
2393 map = isl_map_read_from_file(ctx, input, nparam);
2394 if (!map)
2395 return NULL;
2396 isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
2397 return (struct isl_set *)map;
2398 error:
2399 isl_map_free(map);
2400 return NULL;
2401 }
2402
2403 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2404 const char *str, int nparam)
2405 {
2406 struct isl_map *map;
2407 map = isl_map_read_from_str(ctx, str, nparam);
2408 if (!map)
2409 return NULL;
2410 isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
2411 return (struct isl_set *)map;
2412 error:
2413 isl_map_free(map);
2414 return NULL;
2415 }
2416
2417 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2418 FILE *input)
2419 {
2420 isl_union_map *umap;
2421 struct isl_stream *s = isl_stream_new_file(ctx, input);
2422 if (!s)
2423 return NULL;
2424 umap = isl_stream_read_union_map(s);
2425 isl_stream_free(s);
2426 return umap;
2427 }
2428
2429 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2430 const char *str)
2431 {
2432 isl_union_map *umap;
2433 struct isl_stream *s = isl_stream_new_str(ctx, str);
2434 if (!s)
2435 return NULL;
2436 umap = isl_stream_read_union_map(s);
2437 isl_stream_free(s);
2438 return umap;
2439 }
2440
2441 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2442 FILE *input)
2443 {
2444 isl_union_set *uset;
2445 struct isl_stream *s = isl_stream_new_file(ctx, input);
2446 if (!s)
2447 return NULL;
2448 uset = isl_stream_read_union_set(s);
2449 isl_stream_free(s);
2450 return uset;
2451 }
2452
2453 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2454 const char *str)
2455 {
2456 isl_union_set *uset;
2457 struct isl_stream *s = isl_stream_new_str(ctx, str);
2458 if (!s)
2459 return NULL;
2460 uset = isl_stream_read_union_set(s);
2461 isl_stream_free(s);
2462 return uset;
2463 }
2464
2465 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2466 {
2467 struct isl_vec *vec = NULL;
2468 struct isl_token *tok;
2469 unsigned size;
2470 int j;
2471
2472 tok = isl_stream_next_token(s);
2473 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2474 isl_stream_error(s, tok, "expecting vector length");
2475 goto error;
2476 }
2477
2478 size = isl_int_get_si(tok->u.v);
2479 isl_token_free(tok);
2480
2481 vec = isl_vec_alloc(s->ctx, size);
2482
2483 for (j = 0; j < size; ++j) {
2484 tok = isl_stream_next_token(s);
2485 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2486 isl_stream_error(s, tok, "expecting constant value");
2487 goto error;
2488 }
2489 isl_int_set(vec->el[j], tok->u.v);
2490 isl_token_free(tok);
2491 }
2492
2493 return vec;
2494 error:
2495 isl_token_free(tok);
2496 isl_vec_free(vec);
2497 return NULL;
2498 }
2499
2500 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2501 {
2502 return isl_vec_read_polylib(s);
2503 }
2504
2505 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2506 {
2507 isl_vec *v;
2508 struct isl_stream *s = isl_stream_new_file(ctx, input);
2509 if (!s)
2510 return NULL;
2511 v = vec_read(s);
2512 isl_stream_free(s);
2513 return v;
2514 }
2515
2516 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2517 struct isl_stream *s)
2518 {
2519 struct isl_obj obj;
2520
2521 obj = obj_read(s, -1);
2522 if (obj.v)
2523 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2524 goto error);
2525
2526 return obj.v;
2527 error:
2528 obj.type->free(obj.v);
2529 return NULL;
2530 }
2531
2532 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2533 const char *str)
2534 {
2535 isl_pw_qpolynomial *pwqp;
2536 struct isl_stream *s = isl_stream_new_str(ctx, str);
2537 if (!s)
2538 return NULL;
2539 pwqp = isl_stream_read_pw_qpolynomial(s);
2540 isl_stream_free(s);
2541 return pwqp;
2542 }
2543
2544 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
2545 FILE *input)
2546 {
2547 isl_pw_qpolynomial *pwqp;
2548 struct isl_stream *s = isl_stream_new_file(ctx, input);
2549 if (!s)
2550 return NULL;
2551 pwqp = isl_stream_read_pw_qpolynomial(s);
2552 isl_stream_free(s);
2553 return pwqp;
2554 }
Integer set library