?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_union_map_read_from_str
[isl.git] / isl_input.c
blob9c9c2988f1334da71fd70e16565f603ceeacab8d
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 isl_token_free(tok);
1334 qp = read_term(s, bmap, v);
1335 if (!qp)
1336 return NULL;
1337 if (isl_stream_eat(s, ')'))
1338 goto error;
1339 } else if (tok->type == ISL_TOKEN_VALUE) {
1340 struct isl_token *tok2;
1341 tok2 = isl_stream_next_token(s);
1342 if (tok2 && tok2->type == '/') {
1343 isl_token_free(tok2);
1344 tok2 = isl_stream_next_token(s);
1345 if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1346 isl_stream_error(s, tok2, "expected denominator");
1347 isl_token_free(tok);
1348 isl_token_free(tok2);
1349 return NULL;
1350 }
1351 qp = isl_qpolynomial_rat_cst(isl_basic_map_get_dim(bmap),
1352 tok->u.v, tok2->u.v);
1353 isl_token_free(tok2);
1354 } else {
1355 isl_stream_push_token(s, tok2);
1356 qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap),
1357 tok->u.v);
1358 }
1359 isl_token_free(tok);
1360 } else if (tok->type == ISL_TOKEN_INFTY) {
1361 isl_token_free(tok);
1362 qp = isl_qpolynomial_infty(isl_basic_map_get_dim(bmap));
1363 } else if (tok->type == ISL_TOKEN_NAN) {
1364 isl_token_free(tok);
1365 qp = isl_qpolynomial_nan(isl_basic_map_get_dim(bmap));
1366 } else if (tok->type == ISL_TOKEN_IDENT) {
1367 int n = v->n;
1368 int pos = vars_pos(v, tok->u.s, -1);
1369 int pow;
1370 if (pos < 0) {
1371 isl_token_free(tok);
1372 return NULL;
1373 }
1374 if (pos >= n) {
1375 isl_stream_error(s, tok, "unknown identifier");
1376 isl_token_free(tok);
1377 return NULL;
1378 }
1379 isl_token_free(tok);
1380 pow = optional_power(s);
1381 qp = isl_qpolynomial_pow(isl_basic_map_get_dim(bmap), pos, pow);
1382 } else if (tok->type == '[') {
1383 isl_div *div;
1384 int pow;
1385
1386 isl_stream_push_token(s, tok);
1387 div = read_div(s, isl_basic_map_get_dim(bmap), v);
1388 pow = optional_power(s);
1389 qp = isl_qpolynomial_div_pow(div, pow);
1390 } else if (tok->type == '-') {
1391 struct isl_qpolynomial *qp2;
1392
1393 isl_token_free(tok);
1394 qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap),
1395 s->ctx->negone);
1396 qp2 = read_factor(s, bmap, v);
1397 qp = isl_qpolynomial_mul(qp, qp2);
1398 } else {
1399 isl_stream_error(s, tok, "unexpected isl_token");
1400 isl_stream_push_token(s, tok);
1401 return NULL;
1402 }
1403
1404 if (isl_stream_eat_if_available(s, '*') ||
1405 isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
1406 struct isl_qpolynomial *qp2;
1407
1408 qp2 = read_factor(s, bmap, v);
1409 qp = isl_qpolynomial_mul(qp, qp2);
1410 }
1411
1412 return qp;
1413 error:
1414 isl_qpolynomial_free(qp);
1415 return NULL;
1416 }
1417
1418 static __isl_give isl_qpolynomial *read_term(struct isl_stream *s,
1419 __isl_keep isl_basic_map *bmap, struct vars *v)
1420 {
1421 struct isl_token *tok;
1422 struct isl_qpolynomial *qp;
1423
1424 qp = read_factor(s, bmap, v);
1425
1426 for (;;) {
1427 tok = isl_stream_next_token(s);
1428 if (!tok)
1429 return qp;
1430
1431 if (tok->type == '+') {
1432 struct isl_qpolynomial *qp2;
1433
1434 isl_token_free(tok);
1435 qp2 = read_factor(s, bmap, v);
1436 qp = isl_qpolynomial_add(qp, qp2);
1437 } else if (tok->type == '-') {
1438 struct isl_qpolynomial *qp2;
1439
1440 isl_token_free(tok);
1441 qp2 = read_factor(s, bmap, v);
1442 qp = isl_qpolynomial_sub(qp, qp2);
1443 } else if (tok->type == ISL_TOKEN_VALUE &&
1444 isl_int_is_neg(tok->u.v)) {
1445 struct isl_qpolynomial *qp2;
1446
1447 isl_stream_push_token(s, tok);
1448 qp2 = read_factor(s, bmap, v);
1449 qp = isl_qpolynomial_add(qp, qp2);
1450 } else {
1451 isl_stream_push_token(s, tok);
1452 break;
1453 }
1454 }
1455
1456 return qp;
1457 }
1458
1459 static __isl_give isl_map *read_optional_disjuncts(struct isl_stream *s,
1460 __isl_take isl_basic_map *bmap, struct vars *v)
1461 {
1462 struct isl_token *tok;
1463 struct isl_map *map;
1464
1465 tok = isl_stream_next_token(s);
1466 if (!tok) {
1467 isl_stream_error(s, NULL, "unexpected EOF");
1468 goto error;
1469 }
1470 map = isl_map_from_basic_map(isl_basic_map_copy(bmap));
1471 if (tok->type == ':') {
1472 isl_token_free(tok);
1473 map = isl_map_intersect(map,
1474 read_disjuncts(s, v, isl_basic_map_get_dim(bmap)));
1475 } else
1476 isl_stream_push_token(s, tok);
1477
1478 isl_basic_map_free(bmap);
1479
1480 return map;
1481 error:
1482 isl_basic_map_free(bmap);
1483 return NULL;
1484 }
1485
1486 static struct isl_obj obj_read_poly(struct isl_stream *s,
1487 __isl_take isl_basic_map *bmap, struct vars *v, int n)
1488 {
1489 struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
1490 struct isl_pw_qpolynomial *pwqp;
1491 struct isl_qpolynomial *qp;
1492 struct isl_map *map;
1493 struct isl_set *set;
1494
1495 qp = read_term(s, bmap, v);
1496 map = read_optional_disjuncts(s, bmap, v);
1497 set = isl_map_range(map);
1498
1499 pwqp = isl_pw_qpolynomial_alloc(set, qp);
1500
1501 vars_drop(v, v->n - n);
1502
1503 obj.v = pwqp;
1504 return obj;
1505 }
1506
1507 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
1508 __isl_take isl_basic_map *bmap, struct vars *v, int n)
1509 {
1510 struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
1511 struct isl_obj obj_p;
1512 isl_qpolynomial *qp;
1513 isl_qpolynomial_fold *fold = NULL;
1514 isl_pw_qpolynomial_fold *pwf;
1515 isl_map *map;
1516 isl_set *set;
1517
1518 if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
1519 return obj_read_poly(s, bmap, v, n);
1520
1521 if (isl_stream_eat(s, '('))
1522 goto error;
1523
1524 qp = read_term(s, bmap, v);
1525 fold = isl_qpolynomial_fold_alloc(isl_fold_max, qp);
1526
1527 while (isl_stream_eat_if_available(s, ',')) {
1528 isl_qpolynomial_fold *fold_i;
1529 qp = read_term(s, bmap, v);
1530 fold_i = isl_qpolynomial_fold_alloc(isl_fold_max, qp);
1531 fold = isl_qpolynomial_fold_fold(fold, fold_i);
1532 }
1533
1534 if (isl_stream_eat(s, ')'))
1535 goto error;
1536
1537 map = read_optional_disjuncts(s, bmap, v);
1538 set = isl_map_range(map);
1539 pwf = isl_pw_qpolynomial_fold_alloc(isl_fold_max, set, fold);
1540
1541 vars_drop(v, v->n - n);
1542
1543 obj.v = pwf;
1544 return obj;
1545 error:
1546 isl_basic_map_free(bmap);
1547 isl_qpolynomial_fold_free(fold);
1548 obj.type = isl_obj_none;
1549 return obj;
1550 }
1551
1552 static struct isl_obj obj_read_body(struct isl_stream *s,
1553 __isl_take isl_basic_map *bmap, struct vars *v)
1554 {
1555 struct isl_map *map = NULL;
1556 struct isl_token *tok;
1557 struct isl_obj obj = { isl_obj_set, NULL };
1558 int n = v->n;
1559
1560 if (!next_is_tuple(s))
1561 return obj_read_poly_or_fold(s, bmap, v, n);
1562
1563 bmap = read_tuple(s, bmap, isl_dim_in, v);
1564 if (!bmap)
1565 goto error;
1566 tok = isl_stream_next_token(s);
1567 if (tok && tok->type == ISL_TOKEN_TO) {
1568 obj.type = isl_obj_map;
1569 isl_token_free(tok);
1570 if (!next_is_tuple(s)) {
1571 bmap = isl_basic_map_reverse(bmap);
1572 return obj_read_poly_or_fold(s, bmap, v, n);
1573 }
1574 bmap = read_tuple(s, bmap, isl_dim_out, v);
1575 if (!bmap)
1576 goto error;
1577 } else {
1578 bmap = isl_basic_map_reverse(bmap);
1579 if (tok)
1580 isl_stream_push_token(s, tok);
1581 }
1582
1583 map = read_optional_disjuncts(s, bmap, v);
1584
1585 vars_drop(v, v->n - n);
1586
1587 obj.v = map;
1588 return obj;
1589 error:
1590 isl_basic_map_free(bmap);
1591 obj.type = isl_obj_none;
1592 return obj;
1593 }
1594
1595 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
1596 {
1597 if (obj.type == isl_obj_map) {
1598 obj.v = isl_union_map_from_map(obj.v);
1599 obj.type = isl_obj_union_map;
1600 } else if (obj.type == isl_obj_set) {
1601 obj.v = isl_union_set_from_set(obj.v);
1602 obj.type = isl_obj_union_set;
1603 } else if (obj.type == isl_obj_pw_qpolynomial) {
1604 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
1605 obj.type = isl_obj_union_pw_qpolynomial;
1606 } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
1607 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
1608 obj.type = isl_obj_union_pw_qpolynomial_fold;
1609 } else
1610 isl_assert(ctx, 0, goto error);
1611 return obj;
1612 error:
1613 obj.type->free(obj.v);
1614 obj.type = isl_obj_none;
1615 return obj;
1616 }
1617
1618 static struct isl_obj obj_add(struct isl_ctx *ctx,
1619 struct isl_obj obj1, struct isl_obj obj2)
1620 {
1621 if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
1622 obj1 = to_union(ctx, obj1);
1623 if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
1624 obj2 = to_union(ctx, obj2);
1625 if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
1626 obj1 = to_union(ctx, obj1);
1627 if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
1628 obj2 = to_union(ctx, obj2);
1629 if (obj1.type == isl_obj_pw_qpolynomial &&
1630 obj2.type == isl_obj_union_pw_qpolynomial)
1631 obj1 = to_union(ctx, obj1);
1632 if (obj1.type == isl_obj_union_pw_qpolynomial &&
1633 obj2.type == isl_obj_pw_qpolynomial)
1634 obj2 = to_union(ctx, obj2);
1635 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1636 obj2.type == isl_obj_union_pw_qpolynomial_fold)
1637 obj1 = to_union(ctx, obj1);
1638 if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
1639 obj2.type == isl_obj_pw_qpolynomial_fold)
1640 obj2 = to_union(ctx, obj2);
1641 isl_assert(ctx, obj1.type == obj2.type, goto error);
1642 if (obj1.type == isl_obj_map && !isl_map_has_equal_dim(obj1.v, obj2.v)) {
1643 obj1 = to_union(ctx, obj1);
1644 obj2 = to_union(ctx, obj2);
1645 }
1646 if (obj1.type == isl_obj_set && !isl_set_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_pw_qpolynomial &&
1651 !isl_pw_qpolynomial_has_equal_dim(obj1.v, obj2.v)) {
1652 obj1 = to_union(ctx, obj1);
1653 obj2 = to_union(ctx, obj2);
1654 }
1655 if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1656 !isl_pw_qpolynomial_fold_has_equal_dim(obj1.v, obj2.v)) {
1657 obj1 = to_union(ctx, obj1);
1658 obj2 = to_union(ctx, obj2);
1659 }
1660 obj1.v = obj1.type->add(obj1.v, obj2.v);
1661 return obj1;
1662 error:
1663 obj1.type->free(obj1.v);
1664 obj2.type->free(obj2.v);
1665 obj1.type = isl_obj_none;
1666 obj1.v = NULL;
1667 return obj1;
1668 }
1669
1670 static struct isl_obj obj_read(struct isl_stream *s, int nparam)
1671 {
1672 isl_basic_map *bmap = NULL;
1673 struct isl_token *tok;
1674 struct vars *v = NULL;
1675 struct isl_obj obj = { isl_obj_set, NULL };
1676
1677 tok = isl_stream_next_token(s);
1678 if (!tok) {
1679 isl_stream_error(s, NULL, "unexpected EOF");
1680 goto error;
1681 }
1682 if (tok->type == ISL_TOKEN_VALUE) {
1683 struct isl_map *map;
1684 isl_stream_push_token(s, tok);
1685 map = map_read_polylib(s, nparam);
1686 if (!map)
1687 goto error;
1688 if (isl_map_dim(map, isl_dim_in) > 0)
1689 obj.type = isl_obj_map;
1690 obj.v = map;
1691 return obj;
1692 }
1693 v = vars_new(s->ctx);
1694 if (!v) {
1695 isl_stream_push_token(s, tok);
1696 goto error;
1697 }
1698 bmap = isl_basic_map_alloc(s->ctx, 0, 0, 0, 0, 0, 0);
1699 if (tok->type == '[') {
1700 isl_stream_push_token(s, tok);
1701 bmap = read_tuple(s, bmap, isl_dim_param, v);
1702 if (!bmap)
1703 goto error;
1704 if (nparam >= 0)
1705 isl_assert(s->ctx, nparam == v->n, goto error);
1706 tok = isl_stream_next_token(s);
1707 if (!tok || tok->type != ISL_TOKEN_TO) {
1708 isl_stream_error(s, tok, "expecting '->'");
1709 if (tok)
1710 isl_stream_push_token(s, tok);
1711 goto error;
1712 }
1713 isl_token_free(tok);
1714 tok = isl_stream_next_token(s);
1715 } else if (nparam > 0)
1716 bmap = isl_basic_map_add(bmap, isl_dim_param, nparam);
1717 if (!tok || tok->type != '{') {
1718 isl_stream_error(s, tok, "expecting '{'");
1719 if (tok)
1720 isl_stream_push_token(s, tok);
1721 goto error;
1722 }
1723 isl_token_free(tok);
1724
1725 tok = isl_stream_next_token(s);
1726 if (!tok)
1727 ;
1728 else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
1729 isl_token_free(tok);
1730 if (isl_stream_eat(s, '='))
1731 goto error;
1732 bmap = read_tuple(s, bmap, isl_dim_param, v);
1733 if (!bmap)
1734 goto error;
1735 if (nparam >= 0)
1736 isl_assert(s->ctx, nparam == v->n, goto error);
1737 } else if (tok->type == '}') {
1738 obj.type = isl_obj_union_set;
1739 obj.v = isl_union_set_empty(isl_basic_map_get_dim(bmap));
1740 isl_token_free(tok);
1741 goto done;
1742 } else
1743 isl_stream_push_token(s, tok);
1744
1745 for (;;) {
1746 struct isl_obj o;
1747 tok = NULL;
1748 o = obj_read_body(s, isl_basic_map_copy(bmap), v);
1749 if (o.type == isl_obj_none || !o.v)
1750 goto error;
1751 if (!obj.v)
1752 obj = o;
1753 else {
1754 obj = obj_add(s->ctx, obj, o);
1755 if (obj.type == isl_obj_none || !obj.v)
1756 goto error;
1757 }
1758 tok = isl_stream_next_token(s);
1759 if (!tok || tok->type != ';')
1760 break;
1761 isl_token_free(tok);
1762 }
1763
1764 if (tok && tok->type == '}') {
1765 isl_token_free(tok);
1766 } else {
1767 isl_stream_error(s, tok, "unexpected isl_token");
1768 if (tok)
1769 isl_token_free(tok);
1770 goto error;
1771 }
1772 done:
1773 vars_free(v);
1774 isl_basic_map_free(bmap);
1775
1776 return obj;
1777 error:
1778 isl_basic_map_free(bmap);
1779 obj.type->free(obj.v);
1780 if (v)
1781 vars_free(v);
1782 obj.v = NULL;
1783 return obj;
1784 }
1785
1786 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
1787 {
1788 return obj_read(s, -1);
1789 }
1790
1791 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s, int nparam)
1792 {
1793 struct isl_obj obj;
1794 struct isl_map *map;
1795
1796 obj = obj_read(s, nparam);
1797 if (obj.v)
1798 isl_assert(s->ctx, obj.type == isl_obj_map ||
1799 obj.type == isl_obj_set, goto error);
1800
1801 return obj.v;
1802 error:
1803 obj.type->free(obj.v);
1804 return NULL;
1805 }
1806
1807 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s, int nparam)
1808 {
1809 struct isl_obj obj;
1810 struct isl_set *set;
1811
1812 obj = obj_read(s, nparam);
1813 if (obj.v)
1814 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
1815
1816 return obj.v;
1817 error:
1818 obj.type->free(obj.v);
1819 return NULL;
1820 }
1821
1822 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
1823 {
1824 struct isl_obj obj;
1825 isl_union_map *umap;
1826
1827 obj = obj_read(s, -1);
1828 if (obj.type == isl_obj_map) {
1829 obj.type = isl_obj_union_map;
1830 obj.v = isl_union_map_from_map(obj.v);
1831 }
1832 if (obj.type == isl_obj_set) {
1833 obj.type = isl_obj_union_set;
1834 obj.v = isl_union_set_from_set(obj.v);
1835 }
1836 if (obj.v)
1837 isl_assert(s->ctx, obj.type == isl_obj_union_map ||
1838 obj.type == isl_obj_union_set, goto error);
1839
1840 return obj.v;
1841 error:
1842 obj.type->free(obj.v);
1843 return NULL;
1844 }
1845
1846 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
1847 {
1848 struct isl_obj obj;
1849 isl_union_set *uset;
1850
1851 obj = obj_read(s, -1);
1852 if (obj.type == isl_obj_set) {
1853 obj.type = isl_obj_union_set;
1854 obj.v = isl_union_set_from_set(obj.v);
1855 }
1856 if (obj.v)
1857 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
1858
1859 return obj.v;
1860 error:
1861 obj.type->free(obj.v);
1862 return NULL;
1863 }
1864
1865 static struct isl_basic_map *basic_map_read(struct isl_stream *s, int nparam)
1866 {
1867 struct isl_obj obj;
1868 struct isl_map *map;
1869 struct isl_basic_map *bmap;
1870
1871 obj = obj_read(s, nparam);
1872 map = obj.v;
1873 if (!map)
1874 return NULL;
1875
1876 isl_assert(map->ctx, map->n <= 1, goto error);
1877
1878 if (map->n == 0)
1879 bmap = isl_basic_map_empty_like_map(map);
1880 else
1881 bmap = isl_basic_map_copy(map->p[0]);
1882
1883 isl_map_free(map);
1884
1885 return bmap;
1886 error:
1887 isl_map_free(map);
1888 return NULL;
1889 }
1890
1891 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
1892 FILE *input, int nparam)
1893 {
1894 struct isl_basic_map *bmap;
1895 struct isl_stream *s = isl_stream_new_file(ctx, input);
1896 if (!s)
1897 return NULL;
1898 bmap = basic_map_read(s, nparam);
1899 isl_stream_free(s);
1900 return bmap;
1901 }
1902
1903 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
1904 FILE *input, int nparam)
1905 {
1906 struct isl_basic_map *bmap;
1907 bmap = isl_basic_map_read_from_file(ctx, input, nparam);
1908 if (!bmap)
1909 return NULL;
1910 isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
1911 return (struct isl_basic_set *)bmap;
1912 error:
1913 isl_basic_map_free(bmap);
1914 return NULL;
1915 }
1916
1917 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
1918 const char *str, int nparam)
1919 {
1920 struct isl_basic_map *bmap;
1921 struct isl_stream *s = isl_stream_new_str(ctx, str);
1922 if (!s)
1923 return NULL;
1924 bmap = basic_map_read(s, nparam);
1925 isl_stream_free(s);
1926 return bmap;
1927 }
1928
1929 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
1930 const char *str, int nparam)
1931 {
1932 struct isl_basic_map *bmap;
1933 bmap = isl_basic_map_read_from_str(ctx, str, nparam);
1934 if (!bmap)
1935 return NULL;
1936 isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
1937 return (struct isl_basic_set *)bmap;
1938 error:
1939 isl_basic_map_free(bmap);
1940 return NULL;
1941 }
1942
1943 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
1944 FILE *input, int nparam)
1945 {
1946 struct isl_map *map;
1947 struct isl_stream *s = isl_stream_new_file(ctx, input);
1948 if (!s)
1949 return NULL;
1950 map = isl_stream_read_map(s, nparam);
1951 isl_stream_free(s);
1952 return map;
1953 }
1954
1955 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
1956 const char *str, int nparam)
1957 {
1958 struct isl_map *map;
1959 struct isl_stream *s = isl_stream_new_str(ctx, str);
1960 if (!s)
1961 return NULL;
1962 map = isl_stream_read_map(s, nparam);
1963 isl_stream_free(s);
1964 return map;
1965 }
1966
1967 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
1968 FILE *input, int nparam)
1969 {
1970 struct isl_map *map;
1971 map = isl_map_read_from_file(ctx, input, nparam);
1972 if (!map)
1973 return NULL;
1974 isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
1975 return (struct isl_set *)map;
1976 error:
1977 isl_map_free(map);
1978 return NULL;
1979 }
1980
1981 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
1982 const char *str, int nparam)
1983 {
1984 struct isl_map *map;
1985 map = isl_map_read_from_str(ctx, str, nparam);
1986 if (!map)
1987 return NULL;
1988 isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
1989 return (struct isl_set *)map;
1990 error:
1991 isl_map_free(map);
1992 return NULL;
1993 }
1994
1995 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
1996 const char *str)
1997 {
1998 isl_union_map *umap;
1999 struct isl_stream *s = isl_stream_new_str(ctx, str);
2000 if (!s)
2001 return NULL;
2002 umap = isl_stream_read_union_map(s);
2003 isl_stream_free(s);
2004 return umap;
2005 }
2006
2007 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2008 const char *str)
2009 {
2010 isl_union_set *uset;
2011 struct isl_stream *s = isl_stream_new_str(ctx, str);
2012 if (!s)
2013 return NULL;
2014 uset = isl_stream_read_union_set(s);
2015 isl_stream_free(s);
2016 return uset;
2017 }
2018
2019 static char *next_line(FILE *input, char *line, unsigned len)
2020 {
2021 char *p;
2022
2023 do {
2024 if (!(p = fgets(line, len, input)))
2025 return NULL;
2026 while (isspace(*p) && *p != '\n')
2027 ++p;
2028 } while (*p == '#' || *p == '\n');
2029
2030 return p;
2031 }
2032
2033 static struct isl_vec *isl_vec_read_from_file_polylib(struct isl_ctx *ctx,
2034 FILE *input)
2035 {
2036 struct isl_vec *vec = NULL;
2037 char line[1024];
2038 char val[1024];
2039 char *p;
2040 unsigned size;
2041 int j;
2042 int n;
2043 int offset;
2044
2045 isl_assert(ctx, next_line(input, line, sizeof(line)), return NULL);
2046 isl_assert(ctx, sscanf(line, "%u", &size) == 1, return NULL);
2047
2048 vec = isl_vec_alloc(ctx, size);
2049
2050 p = next_line(input, line, sizeof(line));
2051 isl_assert(ctx, p, goto error);
2052
2053 for (j = 0; j < size; ++j) {
2054 n = sscanf(p, "%s%n", val, &offset);
2055 isl_assert(ctx, n != 0, goto error);
2056 isl_int_read(vec->el[j], val);
2057 p += offset;
2058 }
2059
2060 return vec;
2061 error:
2062 isl_vec_free(vec);
2063 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 if (input_format == ISL_FORMAT_POLYLIB)
2070 return isl_vec_read_from_file_polylib(ctx, input);
2071 else
2072 isl_assert(ctx, 0, return NULL);
2073 }
2074
2075 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2076 struct isl_stream *s)
2077 {
2078 struct isl_obj obj;
2079 struct isl_pw_qpolynomial *pwqp;
2080
2081 obj = obj_read(s, -1);
2082 if (obj.v)
2083 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2084 goto error);
2085
2086 return obj.v;
2087 error:
2088 obj.type->free(obj.v);
2089 return NULL;
2090 }
2091
2092 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2093 const char *str)
2094 {
2095 isl_pw_qpolynomial *pwqp;
2096 struct isl_stream *s = isl_stream_new_str(ctx, str);
2097 if (!s)
2098 return NULL;
2099 pwqp = isl_stream_read_pw_qpolynomial(s);
2100 isl_stream_free(s);
2101 return pwqp;
2102 }
Integer set library