sym.h

Go to the documentation of this file.

#pragma once
 
#include <cassert>
#include <concepts>
 
#include <array>
#include <bit>
#include <iosfwd>
#include <optional>
#include <string>
 
#ifdef FE_ABSL
#    include <absl/container/flat_hash_map.h>
#    include <absl/container/flat_hash_set.h>
#    include <absl/hash/hash.h>
#else
#    include <unordered_map>
#    include <unordered_set>
#endif
 
#include "fe/arena.h"
#include "fe/hash.h"
 
namespace fe {
 
/// A Sym%bol just wraps a pointer to Sym::String, so pass Sym itself around as value.
/// Retrieving a `std::string_view` (via Sym::view) is basically free.
/// You can also obtain a `std::string` (via Sym::str), but this involves a copy.
/// The characters are *not* null-terminated.
/// With the exception of the empty string, you should only create Sym%bols via SymPool::sym.
/// This in turn will toss all Sym%bols into a big hash set.
/// This makes Sym::operator== and Sym::operator!= an O(1) operation.
/// The empty string is internally handled as `nullptr`.
/// Thus, you can create a Sym%bol representing an empty string without having access to the SymPool.
/// @note The empty `std::string`/`std::string_view` and `nullptr` are all identified as Sym::Sym().
/// @warning Big endian version has not been tested.
class Sym {
public:
    static constexpr size_t Short_String_Bytes = sizeof(uintptr_t);
    static constexpr size_t Short_String_Mask  = Short_String_Bytes - 1;
 
    struct String {
        constexpr String() noexcept = default;
        constexpr String(size_t size) noexcept
            : size(size) {}
 
        size_t size = 0;
        char chars[]; // This is actually a C-only feature, but all C++ compilers support that anyway.
 
        struct Equal {
            constexpr bool operator()(const String* s1, const String* s2) const noexcept {
                bool res = s1->size == s2->size;
                for (size_t i = 0, e = s1->size; res && i != e; ++i)
                    res &= s1->chars[i] == s2->chars[i];
                return res;
            }
        };
 
        /// Hashes the characters, not the pointer - String::Equal compares them, and the two have to agree.
        struct Hash {
            size_t operator()(const String* s) const noexcept {
                auto sv = std::string_view(s->chars, s->size);
#ifdef FE_ABSL
                return absl::HashOf(sv); // a few percent ahead of ours, and we link it anyway
#else
                return hash_begin(sv);
#endif
            }
        };
    };
 
    static_assert(sizeof(String) == sizeof(size_t), "String.chars should be 0");
 
private:
    constexpr Sym(uintptr_t ptr) noexcept
        : ptr_(ptr) {}
 
public:
    constexpr Sym() noexcept = default;
 
    /// @name Getters
    ///@{
    [[nodiscard]] constexpr bool empty() const noexcept { return ptr_ == 0; }
    [[nodiscard]] constexpr size_t size() const noexcept {
        if (empty()) return 0;
        if (auto size = ptr_ & Short_String_Mask) return size;
        return ((const String*)ptr_)->size;
    }
    [[nodiscard]] constexpr uintptr_t raw() const noexcept { return ptr_; }
    ///@}
 
    /// @name Access
    ///@{
    constexpr char operator[](size_t i) const noexcept {
        assert(i < size());
        return view()[i];
    }
    constexpr char front() const noexcept { return (*this)[0]; }
    constexpr char back() const noexcept { return (*this)[size() - 1]; }
    ///@}
 
    /// @name Iterators
    ///@{
    constexpr auto begin() const noexcept { return view().data(); }
    constexpr auto end() const noexcept { return begin() + size(); }
    constexpr auto cbegin() const noexcept { return begin(); }
    constexpr auto cend() const noexcept { return end(); }
    constexpr auto rbegin() const noexcept { return std::reverse_iterator(end()); }
    constexpr auto rend() const noexcept { return std::reverse_iterator(begin()); }
    constexpr auto crbegin() const noexcept { return rbegin(); }
    constexpr auto crend() const noexcept { return rend(); }
    ///@}
 
    /// @name Comparison: Sym w/ Sym
    ///@{
    friend constexpr auto operator<=>(Sym s1, Sym s2) noexcept { return s1.view() <=> s2.view(); }
    friend constexpr bool operator==(Sym s1, Sym s2) noexcept { return s1.ptr_ == s2.ptr_; }
    ///@}
 
