lexer.cpp

#include <sstream>

#include <doctest/doctest.h>
#include <fe/driver.h>
#include <fe/lexer.h>
#include <fe/loc.cpp.h>
#include <fe/parser.h>

using fe::Loc;
using fe::Pos;
using fe::Sym;

namespace utf8 = fe::utf8;

// clang-format off
#define LET_KEY(m)          \
    m(K_let, "let")         \
    m(K_return, "return")

#define LET_MISC(m)         \
    m(M_id, "<identifier>") \
    m(M_lit, "<literal>")

#define LET_TOK(m)          \
    m(D_paren_l, "(")       \
    m(D_paren_r, ")")       \
    m(D_quote_l, "«")       \
    m(D_quote_r, "»")       \
    m(T_semicolon, ";")     \
    m(T_lambda, "λ")        \
    m(EoF, "<end of file>")

#define LET_OP(m)            \
    m(O_add, "+", Add, true) \
    m(O_sub, "-", Add, true) \
    m(O_mul, "*", Mul, true) \
    m(O_div, "/", Mul, true) \
    m(O_ass, "=", ASS, false)
// clang-format on

class Tok {
public:
    enum Tag {
        Nil,
#define CODE(t, str) t,
        LET_KEY(CODE) LET_MISC(CODE) LET_TOK(CODE)
#undef CODE
#define CODE(t, str, prec, left_assoc) t,
            LET_OP(CODE)
#undef CODE
    };

    enum Prec { Err, Bot, Ass, Add, Mul };

    Tok() {}
    Tok(Loc loc, Tag tag)
        : loc_(loc)
        , tag_(tag) {}
    Tok(Loc loc, Sym sym)
        : loc_(loc)
        , tag_(Tag::M_id)
        , sym_(sym) {}
    Tok(Loc loc, uint64_t u64)
        : loc_(loc)
        , tag_(Tag::M_lit)
        , u64_(u64) {}

    Tag tag() const { return tag_; }
    Loc loc() const { return loc_; }
    explicit operator bool() const { return tag_ != Tag::Nil; }

    static const char* tag2str(Tag tag) {
        switch (tag) {
#define CODE(t, str) \
    case Tok::Tag::t: return str;
            LET_KEY(CODE)
            LET_TOK(CODE)
            LET_MISC(CODE)
#undef CODE
#define CODE(t, str, prec, left_assoc) \
    case Tok::Tag::t: return str;
            LET_OP(CODE)
#undef CODE
            default: fe::unreachable();
        }
    }

    std::string to_string() const {
        if (tag_ == M_id) return sym_.str();
        if (tag_ == M_lit) return std::to_string(u64_);
        return tag2str(tag_);
    }

    friend std::ostream& operator<<(std::ostream& os, Tok tok) { return os << tok.to_string(); }

private:
    Loc loc_;
    Tag tag_ = Tag::Nil;
    union {
        Sym sym_;
        uint64_t u64_;
    };
};

template<>
struct std::formatter<Tok> : fe::ostream_formatter {};

template<size_t K = 1>
class Lexer : public fe::Lexer<K, Lexer<K>> {
public:
    using fe::Lexer<K, Lexer<K>>::ahead;
    using fe::Lexer<K, Lexer<K>>::accept;
    using fe::Lexer<K, Lexer<K>>::next;

    using fe::Lexer<K, Lexer<K>>::loc_;
    using fe::Lexer<K, Lexer<K>>::peek_;
    using fe::Lexer<K, Lexer<K>>::str_;

    Lexer(fe::Driver& driver, std::istream& istream, const std::filesystem::path* path = nullptr)
        : fe::Lexer<K, Lexer<K>>(istream, path)
        , driver_(driver) {}

