?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_stream_read_pw_qpolynomial: accept powers on compound expressions
[isl.git] / isl_input.c
blobec25b7fc4a4a76ba4ad814c745a63c33332a7706
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 <strings.h>
17 #include <isl/set.h>
18 #include <isl/seq.h>
19 #include <isl/div.h>
20 #include <isl/stream.h>
21 #include "isl_map_private.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 struct variable *next;
32 };
33
34 struct vars {
35 struct isl_ctx *ctx;
36 int n;
37 struct variable *v;
38 };
39
40 static struct vars *vars_new(struct isl_ctx *ctx)
41 {
42 struct vars *v;
43 v = isl_alloc_type(ctx, struct vars);
44 if (!v)
45 return NULL;
46 v->ctx = ctx;
47 v->n = 0;
48 v->v = NULL;
49 return v;
50 }
51
52 static void variable_free(struct variable *var)
53 {
54 while (var) {
55 struct variable *next = var->next;
56 isl_vec_free(var->def);
57 free(var->name);
58 free(var);
59 var = next;
60 }
61 }
62
63 static void vars_free(struct vars *v)
64 {
65 if (!v)
66 return;
67 variable_free(v->v);
68 free(v);
69 }
70
71 static void vars_drop(struct vars *v, int n)
72 {
73 struct variable *var;
74
75 if (!v || !v->v)
76 return;
77
78 v->n -= n;
79
80 var = v->v;
81 while (--n >= 0) {
82 struct variable *next = var->next;
83 isl_vec_free(var->def);
84 free(var->name);
85 free(var);
86 var = next;
87 }
88 v->v = var;
89 }
90
91 static struct variable *variable_new(struct vars *v, const char *name, int len,
92 int pos)
93 {
94 struct variable *var;
95 var = isl_alloc_type(v->ctx, struct variable);
96 if (!var)
97 goto error;
98 var->name = strdup(name);
99 var->name[len] = '\0';
100 var->pos = pos;
101 var->def = NULL;
102 var->next = v->v;
103 return var;
104 error:
105 variable_free(v->v);
106 return NULL;
107 }
108
109 static int vars_pos(struct vars *v, const char *s, int len)
110 {
111 int pos;
112 struct variable *q;
113
114 if (len == -1)
115 len = strlen(s);
116 for (q = v->v; q; q = q->next) {
117 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
118 break;
119 }
120 if (q)
121 pos = q->pos;
122 else {
123 pos = v->n;
124 v->v = variable_new(v, s, len, v->n);
125 if (!v->v)
126 return -1;
127 v->n++;
128 }
129 return pos;
130 }
131
132 static int vars_add_anon(struct vars *v)
133 {
134 v->v = variable_new(v, "", 0, v->n);
135
136 if (!v->v)
137 return -1;
138 v->n++;
139
140 return 0;
141 }
142
143 static __isl_give isl_basic_map *set_name(__isl_take isl_basic_map *bmap,
144 enum isl_dim_type type, unsigned pos, char *name)
145 {
146 char *prime;
147
148 if (!bmap)
149 return NULL;
150 if (!name)
151 return bmap;
152
153 prime = strchr(name, '\'');
154 if (prime)
155 *prime = '\0';
156 bmap = isl_basic_map_set_dim_name(bmap, type, pos, name);
157 if (prime)
158 *prime = '\'';
159
160 return bmap;
161 }
162
163 static int accept_cst_factor(struct isl_stream *s, isl_int *f)
164 {
165 struct isl_token *tok;
166
167 tok = isl_stream_next_token(s);
168 if (!tok || tok->type != ISL_TOKEN_VALUE) {
169 isl_stream_error(s, tok, "expecting constant value");
170 goto error;
171 }
172
173 isl_int_mul(*f, *f, tok->u.v);
174
175 isl_token_free(tok);
176
177 if (isl_stream_eat_if_available(s, '*'))
178 return accept_cst_factor(s, f);
179
180 return 0;
181 error:
182 isl_token_free(tok);
183 return -1;
184 }
185
186 static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v);
187 static int read_div_definition(struct isl_stream *s, struct vars *v);
188
189 static __isl_give isl_vec *accept_affine_factor(struct isl_stream *s,
190 struct vars *v)
191 {
192 struct isl_token *tok = NULL;
193 isl_vec *aff = NULL;
194
195 tok = isl_stream_next_token(s);
196 if (!tok) {
197 isl_stream_error(s, NULL, "unexpected EOF");
198 goto error;
199 }
200 if (tok->type == ISL_TOKEN_IDENT) {
201 int n = v->n;
202 int pos = vars_pos(v, tok->u.s, -1);
203 if (pos < 0)
204 goto error;
205 if (pos >= n) {
206 isl_stream_error(s, tok, "unknown identifier");
207 goto error;
208 }
209
210 aff = isl_vec_alloc(v->ctx, 1 + v->n);
211 if (!aff)
212 goto error;
213 isl_seq_clr(aff->el, aff->size);
214 isl_int_set_si(aff->el[1 + pos], 1);
215 isl_token_free(tok);
216 } else if (tok->type == ISL_TOKEN_VALUE) {
217 if (isl_stream_eat_if_available(s, '*')) {
218 aff = accept_affine_factor(s, v);
219 aff = isl_vec_scale(aff, tok->u.v);
220 } else {
221 aff = isl_vec_alloc(v->ctx, 1 + v->n);
222 if (!aff)
223 goto error;
224 isl_seq_clr(aff->el, aff->size);
225 isl_int_set(aff->el[0], tok->u.v);
226 }
227 isl_token_free(tok);
228 } else if (tok->type == '(') {
229 isl_token_free(tok);
230 tok = NULL;
231 aff = accept_affine(s, v);
232 if (!aff)
233 goto error;
234 if (isl_stream_eat(s, ')'))
235 goto error;
236 } else if (tok->type == '[') {
237 if (vars_add_anon(v) < 0)
238 goto error;
239 aff = isl_vec_alloc(v->ctx, 1 + v->n);
240 if (!aff)
241 goto error;
242 isl_seq_clr(aff->el, aff->size);
243 isl_int_set_si(aff->el[1 + v->n - 1], 1);
244 isl_stream_push_token(s, tok);
245 tok = NULL;
246 if (read_div_definition(s, v) < 0)
247 goto error;
248 } else {
249 isl_stream_error(s, tok, "expecting factor");
250 goto error;
251 }
252 if (isl_stream_eat_if_available(s, '*')) {
253 isl_int f;
254 isl_int_init(f);
255 isl_int_set_si(f, 1);
256 if (accept_cst_factor(s, &f) < 0) {
257 isl_int_clear(f);
258 goto error;
259 }
260 aff = isl_vec_scale(aff, f);
261 isl_int_clear(f);
262 }
263
264 return aff;
265 error:
266 isl_token_free(tok);
267 isl_vec_free(aff);
268 return NULL;
269 }
270
271 static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v)
272 {
273 struct isl_token *tok = NULL;
274 struct isl_vec *aff;
275 int sign = 1;
276
277 aff = isl_vec_alloc(v->ctx, 1 + v->n);
278 if (!aff)
279 return NULL;
280 isl_seq_clr(aff->el, aff->size);
281
282 for (;;) {
283 tok = isl_stream_next_token(s);
284 if (!tok) {
285 isl_stream_error(s, NULL, "unexpected EOF");
286 goto error;
287 }
288 if (tok->type == '-') {
289 sign = -sign;
290 isl_token_free(tok);
291 continue;
292 }
293 if (tok->type == '(' || tok->type == '[' ||
294 tok->type == ISL_TOKEN_IDENT) {
295 isl_vec *aff2;
296 isl_stream_push_token(s, tok);
297 tok = NULL;
298 aff2 = accept_affine_factor(s, v);
299 if (sign < 0)
300 aff2 = isl_vec_scale(aff2, s->ctx->negone);
301 aff = isl_vec_zero_extend(aff, 1 + v->n);
302 aff = isl_vec_add(aff, aff2);
303 if (!aff)
304 goto error;
305 sign = 1;
306 } else if (tok->type == ISL_TOKEN_VALUE) {
307 if (sign < 0)
308 isl_int_neg(tok->u.v, tok->u.v);
309 if (isl_stream_eat_if_available(s, '*') ||
310 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
311 isl_vec *aff2;
312 aff2 = accept_affine_factor(s, v);
313 aff2 = isl_vec_scale(aff2, tok->u.v);
314 aff = isl_vec_zero_extend(aff, 1 + v->n);
315 aff = isl_vec_add(aff, aff2);
316 if (!aff)
317 goto error;
318 } else {
319 isl_int_add(aff->el[0], aff->el[0], tok->u.v);
320 }
321 sign = 1;
322 } else {
323 isl_stream_error(s, tok, "unexpected isl_token");
324 isl_stream_push_token(s, tok);
325 isl_vec_free(aff);
326 return NULL;
327 }
328 isl_token_free(tok);
329
330 tok = isl_stream_next_token(s);
331 if (tok && tok->type == '-') {
332 sign = -sign;
333 isl_token_free(tok);
334 } else if (tok && tok->type == '+') {
335 /* nothing */
336 isl_token_free(tok);
337 } else if (tok && tok->type == ISL_TOKEN_VALUE &&
338 isl_int_is_neg(tok->u.v)) {
339 isl_stream_push_token(s, tok);
340 } else {
341 if (tok)
342 isl_stream_push_token(s, tok);
343 break;
344 }
345 }
346
347 return aff;
348 error:
349 isl_token_free(tok);
350 isl_vec_free(aff);
351 return NULL;
352 }
353
354 /* Add any variables in the variable list "v" that are not already in "bmap"
355 * as existentially quantified variables in "bmap".
356 */
357 static __isl_give isl_basic_map *add_divs(__isl_take isl_basic_map *bmap,
358 struct vars *v)
359 {
360 int i;
361 int extra;
362 struct variable *var;
363
364 extra = v->n - isl_basic_map_total_dim(bmap);
365
366 if (extra == 0)
367 return bmap;
368
369 bmap = isl_basic_map_extend_dim(bmap, isl_basic_map_get_dim(bmap),
370 extra, 0, 2 * extra);
371
372 for (i = 0; i < extra; ++i)
373 if (isl_basic_map_alloc_div(bmap) < 0)
374 goto error;
375
376 for (i = 0, var = v->v; i < extra; ++i, var = var->next) {
377 int k = bmap->n_div - 1 - i;
378
379 isl_seq_cpy(bmap->div[k], var->def->el, var->def->size);
380 isl_seq_clr(bmap->div[k] + var->def->size,
381 2 + v->n - var->def->size);
382
383 if (isl_basic_map_add_div_constraints(bmap, k) < 0)
384 goto error;
385 }
386
387 return bmap;
388 error:
389 isl_basic_map_free(bmap);
390 return NULL;
391 }
392
393 static __isl_give isl_basic_map *read_var_def(struct isl_stream *s,
394 __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
395 {
396 isl_dim *dim;
397 isl_basic_map *def = NULL;
398 struct isl_vec *vec;
399 int k;
400 int n;
401
402 if (vars_add_anon(v) < 0)
403 goto error;
404 n = v->n;
405
406 vec = accept_affine(s, v);
407 if (!vec)
408 goto error;
409
410 dim = isl_basic_map_get_dim(bmap);
411 def = isl_basic_map_universe(dim);
412 def = add_divs(def, v);
413 def = isl_basic_map_extend_constraints(def, 1, 0);
414 k = isl_basic_map_alloc_equality(def);
415 if (k >= 0) {
416 isl_seq_cpy(def->eq[k], vec->el, vec->size);
417 isl_int_set_si(def->eq[k][1 + n - 1], -1);
418 }
419 isl_vec_free(vec);
420 if (k < 0)
421 goto error;
422
423 vars_drop(v, v->n - n);
424
425 def = isl_basic_map_simplify(def);
426 def = isl_basic_map_finalize(def);
427 bmap = isl_basic_map_intersect(bmap, def);
428 return bmap;
429 error:
430 isl_basic_map_free(bmap);
431 isl_basic_map_free(def);
432 return NULL;
433 }
434
435 static __isl_give isl_basic_map *read_var_list(struct isl_stream *s,
436 __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
437 {
438 int i = 0;
439 struct isl_token *tok;
440
441 while ((tok = isl_stream_next_token(s)) != NULL) {
442 int new_name = 0;
443
444 if (tok->type == ISL_TOKEN_IDENT) {
445 int n = v->n;
446 int p = vars_pos(v, tok->u.s, -1);
447 if (p < 0)
448 goto error;
449 new_name = p >= n;
450 }
451
452 if (new_name) {
453 bmap = isl_basic_map_add(bmap, type, 1);
454 bmap = set_name(bmap, type, i, v->v->name);
455 isl_token_free(tok);
456 } else if (tok->type == ISL_TOKEN_IDENT ||
457 tok->type == ISL_TOKEN_VALUE ||
458 tok->type == '-' ||
459 tok->type == '(') {
460 if (type == isl_dim_param) {
461 isl_stream_error(s, tok,
462 "expecting unique identifier");
463 goto error;
464 }
465 isl_stream_push_token(s, tok);
466 tok = NULL;
467 bmap = isl_basic_map_add(bmap, type, 1);
468 bmap = read_var_def(s, bmap, type, v);
469 } else
470 break;
471
472 tok = isl_stream_next_token(s);
473 if (!tok || tok->type != ',')
474 break;
475
476 isl_token_free(tok);
477 i++;
478 }
479 if (tok)
480 isl_stream_push_token(s, tok);
481
482 return bmap;
483 error:
484 isl_token_free(tok);
485 isl_basic_map_free(bmap);
486 return NULL;
487 }
488
489 static __isl_give isl_mat *accept_affine_list(struct isl_stream *s,
490 struct vars *v)
491 {
492 struct isl_vec *vec;
493 struct isl_mat *mat;
494 struct isl_token *tok = NULL;
495
496 vec = accept_affine(s, v);
497 mat = isl_mat_from_row_vec(vec);
498 if (!mat)
499 return NULL;
500
501 for (;;) {
502 tok = isl_stream_next_token(s);
503 if (!tok) {
504 isl_stream_error(s, NULL, "unexpected EOF");
505 goto error;
506 }
507 if (tok->type != ',') {
508 isl_stream_push_token(s, tok);
509 break;
510 }
511 isl_token_free(tok);
512
513 vec = accept_affine(s, v);
514 mat = isl_mat_add_zero_cols(mat, 1 + v->n - isl_mat_cols(mat));
515 mat = isl_mat_vec_concat(mat, vec);
516 if (!mat)
517 return NULL;
518 }
519
520 return mat;
521 error:
522 isl_mat_free(mat);
523 return NULL;
524 }
525
526 static int read_div_definition(struct isl_stream *s, struct vars *v)
527 {
528 struct isl_token *tok;
529 int seen_paren = 0;
530 struct isl_vec *aff;
531 struct variable *var;
532
533 if (isl_stream_eat(s, '['))
534 return -1;
535
536 tok = isl_stream_next_token(s);
537 if (!tok)
538 return -1;
539 if (tok->type == '(') {
540 seen_paren = 1;
541 isl_token_free(tok);
542 } else
543 isl_stream_push_token(s, tok);
544
545 var = v->v;
546
547 aff = accept_affine(s, v);
548 if (!aff)
549 return -1;
550
551 var->def = isl_vec_alloc(s->ctx, 2 + v->n);
552 if (!var->def) {
553 isl_vec_free(aff);
554 return -1;
555 }
556
557 isl_seq_cpy(var->def->el + 1, aff->el, aff->size);
558
559 isl_vec_free(aff);
560
561 if (seen_paren && isl_stream_eat(s, ')'))
562 return -1;
563 if (isl_stream_eat(s, '/'))
564 return -1;
565
566 tok = isl_stream_next_token(s);
567 if (!tok)
568 return -1;
569 if (tok->type != ISL_TOKEN_VALUE) {
570 isl_stream_error(s, tok, "expected denominator");
571 isl_stream_push_token(s, tok);
572 return -1;
573 }
574 isl_int_set(var->def->el[0], tok->u.v);
575 isl_token_free(tok);
576
577 if (isl_stream_eat(s, ']'))
578 return -1;
579
580 return 0;
581 }
582
583 static struct isl_basic_map *add_div_definition(struct isl_stream *s,
584 struct vars *v, struct isl_basic_map *bmap, int k)
585 {
586 struct variable *var = v->v;
587
588 if (read_div_definition(s, v) < 0)
589 goto error;
590
591 isl_seq_cpy(bmap->div[k], var->def->el, 2 + v->n);
592
593 if (isl_basic_map_add_div_constraints(bmap, k) < 0)
594 goto error;
595
596 return bmap;
597 error:
598 isl_basic_map_free(bmap);
599 return NULL;
600 }
601
602 static struct isl_basic_map *read_defined_var_list(struct isl_stream *s,
603 struct vars *v, struct isl_basic_map *bmap)
604 {
605 struct isl_token *tok;
606
607 while ((tok = isl_stream_next_token(s)) != NULL) {
608 int k;
609 int p;
610 int n = v->n;
611 unsigned total = isl_basic_map_total_dim(bmap);
612
613 if (tok->type != ISL_TOKEN_IDENT)
614 break;
615
616 p = vars_pos(v, tok->u.s, -1);
617 if (p < 0)
618 goto error;
619 if (p < n) {
620 isl_stream_error(s, tok, "expecting unique identifier");
621 goto error;
622 }
623
624 bmap = isl_basic_map_cow(bmap);
625 bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
626 1, 0, 2);
627
628 if ((k = isl_basic_map_alloc_div(bmap)) < 0)
629 goto error;
630 isl_seq_clr(bmap->div[k], 1 + 1 + total);
631
632 isl_token_free(tok);
633 tok = isl_stream_next_token(s);
634 if (tok && tok->type == '=') {
635 isl_token_free(tok);
636 bmap = add_div_definition(s, v, bmap, k);
637 tok = isl_stream_next_token(s);
638 }
639
640 if (!tok || tok->type != ',')
641 break;
642
643 isl_token_free(tok);
644 }
645 if (tok)
646 isl_stream_push_token(s, tok);
647
648 return bmap;
649 error:
650 isl_token_free(tok);
651 isl_basic_map_free(bmap);
652 return NULL;
653 }
654
655 static int next_is_tuple(struct isl_stream *s)
656 {
657 struct isl_token *tok;
658 int is_tuple;
659
660 tok = isl_stream_next_token(s);
661 if (!tok)
662 return 0;
663 if (tok->type == '[') {
664 isl_stream_push_token(s, tok);
665 return 1;
666 }
667 if (tok->type != ISL_TOKEN_IDENT) {
668 isl_stream_push_token(s, tok);
669 return 0;
670 }
671
672 is_tuple = isl_stream_next_token_is(s, '[');
673
674 isl_stream_push_token(s, tok);
675
676 return is_tuple;
677 }
678
679 static __isl_give isl_basic_map *read_tuple(struct isl_stream *s,
680 __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v);
681
682 static __isl_give isl_basic_map *read_nested_tuple(struct isl_stream *s,
683 __isl_take isl_basic_map *bmap, struct vars *v)
684 {
685 bmap = read_tuple(s, bmap, isl_dim_in, v);
686 if (isl_stream_eat(s, ISL_TOKEN_TO))
687 goto error;
688 bmap = read_tuple(s, bmap, isl_dim_out, v);
689 bmap = isl_basic_map_from_range(isl_basic_map_wrap(bmap));
690 return bmap;
691 error:
692 isl_basic_map_free(bmap);
693 return NULL;
694 }
695
696 static __isl_give isl_basic_map *read_tuple(struct isl_stream *s,
697 __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
698 {
699 struct isl_token *tok;
700 char *name = NULL;
701
702 tok = isl_stream_next_token(s);
703 if (tok && tok->type == ISL_TOKEN_IDENT) {
704 name = strdup(tok->u.s);
705 if (!name)
706 goto error;
707 isl_token_free(tok);
708 tok = isl_stream_next_token(s);
709 }
710 if (!tok || tok->type != '[') {
711 isl_stream_error(s, tok, "expecting '['");
712 goto error;
713 }
714 isl_token_free(tok);
715 if (type != isl_dim_param && next_is_tuple(s)) {
716 isl_dim *dim = isl_basic_map_get_dim(bmap);
717 int nparam = isl_dim_size(dim, isl_dim_param);
718 int n_in = isl_dim_size(dim, isl_dim_in);
719 isl_basic_map *nested;
720 if (type == isl_dim_out)
721 dim = isl_dim_move(dim, isl_dim_param, nparam,
722 isl_dim_in, 0, n_in);
723 nested = isl_basic_map_alloc_dim(dim, 0, 0, 0);
724 nested = read_nested_tuple(s, nested, v);
725 if (type == isl_dim_in) {
726 nested = isl_basic_map_reverse(nested);
727 bmap = isl_basic_map_intersect(nested, bmap);
728 } else {
729 isl_basic_set *bset;
730 dim = isl_dim_range(isl_basic_map_get_dim(nested));
731 dim = isl_dim_drop(dim, isl_dim_param, nparam, n_in);
732 dim = isl_dim_join(isl_basic_map_get_dim(bmap), dim);
733 bset = isl_basic_map_domain(bmap);
734 nested = isl_basic_map_reset_dim(nested, dim);
735 bmap = isl_basic_map_intersect_domain(nested, bset);
736 }
737 } else
738 bmap = read_var_list(s, bmap, type, v);
739 tok = isl_stream_next_token(s);
740 if (!tok || tok->type != ']') {
741 isl_stream_error(s, tok, "expecting ']'");
742 goto error;
743 }
744 isl_token_free(tok);
745
746 if (name) {
747 bmap = isl_basic_map_set_tuple_name(bmap, type, name);
748 free(name);
749 }
750
751 return bmap;
752 error:
753 if (tok)
754 isl_token_free(tok);
755 isl_basic_map_free(bmap);
756 return NULL;
757 }
758
759 static struct isl_basic_map *add_constraints(struct isl_stream *s,
760 struct vars *v, struct isl_basic_map *bmap);
761
762 static struct isl_basic_map *add_exists(struct isl_stream *s,
763 struct vars *v, struct isl_basic_map *bmap)
764 {
765 struct isl_token *tok;
766 int n = v->n;
767 int extra;
768 int seen_paren = 0;
769 int i;
770 unsigned total;
771
772 tok = isl_stream_next_token(s);
773 if (!tok)
774 goto error;
775 if (tok->type == '(') {
776 seen_paren = 1;
777 isl_token_free(tok);
778 } else
779 isl_stream_push_token(s, tok);
780
781 bmap = read_defined_var_list(s, v, bmap);
782 if (!bmap)
783 goto error;
784
785 if (isl_stream_eat(s, ':'))
786 goto error;
787 bmap = add_constraints(s, v, bmap);
788 if (seen_paren && isl_stream_eat(s, ')'))
789 goto error;
790 return bmap;
791 error:
792 isl_basic_map_free(bmap);
793 return NULL;
794 }
795
796 static __isl_give isl_basic_map *construct_constraint(
797 __isl_take isl_basic_map *bmap, enum isl_token_type type,
798 isl_int *left, isl_int *right)
799 {
800 int k;
801 unsigned len;
802 struct isl_ctx *ctx;
803
804 if (!bmap)
805 return NULL;
806 len = 1 + isl_basic_map_total_dim(bmap);
807 ctx = bmap->ctx;
808
809 k = isl_basic_map_alloc_inequality(bmap);
810 if (k < 0)
811 goto error;
812 if (type == ISL_TOKEN_LE)
813 isl_seq_combine(bmap->ineq[k], ctx->negone, left,
814 ctx->one, right,
815 len);
816 else if (type == ISL_TOKEN_GE)
817 isl_seq_combine(bmap->ineq[k], ctx->one, left,
818 ctx->negone, right,
819 len);
820 else if (type == ISL_TOKEN_LT) {
821 isl_seq_combine(bmap->ineq[k], ctx->negone, left,
822 ctx->one, right,
823 len);
824 isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1);
825 } else if (type == ISL_TOKEN_GT) {
826 isl_seq_combine(bmap->ineq[k], ctx->one, left,
827 ctx->negone, right,
828 len);
829 isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1);
830 } else {
831 isl_seq_combine(bmap->ineq[k], ctx->one, left,
832 ctx->negone, right,
833 len);
834 isl_basic_map_inequality_to_equality(bmap, k);
835 }
836
837 return bmap;
838 error:
839 isl_basic_map_free(bmap);
840 return NULL;
841 }
842
843 static int is_comparator(struct isl_token *tok)
844 {
845 if (!tok)
846 return 0;
847
848 switch (tok->type) {
849 case ISL_TOKEN_LT:
850 case ISL_TOKEN_GT:
851 case ISL_TOKEN_LE:
852 case ISL_TOKEN_GE:
853 case '=':
854 return 1;
855 default:
856 return 0;
857 }
858 }
859
860 static struct isl_basic_map *add_constraint(struct isl_stream *s,
861 struct vars *v, struct isl_basic_map *bmap)
862 {
863 int i, j;
864 struct isl_token *tok = NULL;
865 struct isl_mat *aff1 = NULL, *aff2 = NULL;
866
867 tok = isl_stream_next_token(s);
868 if (!tok)
869 goto error;
870 if (tok->type == ISL_TOKEN_EXISTS) {
871 isl_token_free(tok);
872 return add_exists(s, v, bmap);
873 }
874 isl_stream_push_token(s, tok);
875 tok = NULL;
876
877 bmap = isl_basic_map_cow(bmap);
878
879 aff1 = accept_affine_list(s, v);
880 if (!aff1)
881 goto error;
882 tok = isl_stream_next_token(s);
883 if (!is_comparator(tok)) {
884 isl_stream_error(s, tok, "missing operator");
885 if (tok)
886 isl_stream_push_token(s, tok);
887 tok = NULL;
888 goto error;
889 }
890 for (;;) {
891 aff2 = accept_affine_list(s, v);
892 if (!aff2)
893 goto error;
894
895 aff1 = isl_mat_add_zero_cols(aff1, aff2->n_col - aff1->n_col);
896 if (!aff1)
897 goto error;
898 bmap = add_divs(bmap, v);
899 bmap = isl_basic_map_extend_constraints(bmap, 0,
900 aff1->n_row * aff2->n_row);
901 for (i = 0; i < aff1->n_row; ++i)
902 for (j = 0; j < aff2->n_row; ++j)
903 bmap = construct_constraint(bmap, tok->type,
904 aff1->row[i], aff2->row[j]);
905 isl_token_free(tok);
906 isl_mat_free(aff1);
907 aff1 = aff2;
908
909 tok = isl_stream_next_token(s);
910 if (!is_comparator(tok)) {
911 if (tok)
912 isl_stream_push_token(s, tok);
913 break;
914 }
915 }
916 isl_mat_free(aff1);
917
918 return bmap;
919 error:
920 if (tok)
921 isl_token_free(tok);
922 isl_mat_free(aff1);
923 isl_mat_free(aff2);
924 isl_basic_map_free(bmap);
925 return NULL;
926 }
927
928 static struct isl_basic_map *add_constraints(struct isl_stream *s,
929 struct vars *v, struct isl_basic_map *bmap)
930 {
931 struct isl_token *tok;
932
933 for (;;) {
934 bmap = add_constraint(s, v, bmap);
935 if (!bmap)
936 return NULL;
937 tok = isl_stream_next_token(s);
938 if (!tok) {
939 isl_stream_error(s, NULL, "unexpected EOF");
940 goto error;
941 }
942 if (tok->type != ISL_TOKEN_AND)
943 break;
944 isl_token_free(tok);
945 }
946 isl_stream_push_token(s, tok);
947
948 return bmap;
949 error:
950 if (tok)
951 isl_token_free(tok);
952 isl_basic_map_free(bmap);
953 return NULL;
954 }
955
956 static struct isl_basic_map *read_disjunct(struct isl_stream *s,
957 struct vars *v, __isl_take isl_dim *dim)
958 {
959 int seen_paren = 0;
960 struct isl_token *tok;
961 struct isl_basic_map *bmap;
962
963 bmap = isl_basic_map_alloc_dim(dim, 0, 0, 0);
964 if (!bmap)
965 return NULL;
966
967 tok = isl_stream_next_token(s);
968 if (!tok)
969 goto error;
970 if (tok->type == '(') {
971 seen_paren = 1;
972 isl_token_free(tok);
973 } else
974 isl_stream_push_token(s, tok);
975
976 bmap = add_constraints(s, v, bmap);
977 bmap = isl_basic_map_simplify(bmap);
978 bmap = isl_basic_map_finalize(bmap);
979
980 if (seen_paren && isl_stream_eat(s, ')'))
981 goto error;
982
983 return bmap;
984 error:
985 isl_basic_map_free(bmap);
986 return NULL;
987 }
988
989 static struct isl_map *read_disjuncts(struct isl_stream *s,
990 struct vars *v, __isl_take isl_dim *dim)
991 {
992 struct isl_token *tok;
993 struct isl_map *map;
994
995 tok = isl_stream_next_token(s);
996 if (!tok) {
997 isl_stream_error(s, NULL, "unexpected EOF");
998 goto error;
999 }
1000 if (tok->type == '}') {
1001 isl_stream_push_token(s, tok);
1002 return isl_map_universe(dim);
1003 }
1004 isl_stream_push_token(s, tok);
1005
1006 map = isl_map_empty(isl_dim_copy(dim));
1007 for (;;) {
1008 struct isl_basic_map *bmap;
1009 int n = v->n;
1010
1011 bmap = read_disjunct(s, v, isl_dim_copy(dim));
1012 map = isl_map_union(map, isl_map_from_basic_map(bmap));
1013
1014 vars_drop(v, v->n - n);
1015
1016 tok = isl_stream_next_token(s);
1017 if (!tok || tok->type != ISL_TOKEN_OR)
1018 break;
1019 isl_token_free(tok);
1020 }
1021 if (tok)
1022 isl_stream_push_token(s, tok);
1023
1024 isl_dim_free(dim);
1025 return map;
1026 error:
1027 isl_dim_free(dim);
1028 return NULL;
1029 }
1030
1031 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1032 {
1033 if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1034 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1035 isl_basic_map_dim(bmap, isl_dim_in) + pos;
1036 pos -= isl_basic_map_dim(bmap, isl_dim_out);
1037
1038 if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1039 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1040 pos -= isl_basic_map_dim(bmap, isl_dim_in);
1041
1042 if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1043 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1044 isl_basic_map_dim(bmap, isl_dim_in) +
1045 isl_basic_map_dim(bmap, isl_dim_out) + pos;
1046 pos -= isl_basic_map_dim(bmap, isl_dim_div);
1047
1048 if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1049 return 1 + pos;
1050
1051 return 0;
1052 }
1053
1054 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1055 struct isl_stream *s, __isl_take isl_basic_map *bmap)
1056 {
1057 int j;
1058 struct isl_token *tok;
1059 int type;
1060 int k;
1061 isl_int *c;
1062 unsigned nparam;
1063 unsigned dim;
1064
1065 if (!bmap)
1066 return NULL;
1067
1068 nparam = isl_basic_map_dim(bmap, isl_dim_param);
1069 dim = isl_basic_map_dim(bmap, isl_dim_out);
1070
1071 tok = isl_stream_next_token(s);
1072 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1073 isl_stream_error(s, tok, "expecting coefficient");
1074 if (tok)
1075 isl_stream_push_token(s, tok);
1076 goto error;
1077 }
1078 if (!tok->on_new_line) {
1079 isl_stream_error(s, tok, "coefficient should appear on new line");
1080 isl_stream_push_token(s, tok);
1081 goto error;
1082 }
1083
1084 type = isl_int_get_si(tok->u.v);
1085 isl_token_free(tok);
1086
1087 isl_assert(s->ctx, type == 0 || type == 1, goto error);
1088 if (type == 0) {
1089 k = isl_basic_map_alloc_equality(bmap);
1090 c = bmap->eq[k];
1091 } else {
1092 k = isl_basic_map_alloc_inequality(bmap);
1093 c = bmap->ineq[k];
1094 }
1095 if (k < 0)
1096 goto error;
1097
1098 for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1099 int pos;
1100 tok = isl_stream_next_token(s);
1101 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1102 isl_stream_error(s, tok, "expecting coefficient");
1103 if (tok)
1104 isl_stream_push_token(s, tok);
1105 goto error;
1106 }
1107 if (tok->on_new_line) {
1108 isl_stream_error(s, tok,
1109 "coefficient should not appear on new line");
1110 isl_stream_push_token(s, tok);
1111 goto error;
1112 }
1113 pos = polylib_pos_to_isl_pos(bmap, j);
1114 isl_int_set(c[pos], tok->u.v);
1115 isl_token_free(tok);
1116 }
1117
1118 return bmap;
1119 error:
1120 isl_basic_map_free(bmap);
1121 return NULL;
1122 }
1123
1124 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s,
1125 int nparam)
1126 {
1127 int i;
1128 struct isl_token *tok;
1129 struct isl_token *tok2;
1130 int n_row, n_col;
1131 int on_new_line;
1132 unsigned in = 0, out, local = 0;
1133 struct isl_basic_map *bmap = NULL;
1134
1135 if (nparam < 0)
1136 nparam = 0;
1137
1138 tok = isl_stream_next_token(s);
1139 if (!tok) {
1140 isl_stream_error(s, NULL, "unexpected EOF");
1141 return NULL;
1142 }
1143 tok2 = isl_stream_next_token(s);
1144 if (!tok2) {
1145 isl_token_free(tok);
1146 isl_stream_error(s, NULL, "unexpected EOF");
1147 return NULL;
1148 }
1149 n_row = isl_int_get_si(tok->u.v);
1150 n_col = isl_int_get_si(tok2->u.v);
1151 on_new_line = tok2->on_new_line;
1152 isl_token_free(tok2);
1153 isl_token_free(tok);
1154 isl_assert(s->ctx, !on_new_line, return NULL);
1155 isl_assert(s->ctx, n_row >= 0, return NULL);
1156 isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1157 tok = isl_stream_next_token_on_same_line(s);
1158 if (tok) {
1159 if (tok->type != ISL_TOKEN_VALUE) {
1160 isl_stream_error(s, tok,
1161 "expecting number of output dimensions");
1162 isl_stream_push_token(s, tok);
1163 goto error;
1164 }
1165 out = isl_int_get_si(tok->u.v);
1166 isl_token_free(tok);
1167
1168 tok = isl_stream_next_token_on_same_line(s);
1169 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1170 isl_stream_error(s, tok,
1171 "expecting number of input dimensions");
1172 if (tok)
1173 isl_stream_push_token(s, tok);
1174 goto error;
1175 }
1176 in = isl_int_get_si(tok->u.v);
1177 isl_token_free(tok);
1178
1179 tok = isl_stream_next_token_on_same_line(s);
1180 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1181 isl_stream_error(s, tok,
1182 "expecting number of existentials");
1183 if (tok)
1184 isl_stream_push_token(s, tok);
1185 goto error;
1186 }
1187 local = isl_int_get_si(tok->u.v);
1188 isl_token_free(tok);
1189
1190 tok = isl_stream_next_token_on_same_line(s);
1191 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1192 isl_stream_error(s, tok,
1193 "expecting number of parameters");
1194 if (tok)
1195 isl_stream_push_token(s, tok);
1196 goto error;
1197 }
1198 nparam = isl_int_get_si(tok->u.v);
1199 isl_token_free(tok);
1200 if (n_col != 1 + out + in + local + nparam + 1) {
1201 isl_stream_error(s, NULL,
1202 "dimensions don't match");
1203 goto error;
1204 }
1205 } else
1206 out = n_col - 2 - nparam;
1207 bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1208 if (!bmap)
1209 return NULL;
1210
1211 for (i = 0; i < local; ++i) {
1212 int k = isl_basic_map_alloc_div(bmap);
1213 if (k < 0)
1214 goto error;
1215 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1216 }
1217
1218 for (i = 0; i < n_row; ++i)
1219 bmap = basic_map_read_polylib_constraint(s, bmap);
1220
1221 tok = isl_stream_next_token_on_same_line(s);
1222 if (tok) {
1223 isl_stream_error(s, tok, "unexpected extra token on line");
1224 isl_stream_push_token(s, tok);
1225 goto error;
1226 }
1227
1228 bmap = isl_basic_map_simplify(bmap);
1229 bmap = isl_basic_map_finalize(bmap);
1230 return bmap;
1231 error:
1232 isl_basic_map_free(bmap);
1233 return NULL;
1234 }
1235
1236 static struct isl_map *map_read_polylib(struct isl_stream *s, int nparam)
1237 {
1238 struct isl_token *tok;
1239 struct isl_token *tok2;
1240 int i, n;
1241 struct isl_map *map;
1242
1243 tok = isl_stream_next_token(s);
1244 if (!tok) {
1245 isl_stream_error(s, NULL, "unexpected EOF");
1246 return NULL;
1247 }
1248 tok2 = isl_stream_next_token_on_same_line(s);
1249 if (tok2) {
1250 isl_stream_push_token(s, tok2);
1251 isl_stream_push_token(s, tok);
1252 return isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
1253 }
1254 n = isl_int_get_si(tok->u.v);
1255 isl_token_free(tok);
1256
1257 isl_assert(s->ctx, n >= 1, return NULL);
1258
1259 map = isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
1260
1261 for (i = 1; i < n; ++i)
1262 map = isl_map_union(map,
1263 isl_map_from_basic_map(basic_map_read_polylib(s, nparam)));
1264
1265 return map;
1266 }
1267
1268 static int optional_power(struct isl_stream *s)
1269 {
1270 int pow;
1271 struct isl_token *tok;
1272
1273 tok = isl_stream_next_token(s);
1274 if (!tok)
1275 return 1;
1276 if (tok->type != '^') {
1277 isl_stream_push_token(s, tok);
1278 return 1;
1279 }
1280 isl_token_free(tok);
1281 tok = isl_stream_next_token(s);
1282 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1283 isl_stream_error(s, tok, "expecting exponent");
1284 if (tok)
1285 isl_stream_push_token(s, tok);
1286 return 1;
1287 }
1288 pow = isl_int_get_si(tok->u.v);
1289 isl_token_free(tok);
1290 return pow;
1291 }
1292
1293 static __isl_give isl_div *read_div(struct isl_stream *s,
1294 __isl_take isl_dim *dim, struct vars *v)
1295 {
1296 int n;
1297 isl_basic_map *bmap;
1298
1299 n = v->n;
1300 bmap = isl_basic_map_universe(dim);
1301
1302 if (vars_add_anon(v) < 0)
1303 goto error;
1304 if (read_div_definition(s, v) < 0)
1305 goto error;
1306 bmap = add_divs(bmap, v);
1307 bmap = isl_basic_map_order_divs(bmap);
1308 if (!bmap)
1309 goto error;
1310 vars_drop(v, v->n - n);
1311
1312 return isl_basic_map_div(bmap, bmap->n_div - 1);
1313 error:
1314 isl_basic_map_free(bmap);
1315 return NULL;
1316 }
1317
1318 static __isl_give isl_qpolynomial *read_term(struct isl_stream *s,
1319 __isl_keep isl_basic_map *bmap, struct vars *v);
1320
1321 static __isl_give isl_qpolynomial *read_factor(struct isl_stream *s,
1322 __isl_keep isl_basic_map *bmap, struct vars *v)
1323 {
1324 struct isl_qpolynomial *qp;
1325 struct isl_token *tok;
1326
1327 tok = isl_stream_next_token(s);
1328 if (!tok) {
1329 isl_stream_error(s, NULL, "unexpected EOF");
1330 return NULL;
1331 }
1332 if (tok->type == '(') {
1333 int pow;
1334
1335 isl_token_free(tok);
1336 qp = read_term(s, bmap, v);
1337 if (!qp)
1338 return NULL;
1339 if (isl_stream_eat(s, ')'))
1340 goto error;
1341 pow = optional_power(s);
1342 qp = isl_qpolynomial_pow(qp, pow);
1343 } else if (tok->type == ISL_TOKEN_VALUE) {
1344 struct isl_token *tok2;
1345 tok2 = isl_stream_next_token(s);
1346 if (tok2 && tok2->type == '/') {
1347 isl_token_free(tok2);
1348 tok2 = isl_stream_next_token(s);
1349 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1350 isl_stream_error(s, tok2, "expected denominator");
1351 isl_token_free(tok);
1352 isl_token_free(tok2);
1353 return NULL;
1354 }
1355 qp = isl_qpolynomial_rat_cst(isl_basic_map_get_dim(bmap),
1356 tok->u.v, tok2->u.v);
1357 isl_token_free(tok2);
1358 } else {
1359 isl_stream_push_token(s, tok2);
1360 qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap),
1361 tok->u.v);
1362 }
1363 isl_token_free(tok);
1364 } else if (tok->type == ISL_TOKEN_INFTY) {
1365 isl_token_free(tok);
1366 qp = isl_qpolynomial_infty(isl_basic_map_get_dim(bmap));
1367 } else if (tok->type == ISL_TOKEN_NAN) {
1368 isl_token_free(tok);
1369 qp = isl_qpolynomial_nan(isl_basic_map_get_dim(bmap));
1370 } else if (tok->type == ISL_TOKEN_IDENT) {
1371 int n = v->n;
1372 int pos = vars_pos(v, tok->u.s, -1);
1373 int pow;
1374 if (pos < 0) {
1375 isl_token_free(tok);
1376 return NULL;
1377 }
1378 if (pos >= n) {
1379 isl_stream_error(s, tok, "unknown identifier");
1380 isl_token_free(tok);
1381 return NULL;
1382 }
1383 isl_token_free(tok);
1384 pow = optional_power(s);
1385 qp = isl_qpolynomial_var_pow(isl_basic_map_get_dim(bmap), pos, pow);
1386 } else if (tok->type == '[') {
1387 isl_div *div;
1388 int pow;
1389
1390 isl_stream_push_token(s, tok);
1391 div = read_div(s, isl_basic_map_get_dim(bmap), v);
1392 pow = optional_power(s);
1393 qp = isl_qpolynomial_div_pow(div, pow);
1394 } else if (tok->type == '-') {
1395 struct isl_qpolynomial *qp2;
1396
1397 isl_token_free(tok);
1398 qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap),
1399 s->ctx->negone);
1400 qp2 = read_factor(s, bmap, v);
1401 qp = isl_qpolynomial_mul(qp, qp2);
1402 } else {
1403 isl_stream_error(s, tok, "unexpected isl_token");
1404 isl_stream_push_token(s, tok);
1405 return NULL;
1406 }
1407
1408 if (isl_stream_eat_if_available(s, '*') ||
1409 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
1410 struct isl_qpolynomial *qp2;
1411
1412 qp2 = read_factor(s, bmap, v);
1413 qp = isl_qpolynomial_mul(qp, qp2);
1414 }
1415
1416 return qp;
1417 error:
1418 isl_qpolynomial_free(qp);
1419 return NULL;
1420 }
1421
1422 static __isl_give isl_qpolynomial *read_term(struct isl_stream *s,
1423 __isl_keep isl_basic_map *bmap, struct vars *v)
1424 {
1425 struct isl_token *tok;
1426 struct isl_qpolynomial *qp;
1427
1428 qp = read_factor(s, bmap, v);
1429
1430 for (;;) {
1431 tok = isl_stream_next_token(s);
1432 if (!tok)
1433 return qp;
1434
1435 if (tok->type == '+') {
1436 struct isl_qpolynomial *qp2;
1437
1438 isl_token_free(tok);
1439 qp2 = read_factor(s, bmap, v);
1440 qp = isl_qpolynomial_add(qp, qp2);
1441 } else if (tok->type == '-') {
1442 struct isl_qpolynomial *qp2;
1443
1444 isl_token_free(tok);
1445 qp2 = read_factor(s, bmap, v);
1446 qp = isl_qpolynomial_sub(qp, qp2);
1447 } else if (tok->type == ISL_TOKEN_VALUE &&
1448 isl_int_is_neg(tok->u.v)) {
1449 struct isl_qpolynomial *qp2;
1450
1451 isl_stream_push_token(s, tok);
1452 qp2 = read_factor(s, bmap, v);
1453 qp = isl_qpolynomial_add(qp, qp2);
1454 } else {
1455 isl_stream_push_token(s, tok);
1456 break;
1457 }
1458 }
1459
1460 return qp;
1461 }
1462
1463 static __isl_give isl_map *read_optional_disjuncts(struct isl_stream *s,
1464 __isl_take isl_basic_map *bmap, struct vars *v)
1465 {
1466 struct isl_token *tok;
1467 struct isl_map *map;
1468
1469 tok = isl_stream_next_token(s);
1470 if (!tok) {
1471 isl_stream_error(s, NULL, "unexpected EOF");
1472 goto error;
1473 }
1474 map = isl_map_from_basic_map(isl_basic_map_copy(bmap));
1475 if (tok->type == ':') {
1476 isl_token_free(tok);
1477 map = isl_map_intersect(map,
1478 read_disjuncts(s, v, isl_basic_map_get_dim(bmap)));
1479 } else
1480 isl_stream_push_token(s, tok);
1481
1482 isl_basic_map_free(bmap);
1483
1484 return map;
1485 error:
1486 isl_basic_map_free(bmap);
1487 return NULL;
1488 }
1489
1490 static struct isl_obj obj_read_poly(struct isl_stream *s,
1491 __isl_take isl_basic_map *bmap, struct vars *v, int n)
1492 {
1493 struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
1494 struct isl_pw_qpolynomial *pwqp;
1495 struct isl_qpolynomial *qp;
1496 struct isl_map *map;
1497 struct isl_set *set;
1498
1499 qp = read_term(s, bmap, v);
1500 map = read_optional_disjuncts(s, bmap, v);
1501 set = isl_map_range(map);
1502
1503 pwqp = isl_pw_qpolynomial_alloc(set, qp);
1504
1505 vars_drop(v, v->n - n);
1506
1507 obj.v = pwqp;
1508 return obj;
1509 }
1510
1511 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
1512 __isl_take isl_basic_map *bmap, struct vars *v, int n)
1513 {
1514 struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
1515 struct isl_obj obj_p;
1516 isl_qpolynomial *qp;
1517 isl_qpolynomial_fold *fold = NULL;
1518 isl_pw_qpolynomial_fold *pwf;
1519 isl_map *map;
1520 isl_set *set;
1521
1522 if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
1523 return obj_read_poly(s, bmap, v, n);
1524
1525 if (isl_stream_eat(s, '('))
1526 goto error;
1527
1528 qp = read_term(s, bmap, v);
1529 fold = isl_qpolynomial_fold_alloc(isl_fold_max, qp);
1530
1531 while (isl_stream_eat_if_available(s, ',')) {
1532 isl_qpolynomial_fold *fold_i;
1533 qp = read_term(s, bmap, v);
1534 fold_i = isl_qpolynomial_fold_alloc(isl_fold_max, qp);
1535 fold = isl_qpolynomial_fold_fold(fold, fold_i);
1536 }
1537
1538 if (isl_stream_eat(s, ')'))
1539 goto error;
1540
1541 map = read_optional_disjuncts(s, bmap, v);
1542 set = isl_map_range(map);
1543 pwf = isl_pw_qpolynomial_fold_alloc(isl_fold_max, set, fold);
1544
1545 vars_drop(v, v->n - n);
1546
1547 obj.v = pwf;
1548 return obj;
1549 error:
1550 isl_basic_map_free(bmap);
1551 isl_qpolynomial_fold_free(fold);
1552 obj.type = isl_obj_none;
1553 return obj;
1554 }
1555
1556 static struct isl_obj obj_read_body(struct isl_stream *s,
1557 __isl_take isl_basic_map *bmap, struct vars *v)
1558 {
1559 struct isl_map *map = NULL;
1560 struct isl_token *tok;
1561 struct isl_obj obj = { isl_obj_set, NULL };
1562 int n = v->n;
1563
1564 if (!next_is_tuple(s))
1565 return obj_read_poly_or_fold(s, bmap, v, n);
1566
1567 bmap = read_tuple(s, bmap, isl_dim_in, v);
1568 if (!bmap)
1569 goto error;
1570 tok = isl_stream_next_token(s);
1571 if (tok && tok->type == ISL_TOKEN_TO) {
1572 obj.type = isl_obj_map;
1573 isl_token_free(tok);
1574 if (!next_is_tuple(s)) {
1575 bmap = isl_basic_map_reverse(bmap);
1576 return obj_read_poly_or_fold(s, bmap, v, n);
1577 }
1578 bmap = read_tuple(s, bmap, isl_dim_out, v);
1579 if (!bmap)
1580 goto error;
1581 } else {
1582 bmap = isl_basic_map_reverse(bmap);
1583 if (tok)
1584 isl_stream_push_token(s, tok);
1585 }
1586
1587 map = read_optional_disjuncts(s, bmap, v);
1588
1589 vars_drop(v, v->n - n);
1590
1591 obj.v = map;
1592 return obj;
1593 error:
1594 isl_basic_map_free(bmap);
1595 obj.type = isl_obj_none;
1596 return obj;
1597 }
1598
1599 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
1600 {
1601 if (obj.type == isl_obj_map) {
1602 obj.v = isl_union_map_from_map(obj.v);
1603 obj.type = isl_obj_union_map;
1604 } else if (obj.type == isl_obj_set) {
1605 obj.v = isl_union_set_from_set(obj.v);
1606 obj.type = isl_obj_union_set;
1607 } else if (obj.type == isl_obj_pw_qpolynomial) {
1608 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
1609 obj.type = isl_obj_union_pw_qpolynomial;
1610 } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
1611 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
1612 obj.type = isl_obj_union_pw_qpolynomial_fold;
1613 } else
1614 isl_assert(ctx, 0, goto error);
1615 return obj;
1616 error:
1617 obj.type->free(obj.v);
1618 obj.type = isl_obj_none;
1619 return obj;
1620 }
1621
1622 static struct isl_obj obj_add(struct isl_ctx *ctx,
1623 struct isl_obj obj1, struct isl_obj obj2)
1624 {
1625 if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
1626 obj1 = to_union(ctx, obj1);
1627 if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
1628 obj2 = to_union(ctx, obj2);
1629 if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
1630 obj1 = to_union(ctx, obj1);
1631 if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
1632 obj2 = to_union(ctx, obj2);
1633 if (obj1.type == isl_obj_pw_qpolynomial &&
1634 obj2.type == isl_obj_union_pw_qpolynomial)
1635 obj1 = to_union(ctx, obj1);
1636 if (obj1.type == isl_obj_union_pw_qpolynomial &&
1637 obj2.type == isl_obj_pw_qpolynomial)
1638 obj2 = to_union(ctx, obj2);
1639 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1640 obj2.type == isl_obj_union_pw_qpolynomial_fold)
1641 obj1 = to_union(ctx, obj1);
1642 if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
1643 obj2.type == isl_obj_pw_qpolynomial_fold)
1644 obj2 = to_union(ctx, obj2);
1645 isl_assert(ctx, obj1.type == obj2.type, goto error);
1646 if (obj1.type == isl_obj_map && !isl_map_has_equal_dim(obj1.v, obj2.v)) {
1647 obj1 = to_union(ctx, obj1);
1648 obj2 = to_union(ctx, obj2);
1649 }
1650 if (obj1.type == isl_obj_set && !isl_set_has_equal_dim(obj1.v, obj2.v)) {
1651 obj1 = to_union(ctx, obj1);
1652 obj2 = to_union(ctx, obj2);
1653 }
1654 if (obj1.type == isl_obj_pw_qpolynomial &&
1655 !isl_pw_qpolynomial_has_equal_dim(obj1.v, obj2.v)) {
1656 obj1 = to_union(ctx, obj1);
1657 obj2 = to_union(ctx, obj2);
1658 }
1659 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1660 !isl_pw_qpolynomial_fold_has_equal_dim(obj1.v, obj2.v)) {
1661 obj1 = to_union(ctx, obj1);
1662 obj2 = to_union(ctx, obj2);
1663 }
1664 obj1.v = obj1.type->add(obj1.v, obj2.v);
1665 return obj1;
1666 error:
1667 obj1.type->free(obj1.v);
1668 obj2.type->free(obj2.v);
1669 obj1.type = isl_obj_none;
1670 obj1.v = NULL;
1671 return obj1;
1672 }
1673
1674 static struct isl_obj obj_read(struct isl_stream *s, int nparam)
1675 {
1676 isl_basic_map *bmap = NULL;
1677 struct isl_token *tok;
1678 struct vars *v = NULL;
1679 struct isl_obj obj = { isl_obj_set, NULL };
1680
1681 tok = isl_stream_next_token(s);
1682 if (!tok) {
1683 isl_stream_error(s, NULL, "unexpected EOF");
1684 goto error;
1685 }
1686 if (tok->type == ISL_TOKEN_VALUE) {
1687 struct isl_map *map;
1688 isl_stream_push_token(s, tok);
1689 map = map_read_polylib(s, nparam);
1690 if (!map)
1691 goto error;
1692 if (isl_map_dim(map, isl_dim_in) > 0)
1693 obj.type = isl_obj_map;
1694 obj.v = map;
1695 return obj;
1696 }
1697 v = vars_new(s->ctx);
1698 if (!v) {
1699 isl_stream_push_token(s, tok);
1700 goto error;
1701 }
1702 bmap = isl_basic_map_alloc(s->ctx, 0, 0, 0, 0, 0, 0);
1703 if (tok->type == '[') {
1704 isl_stream_push_token(s, tok);
1705 bmap = read_tuple(s, bmap, isl_dim_param, v);
1706 if (!bmap)
1707 goto error;
1708 if (nparam >= 0)
1709 isl_assert(s->ctx, nparam == v->n, goto error);
1710 tok = isl_stream_next_token(s);
1711 if (!tok || tok->type != ISL_TOKEN_TO) {
1712 isl_stream_error(s, tok, "expecting '->'");
1713 if (tok)
1714 isl_stream_push_token(s, tok);
1715 goto error;
1716 }
1717 isl_token_free(tok);
1718 tok = isl_stream_next_token(s);
1719 } else if (nparam > 0)
1720 bmap = isl_basic_map_add(bmap, isl_dim_param, nparam);
1721 if (!tok || tok->type != '{') {
1722 isl_stream_error(s, tok, "expecting '{'");
1723 if (tok)
1724 isl_stream_push_token(s, tok);
1725 goto error;
1726 }
1727 isl_token_free(tok);
1728
1729 tok = isl_stream_next_token(s);
1730 if (!tok)
1731 ;
1732 else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
1733 isl_token_free(tok);
1734 if (isl_stream_eat(s, '='))
1735 goto error;
1736 bmap = read_tuple(s, bmap, isl_dim_param, v);
1737 if (!bmap)
1738 goto error;
1739 if (nparam >= 0)
1740 isl_assert(s->ctx, nparam == v->n, goto error);
1741 } else if (tok->type == '}') {
1742 obj.type = isl_obj_union_set;
1743 obj.v = isl_union_set_empty(isl_basic_map_get_dim(bmap));
1744 isl_token_free(tok);
1745 goto done;
1746 } else
1747 isl_stream_push_token(s, tok);
1748
1749 for (;;) {
1750 struct isl_obj o;
1751 tok = NULL;
1752 o = obj_read_body(s, isl_basic_map_copy(bmap), v);
1753 if (o.type == isl_obj_none || !o.v)
1754 goto error;
1755 if (!obj.v)
1756 obj = o;
1757 else {
1758 obj = obj_add(s->ctx, obj, o);
1759 if (obj.type == isl_obj_none || !obj.v)
1760 goto error;
1761 }
1762 tok = isl_stream_next_token(s);
1763 if (!tok || tok->type != ';')
1764 break;
1765 isl_token_free(tok);
1766 }
1767
1768 if (tok && tok->type == '}') {
1769 isl_token_free(tok);
1770 } else {
1771 isl_stream_error(s, tok, "unexpected isl_token");
1772 if (tok)
1773 isl_token_free(tok);
1774 goto error;
1775 }
1776 done:
1777 vars_free(v);
1778 isl_basic_map_free(bmap);
1779
1780 return obj;
1781 error:
1782 isl_basic_map_free(bmap);
1783 obj.type->free(obj.v);
1784 if (v)
1785 vars_free(v);
1786 obj.v = NULL;
1787 return obj;
1788 }
1789
1790 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
1791 {
1792 return obj_read(s, -1);
1793 }
1794
1795 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s, int nparam)
1796 {
1797 struct isl_obj obj;
1798 struct isl_map *map;
1799
1800 obj = obj_read(s, nparam);
1801 if (obj.v)
1802 isl_assert(s->ctx, obj.type == isl_obj_map ||
1803 obj.type == isl_obj_set, goto error);
1804
1805 return obj.v;
1806 error:
1807 obj.type->free(obj.v);
1808 return NULL;
1809 }
1810
1811 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s, int nparam)
1812 {
1813 struct isl_obj obj;
1814 struct isl_set *set;
1815
1816 obj = obj_read(s, nparam);
1817 if (obj.v)
1818 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
1819
1820 return obj.v;
1821 error:
1822 obj.type->free(obj.v);
1823 return NULL;
1824 }
1825
1826 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
1827 {
1828 struct isl_obj obj;
1829 isl_union_map *umap;
1830
1831 obj = obj_read(s, -1);
1832 if (obj.type == isl_obj_map) {
1833 obj.type = isl_obj_union_map;
1834 obj.v = isl_union_map_from_map(obj.v);
1835 }
1836 if (obj.type == isl_obj_set) {
1837 obj.type = isl_obj_union_set;
1838 obj.v = isl_union_set_from_set(obj.v);
1839 }
1840 if (obj.v)
1841 isl_assert(s->ctx, obj.type == isl_obj_union_map ||
1842 obj.type == isl_obj_union_set, goto error);
1843
1844 return obj.v;
1845 error:
1846 obj.type->free(obj.v);
1847 return NULL;
1848 }
1849
1850 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
1851 {
1852 struct isl_obj obj;
1853 isl_union_set *uset;
1854
1855 obj = obj_read(s, -1);
1856 if (obj.type == isl_obj_set) {
1857 obj.type = isl_obj_union_set;
1858 obj.v = isl_union_set_from_set(obj.v);
1859 }
1860 if (obj.v)
1861 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
1862
1863 return obj.v;
1864 error:
1865 obj.type->free(obj.v);
1866 return NULL;
1867 }
1868
1869 static struct isl_basic_map *basic_map_read(struct isl_stream *s, int nparam)
1870 {
1871 struct isl_obj obj;
1872 struct isl_map *map;
1873 struct isl_basic_map *bmap;
1874
1875 obj = obj_read(s, nparam);
1876 map = obj.v;
1877 if (!map)
1878 return NULL;
1879
1880 isl_assert(map->ctx, map->n <= 1, goto error);
1881
1882 if (map->n == 0)
1883 bmap = isl_basic_map_empty_like_map(map);
1884 else
1885 bmap = isl_basic_map_copy(map->p[0]);
1886
1887 isl_map_free(map);
1888
1889 return bmap;
1890 error:
1891 isl_map_free(map);
1892 return NULL;
1893 }
1894
1895 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
1896 FILE *input, int nparam)
1897 {
1898 struct isl_basic_map *bmap;
1899 struct isl_stream *s = isl_stream_new_file(ctx, input);
1900 if (!s)
1901 return NULL;
1902 bmap = basic_map_read(s, nparam);
1903 isl_stream_free(s);
1904 return bmap;
1905 }
1906
1907 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
1908 FILE *input, int nparam)
1909 {
1910 struct isl_basic_map *bmap;
1911 bmap = isl_basic_map_read_from_file(ctx, input, nparam);
1912 if (!bmap)
1913 return NULL;
1914 isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
1915 return (struct isl_basic_set *)bmap;
1916 error:
1917 isl_basic_map_free(bmap);
1918 return NULL;
1919 }
1920
1921 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
1922 const char *str, int nparam)
1923 {
1924 struct isl_basic_map *bmap;
1925 struct isl_stream *s = isl_stream_new_str(ctx, str);
1926 if (!s)
1927 return NULL;
1928 bmap = basic_map_read(s, nparam);
1929 isl_stream_free(s);
1930 return bmap;
1931 }
1932
1933 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
1934 const char *str, int nparam)
1935 {
1936 struct isl_basic_map *bmap;
1937 bmap = isl_basic_map_read_from_str(ctx, str, nparam);
1938 if (!bmap)
1939 return NULL;
1940 isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
1941 return (struct isl_basic_set *)bmap;
1942 error:
1943 isl_basic_map_free(bmap);
1944 return NULL;
1945 }
1946
1947 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
1948 FILE *input, int nparam)
1949 {
1950 struct isl_map *map;
1951 struct isl_stream *s = isl_stream_new_file(ctx, input);
1952 if (!s)
1953 return NULL;
1954 map = isl_stream_read_map(s, nparam);
1955 isl_stream_free(s);
1956 return map;
1957 }
1958
1959 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
1960 const char *str, int nparam)
1961 {
1962 struct isl_map *map;
1963 struct isl_stream *s = isl_stream_new_str(ctx, str);
1964 if (!s)
1965 return NULL;
1966 map = isl_stream_read_map(s, nparam);
1967 isl_stream_free(s);
1968 return map;
1969 }
1970
1971 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
1972 FILE *input, int nparam)
1973 {
1974 struct isl_map *map;
1975 map = isl_map_read_from_file(ctx, input, nparam);
1976 if (!map)
1977 return NULL;
1978 isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
1979 return (struct isl_set *)map;
1980 error:
1981 isl_map_free(map);
1982 return NULL;
1983 }
1984
1985 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
1986 const char *str, int nparam)
1987 {
1988 struct isl_map *map;
1989 map = isl_map_read_from_str(ctx, str, nparam);
1990 if (!map)
1991 return NULL;
1992 isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
1993 return (struct isl_set *)map;
1994 error:
1995 isl_map_free(map);
1996 return NULL;
1997 }
1998
1999 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2000 const char *str)
2001 {
2002 isl_union_map *umap;
2003 struct isl_stream *s = isl_stream_new_str(ctx, str);
2004 if (!s)
2005 return NULL;
2006 umap = isl_stream_read_union_map(s);
2007 isl_stream_free(s);
2008 return umap;
2009 }
2010
2011 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2012 const char *str)
2013 {
2014 isl_union_set *uset;
2015 struct isl_stream *s = isl_stream_new_str(ctx, str);
2016 if (!s)
2017 return NULL;
2018 uset = isl_stream_read_union_set(s);
2019 isl_stream_free(s);
2020 return uset;
2021 }
2022
2023 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2024 {
2025 struct isl_vec *vec = NULL;
2026 struct isl_token *tok;
2027 unsigned size;
2028 int j;
2029
2030 tok = isl_stream_next_token(s);
2031 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2032 isl_stream_error(s, tok, "expecting vector length");
2033 goto error;
2034 }
2035
2036 size = isl_int_get_si(tok->u.v);
2037 isl_token_free(tok);
2038
2039 vec = isl_vec_alloc(s->ctx, size);
2040
2041 for (j = 0; j < size; ++j) {
2042 tok = isl_stream_next_token(s);
2043 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2044 isl_stream_error(s, tok, "expecting constant value");
2045 goto error;
2046 }
2047 isl_int_set(vec->el[j], tok->u.v);
2048 isl_token_free(tok);
2049 }
2050
2051 return vec;
2052 error:
2053 isl_token_free(tok);
2054 isl_vec_free(vec);
2055 return NULL;
2056 }
2057
2058 static __isl_give isl_vec *vec_read(struct isl_stream *s,
2059 unsigned input_format)
2060 {
2061 if (input_format == ISL_FORMAT_POLYLIB)
2062 return isl_vec_read_polylib(s);
2063 isl_assert(s->ctx, 0, return NULL);
2064 }
2065
2066 struct isl_vec *isl_vec_read_from_file(struct isl_ctx *ctx,
2067 FILE *input, unsigned input_format)
2068 {
2069 isl_vec *v;
2070 struct isl_stream *s = isl_stream_new_file(ctx, input);
2071 if (!s)
2072 return NULL;
2073 v = vec_read(s, input_format);
2074 isl_stream_free(s);
2075 return v;
2076 }
2077
2078 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2079 struct isl_stream *s)
2080 {
2081 struct isl_obj obj;
2082 struct isl_pw_qpolynomial *pwqp;
2083
2084 obj = obj_read(s, -1);
2085 if (obj.v)
2086 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2087 goto error);
2088
2089 return obj.v;
2090 error:
2091 obj.type->free(obj.v);
2092 return NULL;
2093 }
2094
2095 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2096 const char *str)
2097 {
2098 isl_pw_qpolynomial *pwqp;
2099 struct isl_stream *s = isl_stream_new_str(ctx, str);
2100 if (!s)
2101 return NULL;
2102 pwqp = isl_stream_read_pw_qpolynomial(s);
2103 isl_stream_free(s);
2104 return pwqp;
2105 }
Integer set library