    /// @name Comparison: Sym w/ char
    ///@{
    friend constexpr std::strong_ordering operator<=>(Sym s, char c) noexcept { return cmp<false>(s, c); }
    friend constexpr std::strong_ordering operator<=>(char c, Sym s) noexcept { return cmp<true>(s, c); }
    friend constexpr bool operator==(Sym s, char c) noexcept { return (s.size() == 1) && (s[0] == c); }
    friend constexpr bool operator==(char c, Sym s) noexcept { return (s.size() == 1) && (s[0] == c); }
    ///@}
 
    /// @name Comparison: Sym w/ convertible to std::string_view
    ///@{
    friend constexpr auto operator<=>(Sym lhs, const std::convertible_to<std::string_view> auto& rhs) noexcept {
        return lhs.view() <=> std::string_view(rhs);
    }
    friend constexpr auto operator<=>(const std::convertible_to<std::string_view> auto& lhs, Sym rhs) noexcept {
        return std::string_view(lhs) <=> rhs.view();
    }
 
    friend constexpr bool operator==(Sym lhs, const std::convertible_to<std::string_view> auto& rhs) noexcept {
        return lhs.view() == std::string_view(rhs);
    }
 
    friend constexpr bool operator==(const std::convertible_to<std::string_view> auto& lhs, Sym rhs) noexcept {
        return std::string_view(lhs) == rhs.view();
    }
    ///@}
 
    /// @name Conversions
    ///@{
    /// @warning For a *short* Sym%bol (size < Sym::Short_String_Bytes) the characters are stored inline within this
    /// object's `ptr_`, so the returned view points into *this* Sym%bol and is only valid as long as it lives - it
    /// dangles for a temporary (e.g. `pool.sym("ab").view()`). Use Sym::str if the string must outlive the Sym%bol.
    [[nodiscard]] constexpr std::string_view view() const noexcept {
        if (empty()) return {std::bit_cast<const char*>(&ptr_), 0};
        // Little endian: 2 a b ? register: ?ba2
        // Big endian:    a b ? 2 register: ab?2
        uintptr_t offset = std::endian::native == std::endian::little ? 1 : 0;
        if (auto size = ptr_ & Short_String_Mask) return {std::bit_cast<const char*>(&ptr_) + offset, size};
        auto S = std::bit_cast<const String*>(ptr_);
        return std::string_view(S->chars, S->size);
    }
    constexpr operator std::string_view() const noexcept { return view(); }
    constexpr std::string_view operator*() const noexcept { return view(); }
    // Unfortunately, this doesn't work:
    // std::string_view operator->() const { return view(); }
 
    constexpr std::string str() const { return std::string(view()); }  ///< This involves a copy.
    constexpr explicit operator std::string() const { return str(); }  ///< `explicit` as this involves a copy.
    constexpr explicit operator bool() const noexcept { return ptr_; } ///< Is not empty?
    ///@}
 
    template<class H>
    friend constexpr H AbslHashValue(H h, Sym sym) noexcept {
        return H::combine(std::move(h), sym.ptr_);
    }
    friend struct ::std::hash<fe::Sym>;
    friend std::ostream& operator<<(std::ostream& os, Sym sym);
 
    /// @name Hash/Eq for hash tables.
    /// Both work on the interned pointer, so they are O(1).
    /// @note There is deliberately *no* heterogeneous (`std::string_view`) lookup:
    /// a content-based hash would be inconsistent with the pointer-based one.
    /// Intern via SymPool::sym first, then look up with the resulting Sym.
    ///@{
    struct Hash {
        size_t operator()(Sym s) const noexcept { return fe::hash(s.ptr_); }
    };
 
    struct Eq {
        constexpr bool operator()(Sym a, Sym b) const noexcept { return a.ptr_ == b.ptr_; }
    };
    ///@}
 
private:
    template<bool Rev>
    static constexpr std::strong_ordering cmp(Sym s, char c) noexcept {
        const auto n = s.size();
        if (n == 0) return Rev ? std::strong_ordering::greater : std::strong_ordering::less;
 
        auto cmp = s[0] <=> c;
        if (cmp != 0) return cmp;
 
        return (n == 1) ? std::strong_ordering::equal
                        : (Rev ? std::strong_ordering::less : std::strong_ordering::greater);
    }
 
    // Little endian: 2 a b ? register: ?ba2
    // Big endian:    a b ? 2 register: ab?2
    uintptr_t ptr_ = 0;
 
    friend class SymPool;
};
 
#ifndef DOXYGEN
} // namespace fe
 
template<>
struct std::hash<fe::Sym> {
    size_t operator()(fe::Sym sym) const noexcept { return fe::hash(sym.ptr_); }
};
 