    Tok lex() {
        while (true) {
            this->start();

            if (accept(utf8::Invalid)) {
                std::cerr << "invalid UTF-8 sequence" << std::endl;
                continue;
            }

            if (accept(utf8::EoF)) return {loc_, Tok::Tag::EoF};
            if (accept(utf8::isspace)) continue;

            if (accept('(')) return {loc_, Tok::Tag::D_paren_l};
            if (accept(')')) return {loc_, Tok::Tag::D_paren_r};
            if (accept(U'«')) return {loc_, Tok::Tag::D_quote_l};
            if (accept(U'»')) return {loc_, Tok::Tag::D_quote_r};

            if (accept('+')) return {loc_, Tok::Tag::O_add};
            if (accept('-')) return {loc_, Tok::Tag::O_sub};
            if (accept('*')) return {loc_, Tok::Tag::O_mul};
            if (accept('/')) return {loc_, Tok::Tag::O_div};
            if (accept('=')) return {loc_, Tok::Tag::O_ass};

            if (accept(';')) return {loc_, Tok::Tag::T_semicolon};

            if (accept(U'λ')) return {loc_, Tok::Tag::T_lambda};

            if (accept([](char32_t c) { return c == '_' || utf8::isalpha(c); })) {
                while (accept([](char32_t c) { return c == '_' || c == '.' || utf8::isalnum(c); })) {}
                return {loc_, driver_.sym(str_)};
            }

            if (accept(utf8::isdigit)) {
                while (accept(utf8::isdigit)) {}
                auto u = strtoull(str_.c_str(), nullptr, 10);
                return {loc_, u};
            }

            driver_.err(peek_, "invalid input character: ''{}'", utf8::Char32(ahead()));
            next();
        }
    }

private:
    fe::Driver& driver_;
};

/// Minimal precedence-climbing expression parser, mirroring the intended `fe::Parser` usage in the
/// sister `let` project: derive via CRTP, expose `lexer()`, provide `syntax_err`, drive the parse with
/// the inherited `tracker`/`ahead`/`accept`/`expect`/`eat`/`lex` helpers.
/// `parse` returns the expression as an s-expression string so precedence/associativity are easy to check.
template<size_t K = 1>
class Parser : public fe::Parser<Tok, Tok::Tag, K, Parser<K>> {
public:
    using Super = fe::Parser<Tok, Tok::Tag, K, Parser<K>>;
    using Super::accept;
    using Super::ahead;
    using Super::curr_;
    using Super::eat;
    using Super::expect;
    using Super::lex;
    using Super::tracker;

    Parser(fe::Driver& driver, std::istream& istream, const std::filesystem::path* path = nullptr)
        : driver_(driver)
        , lexer_(driver, istream, path) {
        this->init(path); // fill lookahead; must run after lexer_ is constructed
    }

    Lexer<K>& lexer() { return lexer_; }
    fe::Driver& driver() { return driver_; }

    /// Parse one whole expression and return {s-expression string, its Loc}.
    std::pair<std::string, Loc> parse() {
        auto track = tracker();
        auto str   = parse_expr("expression", Tok::Bot);
        expect(Tok::Tag::EoF, "expression");
        return {str, track.loc()};
    }

    void syntax_err(Tok::Tag tag, std::string_view ctxt) {
        driver_.err(ahead().loc(), "expected '{}' while parsing {}", Tok::tag2str(tag), ctxt);
    }

private:
    // clang-format off
    static Tok::Prec bin_prec(Tok::Tag t) {
        switch (t) {
            case Tok::O_add: case Tok::O_sub: return Tok::Add;
            case Tok::O_mul: case Tok::O_div: return Tok::Mul;
            case Tok::O_ass:                  return Tok::Ass;
            default:                          return Tok::Err;
        }
    }
    // clang-format on
    static bool left_assoc(Tok::Tag t) { return t != Tok::O_ass; } // '=' is right-associative

    std::string parse_primary(std::string_view ctxt) {
        if (auto tok = accept(Tok::Tag::M_id)) return tok.to_string();
        if (auto tok = accept(Tok::Tag::M_lit)) return tok.to_string();
        if (accept(Tok::Tag::D_paren_l)) {
            auto str = parse_expr("parenthesized expression", Tok::Bot);
            expect(Tok::Tag::D_paren_r, "parenthesized expression");
            return str;
        }
        syntax_err(Tok::Tag::M_id, ctxt);
        return "<error>";
    }

    std::string parse_expr(std::string_view ctxt, Tok::Prec curr_prec) {
        auto lhs = parse_primary(ctxt);
        while (true) {
            auto tag  = ahead().tag();
            auto prec = bin_prec(tag);
            if (prec <= curr_prec) break;
            auto op   = lex(); // consume the operator
            auto next = left_assoc(tag) ? prec : Tok::Prec(prec - 1);
            auto rhs  = parse_expr("right-hand side", next);
            lhs       = std::format("({} {} {})", op.to_string(), lhs, rhs);
        }
        return lhs;
    }

