src/ebisp/parser.c

   1 #include "system/stacktrace.h"
   2 #include <ctype.h>
   3 #include <errno.h>
   4 #include <stdint.h>
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <inttypes.h>
   9
  10 #include "ebisp/builtins.h"
  11 #include "ebisp/parser.h"
  12 #include "system/lt.h"
  13
  14 #define MAX_BUFFER_LENGTH (5 * 1000 * 1000)
  15
  16 static void fclose_lt(void* file)
  17 {
  18     fclose(file);
  19 }
  20
  21 static struct ParseResult parse_expr(Gc *gc, struct Token current_token);
  22
  23 static struct ParseResult parse_cdr(Gc *gc, struct Token current_token)
  24 {
  25     if (*current_token.begin != '.') {
  26         return parse_failure("Expected .", current_token.begin);
  27     }
  28
  29     struct ParseResult cdr = read_expr_from_string(gc, current_token.end);
  30     if (cdr.is_error) {
  31         return cdr;
  32     }
  33
  34     current_token = next_token(cdr.end);
  35
  36     if (*current_token.begin != ')') {
  37         return parse_failure("Expected )", current_token.begin);
  38     }
  39
  40     return parse_success(cdr.expr, current_token.end);
  41 }
  42
  43 static struct ParseResult parse_list_end(Gc *gc, struct Token current_token)
  44 {
  45     if (*current_token.begin != ')') {
  46         return parse_failure("Expected )", current_token.begin);
  47     }
  48
  49     return parse_success(atom_as_expr(create_symbol_atom(gc, "nil", NULL)),
  50                          current_token.end);
  51 }
  52
  53 static struct ParseResult parse_list(Gc *gc, struct Token current_token)
  54 {
  55     if (*current_token.begin != '(') {
  56         return parse_failure("Expected (", current_token.begin);
  57     }
  58
  59     current_token = next_token(current_token.end);
  60
  61     if (*current_token.begin == ')') {
  62         return parse_list_end(gc, current_token);
  63     }
  64
  65     struct ParseResult car = parse_expr(gc, current_token);
  66     if (car.is_error) {
  67         return car;
  68     }
  69
  70     struct Cons *list = create_cons(gc, car.expr, void_expr());
  71     struct Cons *cons = list;
  72     current_token = next_token(car.end);
  73
  74     while (*current_token.begin != '.' &&
  75            *current_token.begin != ')' &&
  76            *current_token.begin != 0) {
  77         car = parse_expr(gc, current_token);
  78         if (car.is_error) {
  79             return car;
  80         }
  81
  82         cons->cdr = cons_as_expr(create_cons(gc, car.expr, void_expr()));
  83         cons = cons->cdr.cons;
  84
  85         current_token = next_token(car.end);
  86     }
  87
  88     struct ParseResult cdr = *current_token.begin == '.'
  89         ? parse_cdr(gc, current_token)
  90         : parse_list_end(gc, current_token);
  91
  92     if (cdr.is_error) {
  93         return cdr;
  94     }
  95
  96     cons->cdr = cdr.expr;
  97
  98     return parse_success(cons_as_expr(list), cdr.end);
  99 }
 100
 101 static struct ParseResult parse_string(Gc *gc, struct Token current_token)
 102 {
 103     if (*current_token.begin != '"') {
 104         return parse_failure("Expected \"", current_token.begin);
 105     }
 106
 107     if (*(current_token.end - 1) != '"') {
 108         return parse_failure("Unclosed string", current_token.begin);
 109     }
 110
 111     if (current_token.begin + 1 == current_token.end) {
 112         return parse_success(atom_as_expr(create_string_atom(gc, "", NULL)),
 113                              current_token.end);
 114     }
 115
 116     return parse_success(
 117         atom_as_expr(
 118             create_string_atom(gc, current_token.begin + 1, current_token.end - 1)),
 119         current_token.end);
 120 }
 121
 122 static struct ParseResult parse_number(Gc *gc, struct Token current_token)
 123 {
 124     char *endptr = 0;
 125     const long int x = strtol(current_token.begin, &endptr, 10);
 126
 127     if (current_token.begin == endptr || current_token.end != endptr) {
 128         return parse_failure("Expected number", current_token.begin);
 129     }
 130
 131     return parse_success(
 132         atom_as_expr(create_number_atom(gc, x)),
 133         current_token.end);
 134 }
 135
 136 static struct ParseResult parse_symbol(Gc *gc, struct Token current_token)
 137 {
 138     if (*current_token.begin == 0) {
 139         return parse_failure("EOF", current_token.begin);
 140     }
 141
 142     return parse_success(
 143         atom_as_expr(create_symbol_atom(gc, current_token.begin, current_token.end)),
 144         current_token.end);
 145 }
 146
 147 static struct ParseResult parse_expr(Gc *gc, struct Token current_token)
 148 {
 149     if (*current_token.begin == 0) {
 150         return parse_failure("EOF", current_token.begin);
 151     }
 152
 153     switch (*current_token.begin) {
 154     case '(': return parse_list(gc, current_token);
 155     /* TODO(#292): parser does not support escaped string characters */
 156     case '"': return parse_string(gc, current_token);
 157     case '\'': {
 158         struct ParseResult result = parse_expr(gc, next_token(current_token.end));
 159
 160         if (result.is_error) {
 161             return result;
 162         }
 163
 164         result.expr = list(gc, "qe", "quote", result.expr);
 165
 166         return result;
 167     } break;
 168
 169     case '`': {
 170         struct ParseResult result = parse_expr(gc, next_token(current_token.end));
 171
 172         if (result.is_error) {
 173             return result;
 174         }
 175
 176         result.expr = list(gc, "qe", "quasiquote", result.expr);
 177
 178         return result;
 179     } break;
 180
 181     case ',': {
 182         struct ParseResult result = parse_expr(gc, next_token(current_token.end));
 183
 184         if (result.is_error) {
 185             return result;
 186         }
 187
 188         result.expr = list(gc, "qe", "unquote", result.expr);
 189
 190         return result;
 191     } break;
 192
 193     default: {}
 194     }
 195
 196     if (*current_token.begin == '-' || isdigit(*current_token.begin)) {
 197         struct ParseResult result = parse_number(gc, current_token);
 198         if (!result.is_error) {
 199             return result;
 200         }
 201     }
 202
 203     return parse_symbol(gc, current_token);
 204 }
 205
 206 struct ParseResult read_expr_from_string(Gc *gc, const char *str)
 207 {
 208     trace_assert(gc);
 209     trace_assert(str);
 210     return parse_expr(gc, next_token(str));
 211 }
 212
 213 struct ParseResult read_all_exprs_from_string(Gc *gc, const char *str)
 214 {
 215     trace_assert(gc);
 216     trace_assert(str);
 217
 218     struct Token current_token = next_token(str);
 219     if (*current_token.end == 0) {
 220         return parse_success(NIL(gc), current_token.end);
 221     }
 222
 223     struct ParseResult parse_result = parse_expr(gc, current_token);
 224     if (parse_result.is_error) {
 225         return parse_result;
 226     }
 227
 228     struct Cons *head = create_cons(gc, parse_result.expr, void_expr());
 229     struct Cons *cons = head;
 230
 231     current_token = next_token(parse_result.end);
 232     while (*current_token.end != 0) {
 233         parse_result = parse_expr(gc, current_token);
 234         if (parse_result.is_error) {
 235             return parse_result;
 236         }
 237
 238         cons->cdr = CONS(gc, parse_result.expr, void_expr());
 239         cons = cons->cdr.cons;
 240         current_token = next_token(parse_result.end);
 241     }
 242
 243     cons->cdr = NIL(gc);
 244
 245     return parse_success(cons_as_expr(head), parse_result.end);
 246 }
 247
 248 struct ParseResult read_expr_from_file(Gc *gc, const char *filename)
 249 {
 250     trace_assert(filename);
 251
 252     Lt *lt = create_lt();
 253
 254     FILE *stream = PUSH_LT(lt, fopen(filename, "rb"), fclose_lt);
 255     if (!stream) {
 256         /* TODO(#307): ParseResult should not be used for reporting IO failures */
 257         RETURN_LT(lt, parse_failure(strerror(errno), NULL));
 258     }
 259
 260     if (fseek(stream, 0, SEEK_END) != 0) {
 261         RETURN_LT(lt, parse_failure("Could not find the end of the file", NULL));
 262     }
 263
 264     const long int buffer_length = ftell(stream);
 265
 266     if (buffer_length < 0) {
 267         RETURN_LT(lt, parse_failure("Couldn't get the size of file", NULL));
 268     }
 269
 270     if (buffer_length == 0) {
 271         RETURN_LT(lt, parse_failure("File is empty", NULL));
 272     }
 273
 274     if (buffer_length >= MAX_BUFFER_LENGTH) {
 275         RETURN_LT(lt, parse_failure("File is too big", NULL));
 276     }
 277
 278     if (fseek(stream, 0, SEEK_SET) != 0) {
 279         RETURN_LT(lt, parse_failure("Could not find the beginning of the file", NULL));
 280     }
 281
 282     char * const buffer = PUSH_LT(lt, malloc((size_t) buffer_length + 1), free);
 283     if (buffer == NULL) {
 284         RETURN_LT(lt, parse_failure(strerror(errno), NULL));
 285     }
 286
 287     if (fread(buffer, 1, (size_t) buffer_length, stream) != (size_t) buffer_length) {
 288         RETURN_LT(lt, parse_failure("Could not read the file", NULL));
 289     }
 290
 291     struct ParseResult result = read_expr_from_string(gc, buffer);
 292
 293     RETURN_LT(lt, result);
 294 }
 295
 296 /* TODO(#598): duplicate code in read_all_exprs_from_file and read_expr_from_file  */
 297 struct ParseResult read_all_exprs_from_file(Gc *gc, const char *filename)
 298 {
 299     trace_assert(filename);
 300
 301     Lt *lt = create_lt();
 302
 303     FILE *stream = PUSH_LT(lt, fopen(filename, "rb"), fclose_lt);
 304     if (!stream) {
 305         RETURN_LT(lt, parse_failure(strerror(errno), NULL));
 306     }
 307
 308     if (fseek(stream, 0, SEEK_END) != 0) {
 309         RETURN_LT(lt, parse_failure("Could not find the end of the file", NULL));
 310     }
 311
 312     const long int buffer_length = ftell(stream);
 313
 314     if (buffer_length < 0) {
 315         RETURN_LT(lt, parse_failure("Couldn't get the size of file", NULL));
 316     }
 317
 318     if (buffer_length == 0) {
 319         RETURN_LT(lt, parse_failure("File is empty", NULL));
 320     }
 321
 322     if (buffer_length >= MAX_BUFFER_LENGTH) {
 323         RETURN_LT(lt, parse_failure("File is too big", NULL));
 324     }
 325
 326     if (fseek(stream, 0, SEEK_SET) != 0) {
 327         RETURN_LT(lt, parse_failure("Could not find the beginning of the file", NULL));
 328     }
 329
 330     char * const buffer = PUSH_LT(lt, malloc((size_t) buffer_length + 1), free);
 331     if (buffer == NULL) {
 332         RETURN_LT(lt, parse_failure(strerror(errno), NULL));
 333     }
 334
 335     if (fread(buffer, 1, (size_t) buffer_length, stream) != (size_t) buffer_length) {
 336         RETURN_LT(lt, parse_failure("Could not read the file", NULL));
 337     }
 338
 339     struct ParseResult result = read_all_exprs_from_string(gc, buffer);
 340
 341     RETURN_LT(lt, result);
 342 }
 343
 344 struct ParseResult parse_success(struct Expr expr,
 345                                  const char *end)
 346 {
 347     struct ParseResult result = {
 348         .is_error = false,
 349         .expr = expr,
 350         .end = end
 351     };
 352
 353     return result;
 354 }
 355
 356 struct ParseResult parse_failure(const char *error_message,
 357                                  const char *end)
 358 {
 359     struct ParseResult result = {
 360         .is_error = true,
 361         .error_message = error_message,
 362         .end = end
 363     };
 364
 365     return result;
 366 }
 367
 368 void print_parse_error(FILE *stream,
 369                        const char *str,
 370                        struct ParseResult result)
 371 {
 372     /* TODO(#294): print_parse_error doesn't support multiple lines */
 373     if (!result.is_error) {
 374         return;
 375     }
 376
 377     if (result.end) {
 378         fprintf(stream, "%s\n", str);
 379         for (size_t i = 0; i < (size_t) (result.end - str); ++i) {
 380             fprintf(stream, " ");
 381         }
 382         fprintf(stream, "^\n");
 383     }
 384
 385     fprintf(stream, "%s\n", result.error_message);
 386 }