path: root/boot/tree.c

/*
 * abstract syntax tree types for a catskill source.
 */

enum Unary_Operation
{
    UNARY_NONE,

    UNARY_MINUS,
    UNARY_NOT,

    UNARY_BITWISE_NOT,
};

enum Unary_Operation
unary_operation_from_token(const struct Token* token)
{
    switch (token->kind) {
    case TOKEN_MINUS:
        return UNARY_MINUS;
    case TOKEN_NOT:
        return UNARY_NOT;
        // TODO: tilde token
        // case TOKEN_TILDE:
        //    return UNARY_BITWISE_NOT;

    default:
        return UNARY_NONE;
    }
}

const ascii*
unary_operation_to_string(enum Unary_Operation operation)
{
    switch (operation) {
    case UNARY_MINUS:
        return "-";
    case UNARY_NOT:
        return "!";
    case UNARY_BITWISE_NOT:
        return "~";

    default:
        return "unknown";
    }
}

enum Binary_Operation
{
    BINARY_NONE,

    BINARY_PLUS,
    BINARY_MINUS,
    BINARY_MULTIPLY,
    BINARY_DIVIDE,
    BINARY_MODULO,

    BINARY_EQUAL,
    BINARY_NOT_EQUAL,
    BINARY_GREATER_THAN,
    BINARY_GREATER_THAN_EQUAL,
    BINARY_LESS_THAN,
    BINARY_LESS_THAN_EQUAL,
    BINARY_AND,
    BINARY_OR,

    BINARY_BITWISE_AND,
    BINARY_BITWISE_OR,
    BINARY_BITWISE_XOR,
    BINARY_BITWISE_LEFT_SHIFT,
    BINARY_BITWISE_RIGHT_SHIFT,
};

enum Binary_Operation
binary_operation_from_token(const struct Token* token)
{
    switch (token->kind) {
    case TOKEN_PLUS:
        return BINARY_PLUS;
    case TOKEN_MINUS:
        return BINARY_MINUS;
    case TOKEN_STAR:
        return BINARY_MULTIPLY;
    case TOKEN_SLASH:
        return BINARY_DIVIDE;
        // TODO: percent token
        // case TOKEN_PERCENT:
        // return BINARY_MODULO;

    case TOKEN_EQUAL:
        return BINARY_EQUAL;
    case TOKEN_NOT_EQUAL:
        return BINARY_NOT_EQUAL;
    case TOKEN_GREATER:
        return BINARY_GREATER_THAN;
    case TOKEN_GREATER_EQUAL:
        return BINARY_GREATER_THAN_EQUAL;
    case TOKEN_LESS:
        return BINARY_LESS_THAN;
    case TOKEN_LESS_EQUAL:
        return BINARY_LESS_THAN_EQUAL;
    case TOKEN_AND:
        return BINARY_AND;
    case TOKEN_OR:
        return BINARY_OR;

    default:
        return BINARY_NONE;
    }
}

// return the precedence of the given binary operation.
// lower values are weaker, with 1 being the weakest.
// the values are taken mostly the same as other C-family languages.
uint
binary_operation_precedence(enum Binary_Operation operation)
{
    switch (operation) {
    // weakest
    case BINARY_OR:
        return 1;
    case BINARY_AND:
        return 2;
    case BINARY_BITWISE_OR:
        return 3;
    case BINARY_BITWISE_XOR:
        return 4;
    case BINARY_BITWISE_AND:
        return 5;
    case BINARY_EQUAL:
    case BINARY_NOT_EQUAL:
        return 6;
    case BINARY_GREATER_THAN:
    case BINARY_GREATER_THAN_EQUAL:
    case BINARY_LESS_THAN:
    case BINARY_LESS_THAN_EQUAL:
        return 7;
    case BINARY_BITWISE_LEFT_SHIFT:
    case BINARY_BITWISE_RIGHT_SHIFT:
        return 8;
    case BINARY_PLUS:
    case BINARY_MINUS:
        return 9;
    case BINARY_MULTIPLY:
    case BINARY_DIVIDE:
    case BINARY_MODULO:
        return 10;
        // strongest

    default:
        return 0;
    }
}

