Sourcemeta Core 0.0.0
Loading...
Searching...
No Matches
jsonpointer_pointer.h
1#ifndef SOURCEMETA_CORE_JSONPOINTER_POINTER_H_
2#define SOURCEMETA_CORE_JSONPOINTER_POINTER_H_
3
4#include <sourcemeta/core/jsonpointer_token.h>
5
6#include <algorithm> // std::move, std::equal
7#include <cassert> // assert
8#include <cstddef> // std::size_t
9#include <functional> // std::reference_wrapper
10#include <initializer_list> // std::initializer_list
11#include <iterator> // std::advance, std::back_inserter, std::next
12#include <optional> // std::optional
13#include <ranges> // std::ranges::subrange
14#include <type_traits> // std::is_same_v, std::decay_t
15#include <utility> // std::move
16#include <vector> // std::vector
17
18#include <sourcemeta/core/preprocessor.h>
19
20namespace sourcemeta::core {
21
25template <typename PropertyT, typename Hash> class GenericPointer {
26public:
32 using Container = std::vector<Token>;
33
43 GenericPointer() noexcept : data_{} {}
44
56 GenericPointer(std::initializer_list<Token> tokens)
57 : data_{std::move(tokens)} {}
58
59 // Member types
60 using value_type = Container::value_type;
61 using allocator_type = Container::allocator_type;
62 using size_type = Container::size_type;
63 using difference_type = Container::difference_type;
64 using reference = Container::reference;
65 using const_reference = Container::const_reference;
66 using pointer = Container::pointer;
67 using const_pointer = Container::const_pointer;
68 using iterator = Container::iterator;
69 using const_iterator = Container::const_iterator;
70 using reverse_iterator = Container::reverse_iterator;
71 using const_reverse_iterator = Container::const_reverse_iterator;
72
74 auto begin() noexcept -> iterator { return this->data_.begin(); }
76 auto end() noexcept -> iterator { return this->data_.end(); }
78 [[nodiscard]] auto begin() const noexcept -> const_iterator {
79 return this->data_.begin();
80 }
82 [[nodiscard]] auto end() const noexcept -> const_iterator {
83 return this->data_.end();
84 }
86 [[nodiscard]] auto cbegin() const noexcept -> const_iterator {
87 return this->data_.cbegin();
88 }
90 [[nodiscard]] auto cend() const noexcept -> const_iterator {
91 return this->data_.cend();
92 }
94 auto rbegin() noexcept -> reverse_iterator { return this->data_.rbegin(); }
96 auto rend() noexcept -> reverse_iterator { return this->data_.rend(); }
98 [[nodiscard]] auto rbegin() const noexcept -> const_reverse_iterator {
99 return this->data_.rbegin();
100 }
102 [[nodiscard]] auto rend() const noexcept -> const_reverse_iterator {
103 return this->data_.rend();
104 }
106 [[nodiscard]] auto crbegin() const noexcept -> const_reverse_iterator {
107 return this->data_.crbegin();
108 }
110 [[nodiscard]] auto crend() const noexcept -> const_reverse_iterator {
111 return this->data_.crend();
112 }
113
125 [[nodiscard]] auto at(const size_type index) const -> const_reference {
126 assert(this->size() > index);
127 return this->data_[index];
128 }
129
141 [[nodiscard]] SOURCEMETA_FORCEINLINE auto back() const -> const_reference {
142 assert(!this->empty());
143 return this->data_.back();
144 }
145
156 [[nodiscard]] SOURCEMETA_FORCEINLINE auto size() const noexcept -> size_type {
157 return this->data_.size();
158 }
159
172 [[nodiscard]] SOURCEMETA_FORCEINLINE auto empty() const noexcept -> bool {
173 return this->data_.empty();
174 }
175
189 template <class... Args>
190 SOURCEMETA_FORCEINLINE auto emplace_back(Args &&...args) -> reference {
191 return this->data_.emplace_back(std::forward<Args>(args)...);
192 }
193
202 auto reserve(const Container::size_type capacity) -> void {
203 this->data_.reserve(capacity);
204 }
205
226 SOURCEMETA_FORCEINLINE auto
228 if (other.empty()) {
229 return;
230 }
231 if (other.size() == 1) {
232 this->emplace_back(other.back());
233 return;
234 }
235
236 this->reserve(this->data_.size() + other.size());
237// TODO: Remove once GitHub Actions ship proper C++23 support
238#if __cpp_lib_containers_ranges >= 202202L
239 this->data_.append_range(other.data_);
240#else
241 std::copy(other.data_.cbegin(), other.data_.cend(),
242 std::back_inserter(this->data_));
243#endif
244 }
245
266 SOURCEMETA_FORCEINLINE auto push_back(GenericPointer<PropertyT, Hash> &&other)
267 -> void {
268 if (other.empty()) {
269 return;
270 }
271 if (other.size() == 1) {
272 this->emplace_back(std::move(other.back()));
273 return;
274 }
275
276 this->reserve(this->data_.size() + other.size());
277 std::move(other.data_.begin(), other.data_.end(),
278 std::back_inserter(this->data_));
279 }
280
303 template <typename OtherT>
304 SOURCEMETA_FORCEINLINE auto
306 requires std::is_same_v<PropertyT, std::reference_wrapper<const OtherT>>
307 {
308 if (other.empty()) {
309 return;
310 }
311 if (other.size() == 1) {
312 const auto &token{other.back()};
313 if (token.is_property()) {
314 // We should make sure to re-use the existing hash
315 this->data_.emplace_back(token.to_property(), token.property_hash());
316 } else {
317 this->data_.emplace_back(token.to_index());
318 }
319 } else {
320 this->reserve(this->data_.size() + other.size());
321 for (const auto &token : other) {
322 if (token.is_property()) {
323 // We should make sure to re-use the existing hash
324 this->data_.emplace_back(token.to_property(), token.property_hash());
325 } else {
326 this->data_.emplace_back(token.to_index());
327 }
328 }
329 }
330 }
331
350 SOURCEMETA_FORCEINLINE auto push_back(const Token::Property &property)
351 -> void {
352 this->data_.emplace_back(property);
353 }
354
372 SOURCEMETA_FORCEINLINE auto push_back(Token::Property &&property) -> void {
373 this->data_.emplace_back(std::move(property));
374 }
375
394 SOURCEMETA_FORCEINLINE auto push_back(const Token::Index &index) -> void {
395 this->data_.emplace_back(index);
396 }
397
410 auto pop_back() -> void {
411 assert(!this->empty());
412 this->data_.pop_back();
413 }
414
427 auto pop_back(const size_type count) -> void {
428 assert(this->size() >= count);
429 for (std::size_t index = 0; index < count; index++) {
430 this->data_.pop_back();
431 }
432 }
433
449 [[nodiscard]] auto initial() const -> GenericPointer<PropertyT, Hash> {
450 assert(!this->empty());
452 result.pop_back();
453 return result;
454 }
455
472 [[nodiscard]] auto slice(const std::size_t index) const
474 assert(index <= this->size());
475 auto new_begin{this->data_.cbegin()};
476 std::advance(new_begin, index);
478 result.reserve(this->size() - index);
479// TODO: Remove once GitHub Actions ship proper C++23 support
480#if __cpp_lib_containers_ranges >= 202202L
481 result.data_.append_range(
482 std::ranges::subrange(new_begin, this->data_.cend()));
483#else
484 std::copy(new_begin, this->data_.cend(), std::back_inserter(result.data_));
485#endif
486 return result;
487 }
488
506 [[nodiscard]] auto slice(const std::size_t start, const std::size_t end) const
508 assert(start <= end);
509 assert(end <= this->size());
510 auto new_begin{this->data_.cbegin()};
511 std::advance(new_begin, start);
512 auto new_end{this->data_.cbegin()};
513 std::advance(new_end, end);
515 result.reserve(end - start);
516// TODO: Remove once GitHub Actions ship proper C++23 support
517#if __cpp_lib_containers_ranges >= 202202L
518 result.data_.append_range(std::ranges::subrange(new_begin, new_end));
519#else
520 std::copy(new_begin, new_end, std::back_inserter(result.data_));
521#endif
522 return result;
523 }
524
537 [[nodiscard]] auto concat(const GenericPointer<PropertyT, Hash> &other) const
540 result.reserve(this->data_.size() + other.data_.size());
541 result.push_back(*this);
542 result.push_back(other);
543 return result;
544 }
545
556 [[nodiscard]] auto concat(const Token::Property &property) const
559 result.reserve(this->data_.size() + 1);
560 result.push_back(*this);
561 result.push_back(property);
562 return result;
563 }
564
575 [[nodiscard]] auto concat(const Token::Index &index) const
578 result.reserve(this->data_.size() + 1);
579 result.push_back(*this);
580 result.push_back(index);
581 return result;
582 }
583
595 [[nodiscard]] auto
596 starts_with(const GenericPointer<PropertyT, Hash> &other) const -> bool {
597 return other.data_.size() <= this->data_.size() &&
598 std::equal(other.data_.cbegin(), other.data_.cend(),
599 this->data_.cbegin());
600 }
601
614 [[nodiscard]] auto starts_with(const GenericPointer<PropertyT, Hash> &other,
615 const Token &tail) const -> bool {
616 if (other.size() == this->size() + 1) {
617 assert(!other.empty());
618 return other.starts_with(*this) && other.back() == tail;
619 }
620 return this->starts_with(other);
621 }
622
636 template <typename StringT>
637 requires(!std::is_same_v<std::decay_t<StringT>, Token>)
638 [[nodiscard]] auto starts_with(const GenericPointer<PropertyT, Hash> &other,
639 const StringT &tail) const -> bool {
640 const auto prefix_size{other.size()};
641 return this->size() > prefix_size && this->starts_with(other) &&
642 this->data_[prefix_size].is_property() &&
643 this->data_[prefix_size].to_property() == tail;
644 }
645
659 template <typename StringLeftT, typename StringRightT>
660 requires(!std::is_same_v<std::decay_t<StringLeftT>, Token> &&
661 !std::is_same_v<std::decay_t<StringRightT>, Token>)
662 [[nodiscard]] auto starts_with(const GenericPointer<PropertyT, Hash> &other,
663 const StringLeftT &tail_left,
664 const StringRightT &tail_right) const -> bool {
665 const auto prefix_size{other.size()};
666 return this->size() > prefix_size + 1 &&
667 this->starts_with(other, tail_left) &&
668 this->data_[prefix_size + 1].is_property() &&
669 this->data_[prefix_size + 1].to_property() == tail_right;
670 }
671
684 [[nodiscard]] auto shares_prefix(const GenericPointer<PropertyT, Hash> &other,
685 const size_type prefix_size) const -> bool {
686 return this->data_.size() >= prefix_size &&
687 other.data_.size() >= prefix_size &&
688 std::equal(this->data_.cbegin(),
689 std::next(this->data_.cbegin(),
690 static_cast<difference_type>(prefix_size)),
691 other.data_.cbegin());
692 }
693
706 [[nodiscard]] auto
708 -> bool {
709 return this->data_.size() > other.data_.size() &&
710 this->shares_prefix(other, other.data_.size());
711 }
712
724 [[nodiscard]] auto
726 -> bool {
727 const auto prefix_size{other.size()};
728 if (prefix_size == 0) {
729 return true;
730 }
731 if (this->size() < prefix_size - 1) {
732 return false;
733 }
734
735 for (std::size_t index = 0; index < prefix_size - 1; index++) {
736 if (this->data_[index] != other.data_[index]) {
737 return false;
738 }
739 }
740
741 return true;
742 }
743
757 [[nodiscard]] auto
759 const GenericPointer<PropertyT, Hash> &replacement) const
761 typename Container::size_type index{0};
762 while (index < prefix.size()) {
763 if (index >= this->size() || prefix.data_[index] != this->data_[index]) {
764 return *this;
765 }
766 index++;
767 }
768
769 assert(index == prefix.size());
770 assert(this->starts_with(prefix));
771 auto new_begin{this->data_.cbegin()};
772 std::advance(new_begin, index);
773 GenericPointer<PropertyT, Hash> result{replacement};
774// TODO: Remove once GitHub Actions ship proper C++23 support
775#if __cpp_lib_containers_ranges >= 202202L
776 result.data_.append_range(
777 std::ranges::subrange(new_begin, this->data_.cend()));
778#else
779 std::copy(new_begin, this->data_.cend(), std::back_inserter(result.data_));
780#endif
781 return result;
782 }
783
798 [[nodiscard]] auto
801 if (base.empty()) {
802 return *this;
803 }
804
805 typename Container::size_type index{0};
806 while (index < base.size()) {
807 if (index >= this->size() || base.data_[index] != this->data_[index]) {
808 return *this;
809 }
810 index++;
811 }
812
813 // Make a pointer from the remaining tokens
814 auto new_begin{this->data_.cbegin()};
815 std::advance(new_begin, index);
817 const auto remaining{
818 static_cast<Container::size_type>(this->data_.cend() - new_begin)};
819 result.data_.reserve(remaining);
820// TODO: Remove once GitHub Actions ship proper C++23 support
821#if __cpp_lib_containers_ranges >= 202202L
822 result.data_.append_range(
823 std::ranges::subrange(new_begin, this->data_.cend()));
824#else
825 std::copy(new_begin, this->data_.cend(), std::back_inserter(result.data_));
826#endif
827 return result;
828 }
829
831 [[nodiscard]] auto
832 operator==(const GenericPointer<PropertyT, Hash> &other) const noexcept
833 -> bool {
834 return this->data_ == other.data_;
835 }
836
838 [[nodiscard]] auto
839 operator==(const std::reference_wrapper<const GenericPointer<PropertyT, Hash>>
840 &other) const noexcept -> bool {
841 return this->data_ == other.get().data_;
842 }
843
846 [[nodiscard]] auto
847 operator<(const GenericPointer<PropertyT, Hash> &other) const noexcept
848 -> bool {
849 return this->data_ < other.data_;
850 }
851
853 [[nodiscard]] auto
854 operator<(const std::reference_wrapper<const GenericPointer<PropertyT, Hash>>
855 &other) const noexcept -> bool {
856 return this->data_ < other.get().data_;
857 }
858
860 struct Hasher {
861 using is_transparent = void;
862
863 auto
864 operator()(const GenericPointer<PropertyT, Hash> &pointer) const noexcept
865 -> std::size_t {
866 const auto size{pointer.size()};
867 if (size == 0) {
868 return size;
869 }
870
871 const auto &first{pointer.at(0)};
872 const auto &middle{pointer.at(size / 2)};
873 const auto &last{pointer.at(size - 1)};
874
875 return size +
876 (first.is_property() ? property_hash(first.property_hash())
877 : first.to_index()) +
878 (middle.is_property() ? property_hash(middle.property_hash())
879 : middle.to_index()) +
880 (last.is_property() ? property_hash(last.property_hash())
881 : last.to_index());
882 }
883
884 auto operator()(
885 const std::reference_wrapper<const GenericPointer<PropertyT, Hash>>
886 &reference) const noexcept -> std::size_t {
887 return (*this)(reference.get());
888 }
889
890 private:
891 // Intentionally only fold hash.a for performance, as the first
892 // 16 bytes already provide sufficient entropy for bucketing
893 static auto property_hash(const Hash::HashType &hash) noexcept
894 -> std::size_t {
895 return static_cast<std::size_t>(hash.a) ^
896 static_cast<std::size_t>(hash.a >> 64);
897 }
898 };
899
901 struct Comparator {
902 using is_transparent = void;
903
904 auto operator()(const GenericPointer<PropertyT, Hash> &left,
905 const GenericPointer<PropertyT, Hash> &right) const noexcept
906 -> bool {
907 return left == right;
908 }
909
910 auto operator()(
911 const std::reference_wrapper<const GenericPointer<PropertyT, Hash>>
912 &left,
913 const std::reference_wrapper<const GenericPointer<PropertyT, Hash>>
914 &right) const noexcept -> bool {
915 return left.get() == right.get();
916 }
917
918 auto operator()(
919 const std::reference_wrapper<const GenericPointer<PropertyT, Hash>>
920 &left,
921 const GenericPointer<PropertyT, Hash> &right) const noexcept -> bool {
922 return left.get() == right;
923 }
924
925 auto operator()(
927 const std::reference_wrapper<const GenericPointer<PropertyT, Hash>>
928 &right) const noexcept -> bool {
929 return left == right.get();
930 }
931 };
932
934 [[nodiscard]] auto to_json() const -> Value {
935 auto result{Value::make_array()};
936 for (const auto &token : this->data_) {
937 result.push_back(token.to_json());
938 }
939
940 return result;
941 }
942
944 static auto from_json(const Value &value)
945 -> std::optional<GenericPointer<PropertyT, Hash>>
946 requires std::is_same_v<PropertyT, typename Value::String>
947 {
948 if (!value.is_array()) {
949 return std::nullopt;
950 }
951
953 for (const auto &element : value.as_array()) {
954 if (element.is_string()) {
955 result.emplace_back(element.to_string());
956 } else if (element.is_integer() && element.to_integer() >= 0) {
957 result.emplace_back(static_cast<Token::Index>(element.to_integer()));
958 } else {
959 return std::nullopt;
960 }
961 }
962
963 return result;
964 }
965
966private:
967 Container data_;
968};
969
970} // namespace sourcemeta::core
971
972#endif
static auto make_array() -> JSON
auto rebase(const GenericPointer< PropertyT, Hash > &prefix, const GenericPointer< PropertyT, Hash > &replacement) const -> GenericPointer< PropertyT, Hash >
Definition jsonpointer_pointer.h:758
auto reserve(const Container::size_type capacity) -> void
Definition jsonpointer_pointer.h:202
auto slice(const std::size_t start, const std::size_t end) const -> GenericPointer< PropertyT, Hash >
Definition jsonpointer_pointer.h:506
auto shares_prefix(const GenericPointer< PropertyT, Hash > &other, const size_type prefix_size) const -> bool
Definition jsonpointer_pointer.h:684
static auto from_json(const Value &value) -> std::optional< GenericPointer< PropertyT, Hash > >
Deserialise a JSON Pointer from a JSON array of tokens.
Definition jsonpointer_pointer.h:944
auto slice(const std::size_t index) const -> GenericPointer< PropertyT, Hash >
Definition jsonpointer_pointer.h:472
JSON Value
The JSON value type these tokens convert to.
Definition jsonpointer_token.h:16
auto concat(const GenericPointer< PropertyT, Hash > &other) const -> GenericPointer< PropertyT, Hash >
Definition jsonpointer_pointer.h:537
SOURCEMETA_FORCEINLINE auto push_back(GenericPointer< PropertyT, Hash > &&other) -> void
Definition jsonpointer_pointer.h:266
auto resolve_from(const GenericPointer< PropertyT, Hash > &base) const -> GenericPointer< PropertyT, Hash >
Definition jsonpointer_pointer.h:799
auto starts_with_initial(const GenericPointer< PropertyT, Hash > &other) const -> bool
Definition jsonpointer_pointer.h:725
auto starts_with(const GenericPointer< PropertyT, Hash > &other, const Token &tail) const -> bool
Definition jsonpointer_pointer.h:614
SOURCEMETA_FORCEINLINE auto emplace_back(Args &&...args) -> reference
Definition jsonpointer_pointer.h:190
auto pop_back() -> void
Definition jsonpointer_pointer.h:410
auto starts_with(const GenericPointer< PropertyT, Hash > &other, const StringLeftT &tail_left, const StringRightT &tail_right) const -> bool
Definition jsonpointer_pointer.h:662
Value::Array::size_type Index
The stored type of an array index token.
Definition jsonpointer_token.h:20
SOURCEMETA_FORCEINLINE auto push_back(const GenericPointer< PropertyT, Hash > &other) -> void
Definition jsonpointer_pointer.h:227
auto concat(const Token::Property &property) const -> GenericPointer< PropertyT, Hash >
Definition jsonpointer_pointer.h:556
auto at(const size_type index) const -> const_reference
Definition jsonpointer_pointer.h:125
SOURCEMETA_FORCEINLINE auto empty() const noexcept -> bool
Definition jsonpointer_pointer.h:172
auto starts_with(const GenericPointer< PropertyT, Hash > &other) const -> bool
Definition jsonpointer_pointer.h:596
auto starts_with_strict(const GenericPointer< PropertyT, Hash > &other) const -> bool
Definition jsonpointer_pointer.h:707
GenericPointer() noexcept
Definition jsonpointer_pointer.h:43
SOURCEMETA_FORCEINLINE auto push_back(const Token::Property &property) -> void
Definition jsonpointer_pointer.h:350
SOURCEMETA_FORCEINLINE auto back() const -> const_reference
Definition jsonpointer_pointer.h:141
GenericToken< JSON::String, PropertyHashJSON< JSON::String > > Token
Definition jsonpointer_pointer.h:28
SOURCEMETA_FORCEINLINE auto push_back(Token::Property &&property) -> void
Definition jsonpointer_pointer.h:372
GenericPointer(std::initializer_list< Token > tokens)
Definition jsonpointer_pointer.h:56
auto concat(const Token::Index &index) const -> GenericPointer< PropertyT, Hash >
Definition jsonpointer_pointer.h:575
auto to_json() const -> Value
Serialise a JSON Pointer as a JSON array of tokens.
Definition jsonpointer_pointer.h:934
auto starts_with(const GenericPointer< PropertyT, Hash > &other, const StringT &tail) const -> bool
Definition jsonpointer_pointer.h:638
auto pop_back(const size_type count) -> void
Definition jsonpointer_pointer.h:427
SOURCEMETA_FORCEINLINE auto push_back(const GenericPointer< OtherT, Hash > &other) -> void
Definition jsonpointer_pointer.h:305
SOURCEMETA_FORCEINLINE auto size() const noexcept -> size_type
Definition jsonpointer_pointer.h:156
std::vector< Token > Container
Definition jsonpointer_pointer.h:32
SOURCEMETA_FORCEINLINE auto push_back(const Token::Index &index) -> void
Definition jsonpointer_pointer.h:394
PropertyT Property
The stored type of an object property token.
Definition jsonpointer_token.h:18
auto initial() const -> GenericPointer< PropertyT, Hash >
Definition jsonpointer_pointer.h:449
Definition jsonpointer_pointer.h:25
Definition jsonpointer_token.h:13
Comparator for use with containers.
Definition jsonpointer_pointer.h:901
Hash functor for use with containers.
Definition jsonpointer_pointer.h:860