tok.h

Go to the documentation of this file.

#pragma once
 
#include <optional>
#include <string_view>
#include <utility>
 
#include <fe/assert.h>
#include <fe/format.h>
 
#include "mim/util/dbg.h"
 
namespace mim {
 
class Def;
 
namespace ast {
 
/// @name Precedence Table
/// X-macro listing all expression precedences from lowest to highest as `m(name, assoc)`.
/// @p assoc is `L`eft-, `R`ight-, or `N`on-associative; `a op b op c` is an error for an `N` level.
/// Only a level named by MIM_INFIX or by an entry below is an actual operator:
/// `Err`, `Bot`, `Pi`, and `Lit` merely serve as a `curr_prec` bound while parsing.
/// Application binds tighter than every operator - only `Extract` and `Lit` bind tighter still.
///@{
// clang-format off
#define MIM_PREC(m)     \
    m(Err,     N)       \
    m(Bot,     N)       \
    m(Where,   L)       \
    m(Ins,     R)       \
    m(Inj,     R)       \
    m(Union,   L)       \
    m(Arrow,   R)       \
    m(Pi,      N)       \
    m(Eq,      N)       \
    m(Rel,     N)       \
    m(Add,     L)       \
    m(Mul,     L)       \
    m(Shift,   L)       \
    m(App,     L)       \
    m(Extract, L)       \
    m(Lit,     N)
// clang-format on
///@}
 
/// Associativity of an infix expression.
enum class Assoc { N, L, R };
 
/// Expression precedences used by the parser and the dumper; ordered low to high.
enum class Prec {
#define CODE(name, ...) name,
    MIM_PREC(CODE)
#undef CODE
};
 
/// Associativity of precedence level @p p.
constexpr Assoc prec_assoc(Prec p) {
    switch (p) {
#define CODE(name, assoc) \
    case Prec::name: return Assoc::assoc;
        MIM_PREC(CODE)
#undef CODE
    }
    fe::unreachable();
}
 
constexpr bool is_rassoc(Prec p) { return prec_assoc(p) == Assoc::R; }
constexpr bool is_lassoc(Prec p) { return prec_assoc(p) == Assoc::L; }
 
/// Should a Pratt parser reduce when the current binding power is @p curr
/// and the infix operator has precedence @p op?
constexpr bool should_reduce(Prec curr, Prec op) { return is_rassoc(op) ? curr > op : curr >= op; }
 
// clang-format off
#define MIM_KEY(m)                    \
    m(K_Bool,   "Bool"  )             \
    m(K_Cn,     "Cn"    )             \
    m(K_Fn,     "Fn"    )             \
    m(K_I1,     "I1"    )             \
    m(K_I16,    "I16"   )             \
    m(K_I32,    "I32"   )             \
    m(K_I64,    "I64"   )             \
    m(K_I8,     "I8"    )             \
    m(K_Idx,    "Idx"   )             \
    m(K_Nat,    "Nat"   )             \
    m(K_Type,   "Type"  )             \
    m(K_Univ,   "Univ"  )             \
    m(K_and,    "and"   )             \
    m(K_anx,    "anx"   )             \
    m(K_as,     "as"    )             \
    m(K_axm,    "axm"   )             \
    m(K_cn,     "cn"    )             \
    m(K_con,    "con"   )             \
    m(K_end,    "end"   )             \
    m(K_extern, "extern")             \
    m(K_ff,     "ff"    )             \
    m(K_fn,     "fn"    )             \
    m(K_fun,    "fun"   )             \
    m(K_i1,     "i1"    )             \
    m(K_i16,    "i16"   )             \
    m(K_i32,    "i32"   )             \
    m(K_i64,    "i64"   )             \
    m(K_i8,     "i8"    )             \
    m(K_import, "import")             \
    m(K_inj,    "inj"   )             \
    m(K_lam,    "lam"   )             \
    m(K_let,    "let"   )             \
    m(K_match,  "match" )             \
    m(K_mod,    "mod"   )             \
    m(K_norm,   "norm"  )             \
    m(K_plugin, "plugin")             \
    m(K_priv,   "priv"  )             \
    m(K_pub,    "pub"   )             \
    m(K_rec,    "rec"   )             \
    m(K_ret,    "ret"   )             \
    m(K_rule,   "rule"  )             \
    m(K_Rule,   "Rule"  )             \
    m(K_tt,     "tt"    )             \
    m(K_use,    "use"   )             \
    m(K_when,   "when"  )             \
    m(K_where,  "where" )             \
    m(K_with,   "with"  )             \
 
#define CODE(t, str) + size_t(1)
constexpr auto Num_Keys = size_t(0) MIM_KEY(CODE);
#undef CODE
 
#define MIM_TOK(m)                     \
    m(EoF, "<end of file>"    )        \
    /* literals */                     \
    m(L_s, "<signed integer literal>") \
    m(L_u, "<integer literal>"       ) \
    m(L_i, "<index literal>"         ) \
    m(L_f, "<floating-point literal>") \
    m(L_c, "<char literal>"          ) \
    m(L_str,  "<string literal>"     ) \
    /* misc */                         \
    m(M_id,   "<identifier>"  )        \
    /* delimiters */                   \
    m(D_angle_l,    "‹")               \
    m(D_angle_r,    "›")               \
    m(D_brace_l,    "{")               \
    m(D_brace_r,    "}")               \
    m(D_brckt_l,    "[")               \
    m(D_brckt_r,    "]")               \
    m(D_curly_l,    "⦃")               \
    m(D_curly_r,    "⦄")               \
    m(D_paren_l,    "(")               \
    m(D_paren_r,    ")")               \
    m(D_quote_l,    "«")               \
    m(D_quote_r,    "»")               \
    /* further tokens */               \
    m(T_add,        "+")               \
    m(T_arrow_r,      "→")               \
    m(T_fat_arrow, "=>")               \
    m(T_assign,     "=")               \
    m(T_at,         "@")               \
    m(T_bot,        "⊥")               \
    m(T_top,        "⊤")               \
    m(T_box,        "□")               \
    m(T_colon,      ":")               \
    m(T_comma,      ",")               \
    m(T_div,        "/")               \
    m(T_dollar,     "$")               \
    m(T_dot,        ".")               \
    m(T_eq,         "==")              \
    m(T_extract,    "#")               \
    m(T_ge,         ">=")              \
    m(T_gt,         ">")               \
    m(T_arrow_l,    "←")               \
    m(T_le,         "<=")              \
    m(T_lm,         "λ")               \
    m(T_lt,         "<")               \
    m(T_ne,         "!=")              \
    m(T_rem,        "%")               \
    m(T_semicolon,  ";")               \
    m(T_shl,        "<<")              \
    m(T_shr,        ">>")              \
    m(T_star,       "*")               \
    m(T_sub,        "-")               \
    m(T_union,      "∪")               \
    m(T_pipe,       "|")               \
 
/// @name Infix Operator Table
/// X-macros listing all infix operators as `m(tag, str, prec)`.
///@{
 
/// `a str b` is sugar for `` `str (a, b) ``; what `` `str `` means is up to whatever the user binds it to.
#define MIM_INFIX_SUGAR(m)  \
    m(T_eq,   "==", Eq   )  \
    m(T_ne,   "!=", Eq   )  \
    m(T_lt,   "<",  Rel  )  \
    m(T_le,   "<=", Rel  )  \
    m(T_gt,   ">",  Rel  )  \
    m(T_ge,   ">=", Rel  )  \
    m(T_shl,  "<<", Shift)  \
    m(T_shr,  ">>", Shift)  \
    m(T_add,  "+",  Add  )  \
    m(T_sub,  "-",  Add  )  \
    m(T_star, "*",  Mul  )  \
    m(T_div,  "/",  Mul  )  \
    m(T_rem,  "%",  Mul  )
 
/// These have a meaning of their own; InfixExpr::emit_ dispatches on the tag.
#define MIM_INFIX_CORE(m)         \
    m(T_extract,  "#",   Extract) \
    m(T_union,    "∪",   Union  ) \
    m(K_inj,      "inj", Inj    ) \
    m(T_arrow_r,  "→",   Arrow  ) \
    m(T_arrow_l,  "←",   Ins    ) \
    m(T_at,       "@",   App    )
 
#define MIM_INFIX(m) MIM_INFIX_SUGAR(m) MIM_INFIX_CORE(m)
///@}
 
#define MIM_SUBST(m)                  \
    m("lm",     T_lm   )              \
    m("bot",    T_bot  )              \
    m("top",    T_top  )              \
 
#define CODE(str, t) + size_t(1)
constexpr auto Num_Subst = size_t(0) MIM_SUBST(CODE);
#undef CODE
 
class Tok {
public:
    /// @name Tag
    ///@{
    enum class Tag {
        Nil,
#define CODE(t, str) t,
        MIM_KEY(CODE) MIM_TOK(CODE)
#undef CODE
    };
 
