header_map.hpp

#pragma once
 
#include <initializer_list>
#include <iterator>
#include <string>
#include <vector>
 
#include <userver/formats/json_fwd.hpp>
#include <userver/formats/parse/to.hpp>
#include <userver/http/predefined_header.hpp>
#include <userver/utils/fast_pimpl.hpp>
 
USERVER_NAMESPACE_BEGIN
 
namespace http::headers {
 
class TestsHelper;
 
namespace header_map {
class Map;
}
 
/// @ingroup userver_universal userver_containers
///
/// @brief Container that maps case-insensitive header name into header value.
///
/// Allows storing up to 24576 name->value pairs, after that an attempt to
/// insert a new pair will throw.
///
/// Has an anti-hashdos collisions resolution built-in, and the capacity limit
/// might be lowered in case of an attack being detected.
///
/// Iterators/pointers invalidation loosely matches that of std::vector:
/// * if an insertion took place, iterators/pointers are invalidated;
/// * successful erase invalidates the iterator being erased and `begin` (it's
/// implemented via swap and pop_back idiom, and `begin` is actually an `rbegin`
/// of underlying vector).
class HeaderMap final {
public:
    /// Iterator
    class Iterator;
    /// Const iterator
    class ConstIterator;
 
    using iterator = Iterator;
    using const_iterator = ConstIterator;
 
    using key_type = std::string;
    using mapped_type = std::string;
 
    /// The exception being thrown in case of capacity overflow
    class TooManyHeadersException final : public std::runtime_error {
        using std::runtime_error::runtime_error;
    };
 
    /// Default constructor.
    HeaderMap();
    /// Constructor from initializer list: `HeaderMap({{"a", "b"}, {"c", "d"}})`.
    /// Its unspecified which pair is inserted in case of names not being unique.
    HeaderMap(std::initializer_list<std::pair<std::string, std::string>> headers);
    /// Constructor from initializer list: `HeaderMap({{"a", "b"}, {"c", "d"}})`.
    /// Its unspecified which pair is inserted in case of names not being unique.
    HeaderMap(std::initializer_list<std::pair<PredefinedHeader, std::string>> headers);
    /// Constructor with capacity: preallocates `capacity` elements for internal
    /// storage.
    HeaderMap(std::size_t capacity);
    /// Constructor from iterator pair:
    /// `HeaderMap{key_value_pairs.begin(), key_value_pairs.end()}`.
    /// Its unspecified which pair is inserted in case of names not being unique.
    template <typename InputIt>
    HeaderMap(InputIt first, InputIt last);
 
    /// Destructor
    ~HeaderMap();
 
    /// Copy constructor
    HeaderMap(const HeaderMap& other);
    /// Move constructor
    HeaderMap(HeaderMap&& other) noexcept;
    /// Copy assignment operator
    HeaderMap& operator=(const HeaderMap& other);
    /// Move assignment operator
    HeaderMap& operator=(HeaderMap&& other) noexcept;
 
    /// Non-binding call to reserve `capacity` elements for internal storage.
    void reserve(std::size_t capacity);
    /// Returns the amount of name-value-pairs being stored.
    std::size_t size() const noexcept;
    /// Return true if no name-value-pairs are being stored, false otherwise.
    bool empty() const noexcept;
    /// Removes all the key-value-pairs being stored,
    /// doesn't shrink underlying storage.
    void clear();
 
    /// Returns 1 if the key exists, 0 otherwise.
    std::size_t count(std::string_view key) const noexcept;
    /// @overload
    std::size_t count(const PredefinedHeader& key) const noexcept;
 
    template <std::size_t Size>
    [[noreturn]] std::size_t count(const char (&)[Size]) const noexcept {
        ReportMisuse<Size>();
    }
 
    /// Returns true if the key exists, false otherwise.
    bool contains(std::string_view key) const noexcept;
    /// @overload
    bool contains(const PredefinedHeader& key) const noexcept;
 
