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