harec

[hare] Hare compiler, written in C11 for POSIX OSs
Log | Files | Refs | README | LICENSE

parse.c (57461B)


      1 #include <assert.h>
      2 #include <ctype.h>
      3 #include <stdarg.h>
      4 #include <stdbool.h>
      5 #include <stdio.h>
      6 #include <stdlib.h>
      7 #include <stdnoreturn.h>
      8 #include <string.h>
      9 #include "ast.h"
     10 #include "check.h"
     11 #include "identifier.h"
     12 #include "lex.h"
     13 #include "parse.h"
     14 #include "types.h"
     15 #include "utf8.h"
     16 #include "util.h"
     17 
     18 static void
     19 synassert_msg(bool cond, const char *msg, struct token *tok)
     20 {
     21 	if (!cond) {
     22 		fprintf(stderr, "Syntax error: %s at %s:%d:%d (found '%s')\n", msg,
     23 			sources[tok->loc.file], tok->loc.lineno, tok->loc.colno,
     24 			token_str(tok));
     25 		exit(EXIT_FAILURE);
     26 	}
     27 }
     28 
     29 static noreturn void
     30 vsynerr(struct token *tok, va_list ap)
     31 {
     32 	enum lexical_token t = va_arg(ap, enum lexical_token);
     33 	fprintf(stderr,
     34 		"Syntax error: unexpected '%s' at %s:%d:%d%s",
     35 		token_str(tok), sources[tok->loc.file], tok->loc.lineno,
     36 		tok->loc.colno, t == T_EOF ? "\n" : ", expected " );
     37 	while (t != T_EOF) {
     38 		if (t == T_LITERAL || t == T_NAME) {
     39 			fprintf(stderr, "%s", lexical_token_str(t));
     40 		} else {
     41 			fprintf(stderr, "'%s'", lexical_token_str(t));
     42 		}
     43 		t = va_arg(ap, enum lexical_token);
     44 		fprintf(stderr, "%s", t == T_EOF ? "\n" : ", ");
     45 	}
     46 	exit(EXIT_FAILURE);
     47 }
     48 
     49 static noreturn void
     50 synerr(struct token *tok, ...)
     51 {
     52 	va_list ap;
     53 	va_start(ap, tok);
     54 	vsynerr(tok, ap);
     55 }
     56 
     57 static void
     58 synassert(bool cond, struct token *tok, ...)
     59 {
     60 	if (!cond) {
     61 		va_list ap;
     62 		va_start(ap, tok);
     63 		vsynerr(tok, ap);
     64 	}
     65 }
     66 
     67 static void
     68 want(struct lexer *lexer, enum lexical_token ltok, struct token *tok)
     69 {
     70 	struct token _tok = {0};
     71 	struct token *out = tok ? tok : &_tok;
     72 	lex(lexer, out);
     73 	synassert(out->token == ltok, out, ltok, T_EOF);
     74 	if (!tok) {
     75 		token_finish(out);
     76 	}
     77 }
     78 
     79 static struct ast_expression *
     80 mkexpr(const struct location *loc)
     81 {
     82 	struct ast_expression *exp = xcalloc(1, sizeof(struct ast_expression));
     83 	exp->loc = *loc;
     84 	return exp;
     85 }
     86 
     87 static struct ast_type *
     88 mktype(const struct location *loc)
     89 {
     90 	struct ast_type *t = xcalloc(1, sizeof(struct ast_type));
     91 	t->loc = *loc;
     92 	return t;
     93 }
     94 
     95 static struct ast_function_parameters *
     96 mkfuncparams(const struct location *loc)
     97 {
     98 	struct ast_function_parameters *p =
     99 		xcalloc(1, sizeof(struct ast_function_parameters));
    100 	p->loc = *loc;
    101 	return p;
    102 }
    103 
    104 bool
    105 parse_identifier(struct lexer *lexer, struct identifier *ident, bool trailing)
    106 {
    107 	struct token tok = {0};
    108 	struct identifier *i = ident;
    109 	*ident = (struct identifier){0};
    110 	bool found_trailing = false;
    111 	while (!i->name) {
    112 		switch (lex(lexer, &tok)) {
    113 		case T_NAME:
    114 			i->name = strdup(tok.name);
    115 			token_finish(&tok);
    116 			break;
    117 		default:
    118 			synassert(trailing && i->ns, &tok, T_NAME, T_EOF);
    119 			unlex(lexer, &tok);
    120 			struct identifier *ns = i->ns;
    121 			*i = *ns;
    122 			free(ns);
    123 			found_trailing = true;
    124 			continue;
    125 		}
    126 
    127 		struct identifier *ns;
    128 		switch (lex(lexer, &tok)) {
    129 		case T_DOUBLE_COLON:
    130 			ns = xcalloc(1, sizeof(struct identifier));
    131 			*ns = *i;
    132 			i->ns = ns;
    133 			i->name = NULL;
    134 			break;
    135 		default:
    136 			unlex(lexer, &tok);
    137 			break;
    138 		}
    139 	}
    140 	return found_trailing;
    141 }
    142 
    143 static void
    144 parse_name_list(struct lexer *lexer, struct ast_imports *name)
    145 {
    146 	bool more = true;
    147 	struct ast_imports **next = &name->next;
    148 	while (more) {
    149 		struct token tok = {0};
    150 		want(lexer, T_NAME, &tok);
    151 		name->ident.name = strdup(tok.name);
    152 		name->loc = tok.loc;
    153 		token_finish(&tok);
    154 
    155 		switch (lex(lexer, &tok)) {
    156 		case T_COMMA:
    157 			switch (lex(lexer, &tok)) {
    158 			case T_RBRACE:
    159 				more = false;
    160 				break;
    161 			default:
    162 				unlex(lexer, &tok);
    163 				name = xcalloc(1, sizeof(struct ast_imports));
    164 				*next = name;
    165 				next = &name->next;
    166 			}
    167 			break;
    168 		case T_EQUAL:
    169 			name->alias = xcalloc(1, sizeof(struct identifier));
    170 			*name->alias = name->ident;
    171 			break;
    172 		case T_RBRACE:
    173 			more = false;
    174 			break;
    175 		default:
    176 			synerr(&tok, T_RBRACE, T_EQUAL, T_COMMA, T_EOF);
    177 			break;
    178 		}
    179 	}
    180 }
    181 
    182 static void
    183 parse_import(struct lexer *lexer, struct ast_imports *imports)
    184 {
    185 	struct identifier ident = {0};
    186 	struct token tok = {0};
    187 	imports->mode = 0;
    188 	while (true) {
    189 		bool trailing_colon = parse_identifier(lexer, &ident, true);
    190 		switch (lex(lexer, &tok)) {
    191 		case T_EQUAL:
    192 			synassert(!trailing_colon, &tok, T_NAME, T_EOF);
    193 			synassert(!(imports->mode & AST_IMPORT_ALIAS), &tok,
    194 					T_SEMICOLON, T_LBRACE, T_EOF);
    195 			imports->mode |= AST_IMPORT_ALIAS;
    196 			imports->alias = xcalloc(1, sizeof(struct identifier));
    197 			*imports->alias = ident;
    198 			break;
    199 		case T_LBRACE:
    200 			synassert(trailing_colon, &tok, T_DOUBLE_COLON, T_EOF);
    201 			imports->mode |= AST_IMPORT_MEMBERS;
    202 			imports->ident = ident;
    203 			imports->members = xcalloc(1, sizeof(struct ast_imports));
    204 			parse_name_list(lexer, imports->members);
    205 			want(lexer, T_SEMICOLON, &tok);
    206 			return;
    207 		case T_SEMICOLON:
    208 			synassert(!trailing_colon, &tok, T_NAME, T_EOF);
    209 			imports->ident = ident;
    210 			return;
    211 		case T_TIMES:
    212 			synassert(trailing_colon, &tok, T_DOUBLE_COLON, T_EOF);
    213 			synassert(!(imports->mode & AST_IMPORT_ALIAS), &tok,
    214 					T_SEMICOLON, T_LBRACE, T_EOF);
    215 			imports->mode |= AST_IMPORT_WILDCARD;
    216 			imports->alias = NULL;
    217 			imports->ident = ident;
    218 			want(lexer, T_SEMICOLON, &tok);
    219 			return;
    220 		default:
    221 			synassert(!trailing_colon, &tok, T_EQUAL, T_SEMICOLON, T_EOF);
    222 			synassert(trailing_colon, &tok, T_NAME, T_LBRACE, T_EOF);
    223 			break;
    224 		}
    225 	}
    226 }
    227 
    228 static void
    229 parse_imports(struct lexer *lexer, struct ast_subunit *subunit)
    230 {
    231 	struct token tok = {0};
    232 	struct ast_imports **next = &subunit->imports;
    233 
    234 	bool more = true;
    235 	while (more) {
    236 		struct ast_imports *imports;
    237 		switch (lex(lexer, &tok)) {
    238 		case T_USE:
    239 			imports = xcalloc(1, sizeof(struct ast_imports));
    240 			parse_import(lexer, imports);
    241 			*next = imports;
    242 			next = &imports->next;
    243 			break;
    244 		default:
    245 			unlex(lexer, &tok);
    246 			more = false;
    247 			break;
    248 		}
    249 	}
    250 }
    251 
    252 static void
    253 parse_parameter_list(struct lexer *lexer, struct ast_function_type *type)
    254 {
    255 	struct token tok = {0};
    256 	bool more = true;
    257 	type->params = mkfuncparams(&lexer->loc);
    258 	struct ast_function_parameters *next = type->params;
    259 	while (more) {
    260 		switch (lex(lexer, &tok)) {
    261 		case T_UNDERSCORE:
    262 			break;
    263 		case T_NAME:
    264 			next->name = tok.name; // Assumes ownership
    265 			break;
    266 		default:
    267 			synerr(&tok, T_UNDERSCORE, T_NAME, T_EOF);
    268 		}
    269 		want(lexer, T_COLON, NULL);
    270 		next->type = parse_type(lexer);
    271 
    272 		switch (lex(lexer, &tok)) {
    273 		case T_COMMA:
    274 			switch (lex(lexer, &tok)) {
    275 			case T_ELLIPSIS:
    276 				type->variadism = VARIADISM_C;
    277 				if (lex(lexer, &tok) != T_COMMA) {
    278 					unlex(lexer, &tok);
    279 				}
    280 				more = false;
    281 				break;
    282 			case T_RPAREN:
    283 				more = false;
    284 				unlex(lexer, &tok);
    285 				break;
    286 			default:
    287 				unlex(lexer, &tok);
    288 				next->next = mkfuncparams(&lexer->loc);
    289 				next = next->next;
    290 				break;
    291 			}
    292 			break;
    293 		case T_ELLIPSIS:
    294 			type->variadism = VARIADISM_HARE;
    295 			if (lex(lexer, &tok) != T_COMMA) {
    296 				unlex(lexer, &tok);
    297 			}
    298 			more = false;
    299 			break;
    300 		default:
    301 			more = false;
    302 			unlex(lexer, &tok);
    303 			break;
    304 		}
    305 	}
    306 }
    307 
    308 static void
    309 parse_prototype(struct lexer *lexer, struct ast_function_type *type)
    310 {
    311 	want(lexer, T_LPAREN, NULL);
    312 	struct token tok = {0};
    313 	if (lex(lexer, &tok) != T_RPAREN) {
    314 		unlex(lexer, &tok);
    315 		parse_parameter_list(lexer, type);
    316 		want(lexer, T_RPAREN, NULL);
    317 	}
    318 	type->result = parse_type(lexer);
    319 }
    320 
    321 static enum type_storage
    322 parse_integer_type(struct lexer *lexer)
    323 {
    324 	struct token tok = {0};
    325 	switch (lex(lexer, &tok)) {
    326 	case T_I8:
    327 		return STORAGE_I8;
    328 	case T_I16:
    329 		return STORAGE_I16;
    330 	case T_I32:
    331 		return STORAGE_I32;
    332 	case T_I64:
    333 		return STORAGE_I64;
    334 	case T_U8:
    335 		return STORAGE_U8;
    336 	case T_U16:
    337 		return STORAGE_U16;
    338 	case T_U32:
    339 		return STORAGE_U32;
    340 	case T_U64:
    341 		return STORAGE_U64;
    342 	case T_INT:
    343 		return STORAGE_INT;
    344 	case T_UINT:
    345 		return STORAGE_UINT;
    346 	case T_SIZE:
    347 		return STORAGE_SIZE;
    348 	case T_UINTPTR:
    349 		return STORAGE_UINTPTR;
    350 	case T_CHAR:
    351 		return STORAGE_CHAR;
    352 	default:
    353 		assert(0);
    354 	}
    355 }
    356 
    357 static struct ast_type *
    358 parse_primitive_type(struct lexer *lexer)
    359 {
    360 	struct token tok = {0};
    361 	struct ast_type *type = mktype(&lexer->loc);
    362 	switch (lex(lexer, &tok)) {
    363 	case T_I8:
    364 	case T_I16:
    365 	case T_I32:
    366 	case T_I64:
    367 	case T_U8:
    368 	case T_U16:
    369 	case T_U32:
    370 	case T_U64:
    371 	case T_INT:
    372 	case T_UINT:
    373 	case T_SIZE:
    374 	case T_UINTPTR:
    375 	case T_CHAR:
    376 		unlex(lexer, &tok);
    377 		type->storage = parse_integer_type(lexer);
    378 		break;
    379 	case T_RUNE:
    380 		type->storage = STORAGE_RUNE;
    381 		break;
    382 	case T_STR:
    383 		type->storage = STORAGE_STRING;
    384 		break;
    385 	case T_F32:
    386 		type->storage = STORAGE_F32;
    387 		break;
    388 	case T_F64:
    389 		type->storage = STORAGE_F64;
    390 		break;
    391 	case T_BOOL:
    392 		type->storage = STORAGE_BOOL;
    393 		break;
    394 	case T_VOID:
    395 		type->storage = STORAGE_VOID;
    396 		break;
    397 	case T_VALIST:
    398 		type->storage = STORAGE_VALIST;
    399 		break;
    400 	default:
    401 		assert(0);
    402 	}
    403 	return type;
    404 }
    405 
    406 static struct ast_expression *parse_binding_list(
    407 		struct lexer *lexer, bool is_static);
    408 static struct ast_expression *parse_object_selector(struct lexer *lexer);
    409 
    410 static struct ast_type *
    411 parse_enum_type(struct identifier *ident, struct lexer *lexer)
    412 {
    413 	struct token tok = {0};
    414 	struct ast_type *type = mktype(&lexer->loc);
    415 	type->storage = STORAGE_ENUM;
    416 	identifier_dup(&type->alias, ident);
    417 	struct ast_enum_field **next = &type->_enum.values;
    418 	switch (lex(lexer, &tok)) {
    419 	case T_LBRACE:
    420 		type->_enum.storage = STORAGE_INT;
    421 		unlex(lexer, &tok);
    422 		break;
    423 	case T_I8:
    424 	case T_I16:
    425 	case T_I32:
    426 	case T_I64:
    427 	case T_U8:
    428 	case T_U16:
    429 	case T_U32:
    430 	case T_U64:
    431 	case T_INT:
    432 	case T_UINT:
    433 	case T_SIZE:
    434 	case T_UINTPTR:
    435 	case T_CHAR:
    436 		unlex(lexer, &tok);
    437 		type->_enum.storage = parse_integer_type(lexer);
    438 		break;
    439 	case T_RUNE:
    440 		type->_enum.storage = STORAGE_RUNE;
    441 		break;
    442 	default:
    443 		synassert_msg(false, "Enum storage must be an integer or rune", &tok);
    444 	}
    445 	want(lexer, T_LBRACE, NULL);
    446 	while (tok.token != T_RBRACE) {
    447 		*next = xcalloc(1, sizeof(struct ast_enum_field));
    448 		want(lexer, T_NAME, &tok);
    449 		(*next)->name = tok.name;
    450 		(*next)->loc = tok.loc;
    451 		if (lex(lexer, &tok) == T_EQUAL) {
    452 			(*next)->value = parse_expression(lexer);
    453 		} else {
    454 			unlex(lexer, &tok);
    455 		}
    456 		next = &(*next)->next;
    457 		switch (lex(lexer, &tok)) {
    458 		case T_COMMA:
    459 			if (lex(lexer, &tok) != T_RBRACE) {
    460 				unlex(lexer, &tok);
    461 			}
    462 			break;
    463 		case T_RBRACE:
    464 			break;
    465 		default:
    466 			synerr(&tok, T_COMMA, T_RBRACE, T_EOF);
    467 		}
    468 	}
    469 	return type;
    470 }
    471 
    472 static struct ast_type *
    473 parse_struct_union_type(struct lexer *lexer)
    474 {
    475 	struct token tok = {0};
    476 	struct ast_type *type = mktype(&lexer->loc);
    477 	struct ast_struct_union_type *next = &type->struct_union;
    478 	switch (lex(lexer, &tok)) {
    479 	case T_STRUCT:
    480 		type->storage = STORAGE_STRUCT;
    481 		break;
    482 	case T_UNION:
    483 		type->storage = STORAGE_UNION;
    484 		break;
    485 	default:
    486 		synerr(&tok, T_STRUCT, T_UNION, T_EOF);
    487 		break;
    488 	}
    489 	want(lexer, T_LBRACE, NULL);
    490 	while (tok.token != T_RBRACE) {
    491 		if (lex(lexer, &tok) == T_ATTR_OFFSET) {
    492 			want(lexer, T_LPAREN, NULL);
    493 			next->offset = parse_expression(lexer);
    494 			want(lexer, T_RPAREN, NULL);
    495 		} else {
    496 			unlex(lexer, &tok);
    497 		}
    498 
    499 		char *name;
    500 		switch (lex(lexer, &tok)) {
    501 		case T_NAME:
    502 			name = tok.name;
    503 			struct location loc = tok.loc;
    504 			switch (lex(lexer, &tok)) {
    505 			case T_COLON:
    506 				next->name = name;
    507 				next->type = parse_type(lexer);
    508 				break;
    509 			case T_DOUBLE_COLON:
    510 				next->type = mktype(&loc);
    511 				next->type->storage = STORAGE_ALIAS;
    512 				next->type->unwrap = false;
    513 				parse_identifier(lexer, &next->type->alias, false);
    514 				struct identifier *i = &next->type->alias;
    515 				while (i->ns != NULL) {
    516 					i = i->ns;
    517 				}
    518 				i->ns = xcalloc(sizeof(struct identifier), 1);
    519 				i->ns->name = name;
    520 				break;
    521 			default:
    522 				unlex(lexer, &tok);
    523 				next->type = mktype(&loc);
    524 				next->type->storage = STORAGE_ALIAS;
    525 				next->type->alias.name = name;
    526 				next->type->unwrap = false;
    527 				break;
    528 			}
    529 			break;
    530 		case T_STRUCT:
    531 		case T_UNION:
    532 			unlex(lexer, &tok);
    533 			next->name = NULL;
    534 			next->type = parse_type(lexer);
    535 			break;
    536 		default:
    537 			synerr(&tok, T_NAME, T_STRUCT, T_UNION, T_EOF);
    538 		}
    539 		switch (lex(lexer, &tok)) {
    540 		case T_COMMA:
    541 			if (lex(lexer, &tok) != T_RBRACE) {
    542 				unlex(lexer, &tok);
    543 				next->next = xcalloc(1,
    544 					sizeof(struct ast_struct_union_type));
    545 				next = next->next;
    546 			}
    547 			break;
    548 		case T_RBRACE:
    549 			break;
    550 		default:
    551 			synerr(&tok, T_COMMA, T_RBRACE, T_EOF);
    552 		}
    553 	}
    554 	return type;
    555 }
    556 
    557 static struct ast_type *
    558 parse_tagged_type(struct lexer *lexer, struct ast_type *first)
    559 {
    560 	struct ast_type *type = mktype(&first->loc);
    561 	type->storage = STORAGE_TAGGED;
    562 	struct ast_tagged_union_type *next = &type->tagged_union;
    563 	next->type = first;
    564 	struct token tok = {0};
    565 	while (tok.token != T_RPAREN) {
    566 		next->next = xcalloc(sizeof(struct ast_tagged_union_type), 1);
    567 		next = next->next;
    568 		next->type = parse_type(lexer);
    569 		switch (lex(lexer, &tok)) {
    570 		case T_BOR:
    571 			if (lex(lexer, &tok) != T_RPAREN) {
    572 				unlex(lexer, &tok);
    573 			}
    574 			break;
    575 		case T_RPAREN:
    576 			break;
    577 		default:
    578 			synerr(&tok, T_BOR, T_RPAREN, T_EOF);
    579 		}
    580 	}
    581 	return type;
    582 }
    583 
    584 static struct ast_type *
    585 parse_tuple_type(struct lexer *lexer, struct ast_type *first)
    586 {
    587 	struct ast_type *type = mktype(&first->loc);
    588 	type->storage = STORAGE_TUPLE;
    589 	struct ast_tuple_type *next = &type->tuple;
    590 	next->type = first;
    591 	struct token tok = {0};
    592 	while (tok.token != T_RPAREN) {
    593 		next->next = xcalloc(sizeof(struct ast_tuple_type), 1);
    594 		next = next->next;
    595 		next->type = parse_type(lexer);
    596 		switch (lex(lexer, &tok)) {
    597 		case T_COMMA:
    598 			if (lex(lexer, &tok) != T_RPAREN) {
    599 				unlex(lexer, &tok);
    600 			}
    601 			break;
    602 		case T_RPAREN:
    603 			break;
    604 		default:
    605 			synerr(&tok, T_COMMA, T_RPAREN, T_EOF);
    606 		}
    607 	}
    608 	return type;
    609 }
    610 
    611 static struct ast_type *
    612 parse_tagged_or_tuple_type(struct lexer *lexer)
    613 {
    614 	struct ast_type *type = parse_type(lexer);
    615 	struct token tok = {0};
    616 	switch (lex(lexer, &tok)) {
    617 	case T_BOR:
    618 		return parse_tagged_type(lexer, type);
    619 	case T_COMMA:
    620 		return parse_tuple_type(lexer, type);
    621 	default:
    622 		synerr(&tok, T_BOR, T_COMMA, T_EOF);
    623 	}
    624 	assert(0); // Unreachable
    625 }
    626 
    627 struct ast_type *
    628 parse_type(struct lexer *lexer)
    629 {
    630 	struct token tok = {0};
    631 	uint32_t flags = 0;
    632 	switch (lex(lexer, &tok)) {
    633 	case T_CONST:
    634 		flags |= TYPE_CONST;
    635 		break;
    636 	default:
    637 		unlex(lexer, &tok);
    638 		break;
    639 	}
    640 	switch (lex(lexer, &tok)) {
    641 	case T_LNOT:
    642 		flags |= TYPE_ERROR;
    643 		break;
    644 	default:
    645 		unlex(lexer, &tok);
    646 		break;
    647 	}
    648 	struct ast_type *type = NULL;
    649 	bool _noreturn = false, nullable = false, unwrap = false;
    650 	switch (lex(lexer, &tok)) {
    651 	case T_BOOL:
    652 	case T_CHAR:
    653 	case T_F32:
    654 	case T_F64:
    655 	case T_I16:
    656 	case T_I32:
    657 	case T_I64:
    658 	case T_I8:
    659 	case T_INT:
    660 	case T_RUNE:
    661 	case T_SIZE:
    662 	case T_STR:
    663 	case T_U16:
    664 	case T_U32:
    665 	case T_U64:
    666 	case T_U8:
    667 	case T_UINT:
    668 	case T_UINTPTR:
    669 	case T_VALIST:
    670 	case T_VOID:
    671 		unlex(lexer, &tok);
    672 		type = parse_primitive_type(lexer);
    673 		break;
    674 	case T_NULLABLE:
    675 		nullable = true;
    676 		want(lexer, T_TIMES, NULL);
    677 		/* fallthrough */
    678 	case T_TIMES:
    679 		type = mktype(&lexer->loc);
    680 		type->storage = STORAGE_POINTER;
    681 		type->pointer.referent = parse_type(lexer);
    682 		if (nullable) {
    683 			type->pointer.flags |= PTR_NULLABLE;
    684 		}
    685 		break;
    686 	case T_STRUCT:
    687 	case T_UNION:
    688 		unlex(lexer, &tok);
    689 		type = parse_struct_union_type(lexer);
    690 		break;
    691 	case T_LPAREN:
    692 		type = parse_tagged_or_tuple_type(lexer);
    693 		break;
    694 	case T_LBRACKET:
    695 		type = mktype(&lexer->loc);
    696 		switch (lex(lexer, &tok)) {
    697 		case T_RBRACKET:
    698 			type->storage = STORAGE_SLICE;
    699 			type->slice.members = parse_type(lexer);
    700 			break;
    701 		case T_TIMES:
    702 			type->storage = STORAGE_ARRAY;
    703 			type->array.length = NULL;
    704 			want(lexer, T_RBRACKET, NULL);
    705 			type->array.members = parse_type(lexer);
    706 			break;
    707 		case T_UNDERSCORE:
    708 			type->storage = STORAGE_ARRAY;
    709 			type->array.length = NULL;
    710 			type->array.contextual = true;
    711 			want(lexer, T_RBRACKET, NULL);
    712 			type->array.members = parse_type(lexer);
    713 			break;
    714 		default:
    715 			type->storage = STORAGE_ARRAY;
    716 			unlex(lexer, &tok);
    717 			type->array.length = parse_expression(lexer);
    718 			want(lexer, T_RBRACKET, NULL);
    719 			type->array.members = parse_type(lexer);
    720 			break;
    721 		}
    722 		break;
    723 	case T_ATTR_NORETURN:
    724 		_noreturn = true;
    725 		want(lexer, T_FN, NULL);
    726 		// fallthrough
    727 	case T_FN:
    728 		type = mktype(&lexer->loc);
    729 		type->storage = STORAGE_FUNCTION;
    730 		parse_prototype(lexer, &type->func);
    731 		if (_noreturn) {
    732 			type->func.flags |= FN_NORETURN;
    733 		}
    734 		break;
    735 	case T_ELLIPSIS:
    736 		unwrap = true;
    737 		want(lexer, T_NAME, &tok);
    738 		// Fallthrough
    739 	case T_NAME:
    740 		unlex(lexer, &tok);
    741 		type = mktype(&lexer->loc);
    742 		type->storage = STORAGE_ALIAS;
    743 		type->unwrap = unwrap;
    744 		parse_identifier(lexer, &type->alias, false);
    745 		break;
    746 	default:
    747 		synassert_msg(false, "expected type", &tok);
    748 		break;
    749 	}
    750 	type->flags |= flags;
    751 
    752 	return type;
    753 }
    754 
    755 static struct ast_expression *
    756 parse_access(struct lexer *lexer, struct identifier ident)
    757 {
    758 	struct ast_expression *exp = mkexpr(&lexer->loc);
    759 	exp->type = EXPR_ACCESS;
    760 	exp->access.type = ACCESS_IDENTIFIER;
    761 	exp->access.ident = ident;
    762 	return exp;
    763 }
    764 
    765 static struct ast_expression *
    766 parse_constant(struct lexer *lexer)
    767 {
    768 	struct ast_expression *exp = mkexpr(&lexer->loc);
    769 	exp->type = EXPR_CONSTANT;
    770 
    771 	struct token tok = {0};
    772 	switch (lex(lexer, &tok)) {
    773 	case T_TRUE:
    774 		exp->constant.storage = STORAGE_BOOL;
    775 		exp->constant.bval = true;
    776 		return exp;
    777 	case T_FALSE:
    778 		exp->constant.storage = STORAGE_BOOL;
    779 		exp->constant.bval = false;
    780 		return exp;
    781 	case T_NULL:
    782 		exp->constant.storage = STORAGE_NULL;
    783 		return exp;
    784 	case T_VOID:
    785 		exp->constant.storage = STORAGE_VOID;
    786 		return exp;
    787 	case T_LITERAL:
    788 		exp->constant.storage = tok.storage;
    789 		break;
    790 	default:
    791 		synerr(&tok, T_LITERAL, T_TRUE,
    792 			T_FALSE, T_NULL, T_VOID, T_EOF);
    793 		break;
    794 	}
    795 
    796 	switch (tok.storage) {
    797 	case STORAGE_CHAR:
    798 	case STORAGE_U8:
    799 	case STORAGE_U16:
    800 	case STORAGE_U32:
    801 	case STORAGE_U64:
    802 	case STORAGE_UINT:
    803 	case STORAGE_UINTPTR:
    804 	case STORAGE_SIZE:
    805 		exp->constant.uval = (uintmax_t)tok.uval;
    806 		break;
    807 	case STORAGE_I8:
    808 	case STORAGE_I16:
    809 	case STORAGE_I32:
    810 	case STORAGE_I64:
    811 	case STORAGE_ICONST:
    812 	case STORAGE_INT:
    813 		exp->constant.ival = (intmax_t)tok.ival;
    814 		break;
    815 	case STORAGE_F32:
    816 	case STORAGE_F64:
    817 	case STORAGE_FCONST:
    818 		exp->constant.fval = tok.fval;
    819 		break;
    820 	case STORAGE_RCONST:
    821 		exp->constant.rune = tok.rune;
    822 		break;
    823 	case STORAGE_STRING:
    824 		exp->constant.string.len = tok.string.len;
    825 		exp->constant.string.value = tok.string.value;
    826 		while (lex(lexer, &tok) == T_LITERAL
    827 				&& tok.storage == STORAGE_STRING) {
    828 			size_t len = exp->constant.string.len;
    829 			exp->constant.string.value = xrealloc(
    830 				exp->constant.string.value,
    831 				len + tok.string.len);
    832 			memcpy(exp->constant.string.value + len,
    833 				tok.string.value, tok.string.len);
    834 			exp->constant.string.len += tok.string.len;
    835 		}
    836 		unlex(lexer, &tok);
    837 		break;
    838 	case STORAGE_BOOL:
    839 	case STORAGE_NULL:
    840 	case STORAGE_VOID:
    841 		assert(0); // Handled above
    842 	case STORAGE_ALIAS:
    843 	case STORAGE_ARRAY:
    844 	case STORAGE_ENUM:
    845 	case STORAGE_FUNCTION:
    846 	case STORAGE_POINTER:
    847 	case STORAGE_RUNE:
    848 	case STORAGE_SLICE:
    849 	case STORAGE_STRUCT:
    850 	case STORAGE_TAGGED:
    851 	case STORAGE_TUPLE:
    852 	case STORAGE_UNION:
    853 	case STORAGE_VALIST:
    854 		assert(0); // Handled in a different nonterminal
    855 	}
    856 	return exp;
    857 }
    858 
    859 static struct ast_expression *
    860 parse_array_literal(struct lexer *lexer)
    861 {
    862 	struct token tok;
    863 	want(lexer, T_LBRACKET, &tok);
    864 
    865 	struct ast_expression *exp = mkexpr(&lexer->loc);
    866 	exp->type = EXPR_CONSTANT;
    867 	exp->constant.storage = STORAGE_ARRAY;
    868 
    869 	struct ast_array_constant *item, **next = &exp->constant.array;
    870 
    871 	while (lex(lexer, &tok) != T_RBRACKET) {
    872 		unlex(lexer, &tok);
    873 
    874 		item = *next = xcalloc(1, sizeof(struct ast_array_constant));
    875 		item->value = parse_expression(lexer);
    876 		next = &item->next;
    877 
    878 		switch (lex(lexer, &tok)) {
    879 		case T_ELLIPSIS:
    880 			item->expand = true;
    881 			lex(lexer, &tok);
    882 			if (tok.token == T_COMMA) {
    883 				want(lexer, T_RBRACKET, &tok);
    884 				unlex(lexer, &tok);
    885 			} else if (tok.token == T_RBRACKET) {
    886 				unlex(lexer, &tok);
    887 			} else {
    888 				synerr(&tok, T_COMMA, T_RBRACKET, T_EOF);
    889 			}
    890 			break;
    891 		case T_COMMA:
    892 			// Move on
    893 			break;
    894 		case T_RBRACKET:
    895 			unlex(lexer, &tok);
    896 			break;
    897 		default:
    898 			synerr(&tok, T_ELLIPSIS, T_COMMA, T_RBRACKET, T_EOF);
    899 		}
    900 	}
    901 	return exp;
    902 }
    903 
    904 static struct ast_expression *parse_struct_literal(struct lexer *lexer,
    905 	struct identifier ident);
    906 
    907 static struct ast_field_value *
    908 parse_field_value(struct lexer *lexer)
    909 {
    910 	struct ast_field_value *exp =
    911 		xcalloc(sizeof(struct ast_field_value), 1);
    912 	char *name;
    913 	struct token tok = {0};
    914 	struct identifier ident = {0};
    915 	struct identifier *i;
    916 	switch (lex(lexer, &tok)) {
    917 	case T_NAME:
    918 		name = tok.name;
    919 		switch (lex(lexer, &tok)) {
    920 		case T_COLON:
    921 			exp->name = name;
    922 			exp->type = parse_type(lexer);
    923 			want(lexer, T_EQUAL, NULL);
    924 			exp->initializer = parse_expression(lexer);
    925 			break;
    926 		case T_EQUAL:
    927 			exp->name = name;
    928 			exp->initializer = parse_expression(lexer);
    929 			break;
    930 		case T_DOUBLE_COLON:
    931 			i = &ident;
    932 			parse_identifier(lexer, i, false);
    933 			while (i->ns != NULL) {
    934 				i = i->ns;
    935 			}
    936 			i->ns = xcalloc(sizeof(struct identifier), 1);
    937 			i->ns->name = name;
    938 			exp->initializer = parse_struct_literal(lexer, ident);
    939 			break;
    940 		default:
    941 			unlex(lexer, &tok);
    942 			ident.name = name;
    943 			ident.ns = NULL;
    944 			exp->initializer = parse_struct_literal(lexer, ident);
    945 			break;
    946 		}
    947 		break;
    948 	case T_STRUCT:
    949 		exp->initializer = parse_struct_literal(lexer, ident);
    950 		break;
    951 	default:
    952 		assert(0);
    953 	}
    954 	return exp;
    955 }
    956 
    957 static struct ast_expression *
    958 parse_struct_literal(struct lexer *lexer, struct identifier ident)
    959 {
    960 	want(lexer, T_LBRACE, NULL);
    961 	struct ast_expression *exp = mkexpr(&lexer->loc);
    962 	exp->type = EXPR_STRUCT;
    963 	exp->_struct.type = ident;
    964 	struct ast_field_value **next = &exp->_struct.fields;
    965 	struct token tok = {0};
    966 	while (tok.token != T_RBRACE) {
    967 		switch (lex(lexer, &tok)) {
    968 		case T_ELLIPSIS:
    969 			synassert(ident.name != NULL, &tok, T_RBRACE, T_EOF);
    970 			exp->_struct.autofill = true;
    971 			if (lex(lexer, &tok) != T_COMMA) {
    972 				unlex(lexer, &tok);
    973 			}
    974 			want(lexer, T_RBRACE, &tok);
    975 			unlex(lexer, &tok);
    976 			break;
    977 		case T_NAME:
    978 		case T_STRUCT:
    979 			unlex(lexer, &tok);
    980 			*next = parse_field_value(lexer);
    981 			next = &(*next)->next;
    982 			break;
    983 		default:
    984 			synerr(&tok, T_ELLIPSIS, T_NAME, T_RBRACE,
    985 				T_STRUCT, T_EOF);
    986 			break;
    987 		}
    988 		switch (lex(lexer, &tok)) {
    989 		case T_COMMA:
    990 			if (lex(lexer, &tok) != T_RBRACE) {
    991 				unlex(lexer, &tok);
    992 			}
    993 			break;
    994 		case T_RBRACE:
    995 			break;
    996 		default:
    997 			synerr(&tok, T_COMMA, T_RBRACE, T_EOF);
    998 		}
    999 	}
   1000 	return exp;
   1001 }
   1002 
   1003 static struct ast_expression *
   1004 parse_tuple_expression(struct lexer *lexer, struct ast_expression *first)
   1005 {
   1006 	struct ast_expression *exp = mkexpr(&first->loc);
   1007 	exp->type = EXPR_TUPLE;
   1008 
   1009 	bool more = true;
   1010 	struct token tok = {0};
   1011 	struct ast_expression_tuple *tuple = &exp->tuple;
   1012 	tuple->expr = first;
   1013 	tuple->next = xcalloc(1, sizeof(struct ast_expression_tuple));
   1014 	tuple = tuple->next;
   1015 
   1016 	while (more) {
   1017 		tuple->expr = parse_expression(lexer);
   1018 
   1019 		switch (lex(lexer, &tok)) {
   1020 		case T_RPAREN:
   1021 			more = false;
   1022 			break;
   1023 		case T_COMMA:
   1024 			if (lex(lexer, &tok) == T_RPAREN) {
   1025 				more = false;
   1026 			} else {
   1027 				unlex(lexer, &tok);
   1028 				tuple->next = xcalloc(1,
   1029 					sizeof(struct ast_expression_tuple));
   1030 				tuple = tuple->next;
   1031 			}
   1032 			break;
   1033 		default:
   1034 			synerr(&tok, T_RPAREN, T_COMMA, T_EOF);
   1035 		}
   1036 	}
   1037 
   1038 	return exp;
   1039 }
   1040 
   1041 static struct ast_expression *
   1042 parse_plain_expression(struct lexer *lexer)
   1043 {
   1044 	struct token tok = {0};
   1045 	struct ast_expression *exp;
   1046 	switch (lex(lexer, &tok)) {
   1047 	// plain-expression
   1048 	case T_LITERAL:
   1049 	case T_TRUE:
   1050 	case T_FALSE:
   1051 	case T_NULL:
   1052 	case T_VOID:
   1053 		unlex(lexer, &tok);
   1054 		return parse_constant(lexer);
   1055 	case T_NAME:
   1056 		unlex(lexer, &tok);
   1057 		struct identifier ident = {0};
   1058 		parse_identifier(lexer, &ident, false);
   1059 		switch (lex(lexer, &tok)) {
   1060 		case T_LBRACE:
   1061 			unlex(lexer, &tok);
   1062 			return parse_struct_literal(lexer, ident);
   1063 		default:
   1064 			unlex(lexer, &tok);
   1065 			return parse_access(lexer, ident);
   1066 		}
   1067 		assert(0);
   1068 	case T_LBRACKET:
   1069 		unlex(lexer, &tok);
   1070 		return parse_array_literal(lexer);
   1071 	case T_STRUCT:
   1072 		ident.name = NULL;
   1073 		ident.ns = NULL;
   1074 		return parse_struct_literal(lexer, ident);
   1075 	// nested-expression
   1076 	case T_LPAREN:
   1077 		exp = parse_expression(lexer);
   1078 		switch (lex(lexer, &tok)) {
   1079 		case T_RPAREN:
   1080 			return exp;
   1081 		case T_COMMA:
   1082 			return parse_tuple_expression(lexer, exp);
   1083 		default:
   1084 			synerr(&tok, T_RPAREN, T_COMMA, T_EOF);
   1085 		};
   1086 		assert(0); // Unreachable
   1087 	default:
   1088 		synerr(&tok, T_LITERAL, T_NAME,
   1089 			T_LBRACKET, T_STRUCT, T_LPAREN, T_EOF);
   1090 	}
   1091 	assert(0); // Unreachable
   1092 }
   1093 
   1094 static struct ast_expression *
   1095 parse_assertion_expression(struct lexer *lexer, bool is_static)
   1096 {
   1097 	struct ast_expression *exp = mkexpr(&lexer->loc);
   1098 	exp->type = EXPR_ASSERT;
   1099 	exp->assert.is_static = is_static;
   1100 
   1101 	struct token tok;
   1102 	switch (lex(lexer, &tok)) {
   1103 	case T_ASSERT:
   1104 	case T_ABORT:
   1105 		break;
   1106 	default:
   1107 		synerr(&tok, T_ASSERT, T_ABORT, T_EOF);
   1108 	}
   1109 
   1110 	switch (tok.token) {
   1111 	case T_ASSERT:
   1112 		want(lexer, T_LPAREN, &tok);
   1113 		exp->assert.cond = parse_expression(lexer);
   1114 		if (lex(lexer, &tok) == T_COMMA) {
   1115 			exp->assert.message = parse_constant(lexer);
   1116 		} else {
   1117 			unlex(lexer, &tok);
   1118 		}
   1119 		want(lexer, T_RPAREN, &tok);
   1120 		break;
   1121 	case T_ABORT:
   1122 		want(lexer, T_LPAREN, &tok);
   1123 		if (lex(lexer, &tok) != T_RPAREN) {
   1124 			unlex(lexer, &tok);
   1125 			exp->assert.message = parse_constant(lexer);
   1126 			want(lexer, T_RPAREN, &tok);
   1127 		}
   1128 		break;
   1129 	default:
   1130 		assert(0); // Invariant
   1131 	}
   1132 
   1133 	return exp;
   1134 }
   1135 
   1136 static struct ast_expression *
   1137 parse_measurement_expression(struct lexer *lexer)
   1138 {
   1139 	struct ast_expression *exp = mkexpr(&lexer->loc);
   1140 	exp->type = EXPR_MEASURE;
   1141 
   1142 	struct token tok;
   1143 	lex(lexer, &tok);
   1144 
   1145 	want(lexer, T_LPAREN, NULL);
   1146 	switch (tok.token) {
   1147 	case T_SIZE:
   1148 		exp->measure.op = M_SIZE;
   1149 		exp->measure.type = parse_type(lexer);
   1150 		break;
   1151 	case T_LEN:
   1152 		exp->measure.op = M_LEN;
   1153 		exp->measure.value = parse_expression(lexer);
   1154 		break;
   1155 	case T_OFFSET:
   1156 		exp->measure.op = M_OFFSET;
   1157 		// Let check error out on non-field-accesses
   1158 		exp->measure.value = parse_expression(lexer);
   1159 		break;
   1160 	default:
   1161 		synerr(&tok, T_SIZE, T_LEN, T_OFFSET, T_EOF);
   1162 	}
   1163 
   1164 	want(lexer, T_RPAREN, NULL);
   1165 	return exp;
   1166 }
   1167 
   1168 static struct ast_expression *
   1169 parse_call_expression(struct lexer *lexer, struct ast_expression *lvalue)
   1170 {
   1171 	struct token tok;
   1172 	want(lexer, T_LPAREN, &tok);
   1173 
   1174 	struct ast_expression *expr = mkexpr(&lexer->loc);
   1175 	expr->type = EXPR_CALL;
   1176 	expr->call.lvalue = lvalue;
   1177 
   1178 	struct ast_call_argument *arg, **next = &expr->call.args;
   1179 	while (lex(lexer, &tok) != T_RPAREN) {
   1180 		unlex(lexer, &tok);
   1181 		arg = *next = xcalloc(1, sizeof(struct ast_call_argument));
   1182 		arg->value = parse_expression(lexer);
   1183 
   1184 		if (lex(lexer, &tok) == T_ELLIPSIS) {
   1185 			arg->variadic = true;
   1186 		} else {
   1187 			unlex(lexer, &tok);
   1188 		}
   1189 
   1190 		switch (lex(lexer, &tok)) {
   1191 		case T_COMMA:
   1192 			break;
   1193 		case T_RPAREN:
   1194 			unlex(lexer, &tok);
   1195 			break;
   1196 		default:
   1197 			synerr(&tok, T_COMMA, T_RPAREN, T_EOF);
   1198 		}
   1199 
   1200 		next = &arg->next;
   1201 	}
   1202 	return expr;
   1203 }
   1204 
   1205 static struct ast_expression *
   1206 parse_index_slice_expression(struct lexer *lexer, struct ast_expression *lvalue)
   1207 {
   1208 	struct ast_expression *exp = mkexpr(&lexer->loc);
   1209 	struct ast_expression *start = NULL, *end = NULL;
   1210 	struct token tok;
   1211 	want(lexer, T_LBRACKET, &tok);
   1212 
   1213 	bool is_slice = false;
   1214 	switch (lex(lexer, &tok)) {
   1215 	case T_SLICE:
   1216 		is_slice = true;
   1217 		break;
   1218 	default:
   1219 		unlex(lexer, &tok);
   1220 		start = parse_expression(lexer);
   1221 		break;
   1222 	}
   1223 
   1224 	switch (lex(lexer, &tok)) {
   1225 	case T_SLICE:
   1226 		is_slice = true;
   1227 		break;
   1228 	case T_RBRACKET:
   1229 		break;
   1230 	default:
   1231 		if (is_slice) {
   1232 			unlex(lexer, &tok);
   1233 			break;
   1234 		}
   1235 		synerr(&tok, T_SLICE, T_RBRACKET, T_EOF);
   1236 		break;
   1237 	}
   1238 
   1239 	if (!is_slice) {
   1240 		exp->type = EXPR_ACCESS;
   1241 		exp->access.type = ACCESS_INDEX;
   1242 		exp->access.array = lvalue;
   1243 		exp->access.index = start;
   1244 		return exp;
   1245 	} else if (tok.token == T_RBRACKET) {
   1246 		unlex(lexer, &tok);
   1247 	}
   1248 
   1249 	switch (lex(lexer, &tok)) {
   1250 	case T_RBRACKET:
   1251 		break;
   1252 	default:
   1253 		unlex(lexer, &tok);
   1254 		end = parse_expression(lexer);
   1255 		want(lexer, T_RBRACKET, &tok);
   1256 		break;
   1257 	}
   1258 
   1259 	exp->type = EXPR_SLICE;
   1260 	exp->slice.object = lvalue;
   1261 	exp->slice.start = start;
   1262 	exp->slice.end = end;
   1263 	return exp;
   1264 }
   1265 
   1266 static struct ast_expression *
   1267 parse_allocation_expression(struct lexer *lexer)
   1268 {
   1269 	struct ast_expression *exp = NULL;
   1270 	struct token tok = {0};
   1271 	switch (lex(lexer, &tok)) {
   1272 	case T_ALLOC:
   1273 		exp = mkexpr(&tok.loc);
   1274 		exp->type = EXPR_ALLOC;
   1275 		exp->alloc.kind = ALLOC_OBJECT;
   1276 		want(lexer, T_LPAREN, NULL);
   1277 		exp->alloc.init = parse_expression(lexer);
   1278 		switch (lex(lexer, &tok)) {
   1279 		case T_COMMA:
   1280 			// alloc(init, cap)
   1281 			exp->alloc.cap = parse_expression(lexer);
   1282 			exp->alloc.kind = ALLOC_WITH_CAP;
   1283 			want(lexer, T_RPAREN, NULL);
   1284 			break;
   1285 		case T_ELLIPSIS:
   1286 			// alloc(init...)
   1287 			exp->alloc.kind = ALLOC_COPY;
   1288 			want(lexer, T_RPAREN, NULL);
   1289 			break;
   1290 		case T_RPAREN:
   1291 			// alloc(init)
   1292 			break;
   1293 		default:
   1294 			synerr(&tok, T_COMMA, T_RPAREN, T_ELLIPSIS, T_EOF);
   1295 		}
   1296 		break;
   1297 	case T_FREE:
   1298 		exp = mkexpr(&tok.loc);
   1299 		exp->type = EXPR_FREE;
   1300 		want(lexer, T_LPAREN, NULL);
   1301 		exp->free.expr = parse_expression(lexer);
   1302 		want(lexer, T_RPAREN, NULL);
   1303 		break;
   1304 	default:
   1305 		assert(0);
   1306 	}
   1307 	return exp;
   1308 }
   1309 
   1310 static struct ast_expression *
   1311 parse_append_insert(struct lexer *lexer, struct location *loc,
   1312 		bool is_static, enum expr_type etype)
   1313 {
   1314 	struct token tok = {0};
   1315 	struct ast_expression *expr = mkexpr(loc);
   1316 	expr->type = etype;
   1317 
   1318 	want(lexer, T_LPAREN, NULL);
   1319 	expr->append.object = parse_object_selector(lexer);
   1320 	want(lexer, T_COMMA, NULL);
   1321 	expr->append.value = parse_expression(lexer);
   1322 	expr->append.is_static = is_static;
   1323 
   1324 	switch (lex(lexer, &tok)) {
   1325 	case T_ELLIPSIS:
   1326 		expr->append.is_multi = true;
   1327 		break;
   1328 	default:
   1329 		unlex(lexer, &tok);
   1330 		break;
   1331 	}
   1332 
   1333 	if (etype == EXPR_INSERT) {
   1334 		synassert_msg(expr->append.object->access.type == ACCESS_INDEX,
   1335 				"expected indexing expression", &tok);
   1336 		want(lexer, T_RPAREN, NULL);
   1337 		return expr;
   1338 	}
   1339 
   1340 	switch (lex(lexer, &tok)) {
   1341 	case T_RPAREN:
   1342 		// This space deliberately left blank
   1343 		break;
   1344 	case T_COMMA:
   1345 		expr->append.length = parse_expression(lexer);
   1346 		want(lexer, T_RPAREN, NULL);
   1347 		break;
   1348 	default:
   1349 		synerr(&tok, T_RPAREN, T_COMMA, T_EOF);
   1350 	}
   1351 
   1352 	return expr;
   1353 }
   1354 
   1355 static struct ast_expression *
   1356 parse_delete(struct lexer *lexer, struct location *loc, bool is_static)
   1357 {
   1358 	struct ast_expression *exp = mkexpr(loc);
   1359 	exp->type = EXPR_DELETE;
   1360 	want(lexer, T_LPAREN, NULL);
   1361 	exp->delete.expr = parse_expression(lexer);
   1362 	exp->delete.is_static = is_static;
   1363 	want(lexer, T_RPAREN, NULL);
   1364 	return exp;
   1365 }
   1366 
   1367 static struct ast_expression *
   1368 parse_slice_mutation(struct lexer *lexer, bool is_static)
   1369 {
   1370 	struct token tok = {0};
   1371 	switch (lex(lexer, &tok)) {
   1372 	case T_APPEND:
   1373 	case T_INSERT:
   1374 		return parse_append_insert(lexer, &tok.loc, is_static,
   1375 			tok.token == T_APPEND ? EXPR_APPEND : EXPR_INSERT);
   1376 	case T_DELETE:
   1377 		return parse_delete(lexer, &tok.loc, is_static);
   1378 	default:
   1379 		abort(); // Invariant
   1380 	}
   1381 }
   1382 
   1383 static struct ast_expression *
   1384 parse_static_expression(struct lexer *lexer, bool allowbinding)
   1385 {
   1386 	struct token tok = {0};
   1387 	switch (lex(lexer, &tok)) {
   1388 	case T_LET:
   1389 	case T_CONST:
   1390 		synassert(allowbinding, &tok, T_ABORT, T_ASSERT, T_APPEND,
   1391 			T_INSERT, T_DELETE, T_EOF);
   1392 		unlex(lexer, &tok);
   1393 		return parse_binding_list(lexer, true);
   1394 	case T_ABORT:
   1395 	case T_ASSERT:
   1396 		unlex(lexer, &tok);
   1397 		return parse_assertion_expression(lexer, true);
   1398 	case T_APPEND:
   1399 	case T_INSERT:
   1400 	case T_DELETE:
   1401 		unlex(lexer, &tok);
   1402 		return parse_slice_mutation(lexer, true);
   1403 	default:
   1404 		if (allowbinding) {
   1405 			synerr(&tok, T_LET, T_CONST, T_ABORT,
   1406 				T_ASSERT, T_APPEND, T_INSERT, T_DELETE, T_EOF);
   1407 		} else {
   1408 			synerr(&tok, T_ABORT, T_ASSERT, T_APPEND,
   1409 				T_INSERT, T_DELETE, T_EOF);
   1410 		}
   1411 	}
   1412 	assert(0); // Unreachable
   1413 }
   1414 
   1415 static struct ast_expression *
   1416 parse_postfix_expression(struct lexer *lexer, struct ast_expression *lvalue)
   1417 {
   1418 	if (lvalue == NULL) {
   1419 		lvalue = parse_plain_expression(lexer);
   1420 	}
   1421 
   1422 	struct token tok;
   1423 	struct ast_expression *exp;
   1424 	switch (lex(lexer, &tok)) {
   1425 	case T_LPAREN:
   1426 		unlex(lexer, &tok);
   1427 		lvalue = parse_call_expression(lexer, lvalue);
   1428 		break;
   1429 	case T_DOT:
   1430 		exp = mkexpr(&lexer->loc);
   1431 		exp->type = EXPR_ACCESS;
   1432 
   1433 		switch (lex(lexer, &tok)) {
   1434 		case T_NAME:
   1435 			exp->access.type = ACCESS_FIELD;
   1436 			exp->access._struct = lvalue;
   1437 			exp->access.field = tok.name;
   1438 			break;
   1439 		case T_LITERAL:
   1440 			exp->access.type = ACCESS_TUPLE;
   1441 			exp->access.tuple = lvalue;
   1442 			unlex(lexer, &tok);
   1443 			exp->access.value = parse_constant(lexer);
   1444 			break;
   1445 		default:
   1446 			synerr(&tok, T_NAME, T_LITERAL, T_EOF);
   1447 		}
   1448 
   1449 		lvalue = exp;
   1450 		break;
   1451 	case T_LBRACKET:
   1452 		unlex(lexer, &tok);
   1453 		lvalue = parse_index_slice_expression(lexer, lvalue);
   1454 		break;
   1455 	case T_QUESTION:
   1456 	case T_LNOT:
   1457 		exp = mkexpr(&lexer->loc);
   1458 		exp->type = EXPR_PROPAGATE;
   1459 		exp->propagate.value = lvalue;
   1460 		exp->propagate.abort = tok.token == T_LNOT;
   1461 		lvalue = exp;
   1462 		break;
   1463 	default:
   1464 		unlex(lexer, &tok);
   1465 		return lvalue;
   1466 	}
   1467 
   1468 	return parse_postfix_expression(lexer, lvalue);
   1469 }
   1470 
   1471 static enum unarithm_operator
   1472 unop_for_token(enum lexical_token tok)
   1473 {
   1474 	switch (tok) {
   1475 	case T_PLUS:	// +
   1476 		return UN_PLUS;
   1477 	case T_MINUS:	// -
   1478 		return UN_MINUS;
   1479 	case T_BNOT:	// ~
   1480 		return UN_BNOT;
   1481 	case T_LNOT:	// !
   1482 		return UN_LNOT;
   1483 	case T_TIMES:	// *
   1484 		return UN_DEREF;
   1485 	case T_BAND:	// &
   1486 		return UN_ADDRESS;
   1487 	default:
   1488 		assert(0); // Invariant
   1489 	}
   1490 	assert(0); // Unreachable
   1491 }
   1492 
   1493 static struct ast_expression *
   1494 parse_object_selector(struct lexer *lexer)
   1495 {
   1496 	struct token tok;
   1497 	lex(lexer, &tok);
   1498 	unlex(lexer, &tok);
   1499 	struct ast_expression *exp = parse_postfix_expression(lexer, NULL);
   1500 	synassert_msg(exp->type == EXPR_ACCESS, "expected object", &tok);
   1501 	return exp;
   1502 }
   1503 
   1504 static struct ast_expression *
   1505 parse_va_expression(struct lexer *lexer)
   1506 {
   1507 	struct ast_expression *expr;
   1508 	struct token tok;
   1509 	switch (lex(lexer, &tok)) {
   1510 	case T_VASTART:
   1511 		expr = mkexpr(&lexer->loc);
   1512 		expr->type = EXPR_VASTART;
   1513 		want(lexer, T_LPAREN, NULL);
   1514 		want(lexer, T_RPAREN, NULL);
   1515 		return expr;
   1516 	case T_VAARG:
   1517 		expr = mkexpr(&lexer->loc);
   1518 		expr->type = EXPR_VAARG;
   1519 		want(lexer, T_LPAREN, NULL);
   1520 		expr->vaarg.ap = parse_object_selector(lexer);
   1521 		want(lexer, T_RPAREN, NULL);
   1522 		return expr;
   1523 	case T_VAEND:
   1524 		expr = mkexpr(&lexer->loc);
   1525 		expr->type = EXPR_VAEND;
   1526 		want(lexer, T_LPAREN, NULL);
   1527 		expr->vaarg.ap = parse_object_selector(lexer);
   1528 		want(lexer, T_RPAREN, NULL);
   1529 		return expr;
   1530 	default:
   1531 		assert(0);
   1532 	}
   1533 }
   1534 
   1535 static struct ast_expression *
   1536 parse_builtin_expression(struct lexer *lexer)
   1537 {
   1538 	struct token tok;
   1539 	switch (lex(lexer, &tok)) {
   1540 	case T_ALLOC:
   1541 	case T_FREE:
   1542 		unlex(lexer, &tok);
   1543 		return parse_allocation_expression(lexer);
   1544 	case T_APPEND:
   1545 	case T_DELETE:
   1546 	case T_INSERT:
   1547 		unlex(lexer, &tok);
   1548 		return parse_slice_mutation(lexer, false);
   1549 	case T_STATIC:
   1550 		return parse_static_expression(lexer, false);
   1551 	case T_ABORT:
   1552 	case T_ASSERT:
   1553 		unlex(lexer, &tok);
   1554 		return parse_assertion_expression(lexer, false);
   1555 	case T_SIZE:
   1556 	case T_LEN:
   1557 	case T_OFFSET:
   1558 		unlex(lexer, &tok);
   1559 		return parse_measurement_expression(lexer);
   1560 	case T_VAARG:
   1561 	case T_VAEND:
   1562 	case T_VASTART:
   1563 		unlex(lexer, &tok);
   1564 		return parse_va_expression(lexer);
   1565 	default:
   1566 		unlex(lexer, &tok);
   1567 		break;
   1568 	}
   1569 	return parse_postfix_expression(lexer, NULL);
   1570 }
   1571 
   1572 static struct ast_expression *
   1573 parse_unary_expression(struct lexer *lexer)
   1574 {
   1575 	struct token tok;
   1576 	struct ast_expression *exp;
   1577 	switch (lex(lexer, &tok)) {
   1578 	case T_PLUS:	// +
   1579 	case T_MINUS:	// -
   1580 	case T_BNOT:	// ~
   1581 	case T_LNOT:	// !
   1582 	case T_TIMES:	// *
   1583 	case T_BAND:	// &
   1584 		exp = mkexpr(&lexer->loc);
   1585 		exp->type = EXPR_UNARITHM;
   1586 		exp->unarithm.op = unop_for_token(tok.token);
   1587 		exp->unarithm.operand = parse_unary_expression(lexer);
   1588 		return exp;
   1589 	default:
   1590 		unlex(lexer, &tok);
   1591 		return parse_builtin_expression(lexer);
   1592 	}
   1593 }
   1594 
   1595 static struct ast_expression *
   1596 parse_cast_expression(struct lexer *lexer, struct ast_expression *value)
   1597 {
   1598 	if (value == NULL) {
   1599 		value = parse_unary_expression(lexer);
   1600 	}
   1601 	enum cast_kind kind;
   1602 	struct token tok;
   1603 	switch (lex(lexer, &tok)) {
   1604 	case T_COLON:
   1605 		kind = C_CAST;
   1606 		break;
   1607 	case T_AS:
   1608 		kind = C_ASSERTION;
   1609 		break;
   1610 	case T_IS:
   1611 		kind = C_TEST;
   1612 		break;
   1613 	default:
   1614 		unlex(lexer, &tok);
   1615 		return value;
   1616 	}
   1617 
   1618 	struct ast_expression *exp = mkexpr(&lexer->loc);
   1619 	exp->type = EXPR_CAST;
   1620 	exp->cast.kind = kind;
   1621 	exp->cast.value = value;
   1622 	if (lex(lexer, &tok) == T_NULL) {
   1623 		exp->cast.type = mktype(&tok.loc);
   1624 		exp->cast.type->storage = STORAGE_NULL;
   1625 	} else {
   1626 		unlex(lexer, &tok);
   1627 		exp->cast.type = parse_type(lexer);
   1628 	}
   1629 	return parse_cast_expression(lexer, exp);
   1630 }
   1631 
   1632 static int
   1633 precedence(enum lexical_token token)
   1634 {
   1635 	switch (token) {
   1636 	case T_LOR:
   1637 		return 0;
   1638 	case T_LXOR:
   1639 		return 1;
   1640 	case T_LAND:
   1641 		return 2;
   1642 	case T_LEQUAL:
   1643 	case T_NEQUAL:
   1644 		return 3;
   1645 	case T_LESS:
   1646 	case T_LESSEQ:
   1647 	case T_GREATER:
   1648 	case T_GREATEREQ:
   1649 		return 4;
   1650 	case T_BOR:
   1651 		return 5;
   1652 	case T_BXOR:
   1653 		return 6;
   1654 	case T_BAND:
   1655 		return 7;
   1656 	case T_LSHIFT:
   1657 	case T_RSHIFT:
   1658 		return 8;
   1659 	case T_PLUS:
   1660 	case T_MINUS:
   1661 		return 9;
   1662 	case T_TIMES:
   1663 	case T_DIV:
   1664 	case T_MODULO:
   1665 		return 10;
   1666 	default:
   1667 		return -1;
   1668 	}
   1669 	assert(0); // Unreachable
   1670 }
   1671 
   1672 static enum binarithm_operator
   1673 binop_for_token(enum lexical_token tok)
   1674 {
   1675 	switch (tok) {
   1676 	case T_LOR:
   1677 		return BIN_LOR;
   1678 	case T_LAND:
   1679 		return BIN_LAND;
   1680 	case T_LXOR:
   1681 		return BIN_LXOR;
   1682 	case T_BOR:
   1683 		return BIN_BOR;
   1684 	case T_BXOR:
   1685 		return BIN_BXOR;
   1686 	case T_BAND:
   1687 		return BIN_BAND;
   1688 	case T_LEQUAL:
   1689 		return BIN_LEQUAL;
   1690 	case T_NEQUAL:
   1691 		return BIN_NEQUAL;
   1692 	case T_LESS:
   1693 		return BIN_LESS;
   1694 	case T_LESSEQ:
   1695 		return BIN_LESSEQ;
   1696 	case T_GREATER:
   1697 		return BIN_GREATER;
   1698 	case T_GREATEREQ:
   1699 		return BIN_GREATEREQ;
   1700 	case T_LSHIFT:
   1701 		return BIN_LSHIFT;
   1702 	case T_RSHIFT:
   1703 		return BIN_RSHIFT;
   1704 	case T_PLUS:
   1705 		return BIN_PLUS;
   1706 	case T_MINUS:
   1707 		return BIN_MINUS;
   1708 	case T_TIMES:
   1709 		return BIN_TIMES;
   1710 	case T_DIV:
   1711 		return BIN_DIV;
   1712 	case T_MODULO:
   1713 		return BIN_MODULO;
   1714 	default:
   1715 		assert(0); // Invariant
   1716 	}
   1717 	assert(0); // Unreachable
   1718 }
   1719 
   1720 static struct ast_expression *
   1721 parse_bin_expression(struct lexer *lexer, struct ast_expression *lvalue, int i)
   1722 {
   1723 	if (!lvalue) {
   1724 		lvalue = parse_cast_expression(lexer, NULL);
   1725 	}
   1726 
   1727 	struct token tok;
   1728 	lex(lexer, &tok);
   1729 
   1730 	int j;
   1731 	while ((j = precedence(tok.token)) >= i) {
   1732 		enum binarithm_operator op = binop_for_token(tok.token);
   1733 
   1734 		struct ast_expression *rvalue =
   1735 			parse_cast_expression(lexer, NULL);
   1736 		lex(lexer, &tok);
   1737 
   1738 		int k;
   1739 		while ((k = precedence(tok.token)) > j) {
   1740 			unlex(lexer, &tok);
   1741 			rvalue = parse_bin_expression(lexer, rvalue, k);
   1742 			lex(lexer, &tok);
   1743 		}
   1744 
   1745 		struct ast_expression *e = mkexpr(&lexer->loc);
   1746 		e->type = EXPR_BINARITHM;
   1747 		e->binarithm.op = op;
   1748 		e->binarithm.lvalue = lvalue;
   1749 		e->binarithm.rvalue = rvalue;
   1750 		lvalue = e;
   1751 	}
   1752 
   1753 	unlex(lexer, &tok);
   1754 	return lvalue;
   1755 }
   1756 
   1757 static struct ast_expression *
   1758 parse_if_expression(struct lexer *lexer)
   1759 {
   1760 	struct ast_expression *exp = mkexpr(&lexer->loc);
   1761 	exp->type = EXPR_IF;
   1762 
   1763 	struct token tok = {0};
   1764 
   1765 	want(lexer, T_LPAREN, &tok);
   1766 	exp->_if.cond = parse_expression(lexer);
   1767 	want(lexer, T_RPAREN, &tok);
   1768 
   1769 	exp->_if.true_branch = parse_expression(lexer);
   1770 
   1771 	switch (lex(lexer, &tok)) {
   1772 	case T_ELSE:
   1773 		if (lex(lexer, &tok) == T_IF) {
   1774 			exp->_if.false_branch = parse_if_expression(lexer);
   1775 		} else {
   1776 			unlex(lexer, &tok);
   1777 			exp->_if.false_branch = parse_expression(lexer);
   1778 		}
   1779 		break;
   1780 	default:
   1781 		unlex(lexer, &tok);
   1782 		break;
   1783 	}
   1784 	return exp;
   1785 }
   1786 
   1787 static struct ast_expression *
   1788 parse_for_expression(struct lexer *lexer)
   1789 {
   1790 	struct ast_expression *exp = mkexpr(&lexer->loc);
   1791 	exp->type = EXPR_FOR;
   1792 
   1793 	struct token tok = {0};
   1794 	want(lexer, T_FOR, &tok);
   1795 	want(lexer, T_LPAREN, &tok);
   1796 	switch (lex(lexer, &tok)) {
   1797 	case T_LET:
   1798 	case T_CONST:
   1799 		unlex(lexer, &tok);
   1800 		exp->_for.bindings = parse_binding_list(lexer, false);
   1801 		want(lexer, T_SEMICOLON, &tok);
   1802 		exp->_for.cond = parse_expression(lexer);
   1803 		break;
   1804 	case T_STATIC:
   1805 		switch (lex(lexer, &tok)) {
   1806 		case T_LET:
   1807 		case T_CONST:
   1808 			unlex(lexer, &tok);
   1809 			exp->_for.bindings = parse_binding_list(lexer, true);
   1810 			want(lexer, T_SEMICOLON, &tok);
   1811 			exp->_for.cond = parse_expression(lexer);
   1812 			break;
   1813 		default:
   1814 			unlex(lexer, &tok);
   1815 			exp->_for.cond = parse_static_expression(lexer, false);
   1816 			break;
   1817 		}
   1818 		break;
   1819 	default:
   1820 		unlex(lexer, &tok);
   1821 		exp->_for.cond = parse_expression(lexer);
   1822 		break;
   1823 	}
   1824 
   1825 	switch (lex(lexer, &tok)) {
   1826 	case T_SEMICOLON:
   1827 		exp->_for.afterthought = parse_expression(lexer);
   1828 		want(lexer, T_RPAREN, &tok);
   1829 		break;
   1830 	case T_RPAREN:
   1831 		break;
   1832 	default:
   1833 		synerr(&tok, T_SEMICOLON, T_RPAREN, T_EOF);
   1834 	}
   1835 
   1836 	exp->_for.body = parse_expression(lexer);
   1837 	return exp;
   1838 }
   1839 
   1840 static struct ast_case_option *
   1841 parse_case_options(struct lexer *lexer)
   1842 {
   1843 	struct token tok = {0};
   1844 	switch (lex(lexer, &tok)) {
   1845 	case T_ARROW:
   1846 		return NULL; // Default case
   1847 	default:
   1848 		unlex(lexer, &tok);
   1849 		break;
   1850 	}
   1851 
   1852 	bool more = true;
   1853 	struct ast_case_option *opt = xcalloc(1, sizeof(struct ast_case_option));
   1854 	struct ast_case_option *opts = opt;
   1855 	struct ast_case_option **next = &opt->next;
   1856 	while (more) {
   1857 		opt->value = parse_expression(lexer);
   1858 		switch (lex(lexer, &tok)) {
   1859 		case T_COMMA:
   1860 			switch (lex(lexer, &tok)) {
   1861 			case T_ARROW:
   1862 				more = false;
   1863 				break;
   1864 			default:
   1865 				unlex(lexer, &tok);
   1866 				opt = xcalloc(1, sizeof(struct ast_case_option));
   1867 				*next = opt;
   1868 				next = &opt->next;
   1869 				break;
   1870 			}
   1871 			break;
   1872 		case T_ARROW:
   1873 			more = false;
   1874 			break;
   1875 		default:
   1876 			synerr(&tok, T_COMMA, T_ARROW, T_EOF);
   1877 			break;
   1878 		}
   1879 	}
   1880 
   1881 	return opts;
   1882 }
   1883 
   1884 static struct ast_expression *
   1885 parse_switch_expression(struct lexer *lexer)
   1886 {
   1887 	struct ast_expression *exp = mkexpr(&lexer->loc);
   1888 	exp->type = EXPR_SWITCH;
   1889 
   1890 	struct token tok = {0};
   1891 	want(lexer, T_LPAREN, &tok);
   1892 	exp->_switch.value = parse_expression(lexer);
   1893 	want(lexer, T_RPAREN, &tok);
   1894 	want(lexer, T_LBRACE, &tok);
   1895 
   1896 	bool more = true;
   1897 	struct ast_switch_case **next_case = &exp->_switch.cases;
   1898 	while (more) {
   1899 		struct ast_switch_case *_case =
   1900 			*next_case = xcalloc(1, sizeof(struct ast_switch_case));
   1901 		want(lexer, T_CASE, &tok);
   1902 		_case->options = parse_case_options(lexer);
   1903 
   1904 		bool exprs = true;
   1905 		struct ast_expression_list *cur = &_case->exprs;
   1906 		struct ast_expression_list **next = &cur->next;
   1907 		while (exprs) {
   1908 			cur->expr = parse_expression(lexer);
   1909 			want(lexer, T_SEMICOLON, &tok);
   1910 
   1911 			switch (lex(lexer, &tok)) {
   1912 			case T_CASE:
   1913 			case T_RBRACE:
   1914 				exprs = false;
   1915 				break;
   1916 			default:
   1917 				break;
   1918 			}
   1919 			unlex(lexer, &tok);
   1920 
   1921 			if (exprs) {
   1922 				*next = xcalloc(1, sizeof(struct ast_expression_list));
   1923 				cur = *next;
   1924 				next = &cur->next;
   1925 			}
   1926 		}
   1927 
   1928 		switch (lex(lexer, &tok)) {
   1929 		case T_CASE:
   1930 			unlex(lexer, &tok);
   1931 			break;
   1932 		case T_RBRACE:
   1933 			more = false;
   1934 			break;
   1935 		default:
   1936 			synerr(&tok, T_CASE, T_RBRACE, T_EOF);
   1937 		}
   1938 
   1939 		next_case = &_case->next;
   1940 	}
   1941 
   1942 	return exp;
   1943 }
   1944 
   1945 static struct ast_expression *
   1946 parse_match_expression(struct lexer *lexer)
   1947 {
   1948 	struct ast_expression *exp = mkexpr(&lexer->loc);
   1949 	exp->type = EXPR_MATCH;
   1950 
   1951 	struct token tok = {0};
   1952 	want(lexer, T_LPAREN, &tok);
   1953 	exp->match.value = parse_expression(lexer);
   1954 	want(lexer, T_RPAREN, &tok);
   1955 	want(lexer, T_LBRACE, &tok);
   1956 
   1957 	bool more = true;
   1958 	struct ast_match_case **next_case = &exp->match.cases;
   1959 	while (more) {
   1960 		struct ast_match_case *_case =
   1961 			*next_case = xcalloc(1, sizeof(struct ast_match_case));
   1962 		want(lexer, T_CASE, &tok);
   1963 
   1964 		struct ast_type *type = NULL;
   1965 		switch (lex(lexer, &tok)) {
   1966 		case T_LET:
   1967 			want(lexer, T_NAME, &tok);
   1968 			_case->name = tok.name;
   1969 			want(lexer, T_COLON, NULL);
   1970 			_case->type = parse_type(lexer);
   1971 			break;
   1972 		case T_ARROW:
   1973 			// Default case
   1974 			unlex(lexer, &tok);
   1975 			break;
   1976 		case T_NULL:
   1977 			type = mktype(&tok.loc);
   1978 			type->storage = STORAGE_NULL;
   1979 			_case->type = type;
   1980 			break;
   1981 		default:
   1982 			unlex(lexer, &tok);
   1983 			_case->type = parse_type(lexer);
   1984 			break;
   1985 		}
   1986 
   1987 		want(lexer, T_ARROW, &tok);
   1988 
   1989 		bool exprs = true;
   1990 		struct ast_expression_list *cur = &_case->exprs;
   1991 		struct ast_expression_list **next = &cur->next;
   1992 		while (exprs) {
   1993 			cur->expr = parse_expression(lexer);
   1994 			want(lexer, T_SEMICOLON, &tok);
   1995 
   1996 			switch (lex(lexer, &tok)) {
   1997 			case T_CASE:
   1998 			case T_RBRACE:
   1999 				exprs = false;
   2000 				break;
   2001 			default:
   2002 				break;
   2003 			}
   2004 			unlex(lexer, &tok);
   2005 
   2006 			if (exprs) {
   2007 				*next = xcalloc(1, sizeof(struct ast_expression_list));
   2008 				cur = *next;
   2009 				next = &cur->next;
   2010 			}
   2011 		}
   2012 
   2013 		switch (lex(lexer, &tok)) {
   2014 		case T_CASE:
   2015 			unlex(lexer, &tok);
   2016 			break;
   2017 		case T_RBRACE:
   2018 			more = false;
   2019 			break;
   2020 		default:
   2021 			synerr(&tok, T_CASE, T_RBRACE, T_EOF);
   2022 		}
   2023 
   2024 		next_case = &_case->next;
   2025 	}
   2026 	return exp;
   2027 }
   2028 
   2029 static void
   2030 parse_binding_unpack(struct lexer *lexer, struct ast_binding_unpack **next)
   2031 {
   2032 	struct token tok = {0};
   2033 
   2034 	bool more = true;
   2035 	while (more) {
   2036 		char *name = NULL;
   2037 		switch (lex(lexer, &tok)) {
   2038 		case T_NAME:
   2039 			name = tok.name;
   2040 			break;
   2041 		case T_UNDERSCORE:
   2042 			break;
   2043 		default:
   2044 			synerr(&tok, T_NAME, T_UNDERSCORE, T_EOF);
   2045 		}
   2046 
   2047 		struct ast_binding_unpack *new = xcalloc(1, sizeof *new);
   2048 		*next = new;
   2049 		next = &new->next;
   2050 
   2051 		new->name = name;
   2052 
   2053 		switch (lex(lexer, &tok)) {
   2054 		case T_COMMA:
   2055 			break;
   2056 		case T_RPAREN:
   2057 			more = false;
   2058 			break;
   2059 		default:
   2060 			synerr(&tok, T_COMMA, T_RPAREN, T_EOF);
   2061 		}
   2062 	}
   2063 }
   2064 
   2065 static struct ast_expression *
   2066 parse_binding_list(struct lexer *lexer, bool is_static)
   2067 {
   2068 	struct ast_expression *exp = mkexpr(&lexer->loc);
   2069 	exp->type = EXPR_BINDING;
   2070 	unsigned int flags = 0;
   2071 
   2072 	struct token tok = {0};
   2073 	switch (lex(lexer, &tok)) {
   2074 	case T_CONST:
   2075 		flags = TYPE_CONST;
   2076 		// fallthrough
   2077 	case T_LET:
   2078 		// no-op
   2079 		break;
   2080 	default:
   2081 		synerr(&tok, T_LET, T_CONST, T_EOF);
   2082 	}
   2083 
   2084 	struct ast_expression_binding *binding = &exp->binding;
   2085 	struct ast_expression_binding **next = &exp->binding.next;
   2086 
   2087 	bool more = true;
   2088 	while (more) {
   2089 		switch (lex(lexer, &tok)) {
   2090 		case T_NAME:
   2091 			binding->name = tok.name;
   2092 			break;
   2093 		case T_LPAREN:
   2094 			parse_binding_unpack(lexer, &binding->unpack);
   2095 			break;
   2096 		default:
   2097 			synerr(&tok, T_NAME, T_LPAREN, T_EOF);
   2098 		}
   2099 		binding->initializer = mkexpr(&lexer->loc);
   2100 		binding->flags = flags;
   2101 		binding->is_static = is_static;
   2102 
   2103 		switch (lex(lexer, &tok)) {
   2104 		case T_COLON:
   2105 			binding->type = parse_type(lexer);
   2106 			binding->type->flags |= flags;
   2107 			want(lexer, T_EQUAL, &tok);
   2108 			binding->initializer = parse_expression(lexer);
   2109 			break;
   2110 		case T_EQUAL:
   2111 			binding->initializer = parse_expression(lexer);
   2112 			break;
   2113 		default:
   2114 			synerr(&tok, T_COLON, T_EQUAL, T_EOF);
   2115 		}
   2116 
   2117 		switch (lex(lexer, &tok)) {
   2118 		case T_COMMA:
   2119 			*next = xcalloc(1, sizeof(struct ast_expression_binding));
   2120 			binding = *next;
   2121 			next = &binding->next;
   2122 			break;
   2123 		default:
   2124 			unlex(lexer, &tok);
   2125 			more = false;
   2126 			break;
   2127 		}
   2128 	}
   2129 	return exp;
   2130 }
   2131 
   2132 static struct ast_expression *
   2133 parse_assignment(struct lexer *lexer, struct ast_expression *object,
   2134 	bool indirect, enum binarithm_operator op)
   2135 {
   2136 	struct ast_expression *value = parse_expression(lexer);
   2137 	struct ast_expression *expr = mkexpr(&lexer->loc);
   2138 	expr->type = EXPR_ASSIGN;
   2139 	expr->assign.op = op;
   2140 	expr->assign.object = object;
   2141 	expr->assign.value = value;
   2142 	expr->assign.indirect = indirect;
   2143 	return expr;
   2144 }
   2145 
   2146 static struct ast_expression *
   2147 parse_deferred_expression(struct lexer *lexer)
   2148 {
   2149 	struct ast_expression *exp = mkexpr(&lexer->loc);
   2150 	exp->type = EXPR_DEFER;
   2151 	exp->defer.deferred = parse_expression(lexer);
   2152 	return exp;
   2153 }
   2154 
   2155 static struct ast_expression *
   2156 parse_control_expression(struct lexer *lexer)
   2157 {
   2158 	struct ast_expression *exp = mkexpr(&lexer->loc);
   2159 
   2160 	struct token tok;
   2161 	switch (lex(lexer, &tok)) {
   2162 	case T_BREAK:
   2163 	case T_CONTINUE:
   2164 		exp->type = tok.token == T_BREAK ? EXPR_BREAK : EXPR_CONTINUE;
   2165 		exp->control.label = NULL;
   2166 		switch (lex(lexer, &tok)) {
   2167 		case T_COLON:
   2168 			want(lexer, T_NAME, &tok);
   2169 			exp->control.label = tok.name;
   2170 			break;
   2171 		default:
   2172 			unlex(lexer, &tok);
   2173 			break;
   2174 		}
   2175 		break;
   2176 	case T_RETURN:
   2177 		exp->type = EXPR_RETURN;
   2178 		exp->_return.value = NULL;
   2179 		switch (lex(lexer, &tok)) {
   2180 		case T_SEMICOLON:
   2181 		case T_COMMA:
   2182 			unlex(lexer, &tok);
   2183 			break;
   2184 		default:
   2185 			unlex(lexer, &tok);
   2186 			exp->_return.value = parse_expression(lexer);
   2187 			break;
   2188 		}
   2189 		break;
   2190 	case T_YIELD:
   2191 		exp->type = EXPR_YIELD;
   2192 		exp->control.value = NULL;
   2193 		switch (lex(lexer, &tok)) {
   2194 		case T_SEMICOLON:
   2195 			unlex(lexer, &tok);
   2196 			break;
   2197 		case T_COLON:
   2198 			want(lexer, T_NAME, &tok);
   2199 			exp->control.label = tok.name;
   2200 			switch (lex(lexer, &tok)) {
   2201 			case T_COMMA:
   2202 				exp->control.value = parse_expression(lexer);
   2203 				break;
   2204 			default:
   2205 				unlex(lexer, &tok);
   2206 				break;
   2207 			}
   2208 			break;
   2209 		default:
   2210 			unlex(lexer, &tok);
   2211 			exp->control.value = parse_expression(lexer);
   2212 			break;
   2213 		}
   2214 		break;
   2215 	default:
   2216 		synerr(&tok,
   2217 			T_BREAK, T_CONTINUE, T_RETURN, T_YIELD, T_EOF);
   2218 	}
   2219 	return exp;
   2220 }
   2221 
   2222 static struct ast_expression *
   2223 parse_compound_expression(struct lexer *lexer)
   2224 {
   2225 	struct ast_expression *exp = mkexpr(&lexer->loc);
   2226 	exp->type = EXPR_COMPOUND;
   2227 
   2228 	struct ast_expression_list *cur = &exp->compound.list;
   2229 	struct ast_expression_list **next = &cur->next;
   2230 
   2231 	struct token tok = {0};
   2232 	switch (lex(lexer, &tok)) {
   2233 	case T_COLON:
   2234 		want(lexer, T_NAME, &tok);
   2235 		exp->compound.label = tok.name;
   2236 		want(lexer, T_LBRACE, &tok);
   2237 		break;
   2238 	case T_LBRACE:
   2239 		break; // no-op
   2240 	default:
   2241 		synerr(&tok, T_LBRACE, T_COLON, T_EOF);
   2242 		break;
   2243 	};
   2244 
   2245 	bool more = true;
   2246 	while (more) {
   2247 		cur->expr = parse_expression(lexer);
   2248 
   2249 		want(lexer, T_SEMICOLON, &tok);
   2250 
   2251 		if (more) {
   2252 			lex(lexer, &tok);
   2253 			if (tok.token == T_RBRACE) {
   2254 				more = false;
   2255 			} else {
   2256 				unlex(lexer, &tok);
   2257 				*next = xcalloc(1, sizeof(struct ast_expression_list));
   2258 				cur = *next;
   2259 				next = &cur->next;
   2260 			}
   2261 		} else {
   2262 			want(lexer, T_RBRACE, &tok);
   2263 		}
   2264 	}
   2265 	return exp;
   2266 }
   2267 
   2268 struct ast_expression *
   2269 parse_expression(struct lexer *lexer)
   2270 {
   2271 	// This is one of the more complicated non-terminals to parse.
   2272 	struct token tok;
   2273 	bool indirect = false;
   2274 	switch (lex(lexer, &tok)) {
   2275 	case T_TIMES: // *ptr = value (or unary-expression)
   2276 		indirect = true;
   2277 		break;
   2278 	default:
   2279 		unlex(lexer, &tok);
   2280 		break;
   2281 	}
   2282 
   2283 	struct ast_expression *value;
   2284 	switch (lex(lexer, &tok)) {
   2285 	case T_LET:
   2286 	case T_CONST:
   2287 		unlex(lexer, &tok);
   2288 		return parse_binding_list(lexer, false);
   2289 	case T_STATIC:
   2290 		return parse_static_expression(lexer, true);
   2291 	case T_BREAK:
   2292 	case T_CONTINUE:
   2293 	case T_RETURN:
   2294 	case T_YIELD:
   2295 	case T_DEFER:
   2296 	case T_FOR:
   2297 	case T_IF:
   2298 	case T_LBRACE:
   2299 	case T_MATCH:
   2300 	case T_SWITCH:
   2301 	case T_COLON:
   2302 		switch (tok.token) {
   2303 		case T_BREAK:
   2304 		case T_CONTINUE:
   2305 		case T_RETURN:
   2306 		case T_YIELD:
   2307 			unlex(lexer, &tok);
   2308 			value = parse_control_expression(lexer);
   2309 			break;
   2310 		case T_DEFER:
   2311 			value = parse_deferred_expression(lexer);
   2312 			break;
   2313 		case T_FOR:
   2314 			unlex(lexer, &tok);
   2315 			value = parse_for_expression(lexer);
   2316 			break;
   2317 		case T_IF:
   2318 			value = parse_if_expression(lexer);
   2319 			break;
   2320 		case T_LBRACE:
   2321 		case T_COLON:
   2322 			unlex(lexer, &tok);
   2323 			value = parse_compound_expression(lexer);
   2324 			value = parse_cast_expression(lexer, value);
   2325 			value = parse_bin_expression(lexer, value, 0);
   2326 			break;
   2327 		case T_MATCH:
   2328 			value = parse_match_expression(lexer);
   2329 			value = parse_cast_expression(lexer, value);
   2330 			value = parse_bin_expression(lexer, value, 0);
   2331 			break;
   2332 		case T_SWITCH:
   2333 			value = parse_switch_expression(lexer);
   2334 			value = parse_cast_expression(lexer, value);
   2335 			value = parse_bin_expression(lexer, value, 0);
   2336 			break;
   2337 		default:
   2338 			assert(0);
   2339 		}
   2340 		if (indirect) {
   2341 			struct ast_expression *deref = mkexpr(&value->loc);
   2342 			deref->type = EXPR_UNARITHM;
   2343 			deref->unarithm.op = UN_DEREF;
   2344 			deref->unarithm.operand = value;
   2345 			return deref;
   2346 		}
   2347 		return value;
   2348 	default:
   2349 		unlex(lexer, &tok);
   2350 		value = parse_unary_expression(lexer);
   2351 		if (!indirect && value->type != EXPR_ACCESS
   2352 				&& value->type != EXPR_SLICE) {
   2353 			value = parse_cast_expression(lexer, value);
   2354 			return parse_bin_expression(lexer, value, 0);
   2355 		}
   2356 		// Is possible object-selector, try for assignment
   2357 		break;
   2358 	}
   2359 
   2360 	switch (lex(lexer, &tok)) {
   2361 	case T_EQUAL:
   2362 		return parse_assignment(lexer, value, indirect, BIN_LEQUAL);
   2363 	case T_BANDEQ:
   2364 		return parse_assignment(lexer, value, indirect, BIN_BAND);
   2365 	case T_LANDEQ:
   2366 		return parse_assignment(lexer, value, indirect, BIN_LAND);
   2367 	case T_DIVEQ:
   2368 		return parse_assignment(lexer, value, indirect, BIN_DIV);
   2369 	case T_LSHIFTEQ:
   2370 		return parse_assignment(lexer, value, indirect, BIN_LSHIFT);
   2371 	case T_MINUSEQ:
   2372 		return parse_assignment(lexer, value, indirect, BIN_MINUS);
   2373 	case T_MODEQ:
   2374 		return parse_assignment(lexer, value, indirect, BIN_MODULO);
   2375 	case T_BOREQ:
   2376 		return parse_assignment(lexer, value, indirect, BIN_BOR);
   2377 	case T_LOREQ:
   2378 		return parse_assignment(lexer, value, indirect, BIN_LOR);
   2379 	case T_PLUSEQ:
   2380 		return parse_assignment(lexer, value, indirect, BIN_PLUS);
   2381 	case T_RSHIFTEQ:
   2382 		return parse_assignment(lexer, value, indirect, BIN_RSHIFT);
   2383 	case T_TIMESEQ:
   2384 		return parse_assignment(lexer, value, indirect, BIN_TIMES);
   2385 	case T_BXOREQ:
   2386 		return parse_assignment(lexer, value, indirect, BIN_BXOR);
   2387 	case T_LXOREQ:
   2388 		return parse_assignment(lexer, value, indirect, BIN_LXOR);
   2389 	default:
   2390 		unlex(lexer, &tok);
   2391 		if (indirect) {
   2392 			struct ast_expression *deref = mkexpr(&value->loc);
   2393 			deref->type = EXPR_UNARITHM;
   2394 			deref->unarithm.op = UN_DEREF;
   2395 			deref->unarithm.operand = value;
   2396 			value = deref;
   2397 		}
   2398 		value = parse_cast_expression(lexer, value);
   2399 		value = parse_bin_expression(lexer, value, 0);
   2400 		return value;
   2401 	}
   2402 }
   2403 
   2404 static char *
   2405 parse_attr_symbol(struct lexer *lexer)
   2406 {
   2407 	struct token tok = {0};
   2408 	want(lexer, T_LPAREN, NULL);
   2409 	want(lexer, T_LITERAL, &tok);
   2410 	synassert_msg(tok.storage == STORAGE_STRING,
   2411 		"expected string literal", &tok);
   2412 	for (size_t i = 0; i < tok.string.len; i++) {
   2413 		uint32_t c = tok.string.value[i];
   2414 		synassert_msg(c <= 0x7F && (isalnum(c) || c == '_' || c == '$'
   2415 			|| c == '.'), "invalid symbol", &tok);
   2416 		synassert_msg(i != 0 || (!isdigit(c) && c != '$'),
   2417 			"invalid symbol", &tok);
   2418 	}
   2419 	want(lexer, T_RPAREN, NULL);
   2420 	return tok.string.value;
   2421 }
   2422 
   2423 static void
   2424 parse_global_decl(struct lexer *lexer, enum lexical_token mode,
   2425 		struct ast_global_decl *decl)
   2426 {
   2427 	struct token tok = {0};
   2428 	struct ast_global_decl *i = decl;
   2429 	assert(mode == T_LET || mode == T_CONST || mode == T_DEF);
   2430 	bool more = true;
   2431 	while (more) {
   2432 		if (mode == T_LET || mode == T_CONST) {
   2433 			switch (lex(lexer, &tok)) {
   2434 			case T_ATTR_SYMBOL:
   2435 				i->symbol = parse_attr_symbol(lexer);
   2436 				break;
   2437 			default:
   2438 				unlex(lexer, &tok);
   2439 				break;
   2440 			}
   2441 		}
   2442 		parse_identifier(lexer, &i->ident, false);
   2443 		want(lexer, T_COLON, NULL);
   2444 		i->type = parse_type(lexer);
   2445 		if (mode == T_CONST) {
   2446 			i->type->flags |= TYPE_CONST;
   2447 		}
   2448 
   2449 		if (mode == T_DEF) {
   2450 			want(lexer, T_EQUAL, NULL);
   2451 			i->init = parse_expression(lexer);
   2452 		} else if (lex(lexer, &tok) == T_EQUAL) {
   2453 			i->init = parse_expression(lexer);
   2454 		} else {
   2455 			unlex(lexer, &tok);
   2456 		}
   2457 
   2458 		switch (lex(lexer, &tok)) {
   2459 		case T_COMMA:
   2460 			lex(lexer, &tok);
   2461 			if (tok.token == T_NAME
   2462 					|| tok.token == T_ATTR_SYMBOL) {
   2463 				i->next = xcalloc(1, sizeof(struct ast_global_decl));
   2464 				i = i->next;
   2465 				unlex(lexer, &tok);
   2466 				break;
   2467 			}
   2468 			/* fallthrough */
   2469 		default:
   2470 			more = false;
   2471 			unlex(lexer, &tok);
   2472 			break;
   2473 		}
   2474 	}
   2475 }
   2476 
   2477 static void
   2478 parse_type_decl(struct lexer *lexer, struct ast_type_decl *decl)
   2479 {
   2480 	struct token tok = {0};
   2481 	struct ast_type_decl *i = decl;
   2482 	bool more = true;
   2483 	while (more) {
   2484 		parse_identifier(lexer, &i->ident, false);
   2485 		want(lexer, T_EQUAL, NULL);
   2486 		switch (lex(lexer, &tok)) {
   2487 		case T_ENUM:
   2488 			i->type = parse_enum_type(&i->ident, lexer);
   2489 			break;
   2490 		default:
   2491 			unlex(lexer, &tok);
   2492 			i->type = parse_type(lexer);
   2493 		}
   2494 		switch (lex(lexer, &tok)) {
   2495 		case T_COMMA:
   2496 			if (lex(lexer, &tok) == T_NAME) {
   2497 				i->next = xcalloc(1, sizeof(struct ast_type_decl));
   2498 				i = i->next;
   2499 				unlex(lexer, &tok);
   2500 				break;
   2501 			}
   2502 			/* fallthrough */
   2503 		default:
   2504 			more = false;
   2505 			unlex(lexer, &tok);
   2506 			break;
   2507 		}
   2508 	}
   2509 }
   2510 
   2511 static void
   2512 parse_fn_decl(struct lexer *lexer, struct ast_function_decl *decl)
   2513 {
   2514 	struct token tok = {0};
   2515 	bool more = true;
   2516 	bool _noreturn = false;
   2517 	while (more) {
   2518 		switch (lex(lexer, &tok)) {
   2519 		case T_ATTR_FINI:
   2520 			decl->flags |= FN_FINI;
   2521 			break;
   2522 		case T_ATTR_INIT:
   2523 			decl->flags |= FN_INIT;
   2524 			break;
   2525 		case T_ATTR_SYMBOL:
   2526 			decl->symbol = parse_attr_symbol(lexer);
   2527 			break;
   2528 		case T_ATTR_TEST:
   2529 			decl->flags |= FN_TEST;
   2530 			break;
   2531 		case T_ATTR_NORETURN:
   2532 			_noreturn = true;
   2533 			break;
   2534 		default:
   2535 			more = false;
   2536 			unlex(lexer, &tok);
   2537 			break;
   2538 		}
   2539 	}
   2540 	want(lexer, T_FN, NULL);
   2541 	parse_identifier(lexer, &decl->ident, false);
   2542 	parse_prototype(lexer, &decl->prototype);
   2543 	if (_noreturn) {
   2544 		decl->prototype.flags |= FN_NORETURN;
   2545 	}
   2546 
   2547 	switch (lex(lexer, &tok)) {
   2548 	case T_EQUAL:
   2549 		decl->body = parse_expression(lexer);
   2550 		break;
   2551 	case T_SEMICOLON:
   2552 		unlex(lexer, &tok);
   2553 		decl->body = NULL; // Prototype
   2554 		break;
   2555 	default:
   2556 		synerr(&tok, T_EQUAL, T_SEMICOLON, T_EOF);
   2557 	}
   2558 }
   2559 
   2560 static void
   2561 parse_decl(struct lexer *lexer, struct ast_decl *decl)
   2562 {
   2563 	struct token tok = {0};
   2564 	decl->loc = lexer->loc;
   2565 	switch (lex(lexer, &tok)) {
   2566 	case T_CONST:
   2567 	case T_LET:
   2568 		decl->decl_type = AST_DECL_GLOBAL;
   2569 		parse_global_decl(lexer, tok.token, &decl->global);
   2570 		break;
   2571 	case T_DEF:
   2572 		decl->decl_type = AST_DECL_CONST;
   2573 		parse_global_decl(lexer, tok.token, &decl->constant);
   2574 		break;
   2575 	case T_TYPE:
   2576 		decl->decl_type = AST_DECL_TYPE;
   2577 		parse_type_decl(lexer, &decl->type);
   2578 		break;
   2579 	default:
   2580 		unlex(lexer, &tok);
   2581 		decl->decl_type = AST_DECL_FUNC;
   2582 		parse_fn_decl(lexer, &decl->function);
   2583 		break;
   2584 	}
   2585 }
   2586 
   2587 static void
   2588 parse_decls(struct lexer *lexer, struct ast_decls **decls)
   2589 {
   2590 	struct token tok = {0};
   2591 	struct ast_decls **next = decls;
   2592 	while (tok.token != T_EOF) {
   2593 		struct ast_decls *decl = *next =
   2594 			xcalloc(1, sizeof(struct ast_decls));
   2595 		switch (lex(lexer, &tok)) {
   2596 		case T_EXPORT:
   2597 			decl->decl.exported = true;
   2598 			break;
   2599 		default:
   2600 			unlex(lexer, &tok);
   2601 			break;
   2602 		}
   2603 		if (tok.token == T_EOF) {
   2604 			break;
   2605 		}
   2606 		parse_decl(lexer, &decl->decl);
   2607 		next = &decl->next;
   2608 		want(lexer, T_SEMICOLON, NULL);
   2609 		if (lex(lexer, &tok) != T_EOF) {
   2610 			unlex(lexer, &tok);
   2611 		}
   2612 	}
   2613 	free(*next);
   2614 	*next = 0;
   2615 }
   2616 
   2617 void
   2618 parse(struct lexer *lexer, struct ast_subunit *subunit)
   2619 {
   2620 	parse_imports(lexer, subunit);
   2621 	parse_decls(lexer, &subunit->decls);
   2622 	want(lexer, T_EOF, NULL);
   2623 }