jsonpointer_pointer.h

#ifndef SOURCEMETA_CORE_JSONPOINTER_POINTER_H_
#define SOURCEMETA_CORE_JSONPOINTER_POINTER_H_
 
#include <sourcemeta/core/jsonpointer_token.h>
 
#include <algorithm>        // std::move, std::equal
#include <cassert>          // assert
#include <cstddef>          // std::size_t
#include <functional>       // std::reference_wrapper
#include <initializer_list> // std::initializer_list
#include <iterator>         // std::advance, std::back_inserter, std::next
#include <optional>         // std::optional
#include <ranges>           // std::ranges::subrange
#include <type_traits>      // std::is_same_v, std::decay_t
#include <utility>          // std::move
#include <vector>           // std::vector
 
#include <sourcemeta/core/preprocessor.h>
 
namespace sourcemeta::core {

template <typename PropertyT, typename Hash> class GenericPointer {
public:
  using Token = GenericToken<PropertyT, Hash>;
  using Value = typename Token::Value;
  using Container = std::vector<Token>;

  GenericPointer() noexcept : data{} {}

  GenericPointer(std::initializer_list<Token> tokens)
      : data{std::move(tokens)} {}
 
  // Member types
  using value_type = typename Container::value_type;
  using allocator_type = typename Container::allocator_type;
  using size_type = typename Container::size_type;
  using difference_type = typename Container::difference_type;
  using reference = typename Container::reference;
  using const_reference = typename Container::const_reference;
  using pointer = typename Container::pointer;
  using const_pointer = typename Container::const_pointer;
  using iterator = typename Container::iterator;
  using const_iterator = typename Container::const_iterator;
  using reverse_iterator = typename Container::reverse_iterator;
  using const_reverse_iterator = typename Container::const_reverse_iterator;

  auto begin() noexcept -> iterator { return this->data.begin(); }
  auto end() noexcept -> iterator { return this->data.end(); }
  [[nodiscard]] auto begin() const noexcept -> const_iterator {
    return this->data.begin();
  }
  [[nodiscard]] auto end() const noexcept -> const_iterator {
    return this->data.end();
  }
  [[nodiscard]] auto cbegin() const noexcept -> const_iterator {
    return this->data.cbegin();
  }
  [[nodiscard]] auto cend() const noexcept -> const_iterator {
    return this->data.cend();
  }
  auto rbegin() noexcept -> reverse_iterator { return this->data.rbegin(); }
  auto rend() noexcept -> reverse_iterator { return this->data.rend(); }
  [[nodiscard]] auto rbegin() const noexcept -> const_reverse_iterator {
    return this->data.rbegin();
  }
  [[nodiscard]] auto rend() const noexcept -> const_reverse_iterator {
    return this->data.rend();
  }
  [[nodiscard]] auto crbegin() const noexcept -> const_reverse_iterator {
    return this->data.crbegin();
  }
  [[nodiscard]] auto crend() const noexcept -> const_reverse_iterator {
    return this->data.crend();
  }

  [[nodiscard]] auto at(const size_type index) const -> const_reference {
    assert(this->size() > index);
    return this->data[index];
  }

  [[nodiscard]] SOURCEMETA_FORCEINLINE auto back() const -> const_reference {
    assert(!this->empty());
    return this->data.back();
  }

  [[nodiscard]] SOURCEMETA_FORCEINLINE auto size() const noexcept -> size_type {
    return this->data.size();
  }

  [[nodiscard]] SOURCEMETA_FORCEINLINE auto empty() const noexcept -> bool {
    return this->data.empty();
  }

  template <class... Args>
  SOURCEMETA_FORCEINLINE auto emplace_back(Args &&...args) -> reference {
    return this->data.emplace_back(std::forward<Args>(args)...);
  }

  auto reserve(const typename Container::size_type capacity) -> void {
    this->data.reserve(capacity);
  }

  SOURCEMETA_FORCEINLINE auto
  push_back(const GenericPointer<PropertyT, Hash> &other) -> void {
    if (other.empty()) {
      return;
    } else if (other.size() == 1) {
      this->emplace_back(other.back());
      return;
    }
 
    this->reserve(this->data.size() + other.size());
// TODO: Remove once GitHub Actions ship proper C++23 support
#if __cpp_lib_containers_ranges >= 202202L
    this->data.append_range(other.data);
#else
    std::copy(other.data.cbegin(), other.data.cend(),
              std::back_inserter(this->data));
#endif
  }

  SOURCEMETA_FORCEINLINE auto push_back(GenericPointer<PropertyT, Hash> &&other)
      -> void {
    if (other.empty()) {
      return;
    } else if (other.size() == 1) {
      this->emplace_back(std::move(other.back()));
      return;
    }
 
    this->reserve(this->data.size() + other.size());
    std::move(other.data.begin(), other.data.end(),
              std::back_inserter(this->data));
  }

  template <typename OtherT>
  SOURCEMETA_FORCEINLINE auto
  push_back(const GenericPointer<OtherT, Hash> &other) -> void
    requires std::is_same_v<PropertyT, std::reference_wrapper<const OtherT>>
  {
    if (other.empty()) {
      return;
    } else if (other.size() == 1) {
      const auto &token{other.back()};
      if (token.is_property()) {
        // We should make sure to re-use the existing hash
        this->data.emplace_back(token.to_property(), token.property_hash());
      } else {
        this->data.emplace_back(token.to_index());
      }
    } else {
      this->reserve(this->data.size() + other.size());
      for (const auto &token : other) {
        if (token.is_property()) {
          // We should make sure to re-use the existing hash
          this->data.emplace_back(token.to_property(), token.property_hash());
        } else {
          this->data.emplace_back(token.to_index());
        }
      }
    }
  }

  SOURCEMETA_FORCEINLINE auto
  push_back(const typename Token::Property &property) -> void {
    this->data.emplace_back(property);
  }

  SOURCEMETA_FORCEINLINE auto push_back(typename Token::Property &&property)
      -> void {
    this->data.emplace_back(std::move(property));
  }

  SOURCEMETA_FORCEINLINE auto push_back(const typename Token::Index &index)
      -> void {
    this->data.emplace_back(index);
  }

  auto pop_back() -> void {
    assert(!this->empty());
    this->data.pop_back();
  }

  auto pop_back(const size_type count) -> void {
    assert(this->size() >= count);
    for (std::size_t index = 0; index < count; index++) {
      this->data.pop_back();
    }
  }

  [[nodiscard]] auto initial() const -> GenericPointer<PropertyT, Hash> {
    assert(!this->empty());
    GenericPointer<PropertyT, Hash> result{*this};
    result.pop_back();
    return result;
  }

  [[nodiscard]] auto slice(const std::size_t index) const
      -> GenericPointer<PropertyT, Hash> {
    assert(index <= this->size());
    auto new_begin{this->data.cbegin()};
    std::advance(new_begin, index);
    GenericPointer<PropertyT, Hash> result;
    result.reserve(this->size() - index);
// TODO: Remove once GitHub Actions ship proper C++23 support
#if __cpp_lib_containers_ranges >= 202202L
    result.data.append_range(
        std::ranges::subrange(new_begin, this->data.cend()));
#else
    std::copy(new_begin, this->data.cend(), std::back_inserter(result.data));
#endif
    return result;
  }

  [[nodiscard]] auto slice(const std::size_t start, const std::size_t end) const
      -> GenericPointer<PropertyT, Hash> {
    assert(start <= end);
    assert(end <= this->size());
    auto new_begin{this->data.cbegin()};
    std::advance(new_begin, start);
    auto new_end{this->data.cbegin()};
    std::advance(new_end, end);
    GenericPointer<PropertyT, Hash> result;
    result.reserve(end - start);
// TODO: Remove once GitHub Actions ship proper C++23 support
#if __cpp_lib_containers_ranges >= 202202L
    result.data.append_range(std::ranges::subrange(new_begin, new_end));
#else
    std::copy(new_begin, new_end, std::back_inserter(result.data));
#endif
    return result;
  }

  [[nodiscard]] auto concat(const GenericPointer<PropertyT, Hash> &other) const
      -> GenericPointer<PropertyT, Hash> {
    GenericPointer<PropertyT, Hash> result{*this};
    result.push_back(other);
    return result;
  }

  [[nodiscard]] auto concat(const typename Token::Property &property) const
      -> GenericPointer<PropertyT, Hash> {
    GenericPointer<PropertyT, Hash> result{*this};
    result.push_back(property);
    return result;
  }

  [[nodiscard]] auto concat(const typename Token::Index &index) const
      -> GenericPointer<PropertyT, Hash> {
    GenericPointer<PropertyT, Hash> result{*this};
    result.push_back(index);
    return result;
  }

  [[nodiscard]] auto
  starts_with(const GenericPointer<PropertyT, Hash> &other) const -> bool {
    return other.data.size() <= this->data.size() &&
           std::equal(other.data.cbegin(), other.data.cend(),
                      this->data.cbegin());
  }

  [[nodiscard]] auto starts_with(const GenericPointer<PropertyT, Hash> &other,
                                 const Token &tail) const -> bool {
    if (other.size() == this->size() + 1) {
      assert(!other.empty());
      return other.starts_with(*this) && other.back() == tail;
    } else {
      return this->starts_with(other);
    }
  }

  template <typename StringT>
    requires(!std::is_same_v<std::decay_t<StringT>, Token>)
  [[nodiscard]] auto starts_with(const GenericPointer<PropertyT, Hash> &other,
                                 const StringT &tail) const -> bool {
    const auto prefix_size{other.size()};
    return this->size() > prefix_size && this->starts_with(other) &&
           this->data[prefix_size].is_property() &&
           this->data[prefix_size].to_property() == tail;
  }

  template <typename StringLeftT, typename StringRightT>
    requires(!std::is_same_v<std::decay_t<StringLeftT>, Token> &&
             !std::is_same_v<std::decay_t<StringRightT>, Token>)
  [[nodiscard]] auto starts_with(const GenericPointer<PropertyT, Hash> &other,
                                 const StringLeftT &tail_left,
                                 const StringRightT &tail_right) const -> bool {
    const auto prefix_size{other.size()};
    return this->size() > prefix_size + 1 &&
           this->starts_with(other, tail_left) &&
           this->data[prefix_size + 1].is_property() &&
           this->data[prefix_size + 1].to_property() == tail_right;
  }

  [[nodiscard]] auto shares_prefix(const GenericPointer<PropertyT, Hash> &other,
                                   const size_type prefix_size) const -> bool {
    return this->data.size() >= prefix_size &&
           other.data.size() >= prefix_size &&
           std::equal(this->data.cbegin(),
                      std::next(this->data.cbegin(),
                                static_cast<difference_type>(prefix_size)),
                      other.data.cbegin());
  }

  [[nodiscard]] auto
  starts_with_strict(const GenericPointer<PropertyT, Hash> &other) const
      -> bool {
    return this->data.size() > other.data.size() &&
           this->shares_prefix(other, other.data.size());
  }

  [[nodiscard]] auto
  starts_with_initial(const GenericPointer<PropertyT, Hash> &other) const
      -> bool {
    const auto prefix_size{other.size()};
    if (prefix_size == 0) {
      return true;
    } else if (this->size() < prefix_size - 1) {
      return false;
    }
 
    for (std::size_t index = 0; index < prefix_size - 1; index++) {
      if (this->data[index] != other.data[index]) {
        return false;
      }
    }
 
    return true;
  }

  [[nodiscard]] auto
  rebase(const GenericPointer<PropertyT, Hash> &prefix,
         const GenericPointer<PropertyT, Hash> &replacement) const
      -> GenericPointer<PropertyT, Hash> {
    typename Container::size_type index{0};
    while (index < prefix.size()) {
      if (index >= this->size() || prefix.data[index] != this->data[index]) {
        return *this;
      } else {
        index++;
      }
    }
 
    assert(index == prefix.size());
    assert(this->starts_with(prefix));
    auto new_begin{this->data.cbegin()};
    std::advance(new_begin, index);
    GenericPointer<PropertyT, Hash> result{replacement};
// TODO: Remove once GitHub Actions ship proper C++23 support
#if __cpp_lib_containers_ranges >= 202202L
    result.data.append_range(
        std::ranges::subrange(new_begin, this->data.cend()));
#else
    std::copy(new_begin, this->data.cend(), std::back_inserter(result.data));
#endif
    return result;
  }

  [[nodiscard]] auto
  resolve_from(const GenericPointer<PropertyT, Hash> &base) const
      -> GenericPointer<PropertyT, Hash> {
    if (base.empty()) {
      return *this;
    }
 
    typename Container::size_type index{0};
    while (index < base.size()) {
      if (index >= this->size() || base.data[index] != this->data[index]) {
        return *this;
      } else {
        index++;
      }
    }
 
    // Make a pointer from the remaining tokens
    auto new_begin{this->data.cbegin()};
    std::advance(new_begin, index);
    GenericPointer<PropertyT, Hash> result;
    const auto remaining{static_cast<typename Container::size_type>(
        this->data.cend() - new_begin)};
    result.data.reserve(remaining);
// TODO: Remove once GitHub Actions ship proper C++23 support
#if __cpp_lib_containers_ranges >= 202202L
    result.data.append_range(
        std::ranges::subrange(new_begin, this->data.cend()));
#else
    std::copy(new_begin, this->data.cend(), std::back_inserter(result.data));
#endif
    return result;
  }

  [[nodiscard]] auto
  operator==(const GenericPointer<PropertyT, Hash> &other) const noexcept
      -> bool {
    return this->data == other.data;
  }

  [[nodiscard]] auto
  operator==(const std::reference_wrapper<const GenericPointer<PropertyT, Hash>>
                 &other) const noexcept -> bool {
    return this->data == other.get().data;
  }

  [[nodiscard]] auto
  operator<(const GenericPointer<PropertyT, Hash> &other) const noexcept
      -> bool {
    return this->data < other.data;
  }

  [[nodiscard]] auto
  operator<(const std::reference_wrapper<const GenericPointer<PropertyT, Hash>>
                &other) const noexcept -> bool {
    return this->data < other.get().data;
  }

  struct Hasher {
    using is_transparent = void;
 
    auto
    operator()(const GenericPointer<PropertyT, Hash> &pointer) const noexcept
        -> std::size_t {
      const auto size{pointer.size()};
      if (size == 0) {
        return size;
      }
 
      const auto &first{pointer.at(0)};
      const auto &middle{pointer.at(size / 2)};
      const auto &last{pointer.at(size - 1)};
 
      return size +
             (first.is_property() ? property_hash(first.property_hash())
                                  : first.to_index()) +
             (middle.is_property() ? property_hash(middle.property_hash())
                                   : middle.to_index()) +
             (last.is_property() ? property_hash(last.property_hash())
                                 : last.to_index());
    }
 
    auto operator()(
        const std::reference_wrapper<const GenericPointer<PropertyT, Hash>>
            &reference) const noexcept -> std::size_t {
      return (*this)(reference.get());
    }
 
  private:
    // Intentionally only fold hash.a for performance, as the first
    // 16 bytes already provide sufficient entropy for bucketing
    static auto property_hash(const typename Hash::hash_type &hash) noexcept
        -> std::size_t {
      return static_cast<std::size_t>(hash.a) ^
             static_cast<std::size_t>(hash.a >> 64);
    }
  };

  struct Comparator {
    using is_transparent = void;
 
    auto operator()(const GenericPointer<PropertyT, Hash> &left,
                    const GenericPointer<PropertyT, Hash> &right) const noexcept
        -> bool {
      return left == right;
    }
 
    auto operator()(
        const std::reference_wrapper<const GenericPointer<PropertyT, Hash>>
            &left,
        const std::reference_wrapper<const GenericPointer<PropertyT, Hash>>
            &right) const noexcept -> bool {
      return left.get() == right.get();
    }
 
    auto operator()(
        const std::reference_wrapper<const GenericPointer<PropertyT, Hash>>
            &left,
        const GenericPointer<PropertyT, Hash> &right) const noexcept -> bool {
      return left.get() == right;
    }
 
    auto operator()(
        const GenericPointer<PropertyT, Hash> &left,
        const std::reference_wrapper<const GenericPointer<PropertyT, Hash>>
            &right) const noexcept -> bool {
      return left == right.get();
    }
  };

  [[nodiscard]] auto to_json() const -> Value {
    auto result{Value::make_array()};
    for (const auto &token : this->data) {
      result.push_back(token.to_json());
    }
 
    return result;
  }

  static auto from_json(const Value &value)
      -> std::optional<GenericPointer<PropertyT, Hash>>
    requires std::is_same_v<PropertyT, typename Value::String>
  {
    if (!value.is_array()) {
      return std::nullopt;
    }
 
    GenericPointer<PropertyT, Hash> result;
    for (const auto &element : value.as_array()) {
      if (element.is_string()) {
        result.emplace_back(element.to_string());
      } else if (element.is_integer() && element.to_integer() >= 0) {
        result.emplace_back(
            static_cast<typename Token::Index>(element.to_integer()));
      } else {
        return std::nullopt;
      }
    }
 
    return result;
  }
 
private:
  Container data;
};
 
} // namespace sourcemeta::core
 
#endif