namespace fe {
#endif
 
/// @name SymMap/SymSet
/// Set/Map is keyed by pointer - which is hashed in SymPool.
///@{
///
#ifdef FE_ABSL
template<class V>
using SymMap = absl::flat_hash_map<Sym, V, Sym::Hash, Sym::Eq>;
using SymSet = absl::flat_hash_set<Sym, Sym::Hash, Sym::Eq>;
#else
template<class V>
using SymMap = std::unordered_map<Sym, V, Sym::Hash, Sym::Eq>;
using SymSet = std::unordered_set<Sym, Sym::Hash, Sym::Eq>;
#endif
///@}
 
/// A fixed-capacity Sym%bol -> @p V map for a *closed* set of @p Size entries: filled once, then only
/// looked up - a Lexer's reserved words, say.
/// Prefer this over SymMap for that use: both hash and compare the same interned pointer, but SymMap
/// pays a full finalizer and a SwissTable group probe where this pays one multiply and one probe of
/// a table whose capacity is a compile-time constant.
/// @note @p V has to be default-constructible; an absent key yields no @p V at all - see SymTab::find.
/// @warning Insert-only: there is no erase, and SymTab::emplace asserts on a key already present.
template<class V, size_t Size>
class SymTab {
public:
    /// Twice @p Size, rounded up to a power of two, so the load factor stays below `1/2`.
    static constexpr size_t Capacity = std::bit_ceil(2 * Size);
 
    /// @name Access
    ///@{
    void emplace(Sym sym, V v) {
        assert(!sym.empty() && "the empty Sym%bol marks a free slot");
        for (auto i = idx(sym);; i = (i + 1) & Mask) {
            assert(slots_[i].sym != sym && "already present");
            if (slots_[i].sym.empty()) {
                slots_[i] = {sym, std::move(v)};
                return;
            }
        }
    }
 
    /// Yields nothing if @p sym is not present - the empty Sym%bol never is.
    /// @note The free-slot test comes first: the empty Sym%bol *is* a free slot's key.
    std::optional<V> find(Sym sym) const {
        for (auto i = idx(sym);; i = (i + 1) & Mask) {
            if (slots_[i].sym.empty()) return {};
            if (slots_[i].sym == sym) return slots_[i].v;
        }
    }
 
    bool contains(Sym sym) const { return (bool)find(sym); }
    ///@}
 
private:
    static constexpr size_t Mask    = Capacity - 1;
    static constexpr size_t Shift   = 64 - std::bit_width(Mask);
    static constexpr uint64_t Magic = 0x9E3779B97F4A7C15ull; ///< `2^64/phi` - Fibonacci hashing.
 
    /// Takes the *high* bits of the product: a long Sym%bol is an 8-byte aligned pointer and a short
    /// one's low byte is a size of `1 .. Sym::Short_String_Bytes-1`, so the low bits cluster.
    static size_t idx(Sym sym) { return size_t((uint64_t(sym.raw()) * Magic) >> Shift); }
 
    struct Slot {
        Sym sym;
        V v = {};
    };
 
    std::array<Slot, Capacity> slots_ = {};
};
 
/// Hash set where all strings - wrapped in Sym%bol - live in.
/// You can access the SymPool from Driver.
class SymPool {
public:
    using String = Sym::String;
 
    /// @name Constructor & Destruction
    ///@{
    SymPool(const SymPool&) = delete;
    SymPool() noexcept {}
    SymPool(SymPool&& other) noexcept
        : SymPool() {
        swap(*this, other);
    }
    SymPool& operator=(SymPool) = delete;
    ///@}
 
    /// @name sym
    ///@{
    Sym sym(std::string_view s);
    Sym sym(const std::string& s) { return sym((std::string_view)s); }
    /// @p s is a null-terminated C-string.
    Sym sym(const char* s) { return s == nullptr ? Sym() : sym(std::string_view(s)); }
    // TODO we can try to fit s in current page and hence eliminate the explicit use of strlen
    ///@}
 
    friend void swap(SymPool& p1, SymPool& p2) noexcept {
        using std::swap;
        // clang-format off
        swap(p1.strings_, p2.strings_);
        swap(p1.pool_,    p2.pool_   );
        // clang-format on
    }
 
private:
    Arena strings_;
#ifdef FE_ABSL
    absl::flat_hash_set<const String*, String::Hash, String::Equal> pool_;
#else
    std::unordered_set<const String*, String::Hash, String::Equal> pool_;
#endif
};
 
static_assert(std::is_trivially_copyable_v<Sym>);
static_assert(sizeof(uintptr_t) == sizeof(void*), "uintptr_t must match pointer size");
static_assert(std::has_unique_object_representations_v<uintptr_t>);
static_assert(std::endian::native == std::endian::little || std::endian::native == std::endian::big,
              "mixed endianness not supported");
 
} // namespace fe