enum Binary_Operation_Associativity
{
    BINARY_ASSOCIATIVITY_NONE,
    BINARY_ASSOCIATIVITY_LEFT,
    BINARY_ASSOCIATIVITY_RIGHT,
};

enum Binary_Operation_Associativity
binary_operation_associativity(enum Binary_Operation operation)
{
    // all operations are left associative by default.
    return BINARY_ASSOCIATIVITY_LEFT;
}

const ascii*
binary_operation_to_string(enum Binary_Operation operation)
{
    switch (operation) {
    case BINARY_PLUS:
        return "+";
    case BINARY_MINUS:
        return "-";
    case BINARY_MULTIPLY:
        return "*";
    case BINARY_DIVIDE:
        return "/";
    case BINARY_MODULO:
        return "%";

    case BINARY_EQUAL:
        return "==";
    case BINARY_NOT_EQUAL:
        return "!=";
    case BINARY_GREATER_THAN:
        return ">";
    case BINARY_GREATER_THAN_EQUAL:
        return ">=";
    case BINARY_LESS_THAN:
        return "<";
    case BINARY_LESS_THAN_EQUAL:
        return "<=";
    case BINARY_AND:
        return "&&";
    case BINARY_OR:
        return "||";

    case BINARY_BITWISE_AND:
        return "&";
    case BINARY_BITWISE_OR:
        return "|";
    case BINARY_BITWISE_XOR:
        return "^";
    case BINARY_BITWISE_LEFT_SHIFT:
        return "<<";
    case BINARY_BITWISE_RIGHT_SHIFT:
        return ">>";

    default:
        return "unknown";
    }
}

enum Expression_Kind
{
    EXPRESSION_NONE,

    EXPRESSION_INTEGER_LITERAL,
    EXPRESSION_FLOAT_LITERAL,
    EXPRESSION_STRING_LITERAL,
    EXPRESSION_BOOLEAN_LITERAL,
    EXPRESSION_NAME,

    EXPRESSION_UNARY_OPERATION,
    EXPRESSION_BINARY_OPERATION,

    EXPRESSION_GROUP,
    EXPRESSION_CALL,
    EXPRESSION_SUBSCRIPT,
    EXPRESSION_MEMBER,
};

struct Expression_Integer_Literal
{
    int64 value; // might not fit entire number given in source.
};

struct Expression_Float_Literal
{
    float64 value;
};

struct Expression_String_Literal
{
    struct String value;
};

struct Expression_Bool_Literal
{
    bool value;
};

struct Expression_Name
{
    struct String name;
};

struct Expression_Unary_Operator
{
    enum Unary_Operation operation;
    struct Expression* operand;
};

struct Expression_Binary_Operator
{
    enum Binary_Operation operation;
    struct Expression* left_operand;
    struct Expression* right_operand;
};

struct Expression_Group
{
    struct Expression* inner_expression;
};

struct Expression_Call
{
    struct Expression* subject;
    struct Expression* arguments; // linked list of expressions.
};

struct Expression_Subscript
{
    struct Expression* subject;
    struct Expression* index;
};

struct Expression_Member
{
    struct Expression* subject;
    struct String name;
};

union Expression_Value
{
    struct Expression_Integer_Literal integer_literal;
    struct Expression_Float_Literal float_literal;
    struct Expression_String_Literal string_literal;
    struct Expression_Bool_Literal bool_literal;
    struct Expression_Name name;
    struct Expression_Unary_Operator unary_operator;
    struct Expression_Binary_Operator binary_operator;
    struct Expression_Group group;
    struct Expression_Call call;
    struct Expression_Subscript subscript;
    struct Expression_Member member;
};

struct Expression
{
    enum Expression_Kind kind;
    union Expression_Value value;

    struct Span span;
    struct Cursor location;

    // if expression is within a group of multiple expressions,
    // points to the next expression within it.
    struct Expression* next;
};

REGION(struct Expression, expression)

