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