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