path: root/bootstrap/token.c

/*
 * Tokenization routines for the bootstrap compiler.
 *
 * Copyright © 2025-2026 Samuel Lidén Borell <samuel@kodafritt.se>
 *
 * SPDX-License-Identifier: EUPL-1.2+ OR LGPL-2.1-or-later
 */
#include <assert.h>
#include <string.h>
#include "compiler.h"
#include "token.h"


static FILE *f;
static char line[SOURCELINE_MAX];
static const char *s;
static const char *last_token_start;
static bool has_unread_line;
/* This is a hack (mode parameter) to be able to parse versions, without having
   to have complex multi-part tokens. However, it would be possible to turn
   remove this hack by adding two new tokens, given as regular expressions here
   (where `$` would match either the module version):

    T_WholeLineVersion:
        ^ *([0-9][-0-9a-zA-Z._+~]*) *$
    T_ModuleWithVersion:
        ^ *module *([a-zA-Z][a-zA-Z0-9_]*) (*[0-9][-0-9a-zA-Z._+~]*) *$
*/
bool tokenize_numbers_as_versions = false;

static enum Token tok_symbol(struct LexemeInfo *li_out);
static enum Token tok_alphanum(struct LexemeInfo *li_out);
static enum Token tok_number(struct LexemeInfo *li_out);
static enum Token tok_version(struct LexemeInfo *li_out);
static enum Token tok_string(struct LexemeInfo *li_out);

void tokenizer_init(FILE *file)
{
    f = file;
    s = NULL;
}

static bool line_has_contents(void)
{
    const char *p = line;
    char c;

    do {
        c = *(p++);
        if (c == '\n' || c == '\r' || c == '#') {
            return false;
        }
    } while (c == ' ' || c == '\t');
    return true;
}

bool tokenizer_next_line(void)
{
    int ignorelevel = 0;
    bool ignore_just_started = false;

    if (has_unread_line) {
        has_unread_line = false;
        return true;
    }

    if (s && *s && *s != '#') {
        error("Expected end of line");
    }
    s = line;
    last_token_start = NULL;
    /* Return first line not in an ignore block */
    for (;;) {
        /* Don't strip comments here, because '#' might appear inside strings,
           which read_source_line() doesn't know about. */
        if (!read_source_line(f, line, NULL, KEEP_COMMENTS)) {
            if (ignorelevel) {
                warning("`ignore` block not closed with `end`");
            }
            s = "";
            return false;
        }

        if (!strcmp(line, "ignore")) {
            if (ignorelevel++ > 1000) {
                error("Suspiciously deep ignore block. Aborting");
            }
            ignore_just_started = true;
        } else if (!ignorelevel && line_has_contents()) {
            return true;
        } else {
            if (!strcmp(line, "end") ||
                    /* In interfaces, there' no `end`.
                       But still allow `ignore` just before a function. */
                    (!ignore_just_started && (
                        !strncmp(line, "func ", 5) ||
                        !strncmp(line, "class ", 6)))) {
                ignorelevel--;
            }
            ignore_just_started = false;
        }
    }
}

bool tokenizer_line_is_indented(void)
{
    return line[0] == ' ' || line[0] == '\t';
}


enum Token tokenize(struct LexemeInfo *li_out)
{
    char c;

    assert(!has_unread_line);

    memset(li_out, 99, sizeof(*li_out));
    while (*s == ' ' || *s == '\t') s++;

    last_token_start = s;
    c = *s;
    if (c == '\0' || c == '#') {
        goto end_of_line;
    } else if (c <= 31 || c >= 127) {
        error("Non-ASCII (or control) character outside string/comment");
    } else if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '_') {
        return tok_alphanum(li_out);
    } else if (c >= '0' && c <= '9') {
        if (tokenize_numbers_as_versions) {
            return tok_version(li_out);
        } else {
            return tok_number(li_out);
        }
    } else if (c == '"') {
        return tok_string(li_out);
    } else {
        return tok_symbol(li_out);
    }
    unreachable();
  end_of_line:
    /* read_source_line() strips \n and \r */
    li_out->string = "";
    li_out->len = 0;
    s = "";
    return T_EOL;
}

#define DONE_1CH(token) do { t = (token); goto done_1ch; } while (0)
#define DONE_2CH(token) do { t = (token); goto done_2ch; } while (0)