    static const char* tag2str(Tok::Tag);
    /// Is @p tag something the keyword table yields? MIM_KEY occupies `[1, Num_Keys]`; MIM_SUBST adds a few more.
    static constexpr bool is_key(Tag tag) {
        if (tag == Tag::Nil) return false;
        if (size_t(tag) <= Num_Keys) return true;
        switch (tag) {
#define CODE(str, t) case Tag::t:
            MIM_SUBST(CODE)
#undef CODE
            return true;
            default: return false;
        }
    }
    /// Precedence of the infix operator @p tag; `std::nullopt` if @p tag isn't one.
    static constexpr std::optional<Prec> infix_prec(Tag tag) {
        switch (tag) {
#define CODE(t, str, prec) \
    case Tag::t: return Prec::prec;
            MIM_INFIX(CODE)
#undef CODE
            default: return {};
        }
    }
    /// Name the infix operator @p tag desugars to - including the leading `` ` ``; empty for MIM_INFIX_CORE.
    static constexpr std::string_view infix_sym(Tag tag) {
        switch (tag) {
#define CODE(t, str, prec) \
    case Tag::t: return "`" str;
            MIM_INFIX_SUGAR(CODE)
#undef CODE
            default: return {};
        }
    }
    static constexpr Tok::Tag delim_l2r(Tag tag) { return Tok::Tag(int(tag) + 1); }
    static constexpr bool is_delim_r(Tag tag) {
        return Tag::D_angle_l <= tag && tag <= Tag::D_quote_r && (int(tag) - int(Tag::D_angle_l)) % 2 == 1;
    }
    ///@}
 
