From 5a280ca1d62ac3750bf590328e3d08e0e3342cfc Mon Sep 17 00:00:00 2001 From: Gil Date: Mon, 29 Jan 2018 08:38:32 -0800 Subject: Import iterator_adaptors from google3 (#718) * Import iterator_adapters from google3 * Remove -Wconversion which is annoyingly hard to satisfy * Strip dependency on absl_container from iterator_adapters_test * Format and lint iterator_adaptors * More flexible copyright checking in Travis --- .../src/firebase/firestore/util/CMakeLists.txt | 1 + .../firebase/firestore/util/iterator_adaptors.h | 812 +++++++++++++++++++++ 2 files changed, 813 insertions(+) create mode 100644 Firestore/core/src/firebase/firestore/util/iterator_adaptors.h (limited to 'Firestore/core/src/firebase') diff --git a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt index b763a63..3e32111 100644 --- a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt +++ b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt @@ -113,6 +113,7 @@ cc_library( comparison.h config.h firebase_assert.h + iterator_adaptors.h log.h ordered_code.cc ordered_code.h diff --git a/Firestore/core/src/firebase/firestore/util/iterator_adaptors.h b/Firestore/core/src/firebase/firestore/util/iterator_adaptors.h new file mode 100644 index 0000000..042fd72 --- /dev/null +++ b/Firestore/core/src/firebase/firestore/util/iterator_adaptors.h @@ -0,0 +1,812 @@ +/* + * Copyright 2005, 2018 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +// Provides some iterator adaptors and views. + +#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_ITERATOR_ADAPTORS_H_ +#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_ITERATOR_ADAPTORS_H_ + +#include +#include +#include + +#include "absl/base/port.h" +#include "absl/meta/type_traits.h" + +namespace firebase { +namespace firestore { +namespace util { + +namespace internal { + +// value == true if Iter prohibits modification of its pointees. +template +struct IsConstIter + : std::is_const::reference>::type> {}; + +template +struct AddConstIf : std::conditional {}; + +// SynthIterTraits propagates the constness of the 'BaseIter' iterator +// type to its own exported 'pointer' and 'reference' typedefs. +template +struct SynthIterTraits : std::iterator_traits { + private: + static constexpr bool kIterConst = IsConstIter::value; + + public: + using value_type = typename std::remove_cv::type; + using pointer = typename AddConstIf::type*; + using reference = typename AddConstIf::type&; +}; + +// PointeeSynthIterTraits is similar to SynthIterTraits, but the 'Ptr' +// parameter is a pointer-like type, and value_type is the pointee. +template +struct PointeeSynthIterTraits : std::iterator_traits { + private: + static constexpr bool kIterConst = IsConstIter::value; + + public: + using value_type = typename std::pointer_traits::element_type; + using pointer = typename AddConstIf::type*; + using reference = typename AddConstIf::type&; +}; + +// CRTP base class for generating iterator adaptors. +// 'Sub' is the derived type, and 'Policy' encodes +// all of the behavior for the adaptor. +// Policy requirements: +// - type 'underlying_iterator': the underlying iterator type. +// - type 'adapted_traits': the traits of the adaptor. +// - static 'Extract(underlying_iterator)': convert iterator to reference. +// +template +class IteratorAdaptorBase { + private: + // Everything needed from the Policy type is expressed in this section. + using Iterator = typename Policy::underlying_iterator; + using OutTraits = typename Policy::adapted_traits; + static typename OutTraits::reference Extract(const Iterator& it) { + return Policy::Extract(it); + } + + public: + using iterator_category = typename OutTraits::iterator_category; + using value_type = typename OutTraits::value_type; + using pointer = typename OutTraits::pointer; + using reference = typename OutTraits::reference; + using difference_type = typename OutTraits::difference_type; + + IteratorAdaptorBase() : it_() { + } + // NOLINTNEXTLINE(runtime/explicit) + IteratorAdaptorBase(Iterator it) : it_(it) { + } + + Sub& sub() { + return static_cast(*this); + } + const Sub& sub() const { + return static_cast(*this); + } + + const Iterator& base() const { + return it_; + } + + reference get() const { + return Extract(base()); + } + reference operator*() const { + return get(); + } + pointer operator->() const { + return &get(); + } + reference operator[](difference_type d) const { + return *(sub() + d); + } + + Sub& operator++() { + ++it_; + return sub(); + } + Sub& operator--() { + --it_; + return sub(); + } + Sub operator++(int /*unused*/) { + return it_++; + } + Sub operator--(int /*unused*/) { + return it_--; + } + + Sub& operator+=(difference_type d) { + it_ += d; + return sub(); + } + Sub& operator-=(difference_type d) { + it_ -= d; + return sub(); + } + + bool operator==(Sub b) const { + return base() == b.base(); + } + bool operator!=(Sub b) const { + return base() != b.base(); + } + // These shouldn't be necessary, as implicit conversion from 'Iterator' + // should be enough to make such comparisons work. + bool operator==(Iterator b) const { + return *this == Sub(b); + } + bool operator!=(Iterator b) const { + return *this != Sub(b); + } + + friend Sub operator+(Sub it, difference_type d) { + return it.base() + d; + } + friend Sub operator+(difference_type d, Sub it) { + return it + d; + } + friend Sub operator-(Sub it, difference_type d) { + return it.base() - d; + } + friend difference_type operator-(Sub a, Sub b) { + return a.base() - b.base(); + } + + friend bool operator<(Sub a, Sub b) { + return a.base() < b.base(); + } + friend bool operator>(Sub a, Sub b) { + return a.base() > b.base(); + } + friend bool operator<=(Sub a, Sub b) { + return a.base() <= b.base(); + } + friend bool operator>=(Sub a, Sub b) { + return a.base() >= b.base(); + } + + private: + Iterator it_; +}; + +template +struct FirstPolicy { + using underlying_iterator = It; + using adapted_traits = + SynthIterTraits::value_type::first_type>; + static typename adapted_traits::reference Extract( + const underlying_iterator& it) { + return it->first; + } +}; + +template +struct SecondPolicy { + using underlying_iterator = It; + using adapted_traits = + SynthIterTraits::value_type::second_type>; + static typename adapted_traits::reference Extract( + const underlying_iterator& it) { + return it->second; + } +}; + +template +struct SecondPtrPolicy { + using underlying_iterator = It; + using adapted_traits = + PointeeSynthIterTraits::value_type::second_type>; + static typename adapted_traits::reference Extract( + const underlying_iterator& it) { + return *it->second; + } +}; + +template +struct PtrPolicy { + using underlying_iterator = It; + using adapted_traits = PointeeSynthIterTraits< + underlying_iterator, + typename std::iterator_traits::value_type>; + static typename adapted_traits::reference Extract( + const underlying_iterator& it) { + return **it; + } +}; + +} // namespace internal + +// In both iterator adaptors, iterator_first<> and iterator_second<>, +// we build a new iterator based on a parameterized iterator type, "It". +// The value type, "Val" is determined by "It::value_type::first" or +// "It::value_type::second", respectively. + +// iterator_first<> adapts an iterator to return the first value of a pair. +// It is equivalent to calling it->first on every value. +// Example: +// +// hash_map values; +// values["foo"] = 1; +// values["bar"] = 2; +// for (iterator_first::iterator> x = values.begin(); +// x != values.end(); ++x) { +// printf("%s", x->c_str()); +// } +template +struct iterator_first + : internal::IteratorAdaptorBase, + internal::FirstPolicy> { + using Base = internal::IteratorAdaptorBase, + internal::FirstPolicy>; + iterator_first() { + } + iterator_first(It it) // NOLINT(runtime/explicit) + : Base(it) { + } + template + iterator_first(iterator_first o) // NOLINT(runtime/explicit) + : Base(o.base()) { + } +}; + +template +iterator_first make_iterator_first(It it) { + return iterator_first(it); +} + +// iterator_second<> adapts an iterator to return the second value of a pair. +// It is equivalent to calling it->second on every value. +// Example: +// +// hash_map values; +// values["foo"] = 1; +// values["bar"] = 2; +// for (iterator_second::iterator> x = values.begin(); +// x != values.end(); ++x) { +// int v = *x; +// printf("%d", v); +// } +template +struct iterator_second + : internal::IteratorAdaptorBase, + internal::SecondPolicy> { + using Base = internal::IteratorAdaptorBase, + internal::SecondPolicy>; + iterator_second() { + } + iterator_second(It it) // NOLINT(runtime/explicit) + : Base(it) { + } + template + iterator_second(iterator_second o) // NOLINT(runtime/explicit) + : Base(o.base()) { + } +}; + +template +iterator_second make_iterator_second(It it) { + return iterator_second(it); +} + +// iterator_second_ptr<> adapts an iterator to return the dereferenced second +// value of a pair. +// It is equivalent to calling *it->second on every value. +// The same result can be achieved by composition +// iterator_ptr > +// Can be used with maps where values are regular pointers or pointers wrapped +// into linked_ptr. This iterator adaptor can be used by classes to give their +// clients access to some of their internal data without exposing too much of +// it. +// +// Example: +// class MyClass { +// public: +// MyClass(const string& s); +// string DebugString() const; +// }; +// typedef hash_map > MyMap; +// typedef iterator_second_ptr MyMapValuesIterator; +// MyMap values; +// values["foo"].reset(new MyClass("foo")); +// values["bar"].reset(new MyClass("bar")); +// for (MyMapValuesIterator it = values.begin(); it != values.end(); ++it) { +// printf("%s", it->DebugString().c_str()); +// } +template +struct iterator_second_ptr + : internal::IteratorAdaptorBase, + internal::SecondPtrPolicy> { + using Base = internal::IteratorAdaptorBase, + internal::SecondPtrPolicy>; + iterator_second_ptr() { + } + iterator_second_ptr(It it) // NOLINT(runtime/explicit) + : Base(it) { + } + template + iterator_second_ptr(iterator_second_ptr o) // NOLINT(runtime/explicit) + : Base(o.base()) { + } +}; + +template +iterator_second_ptr make_iterator_second_ptr(It it) { + return iterator_second_ptr(it); +} + +// iterator_ptr<> adapts an iterator to return the dereferenced value. +// With this adaptor you can write *it instead of **it, or it->something instead +// of (*it)->something. +// Can be used with vectors and lists where values are regular pointers +// or pointers wrapped into linked_ptr. This iterator adaptor can be used by +// classes to give their clients access to some of their internal data without +// exposing too much of it. +// +// Example: +// class MyClass { +// public: +// MyClass(const string& s); +// string DebugString() const; +// }; +// typedef vector > MyVector; +// typedef iterator_ptr DereferencingIterator; +// MyVector values; +// values.push_back(make_linked_ptr(new MyClass("foo"))); +// values.push_back(make_linked_ptr(new MyClass("bar"))); +// for (DereferencingIterator it = values.begin(); it != values.end(); ++it) { +// printf("%s", it->DebugString().c_str()); +// } +// +// Without iterator_ptr you would have to do (*it)->DebugString() +template +struct iterator_ptr : internal::IteratorAdaptorBase, + internal::PtrPolicy> { + using Base = internal::IteratorAdaptorBase, + internal::PtrPolicy>; + iterator_ptr() { + } + iterator_ptr(It it) // NOLINT(runtime/explicit) + : Base(it) { + } + template + iterator_ptr(iterator_ptr o) // NOLINT(runtime/explicit) + : Base(o.base()) { + } +}; + +template +iterator_ptr make_iterator_ptr(It it) { + return iterator_ptr(it); +} + +namespace internal { + +// Template that uses SFINAE to inspect Container abilities: +// . Set has_size_type true, iff T::size_type is defined +// . Define size_type as T::size_type if defined, or size_t otherwise +template +struct container_traits { + private: + // Test for availability of C::size_type. + template + struct test_size_type : std::false_type {}; + template + struct test_size_type> + : std::true_type {}; + + // Conditional provisioning of a size_type which defaults to size_t. + template + struct size_type_def { + using type = typename U::size_type; + }; + template + struct size_type_def { + using type = size_t; + }; + + public: + // Determine whether C::size_type is available. + static const bool has_size_type = test_size_type::value; + + // Provide size_type as either C::size_type if available, or as size_t. + using size_type = typename size_type_def::type; +}; + +template +struct IterGenerator { + using container_type = C; + using iterator = typename C::iterator; + using const_iterator = typename C::const_iterator; + + static iterator begin(container_type& c) { // NOLINT(runtime/references) + return c.begin(); + } + static iterator end(container_type& c) { // NOLINT(runtime/references) + return c.end(); + } + static const_iterator begin(const container_type& c) { + return c.begin(); + } + static const_iterator end(const container_type& c) { + return c.end(); + } +}; + +template +struct ReversingIterGeneratorAdaptor { + using container_type = typename SubIterGenerator::container_type; + using iterator = std::reverse_iterator; + using const_iterator = + std::reverse_iterator; + + static iterator begin(container_type& c) { // NOLINT(runtime/references) + return iterator(SubIterGenerator::end(c)); + } + static iterator end(container_type& c) { // NOLINT(runtime/references) + return iterator(SubIterGenerator::begin(c)); + } + static const_iterator begin(const container_type& c) { + return const_iterator(SubIterGenerator::end(c)); + } + static const_iterator end(const container_type& c) { + return const_iterator(SubIterGenerator::begin(c)); + } +}; + +// C: the container type +// Iter: the type of mutable iterator to generate +// ConstIter: the type of constant iterator to generate +// IterGenerator: a policy type that returns native iterators from a C +template > +class iterator_view_helper { + public: + using container_type = C; + using iterator = Iter; + using const_iterator = ConstIter; + using value_type = typename std::iterator_traits::value_type; + using size_type = typename internal::container_traits::size_type; + + explicit iterator_view_helper( + container_type& c) // NOLINT(runtime/references) + : c_(&c) { + } + + iterator begin() { + return iterator(IterGenerator::begin(container())); + } + iterator end() { + return iterator(IterGenerator::end(container())); + } + const_iterator begin() const { + return const_iterator(IterGenerator::begin(container())); + } + const_iterator end() const { + return const_iterator(IterGenerator::end(container())); + } + const_iterator cbegin() const { + return begin(); + } + const_iterator cend() const { + return end(); + } + const container_type& container() const { + return *c_; + } + container_type& container() { + return *c_; + } + + bool empty() const { + return begin() == end(); + } + size_type size() const { + return c_->size(); + } + + private: + container_type* c_; +}; + +template > +class const_iterator_view_helper { + public: + using container_type = C; + using const_iterator = ConstIter; + using value_type = typename std::iterator_traits::value_type; + using size_type = typename internal::container_traits::size_type; + + explicit const_iterator_view_helper(const container_type& c) : c_(&c) { + } + + // Allow implicit conversion from the corresponding iterator_view_helper. + // Erring on the side of constness should be allowed. E.g.: + // MyMap m; + // key_view_type::type keys = key_view(m); // ok + // key_view_type::type const_keys = key_view(m); // ok + template + const_iterator_view_helper(const iterator_view_helper& v) + : c_(&v.container()) { + } + + const_iterator begin() const { + return const_iterator(IterGenerator::begin(container())); + } + const_iterator end() const { + return const_iterator(IterGenerator::end(container())); + } + const_iterator cbegin() const { + return begin(); + } + const_iterator cend() const { + return end(); + } + const container_type& container() const { + return *c_; + } + + bool empty() const { + return begin() == end(); + } + size_type size() const { + return c_->size(); + } + + private: + const container_type* c_; +}; + +} // namespace internal + +// Note: The views like value_view, key_view should be in gtl namespace. +// Currently there are lot of callers that reference the methods in the global +// namespace. +// +// Traits to provide a typedef abstraction for the return value +// of the key_view() and value_view() functions, such that +// they can be declared as: +// +// template key_view_t key_view(C& c); +// template value_view_t value_view(C& c); +// +// This abstraction allows callers of these functions to use readable +// type names, and allows the maintainers of iterator_adaptors.h to +// change the return types if needed without updating callers. + +template +struct key_view_type { + using type = internal::iterator_view_helper< + C, + iterator_first, + iterator_first>; +}; + +template +struct key_view_type { + using type = internal:: + const_iterator_view_helper>; +}; + +template +struct value_view_type { + using type = internal::iterator_view_helper< + C, + iterator_second, + iterator_second>; +}; + +template +struct value_view_type { + using type = internal::const_iterator_view_helper< + C, + iterator_second>; +}; + +// The key_view and value_view functions provide pretty ways to iterate either +// the keys or the values of a map using range based for loops. +// +// Example: +// hash_map my_map; +// ... +// for (string val : value_view(my_map)) { +// ... +// } +// +// Note: If you pass a temporary container to key_view or value_view, be careful +// that the temporary container outlives the wrapper view to avoid dangling +// references. +// This is fine: PublishAll(value_view(Make()); +// This is not: for (const auto& v : value_view(Make())) Publish(v); + +template +typename key_view_type::type key_view( + C& map) { // NOLINT(runtime/references) + return typename key_view_type::type(map); +} + +template +typename key_view_type::type key_view(const C& map) { + return typename key_view_type::type(map); +} + +template +typename value_view_type::type value_view( + C& map) { // NOLINT(runtime/references) + return typename value_view_type::type(map); +} + +template +typename value_view_type::type value_view(const C& map) { + return typename value_view_type::type(map); +} + +// Abstract container view that dereferences the pointer-like .second member +// of a container's std::pair elements, such as the elements of std::map +// or of std::vector>. +// +// Example: +// map elements; +// for (const string& element : deref_second_view(elements)) { +// ... +// } +// +// Note: If you pass a temporary container to deref_second_view, be careful that +// the temporary container outlives the deref_second_view to avoid dangling +// references. +// This is fine: PublishAll(deref_second_view(Make()); +// This is not: for (const auto& v : deref_second_view(Make())) { +// Publish(v); +// } + +template +struct deref_second_view_type { + using type = internal::iterator_view_helper< + C, + iterator_second_ptr, + iterator_second_ptr>; +}; + +template +struct deref_second_view_type { + using type = internal::const_iterator_view_helper< + C, + iterator_second_ptr>; +}; + +template +typename deref_second_view_type::type deref_second_view( + C& map) { // NOLINT(runtime/references) + return typename deref_second_view_type::type(map); +} + +template +typename deref_second_view_type::type deref_second_view(const C& map) { + return typename deref_second_view_type::type(map); +} + +// Abstract container view that dereferences pointer elements. +// +// Example: +// vector elements; +// for (const string& element : deref_view(elements)) { +// ... +// } +// +// Note: If you pass a temporary container to deref_view, be careful that the +// temporary container outlives the deref_view to avoid dangling references. +// This is fine: PublishAll(deref_view(Make()); +// This is not: for (const auto& v : deref_view(Make())) { Publish(v); } + +template +struct deref_view_type { + using type = + internal::iterator_view_helper, + iterator_ptr>; +}; + +template +struct deref_view_type { + using type = internal:: + const_iterator_view_helper>; +}; + +template +typename deref_view_type::type deref_view( + C& c) { // NOLINT(runtime/references) + return typename deref_view_type::type(c); +} + +template +typename deref_view_type::type deref_view(const C& c) { + return typename deref_view_type::type(c); +} + +// Abstract container view that iterates backwards. +// +// Example: +// vector elements; +// for (const string& element : reversed_view(elements)) { +// ... +// } +// +// Note: If you pass a temporary container to reversed_view_type, be careful +// that the temporary container outlives the reversed_view to avoid dangling +// references. This is fine: PublishAll(reversed_view(Make()); +// This is not: for (const auto& v : reversed_view(Make())) { Publish(v); } + +template +struct reversed_view_type { + private: + using policy = + internal::ReversingIterGeneratorAdaptor>; + + public: + using type = internal::iterator_view_helper; +}; + +template +struct reversed_view_type { + private: + using policy = + internal::ReversingIterGeneratorAdaptor>; + + public: + using type = internal:: + const_iterator_view_helper; +}; + +template +typename reversed_view_type::type reversed_view( + C& c) { // NOLINT(runtime/references) + return typename reversed_view_type::type(c); +} + +template +typename reversed_view_type::type reversed_view(const C& c) { + return typename reversed_view_type::type(c); +} + +} // namespace util +} // namespace firestore +} // namespace firebase + +#endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_ITERATOR_ADAPTORS_H_ -- cgit v1.2.3