static enum Token tok_symbol(struct LexemeInfo *li_out)
{
    enum Token t;
    size_t len;
    char c = *(s++);
    switch (c) {
    case '=':
        if (*s == '=') DONE_2CH(T_SYM_DoubleEqual);
        DONE_1CH(T_SYM_SingleEqual);
    case '<':
        if (*s == '>') DONE_2CH(T_SYM_NotEqual);
        if (*s == '=') DONE_2CH(T_SYM_LessEqual);
        DONE_1CH(T_SYM_Less);
    case '>':
        if (*s == '=') DONE_2CH(T_SYM_GreaterEqual);
        DONE_1CH(T_SYM_Greater);
    case '.':
        DONE_1CH(T_SYM_Dot);
    case '!':
        DONE_1CH(T_SYM_ExclMark);
    case '+':
        if (*s == '=') DONE_2CH(T_SYM_PlusEqual);
        DONE_1CH(T_SYM_Plus);
    case '-':
        if (*s == '=') DONE_2CH(T_SYM_MinusEqual);
        DONE_1CH(T_SYM_Minus);
    case '*':
        if (*s == '=') DONE_2CH(T_SYM_AsteriskEqual);
        DONE_1CH(T_SYM_Asterisk);
    case '/':
        if (*s == '=') DONE_2CH(T_SYM_SlashEqual);
        DONE_1CH(T_SYM_Slash);
    case '(':
        DONE_1CH(T_SYM_LParen);
    case ')':
        DONE_1CH(T_SYM_RParen);
    case '[':
        DONE_1CH(T_SYM_LBracket);
    case ']':
        DONE_1CH(T_SYM_RBracket);
    default:
        s--;
        error("Special character outside string/comment");
    }
    unreachable();
  done_1ch:
    len = 1;
    goto done;
  done_2ch:
    len = 2;
    s++;
    goto done;
  done:
    li_out->len = len;
    return t;
}


#define CMP_KW(length, keyword_str, keyword_const)      \
    if (memcmp(ident, keyword_str, (length)) == 0) {    \
        return keyword_const;                           \
    }

static enum Token match_keyword(const char *ident, size_t len)
{
    /* These can be checked with `make -s check-tokens`
       (included in `make check-all`) */
    switch (len) {
    case 2:
        CMP_KW(2, "if", T_KW_if)
        CMP_KW(2, "in", T_KW_in)
        CMP_KW(2, "io", T_KW_io)
        CMP_KW(2, "of", T_KW_of)
        CMP_KW(2, "or", T_KW_or)
        CMP_KW(2, "to", T_KW_to)
        break;
    case 3:
        CMP_KW(3, "and", T_KW_and)
        CMP_KW(3, "end", T_KW_end)
        CMP_KW(3, "for", T_KW_for)
        CMP_KW(3, "int", T_KW_int)
        CMP_KW(3, "mod", T_KW_mod)
        CMP_KW(3, "not", T_KW_not)
        /* XXX should there be `and`/`or`, or `all_of`/`any_of`/`none_of`?
               maybe there should be a T... safe-vararg, like in Java. */
        break;
    case 4:
        CMP_KW(4, "bool", T_KW_bool)
        CMP_KW(4, "byte", T_KW_byte)
        CMP_KW(4, "case", T_KW_case)
        CMP_KW(4, "code", T_KW_code)
        CMP_KW(4, "elif", T_KW_elif)
        CMP_KW(4, "else", T_KW_else)
        CMP_KW(4, "enum", T_KW_enum)
        CMP_KW(4, "from", T_KW_from)
        CMP_KW(4, "func", T_KW_func)
        CMP_KW(4, "long", T_KW_long)
        CMP_KW(4, "none", T_KW_none)
        CMP_KW(4, "sets", T_KW_sets)
        CMP_KW(4, "this", T_KW_this)
        CMP_KW(4, "true", T_KW_true)
        break;
    case 5:
        CMP_KW(5, "break", T_KW_break)
        CMP_KW(5, "class", T_KW_class)
        CMP_KW(5, "entry", T_KW_entry)
        CMP_KW(5, "false", T_KW_false)
        CMP_KW(5, "local", T_KW_local)
        CMP_KW(5, "reads", T_KW_reads)
        CMP_KW(5, "since", T_KW_since)
        CMP_KW(5, "trait", T_KW_trait)
        CMP_KW(5, "while", T_KW_while)
        break;
    case 6:
        CMP_KW(6, "assert", T_KW_assert)
        CMP_KW(6, "export", T_KW_export)
        CMP_KW(6, "giveme", T_KW_giveme)
        CMP_KW(6, "ignore", T_KW_ignore)
        CMP_KW(6, "record", T_KW_record)
        CMP_KW(6, "return", T_KW_return)
        CMP_KW(6, "signed", T_KW_signed)
        CMP_KW(6, "switch", T_KW_switch)
        break;
    case 7:
        CMP_KW(7, "aliased", T_KW_aliased)
        CMP_KW(7, "apihash", T_KW_apihash)
        CMP_KW(7, "default", T_KW_default)
        CMP_KW(7, "loopend", T_KW_loopend)
        CMP_KW(7, "section", T_KW_section)
        CMP_KW(7, "usetype", T_KW_usetype)
        break;
    case 8:
        CMP_KW(8, "continue", T_KW_continue)
        CMP_KW(8, "modifies", T_KW_modifies)
        CMP_KW(8, "unsigned", T_KW_unsigned)
        CMP_KW(8, "versions", T_KW_versions)
        CMP_KW(8, "volatile", T_KW_volatile)
        CMP_KW(8, "wrapping", T_KW_wrapping)
        break;
    case 9:
        CMP_KW(9, "loopempty", T_KW_loopempty)
        CMP_KW(9, "templates", T_KW_templates)
        break;
    case 10:
        CMP_KW(10, "calledfrom", T_KW_calledfrom)
        break;
    case 11:
        CMP_KW(11, "constructor", T_KW_constructor)
        break;
    }
    return 0;
}