    template <std::size_t Size>
    [[noreturn]] bool contains(const char (&)[Size]) const noexcept {
        ReportMisuse<Size>();
    }
 
    /// If the key is present, returns reference to it's header value,
    /// otherwise inserts a pair (key, "") and returns reference
    /// to newly inserted empty string.
    /// In an insertion took place, key is moved-out,
    /// otherwise key is left unchanged.
    std::string& operator[](std::string&& key);
    /// If the key is present, returns reference to it's header value,
    /// otherwise inserts a pair (key, "") and returns reference
    /// to newly inserted empty string.
    std::string& operator[](std::string_view key);
    /// @overload
    std::string& operator[](const PredefinedHeader& key);
 
    template <std::size_t Size>
    [[noreturn]] std::string& operator[](const char (&)[Size]) {
        ReportMisuse<Size>();
    }
 
    /// If the key is present, returns iterator to its name-value pair,
    /// otherwise return end().
    Iterator find(std::string_view key) noexcept;
    /// @overload
    ConstIterator find(std::string_view key) const noexcept;
 
    /// If the key is present, returns iterator to its name-value pair,
    /// otherwise return end().
    Iterator find(const PredefinedHeader& key) noexcept;
    /// @overload
    ConstIterator find(const PredefinedHeader& key) const noexcept;
 
    template <std::size_t Size>
    [[noreturn]] Iterator find(const char (&)[Size]) noexcept;
 
    template <std::size_t Size>
    [[noreturn]] ConstIterator find(const char (&)[Size]) const noexcept;
 
    /// If the key is already present in the map, does nothing.
    /// Otherwise inserts a pair of key and in-place constructed value.
    template <typename... Args>
    void emplace(std::string_view key, Args&&... args) {
        Emplace(std::move(key), std::forward<Args>(args)...);
    }
 
    /// If the key is already present in the map, does nothing.
    /// Otherwise inserts a pair of key and inplace constructed value.
    template <typename... Args>
    void emplace(std::string key, Args&&... args) {
        Emplace(std::move(key), std::forward<Args>(args)...);
    }
 
    /// If the key is already present in the map, does nothing.
    /// Otherwise inserts a pair of key and inplace constructed value.
    template <typename... Args>
    void try_emplace(std::string key, Args&&... args) {
        Emplace(std::move(key), std::forward<Args>(args)...);
    }
 
    /// For every iterator it in [first, last) inserts *it.
    /// Its unspecified which pair is inserted in case of names not being unique.
    template <typename InputIt>
    void insert(InputIt first, InputIt last);
 
    /// If kvp.first is already present in the map, does nothing,
    /// otherwise inserts the pair into container.
    void insert(const std::pair<std::string, std::string>& kvp);
    /// If kvp.first is already present in the map, does nothing,
    /// otherwise inserts the pair into container.
    void insert(std::pair<std::string, std::string>&& kvp);
 
    /// If key is already present in the map, changes corresponding header value
    /// to provided value, otherwise inserts the pair into container.
    void insert_or_assign(std::string key, std::string value);
    /// @overload
    void insert_or_assign(const PredefinedHeader& key, std::string value);
 
    /// If key is already present in the map, appends ",{value}" to the
    /// corresponding header value, otherwise inserts the pair into container.
    void InsertOrAppend(std::string key, std::string value);
    /// @overload
    void InsertOrAppend(const PredefinedHeader& key, std::string value);
 
    /// Erases the pair to which the iterator points, returns iterator following
    /// the last removed element.
    /// Iterators/pointers to erased value and `begin` are invalidated.
    Iterator erase(Iterator it);
    /// Erases the pair to which the iterator points, returns iterator following
    /// the last removed element.
    /// Iterators/pointers to erased value and `begin` are invalidated.
    Iterator erase(ConstIterator it);
 
