parser.jou

import "stdlib/ascii.jou"
import "stdlib/str.jou"
import "stdlib/io.jou"
import "stdlib/mem.jou"
import "./token.jou"
import "./ast.jou"
import "./errors_and_warnings.jou"
import "./paths.jou"


# arity = number of operands, e.g. 2 for a binary operator such as "+"
#
# This cannot be used for ++ and --, because with them we can't know the kind from
# just the token (e.g. ++ could mean pre-increment or post-increment).
def build_operator_expression(t: Token*, arity: int, operands: AstExpression*) -> AstExpression:
    assert arity == 1 or arity == 2
    nbytes = arity * sizeof operands[0]
    ptr = malloc(nbytes)
    memcpy(ptr, operands, nbytes)

    result = AstExpression{location = t->location, operands = ptr}

    if t->is_operator("&"):
        assert arity == 1
        result.kind = AstExpressionKind.AddressOf
    elif t->is_operator("["):
        assert arity == 2
        result.kind = AstExpressionKind.Indexing
    elif t->is_operator("=="):
        assert arity == 2
        result.kind = AstExpressionKind.Eq
    elif t->is_operator("!="):
        assert arity == 2
        result.kind = AstExpressionKind.Ne
    elif t->is_operator(">"):
        assert arity == 2
        result.kind = AstExpressionKind.Gt
    elif t->is_operator(">="):
        assert arity == 2
        result.kind = AstExpressionKind.Ge
    elif t->is_operator("<"):
        assert arity == 2
        result.kind = AstExpressionKind.Lt
    elif t->is_operator("<="):
        assert arity == 2
        result.kind = AstExpressionKind.Le
    elif t->is_operator("+"):
        assert arity == 2
        result.kind = AstExpressionKind.Add
    elif t->is_operator("-"):
        if arity == 2:
            result.kind = AstExpressionKind.Sub
        else:
            result.kind = AstExpressionKind.Negate
    elif t->is_operator("*"):
        if arity == 2:
            result.kind = AstExpressionKind.Mul
        else:
            result.kind = AstExpressionKind.Dereference
    elif t->is_operator("/"):
        assert arity == 2
        result.kind = AstExpressionKind.Div
    elif t->is_operator("%"):
        assert arity == 2
        result.kind = AstExpressionKind.Mod
    elif t->is_keyword("and"):
        assert arity == 2
        result.kind = AstExpressionKind.And
    elif t->is_keyword("or"):
        assert arity == 2
        result.kind = AstExpressionKind.Or
    elif t->is_keyword("not"):
        assert arity == 1
        result.kind = AstExpressionKind.Not
    else:
        assert False

    assert result.get_arity() == arity
    return result

# reverse code golfing: https://xkcd.com/1960/
def determine_the_kind_of_a_statement_that_starts_with_an_expression(
    this_token_is_after_that_initial_expression: Token*
) -> AstStatementKind:
    if this_token_is_after_that_initial_expression->is_operator("="):
        return AstStatementKind.Assign
    if this_token_is_after_that_initial_expression->is_operator("+="):
        return AstStatementKind.InPlaceAdd
    if this_token_is_after_that_initial_expression->is_operator("-="):
        return AstStatementKind.InPlaceSub
    if this_token_is_after_that_initial_expression->is_operator("*="):
        return AstStatementKind.InPlaceMul
    if this_token_is_after_that_initial_expression->is_operator("/="):
        return AstStatementKind.InPlaceDiv
    if this_token_is_after_that_initial_expression->is_operator("%="):
        return AstStatementKind.InPlaceMod
    return AstStatementKind.ExpressionStatement

# TODO: this function is just bad...
def read_assertion_from_file(start: Location, end: Location) -> byte*:
    assert start.path == end.path

    f = fopen(start.path, "rb")
    assert f != NULL

    line: byte[1024]
    lineno = 1
    while lineno < start.lineno:
        assert fgets(line, sizeof(line) as int, f) != NULL
        lineno++

    result: byte* = malloc(2000 * (end.lineno - start.lineno + 1))
    result[0] = '\0'

    while lineno <= end.lineno:
        assert fgets(line, sizeof(line) as int, f) != NULL
        lineno++

        # TODO: strings containing '#' ... so much wrong with dis
        if strstr(line, "#") != NULL:
            *strstr(line, "#") = '\0'
        trim_ascii_whitespace(line)

        # Add spaces between lines, but not after '(' or before ')'
        if not starts_with(line, ")") and not ends_with(result, "("):
            strcat(result, " ")
        strcat(result, line)

    fclose(f)

    trim_ascii_whitespace(result)
    if starts_with(result, "assert"):
        memmove(result, &result[6], strlen(&result[6]) + 1)
        trim_ascii_whitespace(result)

    return result


def decorate(stmt: AstStatement*, decor: byte*, location: Location) -> None:
    assert decor[0] == '@'

    if strcmp(decor, "@public") == 0:
        match stmt->kind:
            case AstStatementKind.FunctionDeclare | AstStatementKind.FunctionDef:
                if strcmp(stmt->function.ast_signature.name, "main") == 0:
                    fail(location, "the main() function cannot be @public")
                stmt->function.public = True
            case AstStatementKind.MethodDef:
                fail(location, "methods cannot be decorated with @public, a class is either fully public or fully private")
            case AstStatementKind.Class:
                stmt->classdef.public = True
            case AstStatementKind.Enum:
                stmt->enumdef.public = True
            case AstStatementKind.GlobalVariableDeclare:
                stmt->global_var_declare.public = True
            case AstStatementKind.GlobalVariableDef:
                stmt->global_var_def.public = True
            case _:
                fail(location, "the @public decorator cannot be used here")
    else:
        msg: byte[200]
        snprintf(msg, sizeof(msg), "there is no decorator named '%s'", decor)
        fail(location, msg)