struct Expression*
expression_new(
    enum Expression_Kind kind, union Expression_Value value, struct Span span,
    struct Cursor location)
{
    check(region_expression_cursor < REGION_SIZE, "out of expression memory");
    struct Expression* expression = &region_expression[region_expression_cursor++];
    *expression = (struct Expression){
        .kind = kind,
        .value = value,
        .span = span,
        .location = location,
        .next = nil,
    };
    return expression;
}

void
expression_print(const struct Expression* expression)
{
    printf("(expr ");
    switch (expression->kind) {
    case EXPRESSION_NONE:
        printf("none");
        break;
    case EXPRESSION_INTEGER_LITERAL:
        printf("%ld", expression->value.integer_literal.value);
        break;
    case EXPRESSION_FLOAT_LITERAL:
        printf("%lf", expression->value.float_literal.value);
        break;
    case EXPRESSION_STRING_LITERAL:
        printf("\"%s\"", expression->value.string_literal.value.data);
        break;
    case EXPRESSION_BOOLEAN_LITERAL:
        printf("%s", expression->value.bool_literal.value ? "true" : "false");
        break;
    case EXPRESSION_NAME:
        printf("(name %s)", expression->value.name.name.data);
        break;
    case EXPRESSION_UNARY_OPERATION:
        printf("(unary %s ", unary_operation_to_string(expression->value.unary_operator.operation));
        expression_print(expression->value.unary_operator.operand);
        printf(")");
        break;
    case EXPRESSION_BINARY_OPERATION:
        printf(
            "(binary %s ", binary_operation_to_string(expression->value.binary_operator.operation));
        expression_print(expression->value.binary_operator.left_operand);
        printf(" ");
        expression_print(expression->value.binary_operator.right_operand);
        printf(")");
        break;
    case EXPRESSION_GROUP:
        printf("(group ");
        expression_print(expression->value.group.inner_expression);
        printf(")");
        break;
    case EXPRESSION_CALL:
        printf("(call ");
        expression_print(expression->value.call.subject);
        FOR_EACH(struct Expression*, argument, expression->value.call.arguments)
        {
            printf(" ");
            expression_print(argument);
        }
        printf(")");
        break;
    case EXPRESSION_SUBSCRIPT:
        printf("(subscript ");
        expression_print(expression->value.subscript.subject);
        printf(" ");
        expression_print(expression->value.subscript.index);
        printf(")");
        break;
    case EXPRESSION_MEMBER:
        printf("(member ");
        expression_print(expression->value.member.subject);
        printf(")");
        break;
    default:
        break;
    }
    printf(")");
}

enum Statement_Kind
{
    STATEMENT_NONE,
    STATEMENT_EXPRESSION,
};

union Statement_Value
{
    struct Expression* expression;
};

struct Statement
{
    enum Statement_Kind kind;
    union Statement_Value value;

    struct Span span;
    struct Cursor location;

    // if statement is within a group of multiple statements,
    // points to the next statement within it.
    struct Statement* next;
};

REGION(struct Statement, statement)

struct Statement*
statement_new(
    enum Statement_Kind kind, union Statement_Value value, struct Span span, struct Cursor location)
{
    check(region_statement_cursor < REGION_SIZE, "out of statement memory");
    struct Statement* statement = &region_statement[region_statement_cursor++];
    *statement = (struct Statement){
        .kind = kind,
        .value = value,
        .span = span,
        .location = location,
        .next = nil,
    };
    return statement;
}

void
statement_print(const struct Statement* statement)
{
    printf("(stmt ");
    switch (statement->kind) {
    case STATEMENT_NONE:
        printf("none");
        break;
    case STATEMENT_EXPRESSION: {
        const struct Expression* expression = statement->value.expression;
        expression_print(expression);
        break;
    }
    default:
        printf("unknown");
        break;
    }
    printf(")");
}

// the top-level tree of a single catskill source file.
struct Tree
{
    struct Statement* top_level_statements;
};

void
tree_print(const struct Tree* tree)
{
    FOR_EACH(struct Statement*, statement, tree->top_level_statements)
    {
        statement_print(statement);
        printf("\n");
    }
}