364389324a299ef310c43deadc6d8ea034d467d5
[platform/upstream/isl.git] / isl_stream.c
1 /*
2  * Copyright 2008-2009 Katholieke Universiteit Leuven
3  *
4  * Use of this software is governed by the GNU LGPLv2.1 license
5  *
6  * Written by Sven Verdoolaege, K.U.Leuven, Departement
7  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8  */
9
10 #include <ctype.h>
11 #include <string.h>
12 #include <strings.h>
13 #include <isl/ctx.h>
14 #include <isl_stream_private.h>
15 #include <isl/map.h>
16 #include <isl/aff.h>
17
18 struct isl_keyword {
19         char                    *name;
20         enum isl_token_type     type;
21 };
22
23 static int same_name(const void *entry, const void *val)
24 {
25         const struct isl_keyword *keyword = (const struct isl_keyword *)entry;
26
27         return !strcmp(keyword->name, val);
28 }
29
30 enum isl_token_type isl_stream_register_keyword(struct isl_stream *s,
31         const char *name)
32 {
33         struct isl_hash_table_entry *entry;
34         struct isl_keyword *keyword;
35         uint32_t name_hash;
36
37         if (!s->keywords) {
38                 s->keywords = isl_hash_table_alloc(s->ctx, 10);
39                 if (!s->keywords)
40                         return ISL_TOKEN_ERROR;
41                 s->next_type = ISL_TOKEN_LAST;
42         }
43
44         name_hash = isl_hash_string(isl_hash_init(), name);
45
46         entry = isl_hash_table_find(s->ctx, s->keywords, name_hash,
47                                         same_name, name, 1);
48         if (!entry)
49                 return ISL_TOKEN_ERROR;
50         if (entry->data) {
51                 keyword = entry->data;
52                 return keyword->type;
53         }
54
55         keyword = isl_calloc_type(s->ctx, struct isl_keyword);
56         if (!keyword)
57                 return ISL_TOKEN_ERROR;
58         keyword->type = s->next_type++;
59         keyword->name = strdup(name);
60         if (!keyword->name) {
61                 free(keyword);
62                 return ISL_TOKEN_ERROR;
63         }
64         entry->data = keyword;
65
66         return keyword->type;
67 }
68
69 struct isl_token *isl_token_new(isl_ctx *ctx,
70         int line, int col, unsigned on_new_line)
71 {
72         struct isl_token *tok = isl_alloc_type(ctx, struct isl_token);
73         if (!tok)
74                 return NULL;
75         tok->line = line;
76         tok->col = col;
77         tok->on_new_line = on_new_line;
78         tok->is_keyword = 0;
79         tok->u.s = NULL;
80         return tok;
81 }
82
83 void isl_token_free(struct isl_token *tok)
84 {
85         if (!tok)
86                 return;
87         if (tok->type == ISL_TOKEN_VALUE)
88                 isl_int_clear(tok->u.v);
89         else if (tok->type == ISL_TOKEN_MAP)
90                 isl_map_free(tok->u.map);
91         else if (tok->type == ISL_TOKEN_AFF)
92                 isl_pw_aff_free(tok->u.pwaff);
93         else
94                 free(tok->u.s);
95         free(tok);
96 }
97
98 void isl_stream_error(struct isl_stream *s, struct isl_token *tok, char *msg)
99 {
100         int line = tok ? tok->line : s->line;
101         int col = tok ? tok->col : s->col;
102         fprintf(stderr, "syntax error (%d, %d): %s\n", line, col, msg);
103         if (tok) {
104                 if (tok->type < 256)
105                         fprintf(stderr, "got '%c'\n", tok->type);
106                 else if (tok->type == ISL_TOKEN_IDENT)
107                         fprintf(stderr, "got ident '%s'\n", tok->u.s);
108                 else if (tok->is_keyword)
109                         fprintf(stderr, "got keyword '%s'\n", tok->u.s);
110                 else if (tok->type == ISL_TOKEN_VALUE) {
111                         fprintf(stderr, "got value '");
112                         isl_int_print(stderr, tok->u.v, 0);
113                         fprintf(stderr, "'\n");
114                 } else if (tok->type == ISL_TOKEN_MAP) {
115                         isl_printer *p;
116                         fprintf(stderr, "got map '");
117                         p = isl_printer_to_file(s->ctx, stderr);
118                         p = isl_printer_print_map(p, tok->u.map);
119                         isl_printer_free(p);
120                         fprintf(stderr, "'\n");
121                 } else if (tok->type == ISL_TOKEN_AFF) {
122                         isl_printer *p;
123                         fprintf(stderr, "got affine expression '");
124                         p = isl_printer_to_file(s->ctx, stderr);
125                         p = isl_printer_print_pw_aff(p, tok->u.pwaff);
126                         isl_printer_free(p);
127                         fprintf(stderr, "'\n");
128                 } else if (tok->u.s)
129                         fprintf(stderr, "got token '%s'\n", tok->u.s);
130                 else
131                         fprintf(stderr, "got token type %d\n", tok->type);
132         }
133 }
134
135 static struct isl_stream* isl_stream_new(struct isl_ctx *ctx)
136 {
137         int i;
138         struct isl_stream *s = isl_alloc_type(ctx, struct isl_stream);
139         if (!s)
140                 return NULL;
141         s->ctx = ctx;
142         isl_ctx_ref(s->ctx);
143         s->file = NULL;
144         s->str = NULL;
145         s->len = 0;
146         s->line = 1;
147         s->col = 0;
148         s->eof = 0;
149         s->c = -1;
150         s->n_un = 0;
151         for (i = 0; i < 5; ++i)
152                 s->tokens[i] = NULL;
153         s->n_token = 0;
154         s->keywords = NULL;
155         s->size = 256;
156         s->buffer = isl_alloc_array(ctx, char, s->size);
157         if (!s->buffer)
158                 goto error;
159         return s;
160 error:
161         isl_stream_free(s);
162         return NULL;
163 }
164
165 struct isl_stream* isl_stream_new_file(struct isl_ctx *ctx, FILE *file)
166 {
167         struct isl_stream *s = isl_stream_new(ctx);
168         if (!s)
169                 return NULL;
170         s->file = file;
171         return s;
172 }
173
174 struct isl_stream* isl_stream_new_str(struct isl_ctx *ctx, const char *str)
175 {
176         struct isl_stream *s = isl_stream_new(ctx);
177         if (!s)
178                 return NULL;
179         s->str = str;
180         return s;
181 }
182
183 static int stream_getc(struct isl_stream *s)
184 {
185         int c;
186         if (s->eof)
187                 return -1;
188         if (s->n_un)
189                 return s->c = s->un[--s->n_un];
190         if (s->file)
191                 c = fgetc(s->file);
192         else {
193                 c = *s->str++;
194                 if (c == '\0')
195                         c = -1;
196         }
197         if (c == -1)
198                 s->eof = 1;
199         if (!s->eof) {
200                 if (s->c == '\n') {
201                         s->line++;
202                         s->col = 0;
203                 } else
204                         s->col++;
205         }
206         s->c = c;
207         return c;
208 }
209
210 static void isl_stream_ungetc(struct isl_stream *s, int c)
211 {
212         isl_assert(s->ctx, s->n_un < 5, return);
213         s->un[s->n_un++] = c;
214         s->c = -1;
215 }
216
217 static int isl_stream_getc(struct isl_stream *s)
218 {
219         int c;
220
221         do {
222                 c = stream_getc(s);
223                 if (c != '\\')
224                         return c;
225                 c = stream_getc(s);
226         } while (c == '\n');
227
228         isl_stream_ungetc(s, c);
229
230         return '\\';
231 }
232
233 static int isl_stream_push_char(struct isl_stream *s, int c)
234 {
235         if (s->len >= s->size) {
236                 char *buffer;
237                 s->size = (3*s->size)/2;
238                 buffer = isl_realloc_array(s->ctx, s->buffer, char, s->size);
239                 if (!buffer)
240                         return -1;
241                 s->buffer = buffer;
242         }
243         s->buffer[s->len++] = c;
244         return 0;
245 }
246
247 void isl_stream_push_token(struct isl_stream *s, struct isl_token *tok)
248 {
249         isl_assert(s->ctx, s->n_token < 5, return);
250         s->tokens[s->n_token++] = tok;
251 }
252
253 static enum isl_token_type check_keywords(struct isl_stream *s)
254 {
255         struct isl_hash_table_entry *entry;
256         struct isl_keyword *keyword;
257         uint32_t name_hash;
258
259         if (!strcasecmp(s->buffer, "exists"))
260                 return ISL_TOKEN_EXISTS;
261         if (!strcasecmp(s->buffer, "and"))
262                 return ISL_TOKEN_AND;
263         if (!strcasecmp(s->buffer, "or"))
264                 return ISL_TOKEN_OR;
265         if (!strcasecmp(s->buffer, "not"))
266                 return ISL_TOKEN_NOT;
267         if (!strcasecmp(s->buffer, "infty"))
268                 return ISL_TOKEN_INFTY;
269         if (!strcasecmp(s->buffer, "infinity"))
270                 return ISL_TOKEN_INFTY;
271         if (!strcasecmp(s->buffer, "NaN"))
272                 return ISL_TOKEN_NAN;
273         if (!strcasecmp(s->buffer, "min"))
274                 return ISL_TOKEN_MIN;
275         if (!strcasecmp(s->buffer, "max"))
276                 return ISL_TOKEN_MAX;
277         if (!strcasecmp(s->buffer, "rat"))
278                 return ISL_TOKEN_RAT;
279         if (!strcasecmp(s->buffer, "true"))
280                 return ISL_TOKEN_TRUE;
281         if (!strcasecmp(s->buffer, "false"))
282                 return ISL_TOKEN_FALSE;
283         if (!strcasecmp(s->buffer, "ceild"))
284                 return ISL_TOKEN_CEILD;
285         if (!strcasecmp(s->buffer, "floord"))
286                 return ISL_TOKEN_FLOORD;
287         if (!strcasecmp(s->buffer, "mod"))
288                 return ISL_TOKEN_MOD;
289
290         if (!s->keywords)
291                 return ISL_TOKEN_IDENT;
292
293         name_hash = isl_hash_string(isl_hash_init(), s->buffer);
294         entry = isl_hash_table_find(s->ctx, s->keywords, name_hash, same_name,
295                                         s->buffer, 0);
296         if (entry) {
297                 keyword = entry->data;
298                 return keyword->type;
299         }
300
301         return ISL_TOKEN_IDENT;
302 }
303
304 int isl_stream_skip_line(struct isl_stream *s)
305 {
306         int c;
307
308         while ((c = isl_stream_getc(s)) != -1 && c != '\n')
309                 /* nothing */
310                 ;
311
312         return c == -1 ? -1 : 0;
313 }
314
315 static struct isl_token *next_token(struct isl_stream *s, int same_line)
316 {
317         int c;
318         struct isl_token *tok = NULL;
319         int line, col;
320         int old_line = s->line;
321
322         if (s->n_token) {
323                 if (same_line && s->tokens[s->n_token - 1]->on_new_line)
324                         return NULL;
325                 return s->tokens[--s->n_token];
326         }
327
328         if (same_line && s->c == '\n')
329                 return NULL;
330
331         s->len = 0;
332
333         /* skip spaces and comment lines */
334         while ((c = isl_stream_getc(s)) != -1) {
335                 if (c == '#') {
336                         if (isl_stream_skip_line(s) < 0)
337                                 break;
338                         c = '\n';
339                         if (same_line)
340                                 break;
341                 } else if (!isspace(c) || (same_line && c == '\n'))
342                         break;
343         }
344
345         line = s->line;
346         col = s->col;
347
348         if (c == -1 || (same_line && c == '\n'))
349                 return NULL;
350         if (c == '(' ||
351             c == ')' ||
352             c == '+' ||
353             c == '*' ||
354             c == '%' ||
355             c == '?' ||
356             c == '^' ||
357             c == '=' ||
358             c == '@' ||
359             c == '$' ||
360             c == ',' ||
361             c == '.' ||
362             c == ';' ||
363             c == '[' ||
364             c == ']' ||
365             c == '{' ||
366             c == '}') {
367                 tok = isl_token_new(s->ctx, line, col, old_line != line);
368                 if (!tok)
369                         return NULL;
370                 tok->type = (enum isl_token_type)c;
371                 return tok;
372         }
373         if (c == '-') {
374                 int c;
375                 if ((c = isl_stream_getc(s)) == '>') {
376                         tok = isl_token_new(s->ctx, line, col, old_line != line);
377                         if (!tok)
378                                 return NULL;
379                         tok->u.s = strdup("->");
380                         tok->type = ISL_TOKEN_TO;
381                         return tok;
382                 }
383                 if (c != -1)
384                         isl_stream_ungetc(s, c);
385                 if (!isdigit(c)) {
386                         tok = isl_token_new(s->ctx, line, col, old_line != line);
387                         if (!tok)
388                                 return NULL;
389                         tok->type = (enum isl_token_type) '-';
390                         return tok;
391                 }
392         }
393         if (c == '-' || isdigit(c)) {
394                 int minus = c == '-';
395                 tok = isl_token_new(s->ctx, line, col, old_line != line);
396                 if (!tok)
397                         return NULL;
398                 tok->type = ISL_TOKEN_VALUE;
399                 isl_int_init(tok->u.v);
400                 if (isl_stream_push_char(s, c))
401                         goto error;
402                 while ((c = isl_stream_getc(s)) != -1 && isdigit(c))
403                         if (isl_stream_push_char(s, c))
404                                 goto error;
405                 if (c != -1)
406                         isl_stream_ungetc(s, c);
407                 isl_stream_push_char(s, '\0');
408                 isl_int_read(tok->u.v, s->buffer);
409                 if (minus && isl_int_is_zero(tok->u.v)) {
410                         tok->col++;
411                         tok->on_new_line = 0;
412                         isl_stream_push_token(s, tok);
413                         tok = isl_token_new(s->ctx, line, col, old_line != line);
414                         if (!tok)
415                                 return NULL;
416                         tok->type = (enum isl_token_type) '-';
417                 }
418                 return tok;
419         }
420         if (isalpha(c) || c == '_') {
421                 tok = isl_token_new(s->ctx, line, col, old_line != line);
422                 if (!tok)
423                         return NULL;
424                 isl_stream_push_char(s, c);
425                 while ((c = isl_stream_getc(s)) != -1 &&
426                                 (isalnum(c) || c == '_'))
427                         isl_stream_push_char(s, c);
428                 if (c != -1)
429                         isl_stream_ungetc(s, c);
430                 while ((c = isl_stream_getc(s)) != -1 && c == '\'')
431                         isl_stream_push_char(s, c);
432                 if (c != -1)
433                         isl_stream_ungetc(s, c);
434                 isl_stream_push_char(s, '\0');
435                 tok->type = check_keywords(s);
436                 if (tok->type != ISL_TOKEN_IDENT)
437                         tok->is_keyword = 1;
438                 tok->u.s = strdup(s->buffer);
439                 if (!tok->u.s)
440                         goto error;
441                 return tok;
442         }
443         if (c == '"') {
444                 tok = isl_token_new(s->ctx, line, col, old_line != line);
445                 if (!tok)
446                         return NULL;
447                 tok->type = ISL_TOKEN_STRING;
448                 tok->u.s = NULL;
449                 while ((c = isl_stream_getc(s)) != -1 && c != '"' && c != '\n')
450                         isl_stream_push_char(s, c);
451                 if (c != '"') {
452                         isl_stream_error(s, NULL, "unterminated string");
453                         goto error;
454                 }
455                 isl_stream_push_char(s, '\0');
456                 tok->u.s = strdup(s->buffer);
457                 return tok;
458         }
459         if (c == ':') {
460                 int c;
461                 tok = isl_token_new(s->ctx, line, col, old_line != line);
462                 if (!tok)
463                         return NULL;
464                 if ((c = isl_stream_getc(s)) == '=') {
465                         tok->u.s = strdup(":=");
466                         tok->type = ISL_TOKEN_DEF;
467                         return tok;
468                 }
469                 if (c != -1)
470                         isl_stream_ungetc(s, c);
471                 tok->type = (enum isl_token_type) ':';
472                 return tok;
473         }
474         if (c == '>') {
475                 int c;
476                 tok = isl_token_new(s->ctx, line, col, old_line != line);
477                 if (!tok)
478                         return NULL;
479                 if ((c = isl_stream_getc(s)) == '=') {
480                         tok->u.s = strdup(">=");
481                         tok->type = ISL_TOKEN_GE;
482                         return tok;
483                 } else if (c == '>') {
484                         if ((c = isl_stream_getc(s)) == '=') {
485                                 tok->u.s = strdup(">>=");
486                                 tok->type = ISL_TOKEN_LEX_GE;
487                                 return tok;
488                         }
489                         tok->u.s = strdup(">>");
490                         tok->type = ISL_TOKEN_LEX_GT;
491                 } else {
492                         tok->u.s = strdup(">");
493                         tok->type = ISL_TOKEN_GT;
494                 }
495                 if (c != -1)
496                         isl_stream_ungetc(s, c);
497                 return tok;
498         }
499         if (c == '<') {
500                 int c;
501                 tok = isl_token_new(s->ctx, line, col, old_line != line);
502                 if (!tok)
503                         return NULL;
504                 if ((c = isl_stream_getc(s)) == '=') {
505                         tok->u.s = strdup("<=");
506                         tok->type = ISL_TOKEN_LE;
507                         return tok;
508                 } else if (c == '<') {
509                         if ((c = isl_stream_getc(s)) == '=') {
510                                 tok->u.s = strdup("<<=");
511                                 tok->type = ISL_TOKEN_LEX_LE;
512                                 return tok;
513                         }
514                         tok->u.s = strdup("<<");
515                         tok->type = ISL_TOKEN_LEX_LT;
516                 } else {
517                         tok->u.s = strdup("<");
518                         tok->type = ISL_TOKEN_LT;
519                 }
520                 if (c != -1)
521                         isl_stream_ungetc(s, c);
522                 return tok;
523         }
524         if (c == '&') {
525                 tok = isl_token_new(s->ctx, line, col, old_line != line);
526                 if (!tok)
527                         return NULL;
528                 tok->type = ISL_TOKEN_AND;
529                 if ((c = isl_stream_getc(s)) != '&' && c != -1) {
530                         tok->u.s = strdup("&");
531                         isl_stream_ungetc(s, c);
532                 } else
533                         tok->u.s = strdup("&&");
534                 return tok;
535         }
536         if (c == '|') {
537                 tok = isl_token_new(s->ctx, line, col, old_line != line);
538                 if (!tok)
539                         return NULL;
540                 tok->type = ISL_TOKEN_OR;
541                 if ((c = isl_stream_getc(s)) != '|' && c != -1) {
542                         tok->u.s = strdup("|");
543                         isl_stream_ungetc(s, c);
544                 } else
545                         tok->u.s = strdup("||");
546                 return tok;
547         }
548         if (c == '/') {
549                 tok = isl_token_new(s->ctx, line, col, old_line != line);
550                 if (!tok)
551                         return NULL;
552                 if ((c = isl_stream_getc(s)) != '\\' && c != -1) {
553                         tok->type = (enum isl_token_type) '/';
554                         isl_stream_ungetc(s, c);
555                 } else {
556                         tok->u.s = strdup("/\\");
557                         tok->type = ISL_TOKEN_AND;
558                 }
559                 return tok;
560         }
561         if (c == '\\') {
562                 tok = isl_token_new(s->ctx, line, col, old_line != line);
563                 if (!tok)
564                         return NULL;
565                 if ((c = isl_stream_getc(s)) != '/' && c != -1) {
566                         tok->type = (enum isl_token_type) '\\';
567                         isl_stream_ungetc(s, c);
568                 } else {
569                         tok->u.s = strdup("\\/");
570                         tok->type = ISL_TOKEN_OR;
571                 }
572                 return tok;
573         }
574         if (c == '!') {
575                 tok = isl_token_new(s->ctx, line, col, old_line != line);
576                 if (!tok)
577                         return NULL;
578                 if ((c = isl_stream_getc(s)) == '=') {
579                         tok->u.s = strdup("!=");
580                         tok->type = ISL_TOKEN_NE;
581                         return tok;
582                 } else {
583                         tok->type = ISL_TOKEN_NOT;
584                         tok->u.s = strdup("!");
585                 }
586                 if (c != -1)
587                         isl_stream_ungetc(s, c);
588                 return tok;
589         }
590
591         tok = isl_token_new(s->ctx, line, col, old_line != line);
592         if (!tok)
593                 return NULL;
594         tok->type = ISL_TOKEN_UNKNOWN;
595         return tok;
596 error:
597         isl_token_free(tok);
598         return NULL;
599 }
600
601 struct isl_token *isl_stream_next_token(struct isl_stream *s)
602 {
603         return next_token(s, 0);
604 }
605
606 struct isl_token *isl_stream_next_token_on_same_line(struct isl_stream *s)
607 {
608         return next_token(s, 1);
609 }
610
611 int isl_stream_eat_if_available(struct isl_stream *s, int type)
612 {
613         struct isl_token *tok;
614
615         tok = isl_stream_next_token(s);
616         if (!tok)
617                 return 0;
618         if (tok->type == type) {
619                 isl_token_free(tok);
620                 return 1;
621         }
622         isl_stream_push_token(s, tok);
623         return 0;
624 }
625
626 int isl_stream_next_token_is(struct isl_stream *s, int type)
627 {
628         struct isl_token *tok;
629         int r;
630
631         tok = isl_stream_next_token(s);
632         if (!tok)
633                 return 0;
634         r = tok->type == type;
635         isl_stream_push_token(s, tok);
636         return r;
637 }
638
639 char *isl_stream_read_ident_if_available(struct isl_stream *s)
640 {
641         struct isl_token *tok;
642
643         tok = isl_stream_next_token(s);
644         if (!tok)
645                 return NULL;
646         if (tok->type == ISL_TOKEN_IDENT) {
647                 char *ident = strdup(tok->u.s);
648                 isl_token_free(tok);
649                 return ident;
650         }
651         isl_stream_push_token(s, tok);
652         return NULL;
653 }
654
655 int isl_stream_eat(struct isl_stream *s, int type)
656 {
657         struct isl_token *tok;
658
659         tok = isl_stream_next_token(s);
660         if (!tok)
661                 return -1;
662         if (tok->type == type) {
663                 isl_token_free(tok);
664                 return 0;
665         }
666         isl_stream_error(s, tok, "expecting other token");
667         isl_stream_push_token(s, tok);
668         return -1;
669 }
670
671 int isl_stream_is_empty(struct isl_stream *s)
672 {
673         struct isl_token *tok;
674
675         tok = isl_stream_next_token(s);
676
677         if (!tok)
678                 return 1;
679
680         isl_stream_push_token(s, tok);
681         return 0;
682 }
683
684 static int free_keyword(void **p, void *user)
685 {
686         struct isl_keyword *keyword = *p;
687
688         free(keyword->name);
689         free(keyword);
690
691         return 0;
692 }
693
694 void isl_stream_flush_tokens(struct isl_stream *s)
695 {
696         int i;
697
698         if (!s)
699                 return;
700         for (i = 0; i < s->n_token; ++i)
701                 isl_token_free(s->tokens[i]);
702         s->n_token = 0;
703 }
704
705 void isl_stream_free(struct isl_stream *s)
706 {
707         if (!s)
708                 return;
709         free(s->buffer);
710         if (s->n_token != 0) {
711                 struct isl_token *tok = isl_stream_next_token(s);
712                 isl_stream_error(s, tok, "unexpected token");
713                 isl_token_free(tok);
714         }
715         if (s->keywords) {
716                 isl_hash_table_foreach(s->ctx, s->keywords, &free_keyword, NULL);
717                 isl_hash_table_free(s->ctx, s->keywords);
718         }
719         isl_ctx_deref(s->ctx);
720         free(s);
721 }