From 0f86336b6939ea673cc1cbe29189286cae67d63a Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Fri, 31 Jan 2020 10:09:12 -0800 Subject: Export of internal Abseil changes -- 0b924fe4e9871200792617329d32beb8356daa9b by Derek Mauro : Use less threads in the GetTID() test to avoid test timeouts PiperOrigin-RevId: 292566826 -- 0b519c4fd48d61b7c4ea94ed6a6be6e981b9c51a by Abseil Team : Internal change. PiperOrigin-RevId: 292563778 -- 3204f6e07bcc2b5e9098d45f1a20998f25ab808e by Abseil Team : Internal change. PiperOrigin-RevId: 292550551 -- 09fbbe73833478d3f26f3e33c8291b991fd3be51 by Derek Mauro : Add a debug bounds-check to absl::string_view::operator[] string_view accesses that are out-of-bounds are undefined behavior: https://en.cppreference.com/w/cpp/string/basic_string_view/operator_at This change causes code to abort in debug mode, indicating a bug and possibly a security issue like a buffer overflow. Code broken by this change should be investigated. PiperOrigin-RevId: 292544735 -- bf2c19cb45682628f963d4067c0cd6deed7e656d by Derek Mauro : Add debug assertions to absl::string_view::front and absl::string_view::back Calling front() or back() on an empty string_view is undefined behavior. This assertion is to help catch broken code. https://en.cppreference.com/w/cpp/string/basic_string_view/front https://en.cppreference.com/w/cpp/string/basic_string_view/back PiperOrigin-RevId: 292453255 -- 47f573679b322f8c0fd2cb037cc87e7bc822ac6b by Xiaoyi Zhang : Release functional/CMakeList.txt. PiperOrigin-RevId: 292417025 GitOrigin-RevId: 0b924fe4e9871200792617329d32beb8356daa9b Change-Id: Ie6980fb1ac351d72a2ce4468f25bd31db396f88a --- absl/CMakeLists.txt | 1 + absl/base/internal/sysinfo_test.cc | 4 +- absl/container/btree_test.cc | 32 +++++-------- absl/container/internal/btree.h | 79 +++++++++++-------------------- absl/container/internal/btree_container.h | 6 +-- absl/functional/CMakeLists.txt | 72 ++++++++++++++++++++++++++++ absl/strings/string_view.h | 12 +++-- absl/strings/string_view_test.cc | 23 +++++++++ 8 files changed, 151 insertions(+), 78 deletions(-) create mode 100644 absl/functional/CMakeLists.txt diff --git a/absl/CMakeLists.txt b/absl/CMakeLists.txt index a1b1f8d..26693ea 100644 --- a/absl/CMakeLists.txt +++ b/absl/CMakeLists.txt @@ -19,6 +19,7 @@ add_subdirectory(algorithm) add_subdirectory(container) add_subdirectory(debugging) add_subdirectory(flags) +add_subdirectory(functional) add_subdirectory(hash) add_subdirectory(memory) add_subdirectory(meta) diff --git a/absl/base/internal/sysinfo_test.cc b/absl/base/internal/sysinfo_test.cc index cdec9b6..fa8b88b 100644 --- a/absl/base/internal/sysinfo_test.cc +++ b/absl/base/internal/sysinfo_test.cc @@ -59,8 +59,8 @@ TEST(SysinfoTest, GetTID) { #endif // Test that TIDs are unique to each thread. // Uses a few loops to exercise implementations that reallocate IDs. - for (int i = 0; i < 32; ++i) { - constexpr int kNumThreads = 64; + for (int i = 0; i < 10; ++i) { + constexpr int kNumThreads = 10; Barrier all_threads_done(kNumThreads); std::vector threads; diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc index af8ee00..9edf38f 100644 --- a/absl/container/btree_test.cc +++ b/absl/container/btree_test.cc @@ -180,9 +180,7 @@ class base_checker { const_iterator find(const key_type &key) const { return iter_check(tree_.find(key), checker_.find(key)); } - bool contains(const key_type &key) const { - return find(key) != end(); - } + bool contains(const key_type &key) const { return find(key) != end(); } size_type count(const key_type &key) const { size_type res = checker_.count(key); EXPECT_EQ(res, tree_.count(key)); @@ -240,8 +238,10 @@ class base_checker { ++checker_end; } } - checker_.erase(checker_begin, checker_end); - tree_.erase(begin, end); + const auto checker_ret = checker_.erase(checker_begin, checker_end); + const auto tree_ret = tree_.erase(begin, end); + EXPECT_EQ(std::distance(checker_.begin(), checker_ret), + std::distance(tree_.begin(), tree_ret)); EXPECT_EQ(tree_.size(), checker_.size()); EXPECT_EQ(tree_.size(), size - count); } @@ -326,7 +326,7 @@ class unique_checker : public base_checker { unique_checker(const unique_checker &x) : super_type(x) {} template unique_checker(InputIterator b, InputIterator e) : super_type(b, e) {} - unique_checker& operator=(const unique_checker&) = default; + unique_checker &operator=(const unique_checker &) = default; // Insertion routines. std::pair insert(const value_type &x) { @@ -374,7 +374,7 @@ class multi_checker : public base_checker { multi_checker(const multi_checker &x) : super_type(x) {} template multi_checker(InputIterator b, InputIterator e) : super_type(b, e) {} - multi_checker& operator=(const multi_checker&) = default; + multi_checker &operator=(const multi_checker &) = default; // Insertion routines. iterator insert(const value_type &x) { @@ -868,7 +868,7 @@ struct CompareIntToString { struct NonTransparentCompare { template - bool operator()(const T& t, const U& u) const { + bool operator()(const T &t, const U &u) const { // Treating all comparators as transparent can cause inefficiencies (see // N3657 C++ proposal). Test that for comparators without 'is_transparent' // alias (like this one), we do not attempt heterogeneous lookup. @@ -1005,21 +1005,15 @@ class StringLike { public: StringLike() = default; - StringLike(const char* s) : s_(s) { // NOLINT + StringLike(const char *s) : s_(s) { // NOLINT ++constructor_calls_; } - bool operator<(const StringLike& a) const { - return s_ < a.s_; - } + bool operator<(const StringLike &a) const { return s_ < a.s_; } - static void clear_constructor_call_count() { - constructor_calls_ = 0; - } + static void clear_constructor_call_count() { constructor_calls_ = 0; } - static int constructor_calls() { - return constructor_calls_; - } + static int constructor_calls() { return constructor_calls_; } private: static int constructor_calls_; @@ -1476,7 +1470,7 @@ struct NoDefaultCtor { int num; explicit NoDefaultCtor(int i) : num(i) {} - friend bool operator<(const NoDefaultCtor& a, const NoDefaultCtor& b) { + friend bool operator<(const NoDefaultCtor &a, const NoDefaultCtor &b) { return a.num < b.num; } }; diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index aef861d..707e9f0 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -882,18 +882,14 @@ struct btree_iterator { } // Accessors for the key/value the iterator is pointing at. - reference operator*() const { - return node->value(position); - } - pointer operator->() const { - return &node->value(position); - } + reference operator*() const { return node->value(position); } + pointer operator->() const { return &node->value(position); } - btree_iterator& operator++() { + btree_iterator &operator++() { increment(); return *this; } - btree_iterator& operator--() { + btree_iterator &operator--() { decrement(); return *this; } @@ -961,7 +957,7 @@ class btree { static node_type *EmptyNode() { #ifdef _MSC_VER - static EmptyNodeType* empty_node = new EmptyNodeType; + static EmptyNodeType *empty_node = new EmptyNodeType; // This assert fails on some other construction methods. assert(empty_node->parent == empty_node); return empty_node; @@ -980,12 +976,9 @@ class btree { struct node_stats { using size_type = typename Params::size_type; - node_stats(size_type l, size_type i) - : leaf_nodes(l), - internal_nodes(i) { - } + node_stats(size_type l, size_type i) : leaf_nodes(l), internal_nodes(i) {} - node_stats& operator+=(const node_stats &x) { + node_stats &operator+=(const node_stats &x) { leaf_nodes += x.leaf_nodes; internal_nodes += x.internal_nodes; return *this; @@ -1054,25 +1047,17 @@ class btree { btree &operator=(const btree &x); btree &operator=(btree &&x) noexcept; - iterator begin() { - return iterator(leftmost(), 0); - } - const_iterator begin() const { - return const_iterator(leftmost(), 0); - } + iterator begin() { return iterator(leftmost(), 0); } + const_iterator begin() const { return const_iterator(leftmost(), 0); } iterator end() { return iterator(rightmost_, rightmost_->count()); } const_iterator end() const { return const_iterator(rightmost_, rightmost_->count()); } - reverse_iterator rbegin() { - return reverse_iterator(end()); - } + reverse_iterator rbegin() { return reverse_iterator(end()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } - reverse_iterator rend() { - return reverse_iterator(begin()); - } + reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } @@ -1160,7 +1145,7 @@ class btree { // Erases range. Returns the number of keys erased and an iterator pointing // to the element after the last erased element. - std::pair erase(iterator begin, iterator end); + std::pair erase_range(iterator begin, iterator end); // Erases the specified key from the btree. Returns 1 if an element was // erased and 0 otherwise. @@ -1242,9 +1227,7 @@ class btree { } // The number of internal, leaf and total nodes used by the btree. - size_type leaf_nodes() const { - return internal_stats(root()).leaf_nodes; - } + size_type leaf_nodes() const { return internal_stats(root()).leaf_nodes; } size_type internal_nodes() const { return internal_stats(root()).internal_nodes; } @@ -1257,11 +1240,9 @@ class btree { size_type bytes_used() const { node_stats stats = internal_stats(root()); if (stats.leaf_nodes == 1 && stats.internal_nodes == 0) { - return sizeof(*this) + - node_type::LeafSize(root()->max_count()); + return sizeof(*this) + node_type::LeafSize(root()->max_count()); } else { - return sizeof(*this) + - stats.leaf_nodes * node_type::LeafSize() + + return sizeof(*this) + stats.leaf_nodes * node_type::LeafSize() + stats.internal_nodes * node_type::InternalSize(); } } @@ -1294,9 +1275,7 @@ class btree { } // The allocator used by the btree. - allocator_type get_allocator() const { - return allocator(); - } + allocator_type get_allocator() const { return allocator(); } private: // Internal accessor routines. @@ -1326,11 +1305,11 @@ class btree { } // Node creation/deletion routines. - node_type* new_internal_node(node_type *parent) { + node_type *new_internal_node(node_type *parent) { node_type *p = allocate(node_type::InternalSize()); return node_type::init_internal(p, parent); } - node_type* new_leaf_node(node_type *parent) { + node_type *new_leaf_node(node_type *parent) { node_type *p = allocate(node_type::LeafSize()); return node_type::init_leaf(p, parent, kNodeValues); } @@ -1431,8 +1410,8 @@ class btree { void internal_clear(node_type *node); // Verifies the tree structure of node. - int internal_verify(const node_type *node, - const key_type *lo, const key_type *hi) const; + int internal_verify(const node_type *node, const key_type *lo, + const key_type *hi) const; node_stats internal_stats(const node_type *node) const { // The root can be a static empty node. @@ -2098,7 +2077,7 @@ auto btree