static enum Token tok_alphanum(struct LexemeInfo *li_out)
{
    enum Token t;
    size_t len = 0;
    const char *start = s;
    char c;
    bool has_underscore = false;

    do {
        c = *(++s);
        if (c == '_') {
            if (s[-1] == '_') {
                /* Double underscores are confusing, and are also used
                   for internal identifiers. */
                error("Double underscore is not allowed in identifiers");
            }
            has_underscore = true;
        }
        len++;
    } while ((c >= 'a' && c <= 'z') ||
             (c >= 'A' && c <= 'Z') ||
             (c >= '0' && c <= '9') || c == '_');

    t = match_keyword(start, len);
    if (t) return t;

    /* No keyword matches. It's an identifier */

    li_out->len = len;
    li_out->string = start;
    if (*start == '_' && start[1] >= 'A' && start[1] <= 'Z') {
        /* These are reserved in C */
        error_token("Identifiers may not begin with `_` followed by an "
                    "uppercase letter", li_out);
    } else if (*start <= 'Z' && has_underscore) {
        /* This could lead to a duplicate name if a class is called
           `Test_do` with a function `stuff` and another class is
           called `Test` with a function `do_stuff`
           (and similarly for nested types). */
        error_token("Type names may not contain `_`", li_out);
    }
    return *start > 'Z' ? T_LowerIdent : T_UpperIdent;
}

static enum Token tok_number(struct LexemeInfo *li_out)
{
    SlulInt num = 0, limit;
    unsigned base;
    const char *num_start;

    base = 10;
    limit = 0x19999999; /* 2^32 / 10 */
    if (*s == '0') {
        switch (s[1]) {
        case 'b':
            base = 2;
            limit = 0x80000000; /* 2^32 / 2 */
            goto skip_base;
        case 'x':
            base = 16;
            limit = 0x10000000; /* 2^32 / 16 */
          skip_base:
            s += 2;
            if (*s == '_') {
                error("Leading underscore in number");
            }
            break;
        case 'B':
        case 'X':
            error("Base (`x` or `b`) must be lowercase");
        }
    }