    // clang-format on
 
    Tok() {}
    Tok(Loc loc, Tag tag)
        : loc_(loc)
        , tag_(tag) {}
    Tok(Loc loc, char8_t c)
        : loc_(loc)
        , tag_(Tag::L_c)
        , c_(c) {}
    Tok(Loc loc, uint64_t u)
        : loc_(loc)
        , tag_(Tag::L_u)
        , u_(u) {}
    Tok(Loc loc, int64_t s)
        : loc_(loc)
        , tag_(Tag::L_s)
        , u_(std::bit_cast<uint64_t>(s)) {}
    Tok(Loc loc, double d)
        : loc_(loc)
        , tag_(Tag::L_f)
        , u_(std::bit_cast<uint64_t>(d)) {}
    /// @p size and @p val of an Idx literal; World::lit_idx makes a Lit of it at emit time.
    Tok(Loc loc, uint64_t size, uint64_t val)
        : loc_(loc)
        , tag_(Tag::L_i)
        , idx_{size, val} {}
    Tok(Loc loc, Tag tag, Sym sym)
        : loc_(loc)
        , tag_(tag)
        , sym_(sym) {
        assert(has_sym() || is_key(tag));
    }
 
    bool isa(Tag tag) const { return tag == tag_; }
    Tag tag() const { return tag_; }
    bool has_sym() const { return isa(Tag::M_id) || isa(Tag::L_str); }
    /// @note A failed Parser::expect yields a Nil Tok; its Dbg is anonymous instead of asserting in Tok::sym.
    Dbg dbg() const { return {loc(), has_sym() ? sym_ : Sym()}; }
    Loc loc() const { return loc_; }
    explicit operator bool() const { return tag_ != Tag::Nil; }
    // clang-format off
    std::pair<uint64_t, uint64_t> lit_i() const { assert(isa(Tag::L_i)); return {idx_.size, idx_.val}; }
    char8_t    lit_c() const { assert(isa(Tag::L_c)); return c_;   }
    uint64_t   lit_u() const { assert(isa(Tag::L_u ) || isa(Tag::L_s ) || isa(Tag::L_f  )); return u_;   }
    Sym        sym()   const { assert(has_sym()); return sym_; }
    // clang-format on
    std::string str() const;
 
    friend std::ostream& operator<<(std::ostream&, Tok);
    friend std::ostream& operator<<(std::ostream& os, Tok::Tag tag) { return os << tag2str(tag); }
 
private:
    Loc loc_;
    Tag tag_ = Tag::Nil;
    union {
        Sym sym_ = {};
        uint64_t u_;
        char8_t c_;
        struct {
            uint64_t size, val;
        } idx_;
    };
};
 
} // namespace ast
} // namespace mim
 
#ifndef DOXYGEN // clang-format off
template<> struct std::formatter<mim::ast::Tok     > : fe::ostream_formatter {};
template<> struct std::formatter<mim::ast::Tok::Tag> : fe::ostream_formatter {};
#endif // clang-format on