::rebalance_after_delete(iterator iter) -> iterator { } template -auto btree

::erase(iterator begin, iterator end) +auto btree

::erase_range(iterator begin, iterator end) -> std::pair { difference_type count = std::distance(begin, end); assert(count >= 0); @@ -2198,7 +2177,7 @@ auto btree

::erase_multi(const K &key) -> size_type { } // Delete all of the keys between begin and upper_bound(key). const iterator end = internal_end(internal_upper_bound(key)); - return erase(begin, end).first; + return erase_range(begin, end).first; } template @@ -2379,8 +2358,7 @@ bool btree

::try_merge_or_rebalance(iterator *iter) { // empty. This is a small optimization for the common pattern of deleting // from the front of the tree. if ((right->count() > kMinNodeValues) && - ((iter->node->count() == 0) || - (iter->position > 0))) { + ((iter->node->count() == 0) || (iter->position > 0))) { int to_move = (right->count() - iter->node->count()) / 2; to_move = (std::min)(to_move, right->count() - 1); iter->node->rebalance_right_to_left(to_move, right, mutable_allocator()); @@ -2578,8 +2556,8 @@ void btree

::internal_clear(node_type *node) { } template -int btree

::internal_verify( - const node_type *node, const key_type *lo, const key_type *hi) const { +int btree

::internal_verify(const node_type *node, const key_type *lo, + const key_type *hi) const { assert(node->count() > 0); assert(node->count() <= node->max_count()); if (lo) { @@ -2597,10 +2575,9 @@ int btree

::internal_verify( assert(node->child(i) != nullptr); assert(node->child(i)->parent() == node); assert(node->child(i)->position() == i); - count += internal_verify( - node->child(i), - (i == 0) ? lo : &node->key(i - 1), - (i == node->count()) ? hi : &node->key(i)); + count += + internal_verify(node->child(i), (i == 0) ? lo : &node->key(i - 1), + (i == node->count()) ? hi : &node->key(i)); } } return count; diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h index 3e6ff4b..f2e4c3a 100644 --- a/absl/container/internal/btree_container.h +++ b/absl/container/internal/btree_container.h @@ -136,7 +136,7 @@ class btree_container { iterator erase(const_iterator iter) { return tree_.erase(iterator(iter)); } iterator erase(iterator iter) { return tree_.erase(iter); } iterator erase(const_iterator first, const_iterator last) { - return tree_.erase(iterator(first), iterator(last)).second; + return tree_.erase_range(iterator(first), iterator(last)).second; } // Extract routines. @@ -465,7 +465,7 @@ class btree_map_container : public btree_set_container { // and then using `k` unsequenced. This is safe because the move is into a // forwarding reference and insert_unique guarantees that `key` is never // referenced after consuming `args`. - const key_type& key_ref = k; + const key_type &key_ref = k; return this->tree_.insert_unique( key_ref, std::piecewise_construct, std::forward_as_tuple(std::move(k)), std::forward_as_tuple(std::forward(args)...)); @@ -485,7 +485,7 @@ class btree_map_container : public btree_set_container { // and then using `k` unsequenced. This is safe because the move is into a // forwarding reference and insert_hint_unique guarantees that `key` is // never referenced after consuming `args`. - const key_type& key_ref = k; + const key_type &key_ref = k; return this->tree_ .insert_hint_unique(iterator(hint), key_ref, std::piecewise_construct, std::forward_as_tuple(std::move(k)), diff --git a/absl/functional/CMakeLists.txt b/absl/functional/CMakeLists.txt new file mode 100644 index 0000000..cda914f --- /dev/null +++ b/absl/functional/CMakeLists.txt @@ -0,0 +1,72 @@ +# +# Copyright 2019 The Abseil Authors. +# +# 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 +# +# https://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. +# + +absl_cc_library( + NAME + bind_front + SRCS + "internal/front_binder.h" + HDRS + "bind_front.h" + COPTS + ${ABSL_DEFAULT_COPTS} + DEPS + absl::base_internal + absl::compressed_tuple + PUBLIC +) + +absl_cc_test( + NAME + bind_front_test + SRCS + "bind_front_test.cc" + COPTS + ${ABSL_DEFAULT_COPTS} + DEPS + absl::bind_front + absl::memory + gmock_main +) + +absl_cc_library( + NAME + function_ref + SRCS + "internal/function_ref.h" + HDRS + "function_ref.h" + COPTS + ${ABSL_DEFAULT_COPTS} + DEPS + absl::base_internal + absl::meta + PUBLIC +) + +absl_cc_test( + NAME + function_ref_test + SRCS + "function_ref_test.cc" + COPTS + ${ABSL_TEST_COPTS} + DEPS + absl::function_ref + absl::memory + absl::test_instance_tracker + gmock_main +) diff --git a/absl/strings/string_view.h b/absl/strings/string_view.h index 01965b0..418dbc8 100644 --- a/absl/strings/string_view.h +++ b/absl/strings/string_view.h @@ -282,7 +282,9 @@ class string_view { // // Returns the ith element of the `string_view` using the array operator. // Note that this operator does not perform any bounds checking. - constexpr const_reference operator[](size_type i) const { return ptr_[i]; } + constexpr const_reference operator[](size_type i) const { + return ABSL_ASSERT(i < size()), ptr_[i]; + } // string_view::at() // @@ -300,12 +302,16 @@ class string_view { // string_view::front() // // Returns the first element of a `string_view`. - constexpr const_reference front() const { return ptr_[0]; } + constexpr const_reference front() const { + return ABSL_ASSERT(!empty()), ptr_[0]; + } // string_view::back() // // Returns the last element of a `string_view`. - constexpr const_reference back() const { return ptr_[size() - 1]; } + constexpr const_reference back() const { + return ABSL_ASSERT(!empty()), ptr_[size() - 1]; + } // string_view::data() // diff --git a/absl/strings/string_view_test.cc b/absl/strings/string_view_test.cc index c4fbd16..7b1d56f 100644 --- a/absl/strings/string_view_test.cc +++ b/absl/strings/string_view_test.cc @@ -818,6 +818,18 @@ TEST(StringViewTest, FrontBackSingleChar) { EXPECT_EQ(&c, &csp.back()); } +TEST(StringViewTest, FrontBackEmpty) { +#ifndef ABSL_USES_STD_STRING_VIEW +#ifndef NDEBUG + // Abseil's string_view implementation has debug assertions that check that + // front() and back() are not called on an empty string_view. + absl::string_view sv; + ABSL_EXPECT_DEATH_IF_SUPPORTED(sv.front(), ""); + ABSL_EXPECT_DEATH_IF_SUPPORTED(sv.back(), ""); +#endif +#endif +} + // `std::string_view::string_view(const char*)` calls // `std::char_traits::length(const char*)` to get the string length. In // libc++, it doesn't allow `nullptr` in the constexpr context, with the error @@ -1108,6 +1120,17 @@ TEST(StringViewTest, Noexcept) { EXPECT_TRUE(noexcept(sp.find_last_not_of('f'))); } +TEST(StringViewTest, BoundsCheck) { +#ifndef ABSL_USES_STD_STRING_VIEW +#ifndef NDEBUG + // Abseil's string_view implementation has bounds-checking in debug mode. + absl::string_view h = "hello"; + ABSL_EXPECT_DEATH_IF_SUPPORTED(h[5], ""); + ABSL_EXPECT_DEATH_IF_SUPPORTED(h[-1], ""); +#endif +#endif +} + TEST(ComparisonOpsTest, StringCompareNotAmbiguous) { EXPECT_EQ("hello", std::string("hello")); EXPECT_LT("hello", std::string("world")); -- cgit v1.2.3