    friend Super;
    fe::Driver& driver_;
    Lexer<K> lexer_;
};

template<size_t K>
void test_parser() {
    auto parse = [](std::string_view src) {
        fe::Driver drv;
        std::istringstream is{std::string(src)};
        Parser<K> parser(drv, is);
        auto [str, loc] = parser.parse();
        return std::tuple{str, loc, drv.num_errors()};
    };

    // precedence
    CHECK(std::get<0>(parse("a + b * c")) == "(+ a (* b c))");
    CHECK(std::get<0>(parse("a * b + c")) == "(+ (* a b) c)");
    // left associativity of +,-,*,/
    CHECK(std::get<0>(parse("a - b - c")) == "(- (- a b) c)");
    CHECK(std::get<0>(parse("a / b / c")) == "(/ (/ a b) c)");
    // right associativity of '='
    CHECK(std::get<0>(parse("a = b = c")) == "(= a (= b c))");
    // parentheses override precedence
    CHECK(std::get<0>(parse("(a + b) * c")) == "(* (+ a b) c)");
    // literals
    CHECK(std::get<0>(parse("1 + 2 * 3")) == "(+ 1 (* 2 3))");

    // no errors on the well-formed inputs above
    CHECK(std::get<2>(parse("a + b * c")) == 0);

    // Tracker spans from the first to the last token of the expression.
    {
        auto [str, loc, errs] = parse("a + b");
        CHECK(str == "(+ a b)");
        CHECK(errs == 0);
        CHECK(loc == Loc({1, 1}, {1, 5}));
    }

    // expect() reports a syntax error on a missing ')'
    CHECK(std::get<2>(parse("(a + b")) == 1);
    // parse_primary reports an error when no primary is found
    CHECK(std::get<2>(parse("a +")) == 1);
}

TEST_CASE("Parser") {
    test_parser<1>();
    test_parser<2>();
    test_parser<3>();
}

template<size_t K>
void test_lexer() {
    fe::Driver drv;
    std::istringstream is(" test  abc    def if  \nwhile λ foo «n; X»  ");
    Lexer lexer(drv, is);

    auto t1 = lexer.lex();
    auto t2 = lexer.lex();
    auto t3 = lexer.lex();
    auto t4 = lexer.lex();
    auto t5 = lexer.lex();
    auto t6 = lexer.lex();
    auto t7 = lexer.lex();
    auto t8 = lexer.lex();
    auto t9 = lexer.lex();
    auto t0 = lexer.lex();
    auto ta = lexer.lex();
    auto tb = lexer.lex();
    auto tc = lexer.lex();
    auto td = lexer.lex();
    auto s  = std::format("{} {} {} {} {} {} {} {} {} {} {} {} {} {}", t1, t2, t3, t4, t5, t6, t7, t8, t9, t0, ta, tb,
                          tc, td);
    CHECK(s == "test abc def if while λ foo « n ; X » <end of file> <end of file>");

    // clang-format off
    CHECK(t1.loc() == Loc({1,  2}, {1,  5})); // test
    CHECK(t2.loc() == Loc({1,  8}, {1, 10})); // abc
    CHECK(t3.loc() == Loc({1, 15}, {1, 17})); // def
    CHECK(t4.loc() == Loc({1, 19}, {1, 20})); // if
    CHECK(t5.loc() == Loc({2,  1}, {2,  5})); // while
    CHECK(t6.loc() == Loc({2,  7}, {2,  7})); // λ
    CHECK(t7.loc() == Loc({2,  9}, {2, 11})); // foo
    CHECK(t8.loc() == Loc({2, 13}, {2, 13})); // «
    CHECK(t9.loc() == Loc({2, 14}, {2, 14})); // n
    CHECK(t0.loc() == Loc({2, 15}, {2, 15})); // ;
    CHECK(ta.loc() == Loc({2, 17}, {2, 17})); // X
    CHECK(tb.loc() == Loc({2, 18}, {2, 18})); // »
    CHECK(tc.loc() == Loc({2, 20}, {2, 20})); // <end of file>
    CHECK(td.loc() == Loc({2, 20}, {2, 20})); // <end of file>
    // clang-format on
}

TEST_CASE("Lexer") {
    test_lexer<1>();
    test_lexer<2>();
    test_lexer<3>();
}