src/script/parser.c

   1 #include <assert.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 "script/builtins.h"
  11 #include "script/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, 2, SYMBOL(gc, "quote"), result.expr);
 161
 162         return result;
 163     } break;
 164     default: {}
 165     }
 166
 167     if (*current_token.begin == '-' || isdigit(*current_token.begin)) {
 168         struct ParseResult result = parse_number(gc, current_token);
 169         if (!result.is_error) {
 170             return result;
 171         }
 172     }
 173
 174     return parse_symbol(gc, current_token);
 175 }
 176
 177 struct ParseResult read_expr_from_string(Gc *gc, const char *str)
 178 {
 179     assert(str);
 180     return parse_expr(gc, next_token(str));
 181 }
 182
 183 struct ParseResult read_expr_from_file(Gc *gc, const char *filename)
 184 {
 185     assert(filename);
 186
 187     Lt *lt = create_lt();
 188     if (lt == NULL) {
 189         return parse_failure("Could not create Lt object", NULL);
 190     }
 191
 192     FILE *stream = PUSH_LT(lt, fopen(filename, "rb"), fclose_lt);
 193     if (!stream) {
 194         /* TODO(#307): ParseResult should not be used for reporting IO failures */
 195         RETURN_LT(lt, parse_failure(strerror(errno), NULL));
 196     }
 197
 198     if (fseek(stream, 0, SEEK_END) != 0) {
 199         RETURN_LT(lt, parse_failure("Could not find the end of the file", NULL));
 200     }
 201
 202     const long int buffer_length = ftell(stream);
 203
 204     if (buffer_length < 0) {
 205         RETURN_LT(lt, parse_failure("Couldn't get the size of file", NULL));
 206     }
 207
 208     if (buffer_length == 0) {
 209         RETURN_LT(lt, parse_failure("File is empty", NULL));
 210     }
 211
 212     if (buffer_length >= MAX_BUFFER_LENGTH) {
 213         RETURN_LT(lt, parse_failure("File is too big", NULL));
 214     }
 215
 216     if (fseek(stream, 0, SEEK_SET) != 0) {
 217         RETURN_LT(lt, parse_failure("Could not find the beginning of the file", NULL));
 218     }
 219
 220     char * const buffer = PUSH_LT(lt, malloc((size_t) buffer_length + 1), free);
 221     if (buffer == NULL) {
 222         RETURN_LT(lt, parse_failure(strerror(errno), NULL));
 223     }
 224
 225     if (fread(buffer, 1, (size_t) buffer_length, stream) != (size_t) buffer_length) {
 226         RETURN_LT(lt, parse_failure("Could not read the file", NULL));
 227     }
 228
 229     struct ParseResult result = read_expr_from_string(gc, buffer);
 230
 231     RETURN_LT(lt, result);
 232 }
 233
 234 struct ParseResult parse_success(struct Expr expr,
 235                                  const char *end)
 236 {
 237     struct ParseResult result = {
 238         .is_error = false,
 239         .expr = expr,
 240         .end = end
 241     };
 242
 243     return result;
 244 }
 245
 246 struct ParseResult parse_failure(const char *error_message,
 247                                  const char *end)
 248 {
 249     struct ParseResult result = {
 250         .is_error = true,
 251         .error_message = error_message,
 252         .end = end
 253     };
 254
 255     return result;
 256 }
 257
 258 void print_parse_error(FILE *stream,
 259                        const char *str,
 260                        struct ParseResult result)
 261 {
 262     /* TODO(#294): print_parse_error doesn't support multiple lines */
 263     if (!result.is_error) {
 264         return;
 265     }
 266
 267     if (result.end) {
 268         fprintf(stream, "%s\n", str);
 269         for (size_t i = 0; i < (size_t) (result.end - str); ++i) {
 270             fprintf(stream, " ");
 271         }
 272         fprintf(stream, "^\n");
 273     }
 274
 275     fprintf(stream, "%s\n", result.error_message);
 276 }