isl_input.c: merge functions for reading PolyLib and omega-like input
[platform/upstream/isl.git] / isl_input.c
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_stream.h"
20 #include "isl_map_private.h"
21
22 struct variable {
23         char                    *name;
24         int                      pos;
25         struct variable         *next;
26 };
27
28 struct vars {
29         struct isl_ctx  *ctx;
30         int              n;
31         struct variable *v;
32 };
33
34 static struct vars *vars_new(struct isl_ctx *ctx)
35 {
36         struct vars *v;
37         v = isl_alloc_type(ctx, struct vars);
38         if (!v)
39                 return NULL;
40         v->ctx = ctx;
41         v->n = 0;
42         v->v = NULL;
43         return v;
44 }
45
46 static void variable_free(struct variable *var)
47 {
48         while (var) {
49                 struct variable *next = var->next;
50                 free(var->name);
51                 free(var);
52                 var = next;
53         }
54 }
55
56 static void vars_free(struct vars *v)
57 {
58         if (!v)
59                 return;
60         variable_free(v->v);
61         free(v);
62 }
63
64 static struct variable *variable_new(struct vars *v, const char *name, int len,
65                                 int pos)
66 {
67         struct variable *var;
68         var = isl_alloc_type(v->ctx, struct variable);
69         if (!var)
70                 goto error;
71         var->name = strdup(name);
72         var->name[len] = '\0';
73         var->pos = pos;
74         var->next = v->v;
75         return var;
76 error:
77         variable_free(v->v);
78         return NULL;
79 }
80
81 static int vars_pos(struct vars *v, const char *s, int len)
82 {
83         int pos;
84         struct variable *q;
85
86         if (len == -1)
87                 len = strlen(s);
88         for (q = v->v; q; q = q->next) {
89                 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
90                         break;
91         }
92         if (q)
93                 pos = q->pos;
94         else {
95                 pos = v->n;
96                 v->v = variable_new(v, s, len, v->n);
97                 if (!v->v)
98                         return -1;
99                 v->n++;
100         }
101         return pos;
102 }
103
104 static struct vars *read_var_list(struct isl_stream *s, struct vars *v)
105 {
106         struct isl_token *tok;
107
108         while ((tok = isl_stream_next_token(s)) != NULL) {
109                 int p;
110                 int n = v->n;
111
112                 if (tok->type != ISL_TOKEN_IDENT)
113                         break;
114
115                 p = vars_pos(v, tok->u.s, -1);
116                 if (p < 0)
117                         goto error;
118                 if (p < n) {
119                         isl_stream_error(s, tok, "expecting unique identifier");
120                         goto error;
121                 }
122                 isl_token_free(tok);
123                 tok = isl_stream_next_token(s);
124                 if (!tok || tok->type != ',')
125                         break;
126
127                 isl_token_free(tok);
128         }
129         if (tok)
130                 isl_stream_push_token(s, tok);
131
132         return v;
133 error:
134         isl_token_free(tok);
135         vars_free(v);
136         return NULL;
137 }
138
139 static struct vars *read_tuple(struct isl_stream *s, struct vars *v)
140 {
141         struct isl_token *tok;
142
143         tok = isl_stream_next_token(s);
144         if (!tok || tok->type != '[') {
145                 isl_stream_error(s, tok, "expecting '['");
146                 goto error;
147         }
148         isl_token_free(tok);
149         v = read_var_list(s, v);
150         tok = isl_stream_next_token(s);
151         if (!tok || tok->type != ']') {
152                 isl_stream_error(s, tok, "expecting ']'");
153                 goto error;
154         }
155         isl_token_free(tok);
156
157         return v;
158 error:
159         if (tok)
160                 isl_token_free(tok);
161         vars_free(v);
162         return NULL;
163 }
164
165 static struct isl_basic_map *add_constraints(struct isl_stream *s,
166         struct vars **v, struct isl_basic_map *bmap);
167
168 static struct isl_basic_map *add_exists(struct isl_stream *s,
169         struct vars **v, struct isl_basic_map *bmap)
170 {
171         struct isl_token *tok;
172         int n = (*v)->n;
173         int extra;
174         int seen_paren = 0;
175         int i;
176         unsigned total;
177
178         tok = isl_stream_next_token(s);
179         if (!tok)
180                 goto error;
181         if (tok->type == '(') {
182                 seen_paren = 1;
183                 isl_token_free(tok);
184         } else
185                 isl_stream_push_token(s, tok);
186         *v = read_var_list(s, *v);
187         if (!*v)
188                 goto error;
189         extra = (*v)->n - n;
190         bmap = isl_basic_map_cow(bmap);
191         bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
192                         extra, 0, 0);
193         total = isl_basic_map_total_dim(bmap);
194         for (i = 0; i < extra; ++i) {
195                 int k;
196                 if ((k = isl_basic_map_alloc_div(bmap)) < 0)
197                         goto error;
198                 isl_seq_clr(bmap->div[k], 1+1+total);
199         }
200         if (!bmap)
201                 return NULL;
202         if (isl_stream_eat(s, ':'))
203                 goto error;
204         bmap = add_constraints(s, v, bmap);
205         if (seen_paren && isl_stream_eat(s, ')'))
206                 goto error;
207         return bmap;
208 error:
209         isl_basic_map_free(bmap);
210         return NULL;
211 }
212
213 static struct isl_basic_map *add_constraint(struct isl_stream *s,
214         struct vars **v, struct isl_basic_map *bmap)
215 {
216         unsigned total = isl_basic_map_total_dim(bmap);
217         int k;
218         int sign = 1;
219         int equality = 0;
220         int op = 0;
221         struct isl_token *tok = NULL;
222
223         tok = isl_stream_next_token(s);
224         if (!tok)
225                 goto error;
226         if (tok->type == ISL_TOKEN_EXISTS) {
227                 isl_token_free(tok);
228                 return add_exists(s, v, bmap);
229         }
230         isl_stream_push_token(s, tok);
231
232         bmap = isl_basic_map_cow(bmap);
233         bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
234         k = isl_basic_map_alloc_inequality(bmap);
235         if (k < 0)
236                 goto error;
237         isl_seq_clr(bmap->ineq[k], 1+total);
238
239         for (;;) {
240                 tok = isl_stream_next_token(s);
241                 if (!tok) {
242                         isl_stream_error(s, NULL, "unexpected EOF");
243                         goto error;
244                 }
245                 if (tok->type == ISL_TOKEN_IDENT) {
246                         int n = (*v)->n;
247                         int pos = vars_pos(*v, tok->u.s, -1);
248                         if (pos < 0)
249                                 goto error;
250                         if (pos >= n) {
251                                 isl_stream_error(s, tok, "unknown identifier");
252                                 goto error;
253                         }
254                         if (sign > 0)
255                                 isl_int_add_ui(bmap->ineq[k][1+pos],
256                                                 bmap->ineq[k][1+pos], 1);
257                         else
258                                 isl_int_sub_ui(bmap->ineq[k][1+pos],
259                                                 bmap->ineq[k][1+pos], 1);
260                 } else if (tok->type == ISL_TOKEN_VALUE) {
261                         struct isl_token *tok2;
262                         int n = (*v)->n;
263                         int pos = -1;
264                         tok2 = isl_stream_next_token(s);
265                         if (tok2 && tok2->type == ISL_TOKEN_IDENT) {
266                                 pos = vars_pos(*v, tok2->u.s, -1);
267                                 if (pos < 0)
268                                         goto error;
269                                 if (pos >= n) {
270                                         isl_stream_error(s, tok2,
271                                                 "unknown identifier");
272                                         isl_token_free(tok2);
273                                         goto error;
274                                 }
275                                 isl_token_free(tok2);
276                         } else if (tok2)
277                                 isl_stream_push_token(s, tok2);
278                         if (sign < 0)
279                                 isl_int_neg(tok->u.v, tok->u.v);
280                         isl_int_add(bmap->ineq[k][1+pos],
281                                         bmap->ineq[k][1+pos], tok->u.v);
282                 } else if (tok->type == '+') {
283                         /* nothing */
284                 } else if (tok->type == ISL_TOKEN_LE) {
285                         op = 1;
286                         isl_seq_neg(bmap->ineq[k], bmap->ineq[k], 1+total);
287                 } else if (tok->type == ISL_TOKEN_GE) {
288                         op = 1;
289                         sign = -1;
290                 } else if (tok->type == '=') {
291                         if (op) {
292                                 isl_stream_error(s, tok, "too many operators");
293                                 goto error;
294                         }
295                         op = 1;
296                         equality = 1;
297                         sign = -1;
298                 } else {
299                         isl_stream_push_token(s, tok);
300                         break;
301                 }
302                 isl_token_free(tok);
303         }
304         tok = NULL;
305         if (!op) {
306                 isl_stream_error(s, tok, "missing operator");
307                 goto error;
308         }
309         if (equality)
310                 isl_basic_map_inequality_to_equality(bmap, k);
311         return bmap;
312 error:
313         if (tok)
314                 isl_token_free(tok);
315         isl_basic_map_free(bmap);
316         return NULL;
317 }
318
319 static struct isl_basic_map *add_constraints(struct isl_stream *s,
320         struct vars **v, struct isl_basic_map *bmap)
321 {
322         struct isl_token *tok;
323
324         for (;;) {
325                 bmap = add_constraint(s, v, bmap);
326                 if (!bmap)
327                         return NULL;
328                 tok = isl_stream_next_token(s);
329                 if (!tok) {
330                         isl_stream_error(s, NULL, "unexpected EOF");
331                         goto error;
332                 }
333                 if (tok->type != ISL_TOKEN_AND)
334                         break;
335                 isl_token_free(tok);
336         }
337         isl_stream_push_token(s, tok);
338
339         return bmap;
340 error:
341         if (tok)
342                 isl_token_free(tok);
343         isl_basic_map_free(bmap);
344         return NULL;
345 }
346
347 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
348         struct isl_stream *s, __isl_take isl_basic_map *bmap)
349 {
350         int j;
351         struct isl_token *tok;
352         int type;
353         int k;
354         isl_int *c;
355         unsigned nparam;
356         unsigned dim;
357
358         if (!bmap)
359                 return NULL;
360
361         nparam = isl_basic_map_dim(bmap, isl_dim_param);
362         dim = isl_basic_map_dim(bmap, isl_dim_out);
363
364         tok = isl_stream_next_token(s);
365         if (!tok || tok->type != ISL_TOKEN_VALUE) {
366                 isl_stream_error(s, tok, "expecting coefficient");
367                 if (tok)
368                         isl_stream_push_token(s, tok);
369                 goto error;
370         }
371         if (!tok->on_new_line) {
372                 isl_stream_error(s, tok, "coefficient should appear on new line");
373                 isl_stream_push_token(s, tok);
374                 goto error;
375         }
376
377         type = isl_int_get_si(tok->u.v);
378         isl_token_free(tok);
379
380         isl_assert(s->ctx, type == 0 || type == 1, goto error);
381         if (type == 0) {
382                 k = isl_basic_map_alloc_equality(bmap);
383                 c = bmap->eq[k];
384         } else {
385                 k = isl_basic_map_alloc_inequality(bmap);
386                 c = bmap->ineq[k];
387         }
388         if (k < 0)
389                 goto error;
390
391         for (j = 0; j < dim; ++j) {
392                 tok = isl_stream_next_token(s);
393                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
394                         isl_stream_error(s, tok, "expecting coefficient");
395                         if (tok)
396                                 isl_stream_push_token(s, tok);
397                         goto error;
398                 }
399                 isl_int_set(c[1 + nparam + j], tok->u.v);
400                 isl_token_free(tok);
401         }
402         for (j = 0; j < nparam; ++j) {
403                 tok = isl_stream_next_token(s);
404                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
405                         isl_stream_error(s, tok, "expecting coefficient");
406                         if (tok)
407                                 isl_stream_push_token(s, tok);
408                         goto error;
409                 }
410                 isl_int_set(c[1 + j], tok->u.v);
411                 isl_token_free(tok);
412         }
413         tok = isl_stream_next_token(s);
414         if (!tok || tok->type != ISL_TOKEN_VALUE) {
415                 isl_stream_error(s, tok, "expecting coefficient");
416                 if (tok)
417                         isl_stream_push_token(s, tok);
418                 goto error;
419         }
420         isl_int_set(c[0], tok->u.v);
421         isl_token_free(tok);
422
423         return bmap;
424 error:
425         isl_basic_map_free(bmap);
426         return NULL;
427 }
428
429 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s,
430         int nparam)
431 {
432         int i;
433         struct isl_token *tok;
434         struct isl_token *tok2;
435         int n_row, n_col;
436         int on_new_line;
437         unsigned dim;
438         struct isl_basic_map *bmap = NULL;
439
440         if (nparam < 0)
441                 nparam = 0;
442
443         tok = isl_stream_next_token(s);
444         if (!tok) {
445                 isl_stream_error(s, NULL, "unexpected EOF");
446                 return NULL;
447         }
448         tok2 = isl_stream_next_token(s);
449         if (!tok2) {
450                 isl_token_free(tok);
451                 isl_stream_error(s, NULL, "unexpected EOF");
452                 return NULL;
453         }
454         n_row = isl_int_get_si(tok->u.v);
455         n_col = isl_int_get_si(tok2->u.v);
456         on_new_line = tok2->on_new_line;
457         isl_token_free(tok2);
458         isl_token_free(tok);
459         isl_assert(s->ctx, !on_new_line, return NULL);
460         isl_assert(s->ctx, n_row >= 0, return NULL);
461         isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
462         dim = n_col - 2 - nparam;
463         bmap = isl_basic_map_alloc(s->ctx, nparam, 0, dim, 0, n_row, n_row);
464         if (!bmap)
465                 return NULL;
466
467         for (i = 0; i < n_row; ++i)
468                 bmap = basic_map_read_polylib_constraint(s, bmap);
469
470         bmap = isl_basic_map_simplify(bmap);
471         bmap = isl_basic_map_finalize(bmap);
472         return bmap;
473 }
474
475 static struct isl_map *map_read_polylib(struct isl_stream *s, int nparam)
476 {
477         struct isl_token *tok;
478         struct isl_token *tok2;
479         int i, n;
480         struct isl_map *map;
481
482         tok = isl_stream_next_token(s);
483         if (!tok) {
484                 isl_stream_error(s, NULL, "unexpected EOF");
485                 return NULL;
486         }
487         tok2 = isl_stream_next_token(s);
488         if (!tok2) {
489                 isl_token_free(tok);
490                 isl_stream_error(s, NULL, "unexpected EOF");
491                 return NULL;
492         }
493         if (!tok2->on_new_line) {
494                 isl_stream_push_token(s, tok2);
495                 isl_stream_push_token(s, tok);
496                 return isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
497         }
498         isl_stream_push_token(s, tok2);
499         n = isl_int_get_si(tok->u.v);
500         isl_token_free(tok);
501
502         isl_assert(s->ctx, n >= 1, return NULL);
503
504         map = isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
505
506         for (i = 1; i < n; ++i)
507                 map = isl_map_union(map,
508                         isl_map_from_basic_map(basic_map_read_polylib(s, nparam)));
509
510         return map;
511 }
512
513 static struct isl_map *map_read(struct isl_stream *s, int nparam)
514 {
515         struct isl_basic_map *bmap = NULL;
516         struct isl_token *tok;
517         struct vars *v = NULL;
518         int n1;
519         int n2;
520
521         tok = isl_stream_next_token(s);
522         if (!tok) {
523                 isl_stream_error(s, NULL, "unexpected EOF");
524                 goto error;
525         }
526         if (tok->type == ISL_TOKEN_VALUE) {
527                 isl_stream_push_token(s, tok);
528                 return map_read_polylib(s, nparam);
529         }
530         if (tok->type != '{') {
531                 isl_stream_error(s, tok, "expecting '{'");
532                 if (tok)
533                         isl_stream_push_token(s, tok);
534                 goto error;
535         }
536         isl_token_free(tok);
537         isl_assert(s->ctx, nparam == 0, goto error);
538         v = vars_new(s->ctx);
539         v = read_tuple(s, v);
540         if (!v)
541                 return NULL;
542         n1 = v->n;
543         tok = isl_stream_next_token(s);
544         if (tok && tok->type == ISL_TOKEN_TO) {
545                 isl_token_free(tok);
546                 v = read_tuple(s, v);
547                 if (!v)
548                         return NULL;
549                 n2 = v->n - n1;
550         } else {
551                 if (tok)
552                         isl_stream_push_token(s, tok);
553                 n2 = n1;
554                 n1 = 0;
555         }
556         bmap = isl_basic_map_alloc(s->ctx, 0, n1, n2, 0, 0,0);
557         if (!bmap)
558                 goto error;
559         tok = isl_stream_next_token(s);
560         if (tok && tok->type == ':') {
561                 isl_token_free(tok);
562                 bmap = add_constraints(s, &v, bmap);
563                 tok = isl_stream_next_token(s);
564         }
565         if (tok && tok->type == '}') {
566                 isl_token_free(tok);
567         } else {
568                 isl_stream_error(s, tok, "unexpected isl_token");
569                 if (tok)
570                         isl_token_free(tok);
571                 goto error;
572         }
573         vars_free(v);
574
575         bmap = isl_basic_map_simplify(bmap);
576         bmap = isl_basic_map_finalize(bmap);
577         return isl_map_from_basic_map(bmap);
578 error:
579         isl_basic_map_free(bmap);
580         if (v)
581                 vars_free(v);
582         return NULL;
583 }
584
585 static struct isl_basic_map *basic_map_read(struct isl_stream *s, int nparam)
586 {
587         struct isl_map *map;
588         struct isl_basic_map *bmap;
589
590         map = map_read(s, nparam);
591         if (!map)
592                 return NULL;
593
594         isl_assert(map->ctx, map->n <= 1, goto error);
595
596         if (map->n == 0)
597                 bmap = isl_basic_map_empty_like_map(map);
598         else
599                 bmap = isl_basic_map_copy(map->p[0]);
600
601         isl_map_free(map);
602
603         return bmap;
604 error:
605         isl_map_free(map);
606         return NULL;
607 }
608
609 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
610                 FILE *input, unsigned nparam, unsigned input_format)
611 {
612         struct isl_basic_map *bmap;
613         struct isl_stream *s = isl_stream_new_file(ctx, input);
614         if (!s)
615                 return NULL;
616         bmap = basic_map_read(s, nparam);
617         isl_stream_free(s);
618         return bmap;
619 }
620
621 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
622                 FILE *input, unsigned nparam, unsigned input_format)
623 {
624         struct isl_basic_map *bmap;
625         bmap = isl_basic_map_read_from_file(ctx, input, nparam, input_format);
626         if (!bmap)
627                 return NULL;
628         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
629         return (struct isl_basic_set *)bmap;
630 error:
631         isl_basic_map_free(bmap);
632         return NULL;
633 }
634
635 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
636                 const char *str, unsigned nparam, unsigned input_format)
637 {
638         struct isl_basic_map *bmap;
639         struct isl_stream *s = isl_stream_new_str(ctx, str);
640         if (!s)
641                 return NULL;
642         bmap = basic_map_read(s, nparam);
643         isl_stream_free(s);
644         return bmap;
645 }
646
647 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
648                 const char *str, unsigned nparam, unsigned input_format)
649 {
650         struct isl_basic_map *bmap;
651         bmap = isl_basic_map_read_from_str(ctx, str, nparam, input_format);
652         if (!bmap)
653                 return NULL;
654         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
655         return (struct isl_basic_set *)bmap;
656 error:
657         isl_basic_map_free(bmap);
658         return NULL;
659 }
660
661 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
662                 FILE *input, unsigned nparam, unsigned input_format)
663 {
664         struct isl_map *map;
665         struct isl_stream *s = isl_stream_new_file(ctx, input);
666         if (!s)
667                 return NULL;
668         map = map_read(s, nparam);
669         isl_stream_free(s);
670         return map;
671 }
672
673 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
674                 FILE *input, unsigned nparam, unsigned input_format)
675 {
676         struct isl_map *map;
677         map = isl_map_read_from_file(ctx, input, nparam, input_format);
678         if (!map)
679                 return NULL;
680         isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
681         return (struct isl_set *)map;
682 error:
683         isl_map_free(map);
684         return NULL;
685 }
686
687 static char *next_line(FILE *input, char *line, unsigned len)
688 {
689         char *p;
690
691         do {
692                 if (!(p = fgets(line, len, input)))
693                         return NULL;
694                 while (isspace(*p) && *p != '\n')
695                         ++p;
696         } while (*p == '#' || *p == '\n');
697
698         return p;
699 }
700
701 static struct isl_vec *isl_vec_read_from_file_polylib(struct isl_ctx *ctx,
702                 FILE *input)
703 {
704         struct isl_vec *vec = NULL;
705         char line[1024];
706         char val[1024];
707         char *p;
708         unsigned size;
709         int j;
710         int n;
711         int offset;
712
713         isl_assert(ctx, next_line(input, line, sizeof(line)), return NULL);
714         isl_assert(ctx, sscanf(line, "%u", &size) == 1, return NULL);
715
716         vec = isl_vec_alloc(ctx, size);
717
718         p = next_line(input, line, sizeof(line));
719         isl_assert(ctx, p, goto error);
720
721         for (j = 0; j < size; ++j) {
722                 n = sscanf(p, "%s%n", val, &offset);
723                 isl_assert(ctx, n != 0, goto error);
724                 isl_int_read(vec->el[j], val);
725                 p += offset;
726         }
727
728         return vec;
729 error:
730         isl_vec_free(vec);
731         return NULL;
732 }
733
734 struct isl_vec *isl_vec_read_from_file(struct isl_ctx *ctx,
735                 FILE *input, unsigned input_format)
736 {
737         if (input_format == ISL_FORMAT_POLYLIB)
738                 return isl_vec_read_from_file_polylib(ctx, input);
739         else
740                 isl_assert(ctx, 0, return NULL);
741 }