enum WhatAreWeParsing:
    TopLevel  # must be first, so that this is the default (zero)
    ClassBody
    FunctionBody
    MethodBody


class Parser:
    tokens: Token*
    stdlib_path: byte*
    loop_vars: byte**
    nloops: int
    what_are_we_parsing: WhatAreWeParsing

    def eat_newline(self) -> None:
        if self->tokens->kind != TokenKind.Newline:
            self->tokens->fail_expected_got("end of line")
        self->tokens++

    def check_top_level(self, what_is_it: byte*) -> None:
        if self->what_are_we_parsing != WhatAreWeParsing.TopLevel:
            msg: byte[500]
            snprintf(msg, sizeof(msg), "%s must be on top level, not e.g. inside a function", what_is_it)
            fail(self->tokens->location, msg)

    def check_function_or_method(self, what_is_it: byte*) -> None:
        match self->what_are_we_parsing:
            case WhatAreWeParsing.FunctionBody | WhatAreWeParsing.MethodBody:
                pass
            case _:
                msg: byte[500]
                snprintf(msg, sizeof(msg), "%s must be inside a function or method", what_is_it)
                fail(self->tokens->location, msg)

    def parse_import(self) -> AstImport:
        if self->what_are_we_parsing != WhatAreWeParsing.TopLevel:
            fail(self->tokens->location, "imports must be in the beginning of the file")

        assert self->tokens->is_keyword("import")
        self->tokens++

        path_token = self->tokens++
        if path_token->kind != TokenKind.String:
            path_token->fail_expected_got("a string to specify the file name")

        self->eat_newline()

        path: byte*
        if starts_with(path_token->long_string, "stdlib/"):
            # Starts with stdlib --> import from where stdlib actually is
            asprintf(&path, "%s/%s", self->stdlib_path, &path_token->long_string[7])
        elif starts_with(path_token->long_string, "."):
            # Relative to directory where the file is
            tmp = strdup(path_token->location.path)
            asprintf(&path, "%s/%s", dirname(tmp), path_token->long_string)
            free(tmp)
        else:
            fail(
                path_token->location,
                "import path must start with 'stdlib/' (standard-library import) or a dot (relative import)"
            )

        simplify_path(path)
        return AstImport{
            specified_path = strdup(path_token->long_string),
            resolved_path = path,
        }

    def parse_link(self) -> AstLink:
        self->check_top_level("'link' statement")

        assert self->tokens->is_keyword("link")
        self->tokens++

        flags_token = self->tokens++
        if flags_token->kind != TokenKind.String:
            flags_token->fail_expected_got("a string of linker flags after the 'link' keyword")

        self->eat_newline()

        resolved_flags = handle_relative_paths_in_linker_flags(flags_token->long_string, flags_token->location.path)

        return AstLink{
            specified_flags = strdup(flags_token->long_string),
            resolved_flags = resolved_flags,
        }

    def parse_type(self) -> AstType:
        if not (
            self->tokens->kind == TokenKind.Name
            or self->tokens->is_keyword("None")
            or self->tokens->is_keyword("void")
            or self->tokens->is_keyword("noreturn")
            or self->tokens->is_keyword("short")
            or self->tokens->is_keyword("int")
            or self->tokens->is_keyword("long")
            or self->tokens->is_keyword("byte")
            or self->tokens->is_keyword("float")
            or self->tokens->is_keyword("double")
            or self->tokens->is_keyword("bool")
        ):
            self->tokens->fail_expected_got("a type")

        result = AstType{
            kind = AstTypeKind.Named,
            location = self->tokens->location,
            name = self->tokens->short_string,
        }
        self->tokens++

        while self->tokens->is_operator("*") or self->tokens->is_operator("["):
            p: AstType* = malloc(sizeof *p)
            *p = result

            if self->tokens->is_operator("*"):
                result = AstType{
                    location = (self->tokens++)->location,  # TODO: shouldn't need all the parentheses
                    kind = AstTypeKind.Pointer,
                    value_type = p,
                }
            else:
                location = (self->tokens++)->location

                len_expression: AstExpression* = malloc(sizeof *len_expression)
                *len_expression = self->parse_expression()

                if not self->tokens->is_operator("]"):
                    self->tokens->fail_expected_got("a ']' to end the array size")
                self->tokens++

                result = AstType{
                    location = location,
                    kind = AstTypeKind.Array,
                    array = AstArrayType{
                        member_type = p,
                        length = len_expression,
                    }
                }

        return result

    def parse_name_type_value(self, expected_what_for_name: byte*) -> AstNameTypeValue:
        if self->tokens->kind != TokenKind.Name:
            assert expected_what_for_name != NULL
            self->tokens->fail_expected_got(expected_what_for_name)

        result = AstNameTypeValue{name = self->tokens->short_string, name_location = self->tokens->location}
        self->tokens++

        if not self->tokens->is_operator(":"):
            self->tokens->fail_expected_got("':' and a type after it (example: \"foo: int\")")
        self->tokens++
        result.type = self->parse_type()

        if self->tokens->is_operator("="):
            self->tokens++
            p: AstExpression* = malloc(sizeof *p)
            *p = self->parse_expression()
            result.value = p

        return result

    def parse_function_or_method_signature(self, is_method: bool) -> AstSignature:
        if self->tokens->kind != TokenKind.Name:
            if is_method:
                self->tokens->fail_expected_got("a method name")
            else:
                self->tokens->fail_expected_got("a function name")

        result = AstSignature{
            name_location = self->tokens->location,
            name = self->tokens->short_string,
        }
        self->tokens++

        if not self->tokens->is_operator("("):
            self->tokens->fail_expected_got("a '(' to denote the start of arguments")
        self->tokens++

        used_self = False
        while not self->tokens->is_operator(")"):
            if result.takes_varargs:
                fail(self->tokens->location, "if '...' is used, it must be the last parameter")

            if self->tokens->is_operator("..."):
                result.takes_varargs = True
                self->tokens++

            elif self->tokens->is_keyword("self"):
                if not is_method:
                    fail(self->tokens->location, "'self' cannot be used here")

                self_arg = AstNameTypeValue{
                    name = "self",
                    name_location = self->tokens->location,
                }
                self->tokens++

                if self->tokens->is_operator(":"):
                    self->tokens++
                    self_arg.type = self->parse_type()

                result.args = realloc(result.args, sizeof result.args[0] * (result.nargs+1))
                result.args[result.nargs++] = self_arg
                used_self = True

            else:
                arg = self->parse_name_type_value("an argument name")
                if arg.value != NULL:
                    fail(arg.value->location, "arguments cannot have default values")

                for i = 0; i < result.nargs; i++:
                    if strcmp(result.args[i].name, arg.name) == 0:
                        message: byte[200]
                        snprintf(
                            message, sizeof message,
                            "there are multiple arguments named '%s'", arg.name)
                        fail(arg.name_location, message)

                result.args = realloc(result.args, sizeof result.args[0] * (result.nargs+1))
                result.args[result.nargs++] = arg

            if not self->tokens->is_operator(","):
                break
            self->tokens++

        if not self->tokens->is_operator(")"):
            self->tokens->fail_expected_got("a ')'")
        self->tokens++

        # TODO: make sure "self" is first, doesn't seem to be checked?
        #       or do we even want it? consider fread() and /~https://github.com/Akuli/jou/issues/740

        # Special case for common typo:   def foo():
        if self->tokens->is_operator(":"):
            if is_method:
                fail(self->tokens->location, "return type must be specified with '->', or with '-> None' if the method doesn't return anything")
            else:
                fail(self->tokens->location, "return type must be specified with '->', or with '-> None' if the function doesn't return anything")
        if not self->tokens->is_operator("->"):
            self->tokens->fail_expected_got("a '->'")
        self->tokens++

        if not used_self and is_method:
            throwerror: byte[300]
            snprintf(throwerror, sizeof throwerror, "missing self, should be 'def %s(self, ...)'", result.name)
            fail(self->tokens->location, throwerror)

        result.return_type = self->parse_type()
        return result

    def parse_call(self) -> AstCall:
        assert self->tokens->kind == TokenKind.Name  # must be checked when calling this function
        result = AstCall{location = self->tokens->location, name = self->tokens->short_string}
        self->tokens++
        assert self->tokens->is_operator("(")
        self->tokens++

        while not self->tokens->is_operator(")"):
            result.args = realloc(result.args, sizeof result.args[0] * (result.nargs+1))
            result.args[result.nargs++] = self->parse_expression()
            if not self->tokens->is_operator(","):
                break
            self->tokens++

        if not self->tokens->is_operator(")"):
            self->tokens->fail_expected_got("a ')'")
        self->tokens++

        return result

    def parse_instantiation(self) -> AstInstantiation:
        assert self->tokens->kind == TokenKind.Name
        result = AstInstantiation{class_name = self->tokens->short_string}
        self->tokens++
        assert self->tokens->is_operator("{")
        self->tokens++

        while not self->tokens->is_operator("}"):
            if self->tokens->kind != TokenKind.Name:
                self->tokens->fail_expected_got("a field name")
            field_name = self->tokens->short_string
            for i = 0; i < result.nfields; i++:
                if strcmp(result.field_names[i], field_name) == 0:
                    error: byte[500]
                    snprintf(error, sizeof error, "multiple values were given for field '%s'", field_name)
                    fail(self->tokens->location, error)
            result.field_names = realloc(result.field_names, (result.nfields + 1) * sizeof result.field_names[0])
            result.field_names[result.nfields] = field_name
            self->tokens++

            if not self->tokens->is_operator("="):
                msg: byte[300]
                snprintf(msg, sizeof msg, "'=' followed by a value for field '%s'", field_name)
                self->tokens->fail_expected_got(msg)
            self->tokens++

            result.field_values = realloc(result.field_values, sizeof result.field_values[0] * (result.nfields+1))
            result.field_values[result.nfields] = self->parse_expression()

            result.nfields++
            if not self->tokens->is_operator(","):
                break
            self->tokens++

        if not self->tokens->is_operator("}"):
            self->tokens->fail_expected_got("a '}'")
        self->tokens++

        return result

    def parse_array(self) -> AstArray:
        assert self->tokens->is_operator("[")
        self->tokens++

        result = AstArray{}
        while not self->tokens->is_operator("]"):
            result.items = realloc(result.items, (result.length + 1) * sizeof result.items[0])
            result.items[result.length++] = self->parse_expression()
            if not self->tokens->is_operator(","):
                break
            self->tokens++

        if not self->tokens->is_operator("]"):
            self->tokens->fail_expected_got("a ']' to end the array")
        if result.length == 0:
            fail(self->tokens->location, "arrays cannot be empty")
        self->tokens++

        return result

    def parse_elementary_expression(self) -> AstExpression:
        expr = AstExpression{location = self->tokens->location}

        match self->tokens->kind:
            case TokenKind.Short:
                expr.kind = AstExpressionKind.Short
                expr.short_value = self->tokens->short_value
                self->tokens++
            case TokenKind.Int:
                expr.kind = AstExpressionKind.Int
                expr.int_value = self->tokens->int_value
                self->tokens++
            case TokenKind.Long:
                expr.kind = AstExpressionKind.Long
                expr.long_value = self->tokens->long_value
                self->tokens++
            case TokenKind.Byte:
                expr.kind = AstExpressionKind.Byte
                expr.byte_value = self->tokens->byte_value
                self->tokens++
            case TokenKind.String:
                expr.kind = AstExpressionKind.String
                expr.string = strdup(self->tokens->long_string)
                self->tokens++
            case TokenKind.Float:
                expr.kind = AstExpressionKind.Float
                expr.float_or_double_text = self->tokens->short_string
                self->tokens++
            case TokenKind.Double:
                expr.kind = AstExpressionKind.Double
                expr.float_or_double_text = self->tokens->short_string
                self->tokens++
            case TokenKind.Name:
                if self->tokens[1].is_operator("("):
                    expr.kind = AstExpressionKind.Call
                    expr.call = self->parse_call()
                elif self->tokens[1].is_operator("{"):
                    expr.kind = AstExpressionKind.Instantiate
                    expr.instantiation = self->parse_instantiation()
                else:
                    expr.kind = AstExpressionKind.GetVariable
                    expr.varname = self->tokens->short_string
                    self->tokens++
            case _:
                if self->tokens->is_keyword("True"):
                    expr.kind = AstExpressionKind.Bool
                    expr.bool_value = True
                    self->tokens++
                elif self->tokens->is_keyword("False"):
                    expr.kind = AstExpressionKind.Bool
                    expr.bool_value = False
                    self->tokens++
                elif self->tokens->is_keyword("NULL"):
                    expr.kind = AstExpressionKind.Null
                    self->tokens++
                elif self->tokens->is_keyword("None"):
                    fail(self->tokens->location, "None is not a value in Jou, use e.g. -1 for numbers or NULL for pointers")
                elif self->tokens->is_keyword("self"):
                    if self->what_are_we_parsing != WhatAreWeParsing.MethodBody:
                        fail(self->tokens->location, "'self' cannot be used here")
                    expr.kind = AstExpressionKind.Self
                    self->tokens++
                elif self->tokens->is_operator("("):
                    self->tokens++
                    expr = self->parse_expression()
                    if not self->tokens->is_operator(")"):
                        self->tokens->fail_expected_got("a ')'")
                    self->tokens++
                elif self->tokens->is_operator("["):
                    expr.kind = AstExpressionKind.Array
                    expr.array = self->parse_array()
                else:
                    self->tokens->fail_expected_got("an expression")

        return expr

    def parse_expression_with_fields_and_methods_and_indexing(self) -> AstExpression:
        result = self->parse_elementary_expression()

        while self->tokens->is_operator(".") or self->tokens->is_operator("->") or self->tokens->is_operator("["):
            if self->tokens->is_operator("["):
                open_bracket = self->tokens++
                operands = [result, self->parse_expression()]
                if not self->tokens->is_operator("]"):
                    self->tokens->fail_expected_got("a ']'")
                self->tokens++
                result = build_operator_expression(open_bracket, 2, operands)

            else:
                start_op = self->tokens++
                if self->tokens->kind != TokenKind.Name:
                    self->tokens->fail_expected_got("a field or method name")

                instance: AstExpression* = malloc(sizeof *instance)
                *instance = result

                if self->tokens[1].is_operator("("):
                    call = self->parse_call()
                    call.method_call_self = instance
                    call.uses_arrow_operator = start_op->is_operator("->")
                    result = AstExpression{
                        location = call.location,
                        kind = AstExpressionKind.Call,
                        call = call,
                    }
                else:
                    result = AstExpression{
                        location = self->tokens->location,
                        kind = AstExpressionKind.GetClassField,
                        class_field = AstClassField{
                            instance = instance,
                            uses_arrow_operator = start_op->is_operator("->"),
                            field_name = self->tokens->short_string,
                        },
                    }
                    self->tokens++

        return result

    def parse_expression_with_unary_operators(self) -> AstExpression:
        # prefix = sequneces of 0 or more unary operator tokens: start,start+1,...,end-1
        prefix_start = self->tokens
        while (
            self->tokens->is_operator("++")
            or self->tokens->is_operator("--")
            or self->tokens->is_operator("&")
            or self->tokens->is_operator("*")
            or self->tokens->is_keyword("sizeof")
        ):
            self->tokens++
        prefix_end = self->tokens

        result = self->parse_expression_with_fields_and_methods_and_indexing()

        suffix_start = self->tokens
        while self->tokens->is_operator("++") or self->tokens->is_operator("--"):
            self->tokens++
        suffix_end = self->tokens

        while prefix_start != prefix_end or suffix_start != suffix_end:
            # ++ and -- "bind tighter", so *foo++ is equivalent to *(foo++)
            # It is implemented by always consuming ++/-- prefixes and suffixes when they exist.
            if prefix_start != prefix_end and prefix_end[-1].is_operator("++"):
                token = --prefix_end
                kind = AstExpressionKind.PreIncr
            elif prefix_start != prefix_end and prefix_end[-1].is_operator("--"):
                token = --prefix_end
                kind = AstExpressionKind.PreDecr
            elif suffix_start != suffix_end and suffix_start[0].is_operator("++"):
                token = suffix_start++
                kind = AstExpressionKind.PostIncr
            elif suffix_start != suffix_end and suffix_start[0].is_operator("--"):
                token = suffix_start++
                kind = AstExpressionKind.PostDecr
            else:
                # We don't have ++ or --, so it must be something in the prefix
                assert prefix_start != prefix_end and suffix_start == suffix_end
                token = --prefix_end
                if token->is_operator("*"):
                    kind = AstExpressionKind.Dereference
                elif token->is_operator("&"):
                    kind = AstExpressionKind.AddressOf
                elif token->is_keyword("sizeof"):
                    kind = AstExpressionKind.SizeOf
                else:
                    assert False

            p: AstExpression* = malloc(sizeof(*p))
            *p = result
            result = AstExpression{location = token->location, kind = kind, operands = p}

        return result

    def parse_expression_with_mul_and_div(self) -> AstExpression:
        result = self->parse_expression_with_unary_operators()
        while self->tokens->is_operator("*") or self->tokens->is_operator("/") or self->tokens->is_operator("%"):
            t = self->tokens++
            lhs_rhs = [result, self->parse_expression_with_unary_operators()]
            result = build_operator_expression(t, 2, lhs_rhs)
        return result

    def parse_expression_with_add(self) -> AstExpression:
        if self->tokens->is_operator("-"):
            minus = self->tokens++
        else:
            minus = NULL

        result = self->parse_expression_with_mul_and_div()
        if minus != NULL:
            result = build_operator_expression(minus, 1, &result)

        while self->tokens->is_operator("+") or self->tokens->is_operator("-"):
            t = self->tokens++
            lhs_rhs = [result, self->parse_expression_with_mul_and_div()]
            result = build_operator_expression(t, 2, lhs_rhs)

        return result

    # "as" operator has somewhat low precedence, so that "1+2 as float" works as expected
    def parse_expression_with_as(self) -> AstExpression:
        result = self->parse_expression_with_add()
        while self->tokens->is_keyword("as"):
            as_location = (self->tokens++)->location
            p: AstAs* = malloc(sizeof(*p))
            *p = AstAs{type = self->parse_type(), value = result}
            result = AstExpression{
                location = as_location,
                kind = AstExpressionKind.As,
                as_ = p,
            }
        return result

    def parse_expression_with_comparisons(self) -> AstExpression:
        result = self->parse_expression_with_as()
        if self->tokens->is_comparison():
            t = self->tokens++
            lhs_rhs = [result, self->parse_expression_with_as()]
            result = build_operator_expression(t, 2, lhs_rhs)
        if self->tokens->is_comparison():
            fail(self->tokens->location, "comparisons cannot be chained")
        return result

    def parse_expression_with_not(self) -> AstExpression:
        if self->tokens->is_keyword("not"):
            not_token = self->tokens
            self->tokens++
        else:
            not_token = NULL

        if self->tokens->is_keyword("not"):
            fail(self->tokens->location, "'not' cannot be repeated")

        result = self->parse_expression_with_comparisons()
        if not_token != NULL:
            match result.kind:
                case AstExpressionKind.Eq:
                    show_warning(result.location, "use 'foo != bar' instead of 'not foo == bar'")
                case AstExpressionKind.Ne:
                    show_warning(result.location, "use 'foo == bar' instead of 'not foo != bar'")
                case _:
                    pass
            result = build_operator_expression(not_token, 1, &result)
        return result

    def parse_expression_with_and_or(self) -> AstExpression:
        result = self->parse_expression_with_not()
        got_and = False
        got_or = False

        while True:
            if self->tokens->is_keyword("and"):
                got_and = True
            elif self->tokens->is_keyword("or"):
                got_or = True
            else:
                break
            if got_and and got_or:
                fail(self->tokens->location, "'and' cannot be chained with 'or', you need more parentheses")

            t = self->tokens++
            lhs_rhs = [result, self->parse_expression_with_not()]
            result = build_operator_expression(t, 2, lhs_rhs)

        return result

    def parse_expression(self) -> AstExpression:
        return self->parse_expression_with_and_or()

    def parse_expression_with_unnecessary_parens_warning(self, description_of_expr: byte*) -> AstExpression:
        start = self->tokens
        result = self->parse_expression_with_and_or()
        end = &self->tokens[-1]

        if (
            start->is_operator("(")
            and end->is_operator(")")
            and start->location.lineno == end->location.lineno
        ):
            # Check if starting '(' is closed with a ')' before the end
            depth = 1
            closed_early = False
            for p = &start[1]; p < end; p++:
                if p->is_operator("("):
                    depth++
                if p->is_operator(")"):
                    depth--
                    if depth == 0:
                        closed_early = True
                        break
            if not closed_early:
                msg: byte[500]
                snprintf(msg, sizeof(msg), "parentheses around %s are unnecessary", description_of_expr)
                show_warning(start->location, msg)

        return result

    # does not eat a trailing newline
    def parse_oneline_statement(self) -> AstStatement:
        result = AstStatement{ location = self->tokens->location }
        if self->tokens->is_keyword("return"):
            self->check_function_or_method("'return'")
            self->tokens++
            result.kind = AstStatementKind.Return
            if self->tokens->kind != TokenKind.Newline:
                result.return_value = malloc(sizeof *result.return_value)
                *result.return_value = self->parse_expression()
        elif self->tokens->is_keyword("assert"):
            self->check_function_or_method("'assert'")
            self->tokens++
            result.kind = AstStatementKind.Assert
            start = self->tokens->location
            result.assertion.condition = self->parse_expression()
            end = self->tokens->location
            result.assertion.condition_str = read_assertion_from_file(start, end)
        elif self->tokens->is_keyword("pass"):
            self->tokens++
            result.kind = AstStatementKind.Pass
        elif self->tokens->is_keyword("break"):
            if self->nloops == 0:
                fail(self->tokens->location, "'break' can only be used inside a loop")
            self->tokens++
            result.kind = AstStatementKind.Break
        elif self->tokens->is_keyword("continue"):
            if self->nloops == 0:
                fail(self->tokens->location, "'continue' can only be used inside a loop")
            self->tokens++
            result.kind = AstStatementKind.Continue
        elif self->tokens->kind == TokenKind.Name and self->tokens[1].is_operator(":"):
            # e.g. "foo: int"
            match self->what_are_we_parsing:
                case WhatAreWeParsing.TopLevel:
                    fail(self->tokens->location, "missing 'global' keyword when defining global variable")
                case WhatAreWeParsing.ClassBody:
                    result.kind = AstStatementKind.ClassField
                    result.class_field = self->parse_name_type_value(NULL)
                    if result.class_field.value != NULL:
                        fail(result.class_field.value->location, "class fields cannot have default values")
                case WhatAreWeParsing.FunctionBody | WhatAreWeParsing.MethodBody:
                    result.kind = AstStatementKind.DeclareLocalVar
                    result.local_var_declare = self->parse_name_type_value(NULL)
        else:
            expr = self->parse_expression()
            result.kind = determine_the_kind_of_a_statement_that_starts_with_an_expression(self->tokens)
            if (
                result.kind == AstStatementKind.Assign
                and self->what_are_we_parsing == WhatAreWeParsing.TopLevel
            ):
                # Would fail anyway, but let's produce a better error message
                fail(expr.location, "missing 'global' keyword when defining global variable")
            if result.kind == AstStatementKind.ExpressionStatement:
                if not expr.is_valid_as_a_statement():
                    fail(expr.location, "not a valid statement")
                result.expression = expr
                self->check_function_or_method("this line of code")
            else:
                self->tokens++
                result.assignment = AstAssignment{target = expr, value = self->parse_expression()}
                if self->tokens->is_operator("="):
                    # Would fail elsewhere anyway, but let's make the error message clear
                    fail(self->tokens->location, "only one variable can be assigned at a time")
                self->check_function_or_method("assignments")

        return result

    def parse_if_statement(self) -> AstIfStatement:
        ifs_and_elifs: AstConditionAndBody* = NULL
        n = 0

        assert self->tokens->is_keyword("if")
        while True:
            self->tokens++
            cond = self->parse_expression_with_unnecessary_parens_warning("if statement condition")
            body = self->parse_body()
            ifs_and_elifs = realloc(ifs_and_elifs, sizeof ifs_and_elifs[0] * (n+1))
            ifs_and_elifs[n++] = AstConditionAndBody{condition = cond, body = body}
            if not self->tokens->is_keyword("elif"):
                break

        if self->tokens->is_keyword("else"):
            self->tokens++
            else_body = self->parse_body()
        else:
            else_body = AstBody{}

        return AstIfStatement{
            if_and_elifs = ifs_and_elifs,
            n_if_and_elifs = n,
            else_body = else_body,
        }

    def enter_loop_body(self, varname: byte*, location: Location) -> None:
        if varname != NULL:
            for i = 0; i < self->nloops; i++:
                if self->loop_vars[i] != NULL and strcmp(self->loop_vars[i], varname) == 0:
                    msg: byte[500]
                    snprintf(msg, sizeof(msg), "this loop is inside another loop that also uses variable '%s'", varname)
                    show_warning(location, msg)
                    break

        self->loop_vars = realloc(self->loop_vars, sizeof(self->loop_vars[0]) * (self->nloops + 1))
        assert self->loop_vars != NULL
        self->loop_vars[self->nloops++] = varname

    def exit_loop_body(self) -> None:
        self->nloops--

    def parse_while_loop(self) -> AstConditionAndBody:
        assert self->tokens->is_keyword("while")
        self->check_function_or_method("while loop")
        self->tokens++
        cond = self->parse_expression_with_unnecessary_parens_warning("while loop condition")
        self->enter_loop_body(NULL, Location{})
        body = self->parse_body()
        self->exit_loop_body()
        return AstConditionAndBody{condition = cond, body = body}

    def parse_for_loop(self) -> AstForLoop:
        assert self->tokens->is_keyword("for")
        self->check_function_or_method("for loop")
        self->tokens++

        # Check if it's "for i in ..." loop, those are not supported
        if (
            self->tokens[0].kind == TokenKind.Name
            and self->tokens[1].kind == TokenKind.Name
            and strcmp(self->tokens[1].short_string, "in") == 0
        ):
            fail(self->tokens[1].location, "Python-style for loops aren't supported. Use e.g. 'for i = 0; i < 10; i++'")

        init: AstStatement*
        if self->tokens->is_operator(";"):
            init = NULL
        else:
            init = malloc(sizeof *init)
            *init = self->parse_oneline_statement()

        if not self->tokens->is_operator(";"):
            self->tokens->fail_expected_got("a ';'")
        self->tokens++

        cond: AstExpression*
        if self->tokens->is_operator(";"):
            cond = NULL
        else:
            cond = malloc(sizeof *cond)
            *cond = self->parse_expression()

        if not self->tokens->is_operator(";"):
            self->tokens->fail_expected_got("a ';'")
        self->tokens++

        incr: AstStatement*
        if self->tokens->is_operator(":"):
            incr = NULL
        else:
            incr = malloc(sizeof *incr)
            *incr = self->parse_oneline_statement()

        if (
            init != NULL
            and init->kind == AstStatementKind.Assign
            and init->assignment.target.kind == AstExpressionKind.GetVariable
        ):
            # for varname = value; ...
            self->enter_loop_body(init->assignment.target.varname, init->location)
        else:
            self->enter_loop_body(NULL, Location{})
        body = self->parse_body()
        self->exit_loop_body()

        return AstForLoop{init = init, cond = cond, incr = incr, body = body}

    def parse_match_statement(self) -> AstMatchStatement:
        assert self->tokens->is_keyword("match")
        self->check_function_or_method("match statement")
        self->tokens++

        result = AstMatchStatement{match_obj = self->parse_expression()}

        if self->tokens->is_keyword("with"):
            self->tokens++
            if self->tokens->kind != TokenKind.Name:
                self->tokens->fail_expected_got("function name")
            result.func_name = (self->tokens++)->short_string

        self->parse_start_of_body()

        while self->tokens->kind != TokenKind.Dedent:
            if not self->tokens->is_keyword("case"):
                self->tokens->fail_expected_got("the 'case' keyword")
            if result.case_underscore != NULL:
                fail(
                    self->tokens->location,
                    "this case will never run, because 'case _:' above matches anything",
                )
            self->tokens++

            if (
                self->tokens->kind == TokenKind.Name
                and strcmp(self->tokens->short_string, "_") == 0
                and self->tokens[1].is_operator(":")
            ):
                # case _:
                result.case_underscore_location = (self->tokens++)->location
                result.case_underscore = malloc(sizeof(*result.case_underscore))
                assert result.case_underscore != NULL
                *result.case_underscore = self->parse_body()
            else:
                parens = self->tokens->is_operator("(")
                if parens:
                    self->tokens++
                case_objs: AstExpression* = NULL
                n_case_objs = 0
                while True:
                    case_objs = realloc(case_objs, sizeof(case_objs[0]) * (n_case_objs + 1))
                    case_objs[n_case_objs++] = self->parse_expression()
                    if self->tokens->is_operator("|"):
                        self->tokens++
                    elif (not parens) and self->tokens->is_operator(":"):
                        break
                    elif parens and self->tokens->is_operator(")") and self->tokens[1].is_operator(":"):
                        self->tokens++  # skip ')'
                        break
                    else:
                        if parens:
                            self->tokens->fail_expected_got("'|' or '):'")
                        else:
                            self->tokens->fail_expected_got("'|' or ':'")
                result.cases = realloc(result.cases, sizeof result.cases[0] * (result.ncases + 1))
                result.cases[result.ncases++] = AstCase{
                    case_objs = case_objs,
                    n_case_objs = n_case_objs,
                    body = self->parse_body(),
                }
        self->tokens++

        return result

    # Parses the "x: int" part of "x, y, z: int", leaving "y, z: int" to be parsed later.
    def parse_first_of_multiple_local_var_declares(self) -> AstNameTypeValue:
        assert self->tokens->kind == TokenKind.Name

        ntv = AstNameTypeValue{
            name = self->tokens->short_string,
            name_location = self->tokens->location,
        }

        # Take a backup of the parser where first variable name and its comma are consumed.
        save_state = *self
        save_state.tokens = &save_state.tokens[2]

        # Skip variables and commas so we can parse the type that comes after it
        self->tokens++
        while self->tokens->is_operator(",") and self->tokens[1].kind == TokenKind.Name:
            self->tokens = &self->tokens[2]

        # Error for "x, y = 0"
        if self->tokens->is_operator("="):
            fail(self->tokens->location, "only one variable can be assigned at a time")

        if not self->tokens->is_operator(":"):
            self->tokens->fail_expected_got("':' and a type after it (example: \"foo, bar: int\")")
        self->tokens++

        ntv.type = self->parse_type()

        # Error for "x, y: int = 0"
        if self->tokens->is_operator("="):
            fail(self->tokens->location, "only one variable can be assigned at a time")

        *self = save_state
        return ntv

    def parse_statement(self) -> AstStatement:
        decors_start = self->tokens
        while self->tokens->kind == TokenKind.Decorator:
            self->tokens++
            self->eat_newline()
        decors_end = self->tokens

        if self->tokens->is_keyword("import"):
            result = AstStatement{
                location = self->tokens->location,
                kind = AstStatementKind.Import,
                import_statement = self->parse_import(),
            }
        elif self->tokens->is_keyword("link"):
            result = AstStatement{
                location = self->tokens->location,
                kind = AstStatementKind.Link,
                link_statement = self->parse_link(),
            }
        elif self->tokens->is_keyword("def"):
            match self->what_are_we_parsing:
                case WhatAreWeParsing.TopLevel:
                    result = AstStatement{
                        location = self->tokens->location,
                        kind = AstStatementKind.FunctionDef,
                        function = self->parse_function_or_method(False),
                    }
                case WhatAreWeParsing.ClassBody:
                    result = AstStatement{
                        location = self->tokens->location,
                        kind = AstStatementKind.MethodDef,
                        function = self->parse_function_or_method(True),
                    }
                case WhatAreWeParsing.FunctionBody | WhatAreWeParsing.MethodBody:
                    fail(self->tokens->location, "nested functions are not supported")
        elif self->tokens->is_keyword("declare"):
            self->check_top_level("'declare'")
            location = (self->tokens++)->location
            if self->tokens->is_keyword("global"):
                self->tokens++
                ntv = self->parse_name_type_value("a variable name")
                if ntv.value != NULL:
                    fail(
                        ntv.value->location,
                        "a value cannot be given when declaring a global variable",
                    )
                result = AstStatement{
                    location = location,
                    kind = AstStatementKind.GlobalVariableDeclare,
                    global_var_def = AstGlobalVarDef{name = ntv.name, type = ntv.type},
                }
            else:
                result = AstStatement{
                    location = location,
                    kind = AstStatementKind.FunctionDeclare,
                    function = AstFunctionOrMethod{ast_signature = self->parse_function_or_method_signature(False)},
                }
            self->eat_newline()
        elif self->tokens->is_keyword("global"):
            self->check_top_level("global variables")
            location = (self->tokens++)->location
            ntv = self->parse_name_type_value("a variable name")
            if ntv.value != NULL:
                fail(
                    ntv.value->location,
                    "specifying a value for a global variable is not supported yet",
                )
            result = AstStatement{
                location = location,
                kind = AstStatementKind.GlobalVariableDef,
                global_var_def = AstGlobalVarDef{name = ntv.name, type = ntv.type},
            }
            self->eat_newline()
        elif self->tokens->is_keyword("class"):
            result = AstStatement{
                location = self->tokens->location,
                kind = AstStatementKind.Class,
                classdef = self->parse_class(),
            }
        elif self->tokens->is_keyword("union"):
            result = AstStatement{
                location = self->tokens->location,
                kind = AstStatementKind.ClassUnion,
                union_fields = self->parse_union(),
            }
        elif self->tokens->is_keyword("enum"):
            result = AstStatement{
                location = self->tokens->location,
                kind = AstStatementKind.Enum,
                enumdef = self->parse_enum(),
            }
        elif self->tokens->is_keyword("if"):
            result = AstStatement{
                location = self->tokens->location,
                kind = AstStatementKind.If,
                if_statement = self->parse_if_statement(),
            }
        elif self->tokens->is_keyword("for"):
            result = AstStatement{
                location = self->tokens->location,
                kind = AstStatementKind.ForLoop,
                for_loop = self->parse_for_loop(),
            }
        elif self->tokens->is_keyword("while"):
            result = AstStatement{
                location = self->tokens->location,
                kind = AstStatementKind.WhileLoop,
                while_loop = self->parse_while_loop(),
            }
        elif self->tokens->is_keyword("match"):
            result = AstStatement{
                location = self->tokens->location,
                kind = AstStatementKind.Match,
                match_statement = self->parse_match_statement(),
            }
        elif (
            self->tokens[0].kind == TokenKind.Name
            and self->tokens[1].is_operator(",")
            and self->tokens[2].kind == TokenKind.Name
        ):
            result = AstStatement{
                location = self->tokens->location,
                kind = AstStatementKind.DeclareLocalVar,
                local_var_declare = self->parse_first_of_multiple_local_var_declares(),
            }
        else:
            result = self->parse_oneline_statement()
            self->eat_newline()

        for t = decors_start; t < decors_end; t++:
            if t->kind == TokenKind.Decorator:
                decorate(&result, t->short_string, t->location)

        return result

    def parse_start_of_body(self) -> None:
        if not self->tokens->is_operator(":"):
            self->tokens->fail_expected_got("':' followed by a new line with more indentation")
        self->tokens++

        if self->tokens->kind != TokenKind.Newline:
            self->tokens->fail_expected_got("a new line with more indentation after ':'")
        self->tokens++

        if self->tokens->kind != TokenKind.Indent:
            self->tokens->fail_expected_got("more indentation after ':'")
        self->tokens++

    def parse_body(self) -> AstBody:
        self->parse_start_of_body()

        result: AstStatement* = NULL
        n = 0
        while self->tokens->kind != TokenKind.Dedent:
            result = realloc(result, sizeof result[0] * (n+1))
            result[n++] = self->parse_statement()
        self->tokens++

        return AstBody{ statements = result, nstatements = n }

    def parse_function_or_method(self, is_method: bool) -> AstFunctionOrMethod:
        assert self->tokens->is_keyword("def")
        self->tokens++

        signature = self->parse_function_or_method_signature(is_method)
        if strcmp(signature.name, "__init__") == 0 and is_method:
            fail(self->tokens->location, "Jou does not have a special __init__ method like Python")
        if signature.takes_varargs:
            fail(self->tokens->location, "functions with variadic arguments cannot be defined yet")

        old = self->what_are_we_parsing
        if is_method:
            self->what_are_we_parsing = WhatAreWeParsing.MethodBody
        else:
            self->what_are_we_parsing = WhatAreWeParsing.FunctionBody
        body = self->parse_body()
        self->what_are_we_parsing = old

        return AstFunctionOrMethod{ast_signature = signature, body = body}

    def parse_class(self) -> AstClassDef:
        assert self->tokens->is_keyword("class")
        self->check_top_level("classes")
        self->tokens++

        if self->tokens->kind != TokenKind.Name:
            self->tokens->fail_expected_got("a name for the class")
        name = self->tokens->short_string
        self->tokens++

        old = self->what_are_we_parsing
        self->what_are_we_parsing = WhatAreWeParsing.ClassBody
        body = self->parse_body()
        self->what_are_we_parsing = old

        bodyptr: AstBody* = malloc(sizeof(*bodyptr))
        assert bodyptr != NULL
        *bodyptr = body

        return AstClassDef{name = name, body = bodyptr}

    def parse_union(self) -> AstUnionFields:
        if self->what_are_we_parsing != WhatAreWeParsing.ClassBody:
            fail(self->tokens->location, "'union' can only be used inside a class")

        assert self->tokens->is_keyword("union")
        union_keyword_location = (self->tokens++)->location
        self->parse_start_of_body()

        result = AstUnionFields{}
        while self->tokens->kind != TokenKind.Dedent:
            field = self->parse_name_type_value("a union member")
            if field.value != NULL:
                fail(field.value->location, "union members cannot have default values")

            result.fields = realloc(result.fields, (result.nfields + 1) * sizeof result.fields[0])
            result.fields[result.nfields++] = field
            self->eat_newline()

        self->tokens++

        if result.nfields < 2:
            fail(union_keyword_location, "unions must have at least 2 members")
        return result

    def parse_enum(self) -> AstEnumDef:
        assert self->tokens->is_keyword("enum")
        self->check_top_level("enums")
        self->tokens++

        if self->tokens->kind != TokenKind.Name:
            self->tokens->fail_expected_got("a name for the enum")

        result = AstEnumDef{
            name = self->tokens->short_string,
            name_location = self->tokens->location,
        }
        self->tokens++

        self->parse_start_of_body()
        while self->tokens->kind != TokenKind.Dedent:
            if self->tokens->kind != TokenKind.Name:
                self->tokens->fail_expected_got("a name for an enum member")

            for i = 0; i < result.member_count; i++:
                if strcmp(result.member_names[i], self->tokens->short_string) == 0:
                    assert sizeof self->tokens->short_string == 100
                    error: byte[200]
                    sprintf(error, "the enum has two members named '%s'", self->tokens->short_string)
                    fail(self->tokens->location, error)

            result.member_names = realloc(result.member_names, sizeof result.member_names[0] * (result.member_count + 1))
            result.member_names[result.member_count++] = self->tokens->short_string
            self->tokens++
            self->eat_newline()

        self->tokens++
        return result

@public
def parse(tokens: Token*, stdlib_path: byte*) -> AstFile:
    parser = Parser{tokens = tokens, stdlib_path = stdlib_path}
    result = AstFile{path = tokens[0].location.path}

    while parser.tokens->kind != TokenKind.EndOfFile:
        result.body.statements = realloc(result.body.statements, sizeof result.body.statements[0] * (result.body.nstatements + 1))
        result.body.statements[result.body.nstatements++] = parser.parse_statement()

    assert parser.nloops == 0
    free(parser.loop_vars)
    return result