    /// If the key is present in container, behaves exactly like erase(Iterator).
    /// Otherwise does nothing and returns `end()`.
    Iterator erase(std::string_view key);
    /// @overload
    Iterator erase(const PredefinedHeader& key);
 
    template <std::size_t Size>
    [[noreturn]] Iterator erase(const char (&)[Size]);
 
    /// If the key is present in container, returns reference to its header value,
    /// otherwise throws std::out_of_range.
    std::string& at(std::string_view key);
    /// @overload
    std::string& at(const PredefinedHeader& key);
    /// If the key is present in container, returns reference to its header value,
    /// otherwise throws std::out_of_range.
    const std::string& at(std::string_view key) const;
    /// @overload
    const std::string& at(const PredefinedHeader& key) const;
 
    template <std::size_t Size>
    [[noreturn]] std::string& at(const char (&)[Size]) {
        ReportMisuse<Size>();
    }
    template <std::size_t Size>
    [[noreturn]] const std::string& at(const char (&)[Size]) const {
        ReportMisuse<Size>();
    }
 
    /// Returns an iterator to the first name-value-pair being stored.
    Iterator begin() noexcept;
    /// Returns an iterator to the first name-value-pair being stored.
    ConstIterator begin() const noexcept;
    /// Returns an iterator to the first name-value-pair being stored.
    ConstIterator cbegin() const noexcept;
 
    /// Returns an iterator to the end (valid but not dereferenceable).
    Iterator end() noexcept;
    /// Returns an iterator to the end (valid but not dereferenceable).
    ConstIterator end() const noexcept;
    /// Returns an iterator to the end (valid but not dereferenceable).
    ConstIterator cend() const noexcept;
 
    /// Returns true if `other` contains exactly the same set of name-value-pairs,
    /// false otherwise.
    bool operator==(const HeaderMap& other) const noexcept;
 
    /// Appends container content in http headers format to provided buffer,
    /// that is appends
    /// @code
    /// header1: value1\r\n
    /// header2: value2\r\n
    /// ...
    /// @endcode
    /// resizing buffer as needed.
    void OutputInHttpFormat(HeadersString& buffer) const;
 
private:
    friend class TestsHelper;
 
    template <typename KeyType, typename... Args>
    void Emplace(KeyType&& key, Args&&... args);
 
    template <std::size_t Size>
    [[noreturn]] static void ReportMisuse();
 
    utils::FastPimpl<header_map::Map, 272, 8> impl_;
};
 
template <typename InputIt>
HeaderMap::HeaderMap(InputIt first, InputIt last) : HeaderMap{} {
    insert(first, last);
}
 
template <typename InputIt>
void HeaderMap::insert(InputIt first, InputIt last) {
    for (; first != last; ++first) {
        insert(*first);
    }
}
 
template <typename KeyType, typename... Args>
void HeaderMap::Emplace(KeyType&& key, Args&&... args) {
    static_assert(std::is_rvalue_reference_v<decltype(key)>);
    // This is a private function, and we know what we are doing here.
    // NOLINTNEXTLINE(bugprone-move-forwarding-reference)
    auto& value = operator[](std::move(key));
    if (value.empty()) {
        value = std::string{std::forward<Args>(args)...};
    }
}
 
template <std::size_t Size>
void HeaderMap::ReportMisuse() {
    static_assert(
        !Size,
        "Please create a 'constexpr PredefinedHeader' and use that "
        "instead of passing header name as a string literal."
    );
}
 
namespace header_map {
 
class MapEntry final {
public:
    MapEntry();
    ~MapEntry();
 
    MapEntry(std::string&& key, std::string&& value);
 
    MapEntry(const MapEntry& other);
    MapEntry& operator=(const MapEntry& other);
    MapEntry(MapEntry&& other) noexcept;
    MapEntry& operator=(MapEntry&& other) noexcept;
 
    std::pair<const std::string, std::string>& Get();
    const std::pair<const std::string, std::string>& Get() const;
 
    std::pair<std::string, std::string>& GetMutable();
 
