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