    num_start = s;
    for (;; s++) {
        char c = *s;
        unsigned digit;
        if (c >= '0' && c <= '9') {
            digit = (unsigned)c - '0';
          have_digit:
            if (digit >= base) {
                if (base == 10 && digit == 14 /* "e" */) {
                    goto float_num;
                }
                error("Invalid digit in number");
            }
            if (num > limit) {
                error("Number too large (too many digits)");
            }
            num *= base;
            if (num > 0xFFFFFFFF - digit) {
                error("Number too large");
            }
            num += digit;
        } else if (c >= 'A' && c <= 'Z') {
            digit = 10 + (unsigned)(c - 'A');
            goto have_digit;
        } else if (c >= 'a' && c <= 'z') {
            digit = 10 + (unsigned)(c - 'a');
            goto have_digit;
        } else if (c == '.') {
          float_num:
            error("Floating point is not supported in the bootstrap compiler");
        } else if (c == '_') {
            int next = s[1];
            if (next == '_') {
                error("Repeated underscores in number");
            } else if ((next < '0' || next > '9') &&
                       (next < 'a' || next > 'z') &&
                       (next < 'A' || next > 'Z')) {
                error("Trailing `_` in number");
            }
        } else {
            break;
        }
    }
    if (s == num_start) {
        error("No digits after base prefix");
    }
    li_out->num = num;
    return T_Integer;
}

#define DOTCHARS ".~-+"

static enum Token tok_version(struct LexemeInfo *li_out)
{
    size_t len = 0;
    const char *start = s;
    char c;

    do {
        c = *(++s);
        if (c == '_' && s[-1] == '_') {
            error("Double underscore is not allowed in versions");
        } else if (c && strchr(DOTCHARS,c) && strchr(DOTCHARS,s[-1])) {
            error("Repeated .~-+ are not allowed in versions");
        }
        len++;
    } while ((c >= 'a' && c <= 'z') || /* uppercase shouldn't be needed */
             (c >= '0' && c <= '9') ||
             c == '_' || c == '.' || c == '~' || c == '-' || c == '+');

    if (len > 1 && *start == '0' && !strchr(DOTCHARS,start[1])) {
        /* But zeros in middle components are allowed, to allow for
           "calendar versions" like 2021.01.02 */
        error("Versions may not have leading zeros");
    } else if (strchr(DOTCHARS,s[-1])) {
        error("Versions may not end with .~-+");
    } else if (len > 50) {
        error("Versions may not be longer than 50 characters");
    }

    li_out->len = len;
    li_out->string = start;
    return T_Version;
}

static enum Token tok_string(struct LexemeInfo *li_out)
{
    const char *start = ++s;

    for (;;) {
        char c = *(s++);
        if (c == '\0') {
            error("Missing terminating \" of string");
        } else if (c == '"') {
            /* End of string */
            break;
        } else if (c == '\\') {
            /* Escape sequence - Handled in parser */
            if (*(s++) == '\0') {
                error("Unexpected end of string in escape sequence");
            }
        } else {
            /* Regular character */
        }
    }

    li_out->string = start;
    li_out->len = (size_t)(s - start - 1);
    return T_String;
}

void unread_token(void)
{
    assert(!has_unread_line);
    assert(last_token_start != NULL);
    s = last_token_start;
}

void unread_line(void)
{
    has_unread_line = line_has_contents(); /* false on EOF */
    s = line;
    last_token_start = NULL;
}

void expect(struct LexemeInfo *li_out, enum Token expected,
            const char *errmsg)
{
    enum Token t = tokenize(li_out);
    if (t != expected) {
        error(errmsg);
    }
}

void expect_next_line(void)
{
    if (!expect_next_line_or_eof()) {
        error("Unexpected end of file");
    }
}

bool expect_next_line_or_eof(void)
{
    struct LexemeInfo li;
    enum Token t = tokenize(&li);
    if (t != T_EOL) {
        error(t == T_SYM_SingleEqual ?
              "Assignment not possible here. Should probably be `==`" :
              "Expected line break");
    }
    return tokenizer_next_line();
}

enum IdentKind classify_ident(const struct LexemeInfo *li)
{
    return classify_ident_str(li->string, li->len);
}

enum IdentKind classify_ident_str(const char *name, size_t len)
{
    if (len == 3 && !memcmp(name, "new", 3)) {
        return IK_CONSTRUCTOR_DEFAULT;
    } else if (len >= 4 && !memcmp(name, "new_", 4)) {
        return len > 4 ? IK_CONSTRUCTOR : IK_INVALID;
    } else if (len >= 5 && !memcmp(name, "from_", 5)) {
        return len > 5 ? IK_CONSTRUCTOR : IK_INVALID;
    } else {
        return IK_NORMAL;
    }
}

enum Token lookahead_token(void)
{
    const char *saved_last_start;
    struct LexemeInfo li;
    enum Token t;

    saved_last_start = last_token_start;
    t = tokenize(&li);
    unread_token();
    last_token_start = saved_last_start;
    return t;
}