Something went wrong. Try again.
the hito embeddable programming language
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074#include "syntax.h"#include "bitset.h"#include "builtins.h"#include "error.h"#include "lexer.h"#include "scope.h"#include "util.h"#include "intern.h"#include "value.h"#include <string.h>#include <ctype.h>#include <stdlib.h>#include <stdbool.h>#include <stdio.h>
static bool _expect(lexer_t *lexer, token_type expected, error_tag on_failure) { token_t tok = lexer_lex(lexer); if (tok.type != expected) { error_report(error(on_failure,lexer_source(lexer),tok.pos,tok.len)); return false; } else { return true; }}
static expr_t *_alloc_expr(void) { expr_t *ptr = malloc(sizeof(struct expr)); if (ptr == NULL) { die("Out of memory: cannot allocate expr struct"); } return ptr;}
static char *_parse_string_literal(const char *input) { if (!input || *input != '"') { die("Provided string is not a string literal"); } const char *p = input + 1; // skip opening quote size_t capacity = 16; size_t length = 0; char *result = malloc(capacity); if (result == NULL) { die("Out of memory: Cannot allocate space for string literal"); }
while (*p != '\0' && *p != '"') { char c = *p++; if (c == '\\') { if (!*p) break; // unterminated escape char esc = *p++; switch (esc) { case 'n': c = '\n'; break; case 't': c = '\t'; break; case 'r': c = '\r'; break; case '\\': c = '\\'; break; case '"': c = '"'; break; case '\'': c = '\''; break; default: c = esc; break; } } if (length + 1 >= capacity) { capacity *= 2; char *tmp = realloc(result, capacity); if (tmp == NULL) { die("Out of memory: Cannot enlarge space for string literal"); } result = tmp; } result[length++] = c; } if (*p != '"') { die("The impossible happened"); }
result[length] = '\0'; // null-terminate return result;}
static expr_t *_parse_expr(lexer_t *lexer, intern_table_t *table);
static expr_t *_parse_atom(lexer_t *lexer, intern_table_t *table) { token_t tok = lexer_peek(lexer); switch (tok.type) { case TOKEN_LPAREN: { lexer_lex(lexer); expr_t *first_expr = _parse_expr(lexer, table); token_t next_tok = lexer_peek(lexer); if (first_expr == NULL) { if (next_tok.type == TOKEN_RPAREN) { error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), next_tok.pos, 1)); lexer_lex(lexer); // Consume ')' return NULL; } return NULL; }
if (next_tok.type != TOKEN_COMMA) { // Single element parenthesized expression if (!_expect(lexer, TOKEN_RPAREN, ERROR_EXPECTED_RPAREN)) { syntax_expr_free(first_expr); return NULL; } return first_expr; }
// Multi-element tuple lexer_lex(lexer); // consume the first ','
size_t cap = 4; size_t nargs = 1; expr_t **args = malloc(cap * sizeof(expr_t*)); if (args == NULL) die("Out of memory: can't allocate args array for tuple");
args[0] = first_expr;
while (1) { token_t next_arg_tok = lexer_peek(lexer); expr_t *arg = _parse_expr(lexer, table); if (arg == NULL) { error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), next_arg_tok.pos, 1)); for (size_t i = 0; i < nargs; i++) { syntax_expr_free(args[i]); } free(args); return NULL; }
if (nargs == cap) { cap *= 2; expr_t **temp_args = realloc(args, cap * sizeof(expr_t*)); if (temp_args == NULL) die("Out of memory: can't enlarge args array for tuple"); args = temp_args; }
args[nargs++] = arg; token_t post_arg_tok = lexer_peek(lexer); if (post_arg_tok.type != TOKEN_COMMA) { break; } lexer_lex(lexer); // consume ',' } if (!_expect(lexer, TOKEN_RPAREN, ERROR_EXPECTED_RPAREN)) { for (size_t i = 0; i < nargs; i++) { syntax_expr_free(args[i]); } free(args); return NULL; }
if (nargs < cap) { expr_t **temp_args = realloc(args, nargs * sizeof(expr_t*)); if (temp_args == NULL) { die("Out of memory: can't resize args array for tuple"); } args = temp_args; }
expr_t *tuple = _alloc_expr(); tuple->pos = tok.pos; tuple->source = lexer_source(lexer); tuple->tag = EXPR_TUPLE; tuple->as.tuple.elements = args; tuple->as.tuple.nelements = nargs; return tuple; } case TOKEN_LBRACE: { lexer_lex(lexer); expr_t *first_expr = _parse_expr(lexer, table); token_t next_tok = lexer_peek(lexer); if (first_expr == NULL) { if (next_tok.type == TOKEN_RBRACE) { error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), next_tok.pos, 1)); lexer_lex(lexer); // Consume ')' return NULL; } return NULL; } if (next_tok.type != TOKEN_COMMA) { // Single element parenthesized expression if (!_expect(lexer, TOKEN_RBRACE, ERROR_EXPECTED_RBRACE)) { syntax_expr_free(first_expr); return NULL; } return first_expr; } // Multi-element tuple lexer_lex(lexer); // consume the first ',' size_t cap = 4; size_t nargs = 1; expr_t **args = malloc(cap * sizeof(expr_t*)); if (args == NULL) die("Out of memory: can't allocate args array for function group"); args[0] = first_expr; while (1) { token_t next_arg_tok = lexer_peek(lexer); expr_t *arg = _parse_expr(lexer, table); if (arg == NULL) { error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), next_arg_tok.pos, 1)); for (size_t i = 0; i < nargs; i++) { syntax_expr_free(args[i]); } free(args); return NULL; } if (nargs == cap) { cap *= 2; expr_t **temp_args = realloc(args, cap * sizeof(expr_t*)); if (temp_args == NULL) die("Out of memory: can't enlarge args array for function group"); args = temp_args; } args[nargs++] = arg; token_t post_arg_tok = lexer_peek(lexer); if (post_arg_tok.type != TOKEN_COMMA) { break; } lexer_lex(lexer); // consume ',' } if (!_expect(lexer, TOKEN_RBRACE, ERROR_EXPECTED_RBRACE)) { for (size_t i = 0; i < nargs; i++) { syntax_expr_free(args[i]); } free(args); return NULL; } if (nargs < cap) { expr_t **temp_args = realloc(args, nargs * sizeof(expr_t*)); if (temp_args == NULL) { die("Out of memory: can't resize args array for function group"); } args = temp_args; } expr_t *tuple = _alloc_expr(); tuple->pos = tok.pos; tuple->source = lexer_source(lexer); tuple->tag = EXPR_GROUP; tuple->as.tuple.elements = args; tuple->as.tuple.nelements = nargs; return tuple; } case TOKEN_IDENT: { lexer_lex(lexer); intern_t name = intern_prefix(table,tok.start,tok.len); expr_t *it = _alloc_expr(); it->pos = tok.pos; it->source = lexer_source(lexer); it->tag = EXPR_PAT_IDENT; it->as.ident = name; return it; } case TOKEN_FLOAT_LIT: { lexer_lex(lexer); double value = strtod(tok.start, NULL); expr_t *lit = _alloc_expr(); lit->pos = tok.pos; lit->source = lexer_source(lexer); lit->tag = EXPR_FLOAT_LIT; lit->as.float_lit = value; return lit; } case TOKEN_INT_LIT: { lexer_lex(lexer); long value = strtol(tok.start, NULL, 10); expr_t *lit = _alloc_expr(); lit->pos = tok.pos; lit->source = lexer_source(lexer); lit->tag = EXPR_INT_LIT; lit->as.int_lit = value; return lit; } case TOKEN_CONSTRUCTOR: { lexer_lex(lexer); intern_t name = intern_prefix(table,tok.start,tok.len); expr_t *it = _alloc_expr(); it->pos = tok.pos; it->source = lexer_source(lexer); it->tag = EXPR_CONSTRUCTOR; it->as.ident = name; return it; } case TOKEN_STRING_LIT: { lexer_lex(lexer); char* contents = _parse_string_literal(tok.start); expr_t *lit = _alloc_expr(); lit->pos = tok.pos; lit->source = lexer_source(lexer); lit->tag = EXPR_STRING_LIT; lit->as.string_lit = contents; return lit; } default: return NULL; }}
static expr_t *_parse_call_expr(lexer_t *lexer, intern_table_t *table) { expr_t *lhs = _parse_atom(lexer, table); if (lhs == NULL) return NULL;
// Loop to handle chained calls like f(a)(b) // If we see '(', we treat 'lhs' as the callee, parse arguments, // update 'lhs' to the new call node, and repeat. while (lexer_peek(lexer).type == TOKEN_LPAREN) { lexer_lex(lexer); // consume '('
size_t cap = 4; size_t nargs = 0; expr_t **args = malloc(cap * sizeof(expr_t*)); if (args == NULL) die("Out of memory: can't allocate args array"); while (1) { pos_t arg_start_pos = lexer_cur_pos(lexer); // Use _parse_expr here to allow complex args like f(a + b) expr_t *arg = _parse_expr(lexer, table); if (arg == NULL) { error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), arg_start_pos, 1)); // Cleanup for (size_t i = 0; i < nargs; i++) { syntax_expr_free(args[i]); } free(args); syntax_expr_free(lhs); return NULL; }
if (nargs == cap) { cap *= 2; args = realloc(args, cap * sizeof(expr_t*)); if (args == NULL) die("Out of memory: can't enlarge args array"); }
args[nargs++] = arg;
// If we see a comma, consume it and continue to next arg if (lexer_peek(lexer).type == TOKEN_COMMA) { lexer_lex(lexer); continue; }
// If no comma, we expect the closing parenthesis break; }
if (!_expect(lexer, TOKEN_RPAREN, ERROR_EXPECTED_RPAREN)) { // Cleanup for (size_t i = 0; i < nargs; i++) { syntax_expr_free(args[i]); } free(args); syntax_expr_free(lhs); return NULL; } // _expect consumes ')' on success
// shrink array to exact size args = realloc(args, nargs * sizeof(expr_t*)); if (args == NULL) die("Out of memory: can't resize args array");
// build n-ary call node expr_t *call = _alloc_expr(); call->pos = lhs->pos; call->source = lexer_source(lexer); call->tag = EXPR_CALL; call->as.call.callee = lhs; call->as.call.arguments = args; call->as.call.nargs = nargs;
// The result of this call becomes the LHS for the next potential call in the chain lhs = call; }
return lhs;}
static expr_t *_parse_arith_plus(lexer_t *lexer, intern_table_t *table) { expr_t *lhs = _parse_call_expr(lexer, table); while (1) { token_t tok = lexer_peek(lexer); intern_t name = (tok.type == TOKEN_PLUS) ? intern(table, "+") : (tok.type == TOKEN_MINUS) ? intern(table,"-") : NULL; if (name == NULL) { return lhs; } lexer_lex(lexer); expr_t *rhs = _parse_call_expr(lexer, table); expr_t *it = _alloc_expr(); it->pos = tok.pos; it->source = lexer_source(lexer); it->tag = EXPR_CALL; it->as.call.arguments = malloc(sizeof(expr_t*) * 2); if (it->as.call.arguments == NULL) die("Out of memory: cannot allocate args array"); it->as.call.arguments[0] = lhs; it->as.call.arguments[1] = rhs; it->as.call.nargs = 2; it->as.call.callee = _alloc_expr(); it->as.call.callee->tag = EXPR_PAT_IDENT; it->as.call.callee->pos = tok.pos; it->as.call.callee->source = lexer_source(lexer); it->as.call.callee->as.ident = name; lhs = it; }}
static expr_t *_parse_arith(lexer_t *lexer, intern_table_t *table) { expr_t *lhs = _parse_arith_plus(lexer, table); while (1) { token_t tok = lexer_peek(lexer); intern_t name = (tok.type == TOKEN_MULT) ? intern(table, "*") : (tok.type == TOKEN_DIV) ? intern(table,"/") : (tok.type == TOKEN_MOD) ? intern(table,"mod") : (tok.type == TOKEN_IDIV) ? intern(table,"div") : NULL; if (name == NULL) { return lhs; } lexer_lex(lexer); expr_t *rhs = _parse_arith_plus(lexer, table); expr_t *it = _alloc_expr(); it->tag = EXPR_CALL; it->pos = tok.pos; it->source = lexer_source(lexer); it->as.call.arguments = malloc(sizeof(expr_t*) * 2); if (it->as.call.arguments == NULL) die("Out of memory: cannot allocate args array"); it->as.call.arguments[0] = lhs; it->as.call.arguments[1] = rhs; it->as.call.nargs = 2; it->as.call.callee = _alloc_expr(); it->as.call.callee->tag = EXPR_PAT_IDENT; it->as.call.callee->pos = tok.pos; it->as.call.callee->source = lexer_source(lexer); it->as.call.callee->as.ident = name; lhs = it; }}
static expr_t *_parse_binop_comp(lexer_t *lexer, intern_table_t *table) { expr_t *lhs = _parse_arith(lexer, table); token_t tok = lexer_peek(lexer); intern_t name = (tok.type == TOKEN_EQ) ? intern(table, "=") : (tok.type == TOKEN_NOTEQ) ? intern(table,"/=") : (tok.type == TOKEN_GREATER) ? intern(table,">") : (tok.type == TOKEN_LESS) ? intern(table,"<") : (tok.type == TOKEN_LESSEQ) ? intern(table,"<=") : (tok.type == TOKEN_GREATEREQ) ? intern(table,">=") : NULL; if (name != NULL) { lexer_lex(lexer); expr_t *rhs = _parse_arith(lexer, table); expr_t *it = _alloc_expr(); it->tag = EXPR_CALL; it->source = lexer_source(lexer); it->pos = tok.pos; it->as.call.arguments = malloc(sizeof(expr_t*) * 2); if (it->as.call.arguments == NULL) die("Out of memory: cannot allocate args array"); it->as.call.arguments[0] = lhs; it->as.call.arguments[1] = rhs; it->as.call.nargs = 2; it->as.call.callee = _alloc_expr(); it->as.call.callee->pos = tok.pos; it->as.call.callee->source = lexer_source(lexer); it->as.call.callee->tag = EXPR_PAT_IDENT; it->as.call.callee->as.ident = name; return it; } return lhs;}
static expr_t *_parse_binop_and(lexer_t *lexer, intern_table_t *table) { expr_t *lhs = _parse_binop_comp(lexer, table); token_t tok = lexer_peek(lexer); if (tok.type == TOKEN_AND) { lexer_lex(lexer); expr_t *rhs = _parse_binop_and(lexer, table); expr_t *it = _alloc_expr(); it->source = lexer_source(lexer); it->pos = tok.pos; it->tag = EXPR_SEQ; it->as.seq.first = lhs; it->as.seq.then = rhs; return it; } return lhs;}static expr_t *_parse_binop_or(lexer_t *lexer, intern_table_t *table) { expr_t *lhs = _parse_binop_and(lexer, table); token_t tok = lexer_peek(lexer); if (tok.type == TOKEN_OR) { lexer_lex(lexer); expr_t *rhs = _parse_binop_or(lexer, table); expr_t *it = _alloc_expr(); it->tag = EXPR_ALT; it->source = lexer_source(lexer); it->pos = tok.pos; it->as.alt.try = lhs; it->as.alt.orelse = rhs; return it; } return lhs;}/*static expr_t *_parse_binop_or(lexer_t *lexer, intern_table_t *table) { expr_t *lhs = _parse_binop_and(lexer, table); token_t tok = lexer_peek(lexer); intern_t or_name = intern(table, "or"); if (tok.type == TOKEN_OR) { lexer_lex(lexer); expr_t *rhs = _parse_binop_or(lexer, table); expr_t *it = _alloc_expr(); it->tag = EXPR_CALL; it->as.call.arguments = malloc(sizeof(expr_t*) * 2); if (it->as.call.arguments == NULL) die("Out of memory: cannot allocate args array"); it->as.call.arguments[0] = lhs; it->as.call.arguments[1] = rhs; it->as.call.callee = _alloc_expr(); it->as.call.callee->tag = EXPR_PAT_IDENT; it->as.call.callee->as.ident = or_name; return it; } return lhs;}*/static expr_t *_parse_sequence_expr(lexer_t *lexer, intern_table_t *table) { token_t tok = lexer_peek(lexer); if (tok.type == TOKEN_IF) { lexer_lex(lexer); expr_t *lhs = _parse_call_expr(lexer, table); if (lhs == NULL) { error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), tok.pos, 1)); } pos_t pos = lexer_cur_pos(lexer); expr_t *rhs = _parse_sequence_expr(lexer, table); if (rhs == NULL) { syntax_expr_free(lhs); error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), pos, 1)); } expr_t *sequence = _alloc_expr(); sequence->tag = EXPR_SEQ; sequence->pos = lhs->pos; sequence->source = lhs->source; sequence->as.seq.first = lhs; sequence->as.seq.then = rhs; return sequence; } expr_t *lhs = _parse_binop_or(lexer, table); if (lhs == NULL) return NULL;
token_type next_token = lexer_peek(lexer).type; if (next_token == TOKEN_ASSIGN) { expr_t *pattern = lhs; lhs = NULL; // Ownership transferred to 'pattern' variable lexer_lex(lexer); // consume := pos_t value_pos = lexer_cur_pos(lexer); expr_t *value_expr = _parse_expr(lexer, table); if (value_expr == NULL) { error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), value_pos, 1)); syntax_expr_free(pattern); return NULL; }
if (!_expect(lexer, TOKEN_SEMI, ERROR_EXPECTED_SEMI)) { syntax_expr_free(value_expr); syntax_expr_free(pattern); return NULL; }
pos_t body_pos = lexer_cur_pos(lexer); expr_t *body_expr = _parse_sequence_expr(lexer, table); if (body_expr == NULL) { error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), body_pos, 1)); syntax_expr_free(value_expr); // Cleanup: Free the pattern node syntax_expr_free(pattern); return NULL; }
expr_t *let_binding = _alloc_expr(); let_binding->tag = EXPR_LET_BINDING; let_binding->pos = pattern->pos; let_binding->source = pattern->source; let_binding->as.let_binding.pattern.expr = pattern; let_binding->as.let_binding.pattern.bound_vars = (size_t)-1; let_binding->as.let_binding.expr = value_expr; let_binding->as.let_binding.in = body_expr;
return let_binding; } return lhs;}
static expr_t *_parse_alt_expr(lexer_t *lexer, intern_table_t *table) { expr_t *lhs = _parse_sequence_expr(lexer, table); if (lhs == NULL) return NULL;
if (lexer_peek(lexer).type == TOKEN_PIPE) { lexer_lex(lexer);
pos_t rhs_pos = lexer_cur_pos(lexer); expr_t *rhs = _parse_alt_expr(lexer, table); if (rhs == NULL) { error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), rhs_pos, 1)); syntax_expr_free(lhs); return NULL; }
expr_t *disjunction = _alloc_expr(); disjunction->tag = EXPR_ALT; disjunction->pos = lhs->pos; disjunction->source = lhs->source; disjunction->as.alt.try = lhs; disjunction->as.alt.orelse = rhs; return disjunction; }
return lhs;}
static expr_t *_parse_expr(lexer_t *lexer, intern_table_t *table) { expr_t *lhs = NULL; expr_t **params = NULL; size_t nparams = 0; lhs = _parse_alt_expr(lexer, table); if (lhs == NULL) return NULL; token_type next_token = lexer_peek(lexer).type; if (next_token == TOKEN_COLON) { lexer_lex(lexer); if (lexer_peek(lexer).type == TOKEN_PIPE) { lexer_lex(lexer); } pos_t body_pos = lexer_cur_pos(lexer); if (lhs->tag == EXPR_TUPLE) { nparams = lhs->as.tuple.nelements; params = lhs->as.tuple.elements; lhs->as.tuple.elements = NULL; lhs->as.tuple.nelements = 0;
syntax_expr_free(lhs); lhs = NULL;
} else { nparams = 1; params = malloc(sizeof(expr_t*)); if (params == NULL) die("Out of memory: cannot allocate params"); params[0] = lhs; lhs = NULL; }
expr_t *body = _parse_expr(lexer, table); if (body == NULL) { error_report(error(ERROR_EXPECTED_EXPRESSION, lexer_source(lexer), body_pos, 1)); if (params != NULL) { for(size_t i=0; i<nparams; i++) syntax_expr_free(params[i]); free(params); } return NULL; }
expr_t *lambda = _alloc_expr(); lambda->tag = EXPR_LAMBDA; lambda->pos = params[0]->pos; lambda->source = params[0]->source; lambda->as.lambda_raw.patterns = params; lambda->as.lambda_raw.npatterns = nparams; lambda->as.lambda_raw.body = body; return lambda; } return lhs;}
static size_t _scope_check_pattern(expr_t *it, scope_t *scope) { switch (it->tag) { case EXPR_ALT: case EXPR_LAMBDA: case EXPR_LAMBDA_COMPILED: case EXPR_GROUP: case EXPR_SEQ: case EXPR_BUILTIN: case EXPR_LET_BINDING: error_report(error(ERROR_INVALID_PATTERN, it->source,it->pos,1)); return (size_t)-1; case EXPR_VAR: die("Impossible happened: Found a var node when scope-checking."); case EXPR_TUPLE: { size_t i1 = 0; for (int i = 0; i < it->as.tuple.nelements; i++) { size_t i2 = _scope_check_pattern(it->as.tuple.elements[i],scope); if (i2 == (size_t)-1) return i2; i1 += i2; } return i1; } case EXPR_CALL: { if (it->as.call.callee->tag != EXPR_CALL && it->as.call.callee->tag != EXPR_CONSTRUCTOR) { error_report(error(ERROR_INVALID_PATTERN, it->source,it->pos,1)); return (size_t)-1; } size_t i1 = _scope_check_pattern(it->as.call.callee, scope); if (i1 == (size_t)-1) return i1; for (int i = 0; i < it->as.call.nargs; i++) { size_t i2 = _scope_check_pattern(it->as.call.arguments[i],scope); if (i2 == (size_t)-1) return i2; i1 += i2; } return i1; } case EXPR_STRING_LIT: case EXPR_INT_LIT: case EXPR_FLOAT_LIT: case EXPR_CONSTRUCTOR: return 0; case EXPR_PAT_IDENT: { scope_push(scope,it->as.ident); return 1; } }}static inline size_t max(size_t a, size_t b) { return (a > b) ? a : b;}static size_t _max_let_depth(expr_t *it) { switch (it->tag) { case EXPR_ALT: case EXPR_SEQ: return max(_max_let_depth(it->as.alt.try),_max_let_depth(it->as.alt.orelse)); case EXPR_CALL: { size_t ret = _max_let_depth(it->as.call.callee); for (int i = 0; i < it->as.call.nargs;i++) { ret = max(ret,_max_let_depth(it->as.call.arguments[i])); } return ret; } case EXPR_LET_BINDING: { size_t expr = _max_let_depth(it->as.let_binding.expr); return max(expr,_max_let_depth(it->as.let_binding.in) + it->as.let_binding.pattern.bound_vars); } case EXPR_TUPLE: case EXPR_GROUP: { size_t ret = 0; for (int i = 0; i < it->as.tuple.nelements;i++) { ret = max(ret,_max_let_depth(it->as.tuple.elements[i])); } return ret; } case EXPR_LAMBDA: case EXPR_LAMBDA_COMPILED: case EXPR_BUILTIN: case EXPR_INT_LIT: case EXPR_FLOAT_LIT: case EXPR_PAT_IDENT: case EXPR_STRING_LIT: case EXPR_VAR: case EXPR_CONSTRUCTOR: return 0; }}
size_t syntax_expr_required_locals(expr_t *it) { return _max_let_depth(it);}
static char* INTERNAL_NAMES[] = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23"};
static bool _scope_check_expr(expr_t *it, scope_t *scope, builtins_t *builtins, bitset_t *used) { //printf("SCOPE CHECK:"); //scope_debug_dump(scope); //syntax_dump_expr(it); //printf("\n"); switch (it->tag) { case EXPR_ALT: case EXPR_SEQ: return _scope_check_expr(it->as.alt.try, scope, builtins, used) && _scope_check_expr(it->as.alt.orelse, scope, builtins, used); case EXPR_LAMBDA: { size_t idx = 0; expr_t *body = it->as.lambda_raw.body; size_t num_args = it->as.lambda_raw.npatterns; for (int i = 0; i < it->as.lambda_raw.npatterns; i++) { if (it->as.lambda_raw.patterns[i]->tag == EXPR_PAT_IDENT) { scope_push(scope, it->as.lambda_raw.patterns[i]->as.ident); } else { expr_t *ident_expr = _alloc_expr(); ident_expr->tag = EXPR_PAT_IDENT; ident_expr->pos = it->as.lambda_raw.patterns[i]->pos; ident_expr->source = it->as.lambda_raw.patterns[i]->source; ident_expr->as.ident = INTERNAL_NAMES[idx++]; scope_push(scope, ident_expr->as.ident); expr_t *let_binding = _alloc_expr(); let_binding->tag = EXPR_LET_BINDING; let_binding->pos = it->as.lambda_raw.patterns[i]->pos; let_binding->source = it->as.lambda_raw.patterns[i]->source; let_binding->as.let_binding.pattern.expr = it->as.lambda_raw.patterns[i]; let_binding->as.let_binding.pattern.bound_vars = (size_t)-1; let_binding->as.let_binding.expr = ident_expr; let_binding->as.let_binding.in = body; body = let_binding; } } it->tag = EXPR_LAMBDA_COMPILED; it->as.lambda.body = body; it->as.lambda.args = num_args; bitset_t *lambda_mask = bitset_alloc(); bool ret = _scope_check_expr(it->as.lambda.body,scope, builtins, lambda_mask); bitset_shift_down(lambda_mask,num_args); it->as.lambda.mask = lambda_mask; bitset_union(used, lambda_mask); it->as.lambda.num_lets = _max_let_depth(it->as.lambda.body); scope_pop(scope,num_args); return ret; } case EXPR_LET_BINDING: { if (!_scope_check_expr(it->as.let_binding.expr,scope,builtins, used)) return false; size_t amount = _scope_check_pattern(it->as.let_binding.pattern.expr,scope); if (amount == (size_t)-1) return false; it->as.let_binding.pattern.bound_vars = amount; bitset_shift_up(used, amount); bool ret = _scope_check_expr(it->as.let_binding.in,scope,builtins, used); bitset_shift_down(used, amount); scope_pop(scope,amount); return ret; } case EXPR_CALL: if (_scope_check_expr(it->as.call.callee, scope,builtins, used)) { for (int i = 0; i < it->as.call.nargs; i++) { if (!_scope_check_expr(it->as.call.arguments[i], scope,builtins, used)) return false; } return true; } else return false; case EXPR_STRING_LIT: case EXPR_INT_LIT: case EXPR_FLOAT_LIT: case EXPR_CONSTRUCTOR: return true; case EXPR_TUPLE: // TODO case EXPR_GROUP: for (int i = 0; i < it->as.group.nclauses; i++) { if (!_scope_check_expr(it->as.group.clauses[i], scope,builtins, used)) return false; } return true; case EXPR_LAMBDA_COMPILED: case EXPR_VAR: case EXPR_BUILTIN: die("Impossible happened: Found a compiled node when scope-checking."); case EXPR_PAT_IDENT: { de_bruijn_t idx = scope_lookup(scope, it->as.ident); if (idx == (de_bruijn_t)-1) { builtin_func_t *ptr = builtins_lookup(builtins, it->as.ident); if (ptr != NULL) { it->tag = EXPR_BUILTIN; it->as.builtin = ptr; return true; } else { //printf("FOO: %s\n", it->as.ident); error_report(error(ERROR_UNKNOWN_VARIABLE, it->source, it->pos, strlen(it->as.ident))); return false; } } it->tag = EXPR_VAR; it->as.var = idx; bitset_set(used,idx); return true; } }}
expr_t *syntax_parse_expr(lexer_t *lexer, builtins_t *builtins, intern_table_t *table) { expr_t *it = _parse_expr(lexer, table); if (it == NULL) return NULL; bitset_t *used = bitset_alloc(); scope_t *scope = scope_alloc(); syntax_dump_expr(it); _scope_check_expr(it, scope, builtins, used); return it;}void syntax_expr_free(expr_t *it) { switch (it->tag) { case EXPR_ALT: case EXPR_SEQ: syntax_expr_free(it->as.alt.try); syntax_expr_free(it->as.alt.orelse); break; case EXPR_LAMBDA: for (int i = 0; i < it->as.lambda_raw.npatterns;i++) { syntax_expr_free(it->as.lambda_raw.patterns[i]); } free(it->as.lambda_raw.patterns); syntax_expr_free(it->as.lambda_raw.body); break; case EXPR_LAMBDA_COMPILED: syntax_expr_free(it->as.lambda.body); if (it->as.lambda.mask != NULL) bitset_free(it->as.lambda.mask); break; case EXPR_LET_BINDING: syntax_expr_free(it->as.let_binding.expr); syntax_expr_free(it->as.let_binding.in); syntax_expr_free(it->as.let_binding.pattern.expr); break; case EXPR_TUPLE: for (int i = 0; i < it->as.tuple.nelements;i++) { syntax_expr_free(it->as.tuple.elements[i]); } free(it->as.tuple.elements); break; case EXPR_GROUP: for (int i = 0; i < it->as.group.nclauses;i++) { syntax_expr_free(it->as.group.clauses[i]); } free(it->as.group.clauses); break; case EXPR_CALL: syntax_expr_free(it->as.call.callee); for (int i = 0; i < it->as.call.nargs;i++) { syntax_expr_free(it->as.call.arguments[i]); } free(it->as.call.arguments); break; case EXPR_STRING_LIT: free(it->as.string_lit); break; default: break; } free(it);}
void syntax_dump_expr(expr_t *it) { switch (it->tag) { case EXPR_ALT: printf("alt("); goto bits; case EXPR_SEQ: printf("seq("); bits: syntax_dump_expr(it->as.alt.try); printf(","); syntax_dump_expr(it->as.alt.orelse); printf(")"); break; case EXPR_LAMBDA: printf("lambda("); for (int i = 0; i < it->as.lambda_raw.npatterns;i++) { syntax_dump_expr(it->as.lambda_raw.patterns[i]); printf(": "); } syntax_dump_expr(it->as.lambda_raw.body); printf(")"); break; case EXPR_LET_BINDING: printf("let("); syntax_dump_expr(it->as.let_binding.pattern.expr); printf(":="); syntax_dump_expr(it->as.let_binding.expr); printf(";"); syntax_dump_expr(it->as.let_binding.in); printf(")"); break; case EXPR_CALL: syntax_dump_expr(it->as.call.callee); printf("("); for (int i = 0; i < it->as.call.nargs;i++) { syntax_dump_expr(it->as.call.arguments[i]); printf(","); } printf(")"); break; case EXPR_TUPLE: printf("("); for (int i = 0; i < it->as.tuple.nelements;i++) { syntax_dump_expr(it->as.tuple.elements[i]); printf(","); } printf(")"); break; case EXPR_BUILTIN: printf("<builtin%p>",it->as.builtin); break; case EXPR_LAMBDA_COMPILED: printf("lambda_c(%zu,",it->as.lambda.args); syntax_dump_expr(it->as.lambda.body); printf(")"); break; case EXPR_GROUP: printf("{"); for (int i = 0; i < it->as.group.nclauses;i++) { syntax_dump_expr(it->as.group.clauses[i]); printf(","); } printf("}"); break; case EXPR_STRING_LIT: printf("\"%s\"",it->as.string_lit); break; case EXPR_INT_LIT: printf("%ld", it->as.int_lit); break; case EXPR_FLOAT_LIT: printf("%f", it->as.float_lit); break; case EXPR_PAT_IDENT: printf("%s", it->as.ident); break; case EXPR_VAR: printf("\\%zu", it->as.var); break; case EXPR_CONSTRUCTOR: printf("<%s>", it->as.constructor); break; default: break; }}