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