isl_aff.c: fix typo in comment
[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                 tok = isl_token_new(s->ctx, line, col, old_line != line);
367                 if (!tok)
368                         return NULL;
369                 tok->type = (enum isl_token_type)c;
370                 return tok;
371         }
372         if (c == '-') {
373                 int c;
374                 if ((c = isl_stream_getc(s)) == '>') {
375                         tok = isl_token_new(s->ctx, line, col, old_line != line);
376                         if (!tok)
377                                 return NULL;
378                         tok->u.s = strdup("->");
379                         tok->type = ISL_TOKEN_TO;
380                         return tok;
381                 }
382                 if (c != -1)
383                         isl_stream_ungetc(s, c);
384                 if (!isdigit(c)) {
385                         tok = isl_token_new(s->ctx, line, col, old_line != line);
386                         if (!tok)
387                                 return NULL;
388                         tok->type = (enum isl_token_type) '-';
389                         return tok;
390                 }
391         }
392         if (c == '-' || isdigit(c)) {
393                 int minus = c == '-';
394                 tok = isl_token_new(s->ctx, line, col, old_line != line);
395                 if (!tok)
396                         return NULL;
397                 tok->type = ISL_TOKEN_VALUE;
398                 isl_int_init(tok->u.v);
399                 if (isl_stream_push_char(s, c))
400                         goto error;
401                 while ((c = isl_stream_getc(s)) != -1 && isdigit(c))
402                         if (isl_stream_push_char(s, c))
403                                 goto error;
404                 if (c != -1)
405                         isl_stream_ungetc(s, c);
406                 isl_stream_push_char(s, '\0');
407                 isl_int_read(tok->u.v, s->buffer);
408                 if (minus && isl_int_is_zero(tok->u.v)) {
409                         tok->col++;
410                         tok->on_new_line = 0;
411                         isl_stream_push_token(s, tok);
412                         tok = isl_token_new(s->ctx, line, col, old_line != line);
413                         if (!tok)
414                                 return NULL;
415                         tok->type = (enum isl_token_type) '-';
416                 }
417                 return tok;
418         }
419         if (isalpha(c) || c == '_') {
420                 tok = isl_token_new(s->ctx, line, col, old_line != line);
421                 if (!tok)
422                         return NULL;
423                 isl_stream_push_char(s, c);
424                 while ((c = isl_stream_getc(s)) != -1 &&
425                                 (isalnum(c) || c == '_'))
426                         isl_stream_push_char(s, c);
427                 if (c != -1)
428                         isl_stream_ungetc(s, c);
429                 while ((c = isl_stream_getc(s)) != -1 && c == '\'')
430                         isl_stream_push_char(s, c);
431                 if (c != -1)
432                         isl_stream_ungetc(s, c);
433                 isl_stream_push_char(s, '\0');
434                 tok->type = check_keywords(s);
435                 if (tok->type != ISL_TOKEN_IDENT)
436                         tok->is_keyword = 1;
437                 tok->u.s = strdup(s->buffer);
438                 if (!tok->u.s)
439                         goto error;
440                 return tok;
441         }
442         if (c == '"') {
443                 tok = isl_token_new(s->ctx, line, col, old_line != line);
444                 if (!tok)
445                         return NULL;
446                 tok->type = ISL_TOKEN_STRING;
447                 tok->u.s = NULL;
448                 while ((c = isl_stream_getc(s)) != -1 && c != '"' && c != '\n')
449                         isl_stream_push_char(s, c);
450                 if (c != '"') {
451                         isl_stream_error(s, NULL, "unterminated string");
452                         goto error;
453                 }
454                 isl_stream_push_char(s, '\0');
455                 tok->u.s = strdup(s->buffer);
456                 return tok;
457         }
458         if (c == '=') {
459                 int c;
460                 tok = isl_token_new(s->ctx, line, col, old_line != line);
461                 if (!tok)
462                         return NULL;
463                 if ((c = isl_stream_getc(s)) == '=') {
464                         tok->u.s = strdup("==");
465                         tok->type = ISL_TOKEN_EQ_EQ;
466                         return tok;
467                 }
468                 if (c != -1)
469                         isl_stream_ungetc(s, c);
470                 tok->type = (enum isl_token_type) '=';
471                 return tok;
472         }
473         if (c == ':') {
474                 int c;
475                 tok = isl_token_new(s->ctx, line, col, old_line != line);
476                 if (!tok)
477                         return NULL;
478                 if ((c = isl_stream_getc(s)) == '=') {
479                         tok->u.s = strdup(":=");
480                         tok->type = ISL_TOKEN_DEF;
481                         return tok;
482                 }
483                 if (c != -1)
484                         isl_stream_ungetc(s, c);
485                 tok->type = (enum isl_token_type) ':';
486                 return tok;
487         }
488         if (c == '>') {
489                 int c;
490                 tok = isl_token_new(s->ctx, line, col, old_line != line);
491                 if (!tok)
492                         return NULL;
493                 if ((c = isl_stream_getc(s)) == '=') {
494                         tok->u.s = strdup(">=");
495                         tok->type = ISL_TOKEN_GE;
496                         return tok;
497                 } else if (c == '>') {
498                         if ((c = isl_stream_getc(s)) == '=') {
499                                 tok->u.s = strdup(">>=");
500                                 tok->type = ISL_TOKEN_LEX_GE;
501                                 return tok;
502                         }
503                         tok->u.s = strdup(">>");
504                         tok->type = ISL_TOKEN_LEX_GT;
505                 } else {
506                         tok->u.s = strdup(">");
507                         tok->type = ISL_TOKEN_GT;
508                 }
509                 if (c != -1)
510                         isl_stream_ungetc(s, c);
511                 return tok;
512         }
513         if (c == '<') {
514                 int c;
515                 tok = isl_token_new(s->ctx, line, col, old_line != line);
516                 if (!tok)
517                         return NULL;
518                 if ((c = isl_stream_getc(s)) == '=') {
519                         tok->u.s = strdup("<=");
520                         tok->type = ISL_TOKEN_LE;
521                         return tok;
522                 } else if (c == '<') {
523                         if ((c = isl_stream_getc(s)) == '=') {
524                                 tok->u.s = strdup("<<=");
525                                 tok->type = ISL_TOKEN_LEX_LE;
526                                 return tok;
527                         }
528                         tok->u.s = strdup("<<");
529                         tok->type = ISL_TOKEN_LEX_LT;
530                 } else {
531                         tok->u.s = strdup("<");
532                         tok->type = ISL_TOKEN_LT;
533                 }
534                 if (c != -1)
535                         isl_stream_ungetc(s, c);
536                 return tok;
537         }
538         if (c == '&') {
539                 tok = isl_token_new(s->ctx, line, col, old_line != line);
540                 if (!tok)
541                         return NULL;
542                 tok->type = ISL_TOKEN_AND;
543                 if ((c = isl_stream_getc(s)) != '&' && c != -1) {
544                         tok->u.s = strdup("&");
545                         isl_stream_ungetc(s, c);
546                 } else
547                         tok->u.s = strdup("&&");
548                 return tok;
549         }
550         if (c == '|') {
551                 tok = isl_token_new(s->ctx, line, col, old_line != line);
552                 if (!tok)
553                         return NULL;
554                 tok->type = ISL_TOKEN_OR;
555                 if ((c = isl_stream_getc(s)) != '|' && c != -1) {
556                         tok->u.s = strdup("|");
557                         isl_stream_ungetc(s, c);
558                 } else
559                         tok->u.s = strdup("||");
560                 return tok;
561         }
562         if (c == '/') {
563                 tok = isl_token_new(s->ctx, line, col, old_line != line);
564                 if (!tok)
565                         return NULL;
566                 if ((c = isl_stream_getc(s)) != '\\' && c != -1) {
567                         tok->type = (enum isl_token_type) '/';
568                         isl_stream_ungetc(s, c);
569                 } else {
570                         tok->u.s = strdup("/\\");
571                         tok->type = ISL_TOKEN_AND;
572                 }
573                 return tok;
574         }
575         if (c == '\\') {
576                 tok = isl_token_new(s->ctx, line, col, old_line != line);
577                 if (!tok)
578                         return NULL;
579                 if ((c = isl_stream_getc(s)) != '/' && c != -1) {
580                         tok->type = (enum isl_token_type) '\\';
581                         isl_stream_ungetc(s, c);
582                 } else {
583                         tok->u.s = strdup("\\/");
584                         tok->type = ISL_TOKEN_OR;
585                 }
586                 return tok;
587         }
588         if (c == '!') {
589                 tok = isl_token_new(s->ctx, line, col, old_line != line);
590                 if (!tok)
591                         return NULL;
592                 if ((c = isl_stream_getc(s)) == '=') {
593                         tok->u.s = strdup("!=");
594                         tok->type = ISL_TOKEN_NE;
595                         return tok;
596                 } else {
597                         tok->type = ISL_TOKEN_NOT;
598                         tok->u.s = strdup("!");
599                 }
600                 if (c != -1)
601                         isl_stream_ungetc(s, c);
602                 return tok;
603         }
604
605         tok = isl_token_new(s->ctx, line, col, old_line != line);
606         if (!tok)
607                 return NULL;
608         tok->type = ISL_TOKEN_UNKNOWN;
609         return tok;
610 error:
611         isl_token_free(tok);
612         return NULL;
613 }
614
615 struct isl_token *isl_stream_next_token(struct isl_stream *s)
616 {
617         return next_token(s, 0);
618 }
619
620 struct isl_token *isl_stream_next_token_on_same_line(struct isl_stream *s)
621 {
622         return next_token(s, 1);
623 }
624
625 int isl_stream_eat_if_available(struct isl_stream *s, int type)
626 {
627         struct isl_token *tok;
628
629         tok = isl_stream_next_token(s);
630         if (!tok)
631                 return 0;
632         if (tok->type == type) {
633                 isl_token_free(tok);
634                 return 1;
635         }
636         isl_stream_push_token(s, tok);
637         return 0;
638 }
639
640 int isl_stream_next_token_is(struct isl_stream *s, int type)
641 {
642         struct isl_token *tok;
643         int r;
644
645         tok = isl_stream_next_token(s);
646         if (!tok)
647                 return 0;
648         r = tok->type == type;
649         isl_stream_push_token(s, tok);
650         return r;
651 }
652
653 char *isl_stream_read_ident_if_available(struct isl_stream *s)
654 {
655         struct isl_token *tok;
656
657         tok = isl_stream_next_token(s);
658         if (!tok)
659                 return NULL;
660         if (tok->type == ISL_TOKEN_IDENT) {
661                 char *ident = strdup(tok->u.s);
662                 isl_token_free(tok);
663                 return ident;
664         }
665         isl_stream_push_token(s, tok);
666         return NULL;
667 }
668
669 int isl_stream_eat(struct isl_stream *s, int type)
670 {
671         struct isl_token *tok;
672
673         tok = isl_stream_next_token(s);
674         if (!tok)
675                 return -1;
676         if (tok->type == type) {
677                 isl_token_free(tok);
678                 return 0;
679         }
680         isl_stream_error(s, tok, "expecting other token");
681         isl_stream_push_token(s, tok);
682         return -1;
683 }
684
685 int isl_stream_is_empty(struct isl_stream *s)
686 {
687         struct isl_token *tok;
688
689         tok = isl_stream_next_token(s);
690
691         if (!tok)
692                 return 1;
693
694         isl_stream_push_token(s, tok);
695         return 0;
696 }
697
698 static int free_keyword(void **p, void *user)
699 {
700         struct isl_keyword *keyword = *p;
701
702         free(keyword->name);
703         free(keyword);
704
705         return 0;
706 }
707
708 void isl_stream_flush_tokens(struct isl_stream *s)
709 {
710         int i;
711
712         if (!s)
713                 return;
714         for (i = 0; i < s->n_token; ++i)
715                 isl_token_free(s->tokens[i]);
716         s->n_token = 0;
717 }
718
719 void isl_stream_free(struct isl_stream *s)
720 {
721         if (!s)
722                 return;
723         free(s->buffer);
724         if (s->n_token != 0) {
725                 struct isl_token *tok = isl_stream_next_token(s);
726                 isl_stream_error(s, tok, "unexpected token");
727                 isl_token_free(tok);
728         }
729         if (s->keywords) {
730                 isl_hash_table_foreach(s->ctx, s->keywords, &free_keyword, NULL);
731                 isl_hash_table_free(s->ctx, s->keywords);
732         }
733         isl_ctx_deref(s->ctx);
734         free(s);
735 }