Merge branch 'maint'
[isl.git] / isl_stream.c
blobdb594688845a42dbf1bfddd5384eaa8ec9c7352f
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8 */
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>
18 struct isl_keyword {
19 char *name;
20 enum isl_token_type type;
23 static int same_name(const void *entry, const void *val)
25 const struct isl_keyword *keyword = (const struct isl_keyword *)entry;
27 return !strcmp(keyword->name, val);
30 enum isl_token_type isl_stream_register_keyword(struct isl_stream *s,
31 const char *name)
33 struct isl_hash_table_entry *entry;
34 struct isl_keyword *keyword;
35 uint32_t name_hash;
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;
44 name_hash = isl_hash_string(isl_hash_init(), name);
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;
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;
64 entry->data = keyword;
66 return keyword->type;
69 struct isl_token *isl_token_new(isl_ctx *ctx,
70 int line, int col, unsigned on_new_line)
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;
83 void isl_token_free(struct isl_token *tok)
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);
98 void isl_stream_error(struct isl_stream *s, struct isl_token *tok, char *msg)
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);
135 static struct isl_stream* isl_stream_new(struct isl_ctx *ctx)
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;
165 struct isl_stream* isl_stream_new_file(struct isl_ctx *ctx, FILE *file)
167 struct isl_stream *s = isl_stream_new(ctx);
168 if (!s)
169 return NULL;
170 s->file = file;
171 return s;
174 struct isl_stream* isl_stream_new_str(struct isl_ctx *ctx, const char *str)
176 struct isl_stream *s = isl_stream_new(ctx);
177 if (!s)
178 return NULL;
179 s->str = str;
180 return s;
183 static int stream_getc(struct isl_stream *s)
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;
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++;
206 s->c = c;
207 return c;
210 static void isl_stream_ungetc(struct isl_stream *s, int c)
212 isl_assert(s->ctx, s->n_un < 5, return);
213 s->un[s->n_un++] = c;
214 s->c = -1;
217 static int isl_stream_getc(struct isl_stream *s)
219 int c;
221 do {
222 c = stream_getc(s);
223 if (c != '\\')
224 return c;
225 c = stream_getc(s);
226 } while (c == '\n');
228 isl_stream_ungetc(s, c);
230 return '\\';
233 static int isl_stream_push_char(struct isl_stream *s, int c)
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;
243 s->buffer[s->len++] = c;
244 return 0;
247 void isl_stream_push_token(struct isl_stream *s, struct isl_token *tok)
249 isl_assert(s->ctx, s->n_token < 5, return);
250 s->tokens[s->n_token++] = tok;
253 static enum isl_token_type check_keywords(struct isl_stream *s)
255 struct isl_hash_table_entry *entry;
256 struct isl_keyword *keyword;
257 uint32_t name_hash;
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;
290 if (!s->keywords)
291 return ISL_TOKEN_IDENT;
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;
301 return ISL_TOKEN_IDENT;
304 int isl_stream_skip_line(struct isl_stream *s)
306 int c;
308 while ((c = isl_stream_getc(s)) != -1 && c != '\n')
309 /* nothing */
312 return c == -1 ? -1 : 0;
315 static struct isl_token *next_token(struct isl_stream *s, int same_line)
317 int c;
318 struct isl_token *tok = NULL;
319 int line, col;
320 int old_line = s->line;
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];
328 if (same_line && s->c == '\n')
329 return NULL;
331 s->len = 0;
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;
345 line = s->line;
346 col = s->col;
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;
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;
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;
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) '-';
417 return tok;
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;
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;
454 isl_stream_push_char(s, '\0');
455 tok->u.s = strdup(s->buffer);
456 return tok;
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;
468 if (c != -1)
469 isl_stream_ungetc(s, c);
470 tok->type = (enum isl_token_type) '=';
471 return tok;
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;
483 if (c != -1)
484 isl_stream_ungetc(s, c);
485 tok->type = (enum isl_token_type) ':';
486 return tok;
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;
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;
509 if (c != -1)
510 isl_stream_ungetc(s, c);
511 return tok;
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;
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;
534 if (c != -1)
535 isl_stream_ungetc(s, c);
536 return tok;
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;
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;
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;
573 return tok;
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;
586 return tok;
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("!");
600 if (c != -1)
601 isl_stream_ungetc(s, c);
602 return tok;
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;
615 struct isl_token *isl_stream_next_token(struct isl_stream *s)
617 return next_token(s, 0);
620 struct isl_token *isl_stream_next_token_on_same_line(struct isl_stream *s)
622 return next_token(s, 1);
625 int isl_stream_eat_if_available(struct isl_stream *s, int type)
627 struct isl_token *tok;
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;
636 isl_stream_push_token(s, tok);
637 return 0;
640 int isl_stream_next_token_is(struct isl_stream *s, int type)
642 struct isl_token *tok;
643 int r;
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;
653 char *isl_stream_read_ident_if_available(struct isl_stream *s)
655 struct isl_token *tok;
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;
665 isl_stream_push_token(s, tok);
666 return NULL;
669 int isl_stream_eat(struct isl_stream *s, int type)
671 struct isl_token *tok;
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;
680 isl_stream_error(s, tok, "expecting other token");
681 isl_stream_push_token(s, tok);
682 return -1;
685 int isl_stream_is_empty(struct isl_stream *s)
687 struct isl_token *tok;
689 tok = isl_stream_next_token(s);
691 if (!tok)
692 return 1;
694 isl_stream_push_token(s, tok);
695 return 0;
698 static int free_keyword(void **p, void *user)
700 struct isl_keyword *keyword = *p;
702 free(keyword->name);
703 free(keyword);
705 return 0;
708 void isl_stream_flush_tokens(struct isl_stream *s)
710 int i;
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;
719 void isl_stream_free(struct isl_stream *s)
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);
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);
733 isl_ctx_deref(s->ctx);
734 free(s);