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