    bool operator==(const MapEntry& other) const;
 
private:
    // The interface requires std::pair<CONST std::string, std::string>, but we
    // don't want to copy where move would do, so this.
    // Only 'mutable_value' is ever the active member of 'Slot', but we still
    // can access it through `value` due to
    // https://eel.is/c++draft/class.union.general#note-1
    // The idea was taken from abseil:
    // https://github.com/abseil/abseil-cpp/blob/1ae9b71c474628d60eb251a3f62967fe64151bb2/absl/container/internal/container_memory.h#L302
    union Slot {
        Slot();
        ~Slot();
 
        std::pair<std::string, std::string> mutable_value;
        std::pair<const std::string, std::string> value;
    };
 
    Slot slot_{};
};
 
}  // namespace header_map
 
class HeaderMap::Iterator final {
public:
    using iterator_category = std::forward_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = std::pair<const std::string, std::string>;
    using reference = value_type&;
    using const_reference = const value_type&;
    using pointer = value_type*;
    using const_pointer = const value_type*;
 
    // The underlying iterator is a reversed one to do not invalidate
    // end() on erase - end() is actually an rbegin() of underlying storage and is
    // only invalidated on reallocation.
    using UnderlyingIterator = std::vector<header_map::MapEntry>::reverse_iterator;
 
    Iterator();
    explicit Iterator(UnderlyingIterator it);
    ~Iterator();
 
    Iterator(const Iterator& other);
    Iterator(Iterator&& other) noexcept;
    Iterator& operator=(const Iterator& other);
    Iterator& operator=(Iterator&& other) noexcept;
 
    Iterator operator++(int);
    Iterator& operator++();
 
    reference operator*();
    const_reference operator*() const;
    pointer operator->();
    const_pointer operator->() const;
 
    bool operator==(const Iterator& other) const;
    bool operator!=(const Iterator& other) const;
 
    bool operator==(const ConstIterator& other) const;
 
private:
    friend class HeaderMap::ConstIterator;
 
    UnderlyingIterator it_{};
};
 
class HeaderMap::ConstIterator final {
public:
    using iterator_category = std::forward_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = std::pair<const std::string, std::string>;
    using reference = const value_type&;
    using const_reference = const value_type&;
    using pointer = const value_type*;
    using const_pointer = const value_type*;
 
    // The underlying iterator is a reversed one to do not invalidate
    // end() on erase - end() is actually an rbegin() of underlying storage and is
    // only invalidated on reallocation.
    using UnderlyingIterator = std::vector<header_map::MapEntry>::const_reverse_iterator;
 
    ConstIterator();
    explicit ConstIterator(UnderlyingIterator it);
    ~ConstIterator();
 
    ConstIterator(const ConstIterator& other);
    ConstIterator(ConstIterator&& other) noexcept;
    ConstIterator& operator=(const ConstIterator& other);
    ConstIterator& operator=(ConstIterator&& other) noexcept;
 
    ConstIterator operator++(int);
    ConstIterator& operator++();
 
    reference operator*();
    const_reference operator*() const;
    pointer operator->();
    const_pointer operator->() const;
 
    bool operator==(const ConstIterator& other) const;
    bool operator!=(const ConstIterator& other) const;
 
    bool operator==(const Iterator& other) const;
 
private:
    friend class HeaderMap::Iterator;
 
    UnderlyingIterator it_{};
};
 
template <std::size_t Size>
HeaderMap::Iterator HeaderMap::find(const char (&)[Size]) noexcept {
    ReportMisuse<Size>();
}
 
template <std::size_t Size>
HeaderMap::ConstIterator HeaderMap::find(const char (&)[Size]) const noexcept {
    ReportMisuse<Size>();
}
 
template <std::size_t Size>
HeaderMap::Iterator HeaderMap::erase(const char (&)[Size]) {
    ReportMisuse<Size>();
}
 
}  // namespace http::headers
 
USERVER_NAMESPACE_END