From 0ad7994f10624cd1538b1287e56cae5ac9c0cb40 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 23 Feb 2022 06:56:15 -0800 Subject: Export of internal Abseil changes -- 91d76b3ac9edff91f206d9eee60423c39eeeaf93 by Derek Mauro : Internal change PiperOrigin-RevId: 430442277 -- 9f8a87bcc5cc5b0fd8b7f0318f37d152fd8bea06 by Evan Brown : Small refactoring to work towards allowing for node_btree_* containers. - Change common_params::transfer to rely on slot_policy transfer instead of manually doing construct/destruct. Transfer is not construct/destruct for node containers. - Move maps' value_compare into btree.h from btree_map.h so it can be reused for node_btree_map.h. - Also add a test for maps' value_compare protected members. PiperOrigin-RevId: 430245542 -- 0126e0b6295342317d9c9f0a66e2d7009b858426 by Martijn Vels : Add CordRepSubString::Create function with hard checks on IsFlat() | IsExternal() This hardens internal invariants, IsFlat() || IsExternal() is a cheap, single predicted branch, and removes boilerplate code from cord.cc PiperOrigin-RevId: 429676041 -- ed98a92af49d9e238d9f1d1b69fb4eddcd1ccbc7 by Abseil Team : tweaks to status.h documentation to reflect general-purpose communication PiperOrigin-RevId: 429584104 GitOrigin-RevId: 91d76b3ac9edff91f206d9eee60423c39eeeaf93 Change-Id: I54d6d116a564f86a842b983ca76559bf9b388f72 --- absl/container/btree_map.h | 31 ++++-------------- absl/container/btree_set.h | 21 ++++++------ absl/container/btree_test.cc | 16 ++++++++++ absl/container/internal/btree.h | 36 +++++++++++++++++---- absl/status/status.h | 10 +++--- absl/strings/cord.cc | 30 +++--------------- absl/strings/cord_test.cc | 21 +++--------- absl/strings/internal/cord_internal.cc | 7 ++++ absl/strings/internal/cord_internal.h | 58 ++++++++++++++++++++++++++-------- 9 files changed, 129 insertions(+), 101 deletions(-) diff --git a/absl/container/btree_map.h b/absl/container/btree_map.h index ad484ce0..286817f1 100644 --- a/absl/container/btree_map.h +++ b/absl/container/btree_map.h @@ -59,7 +59,7 @@ ABSL_NAMESPACE_BEGIN namespace container_internal { template + int TargetNodeSize, bool IsMulti> struct map_params; } // namespace container_internal @@ -85,7 +85,7 @@ class btree_map : public container_internal::btree_map_container< container_internal::btree>> { + /*IsMulti=*/false>>> { using Base = typename btree_map::btree_map_container; public: @@ -507,7 +507,7 @@ class btree_multimap : public container_internal::btree_multimap_container< container_internal::btree>> { + /*IsMulti=*/true>>> { using Base = typename btree_multimap::btree_multimap_container; public: @@ -817,9 +817,9 @@ namespace container_internal { // A parameters structure for holding the type parameters for a btree_map. // Compare and Alloc should be nothrow copy-constructible. template -struct map_params : common_params> { + int TargetNodeSize, bool IsMulti> +struct map_params : common_params> { using super_type = typename map_params::common_params; using mapped_type = Data; // This type allows us to move keys when it is safe to do so. It is safe @@ -829,25 +829,6 @@ struct map_params : common_params - friend class btree; - - protected: - explicit value_compare(original_key_compare c) : comp(std::move(c)) {} - - original_key_compare comp; // NOLINT - - public: - auto operator()(const value_type &lhs, const value_type &rhs) const - -> decltype(comp(lhs.first, rhs.first)) { - return comp(lhs.first, rhs.first); - } - }; - using is_map_container = std::true_type; - template static auto key(const V &value) -> decltype(value.first) { return value.first; diff --git a/absl/container/btree_set.h b/absl/container/btree_set.h index 78826830..7b6655ad 100644 --- a/absl/container/btree_set.h +++ b/absl/container/btree_set.h @@ -61,7 +61,7 @@ template struct set_slot_policy; template + bool IsMulti> struct set_params; } // namespace container_internal @@ -87,7 +87,7 @@ class btree_set : public container_internal::btree_set_container< container_internal::btree>> { + /*IsMulti=*/false>>> { using Base = typename btree_set::btree_set_container; public: @@ -427,7 +427,7 @@ class btree_multiset : public container_internal::btree_multiset_container< container_internal::btree>> { + /*IsMulti=*/true>>> { using Base = typename btree_multiset::btree_multiset_container; public: @@ -756,6 +756,12 @@ struct set_slot_policy { absl::allocator_traits::destroy(*alloc, slot); } + template + static void transfer(Alloc *alloc, slot_type *new_slot, slot_type *old_slot) { + construct(alloc, new_slot, old_slot); + destroy(alloc, old_slot); + } + template static void swap(Alloc * /*alloc*/, slot_type *a, slot_type *b) { using std::swap; @@ -771,14 +777,11 @@ struct set_slot_policy { // A parameters structure for holding the type parameters for a btree_set. // Compare and Alloc should be nothrow copy-constructible. template -struct set_params : common_params> { + bool IsMulti> +struct set_params : common_params> { using value_type = Key; using slot_type = typename set_params::common_params::slot_type; - using value_compare = - typename set_params::common_params::original_key_compare; - using is_map_container = std::false_type; template static const V &key(const V &value) { diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc index e829e0ba..4d4c64b2 100644 --- a/absl/container/btree_test.cc +++ b/absl/container/btree_test.cc @@ -1762,6 +1762,22 @@ TEST(Btree, ValueComp) { EXPECT_FALSE(m2.value_comp()(std::make_pair("b", 0), std::make_pair("a", 0))); } +// Test that we have the protected members from the std::map::value_compare API. +// See https://en.cppreference.com/w/cpp/container/map/value_compare. +TEST(Btree, MapValueCompProtected) { + struct key_compare { + bool operator()(int l, int r) const { return l < r; } + int id; + }; + using value_compare = absl::btree_map::value_compare; + struct value_comp_child : public value_compare { + explicit value_comp_child(key_compare kc) : value_compare(kc) {} + int GetId() const { return comp.id; } + }; + value_comp_child c(key_compare{10}); + EXPECT_EQ(c.GetId(), 10); +} + TEST(Btree, DefaultConstruction) { absl::btree_set s; absl::btree_map m; diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index 6c10b00f..a22c9bd7 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -335,8 +335,27 @@ constexpr bool compare_has_valid_result_type() { std::is_convertible::value; } +template +class map_value_compare { + template + friend class btree; + + // Note: this `protected` is part of the API of std::map::value_compare. See + // https://en.cppreference.com/w/cpp/container/map/value_compare. + protected: + explicit map_value_compare(original_key_compare c) : comp(std::move(c)) {} + + original_key_compare comp; // NOLINT + + public: + auto operator()(const value_type &lhs, const value_type &rhs) const + -> decltype(comp(lhs.first, rhs.first)) { + return comp(lhs.first, rhs.first); + } +}; + template + bool IsMulti, bool IsMap, typename SlotPolicy> struct common_params { using original_key_compare = Compare; @@ -384,6 +403,12 @@ struct common_params { using reference = value_type &; using const_reference = const value_type &; + using value_compare = + absl::conditional_t, + original_key_compare>; + using is_map_container = std::integral_constant; + // For the given lookup key type, returns whether we can have multiple // equivalent keys in the btree. If this is a multi-container, then we can. // Otherwise, we can have multiple equivalent keys only if all of the @@ -394,9 +419,9 @@ struct common_params { // that we know has the same equivalence classes for all lookup types. template constexpr static bool can_have_multiple_equivalent_keys() { - return Multi || (IsTransparent::value && - !std::is_same::value && - !kIsKeyCompareStringAdapted); + return IsMulti || (IsTransparent::value && + !std::is_same::value && + !kIsKeyCompareStringAdapted); } enum { @@ -435,8 +460,7 @@ struct common_params { slot_policy::destroy(alloc, slot); } static void transfer(Alloc *alloc, slot_type *new_slot, slot_type *old_slot) { - construct(alloc, new_slot, old_slot); - destroy(alloc, old_slot); + slot_policy::transfer(alloc, new_slot, old_slot); } static void swap(Alloc *alloc, slot_type *a, slot_type *b) { slot_policy::swap(alloc, a, b); diff --git a/absl/status/status.h b/absl/status/status.h index db4b340a..2d003ce6 100644 --- a/absl/status/status.h +++ b/absl/status/status.h @@ -24,11 +24,11 @@ // * A set of helper functions for creating status codes and checking their // values // -// Within Google, `absl::Status` is the primary mechanism for gracefully -// handling errors across API boundaries (and in particular across RPC -// boundaries). Some of these errors may be recoverable, but others may not. -// Most functions that can produce a recoverable error should be designed to -// return an `absl::Status` (or `absl::StatusOr`). +// Within Google, `absl::Status` is the primary mechanism for communicating +// errors in C++, and is used to represent error state in both in-process +// library calls as well as RPC calls. Some of these errors may be recoverable, +// but others may not. Most functions that can produce a recoverable error +// should be designed to return an `absl::Status` (or `absl::StatusOr`). // // Example: // diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc index 6547c2da..b65dc58b 100644 --- a/absl/strings/cord.cc +++ b/absl/strings/cord.cc @@ -151,23 +151,6 @@ void InitializeCordRepExternal(absl::string_view data, CordRepExternal* rep) { } // namespace cord_internal -static CordRep* NewSubstring(CordRep* child, size_t offset, size_t length) { - // Never create empty substring nodes - if (length == 0) { - CordRep::Unref(child); - return nullptr; - } else { - CordRepSubstring* rep = new CordRepSubstring(); - assert(child->IsExternal() || child->IsFlat()); - assert((offset + length) <= child->length); - rep->length = length; - rep->tag = cord_internal::SUBSTRING; - rep->start = offset; - rep->child = child; - return VerifyTree(rep); - } -} - // Creates a CordRep from the provided string. If the string is large enough, // and not wasteful, we move the string into an external cord rep, preserving // the already allocated string contents. @@ -643,7 +626,7 @@ static CordRep* RemovePrefixFrom(CordRep* node, size_t n) { start += node->substring()->start; node = node->substring()->child; } - node = NewSubstring(CordRep::Ref(node), start, len); + node = CordRepSubstring::Create(CordRep::Ref(node), start, len); } while (!rhs_stack.empty()) { node = Concat(node, CordRep::Ref(rhs_stack.back())); @@ -678,7 +661,7 @@ static CordRep* RemoveSuffixFrom(CordRep* node, size_t n) { start = node->substring()->start; node = node->substring()->child; } - node = NewSubstring(CordRep::Ref(node), start, len); + node = CordRepSubstring::Create(CordRep::Ref(node), start, len); } while (!lhs_stack.empty()) { node = Concat(CordRep::Ref(lhs_stack.back()), node); @@ -768,7 +751,7 @@ static CordRep* NewSubRange(CordRep* node, size_t pos, size_t n) { pos += node->substring()->start; node = node->substring()->child; } - results.push_back(NewSubstring(CordRep::Ref(node), pos, n)); + results.push_back(CordRepSubstring::Create(CordRep::Ref(node), pos, n)); } } while (!todo.empty()); assert(results.size() == 1); @@ -1157,12 +1140,7 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { : payload->flat()->Data(); const size_t offset = current_chunk_.data() - data; - CordRepSubstring* tree = new CordRepSubstring(); - tree->tag = cord_internal::SUBSTRING; - tree->length = n; - tree->start = offset; - tree->child = CordRep::Ref(payload); - + auto* tree = CordRepSubstring::Create(CordRep::Ref(payload), offset, n); subcord.contents_.EmplaceTree(VerifyTree(tree), method); bytes_remaining_ -= n; current_chunk_.remove_prefix(n); diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc index 9dcc4ce5..f69209de 100644 --- a/absl/strings/cord_test.cc +++ b/absl/strings/cord_test.cc @@ -56,6 +56,7 @@ using absl::cord_internal::CordRepCrc; using absl::cord_internal::CordRepExternal; using absl::cord_internal::CordRepFlat; using absl::cord_internal::CordRepSubstring; +using absl::cord_internal::CordzUpdateTracker; using absl::cord_internal::kFlatOverhead; using absl::cord_internal::kMaxFlatLength; @@ -212,14 +213,9 @@ class CordTestPeer { ABSL_RAW_CHECK(src.ExpectedChecksum() == absl::nullopt, "Can not be hardened"); Cord cord; - auto* rep = new cord_internal::CordRepSubstring; - rep->tag = cord_internal::SUBSTRING; - rep->child = cord_internal::CordRep::Ref( - cord_internal::SkipCrcNode(src.contents_.tree())); - rep->start = offset; - rep->length = length; - cord.contents_.EmplaceTree(rep, - cord_internal::CordzUpdateTracker::kSubCord); + auto* tree = cord_internal::SkipCrcNode(src.contents_.tree()); + auto* rep = CordRepSubstring::Create(CordRep::Ref(tree), offset, length); + cord.contents_.EmplaceTree(rep, CordzUpdateTracker::kSubCord); return cord; } }; @@ -645,15 +641,6 @@ TEST_P(CordTest, TryFlatSubstrExternal) { EXPECT_EQ(sub.TryFlat(), "ell"); } -TEST_P(CordTest, TryFlatSubstrConcat) { - absl::Cord c = absl::MakeFragmentedCord({"hello", " world"}); - absl::Cord sub = absl::CordTestPeer::MakeSubstring(c, 1, c.size() - 1); - MaybeHarden(sub); - EXPECT_EQ(sub.TryFlat(), absl::nullopt); - c.RemovePrefix(1); - EXPECT_EQ(c.TryFlat(), absl::nullopt); -} - TEST_P(CordTest, TryFlatCommonlyAssumedInvariants) { // The behavior tested below is not part of the API contract of Cord, but it's // something we intend to be true in our current implementation. This test diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc index 06119350..b6b06cfa 100644 --- a/absl/strings/internal/cord_internal.cc +++ b/absl/strings/internal/cord_internal.cc @@ -17,11 +17,13 @@ #include #include +#include "absl/base/internal/raw_logging.h" #include "absl/container/inlined_vector.h" #include "absl/strings/internal/cord_rep_btree.h" #include "absl/strings/internal/cord_rep_crc.h" #include "absl/strings/internal/cord_rep_flat.h" #include "absl/strings/internal/cord_rep_ring.h" +#include "absl/strings/str_cat.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -33,6 +35,11 @@ ABSL_CONST_INIT std::atomic shallow_subcords_enabled( kCordShallowSubcordsDefault); ABSL_CONST_INIT std::atomic cord_btree_exhaustive_validation(false); +void LogFatalNodeType(CordRep* rep) { + ABSL_INTERNAL_LOG(FATAL, absl::StrCat("Unexpected node type: ", + static_cast(rep->tag))); +} + void CordRep::Destroy(CordRep* rep) { assert(rep != nullptr); diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h index 8db6aa6d..ece3db15 100644 --- a/absl/strings/internal/cord_internal.h +++ b/absl/strings/internal/cord_internal.h @@ -21,6 +21,7 @@ #include #include +#include "absl/base/attributes.h" #include "absl/base/config.h" #include "absl/base/internal/endian.h" #include "absl/base/internal/invoke.h" @@ -33,6 +34,19 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace cord_internal { +// The overhead of a vtable is too much for Cord, so we roll our own subclasses +// using only a single byte to differentiate classes from each other - the "tag" +// byte. Define the subclasses first so we can provide downcasting helper +// functions in the base class. +struct CordRep; +struct CordRepConcat; +struct CordRepExternal; +struct CordRepFlat; +struct CordRepSubstring; +struct CordRepCrc; +class CordRepRing; +class CordRepBtree; + class CordzInfo; // Default feature enable states for cord ring buffers @@ -74,6 +88,9 @@ enum Constants { kMaxBytesToCopy = 511 }; +// Emits a fatal error "Unexpected node type: xyz" and aborts the program. +ABSL_ATTRIBUTE_NORETURN void LogFatalNodeType(CordRep* rep); + // Compact class for tracking the reference count and state flags for CordRep // instances. Data is stored in an atomic int32_t for compactness and speed. class RefcountAndFlags { @@ -156,19 +173,6 @@ class RefcountAndFlags { std::atomic count_; }; -// The overhead of a vtable is too much for Cord, so we roll our own subclasses -// using only a single byte to differentiate classes from each other - the "tag" -// byte. Define the subclasses first so we can provide downcasting helper -// functions in the base class. - -struct CordRepConcat; -struct CordRepExternal; -struct CordRepFlat; -struct CordRepSubstring; -struct CordRepCrc; -class CordRepRing; -class CordRepBtree; - // Various representations that we allow enum CordRepKind { UNUSED_0 = 0, @@ -276,6 +280,12 @@ struct CordRep { struct CordRepSubstring : public CordRep { size_t start; // Starting offset of substring in child CordRep* child; + + // Creates a substring on `child`, adopting a reference on `child`. + // Requires `child` to be either a flat or external node, and `pos` and `n` to + // form a non-empty partial sub range of `'child`, i.e.: + // `n > 0 && n < length && n + pos <= length` + static inline CordRepSubstring* Create(CordRep* child, size_t pos, size_t n); }; // Type for function pointer that will invoke the releaser function and also @@ -339,6 +349,28 @@ struct CordRepExternalImpl } }; +inline CordRepSubstring* CordRepSubstring::Create(CordRep* child, size_t pos, + size_t n) { + assert(child != nullptr); + assert(n > 0); + assert(n < child->length); + assert(pos < child->length); + assert(n <= child->length - pos); + + // TODO(b/217376272): Harden internal logic. + // Move to strategical places inside the Cord logic and make this an assert. + if (ABSL_PREDICT_FALSE(!(child->IsExternal() || child->IsFlat()))) { + LogFatalNodeType(child); + } + + CordRepSubstring* rep = new CordRepSubstring(); + rep->length = n; + rep->tag = SUBSTRING; + rep->start = pos; + rep->child = child; + return rep; +} + inline void CordRepExternal::Delete(CordRep* rep) { assert(rep != nullptr && rep->IsExternal()); auto* rep_external = static_cast(rep); -- cgit v1.2.3