?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_aff_drop_dims
[isl.git] / isl_input.c
blob2037998022f396f6777fdaa3bba24c2b0e22bd3c
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 break;
586
587 isl_token_free(tok);
588 i++;
589 }
590 if (tok)
591 isl_stream_push_token(s, tok);
592
593 return bmap;
594 error:
595 isl_token_free(tok);
596 isl_basic_map_free(bmap);
597 return NULL;
598 }
599
600 static __isl_give isl_mat *accept_affine_list(struct isl_stream *s,
601 struct vars *v)
602 {
603 struct isl_vec *vec;
604 struct isl_mat *mat;
605 struct isl_token *tok = NULL;
606
607 vec = accept_affine(s, v);
608 mat = isl_mat_from_row_vec(vec);
609 if (!mat)
610 return NULL;
611
612 for (;;) {
613 tok = isl_stream_next_token(s);
614 if (!tok) {
615 isl_stream_error(s, NULL, "unexpected EOF");
616 goto error;
617 }
618 if (tok->type != ',') {
619 isl_stream_push_token(s, tok);
620 break;
621 }
622 isl_token_free(tok);
623
624 vec = accept_affine(s, v);
625 mat = isl_mat_add_zero_cols(mat, 1 + v->n - isl_mat_cols(mat));
626 mat = isl_mat_vec_concat(mat, vec);
627 if (!mat)
628 return NULL;
629 }
630
631 return mat;
632 error:
633 isl_mat_free(mat);
634 return NULL;
635 }
636
637 static int read_minmax_definition(struct isl_stream *s, struct vars *v)
638 {
639 struct isl_token *tok;
640 struct variable *var;
641
642 var = v->v;
643
644 tok = isl_stream_next_token(s);
645 if (!tok)
646 return -1;
647 var->sign = tok->type == ISL_TOKEN_MIN ? -1 : 1;
648 isl_token_free(tok);
649
650 if (isl_stream_eat(s, '('))
651 return -1;
652
653 var->list = accept_affine_list(s, v);
654 if (!var->list)
655 return -1;
656
657 if (isl_stream_eat(s, ')'))
658 return -1;
659
660 return 0;
661 }
662
663 static int read_div_definition(struct isl_stream *s, struct vars *v)
664 {
665 struct isl_token *tok;
666 int seen_paren = 0;
667 struct isl_vec *aff;
668 struct variable *var;
669 int fc = 0;
670
671 if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOORD) ||
672 isl_stream_eat_if_available(s, ISL_TOKEN_CEILD)) {
673 fc = 1;
674 if (isl_stream_eat(s, '('))
675 return -1;
676 } else {
677 if (isl_stream_eat(s, '['))
678 return -1;
679 if (isl_stream_eat_if_available(s, '('))
680 seen_paren = 1;
681 }
682
683 var = v->v;
684
685 aff = accept_affine(s, v);
686 if (!aff)
687 return -1;
688
689 var->def = isl_vec_alloc(s->ctx, 2 + v->n);
690 if (!var->def) {
691 isl_vec_free(aff);
692 return -1;
693 }
694
695 isl_seq_cpy(var->def->el + 1, aff->el, aff->size);
696
697 isl_vec_free(aff);
698
699 if (fc) {
700 if (isl_stream_eat(s, ','))
701 return -1;
702 } else {
703 if (seen_paren && isl_stream_eat(s, ')'))
704 return -1;
705 if (isl_stream_eat(s, '/'))
706 return -1;
707 }
708
709 tok = next_token(s);
710 if (!tok)
711 return -1;
712 if (tok->type != ISL_TOKEN_VALUE) {
713 isl_stream_error(s, tok, "expected denominator");
714 isl_stream_push_token(s, tok);
715 return -1;
716 }
717 isl_int_set(var->def->el[0], tok->u.v);
718 isl_token_free(tok);
719
720 if (fc) {
721 if (isl_stream_eat(s, ')'))
722 return -1;
723 } else {
724 if (isl_stream_eat(s, ']'))
725 return -1;
726 }
727
728 return 0;
729 }
730
731 static struct isl_basic_map *add_div_definition(struct isl_stream *s,
732 struct vars *v, struct isl_basic_map *bmap, int pos)
733 {
734 struct variable *var = v->v;
735 unsigned o_out = isl_basic_map_offset(bmap, isl_dim_out) - 1;
736
737 if (read_div_definition(s, v) < 0)
738 goto error;
739
740 if (isl_basic_map_add_div_constraints_var(bmap, o_out + pos,
741 var->def->el) < 0)
742 goto error;
743
744 return bmap;
745 error:
746 isl_basic_map_free(bmap);
747 return NULL;
748 }
749
750 static struct isl_basic_map *read_defined_var_list(struct isl_stream *s,
751 struct vars *v, struct isl_basic_map *bmap)
752 {
753 struct isl_token *tok;
754
755 while ((tok = isl_stream_next_token(s)) != NULL) {
756 int p;
757 int n = v->n;
758 unsigned n_out = isl_basic_map_dim(bmap, isl_dim_out);
759
760 if (tok->type != ISL_TOKEN_IDENT)
761 break;
762
763 p = vars_pos(v, tok->u.s, -1);
764 if (p < 0)
765 goto error;
766 if (p < n) {
767 isl_stream_error(s, tok, "expecting unique identifier");
768 goto error;
769 }
770
771 bmap = isl_basic_map_cow(bmap);
772 bmap = isl_basic_map_add(bmap, isl_dim_out, 1);
773 bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
774 0, 0, 2);
775
776 isl_token_free(tok);
777 tok = isl_stream_next_token(s);
778 if (tok && tok->type == '=') {
779 isl_token_free(tok);
780 bmap = add_div_definition(s, v, bmap, n_out);
781 tok = isl_stream_next_token(s);
782 }
783
784 if (!tok || tok->type != ',')
785 break;
786
787 isl_token_free(tok);
788 }
789 if (tok)
790 isl_stream_push_token(s, tok);
791
792 return bmap;
793 error:
794 isl_token_free(tok);
795 isl_basic_map_free(bmap);
796 return NULL;
797 }
798
799 static int next_is_tuple(struct isl_stream *s)
800 {
801 struct isl_token *tok;
802 int is_tuple;
803
804 tok = isl_stream_next_token(s);
805 if (!tok)
806 return 0;
807 if (tok->type == '[') {
808 isl_stream_push_token(s, tok);
809 return 1;
810 }
811 if (tok->type != ISL_TOKEN_IDENT && !tok->is_keyword) {
812 isl_stream_push_token(s, tok);
813 return 0;
814 }
815
816 is_tuple = isl_stream_next_token_is(s, '[');
817
818 isl_stream_push_token(s, tok);
819
820 return is_tuple;
821 }
822
823 static __isl_give isl_basic_map *read_tuple(struct isl_stream *s,
824 __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v);
825
826 static __isl_give isl_basic_map *read_nested_tuple(struct isl_stream *s,
827 __isl_take isl_basic_map *bmap, struct vars *v)
828 {
829 bmap = read_tuple(s, bmap, isl_dim_in, v);
830 if (isl_stream_eat(s, ISL_TOKEN_TO))
831 goto error;
832 bmap = read_tuple(s, bmap, isl_dim_out, v);
833 bmap = isl_basic_map_from_range(isl_basic_map_wrap(bmap));
834 return bmap;
835 error:
836 isl_basic_map_free(bmap);
837 return NULL;
838 }
839
840 static __isl_give isl_basic_map *read_tuple(struct isl_stream *s,
841 __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
842 {
843 struct isl_token *tok;
844 char *name = NULL;
845
846 tok = isl_stream_next_token(s);
847 if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
848 name = strdup(tok->u.s);
849 if (!name)
850 goto error;
851 isl_token_free(tok);
852 tok = isl_stream_next_token(s);
853 }
854 if (!tok || tok->type != '[') {
855 isl_stream_error(s, tok, "expecting '['");
856 goto error;
857 }
858 isl_token_free(tok);
859 if (type != isl_dim_param && next_is_tuple(s)) {
860 isl_dim *dim = isl_basic_map_get_dim(bmap);
861 int nparam = isl_dim_size(dim, isl_dim_param);
862 int n_in = isl_dim_size(dim, isl_dim_in);
863 isl_basic_map *nested;
864 if (type == isl_dim_out)
865 dim = isl_dim_move(dim, isl_dim_param, nparam,
866 isl_dim_in, 0, n_in);
867 nested = isl_basic_map_alloc_dim(dim, 0, 0, 0);
868 nested = read_nested_tuple(s, nested, v);
869 if (type == isl_dim_in) {
870 nested = isl_basic_map_reverse(nested);
871 bmap = isl_basic_map_intersect(nested, bmap);
872 } else {
873 isl_basic_set *bset;
874 dim = isl_dim_range(isl_basic_map_get_dim(nested));
875 dim = isl_dim_drop(dim, isl_dim_param, nparam, n_in);
876 dim = isl_dim_join(isl_basic_map_get_dim(bmap), dim);
877 bset = isl_basic_map_domain(bmap);
878 nested = isl_basic_map_reset_dim(nested, dim);
879 bmap = isl_basic_map_intersect_domain(nested, bset);
880 }
881 } else
882 bmap = read_var_list(s, bmap, type, v);
883 tok = isl_stream_next_token(s);
884 if (!tok || tok->type != ']') {
885 isl_stream_error(s, tok, "expecting ']'");
886 goto error;
887 }
888 isl_token_free(tok);
889
890 if (name) {
891 bmap = isl_basic_map_set_tuple_name(bmap, type, name);
892 free(name);
893 }
894
895 return bmap;
896 error:
897 if (tok)
898 isl_token_free(tok);
899 isl_basic_map_free(bmap);
900 return NULL;
901 }
902
903 static __isl_give isl_basic_map *construct_constraint(
904 __isl_take isl_basic_map *bmap, enum isl_token_type type,
905 isl_int *left, isl_int *right)
906 {
907 int k;
908 unsigned len;
909 struct isl_ctx *ctx;
910
911 if (!bmap)
912 return NULL;
913 len = 1 + isl_basic_map_total_dim(bmap);
914 ctx = bmap->ctx;
915
916 k = isl_basic_map_alloc_inequality(bmap);
917 if (k < 0)
918 goto error;
919 if (type == ISL_TOKEN_LE)
920 isl_seq_combine(bmap->ineq[k], ctx->negone, left,
921 ctx->one, right,
922 len);
923 else if (type == ISL_TOKEN_GE)
924 isl_seq_combine(bmap->ineq[k], ctx->one, left,
925 ctx->negone, right,
926 len);
927 else if (type == ISL_TOKEN_LT) {
928 isl_seq_combine(bmap->ineq[k], ctx->negone, left,
929 ctx->one, right,
930 len);
931 isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1);
932 } else if (type == ISL_TOKEN_GT) {
933 isl_seq_combine(bmap->ineq[k], ctx->one, left,
934 ctx->negone, right,
935 len);
936 isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1);
937 } else {
938 isl_seq_combine(bmap->ineq[k], ctx->one, left,
939 ctx->negone, right,
940 len);
941 isl_basic_map_inequality_to_equality(bmap, k);
942 }
943
944 return bmap;
945 error:
946 isl_basic_map_free(bmap);
947 return NULL;
948 }
949
950 static int is_comparator(struct isl_token *tok)
951 {
952 if (!tok)
953 return 0;
954
955 switch (tok->type) {
956 case ISL_TOKEN_LT:
957 case ISL_TOKEN_GT:
958 case ISL_TOKEN_LE:
959 case ISL_TOKEN_GE:
960 case '=':
961 return 1;
962 default:
963 return 0;
964 }
965 }
966
967 /* Add any variables in the variable list "v" that are not already in "bmap"
968 * as output variables in "bmap".
969 */
970 static __isl_give isl_basic_map *add_lifted_divs(__isl_take isl_basic_map *bmap,
971 struct vars *v)
972 {
973 int i;
974 int extra;
975 struct variable *var;
976
977 extra = v->n - isl_basic_map_total_dim(bmap);
978
979 if (extra == 0)
980 return bmap;
981
982 bmap = isl_basic_map_add(bmap, isl_dim_out, extra);
983 bmap = isl_basic_map_extend_dim(bmap, isl_basic_map_get_dim(bmap),
984 0, 0, 2 * extra);
985
986 for (i = 0, var = v->v; i < extra; ++i, var = var->next) {
987 if (!var->def)
988 continue;
989 var->def = isl_vec_zero_extend(var->def, 2 + v->n);
990 if (!var->def)
991 goto error;
992 if (isl_basic_map_add_div_constraints_var(bmap, var->pos,
993 var->def->el) < 0)
994 goto error;
995 }
996
997 return bmap;
998 error:
999 isl_basic_map_free(bmap);
1000 return NULL;
1001 }
1002
1003 static struct isl_basic_map *add_constraint(struct isl_stream *s,
1004 struct vars *v, struct isl_basic_map *bmap)
1005 {
1006 int i, j;
1007 struct isl_token *tok = NULL;
1008 struct isl_mat *aff1 = NULL, *aff2 = NULL;
1009
1010 bmap = isl_basic_map_cow(bmap);
1011
1012 aff1 = accept_affine_list(s, v);
1013 if (!aff1)
1014 goto error;
1015 tok = isl_stream_next_token(s);
1016 if (!is_comparator(tok)) {
1017 isl_stream_error(s, tok, "missing operator");
1018 if (tok)
1019 isl_stream_push_token(s, tok);
1020 tok = NULL;
1021 goto error;
1022 }
1023 for (;;) {
1024 aff2 = accept_affine_list(s, v);
1025 if (!aff2)
1026 goto error;
1027
1028 aff1 = isl_mat_add_zero_cols(aff1, aff2->n_col - aff1->n_col);
1029 if (!aff1)
1030 goto error;
1031 bmap = add_lifted_divs(bmap, v);
1032 bmap = isl_basic_map_extend_constraints(bmap, 0,
1033 aff1->n_row * aff2->n_row);
1034 for (i = 0; i < aff1->n_row; ++i)
1035 for (j = 0; j < aff2->n_row; ++j)
1036 bmap = construct_constraint(bmap, tok->type,
1037 aff1->row[i], aff2->row[j]);
1038 isl_token_free(tok);
1039 isl_mat_free(aff1);
1040 aff1 = aff2;
1041
1042 tok = isl_stream_next_token(s);
1043 if (!is_comparator(tok)) {
1044 if (tok)
1045 isl_stream_push_token(s, tok);
1046 break;
1047 }
1048 }
1049 isl_mat_free(aff1);
1050
1051 return bmap;
1052 error:
1053 if (tok)
1054 isl_token_free(tok);
1055 isl_mat_free(aff1);
1056 isl_mat_free(aff2);
1057 isl_basic_map_free(bmap);
1058 return NULL;
1059 }
1060
1061 /* Return first variable, starting at n, representing a min or max,
1062 * or NULL if there is no such variable.
1063 */
1064 static struct variable *first_minmax(struct vars *v, int n)
1065 {
1066 struct variable *first = NULL;
1067 struct variable *var;
1068
1069 for (var = v->v; var && var->pos >= n; var = var->next)
1070 if (var->list)
1071 first = var;
1072
1073 return first;
1074 }
1075
1076 /* Check whether the variable at the given position only occurs in
1077 * inequalities and only with the given sign.
1078 */
1079 static int all_coefficients_of_sign(__isl_keep isl_map *map, int pos, int sign)
1080 {
1081 int i, j;
1082
1083 if (!map)
1084 return -1;
1085
1086 for (i = 0; i < map->n; ++i) {
1087 isl_basic_map *bmap = map->p[i];
1088
1089 for (j = 0; j < bmap->n_eq; ++j)
1090 if (!isl_int_is_zero(bmap->eq[j][1 + pos]))
1091 return 0;
1092 for (j = 0; j < bmap->n_ineq; ++j) {
1093 int s = isl_int_sgn(bmap->ineq[j][1 + pos]);
1094 if (s == 0)
1095 continue;
1096 if (s != sign)
1097 return 0;
1098 }
1099 }
1100
1101 return 1;
1102 }
1103
1104 /* Given a variable m which represents a min or a max of n expressions
1105 * b_i, add the constraints
1106 *
1107 * m <= b_i
1108 *
1109 * in case of a min (var->sign < 0) and m >= b_i in case of a max.
1110 */
1111 static __isl_give isl_map *bound_minmax(__isl_take isl_map *map,
1112 struct variable *var)
1113 {
1114 int i, k;
1115 isl_basic_map *bound;
1116 int total;
1117
1118 total = isl_map_dim(map, isl_dim_all);
1119 bound = isl_basic_map_alloc_dim(isl_map_get_dim(map),
1120 0, 0, var->list->n_row);
1121
1122 for (i = 0; i < var->list->n_row; ++i) {
1123 k = isl_basic_map_alloc_inequality(bound);
1124 if (k < 0)
1125 goto error;
1126 if (var->sign < 0)
1127 isl_seq_cpy(bound->ineq[k], var->list->row[i],
1128 var->list->n_col);
1129 else
1130 isl_seq_neg(bound->ineq[k], var->list->row[i],
1131 var->list->n_col);
1132 isl_int_set_si(bound->ineq[k][1 + var->pos], var->sign);
1133 isl_seq_clr(bound->ineq[k] + var->list->n_col,
1134 1 + total - var->list->n_col);
1135 }
1136
1137 map = isl_map_intersect(map, isl_map_from_basic_map(bound));
1138
1139 return map;
1140 error:
1141 isl_basic_map_free(bound);
1142 isl_map_free(map);
1143 return NULL;
1144 }
1145
1146 /* Given a variable m which represents a min (or max) of n expressions
1147 * b_i, add constraints that assigns the minimal upper bound to m, i.e.,
1148 * divide the space into cells where one
1149 * of the upper bounds is smaller than all the others and assign
1150 * this upper bound to m.
1151 *
1152 * In particular, if there are n bounds b_i, then the input map
1153 * is split into n pieces, each with the extra constraints
1154 *
1155 * m = b_i
1156 * b_i <= b_j for j > i
1157 * b_i < b_j for j < i
1158 *
1159 * in case of a min (var->sign < 0) and similarly in case of a max.
1160 *
1161 * Note: this function is very similar to set_minimum in isl_tab_pip.c
1162 * Perhaps we should try to merge the two.
1163 */
1164 static __isl_give isl_map *set_minmax(__isl_take isl_map *map,
1165 struct variable *var)
1166 {
1167 int i, j, k;
1168 isl_basic_map *bmap = NULL;
1169 isl_ctx *ctx;
1170 isl_map *split = NULL;
1171 int total;
1172
1173 ctx = isl_map_get_ctx(map);
1174 total = isl_map_dim(map, isl_dim_all);
1175 split = isl_map_alloc_dim(isl_map_get_dim(map),
1176 var->list->n_row, ISL_SET_DISJOINT);
1177
1178 for (i = 0; i < var->list->n_row; ++i) {
1179 bmap = isl_basic_map_alloc_dim(isl_map_get_dim(map), 0,
1180 1, var->list->n_row - 1);
1181 k = isl_basic_map_alloc_equality(bmap);
1182 if (k < 0)
1183 goto error;
1184 isl_seq_cpy(bmap->eq[k], var->list->row[i], var->list->n_col);
1185 isl_int_set_si(bmap->eq[k][1 + var->pos], -1);
1186 for (j = 0; j < var->list->n_row; ++j) {
1187 if (j == i)
1188 continue;
1189 k = isl_basic_map_alloc_inequality(bmap);
1190 if (k < 0)
1191 goto error;
1192 if (var->sign < 0)
1193 isl_seq_combine(bmap->ineq[k],
1194 ctx->one, var->list->row[j],
1195 ctx->negone, var->list->row[i],
1196 var->list->n_col);
1197 else
1198 isl_seq_combine(bmap->ineq[k],
1199 ctx->negone, var->list->row[j],
1200 ctx->one, var->list->row[i],
1201 var->list->n_col);
1202 isl_seq_clr(bmap->ineq[k] + var->list->n_col,
1203 1 + total - var->list->n_col);
1204 if (j < i)
1205 isl_int_sub_ui(bmap->ineq[k][0],
1206 bmap->ineq[k][0], 1);
1207 }
1208 bmap = isl_basic_map_finalize(bmap);
1209 split = isl_map_add_basic_map(split, bmap);
1210 }
1211
1212 map = isl_map_intersect(map, split);
1213
1214 return map;
1215 error:
1216 isl_basic_map_free(bmap);
1217 isl_map_free(split);
1218 isl_map_free(map);
1219 return NULL;
1220 }
1221
1222 /* Plug in the definitions of all min and max expressions.
1223 * If a min expression only appears in inequalities and only
1224 * with a positive coefficient, then we can simply bound
1225 * the variable representing the min by its defining terms
1226 * and similarly for a max expression.
1227 * Otherwise, we have to assign the different terms to the
1228 * variable under the condition that the assigned term is smaller
1229 * than the other terms.
1230 */
1231 static __isl_give isl_map *add_minmax(__isl_take isl_map *map,
1232 struct vars *v, int n)
1233 {
1234 struct variable *var;
1235
1236 while (n < v->n) {
1237 var = first_minmax(v, n);
1238 if (!var)
1239 break;
1240 if (all_coefficients_of_sign(map, var->pos, -var->sign))
1241 map = bound_minmax(map, var);
1242 else
1243 map = set_minmax(map, var);
1244 n = var->pos + 1;
1245 }
1246
1247 return map;
1248 }
1249
1250 static isl_map *read_constraint(struct isl_stream *s,
1251 struct vars *v, __isl_take isl_basic_map *bmap)
1252 {
1253 int n = v->n;
1254 isl_map *map;
1255 unsigned total;
1256
1257 if (!bmap)
1258 return NULL;
1259
1260 bmap = isl_basic_set_unwrap(isl_basic_set_lift(isl_basic_map_wrap(bmap)));
1261 total = isl_basic_map_total_dim(bmap);
1262 while (v->n < total)
1263 if (vars_add_anon(v) < 0)
1264 goto error;
1265
1266 bmap = add_constraint(s, v, bmap);
1267 bmap = isl_basic_map_simplify(bmap);
1268 bmap = isl_basic_map_finalize(bmap);
1269
1270 map = isl_map_from_basic_map(bmap);
1271
1272 map = add_minmax(map, v, n);
1273
1274 map = isl_set_unwrap(isl_map_domain(map));
1275
1276 vars_drop(v, v->n - n);
1277
1278 return map;
1279 error:
1280 isl_basic_map_free(bmap);
1281 return NULL;
1282 }
1283
1284 static struct isl_map *read_disjuncts(struct isl_stream *s,
1285 struct vars *v, __isl_take isl_basic_map *bmap);
1286
1287 static __isl_give isl_map *read_exists(struct isl_stream *s,
1288 struct vars *v, __isl_take isl_basic_map *bmap)
1289 {
1290 int n = v->n;
1291 int seen_paren = isl_stream_eat_if_available(s, '(');
1292 isl_map *map = NULL;
1293
1294 bmap = isl_basic_map_from_domain(isl_basic_map_wrap(bmap));
1295 bmap = read_defined_var_list(s, v, bmap);
1296
1297 if (isl_stream_eat(s, ':'))
1298 goto error;
1299
1300 map = read_disjuncts(s, v, bmap);
1301 map = isl_set_unwrap(isl_map_domain(map));
1302 bmap = NULL;
1303
1304 vars_drop(v, v->n - n);
1305 if (seen_paren && isl_stream_eat(s, ')'))
1306 goto error;
1307
1308 return map;
1309 error:
1310 isl_basic_map_free(bmap);
1311 isl_map_free(map);
1312 return NULL;
1313 }
1314
1315 static __isl_give isl_map *read_conjunct(struct isl_stream *s,
1316 struct vars *v, __isl_take isl_basic_map *bmap)
1317 {
1318 isl_map *map;
1319
1320 if (isl_stream_eat_if_available(s, '(')) {
1321 map = read_disjuncts(s, v, bmap);
1322 if (isl_stream_eat(s, ')'))
1323 goto error;
1324 return map;
1325 }
1326
1327 if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))
1328 return read_exists(s, v, bmap);
1329
1330 if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))
1331 return isl_map_from_basic_map(bmap);
1332
1333 if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) {
1334 isl_dim *dim = isl_basic_map_get_dim(bmap);
1335 isl_basic_map_free(bmap);
1336 return isl_map_empty(dim);
1337 }
1338
1339 return read_constraint(s, v, bmap);
1340 error:
1341 isl_map_free(map);
1342 return NULL;
1343 }
1344
1345 static __isl_give isl_map *read_conjuncts(struct isl_stream *s,
1346 struct vars *v, __isl_take isl_basic_map *bmap)
1347 {
1348 isl_map *map;
1349 int negate;
1350
1351 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1352 map = read_conjunct(s, v, isl_basic_map_copy(bmap));
1353 if (negate) {
1354 isl_map *t;
1355 t = isl_map_from_basic_map(isl_basic_map_copy(bmap));
1356 map = isl_map_subtract(t, map);
1357 }
1358
1359 while (isl_stream_eat_if_available(s, ISL_TOKEN_AND)) {
1360 isl_map *map_i;
1361
1362 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1363 map_i = read_conjunct(s, v, isl_basic_map_copy(bmap));
1364 if (negate)
1365 map = isl_map_subtract(map, map_i);
1366 else
1367 map = isl_map_intersect(map, map_i);
1368 }
1369
1370 isl_basic_map_free(bmap);
1371 return map;
1372 }
1373
1374 static struct isl_map *read_disjuncts(struct isl_stream *s,
1375 struct vars *v, __isl_take isl_basic_map *bmap)
1376 {
1377 struct isl_map *map;
1378
1379 if (isl_stream_next_token_is(s, '}')) {
1380 isl_dim *dim = isl_basic_map_get_dim(bmap);
1381 isl_basic_map_free(bmap);
1382 return isl_map_universe(dim);
1383 }
1384
1385 map = read_conjuncts(s, v, isl_basic_map_copy(bmap));
1386 while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
1387 isl_map *map_i;
1388
1389 map_i = read_conjuncts(s, v, isl_basic_map_copy(bmap));
1390 map = isl_map_union(map, map_i);
1391 }
1392
1393 isl_basic_map_free(bmap);
1394 return map;
1395 }
1396
1397 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1398 {
1399 if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1400 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1401 isl_basic_map_dim(bmap, isl_dim_in) + pos;
1402 pos -= isl_basic_map_dim(bmap, isl_dim_out);
1403
1404 if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1405 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1406 pos -= isl_basic_map_dim(bmap, isl_dim_in);
1407
1408 if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1409 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1410 isl_basic_map_dim(bmap, isl_dim_in) +
1411 isl_basic_map_dim(bmap, isl_dim_out) + pos;
1412 pos -= isl_basic_map_dim(bmap, isl_dim_div);
1413
1414 if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1415 return 1 + pos;
1416
1417 return 0;
1418 }
1419
1420 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1421 struct isl_stream *s, __isl_take isl_basic_map *bmap)
1422 {
1423 int j;
1424 struct isl_token *tok;
1425 int type;
1426 int k;
1427 isl_int *c;
1428 unsigned nparam;
1429 unsigned dim;
1430
1431 if (!bmap)
1432 return NULL;
1433
1434 nparam = isl_basic_map_dim(bmap, isl_dim_param);
1435 dim = isl_basic_map_dim(bmap, isl_dim_out);
1436
1437 tok = isl_stream_next_token(s);
1438 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1439 isl_stream_error(s, tok, "expecting coefficient");
1440 if (tok)
1441 isl_stream_push_token(s, tok);
1442 goto error;
1443 }
1444 if (!tok->on_new_line) {
1445 isl_stream_error(s, tok, "coefficient should appear on new line");
1446 isl_stream_push_token(s, tok);
1447 goto error;
1448 }
1449
1450 type = isl_int_get_si(tok->u.v);
1451 isl_token_free(tok);
1452
1453 isl_assert(s->ctx, type == 0 || type == 1, goto error);
1454 if (type == 0) {
1455 k = isl_basic_map_alloc_equality(bmap);
1456 c = bmap->eq[k];
1457 } else {
1458 k = isl_basic_map_alloc_inequality(bmap);
1459 c = bmap->ineq[k];
1460 }
1461 if (k < 0)
1462 goto error;
1463
1464 for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1465 int pos;
1466 tok = isl_stream_next_token(s);
1467 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1468 isl_stream_error(s, tok, "expecting coefficient");
1469 if (tok)
1470 isl_stream_push_token(s, tok);
1471 goto error;
1472 }
1473 if (tok->on_new_line) {
1474 isl_stream_error(s, tok,
1475 "coefficient should not appear on new line");
1476 isl_stream_push_token(s, tok);
1477 goto error;
1478 }
1479 pos = polylib_pos_to_isl_pos(bmap, j);
1480 isl_int_set(c[pos], tok->u.v);
1481 isl_token_free(tok);
1482 }
1483
1484 return bmap;
1485 error:
1486 isl_basic_map_free(bmap);
1487 return NULL;
1488 }
1489
1490 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s,
1491 int nparam)
1492 {
1493 int i;
1494 struct isl_token *tok;
1495 struct isl_token *tok2;
1496 int n_row, n_col;
1497 int on_new_line;
1498 unsigned in = 0, out, local = 0;
1499 struct isl_basic_map *bmap = NULL;
1500
1501 if (nparam < 0)
1502 nparam = 0;
1503
1504 tok = isl_stream_next_token(s);
1505 if (!tok) {
1506 isl_stream_error(s, NULL, "unexpected EOF");
1507 return NULL;
1508 }
1509 tok2 = isl_stream_next_token(s);
1510 if (!tok2) {
1511 isl_token_free(tok);
1512 isl_stream_error(s, NULL, "unexpected EOF");
1513 return NULL;
1514 }
1515 if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1516 isl_stream_push_token(s, tok2);
1517 isl_stream_push_token(s, tok);
1518 isl_stream_error(s, NULL,
1519 "expecting constraint matrix dimensions");
1520 return NULL;
1521 }
1522 n_row = isl_int_get_si(tok->u.v);
1523 n_col = isl_int_get_si(tok2->u.v);
1524 on_new_line = tok2->on_new_line;
1525 isl_token_free(tok2);
1526 isl_token_free(tok);
1527 isl_assert(s->ctx, !on_new_line, return NULL);
1528 isl_assert(s->ctx, n_row >= 0, return NULL);
1529 isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1530 tok = isl_stream_next_token_on_same_line(s);
1531 if (tok) {
1532 if (tok->type != ISL_TOKEN_VALUE) {
1533 isl_stream_error(s, tok,
1534 "expecting number of output dimensions");
1535 isl_stream_push_token(s, tok);
1536 goto error;
1537 }
1538 out = isl_int_get_si(tok->u.v);
1539 isl_token_free(tok);
1540
1541 tok = isl_stream_next_token_on_same_line(s);
1542 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1543 isl_stream_error(s, tok,
1544 "expecting number of input dimensions");
1545 if (tok)
1546 isl_stream_push_token(s, tok);
1547 goto error;
1548 }
1549 in = isl_int_get_si(tok->u.v);
1550 isl_token_free(tok);
1551
1552 tok = isl_stream_next_token_on_same_line(s);
1553 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1554 isl_stream_error(s, tok,
1555 "expecting number of existentials");
1556 if (tok)
1557 isl_stream_push_token(s, tok);
1558 goto error;
1559 }
1560 local = isl_int_get_si(tok->u.v);
1561 isl_token_free(tok);
1562
1563 tok = isl_stream_next_token_on_same_line(s);
1564 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1565 isl_stream_error(s, tok,
1566 "expecting number of parameters");
1567 if (tok)
1568 isl_stream_push_token(s, tok);
1569 goto error;
1570 }
1571 nparam = isl_int_get_si(tok->u.v);
1572 isl_token_free(tok);
1573 if (n_col != 1 + out + in + local + nparam + 1) {
1574 isl_stream_error(s, NULL,
1575 "dimensions don't match");
1576 goto error;
1577 }
1578 } else
1579 out = n_col - 2 - nparam;
1580 bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1581 if (!bmap)
1582 return NULL;
1583
1584 for (i = 0; i < local; ++i) {
1585 int k = isl_basic_map_alloc_div(bmap);
1586 if (k < 0)
1587 goto error;
1588 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1589 }
1590
1591 for (i = 0; i < n_row; ++i)
1592 bmap = basic_map_read_polylib_constraint(s, bmap);
1593
1594 tok = isl_stream_next_token_on_same_line(s);
1595 if (tok) {
1596 isl_stream_error(s, tok, "unexpected extra token on line");
1597 isl_stream_push_token(s, tok);
1598 goto error;
1599 }
1600
1601 bmap = isl_basic_map_simplify(bmap);
1602 bmap = isl_basic_map_finalize(bmap);
1603 return bmap;
1604 error:
1605 isl_basic_map_free(bmap);
1606 return NULL;
1607 }
1608
1609 static struct isl_map *map_read_polylib(struct isl_stream *s, int nparam)
1610 {
1611 struct isl_token *tok;
1612 struct isl_token *tok2;
1613 int i, n;
1614 struct isl_map *map;
1615
1616 tok = isl_stream_next_token(s);
1617 if (!tok) {
1618 isl_stream_error(s, NULL, "unexpected EOF");
1619 return NULL;
1620 }
1621 tok2 = isl_stream_next_token_on_same_line(s);
1622 if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
1623 isl_stream_push_token(s, tok2);
1624 isl_stream_push_token(s, tok);
1625 return isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
1626 }
1627 if (tok2) {
1628 isl_stream_error(s, tok2, "unexpected token");
1629 isl_stream_push_token(s, tok2);
1630 isl_stream_push_token(s, tok);
1631 return NULL;
1632 }
1633 n = isl_int_get_si(tok->u.v);
1634 isl_token_free(tok);
1635
1636 isl_assert(s->ctx, n >= 1, return NULL);
1637
1638 map = isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
1639
1640 for (i = 1; map && i < n; ++i)
1641 map = isl_map_union(map,
1642 isl_map_from_basic_map(basic_map_read_polylib(s, nparam)));
1643
1644 return map;
1645 }
1646
1647 static int optional_power(struct isl_stream *s)
1648 {
1649 int pow;
1650 struct isl_token *tok;
1651
1652 tok = isl_stream_next_token(s);
1653 if (!tok)
1654 return 1;
1655 if (tok->type != '^') {
1656 isl_stream_push_token(s, tok);
1657 return 1;
1658 }
1659 isl_token_free(tok);
1660 tok = isl_stream_next_token(s);
1661 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1662 isl_stream_error(s, tok, "expecting exponent");
1663 if (tok)
1664 isl_stream_push_token(s, tok);
1665 return 1;
1666 }
1667 pow = isl_int_get_si(tok->u.v);
1668 isl_token_free(tok);
1669 return pow;
1670 }
1671
1672 static __isl_give isl_div *read_div(struct isl_stream *s,
1673 __isl_take isl_dim *dim, struct vars *v)
1674 {
1675 int n;
1676 isl_basic_map *bmap;
1677
1678 n = v->n;
1679 bmap = isl_basic_map_universe(dim);
1680
1681 if (vars_add_anon(v) < 0)
1682 goto error;
1683 if (read_div_definition(s, v) < 0)
1684 goto error;
1685 bmap = add_divs(bmap, v);
1686 bmap = isl_basic_map_order_divs(bmap);
1687 if (!bmap)
1688 goto error;
1689 vars_drop(v, v->n - n);
1690
1691 return isl_basic_map_div(bmap, bmap->n_div - 1);
1692 error:
1693 isl_basic_map_free(bmap);
1694 return NULL;
1695 }
1696
1697 static __isl_give isl_qpolynomial *read_term(struct isl_stream *s,
1698 __isl_keep isl_basic_map *bmap, struct vars *v);
1699
1700 static __isl_give isl_qpolynomial *read_factor(struct isl_stream *s,
1701 __isl_keep isl_basic_map *bmap, struct vars *v)
1702 {
1703 struct isl_qpolynomial *qp;
1704 struct isl_token *tok;
1705
1706 tok = next_token(s);
1707 if (!tok) {
1708 isl_stream_error(s, NULL, "unexpected EOF");
1709 return NULL;
1710 }
1711 if (tok->type == '(') {
1712 int pow;
1713
1714 isl_token_free(tok);
1715 qp = read_term(s, bmap, v);
1716 if (!qp)
1717 return NULL;
1718 if (isl_stream_eat(s, ')'))
1719 goto error;
1720 pow = optional_power(s);
1721 qp = isl_qpolynomial_pow(qp, pow);
1722 } else if (tok->type == ISL_TOKEN_VALUE) {
1723 struct isl_token *tok2;
1724 tok2 = isl_stream_next_token(s);
1725 if (tok2 && tok2->type == '/') {
1726 isl_token_free(tok2);
1727 tok2 = next_token(s);
1728 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1729 isl_stream_error(s, tok2, "expected denominator");
1730 isl_token_free(tok);
1731 isl_token_free(tok2);
1732 return NULL;
1733 }
1734 qp = isl_qpolynomial_rat_cst(isl_basic_map_get_dim(bmap),
1735 tok->u.v, tok2->u.v);
1736 isl_token_free(tok2);
1737 } else {
1738 isl_stream_push_token(s, tok2);
1739 qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap),
1740 tok->u.v);
1741 }
1742 isl_token_free(tok);
1743 } else if (tok->type == ISL_TOKEN_INFTY) {
1744 isl_token_free(tok);
1745 qp = isl_qpolynomial_infty(isl_basic_map_get_dim(bmap));
1746 } else if (tok->type == ISL_TOKEN_NAN) {
1747 isl_token_free(tok);
1748 qp = isl_qpolynomial_nan(isl_basic_map_get_dim(bmap));
1749 } else if (tok->type == ISL_TOKEN_IDENT) {
1750 int n = v->n;
1751 int pos = vars_pos(v, tok->u.s, -1);
1752 int pow;
1753 if (pos < 0) {
1754 isl_token_free(tok);
1755 return NULL;
1756 }
1757 if (pos >= n) {
1758 vars_drop(v, v->n - n);
1759 isl_stream_error(s, tok, "unknown identifier");
1760 isl_token_free(tok);
1761 return NULL;
1762 }
1763 isl_token_free(tok);
1764 pow = optional_power(s);
1765 qp = isl_qpolynomial_var_pow(isl_basic_map_get_dim(bmap), pos, pow);
1766 } else if (tok->type == '[') {
1767 isl_div *div;
1768 int pow;
1769
1770 isl_stream_push_token(s, tok);
1771 div = read_div(s, isl_basic_map_get_dim(bmap), v);
1772 pow = optional_power(s);
1773 qp = isl_qpolynomial_div_pow(div, pow);
1774 } else if (tok->type == '-') {
1775 struct isl_qpolynomial *qp2;
1776
1777 isl_token_free(tok);
1778 qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap),
1779 s->ctx->negone);
1780 qp2 = read_factor(s, bmap, v);
1781 qp = isl_qpolynomial_mul(qp, qp2);
1782 } else {
1783 isl_stream_error(s, tok, "unexpected isl_token");
1784 isl_stream_push_token(s, tok);
1785 return NULL;
1786 }
1787
1788 if (isl_stream_eat_if_available(s, '*') ||
1789 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
1790 struct isl_qpolynomial *qp2;
1791
1792 qp2 = read_factor(s, bmap, v);
1793 qp = isl_qpolynomial_mul(qp, qp2);
1794 }
1795
1796 return qp;
1797 error:
1798 isl_qpolynomial_free(qp);
1799 return NULL;
1800 }
1801
1802 static __isl_give isl_qpolynomial *read_term(struct isl_stream *s,
1803 __isl_keep isl_basic_map *bmap, struct vars *v)
1804 {
1805 struct isl_token *tok;
1806 struct isl_qpolynomial *qp;
1807
1808 qp = read_factor(s, bmap, v);
1809
1810 for (;;) {
1811 tok = next_token(s);
1812 if (!tok)
1813 return qp;
1814
1815 if (tok->type == '+') {
1816 struct isl_qpolynomial *qp2;
1817
1818 isl_token_free(tok);
1819 qp2 = read_factor(s, bmap, v);
1820 qp = isl_qpolynomial_add(qp, qp2);
1821 } else if (tok->type == '-') {
1822 struct isl_qpolynomial *qp2;
1823
1824 isl_token_free(tok);
1825 qp2 = read_factor(s, bmap, v);
1826 qp = isl_qpolynomial_sub(qp, qp2);
1827 } else if (tok->type == ISL_TOKEN_VALUE &&
1828 isl_int_is_neg(tok->u.v)) {
1829 struct isl_qpolynomial *qp2;
1830
1831 isl_stream_push_token(s, tok);
1832 qp2 = read_factor(s, bmap, v);
1833 qp = isl_qpolynomial_add(qp, qp2);
1834 } else {
1835 isl_stream_push_token(s, tok);
1836 break;
1837 }
1838 }
1839
1840 return qp;
1841 }
1842
1843 static __isl_give isl_map *read_optional_disjuncts(struct isl_stream *s,
1844 __isl_take isl_basic_map *bmap, struct vars *v)
1845 {
1846 struct isl_token *tok;
1847 struct isl_map *map;
1848
1849 tok = isl_stream_next_token(s);
1850 if (!tok) {
1851 isl_stream_error(s, NULL, "unexpected EOF");
1852 goto error;
1853 }
1854 map = isl_map_from_basic_map(isl_basic_map_copy(bmap));
1855 if (tok->type == ':' ||
1856 (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {
1857 isl_token_free(tok);
1858 map = isl_map_intersect(map,
1859 read_disjuncts(s, v, isl_basic_map_copy(bmap)));
1860 } else
1861 isl_stream_push_token(s, tok);
1862
1863 isl_basic_map_free(bmap);
1864
1865 return map;
1866 error:
1867 isl_basic_map_free(bmap);
1868 return NULL;
1869 }
1870
1871 static struct isl_obj obj_read_poly(struct isl_stream *s,
1872 __isl_take isl_basic_map *bmap, struct vars *v, int n)
1873 {
1874 struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
1875 struct isl_pw_qpolynomial *pwqp;
1876 struct isl_qpolynomial *qp;
1877 struct isl_map *map;
1878 struct isl_set *set;
1879
1880 qp = read_term(s, bmap, v);
1881 map = read_optional_disjuncts(s, bmap, v);
1882 set = isl_map_range(map);
1883
1884 pwqp = isl_pw_qpolynomial_alloc(set, qp);
1885
1886 vars_drop(v, v->n - n);
1887
1888 obj.v = pwqp;
1889 return obj;
1890 }
1891
1892 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
1893 __isl_take isl_basic_map *bmap, struct vars *v, int n)
1894 {
1895 struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
1896 isl_qpolynomial *qp;
1897 isl_qpolynomial_fold *fold = NULL;
1898 isl_pw_qpolynomial_fold *pwf;
1899 isl_map *map;
1900 isl_set *set;
1901
1902 if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
1903 return obj_read_poly(s, bmap, v, n);
1904
1905 if (isl_stream_eat(s, '('))
1906 goto error;
1907
1908 qp = read_term(s, bmap, v);
1909 fold = isl_qpolynomial_fold_alloc(isl_fold_max, qp);
1910
1911 while (isl_stream_eat_if_available(s, ',')) {
1912 isl_qpolynomial_fold *fold_i;
1913 qp = read_term(s, bmap, v);
1914 fold_i = isl_qpolynomial_fold_alloc(isl_fold_max, qp);
1915 fold = isl_qpolynomial_fold_fold(fold, fold_i);
1916 }
1917
1918 if (isl_stream_eat(s, ')'))
1919 goto error;
1920
1921 map = read_optional_disjuncts(s, bmap, v);
1922 set = isl_map_range(map);
1923 pwf = isl_pw_qpolynomial_fold_alloc(isl_fold_max, set, fold);
1924
1925 vars_drop(v, v->n - n);
1926
1927 obj.v = pwf;
1928 return obj;
1929 error:
1930 isl_basic_map_free(bmap);
1931 isl_qpolynomial_fold_free(fold);
1932 obj.type = isl_obj_none;
1933 return obj;
1934 }
1935
1936 static int is_rational(struct isl_stream *s)
1937 {
1938 struct isl_token *tok;
1939
1940 tok = isl_stream_next_token(s);
1941 if (!tok)
1942 return 0;
1943 if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) {
1944 isl_token_free(tok);
1945 isl_stream_eat(s, ':');
1946 return 1;
1947 }
1948
1949 isl_stream_push_token(s, tok);
1950
1951 return 0;
1952 }
1953
1954 static struct isl_obj obj_read_body(struct isl_stream *s,
1955 __isl_take isl_basic_map *bmap, struct vars *v)
1956 {
1957 struct isl_map *map = NULL;
1958 struct isl_token *tok;
1959 struct isl_obj obj = { isl_obj_set, NULL };
1960 int n = v->n;
1961
1962 if (is_rational(s))
1963 bmap = isl_basic_map_set_rational(bmap);
1964
1965 if (!next_is_tuple(s))
1966 return obj_read_poly_or_fold(s, bmap, v, n);
1967
1968 bmap = read_tuple(s, bmap, isl_dim_in, v);
1969 if (!bmap)
1970 goto error;
1971 tok = isl_stream_next_token(s);
1972 if (tok && tok->type == ISL_TOKEN_TO) {
1973 obj.type = isl_obj_map;
1974 isl_token_free(tok);
1975 if (!next_is_tuple(s)) {
1976 bmap = isl_basic_map_reverse(bmap);
1977 return obj_read_poly_or_fold(s, bmap, v, n);
1978 }
1979 bmap = read_tuple(s, bmap, isl_dim_out, v);
1980 if (!bmap)
1981 goto error;
1982 } else {
1983 bmap = isl_basic_map_reverse(bmap);
1984 if (tok)
1985 isl_stream_push_token(s, tok);
1986 }
1987
1988 map = read_optional_disjuncts(s, bmap, v);
1989
1990 vars_drop(v, v->n - n);
1991
1992 obj.v = map;
1993 return obj;
1994 error:
1995 isl_basic_map_free(bmap);
1996 obj.type = isl_obj_none;
1997 return obj;
1998 }
1999
2000 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
2001 {
2002 if (obj.type == isl_obj_map) {
2003 obj.v = isl_union_map_from_map(obj.v);
2004 obj.type = isl_obj_union_map;
2005 } else if (obj.type == isl_obj_set) {
2006 obj.v = isl_union_set_from_set(obj.v);
2007 obj.type = isl_obj_union_set;
2008 } else if (obj.type == isl_obj_pw_qpolynomial) {
2009 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2010 obj.type = isl_obj_union_pw_qpolynomial;
2011 } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
2012 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
2013 obj.type = isl_obj_union_pw_qpolynomial_fold;
2014 } else
2015 isl_assert(ctx, 0, goto error);
2016 return obj;
2017 error:
2018 obj.type->free(obj.v);
2019 obj.type = isl_obj_none;
2020 return obj;
2021 }
2022
2023 static struct isl_obj obj_add(struct isl_ctx *ctx,
2024 struct isl_obj obj1, struct isl_obj obj2)
2025 {
2026 if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
2027 obj1 = to_union(ctx, obj1);
2028 if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
2029 obj2 = to_union(ctx, obj2);
2030 if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
2031 obj1 = to_union(ctx, obj1);
2032 if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
2033 obj2 = to_union(ctx, obj2);
2034 if (obj1.type == isl_obj_pw_qpolynomial &&
2035 obj2.type == isl_obj_union_pw_qpolynomial)
2036 obj1 = to_union(ctx, obj1);
2037 if (obj1.type == isl_obj_union_pw_qpolynomial &&
2038 obj2.type == isl_obj_pw_qpolynomial)
2039 obj2 = to_union(ctx, obj2);
2040 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2041 obj2.type == isl_obj_union_pw_qpolynomial_fold)
2042 obj1 = to_union(ctx, obj1);
2043 if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
2044 obj2.type == isl_obj_pw_qpolynomial_fold)
2045 obj2 = to_union(ctx, obj2);
2046 isl_assert(ctx, obj1.type == obj2.type, goto error);
2047 if (obj1.type == isl_obj_map && !isl_map_has_equal_dim(obj1.v, obj2.v)) {
2048 obj1 = to_union(ctx, obj1);
2049 obj2 = to_union(ctx, obj2);
2050 }
2051 if (obj1.type == isl_obj_set && !isl_set_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_pw_qpolynomial &&
2056 !isl_pw_qpolynomial_has_equal_dim(obj1.v, obj2.v)) {
2057 obj1 = to_union(ctx, obj1);
2058 obj2 = to_union(ctx, obj2);
2059 }
2060 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2061 !isl_pw_qpolynomial_fold_has_equal_dim(obj1.v, obj2.v)) {
2062 obj1 = to_union(ctx, obj1);
2063 obj2 = to_union(ctx, obj2);
2064 }
2065 obj1.v = obj1.type->add(obj1.v, obj2.v);
2066 return obj1;
2067 error:
2068 obj1.type->free(obj1.v);
2069 obj2.type->free(obj2.v);
2070 obj1.type = isl_obj_none;
2071 obj1.v = NULL;
2072 return obj1;
2073 }
2074
2075 static struct isl_obj obj_read(struct isl_stream *s, int nparam)
2076 {
2077 isl_basic_map *bmap = NULL;
2078 struct isl_token *tok;
2079 struct vars *v = NULL;
2080 struct isl_obj obj = { isl_obj_set, NULL };
2081
2082 tok = next_token(s);
2083 if (!tok) {
2084 isl_stream_error(s, NULL, "unexpected EOF");
2085 goto error;
2086 }
2087 if (tok->type == ISL_TOKEN_VALUE) {
2088 struct isl_token *tok2;
2089 struct isl_map *map;
2090
2091 tok2 = isl_stream_next_token(s);
2092 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
2093 isl_int_is_neg(tok2->u.v)) {
2094 if (tok2)
2095 isl_stream_push_token(s, tok2);
2096 obj.type = isl_obj_int;
2097 obj.v = isl_int_obj_alloc(s->ctx, tok->u.v);
2098 isl_token_free(tok);
2099 return obj;
2100 }
2101 isl_stream_push_token(s, tok2);
2102 isl_stream_push_token(s, tok);
2103 map = map_read_polylib(s, nparam);
2104 if (!map)
2105 goto error;
2106 if (isl_map_dim(map, isl_dim_in) > 0)
2107 obj.type = isl_obj_map;
2108 obj.v = map;
2109 return obj;
2110 }
2111 v = vars_new(s->ctx);
2112 if (!v) {
2113 isl_stream_push_token(s, tok);
2114 goto error;
2115 }
2116 bmap = isl_basic_map_alloc(s->ctx, 0, 0, 0, 0, 0, 0);
2117 if (tok->type == '[') {
2118 isl_stream_push_token(s, tok);
2119 bmap = read_tuple(s, bmap, isl_dim_param, v);
2120 if (!bmap)
2121 goto error;
2122 if (nparam >= 0)
2123 isl_assert(s->ctx, nparam == v->n, goto error);
2124 tok = isl_stream_next_token(s);
2125 if (!tok || tok->type != ISL_TOKEN_TO) {
2126 isl_stream_error(s, tok, "expecting '->'");
2127 if (tok)
2128 isl_stream_push_token(s, tok);
2129 goto error;
2130 }
2131 isl_token_free(tok);
2132 tok = isl_stream_next_token(s);
2133 } else if (nparam > 0)
2134 bmap = isl_basic_map_add(bmap, isl_dim_param, nparam);
2135 if (!tok || tok->type != '{') {
2136 isl_stream_error(s, tok, "expecting '{'");
2137 if (tok)
2138 isl_stream_push_token(s, tok);
2139 goto error;
2140 }
2141 isl_token_free(tok);
2142
2143 tok = isl_stream_next_token(s);
2144 if (!tok)
2145 ;
2146 else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
2147 isl_token_free(tok);
2148 if (isl_stream_eat(s, '='))
2149 goto error;
2150 bmap = read_tuple(s, bmap, isl_dim_param, v);
2151 if (!bmap)
2152 goto error;
2153 if (nparam >= 0)
2154 isl_assert(s->ctx, nparam == v->n, goto error);
2155 } else if (tok->type == '}') {
2156 obj.type = isl_obj_union_set;
2157 obj.v = isl_union_set_empty(isl_basic_map_get_dim(bmap));
2158 isl_token_free(tok);
2159 goto done;
2160 } else
2161 isl_stream_push_token(s, tok);
2162
2163 for (;;) {
2164 struct isl_obj o;
2165 tok = NULL;
2166 o = obj_read_body(s, isl_basic_map_copy(bmap), v);
2167 if (o.type == isl_obj_none || !o.v)
2168 goto error;
2169 if (!obj.v)
2170 obj = o;
2171 else {
2172 obj = obj_add(s->ctx, obj, o);
2173 if (obj.type == isl_obj_none || !obj.v)
2174 goto error;
2175 }
2176 tok = isl_stream_next_token(s);
2177 if (!tok || tok->type != ';')
2178 break;
2179 isl_token_free(tok);
2180 if (isl_stream_next_token_is(s, '}')) {
2181 tok = isl_stream_next_token(s);
2182 break;
2183 }
2184 }
2185
2186 if (tok && tok->type == '}') {
2187 isl_token_free(tok);
2188 } else {
2189 isl_stream_error(s, tok, "unexpected isl_token");
2190 if (tok)
2191 isl_token_free(tok);
2192 goto error;
2193 }
2194 done:
2195 vars_free(v);
2196 isl_basic_map_free(bmap);
2197
2198 return obj;
2199 error:
2200 isl_basic_map_free(bmap);
2201 obj.type->free(obj.v);
2202 if (v)
2203 vars_free(v);
2204 obj.v = NULL;
2205 return obj;
2206 }
2207
2208 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
2209 {
2210 return obj_read(s, -1);
2211 }
2212
2213 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s, int nparam)
2214 {
2215 struct isl_obj obj;
2216
2217 obj = obj_read(s, nparam);
2218 if (obj.v)
2219 isl_assert(s->ctx, obj.type == isl_obj_map ||
2220 obj.type == isl_obj_set, goto error);
2221
2222 return obj.v;
2223 error:
2224 obj.type->free(obj.v);
2225 return NULL;
2226 }
2227
2228 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s, int nparam)
2229 {
2230 struct isl_obj obj;
2231
2232 obj = obj_read(s, nparam);
2233 if (obj.v)
2234 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2235
2236 return obj.v;
2237 error:
2238 obj.type->free(obj.v);
2239 return NULL;
2240 }
2241
2242 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2243 {
2244 struct isl_obj obj;
2245
2246 obj = obj_read(s, -1);
2247 if (obj.type == isl_obj_map) {
2248 obj.type = isl_obj_union_map;
2249 obj.v = isl_union_map_from_map(obj.v);
2250 }
2251 if (obj.type == isl_obj_set) {
2252 obj.type = isl_obj_union_set;
2253 obj.v = isl_union_set_from_set(obj.v);
2254 }
2255 if (obj.v)
2256 isl_assert(s->ctx, obj.type == isl_obj_union_map ||
2257 obj.type == isl_obj_union_set, goto error);
2258
2259 return obj.v;
2260 error:
2261 obj.type->free(obj.v);
2262 return NULL;
2263 }
2264
2265 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2266 {
2267 struct isl_obj obj;
2268
2269 obj = obj_read(s, -1);
2270 if (obj.type == isl_obj_set) {
2271 obj.type = isl_obj_union_set;
2272 obj.v = isl_union_set_from_set(obj.v);
2273 }
2274 if (obj.v)
2275 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2276
2277 return obj.v;
2278 error:
2279 obj.type->free(obj.v);
2280 return NULL;
2281 }
2282
2283 static struct isl_basic_map *basic_map_read(struct isl_stream *s, int nparam)
2284 {
2285 struct isl_obj obj;
2286 struct isl_map *map;
2287 struct isl_basic_map *bmap;
2288
2289 obj = obj_read(s, nparam);
2290 map = obj.v;
2291 if (!map)
2292 return NULL;
2293
2294 isl_assert(map->ctx, map->n <= 1, goto error);
2295
2296 if (map->n == 0)
2297 bmap = isl_basic_map_empty_like_map(map);
2298 else
2299 bmap = isl_basic_map_copy(map->p[0]);
2300
2301 isl_map_free(map);
2302
2303 return bmap;
2304 error:
2305 isl_map_free(map);
2306 return NULL;
2307 }
2308
2309 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2310 FILE *input, int nparam)
2311 {
2312 struct isl_basic_map *bmap;
2313 struct isl_stream *s = isl_stream_new_file(ctx, input);
2314 if (!s)
2315 return NULL;
2316 bmap = basic_map_read(s, nparam);
2317 isl_stream_free(s);
2318 return bmap;
2319 }
2320
2321 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2322 FILE *input, int nparam)
2323 {
2324 struct isl_basic_map *bmap;
2325 bmap = isl_basic_map_read_from_file(ctx, input, nparam);
2326 if (!bmap)
2327 return NULL;
2328 isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
2329 return (struct isl_basic_set *)bmap;
2330 error:
2331 isl_basic_map_free(bmap);
2332 return NULL;
2333 }
2334
2335 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2336 const char *str, int nparam)
2337 {
2338 struct isl_basic_map *bmap;
2339 struct isl_stream *s = isl_stream_new_str(ctx, str);
2340 if (!s)
2341 return NULL;
2342 bmap = basic_map_read(s, nparam);
2343 isl_stream_free(s);
2344 return bmap;
2345 }
2346
2347 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2348 const char *str, int nparam)
2349 {
2350 struct isl_basic_map *bmap;
2351 bmap = isl_basic_map_read_from_str(ctx, str, nparam);
2352 if (!bmap)
2353 return NULL;
2354 isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
2355 return (struct isl_basic_set *)bmap;
2356 error:
2357 isl_basic_map_free(bmap);
2358 return NULL;
2359 }
2360
2361 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2362 FILE *input, int nparam)
2363 {
2364 struct isl_map *map;
2365 struct isl_stream *s = isl_stream_new_file(ctx, input);
2366 if (!s)
2367 return NULL;
2368 map = isl_stream_read_map(s, nparam);
2369 isl_stream_free(s);
2370 return map;
2371 }
2372
2373 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2374 const char *str, int nparam)
2375 {
2376 struct isl_map *map;
2377 struct isl_stream *s = isl_stream_new_str(ctx, str);
2378 if (!s)
2379 return NULL;
2380 map = isl_stream_read_map(s, nparam);
2381 isl_stream_free(s);
2382 return map;
2383 }
2384
2385 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2386 FILE *input, int nparam)
2387 {
2388 struct isl_map *map;
2389 map = isl_map_read_from_file(ctx, input, nparam);
2390 if (!map)
2391 return NULL;
2392 isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
2393 return (struct isl_set *)map;
2394 error:
2395 isl_map_free(map);
2396 return NULL;
2397 }
2398
2399 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2400 const char *str, int nparam)
2401 {
2402 struct isl_map *map;
2403 map = isl_map_read_from_str(ctx, str, nparam);
2404 if (!map)
2405 return NULL;
2406 isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
2407 return (struct isl_set *)map;
2408 error:
2409 isl_map_free(map);
2410 return NULL;
2411 }
2412
2413 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2414 FILE *input)
2415 {
2416 isl_union_map *umap;
2417 struct isl_stream *s = isl_stream_new_file(ctx, input);
2418 if (!s)
2419 return NULL;
2420 umap = isl_stream_read_union_map(s);
2421 isl_stream_free(s);
2422 return umap;
2423 }
2424
2425 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2426 const char *str)
2427 {
2428 isl_union_map *umap;
2429 struct isl_stream *s = isl_stream_new_str(ctx, str);
2430 if (!s)
2431 return NULL;
2432 umap = isl_stream_read_union_map(s);
2433 isl_stream_free(s);
2434 return umap;
2435 }
2436
2437 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2438 FILE *input)
2439 {
2440 isl_union_set *uset;
2441 struct isl_stream *s = isl_stream_new_file(ctx, input);
2442 if (!s)
2443 return NULL;
2444 uset = isl_stream_read_union_set(s);
2445 isl_stream_free(s);
2446 return uset;
2447 }
2448
2449 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2450 const char *str)
2451 {
2452 isl_union_set *uset;
2453 struct isl_stream *s = isl_stream_new_str(ctx, str);
2454 if (!s)
2455 return NULL;
2456 uset = isl_stream_read_union_set(s);
2457 isl_stream_free(s);
2458 return uset;
2459 }
2460
2461 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2462 {
2463 struct isl_vec *vec = NULL;
2464 struct isl_token *tok;
2465 unsigned size;
2466 int j;
2467
2468 tok = isl_stream_next_token(s);
2469 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2470 isl_stream_error(s, tok, "expecting vector length");
2471 goto error;
2472 }
2473
2474 size = isl_int_get_si(tok->u.v);
2475 isl_token_free(tok);
2476
2477 vec = isl_vec_alloc(s->ctx, size);
2478
2479 for (j = 0; j < size; ++j) {
2480 tok = isl_stream_next_token(s);
2481 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2482 isl_stream_error(s, tok, "expecting constant value");
2483 goto error;
2484 }
2485 isl_int_set(vec->el[j], tok->u.v);
2486 isl_token_free(tok);
2487 }
2488
2489 return vec;
2490 error:
2491 isl_token_free(tok);
2492 isl_vec_free(vec);
2493 return NULL;
2494 }
2495
2496 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2497 {
2498 return isl_vec_read_polylib(s);
2499 }
2500
2501 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2502 {
2503 isl_vec *v;
2504 struct isl_stream *s = isl_stream_new_file(ctx, input);
2505 if (!s)
2506 return NULL;
2507 v = vec_read(s);
2508 isl_stream_free(s);
2509 return v;
2510 }
2511
2512 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2513 struct isl_stream *s)
2514 {
2515 struct isl_obj obj;
2516
2517 obj = obj_read(s, -1);
2518 if (obj.v)
2519 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2520 goto error);
2521
2522 return obj.v;
2523 error:
2524 obj.type->free(obj.v);
2525 return NULL;
2526 }
2527
2528 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2529 const char *str)
2530 {
2531 isl_pw_qpolynomial *pwqp;
2532 struct isl_stream *s = isl_stream_new_str(ctx, str);
2533 if (!s)
2534 return NULL;
2535 pwqp = isl_stream_read_pw_qpolynomial(s);
2536 isl_stream_free(s);
2537 return pwqp;
2538 }
Integer set library