diff options
Diffstat (limited to 'absl/strings/internal')
22 files changed, 693 insertions, 2185 deletions
diff --git a/absl/strings/internal/char_map.h b/absl/strings/internal/char_map.h deleted file mode 100644 index 70a90343..00000000 --- a/absl/strings/internal/char_map.h +++ /dev/null @@ -1,158 +0,0 @@ -// Copyright 2017 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. -// -// Character Map Class -// -// A fast, bit-vector map for 8-bit unsigned characters. -// This class is useful for non-character purposes as well. - -#ifndef ABSL_STRINGS_INTERNAL_CHAR_MAP_H_ -#define ABSL_STRINGS_INTERNAL_CHAR_MAP_H_ - -#include <cstddef> -#include <cstdint> -#include <cstring> - -#include "absl/base/macros.h" -#include "absl/base/port.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace strings_internal { - -class Charmap { - public: - constexpr Charmap() : m_() {} - - // Initializes with a given char*. Note that NUL is not treated as - // a terminator, but rather a char to be flicked. - Charmap(const char* str, int len) : m_() { - while (len--) SetChar(*str++); - } - - // Initializes with a given char*. NUL is treated as a terminator - // and will not be in the charmap. - explicit Charmap(const char* str) : m_() { - while (*str) SetChar(*str++); - } - - constexpr bool contains(unsigned char c) const { - return (m_[c / 64] >> (c % 64)) & 0x1; - } - - // Returns true if and only if a character exists in both maps. - bool IntersectsWith(const Charmap& c) const { - for (size_t i = 0; i < ABSL_ARRAYSIZE(m_); ++i) { - if ((m_[i] & c.m_[i]) != 0) return true; - } - return false; - } - - bool IsZero() const { - for (uint64_t c : m_) { - if (c != 0) return false; - } - return true; - } - - // Containing only a single specified char. - static constexpr Charmap Char(char x) { - return Charmap(CharMaskForWord(x, 0), CharMaskForWord(x, 1), - CharMaskForWord(x, 2), CharMaskForWord(x, 3)); - } - - // Containing all the chars in the C-string 's'. - static constexpr Charmap FromString(const char* s) { - Charmap ret; - while (*s) ret = ret | Char(*s++); - return ret; - } - - // Containing all the chars in the closed interval [lo,hi]. - static constexpr Charmap Range(char lo, char hi) { - return Charmap(RangeForWord(lo, hi, 0), RangeForWord(lo, hi, 1), - RangeForWord(lo, hi, 2), RangeForWord(lo, hi, 3)); - } - - friend constexpr Charmap operator&(const Charmap& a, const Charmap& b) { - return Charmap(a.m_[0] & b.m_[0], a.m_[1] & b.m_[1], a.m_[2] & b.m_[2], - a.m_[3] & b.m_[3]); - } - - friend constexpr Charmap operator|(const Charmap& a, const Charmap& b) { - return Charmap(a.m_[0] | b.m_[0], a.m_[1] | b.m_[1], a.m_[2] | b.m_[2], - a.m_[3] | b.m_[3]); - } - - friend constexpr Charmap operator~(const Charmap& a) { - return Charmap(~a.m_[0], ~a.m_[1], ~a.m_[2], ~a.m_[3]); - } - - private: - constexpr Charmap(uint64_t b0, uint64_t b1, uint64_t b2, uint64_t b3) - : m_{b0, b1, b2, b3} {} - - static constexpr uint64_t RangeForWord(char lo, char hi, uint64_t word) { - return OpenRangeFromZeroForWord(static_cast<unsigned char>(hi) + 1, word) & - ~OpenRangeFromZeroForWord(static_cast<unsigned char>(lo), word); - } - - // All the chars in the specified word of the range [0, upper). - static constexpr uint64_t OpenRangeFromZeroForWord(uint64_t upper, - uint64_t word) { - return (upper <= 64 * word) - ? 0 - : (upper >= 64 * (word + 1)) - ? ~static_cast<uint64_t>(0) - : (~static_cast<uint64_t>(0) >> (64 - upper % 64)); - } - - static constexpr uint64_t CharMaskForWord(char x, uint64_t word) { - const auto unsigned_x = static_cast<unsigned char>(x); - return (unsigned_x / 64 == word) - ? (static_cast<uint64_t>(1) << (unsigned_x % 64)) - : 0; - } - - void SetChar(char c) { - const auto unsigned_c = static_cast<unsigned char>(c); - m_[unsigned_c / 64] |= static_cast<uint64_t>(1) << (unsigned_c % 64); - } - - uint64_t m_[4]; -}; - -// Mirror the char-classifying predicates in <cctype> -constexpr Charmap UpperCharmap() { return Charmap::Range('A', 'Z'); } -constexpr Charmap LowerCharmap() { return Charmap::Range('a', 'z'); } -constexpr Charmap DigitCharmap() { return Charmap::Range('0', '9'); } -constexpr Charmap AlphaCharmap() { return LowerCharmap() | UpperCharmap(); } -constexpr Charmap AlnumCharmap() { return DigitCharmap() | AlphaCharmap(); } -constexpr Charmap XDigitCharmap() { - return DigitCharmap() | Charmap::Range('A', 'F') | Charmap::Range('a', 'f'); -} -constexpr Charmap PrintCharmap() { return Charmap::Range(0x20, 0x7e); } -constexpr Charmap SpaceCharmap() { return Charmap::FromString("\t\n\v\f\r "); } -constexpr Charmap CntrlCharmap() { - return Charmap::Range(0, 0x7f) & ~PrintCharmap(); -} -constexpr Charmap BlankCharmap() { return Charmap::FromString("\t "); } -constexpr Charmap GraphCharmap() { return PrintCharmap() & ~SpaceCharmap(); } -constexpr Charmap PunctCharmap() { return GraphCharmap() & ~AlnumCharmap(); } - -} // namespace strings_internal -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_STRINGS_INTERNAL_CHAR_MAP_H_ diff --git a/absl/strings/internal/char_map_benchmark.cc b/absl/strings/internal/char_map_benchmark.cc deleted file mode 100644 index 5cef967b..00000000 --- a/absl/strings/internal/char_map_benchmark.cc +++ /dev/null @@ -1,61 +0,0 @@ -// Copyright 2017 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. - -#include "absl/strings/internal/char_map.h" - -#include <cstdint> - -#include "benchmark/benchmark.h" - -namespace { - -absl::strings_internal::Charmap MakeBenchmarkMap() { - absl::strings_internal::Charmap m; - uint32_t x[] = {0x0, 0x1, 0x2, 0x3, 0xf, 0xe, 0xd, 0xc}; - for (uint32_t& t : x) t *= static_cast<uint32_t>(0x11111111UL); - for (uint32_t i = 0; i < 256; ++i) { - if ((x[i / 32] >> (i % 32)) & 1) - m = m | absl::strings_internal::Charmap::Char(i); - } - return m; -} - -// Micro-benchmark for Charmap::contains. -void BM_Contains(benchmark::State& state) { - // Loop-body replicated 10 times to increase time per iteration. - // Argument continuously changed to avoid generating common subexpressions. - const absl::strings_internal::Charmap benchmark_map = MakeBenchmarkMap(); - unsigned char c = 0; - int ops = 0; - for (auto _ : state) { - ops += benchmark_map.contains(c++); - ops += benchmark_map.contains(c++); - ops += benchmark_map.contains(c++); - ops += benchmark_map.contains(c++); - ops += benchmark_map.contains(c++); - ops += benchmark_map.contains(c++); - ops += benchmark_map.contains(c++); - ops += benchmark_map.contains(c++); - ops += benchmark_map.contains(c++); - ops += benchmark_map.contains(c++); - } - benchmark::DoNotOptimize(ops); -} -BENCHMARK(BM_Contains); - -// We don't bother benchmarking Charmap::IsZero or Charmap::IntersectsWith; -// their running time is data-dependent and it is not worth characterizing -// "typical" data. - -} // namespace diff --git a/absl/strings/internal/char_map_test.cc b/absl/strings/internal/char_map_test.cc deleted file mode 100644 index d3306241..00000000 --- a/absl/strings/internal/char_map_test.cc +++ /dev/null @@ -1,172 +0,0 @@ -// Copyright 2017 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. - -#include "absl/strings/internal/char_map.h" - -#include <cctype> -#include <string> -#include <vector> - -#include "gmock/gmock.h" -#include "gtest/gtest.h" - -namespace { - -constexpr absl::strings_internal::Charmap everything_map = - ~absl::strings_internal::Charmap(); -constexpr absl::strings_internal::Charmap nothing_map{}; - -TEST(Charmap, AllTests) { - const absl::strings_internal::Charmap also_nothing_map("", 0); - ASSERT_TRUE(everything_map.contains('\0')); - ASSERT_TRUE(!nothing_map.contains('\0')); - ASSERT_TRUE(!also_nothing_map.contains('\0')); - for (unsigned char ch = 1; ch != 0; ++ch) { - ASSERT_TRUE(everything_map.contains(ch)); - ASSERT_TRUE(!nothing_map.contains(ch)); - ASSERT_TRUE(!also_nothing_map.contains(ch)); - } - - const absl::strings_internal::Charmap symbols("&@#@^!@?", 5); - ASSERT_TRUE(symbols.contains('&')); - ASSERT_TRUE(symbols.contains('@')); - ASSERT_TRUE(symbols.contains('#')); - ASSERT_TRUE(symbols.contains('^')); - ASSERT_TRUE(!symbols.contains('!')); - ASSERT_TRUE(!symbols.contains('?')); - int cnt = 0; - for (unsigned char ch = 1; ch != 0; ++ch) - cnt += symbols.contains(ch); - ASSERT_EQ(cnt, 4); - - const absl::strings_internal::Charmap lets("^abcde", 3); - const absl::strings_internal::Charmap lets2("fghij\0klmnop", 10); - const absl::strings_internal::Charmap lets3("fghij\0klmnop"); - ASSERT_TRUE(lets2.contains('k')); - ASSERT_TRUE(!lets3.contains('k')); - - ASSERT_TRUE(symbols.IntersectsWith(lets)); - ASSERT_TRUE(!lets2.IntersectsWith(lets)); - ASSERT_TRUE(lets.IntersectsWith(symbols)); - ASSERT_TRUE(!lets.IntersectsWith(lets2)); - - ASSERT_TRUE(nothing_map.IsZero()); - ASSERT_TRUE(!lets.IsZero()); -} - -namespace { -std::string Members(const absl::strings_internal::Charmap& m) { - std::string r; - for (size_t i = 0; i < 256; ++i) - if (m.contains(i)) r.push_back(i); - return r; -} - -std::string ClosedRangeString(unsigned char lo, unsigned char hi) { - // Don't depend on lo<hi. Just increment until lo==hi. - std::string s; - while (true) { - s.push_back(lo); - if (lo == hi) break; - ++lo; - } - return s; -} - -} // namespace - -TEST(Charmap, Constexpr) { - constexpr absl::strings_internal::Charmap kEmpty = nothing_map; - EXPECT_THAT(Members(kEmpty), ""); - constexpr absl::strings_internal::Charmap kA = - absl::strings_internal::Charmap::Char('A'); - EXPECT_THAT(Members(kA), "A"); - constexpr absl::strings_internal::Charmap kAZ = - absl::strings_internal::Charmap::Range('A', 'Z'); - EXPECT_THAT(Members(kAZ), "ABCDEFGHIJKLMNOPQRSTUVWXYZ"); - constexpr absl::strings_internal::Charmap kIdentifier = - absl::strings_internal::Charmap::Range('0', '9') | - absl::strings_internal::Charmap::Range('A', 'Z') | - absl::strings_internal::Charmap::Range('a', 'z') | - absl::strings_internal::Charmap::Char('_'); - EXPECT_THAT(Members(kIdentifier), - "0123456789" - "ABCDEFGHIJKLMNOPQRSTUVWXYZ" - "_" - "abcdefghijklmnopqrstuvwxyz"); - constexpr absl::strings_internal::Charmap kAll = everything_map; - for (size_t i = 0; i < 256; ++i) { - EXPECT_TRUE(kAll.contains(i)) << i; - } - constexpr absl::strings_internal::Charmap kHello = - absl::strings_internal::Charmap::FromString("Hello, world!"); - EXPECT_THAT(Members(kHello), " !,Hdelorw"); - - // test negation and intersection - constexpr absl::strings_internal::Charmap kABC = - absl::strings_internal::Charmap::Range('A', 'Z') & - ~absl::strings_internal::Charmap::Range('D', 'Z'); - EXPECT_THAT(Members(kABC), "ABC"); -} - -TEST(Charmap, Range) { - // Exhaustive testing takes too long, so test some of the boundaries that - // are perhaps going to cause trouble. - std::vector<size_t> poi = {0, 1, 2, 3, 4, 7, 8, 9, 15, - 16, 17, 30, 31, 32, 33, 63, 64, 65, - 127, 128, 129, 223, 224, 225, 254, 255}; - for (auto lo = poi.begin(); lo != poi.end(); ++lo) { - SCOPED_TRACE(*lo); - for (auto hi = lo; hi != poi.end(); ++hi) { - SCOPED_TRACE(*hi); - EXPECT_THAT(Members(absl::strings_internal::Charmap::Range(*lo, *hi)), - ClosedRangeString(*lo, *hi)); - } - } -} - -bool AsBool(int x) { return static_cast<bool>(x); } - -TEST(CharmapCtype, Match) { - for (int c = 0; c < 256; ++c) { - SCOPED_TRACE(c); - SCOPED_TRACE(static_cast<char>(c)); - EXPECT_EQ(AsBool(std::isupper(c)), - absl::strings_internal::UpperCharmap().contains(c)); - EXPECT_EQ(AsBool(std::islower(c)), - absl::strings_internal::LowerCharmap().contains(c)); - EXPECT_EQ(AsBool(std::isdigit(c)), - absl::strings_internal::DigitCharmap().contains(c)); - EXPECT_EQ(AsBool(std::isalpha(c)), - absl::strings_internal::AlphaCharmap().contains(c)); - EXPECT_EQ(AsBool(std::isalnum(c)), - absl::strings_internal::AlnumCharmap().contains(c)); - EXPECT_EQ(AsBool(std::isxdigit(c)), - absl::strings_internal::XDigitCharmap().contains(c)); - EXPECT_EQ(AsBool(std::isprint(c)), - absl::strings_internal::PrintCharmap().contains(c)); - EXPECT_EQ(AsBool(std::isspace(c)), - absl::strings_internal::SpaceCharmap().contains(c)); - EXPECT_EQ(AsBool(std::iscntrl(c)), - absl::strings_internal::CntrlCharmap().contains(c)); - EXPECT_EQ(AsBool(std::isblank(c)), - absl::strings_internal::BlankCharmap().contains(c)); - EXPECT_EQ(AsBool(std::isgraph(c)), - absl::strings_internal::GraphCharmap().contains(c)); - EXPECT_EQ(AsBool(std::ispunct(c)), - absl::strings_internal::PunctCharmap().contains(c)); - } -} - -} // namespace diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc index b7874385..57d9d385 100644 --- a/absl/strings/internal/cord_internal.cc +++ b/absl/strings/internal/cord_internal.cc @@ -22,15 +22,12 @@ #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 namespace cord_internal { -ABSL_CONST_INIT std::atomic<bool> cord_ring_buffer_enabled( - kCordEnableRingBufferDefault); ABSL_CONST_INIT std::atomic<bool> shallow_subcords_enabled( kCordShallowSubcordsDefault); @@ -47,9 +44,6 @@ void CordRep::Destroy(CordRep* rep) { if (rep->tag == BTREE) { CordRepBtree::Destroy(rep->btree()); return; - } else if (rep->tag == RING) { - CordRepRing::Destroy(rep->ring()); - return; } else if (rep->tag == EXTERNAL) { CordRepExternal::Delete(rep); return; diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h index 20dd008c..8744540e 100644 --- a/absl/strings/internal/cord_internal.h +++ b/absl/strings/internal/cord_internal.h @@ -55,24 +55,15 @@ struct CordRepExternal; struct CordRepFlat; struct CordRepSubstring; struct CordRepCrc; -class CordRepRing; class CordRepBtree; class CordzInfo; // Default feature enable states for cord ring buffers -enum CordFeatureDefaults { - kCordEnableRingBufferDefault = false, - kCordShallowSubcordsDefault = false -}; +enum CordFeatureDefaults { kCordShallowSubcordsDefault = false }; -extern std::atomic<bool> cord_ring_buffer_enabled; extern std::atomic<bool> shallow_subcords_enabled; -inline void enable_cord_ring_buffer(bool enable) { - cord_ring_buffer_enabled.store(enable, std::memory_order_relaxed); -} - inline void enable_shallow_subcords(bool enable) { shallow_subcords_enabled.store(enable, std::memory_order_relaxed); } @@ -110,8 +101,16 @@ inline void SmallMemmove(char* dst, const char* src, size_t n) { if (nullify_tail) { memset(dst + 7, 0, 8); } + // GCC 12 has a false-positive -Wstringop-overflow warning here. +#if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(12, 0) +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wstringop-overflow" +#endif memcpy(dst, &buf1, 8); memcpy(dst + n - 8, &buf2, 8); +#if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(12, 0) +#pragma GCC diagnostic pop +#endif } else if (n >= 4) { uint32_t buf1; uint32_t buf2; @@ -158,18 +157,18 @@ class RefcountAndFlags { // false. Always returns false when the immortal bit is set. inline bool Decrement() { int32_t refcount = count_.load(std::memory_order_acquire); - assert((refcount & kRefcountMask) > 0 || refcount & kImmortalFlag); + assert(refcount > 0 || refcount & kImmortalFlag); return refcount != kRefIncrement && - (count_.fetch_sub(kRefIncrement, std::memory_order_acq_rel) & - kHighRefcountMask) != 0; + count_.fetch_sub(kRefIncrement, std::memory_order_acq_rel) != + kRefIncrement; } // Same as Decrement but expect that refcount is greater than 1. inline bool DecrementExpectHighRefcount() { int32_t refcount = count_.fetch_sub(kRefIncrement, std::memory_order_acq_rel); - assert((refcount & kRefcountMask) > 0 || refcount & kImmortalFlag); - return (refcount & kHighRefcountMask) != 0; + assert(refcount > 0 || refcount & kImmortalFlag); + return refcount != kRefIncrement; } // Returns the current reference count using acquire semantics. @@ -185,10 +184,9 @@ class RefcountAndFlags { // This call performs the test for a reference count of one, and // performs the memory barrier needed for the owning thread // to act on the object, knowing that it has exclusive access to the - // object. Always returns false when the immortal bit is set. + // object. Always returns false when the immortal bit is set. inline bool IsOne() { - return (count_.load(std::memory_order_acquire) & kRefcountMask) == - kRefIncrement; + return count_.load(std::memory_order_acquire) == kRefIncrement; } bool IsImmortal() const { @@ -196,32 +194,15 @@ class RefcountAndFlags { } private: - // We reserve the bottom bits for flags. + // We reserve the bottom bit for flag. // kImmortalBit indicates that this entity should never be collected; it is // used for the StringConstant constructor to avoid collecting immutable // constant cords. - // kReservedFlag is reserved for future use. enum Flags { - kNumFlags = 2, + kNumFlags = 1, kImmortalFlag = 0x1, - kReservedFlag = 0x2, kRefIncrement = (1 << kNumFlags), - - // Bitmask to use when checking refcount by equality. This masks out - // all flags except kImmortalFlag, which is part of the refcount for - // purposes of equality. (A refcount of 0 or 1 does not count as 0 or 1 - // if the immortal bit is set.) - kRefcountMask = ~kReservedFlag, - - // Bitmask to use when checking if refcount is equal to 1 and not - // immortal when decrementing the refcount. This masks out kRefIncrement and - // all flags except kImmortalFlag. If the masked RefcountAndFlags is 0, we - // assume the refcount is equal to 1, since we know it's not immortal and - // not greater than 1. If the masked RefcountAndFlags is not 0, we can - // assume the refcount is not equal to 1 since either a higher bit in the - // refcount is set, or kImmortal is set. - kHighRefcountMask = kRefcountMask & ~kRefIncrement, }; std::atomic<int32_t> count_; @@ -233,7 +214,7 @@ enum CordRepKind { SUBSTRING = 1, CRC = 2, BTREE = 3, - RING = 4, + UNUSED_4 = 4, EXTERNAL = 5, // We have different tags for different sized flat arrays, @@ -252,12 +233,8 @@ enum CordRepKind { // There are various locations where we want to check if some rep is a 'plain' // data edge, i.e. an external or flat rep. By having FLAT == EXTERNAL + 1, we // can perform this check in a single branch as 'tag >= EXTERNAL' -// Likewise, we have some locations where we check for 'ring or external/flat', -// so likewise align RING to EXTERNAL. // Note that we can leave this optimization to the compiler. The compiler will // DTRT when it sees a condition like `tag == EXTERNAL || tag >= FLAT`. -static_assert(RING == BTREE + 1, "BTREE and RING not consecutive"); -static_assert(EXTERNAL == RING + 1, "BTREE and EXTERNAL not consecutive"); static_assert(FLAT == EXTERNAL + 1, "EXTERNAL and FLAT not consecutive"); struct CordRep { @@ -301,15 +278,12 @@ struct CordRep { // # LINT.ThenChange(cord_rep_btree.h:copy_raw) // Returns true if this instance's tag matches the requested type. - constexpr bool IsRing() const { return tag == RING; } constexpr bool IsSubstring() const { return tag == SUBSTRING; } constexpr bool IsCrc() const { return tag == CRC; } constexpr bool IsExternal() const { return tag == EXTERNAL; } constexpr bool IsFlat() const { return tag >= FLAT; } constexpr bool IsBtree() const { return tag == BTREE; } - inline CordRepRing* ring(); - inline const CordRepRing* ring() const; inline CordRepSubstring* substring(); inline const CordRepSubstring* substring() const; inline CordRepCrc* crc(); diff --git a/absl/strings/internal/cord_rep_ring.cc b/absl/strings/internal/cord_rep_ring.cc deleted file mode 100644 index af2fc768..00000000 --- a/absl/strings/internal/cord_rep_ring.cc +++ /dev/null @@ -1,773 +0,0 @@ -// Copyright 2020 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. -#include "absl/strings/internal/cord_rep_ring.h" - -#include <cassert> -#include <cstddef> -#include <cstdint> -#include <iostream> -#include <limits> -#include <memory> -#include <string> - -#include "absl/base/internal/raw_logging.h" -#include "absl/base/internal/throw_delegate.h" -#include "absl/base/macros.h" -#include "absl/container/inlined_vector.h" -#include "absl/strings/internal/cord_internal.h" -#include "absl/strings/internal/cord_rep_consume.h" -#include "absl/strings/internal/cord_rep_flat.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace cord_internal { - -namespace { - -using index_type = CordRepRing::index_type; - -enum class Direction { kForward, kReversed }; - -inline bool IsFlatOrExternal(CordRep* rep) { - return rep->IsFlat() || rep->IsExternal(); -} - -// Verifies that n + extra <= kMaxCapacity: throws std::length_error otherwise. -inline void CheckCapacity(size_t n, size_t extra) { - if (ABSL_PREDICT_FALSE(extra > CordRepRing::kMaxCapacity - n)) { - base_internal::ThrowStdLengthError("Maximum capacity exceeded"); - } -} - -// Creates a flat from the provided string data, allocating up to `extra` -// capacity in the returned flat depending on kMaxFlatLength limitations. -// Requires `len` to be less or equal to `kMaxFlatLength` -CordRepFlat* CreateFlat(const char* s, size_t n, size_t extra = 0) { // NOLINT - assert(n <= kMaxFlatLength); - auto* rep = CordRepFlat::New(n + extra); - rep->length = n; - memcpy(rep->Data(), s, n); - return rep; -} - -// Unrefs the entries in `[head, tail)`. -// Requires all entries to be a FLAT or EXTERNAL node. -void UnrefEntries(const CordRepRing* rep, index_type head, index_type tail) { - rep->ForEach(head, tail, [rep](index_type ix) { - CordRep* child = rep->entry_child(ix); - if (!child->refcount.Decrement()) { - if (child->tag >= FLAT) { - CordRepFlat::Delete(child->flat()); - } else { - CordRepExternal::Delete(child->external()); - } - } - }); -} - -} // namespace - -std::ostream& operator<<(std::ostream& s, const CordRepRing& rep) { - // Note: 'pos' values are defined as size_t (for overflow reasons), but that - // prints really awkward for small prepended values such as -5. ssize_t is not - // portable (POSIX), so we use ptrdiff_t instead to cast to signed values. - s << " CordRepRing(" << &rep << ", length = " << rep.length - << ", head = " << rep.head_ << ", tail = " << rep.tail_ - << ", cap = " << rep.capacity_ << ", rc = " << rep.refcount.Get() - << ", begin_pos_ = " << static_cast<ptrdiff_t>(rep.begin_pos_) << ") {\n"; - CordRepRing::index_type head = rep.head(); - do { - CordRep* child = rep.entry_child(head); - s << " entry[" << head << "] length = " << rep.entry_length(head) - << ", child " << child << ", clen = " << child->length - << ", tag = " << static_cast<int>(child->tag) - << ", rc = " << child->refcount.Get() - << ", offset = " << rep.entry_data_offset(head) - << ", end_pos = " << static_cast<ptrdiff_t>(rep.entry_end_pos(head)) - << "\n"; - head = rep.advance(head); - } while (head != rep.tail()); - return s << "}\n"; -} - -void CordRepRing::AddDataOffset(index_type index, size_t n) { - entry_data_offset()[index] += static_cast<offset_type>(n); -} - -void CordRepRing::SubLength(index_type index, size_t n) { - entry_end_pos()[index] -= n; -} - -class CordRepRing::Filler { - public: - Filler(CordRepRing* rep, index_type pos) : rep_(rep), head_(pos), pos_(pos) {} - - index_type head() const { return head_; } - index_type pos() const { return pos_; } - - void Add(CordRep* child, size_t offset, pos_type end_pos) { - rep_->entry_end_pos()[pos_] = end_pos; - rep_->entry_child()[pos_] = child; - rep_->entry_data_offset()[pos_] = static_cast<offset_type>(offset); - pos_ = rep_->advance(pos_); - } - - private: - CordRepRing* rep_; - index_type head_; - index_type pos_; -}; - -#ifdef ABSL_INTERNAL_NEED_REDUNDANT_CONSTEXPR_DECL -constexpr size_t CordRepRing::kMaxCapacity; -#endif - -bool CordRepRing::IsValid(std::ostream& output) const { - if (capacity_ == 0) { - output << "capacity == 0"; - return false; - } - - if (head_ >= capacity_ || tail_ >= capacity_) { - output << "head " << head_ << " and/or tail " << tail_ << "exceed capacity " - << capacity_; - return false; - } - - const index_type back = retreat(tail_); - size_t pos_length = Distance(begin_pos_, entry_end_pos(back)); - if (pos_length != length) { - output << "length " << length << " does not match positional length " - << pos_length << " from begin_pos " << begin_pos_ << " and entry[" - << back << "].end_pos " << entry_end_pos(back); - return false; - } - - index_type head = head_; - pos_type begin_pos = begin_pos_; - do { - pos_type end_pos = entry_end_pos(head); - size_t entry_length = Distance(begin_pos, end_pos); - if (entry_length == 0) { - output << "entry[" << head << "] has an invalid length " << entry_length - << " from begin_pos " << begin_pos << " and end_pos " << end_pos; - return false; - } - - CordRep* child = entry_child(head); - if (child == nullptr) { - output << "entry[" << head << "].child == nullptr"; - return false; - } - if (child->tag < FLAT && child->tag != EXTERNAL) { - output << "entry[" << head << "].child has an invalid tag " - << static_cast<int>(child->tag); - return false; - } - - size_t offset = entry_data_offset(head); - if (offset >= child->length || entry_length > child->length - offset) { - output << "entry[" << head << "] has offset " << offset - << " and entry length " << entry_length - << " which are outside of the child's length of " << child->length; - return false; - } - - begin_pos = end_pos; - head = advance(head); - } while (head != tail_); - - return true; -} - -#ifdef EXTRA_CORD_RING_VALIDATION -CordRepRing* CordRepRing::Validate(CordRepRing* rep, const char* file, - int line) { - if (!rep->IsValid(std::cerr)) { - std::cerr << "\nERROR: CordRepRing corrupted"; - if (line) std::cerr << " at line " << line; - if (file) std::cerr << " in file " << file; - std::cerr << "\nContent = " << *rep; - abort(); - } - return rep; -} -#endif // EXTRA_CORD_RING_VALIDATION - -CordRepRing* CordRepRing::New(size_t capacity, size_t extra) { - CheckCapacity(capacity, extra); - - size_t size = AllocSize(capacity += extra); - void* mem = ::operator new(size); - auto* rep = new (mem) CordRepRing(static_cast<index_type>(capacity)); - rep->tag = RING; - rep->capacity_ = static_cast<index_type>(capacity); - rep->begin_pos_ = 0; - return rep; -} - -void CordRepRing::SetCapacityForTesting(size_t capacity) { - // Adjust for the changed layout - assert(capacity <= capacity_); - assert(head() == 0 || head() < tail()); - memmove(Layout::Partial(capacity).Pointer<1>(data_) + head(), - Layout::Partial(capacity_).Pointer<1>(data_) + head(), - entries() * sizeof(Layout::ElementType<1>)); - memmove(Layout::Partial(capacity, capacity).Pointer<2>(data_) + head(), - Layout::Partial(capacity_, capacity_).Pointer<2>(data_) + head(), - entries() * sizeof(Layout::ElementType<2>)); - capacity_ = static_cast<index_type>(capacity); -} - -void CordRepRing::Delete(CordRepRing* rep) { - assert(rep != nullptr && rep->IsRing()); -#if defined(__cpp_sized_deallocation) - size_t size = AllocSize(rep->capacity_); - rep->~CordRepRing(); - ::operator delete(rep, size); -#else - rep->~CordRepRing(); - ::operator delete(rep); -#endif -} - -void CordRepRing::Destroy(CordRepRing* rep) { - UnrefEntries(rep, rep->head(), rep->tail()); - Delete(rep); -} - -template <bool ref> -void CordRepRing::Fill(const CordRepRing* src, index_type head, - index_type tail) { - this->length = src->length; - head_ = 0; - tail_ = advance(0, src->entries(head, tail)); - begin_pos_ = src->begin_pos_; - - // TODO(mvels): there may be opportunities here for large buffers. - auto* dst_pos = entry_end_pos(); - auto* dst_child = entry_child(); - auto* dst_offset = entry_data_offset(); - src->ForEach(head, tail, [&](index_type index) { - *dst_pos++ = src->entry_end_pos(index); - CordRep* child = src->entry_child(index); - *dst_child++ = ref ? CordRep::Ref(child) : child; - *dst_offset++ = src->entry_data_offset(index); - }); -} - -CordRepRing* CordRepRing::Copy(CordRepRing* rep, index_type head, - index_type tail, size_t extra) { - CordRepRing* newrep = CordRepRing::New(rep->entries(head, tail), extra); - newrep->Fill<true>(rep, head, tail); - CordRep::Unref(rep); - return newrep; -} - -CordRepRing* CordRepRing::Mutable(CordRepRing* rep, size_t extra) { - // Get current number of entries, and check for max capacity. - size_t entries = rep->entries(); - - if (!rep->refcount.IsOne()) { - return Copy(rep, rep->head(), rep->tail(), extra); - } else if (entries + extra > rep->capacity()) { - const size_t min_grow = rep->capacity() + rep->capacity() / 2; - const size_t min_extra = (std::max)(extra, min_grow - entries); - CordRepRing* newrep = CordRepRing::New(entries, min_extra); - newrep->Fill<false>(rep, rep->head(), rep->tail()); - CordRepRing::Delete(rep); - return newrep; - } else { - return rep; - } -} - -Span<char> CordRepRing::GetAppendBuffer(size_t size) { - assert(refcount.IsOne()); - index_type back = retreat(tail_); - CordRep* child = entry_child(back); - if (child->tag >= FLAT && child->refcount.IsOne()) { - size_t capacity = child->flat()->Capacity(); - pos_type end_pos = entry_end_pos(back); - size_t data_offset = entry_data_offset(back); - size_t entry_length = Distance(entry_begin_pos(back), end_pos); - size_t used = data_offset + entry_length; - if (size_t n = (std::min)(capacity - used, size)) { - child->length = data_offset + entry_length + n; - entry_end_pos()[back] = end_pos + n; - this->length += n; - return {child->flat()->Data() + used, n}; - } - } - return {nullptr, 0}; -} - -Span<char> CordRepRing::GetPrependBuffer(size_t size) { - assert(refcount.IsOne()); - CordRep* child = entry_child(head_); - size_t data_offset = entry_data_offset(head_); - if (data_offset && child->refcount.IsOne() && child->tag >= FLAT) { - size_t n = (std::min)(data_offset, size); - this->length += n; - begin_pos_ -= n; - data_offset -= n; - entry_data_offset()[head_] = static_cast<offset_type>(data_offset); - return {child->flat()->Data() + data_offset, n}; - } - return {nullptr, 0}; -} - -CordRepRing* CordRepRing::CreateFromLeaf(CordRep* child, size_t offset, - size_t len, size_t extra) { - CordRepRing* rep = CordRepRing::New(1, extra); - rep->head_ = 0; - rep->tail_ = rep->advance(0); - rep->length = len; - rep->entry_end_pos()[0] = len; - rep->entry_child()[0] = child; - rep->entry_data_offset()[0] = static_cast<offset_type>(offset); - return Validate(rep); -} - -CordRepRing* CordRepRing::CreateSlow(CordRep* child, size_t extra) { - CordRepRing* rep = nullptr; - Consume(child, [&](CordRep* child_arg, size_t offset, size_t len) { - if (IsFlatOrExternal(child_arg)) { - rep = rep ? AppendLeaf(rep, child_arg, offset, len) - : CreateFromLeaf(child_arg, offset, len, extra); - } else if (rep) { - rep = AddRing<AddMode::kAppend>(rep, child_arg->ring(), offset, len); - } else if (offset == 0 && child_arg->length == len) { - rep = Mutable(child_arg->ring(), extra); - } else { - rep = SubRing(child_arg->ring(), offset, len, extra); - } - }); - return Validate(rep, nullptr, __LINE__); -} - -CordRepRing* CordRepRing::Create(CordRep* child, size_t extra) { - size_t length = child->length; - if (IsFlatOrExternal(child)) { - return CreateFromLeaf(child, 0, length, extra); - } - if (child->IsRing()) { - return Mutable(child->ring(), extra); - } - return CreateSlow(child, extra); -} - -template <CordRepRing::AddMode mode> -CordRepRing* CordRepRing::AddRing(CordRepRing* rep, CordRepRing* ring, - size_t offset, size_t len) { - assert(offset < ring->length); - constexpr bool append = mode == AddMode::kAppend; - Position head = ring->Find(offset); - Position tail = ring->FindTail(head.index, offset + len); - const index_type entries = ring->entries(head.index, tail.index); - - rep = Mutable(rep, entries); - - // The delta for making ring[head].end_pos into 'len - offset' - const pos_type delta_length = - (append ? rep->begin_pos_ + rep->length : rep->begin_pos_ - len) - - ring->entry_begin_pos(head.index) - head.offset; - - // Start filling at `tail`, or `entries` before `head` - Filler filler(rep, append ? rep->tail_ : rep->retreat(rep->head_, entries)); - - if (ring->refcount.IsOne()) { - // Copy entries from source stealing the ref and adjusting the end position. - // Commit the filler as this is no-op. - ring->ForEach(head.index, tail.index, [&](index_type ix) { - filler.Add(ring->entry_child(ix), ring->entry_data_offset(ix), - ring->entry_end_pos(ix) + delta_length); - }); - - // Unref entries we did not copy over, and delete source. - if (head.index != ring->head_) UnrefEntries(ring, ring->head_, head.index); - if (tail.index != ring->tail_) UnrefEntries(ring, tail.index, ring->tail_); - CordRepRing::Delete(ring); - } else { - ring->ForEach(head.index, tail.index, [&](index_type ix) { - CordRep* child = ring->entry_child(ix); - filler.Add(child, ring->entry_data_offset(ix), - ring->entry_end_pos(ix) + delta_length); - CordRep::Ref(child); - }); - CordRepRing::Unref(ring); - } - - if (head.offset) { - // Increase offset of first 'source' entry appended or prepended. - // This is always the entry in `filler.head()` - rep->AddDataOffset(filler.head(), head.offset); - } - - if (tail.offset) { - // Reduce length of last 'source' entry appended or prepended. - // This is always the entry tailed by `filler.pos()` - rep->SubLength(rep->retreat(filler.pos()), tail.offset); - } - - // Commit changes - rep->length += len; - if (append) { - rep->tail_ = filler.pos(); - } else { - rep->head_ = filler.head(); - rep->begin_pos_ -= len; - } - - return Validate(rep); -} - -CordRepRing* CordRepRing::AppendSlow(CordRepRing* rep, CordRep* child) { - Consume(child, [&rep](CordRep* child_arg, size_t offset, size_t len) { - if (child_arg->IsRing()) { - rep = AddRing<AddMode::kAppend>(rep, child_arg->ring(), offset, len); - } else { - rep = AppendLeaf(rep, child_arg, offset, len); - } - }); - return rep; -} - -CordRepRing* CordRepRing::AppendLeaf(CordRepRing* rep, CordRep* child, - size_t offset, size_t len) { - rep = Mutable(rep, 1); - index_type back = rep->tail_; - const pos_type begin_pos = rep->begin_pos_ + rep->length; - rep->tail_ = rep->advance(rep->tail_); - rep->length += len; - rep->entry_end_pos()[back] = begin_pos + len; - rep->entry_child()[back] = child; - rep->entry_data_offset()[back] = static_cast<offset_type>(offset); - return Validate(rep, nullptr, __LINE__); -} - -CordRepRing* CordRepRing::Append(CordRepRing* rep, CordRep* child) { - size_t length = child->length; - if (IsFlatOrExternal(child)) { - return AppendLeaf(rep, child, 0, length); - } - if (child->IsRing()) { - return AddRing<AddMode::kAppend>(rep, child->ring(), 0, length); - } - return AppendSlow(rep, child); -} - -CordRepRing* CordRepRing::PrependSlow(CordRepRing* rep, CordRep* child) { - ReverseConsume(child, [&](CordRep* child_arg, size_t offset, size_t len) { - if (IsFlatOrExternal(child_arg)) { - rep = PrependLeaf(rep, child_arg, offset, len); - } else { - rep = AddRing<AddMode::kPrepend>(rep, child_arg->ring(), offset, len); - } - }); - return Validate(rep); -} - -CordRepRing* CordRepRing::PrependLeaf(CordRepRing* rep, CordRep* child, - size_t offset, size_t len) { - rep = Mutable(rep, 1); - index_type head = rep->retreat(rep->head_); - pos_type end_pos = rep->begin_pos_; - rep->head_ = head; - rep->length += len; - rep->begin_pos_ -= len; - rep->entry_end_pos()[head] = end_pos; - rep->entry_child()[head] = child; - rep->entry_data_offset()[head] = static_cast<offset_type>(offset); - return Validate(rep); -} - -CordRepRing* CordRepRing::Prepend(CordRepRing* rep, CordRep* child) { - size_t length = child->length; - if (IsFlatOrExternal(child)) { - return PrependLeaf(rep, child, 0, length); - } - if (child->IsRing()) { - return AddRing<AddMode::kPrepend>(rep, child->ring(), 0, length); - } - return PrependSlow(rep, child); -} - -CordRepRing* CordRepRing::Append(CordRepRing* rep, absl::string_view data, - size_t extra) { - if (rep->refcount.IsOne()) { - Span<char> avail = rep->GetAppendBuffer(data.length()); - if (!avail.empty()) { - memcpy(avail.data(), data.data(), avail.length()); - data.remove_prefix(avail.length()); - } - } - if (data.empty()) return Validate(rep); - - const size_t flats = (data.length() - 1) / kMaxFlatLength + 1; - rep = Mutable(rep, flats); - - Filler filler(rep, rep->tail_); - pos_type pos = rep->begin_pos_ + rep->length; - - while (data.length() >= kMaxFlatLength) { - auto* flat = CreateFlat(data.data(), kMaxFlatLength); - filler.Add(flat, 0, pos += kMaxFlatLength); - data.remove_prefix(kMaxFlatLength); - } - - if (data.length()) { - auto* flat = CreateFlat(data.data(), data.length(), extra); - filler.Add(flat, 0, pos += data.length()); - } - - rep->length = pos - rep->begin_pos_; - rep->tail_ = filler.pos(); - - return Validate(rep); -} - -CordRepRing* CordRepRing::Prepend(CordRepRing* rep, absl::string_view data, - size_t extra) { - if (rep->refcount.IsOne()) { - Span<char> avail = rep->GetPrependBuffer(data.length()); - if (!avail.empty()) { - const char* tail = data.data() + data.length() - avail.length(); - memcpy(avail.data(), tail, avail.length()); - data.remove_suffix(avail.length()); - } - } - if (data.empty()) return rep; - - const size_t flats = (data.length() - 1) / kMaxFlatLength + 1; - rep = Mutable(rep, flats); - pos_type pos = rep->begin_pos_; - Filler filler(rep, rep->retreat(rep->head_, static_cast<index_type>(flats))); - - size_t first_size = data.size() - (flats - 1) * kMaxFlatLength; - CordRepFlat* flat = CordRepFlat::New(first_size + extra); - flat->length = first_size + extra; - memcpy(flat->Data() + extra, data.data(), first_size); - data.remove_prefix(first_size); - filler.Add(flat, extra, pos); - pos -= first_size; - - while (!data.empty()) { - assert(data.size() >= kMaxFlatLength); - flat = CreateFlat(data.data(), kMaxFlatLength); - filler.Add(flat, 0, pos); - pos -= kMaxFlatLength; - data.remove_prefix(kMaxFlatLength); - } - - rep->head_ = filler.head(); - rep->length += rep->begin_pos_ - pos; - rep->begin_pos_ = pos; - - return Validate(rep); -} - -// 32 entries is 32 * sizeof(pos_type) = 4 cache lines on x86 -static constexpr index_type kBinarySearchThreshold = 32; -static constexpr index_type kBinarySearchEndCount = 8; - -template <bool wrap> -CordRepRing::index_type CordRepRing::FindBinary(index_type head, - index_type tail, - size_t offset) const { - index_type count = tail + (wrap ? capacity_ : 0) - head; - do { - count = (count - 1) / 2; - assert(count < entries(head, tail_)); - index_type mid = wrap ? advance(head, count) : head + count; - index_type after_mid = wrap ? advance(mid) : mid + 1; - bool larger = (offset >= entry_end_offset(mid)); - head = larger ? after_mid : head; - tail = larger ? tail : mid; - assert(head != tail); - } while (ABSL_PREDICT_TRUE(count > kBinarySearchEndCount)); - return head; -} - -CordRepRing::Position CordRepRing::FindSlow(index_type head, - size_t offset) const { - index_type tail = tail_; - - // Binary search until we are good for linear search - // Optimize for branchless / non wrapping ops - if (tail > head) { - index_type count = tail - head; - if (count > kBinarySearchThreshold) { - head = FindBinary<false>(head, tail, offset); - } - } else { - index_type count = capacity_ + tail - head; - if (count > kBinarySearchThreshold) { - head = FindBinary<true>(head, tail, offset); - } - } - - pos_type pos = entry_begin_pos(head); - pos_type end_pos = entry_end_pos(head); - while (offset >= Distance(begin_pos_, end_pos)) { - head = advance(head); - pos = end_pos; - end_pos = entry_end_pos(head); - } - - return {head, offset - Distance(begin_pos_, pos)}; -} - -CordRepRing::Position CordRepRing::FindTailSlow(index_type head, - size_t offset) const { - index_type tail = tail_; - const size_t tail_offset = offset - 1; - - // Binary search until we are good for linear search - // Optimize for branchless / non wrapping ops - if (tail > head) { - index_type count = tail - head; - if (count > kBinarySearchThreshold) { - head = FindBinary<false>(head, tail, tail_offset); - } - } else { - index_type count = capacity_ + tail - head; - if (count > kBinarySearchThreshold) { - head = FindBinary<true>(head, tail, tail_offset); - } - } - - size_t end_offset = entry_end_offset(head); - while (tail_offset >= end_offset) { - head = advance(head); - end_offset = entry_end_offset(head); - } - - return {advance(head), end_offset - offset}; -} - -char CordRepRing::GetCharacter(size_t offset) const { - assert(offset < length); - - Position pos = Find(offset); - size_t data_offset = entry_data_offset(pos.index) + pos.offset; - return GetRepData(entry_child(pos.index))[data_offset]; -} - -CordRepRing* CordRepRing::SubRing(CordRepRing* rep, size_t offset, - size_t len, size_t extra) { - assert(offset <= rep->length); - assert(offset <= rep->length - len); - - if (len == 0) { - CordRep::Unref(rep); - return nullptr; - } - - // Find position of first byte - Position head = rep->Find(offset); - Position tail = rep->FindTail(head.index, offset + len); - const size_t new_entries = rep->entries(head.index, tail.index); - - if (rep->refcount.IsOne() && extra <= (rep->capacity() - new_entries)) { - // We adopt a privately owned rep and no extra entries needed. - if (head.index != rep->head_) UnrefEntries(rep, rep->head_, head.index); - if (tail.index != rep->tail_) UnrefEntries(rep, tail.index, rep->tail_); - rep->head_ = head.index; - rep->tail_ = tail.index; - } else { - // Copy subset to new rep - rep = Copy(rep, head.index, tail.index, extra); - head.index = rep->head_; - tail.index = rep->tail_; - } - - // Adjust begin_pos and length - rep->length = len; - rep->begin_pos_ += offset; - - // Adjust head and tail blocks - if (head.offset) { - rep->AddDataOffset(head.index, head.offset); - } - if (tail.offset) { - rep->SubLength(rep->retreat(tail.index), tail.offset); - } - - return Validate(rep); -} - -CordRepRing* CordRepRing::RemovePrefix(CordRepRing* rep, size_t len, - size_t extra) { - assert(len <= rep->length); - if (len == rep->length) { - CordRep::Unref(rep); - return nullptr; - } - - Position head = rep->Find(len); - if (rep->refcount.IsOne()) { - if (head.index != rep->head_) UnrefEntries(rep, rep->head_, head.index); - rep->head_ = head.index; - } else { - rep = Copy(rep, head.index, rep->tail_, extra); - head.index = rep->head_; - } - - // Adjust begin_pos and length - rep->length -= len; - rep->begin_pos_ += len; - - // Adjust head block - if (head.offset) { - rep->AddDataOffset(head.index, head.offset); - } - - return Validate(rep); -} - -CordRepRing* CordRepRing::RemoveSuffix(CordRepRing* rep, size_t len, - size_t extra) { - assert(len <= rep->length); - - if (len == rep->length) { - CordRep::Unref(rep); - return nullptr; - } - - Position tail = rep->FindTail(rep->length - len); - if (rep->refcount.IsOne()) { - // We adopt a privately owned rep, scrub. - if (tail.index != rep->tail_) UnrefEntries(rep, tail.index, rep->tail_); - rep->tail_ = tail.index; - } else { - // Copy subset to new rep - rep = Copy(rep, rep->head_, tail.index, extra); - tail.index = rep->tail_; - } - - // Adjust length - rep->length -= len; - - // Adjust tail block - if (tail.offset) { - rep->SubLength(rep->retreat(tail.index), tail.offset); - } - - return Validate(rep); -} - -} // namespace cord_internal -ABSL_NAMESPACE_END -} // namespace absl diff --git a/absl/strings/internal/cord_rep_ring.h b/absl/strings/internal/cord_rep_ring.h deleted file mode 100644 index 79a2fdb1..00000000 --- a/absl/strings/internal/cord_rep_ring.h +++ /dev/null @@ -1,607 +0,0 @@ -// Copyright 2020 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. - -#ifndef ABSL_STRINGS_INTERNAL_CORD_REP_RING_H_ -#define ABSL_STRINGS_INTERNAL_CORD_REP_RING_H_ - -#include <cassert> -#include <cstddef> -#include <cstdint> -#include <iosfwd> -#include <limits> -#include <memory> - -#include "absl/container/internal/layout.h" -#include "absl/strings/internal/cord_internal.h" -#include "absl/strings/internal/cord_rep_flat.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace cord_internal { - -// All operations modifying a ring buffer are implemented as static methods -// requiring a CordRepRing instance with a reference adopted by the method. -// -// The methods return the modified ring buffer, which may be equal to the input -// if the input was not shared, and having large enough capacity to accommodate -// any newly added node(s). Otherwise, a copy of the input rep with the new -// node(s) added is returned. -// -// Any modification on non shared ring buffers with enough capacity will then -// require minimum atomic operations. Caller should where possible provide -// reasonable `extra` hints for both anticipated extra `flat` byte space, as -// well as anticipated extra nodes required for complex operations. -// -// Example of code creating a ring buffer, adding some data to it, -// and discarding the buffer when done: -// -// void FunWithRings() { -// // Create ring with 3 flats -// CordRep* flat = CreateFlat("Hello"); -// CordRepRing* ring = CordRepRing::Create(flat, 2); -// ring = CordRepRing::Append(ring, CreateFlat(" ")); -// ring = CordRepRing::Append(ring, CreateFlat("world")); -// DoSomethingWithRing(ring); -// CordRep::Unref(ring); -// } -// -// Example of code Copying an existing ring buffer and modifying it: -// -// void MoreFunWithRings(CordRepRing* src) { -// CordRepRing* ring = CordRep::Ref(src)->ring(); -// ring = CordRepRing::Append(ring, CreateFlat("Hello")); -// ring = CordRepRing::Append(ring, CreateFlat(" ")); -// ring = CordRepRing::Append(ring, CreateFlat("world")); -// DoSomethingWithRing(ring); -// CordRep::Unref(ring); -// } -// -class CordRepRing : public CordRep { - public: - // `pos_type` represents a 'logical position'. A CordRepRing instance has a - // `begin_pos` (default 0), and each node inside the buffer will have an - // `end_pos` which is the `end_pos` of the previous node (or `begin_pos`) plus - // this node's length. The purpose is to allow for a binary search on this - // position, while allowing O(1) prepend and append operations. - using pos_type = size_t; - - // `index_type` is the type for the `head`, `tail` and `capacity` indexes. - // Ring buffers are limited to having no more than four billion entries. - using index_type = uint32_t; - - // `offset_type` is the type for the data offset inside a child rep's data. - using offset_type = uint32_t; - - // Position holds the node index and relative offset into the node for - // some physical offset in the contained data as returned by the Find() - // and FindTail() methods. - struct Position { - index_type index; - size_t offset; - }; - - // The maximum # of child nodes that can be hosted inside a CordRepRing. - static constexpr size_t kMaxCapacity = (std::numeric_limits<uint32_t>::max)(); - - // CordRepring can not be default constructed, moved, copied or assigned. - CordRepRing() = delete; - CordRepRing(const CordRepRing&) = delete; - CordRepRing& operator=(const CordRepRing&) = delete; - - // Returns true if this instance is valid, false if some or all of the - // invariants are broken. Intended for debug purposes only. - // `output` receives an explanation of the broken invariants. - bool IsValid(std::ostream& output) const; - - // Returns the size in bytes for a CordRepRing with `capacity' entries. - static constexpr size_t AllocSize(size_t capacity); - - // Returns the distance in bytes from `pos` to `end_pos`. - static constexpr size_t Distance(pos_type pos, pos_type end_pos); - - // Creates a new ring buffer from the provided `rep`. Adopts a reference - // on `rep`. The returned ring buffer has a capacity of at least `extra + 1` - static CordRepRing* Create(CordRep* child, size_t extra = 0); - - // `head`, `tail` and `capacity` indexes defining the ring buffer boundaries. - index_type head() const { return head_; } - index_type tail() const { return tail_; } - index_type capacity() const { return capacity_; } - - // Returns the number of entries in this instance. - index_type entries() const { return entries(head_, tail_); } - - // Returns the logical begin position of this instance. - pos_type begin_pos() const { return begin_pos_; } - - // Returns the number of entries for a given head-tail range. - // Requires `head` and `tail` values to be less than `capacity()`. - index_type entries(index_type head, index_type tail) const { - assert(head < capacity_ && tail < capacity_); - return tail - head + ((tail > head) ? 0 : capacity_); - } - - // Returns the logical end position of entry `index`. - pos_type const& entry_end_pos(index_type index) const { - assert(IsValidIndex(index)); - return Layout::Partial().Pointer<0>(data_)[index]; - } - - // Returns the child pointer of entry `index`. - CordRep* const& entry_child(index_type index) const { - assert(IsValidIndex(index)); - return Layout::Partial(capacity()).Pointer<1>(data_)[index]; - } - - // Returns the data offset of entry `index` - offset_type const& entry_data_offset(index_type index) const { - assert(IsValidIndex(index)); - return Layout::Partial(capacity(), capacity()).Pointer<2>(data_)[index]; - } - - // Appends the provided child node to the `rep` instance. - // Adopts a reference from `rep` and `child` which may not be null. - // If the provided child is a FLAT or EXTERNAL node, or a SUBSTRING node - // containing a FLAT or EXTERNAL node, then flat or external the node is added - // 'as is', with an offset added for the SUBSTRING case. - // If the provided child is a RING or CONCAT tree, or a SUBSTRING of a RING or - // CONCAT tree, then all child nodes not excluded by any start offset or - // length values are added recursively. - static CordRepRing* Append(CordRepRing* rep, CordRep* child); - - // Appends the provided string data to the `rep` instance. - // This function will attempt to utilize any remaining capacity in the last - // node of the input if that node is not shared (directly or indirectly), and - // of type FLAT. Remaining data will be added as one or more FLAT nodes. - // Any last node added to the ring buffer will be allocated with up to - // `extra` bytes of capacity for (anticipated) subsequent append actions. - static CordRepRing* Append(CordRepRing* rep, string_view data, - size_t extra = 0); - - // Prepends the provided child node to the `rep` instance. - // Adopts a reference from `rep` and `child` which may not be null. - // If the provided child is a FLAT or EXTERNAL node, or a SUBSTRING node - // containing a FLAT or EXTERNAL node, then flat or external the node is - // prepended 'as is', with an optional offset added for the SUBSTRING case. - // If the provided child is a RING or CONCAT tree, or a SUBSTRING of a RING - // or CONCAT tree, then all child nodes not excluded by any start offset or - // length values are added recursively. - static CordRepRing* Prepend(CordRepRing* rep, CordRep* child); - - // Prepends the provided string data to the `rep` instance. - // This function will attempt to utilize any remaining capacity in the first - // node of the input if that node is not shared (directly or indirectly), and - // of type FLAT. Remaining data will be added as one or more FLAT nodes. - // Any first node prepnded to the ring buffer will be allocated with up to - // `extra` bytes of capacity for (anticipated) subsequent prepend actions. - static CordRepRing* Prepend(CordRepRing* rep, string_view data, - size_t extra = 0); - - // Returns a span referencing potentially unused capacity in the last node. - // The returned span may be empty if no such capacity is available, or if the - // current instance is shared. Else, a span of size `n <= size` is returned. - // If non empty, the ring buffer is adjusted to the new length, with the newly - // added capacity left uninitialized. Callers should assign a value to the - // entire span before any other operations on this instance. - Span<char> GetAppendBuffer(size_t size); - - // Returns a span referencing potentially unused capacity in the first node. - // This function is identical to GetAppendBuffer except that it returns a span - // referencing up to `size` capacity directly before the existing data. - Span<char> GetPrependBuffer(size_t size); - - // Returns a cord ring buffer containing `len` bytes of data starting at - // `offset`. If the input is not shared, this function will remove all head - // and tail child nodes outside of the requested range, and adjust the new - // head and tail nodes as required. If the input is shared, this function - // returns a new instance sharing some or all of the nodes from the input. - static CordRepRing* SubRing(CordRepRing* r, size_t offset, size_t len, - size_t extra = 0); - - // Returns a cord ring buffer with the first `len` bytes removed. - // If the input is not shared, this function will remove all head child nodes - // fully inside the first `length` bytes, and adjust the new head as required. - // If the input is shared, this function returns a new instance sharing some - // or all of the nodes from the input. - static CordRepRing* RemoveSuffix(CordRepRing* r, size_t len, - size_t extra = 0); - - // Returns a cord ring buffer with the last `len` bytes removed. - // If the input is not shared, this function will remove all head child nodes - // fully inside the first `length` bytes, and adjust the new head as required. - // If the input is shared, this function returns a new instance sharing some - // or all of the nodes from the input. - static CordRepRing* RemovePrefix(CordRepRing* r, size_t len, - size_t extra = 0); - - // Returns the character at `offset`. Requires that `offset < length`. - char GetCharacter(size_t offset) const; - - // Returns true if this instance manages a single contiguous buffer, in which - // case the (optional) output parameter `fragment` is set. Otherwise, the - // function returns false, and `fragment` is left unchanged. - bool IsFlat(absl::string_view* fragment) const; - - // Returns true if the data starting at `offset` with length `len` is - // managed by this instance inside a single contiguous buffer, in which case - // the (optional) output parameter `fragment` is set to the contiguous memory - // starting at offset `offset` with length `length`. Otherwise, the function - // returns false, and `fragment` is left unchanged. - bool IsFlat(size_t offset, size_t len, absl::string_view* fragment) const; - - // Testing only: set capacity to requested capacity. - void SetCapacityForTesting(size_t capacity); - - // Returns the CordRep data pointer for the provided CordRep. - // Requires that the provided `rep` is either a FLAT or EXTERNAL CordRep. - static const char* GetLeafData(const CordRep* rep); - - // Returns the CordRep data pointer for the provided CordRep. - // Requires that `rep` is either a FLAT, EXTERNAL, or SUBSTRING CordRep. - static const char* GetRepData(const CordRep* rep); - - // Advances the provided position, wrapping around capacity as needed. - // Requires `index` < capacity() - inline index_type advance(index_type index) const; - - // Advances the provided position by 'n`, wrapping around capacity as needed. - // Requires `index` < capacity() and `n` <= capacity. - inline index_type advance(index_type index, index_type n) const; - - // Retreats the provided position, wrapping around 0 as needed. - // Requires `index` < capacity() - inline index_type retreat(index_type index) const; - - // Retreats the provided position by 'n', wrapping around 0 as needed. - // Requires `index` < capacity() - inline index_type retreat(index_type index, index_type n) const; - - // Returns the logical begin position of entry `index` - pos_type const& entry_begin_pos(index_type index) const { - return (index == head_) ? begin_pos_ : entry_end_pos(retreat(index)); - } - - // Returns the physical start offset of entry `index` - size_t entry_start_offset(index_type index) const { - return Distance(begin_pos_, entry_begin_pos(index)); - } - - // Returns the physical end offset of entry `index` - size_t entry_end_offset(index_type index) const { - return Distance(begin_pos_, entry_end_pos(index)); - } - - // Returns the data length for entry `index` - size_t entry_length(index_type index) const { - return Distance(entry_begin_pos(index), entry_end_pos(index)); - } - - // Returns the data for entry `index` - absl::string_view entry_data(index_type index) const; - - // Returns the position for `offset` as {index, prefix}. `index` holds the - // index of the entry at the specified offset and `prefix` holds the relative - // offset inside that entry. - // Requires `offset` < length. - // - // For example we can implement GetCharacter(offset) as: - // char GetCharacter(size_t offset) { - // Position pos = this->Find(offset); - // return this->entry_data(pos.pos)[pos.offset]; - // } - inline Position Find(size_t offset) const; - - // Find starting at `head` - inline Position Find(index_type head, size_t offset) const; - - // Returns the tail position for `offset` as {tail index, suffix}. - // `tail index` holds holds the index of the entry holding the offset directly - // before 'offset` advanced by one. 'suffix` holds the relative offset from - // that relative offset in the entry to the end of the entry. - // For example, FindTail(length) will return {tail(), 0}, FindTail(length - 5) - // will return {retreat(tail), 5)} provided the preceding entry contains at - // least 5 bytes of data. - // Requires offset >= 1 && offset <= length. - // - // This function is very useful in functions that need to clip the end of some - // ring buffer such as 'RemovePrefix'. - // For example, we could implement RemovePrefix for non shared instances as: - // void RemoveSuffix(size_t n) { - // Position pos = FindTail(length - n); - // UnrefEntries(pos.pos, this->tail_); - // this->tail_ = pos.pos; - // entry(retreat(pos.pos)).end_pos -= pos.offset; - // } - inline Position FindTail(size_t offset) const; - - // Find tail starting at `head` - inline Position FindTail(index_type head, size_t offset) const; - - // Invokes f(index_type index) for each entry inside the range [head, tail> - template <typename F> - void ForEach(index_type head, index_type tail, F&& f) const { - index_type n1 = (tail > head) ? tail : capacity_; - for (index_type i = head; i < n1; ++i) f(i); - if (tail <= head) { - for (index_type i = 0; i < tail; ++i) f(i); - } - } - - // Invokes f(index_type index) for each entry inside this instance. - template <typename F> - void ForEach(F&& f) const { - ForEach(head_, tail_, std::forward<F>(f)); - } - - // Dump this instance's data tp stream `s` in human readable format, excluding - // the actual data content itself. Intended for debug purposes only. - friend std::ostream& operator<<(std::ostream& s, const CordRepRing& rep); - - private: - enum class AddMode { kAppend, kPrepend }; - - using Layout = container_internal::Layout<pos_type, CordRep*, offset_type>; - - class Filler; - class Transaction; - class CreateTransaction; - - static constexpr size_t kLayoutAlignment = Layout::Partial().Alignment(); - - // Creates a new CordRepRing. - explicit CordRepRing(index_type capacity) : capacity_(capacity) {} - - // Returns true if `index` is a valid index into this instance. - bool IsValidIndex(index_type index) const; - - // Debug use only: validates the provided CordRepRing invariants. - // Verification of all CordRepRing methods can be enabled by defining - // EXTRA_CORD_RING_VALIDATION, i.e.: `--copts=-DEXTRA_CORD_RING_VALIDATION` - // Verification is VERY expensive, so only do it for debugging purposes. - static CordRepRing* Validate(CordRepRing* rep, const char* file = nullptr, - int line = 0); - - // Allocates a CordRepRing large enough to hold `capacity + extra' entries. - // The returned capacity may be larger if the allocated memory allows for it. - // The maximum capacity of a CordRepRing is capped at kMaxCapacity. - // Throws `std::length_error` if `capacity + extra' exceeds kMaxCapacity. - static CordRepRing* New(size_t capacity, size_t extra); - - // Deallocates (but does not destroy) the provided ring buffer. - static void Delete(CordRepRing* rep); - - // Destroys the provided ring buffer, decrementing the reference count of all - // contained child CordReps. The provided 1\`rep` should have a ref count of - // one (pre decrement destroy call observing `refcount.IsOne()`) or zero - // (post decrement destroy call observing `!refcount.Decrement()`). - static void Destroy(CordRepRing* rep); - - // Returns a mutable reference to the logical end position array. - pos_type* entry_end_pos() { - return Layout::Partial().Pointer<0>(data_); - } - - // Returns a mutable reference to the child pointer array. - CordRep** entry_child() { - return Layout::Partial(capacity()).Pointer<1>(data_); - } - - // Returns a mutable reference to the data offset array. - offset_type* entry_data_offset() { - return Layout::Partial(capacity(), capacity()).Pointer<2>(data_); - } - - // Find implementations for the non fast path 0 / length cases. - Position FindSlow(index_type head, size_t offset) const; - Position FindTailSlow(index_type head, size_t offset) const; - - // Finds the index of the first node that is inside a reasonable distance - // of the node at `offset` from which we can continue with a linear search. - template <bool wrap> - index_type FindBinary(index_type head, index_type tail, size_t offset) const; - - // Fills the current (initialized) instance from the provided source, copying - // entries [head, tail). Adds a reference to copied entries if `ref` is true. - template <bool ref> - void Fill(const CordRepRing* src, index_type head, index_type tail); - - // Create a copy of 'rep', copying all entries [head, tail), allocating room - // for `extra` entries. Adds a reference on all copied entries. - static CordRepRing* Copy(CordRepRing* rep, index_type head, index_type tail, - size_t extra = 0); - - // Returns a Mutable CordRepRing reference from `rep` with room for at least - // `extra` additional nodes. Adopts a reference count from `rep`. - // This function will return `rep` if, and only if: - // - rep.entries + extra <= rep.capacity - // - rep.refcount == 1 - // Otherwise, this function will create a new copy of `rep` with additional - // capacity to satisfy `extra` extra nodes, and unref the old `rep` instance. - // - // If a new CordRepRing can not be allocated, or the new capacity would exceed - // the maximum capacity, then the input is consumed only, and an exception is - // thrown. - static CordRepRing* Mutable(CordRepRing* rep, size_t extra); - - // Slow path for Append(CordRepRing* rep, CordRep* child). This function is - // exercised if the provided `child` in Append() is not a leaf node, i.e., a - // ring buffer or old (concat) cord tree. - static CordRepRing* AppendSlow(CordRepRing* rep, CordRep* child); - - // Appends the provided leaf node. Requires `child` to be FLAT or EXTERNAL. - static CordRepRing* AppendLeaf(CordRepRing* rep, CordRep* child, - size_t offset, size_t length); - - // Prepends the provided leaf node. Requires `child` to be FLAT or EXTERNAL. - static CordRepRing* PrependLeaf(CordRepRing* rep, CordRep* child, - size_t offset, size_t length); - - // Slow path for Prepend(CordRepRing* rep, CordRep* child). This function is - // exercised if the provided `child` in Prepend() is not a leaf node, i.e., a - // ring buffer or old (concat) cord tree. - static CordRepRing* PrependSlow(CordRepRing* rep, CordRep* child); - - // Slow path for Create(CordRep* child, size_t extra). This function is - // exercised if the provided `child` in Prepend() is not a leaf node, i.e., a - // ring buffer or old (concat) cord tree. - static CordRepRing* CreateSlow(CordRep* child, size_t extra); - - // Creates a new ring buffer from the provided `child` leaf node. Requires - // `child` to be FLAT or EXTERNAL. on `rep`. - // The returned ring buffer has a capacity of at least `1 + extra` - static CordRepRing* CreateFromLeaf(CordRep* child, size_t offset, - size_t length, size_t extra); - - // Appends or prepends (depending on AddMode) the ring buffer in `ring' to - // `rep` starting at `offset` with length `len`. - template <AddMode mode> - static CordRepRing* AddRing(CordRepRing* rep, CordRepRing* ring, - size_t offset, size_t len); - - // Increases the data offset for entry `index` by `n`. - void AddDataOffset(index_type index, size_t n); - - // Decreases the length for entry `index` by `n`. - void SubLength(index_type index, size_t n); - - index_type head_; - index_type tail_; - index_type capacity_; - pos_type begin_pos_; - - alignas(kLayoutAlignment) char data_[kLayoutAlignment]; - - friend struct CordRep; -}; - -constexpr size_t CordRepRing::AllocSize(size_t capacity) { - return sizeof(CordRepRing) - sizeof(data_) + - Layout(capacity, capacity, capacity).AllocSize(); -} - -inline constexpr size_t CordRepRing::Distance(pos_type pos, pos_type end_pos) { - return (end_pos - pos); -} - -inline const char* CordRepRing::GetLeafData(const CordRep* rep) { - return rep->tag != EXTERNAL ? rep->flat()->Data() : rep->external()->base; -} - -inline const char* CordRepRing::GetRepData(const CordRep* rep) { - if (rep->tag >= FLAT) return rep->flat()->Data(); - if (rep->tag == EXTERNAL) return rep->external()->base; - return GetLeafData(rep->substring()->child) + rep->substring()->start; -} - -inline CordRepRing::index_type CordRepRing::advance(index_type index) const { - assert(index < capacity_); - return ++index == capacity_ ? 0 : index; -} - -inline CordRepRing::index_type CordRepRing::advance(index_type index, - index_type n) const { - assert(index < capacity_ && n <= capacity_); - return (index += n) >= capacity_ ? index - capacity_ : index; -} - -inline CordRepRing::index_type CordRepRing::retreat(index_type index) const { - assert(index < capacity_); - return (index > 0 ? index : capacity_) - 1; -} - -inline CordRepRing::index_type CordRepRing::retreat(index_type index, - index_type n) const { - assert(index < capacity_ && n <= capacity_); - return index >= n ? index - n : capacity_ - n + index; -} - -inline absl::string_view CordRepRing::entry_data(index_type index) const { - size_t data_offset = entry_data_offset(index); - return {GetRepData(entry_child(index)) + data_offset, entry_length(index)}; -} - -inline bool CordRepRing::IsValidIndex(index_type index) const { - if (index >= capacity_) return false; - return (tail_ > head_) ? (index >= head_ && index < tail_) - : (index >= head_ || index < tail_); -} - -#ifndef EXTRA_CORD_RING_VALIDATION -inline CordRepRing* CordRepRing::Validate(CordRepRing* rep, - const char* /*file*/, int /*line*/) { - return rep; -} -#endif - -inline CordRepRing::Position CordRepRing::Find(size_t offset) const { - assert(offset < length); - return (offset == 0) ? Position{head_, 0} : FindSlow(head_, offset); -} - -inline CordRepRing::Position CordRepRing::Find(index_type head, - size_t offset) const { - assert(offset < length); - assert(IsValidIndex(head) && offset >= entry_start_offset(head)); - return (offset == 0) ? Position{head_, 0} : FindSlow(head, offset); -} - -inline CordRepRing::Position CordRepRing::FindTail(size_t offset) const { - assert(offset > 0 && offset <= length); - return (offset == length) ? Position{tail_, 0} : FindTailSlow(head_, offset); -} - -inline CordRepRing::Position CordRepRing::FindTail(index_type head, - size_t offset) const { - assert(offset > 0 && offset <= length); - assert(IsValidIndex(head) && offset >= entry_start_offset(head) + 1); - return (offset == length) ? Position{tail_, 0} : FindTailSlow(head, offset); -} - -// Now that CordRepRing is defined, we can define CordRep's helper casts: -inline CordRepRing* CordRep::ring() { - assert(IsRing()); - return static_cast<CordRepRing*>(this); -} - -inline const CordRepRing* CordRep::ring() const { - assert(IsRing()); - return static_cast<const CordRepRing*>(this); -} - -inline bool CordRepRing::IsFlat(absl::string_view* fragment) const { - if (entries() == 1) { - if (fragment) *fragment = entry_data(head()); - return true; - } - return false; -} - -inline bool CordRepRing::IsFlat(size_t offset, size_t len, - absl::string_view* fragment) const { - const Position pos = Find(offset); - const absl::string_view data = entry_data(pos.index); - if (data.length() >= len && data.length() - len >= pos.offset) { - if (fragment) *fragment = data.substr(pos.offset, len); - return true; - } - return false; -} - -std::ostream& operator<<(std::ostream& s, const CordRepRing& rep); - -} // namespace cord_internal -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_STRINGS_INTERNAL_CORD_REP_RING_H_ diff --git a/absl/strings/internal/cord_rep_ring_reader.h b/absl/strings/internal/cord_rep_ring_reader.h deleted file mode 100644 index 7ceeaa00..00000000 --- a/absl/strings/internal/cord_rep_ring_reader.h +++ /dev/null @@ -1,118 +0,0 @@ -// Copyright 2021 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. - -#ifndef ABSL_STRINGS_INTERNAL_CORD_REP_RING_READER_H_ -#define ABSL_STRINGS_INTERNAL_CORD_REP_RING_READER_H_ - -#include <cassert> -#include <cstddef> -#include <cstdint> - -#include "absl/strings/internal/cord_internal.h" -#include "absl/strings/internal/cord_rep_ring.h" -#include "absl/strings/string_view.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace cord_internal { - -// CordRepRingReader provides basic navigation over CordRepRing data. -class CordRepRingReader { - public: - // Returns true if this instance is not empty. - explicit operator bool() const { return ring_ != nullptr; } - - // Returns the ring buffer reference for this instance, or nullptr if empty. - CordRepRing* ring() const { return ring_; } - - // Returns the current node index inside the ring buffer for this instance. - // The returned value is undefined if this instance is empty. - CordRepRing::index_type index() const { return index_; } - - // Returns the current node inside the ring buffer for this instance. - // The returned value is undefined if this instance is empty. - CordRep* node() const { return ring_->entry_child(index_); } - - // Returns the length of the referenced ring buffer. - // Requires the current instance to be non empty. - size_t length() const { - assert(ring_); - return ring_->length; - } - - // Returns the end offset of the last navigated-to chunk, which represents the - // total bytes 'consumed' relative to the start of the ring. The returned - // value is never zero. For example, initializing a reader with a ring buffer - // with a first chunk of 19 bytes will return consumed() = 19. - // Requires the current instance to be non empty. - size_t consumed() const { - assert(ring_); - return ring_->entry_end_offset(index_); - } - - // Returns the number of bytes remaining beyond the last navigated-to chunk. - // Requires the current instance to be non empty. - size_t remaining() const { - assert(ring_); - return length() - consumed(); - } - - // Resets this instance to an empty value - void Reset() { ring_ = nullptr; } - - // Resets this instance to the start of `ring`. `ring` must not be null. - // Returns a reference into the first chunk of the provided ring. - absl::string_view Reset(CordRepRing* ring) { - assert(ring); - ring_ = ring; - index_ = ring_->head(); - return ring_->entry_data(index_); - } - - // Navigates to the next chunk inside the reference ring buffer. - // Returns a reference into the navigated-to chunk. - // Requires remaining() to be non zero. - absl::string_view Next() { - assert(remaining()); - index_ = ring_->advance(index_); - return ring_->entry_data(index_); - } - - // Navigates to the chunk at offset `offset`. - // Returns a reference into the navigated-to chunk, adjusted for the relative - // position of `offset` into that chunk. For example, calling Seek(13) on a - // ring buffer containing 2 chunks of 10 and 20 bytes respectively will return - // a string view into the second chunk starting at offset 3 with a size of 17. - // Requires `offset` to be less than `length()` - absl::string_view Seek(size_t offset) { - assert(offset < length()); - size_t current = ring_->entry_end_offset(index_); - CordRepRing::index_type hint = (offset >= current) ? index_ : ring_->head(); - const CordRepRing::Position head = ring_->Find(hint, offset); - index_ = head.index; - auto data = ring_->entry_data(head.index); - data.remove_prefix(head.offset); - return data; - } - - private: - CordRepRing* ring_ = nullptr; - CordRepRing::index_type index_; -}; - -} // namespace cord_internal -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_STRINGS_INTERNAL_CORD_REP_RING_READER_H_ diff --git a/absl/strings/internal/cordz_info.cc b/absl/strings/internal/cordz_info.cc index 515dfafb..b24c3da7 100644 --- a/absl/strings/internal/cordz_info.cc +++ b/absl/strings/internal/cordz_info.cc @@ -21,7 +21,6 @@ #include "absl/strings/internal/cord_internal.h" #include "absl/strings/internal/cord_rep_btree.h" #include "absl/strings/internal/cord_rep_crc.h" -#include "absl/strings/internal/cord_rep_ring.h" #include "absl/strings/internal/cordz_handle.h" #include "absl/strings/internal/cordz_statistics.h" #include "absl/strings/internal/cordz_update_tracker.h" @@ -33,8 +32,6 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace cord_internal { -using ::absl::base_internal::SpinLockHolder; - #ifdef ABSL_INTERNAL_NEED_REDUNDANT_CONSTEXPR_DECL constexpr size_t CordzInfo::kMaxStackDepth; #endif @@ -79,6 +76,8 @@ class CordRepAnalyzer { // adds the results to `statistics`. Note that node counts and memory sizes // are not initialized, computed values are added to any existing values. void AnalyzeCordRep(const CordRep* rep) { + ABSL_ASSERT(rep != nullptr); + // Process all linear nodes. // As per the class comments, use refcout - 1 on the top level node, as the // top level node is assumed to be referenced only for analysis purposes. @@ -86,7 +85,7 @@ class CordRepAnalyzer { RepRef repref{rep, (refcount > 1) ? refcount - 1 : 1}; // Process the top level CRC node, if present. - if (repref.rep->tag == CRC) { + if (repref.tag() == CRC) { statistics_.node_count++; statistics_.node_counts.crc++; memory_usage_.Add(sizeof(CordRepCrc), repref.refcount); @@ -96,15 +95,14 @@ class CordRepAnalyzer { // Process all top level linear nodes (substrings and flats). repref = CountLinearReps(repref, memory_usage_); - if (repref.rep != nullptr) { - if (repref.rep->tag == RING) { - AnalyzeRing(repref); - } else if (repref.rep->tag == BTREE) { + switch (repref.tag()) { + case CordRepKind::BTREE: AnalyzeBtree(repref); - } else { - // We should have either a concat, btree, or ring node if not null. - assert(false); - } + break; + default: + // We should have a btree node if not null. + ABSL_ASSERT(repref.tag() == CordRepKind::UNUSED_0); + break; } // Adds values to output @@ -122,11 +120,19 @@ class CordRepAnalyzer { const CordRep* rep; size_t refcount; - // Returns a 'child' RepRef which contains the cumulative reference count of - // this instance multiplied by the child's reference count. + // Returns a 'child' RepRef which contains the cumulative reference count + // of this instance multiplied by the child's reference count. Returns a + // nullptr RepRef value with a refcount of 0 if `child` is nullptr. RepRef Child(const CordRep* child) const { + if (child == nullptr) return RepRef{nullptr, 0}; return RepRef{child, refcount * child->refcount.Get()}; } + + // Returns the tag of this rep, or UNUSED_0 if this instance is null + constexpr CordRepKind tag() const { + ABSL_ASSERT(rep == nullptr || rep->tag != CordRepKind::UNUSED_0); + return rep ? static_cast<CordRepKind>(rep->tag) : CordRepKind::UNUSED_0; + } }; // Memory usage values @@ -167,7 +173,7 @@ class CordRepAnalyzer { // buffers where we count children unrounded. RepRef CountLinearReps(RepRef rep, MemoryUsage& memory_usage) { // Consume all substrings - while (rep.rep->tag == SUBSTRING) { + while (rep.tag() == SUBSTRING) { statistics_.node_count++; statistics_.node_counts.substring++; memory_usage.Add(sizeof(CordRepSubstring), rep.refcount); @@ -175,7 +181,7 @@ class CordRepAnalyzer { } // Consume possible FLAT - if (rep.rep->tag >= FLAT) { + if (rep.tag() >= FLAT) { size_t size = rep.rep->flat()->AllocatedSize(); CountFlat(size); memory_usage.Add(size, rep.refcount); @@ -183,7 +189,7 @@ class CordRepAnalyzer { } // Consume possible external - if (rep.rep->tag == EXTERNAL) { + if (rep.tag() == EXTERNAL) { statistics_.node_count++; statistics_.node_counts.external++; size_t size = rep.rep->length + sizeof(CordRepExternalImpl<intptr_t>); @@ -194,17 +200,6 @@ class CordRepAnalyzer { return rep; } - // Analyzes the provided ring. - void AnalyzeRing(RepRef rep) { - statistics_.node_count++; - statistics_.node_counts.ring++; - const CordRepRing* ring = rep.rep->ring(); - memory_usage_.Add(CordRepRing::AllocSize(ring->capacity()), rep.refcount); - ring->ForEach([&](CordRepRing::index_type pos) { - CountLinearReps(rep.Child(ring->entry_child(pos)), memory_usage_); - }); - } - // Analyzes the provided btree. void AnalyzeBtree(RepRef rep) { statistics_.node_count++; diff --git a/absl/strings/internal/cordz_info_statistics_test.cc b/absl/strings/internal/cordz_info_statistics_test.cc index 53d2f2ea..d55773f2 100644 --- a/absl/strings/internal/cordz_info_statistics_test.cc +++ b/absl/strings/internal/cordz_info_statistics_test.cc @@ -25,7 +25,6 @@ #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/internal/cordz_info.h" #include "absl/strings/internal/cordz_sample_token.h" #include "absl/strings/internal/cordz_statistics.h" @@ -123,11 +122,6 @@ size_t SizeOf(const CordRepExternal* rep) { return sizeof(CordRepExternalImpl<intptr_t>) + rep->length; } -template <> -size_t SizeOf(const CordRepRing* rep) { - return CordRepRing::AllocSize(rep->capacity()); -} - // Computes fair share memory used in a naive 'we dare to recurse' way. double FairShareImpl(CordRep* rep, size_t ref) { double self = 0.0, children = 0.0; @@ -144,11 +138,6 @@ double FairShareImpl(CordRep* rep, size_t ref) { for (CordRep*edge : rep->btree()->Edges()) { children += FairShareImpl(edge, ref); } - } else if (rep->tag == RING) { - self = SizeOf(rep->ring()); - rep->ring()->ForEach([&](CordRepRing::index_type i) { - self += FairShareImpl(rep->ring()->entry_child(i), 1); - }); } else { assert(false); } @@ -294,64 +283,6 @@ TEST(CordzInfoStatisticsTest, SharedSubstring) { EXPECT_THAT(SampleCord(substring), EqStatistics(expected)); } - -TEST(CordzInfoStatisticsTest, Ring) { - RefHelper ref; - auto* flat1 = Flat(240); - auto* flat2 = Flat(2000); - auto* flat3 = Flat(70); - auto* external = External(3000); - CordRepRing* ring = CordRepRing::Create(flat1); - ring = CordRepRing::Append(ring, flat2); - ring = CordRepRing::Append(ring, flat3); - ring = ref.NeedsUnref(CordRepRing::Append(ring, external)); - - CordzStatistics expected; - expected.size = ring->length; - expected.estimated_memory_usage = SizeOf(ring) + SizeOf(flat1) + - SizeOf(flat2) + SizeOf(flat3) + - SizeOf(external); - expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage; - expected.node_count = 5; - expected.node_counts.flat = 3; - expected.node_counts.flat_128 = 1; - expected.node_counts.flat_256 = 1; - expected.node_counts.external = 1; - expected.node_counts.ring = 1; - - EXPECT_THAT(SampleCord(ring), EqStatistics(expected)); -} - -TEST(CordzInfoStatisticsTest, SharedSubstringRing) { - RefHelper ref; - auto* flat1 = ref.Ref(Flat(240)); - auto* flat2 = Flat(200); - auto* flat3 = Flat(70); - auto* external = ref.Ref(External(3000), 5); - CordRepRing* ring = CordRepRing::Create(flat1); - ring = CordRepRing::Append(ring, flat2); - ring = CordRepRing::Append(ring, flat3); - ring = ref.Ref(CordRepRing::Append(ring, external), 4); - auto* substring = ref.Ref(ref.NeedsUnref(Substring(ring))); - - - CordzStatistics expected; - expected.size = substring->length; - expected.estimated_memory_usage = SizeOf(ring) + SizeOf(flat1) + - SizeOf(flat2) + SizeOf(flat3) + - SizeOf(external) + SizeOf(substring); - expected.estimated_fair_share_memory_usage = FairShare(substring); - expected.node_count = 6; - expected.node_counts.flat = 3; - expected.node_counts.flat_128 = 1; - expected.node_counts.flat_256 = 2; - expected.node_counts.external = 1; - expected.node_counts.ring = 1; - expected.node_counts.substring = 1; - - EXPECT_THAT(SampleCord(substring), EqStatistics(expected)); -} - TEST(CordzInfoStatisticsTest, BtreeLeaf) { ASSERT_THAT(CordRepBtree::kMaxCapacity, Ge(3u)); RefHelper ref; @@ -452,8 +383,7 @@ TEST(CordzInfoStatisticsTest, BtreeNodeShared) { TEST(CordzInfoStatisticsTest, Crc) { RefHelper ref; auto* left = Flat(1000); - auto* crc = - ref.NeedsUnref(CordRepCrc::New(left, crc_internal::CrcCordState())); + auto* crc = ref.NeedsUnref(CordRepCrc::New(left, {})); CordzStatistics expected; expected.size = left->length; @@ -467,6 +397,20 @@ TEST(CordzInfoStatisticsTest, Crc) { EXPECT_THAT(SampleCord(crc), EqStatistics(expected)); } +TEST(CordzInfoStatisticsTest, EmptyCrc) { + RefHelper ref; + auto* crc = ref.NeedsUnref(CordRepCrc::New(nullptr, {})); + + CordzStatistics expected; + expected.size = 0; + expected.estimated_memory_usage = SizeOf(crc); + expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage; + expected.node_count = 1; + expected.node_counts.crc = 1; + + EXPECT_THAT(SampleCord(crc), EqStatistics(expected)); +} + TEST(CordzInfoStatisticsTest, ThreadSafety) { Notification stop; static constexpr int kNumThreads = 8; @@ -497,6 +441,7 @@ TEST(CordzInfoStatisticsTest, ThreadSafety) { InlineData cords[2]; std::minstd_rand gen; std::uniform_int_distribution<int> coin_toss(0, 1); + std::uniform_int_distribution<int> dice_roll(1, 6); while (!stop.HasBeenNotified()) { for (InlineData& cord : cords) { @@ -514,13 +459,21 @@ TEST(CordzInfoStatisticsTest, ThreadSafety) { CordRep::Unref(cord.as_tree()); cord.set_inline_size(0); } else { - // Coin toss to 25% ring, 25% btree, and 50% flat. + // Coin toss to 50% btree, and 50% flat. CordRep* rep = Flat(256); if (coin_toss(gen) != 0) { - if (coin_toss(gen) != 0) { - rep = CordRepRing::Create(rep); + rep = CordRepBtree::Create(rep); + } + + // Maybe CRC this cord + if (dice_roll(gen) == 6) { + if (dice_roll(gen) == 6) { + // Empty CRC rep + CordRep::Unref(rep); + rep = CordRepCrc::New(nullptr, {}); } else { - rep = CordRepBtree::Create(rep); + // Regular CRC rep + rep = CordRepCrc::New(rep, {}); } } cord.make_tree(rep); diff --git a/absl/strings/internal/has_absl_stringify.h b/absl/strings/internal/has_absl_stringify.h index 55a08508..f82cfe26 100644 --- a/absl/strings/internal/has_absl_stringify.h +++ b/absl/strings/internal/has_absl_stringify.h @@ -1,4 +1,4 @@ -// Copyright 2022 The Abseil Authors +// Copyright 2024 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. @@ -14,38 +14,27 @@ #ifndef ABSL_STRINGS_INTERNAL_HAS_ABSL_STRINGIFY_H_ #define ABSL_STRINGS_INTERNAL_HAS_ABSL_STRINGIFY_H_ -#include <string> -#include <type_traits> -#include <utility> -#include "absl/strings/string_view.h" +#include "absl/strings/has_absl_stringify.h" + +#include "absl/base/config.h" namespace absl { ABSL_NAMESPACE_BEGIN namespace strings_internal { -// This is an empty class not intended to be used. It exists so that -// `HasAbslStringify` can reference a universal class rather than needing to be -// copied for each new sink. -class UnimplementedSink { - public: - void Append(size_t count, char ch); - - void Append(string_view v); - - // Support `absl::Format(&sink, format, args...)`. - friend void AbslFormatFlush(UnimplementedSink* sink, absl::string_view v); -}; - -template <typename T, typename = void> -struct HasAbslStringify : std::false_type {}; - -template <typename T> -struct HasAbslStringify< - T, std::enable_if_t<std::is_void<decltype(AbslStringify( - std::declval<strings_internal::UnimplementedSink&>(), - std::declval<const T&>()))>::value>> : std::true_type {}; +// This exists to fix a circular dependency problem with the GoogleTest release. +// GoogleTest referenced this internal file and this internal trait. Since +// simultaneous releases are not possible since once release must reference +// another, we will temporarily add this back. +// https://github.com/google/googletest/blob/v1.14.x/googletest/include/gtest/gtest-printers.h#L119 +// +// This file can be deleted after the next Abseil and GoogleTest release. +// +// https://github.com/google/googletest/pull/4368#issuecomment-1717699895 +// https://github.com/google/googletest/pull/4368#issuecomment-1717699895 +using ::absl::HasAbslStringify; } // namespace strings_internal diff --git a/absl/strings/internal/memutil.cc b/absl/strings/internal/memutil.cc index e2e7347c..0bbd8aa1 100644 --- a/absl/strings/internal/memutil.cc +++ b/absl/strings/internal/memutil.cc @@ -27,10 +27,18 @@ int memcasecmp(const char* s1, const char* s2, size_t len) { const unsigned char* us2 = reinterpret_cast<const unsigned char*>(s2); for (size_t i = 0; i < len; i++) { - const int diff = - int{static_cast<unsigned char>(absl::ascii_tolower(us1[i]))} - - int{static_cast<unsigned char>(absl::ascii_tolower(us2[i]))}; - if (diff != 0) return diff; + unsigned char c1 = us1[i]; + unsigned char c2 = us2[i]; + // If bytes are the same, they will be the same when converted to lower. + // So we only need to convert if bytes are not equal. + // NOTE(b/308193381): We do not use `absl::ascii_tolower` here in order + // to avoid its lookup table and improve performance. + if (c1 != c2) { + c1 = c1 >= 'A' && c1 <= 'Z' ? c1 - 'A' + 'a' : c1; + c2 = c2 >= 'A' && c2 <= 'Z' ? c2 - 'A' + 'a' : c2; + const int diff = int{c1} - int{c2}; + if (diff != 0) return diff; + } } return 0; } diff --git a/absl/strings/internal/str_format/arg.cc b/absl/strings/internal/str_format/arg.cc index c0a9a28e..eeb21081 100644 --- a/absl/strings/internal/str_format/arg.cc +++ b/absl/strings/internal/str_format/arg.cc @@ -18,15 +18,28 @@ // #include "absl/strings/internal/str_format/arg.h" +#include <algorithm> #include <cassert> -#include <cerrno> +#include <cstddef> +#include <cstdint> #include <cstdlib> +#include <cstring> +#include <cwchar> #include <string> #include <type_traits> -#include "absl/base/port.h" +#include "absl/base/config.h" +#include "absl/base/optimization.h" +#include "absl/container/fixed_array.h" +#include "absl/numeric/int128.h" +#include "absl/strings/internal/str_format/extension.h" #include "absl/strings/internal/str_format/float_conversion.h" #include "absl/strings/numbers.h" +#include "absl/strings/string_view.h" + +#if defined(ABSL_HAVE_STD_STRING_VIEW) +#include <string_view> +#endif namespace absl { ABSL_NAMESPACE_BEGIN @@ -298,6 +311,83 @@ inline bool ConvertStringArg(string_view v, const FormatConversionSpecImpl conv, conv.has_left_flag()); } +struct ShiftState { + bool saw_high_surrogate = false; + uint8_t bits = 0; +}; + +// Converts `v` from UTF-16 or UTF-32 to UTF-8 and writes to `buf`. `buf` is +// assumed to have enough space for the output. `s` is used to carry state +// between successive calls with a UTF-16 surrogate pair. Returns the number of +// chars written, or `static_cast<size_t>(-1)` on failure. +// +// This is basically std::wcrtomb(), but always outputting UTF-8 instead of +// respecting the current locale. +inline size_t WideToUtf8(wchar_t wc, char *buf, ShiftState &s) { + const auto v = static_cast<uint32_t>(wc); + if (v < 0x80) { + *buf = static_cast<char>(v); + return 1; + } else if (v < 0x800) { + *buf++ = static_cast<char>(0xc0 | (v >> 6)); + *buf = static_cast<char>(0x80 | (v & 0x3f)); + return 2; + } else if (v < 0xd800 || (v - 0xe000) < 0x2000) { + *buf++ = static_cast<char>(0xe0 | (v >> 12)); + *buf++ = static_cast<char>(0x80 | ((v >> 6) & 0x3f)); + *buf = static_cast<char>(0x80 | (v & 0x3f)); + return 3; + } else if ((v - 0x10000) < 0x100000) { + *buf++ = static_cast<char>(0xf0 | (v >> 18)); + *buf++ = static_cast<char>(0x80 | ((v >> 12) & 0x3f)); + *buf++ = static_cast<char>(0x80 | ((v >> 6) & 0x3f)); + *buf = static_cast<char>(0x80 | (v & 0x3f)); + return 4; + } else if (v < 0xdc00) { + s.saw_high_surrogate = true; + s.bits = static_cast<uint8_t>(v & 0x3); + const uint8_t high_bits = ((v >> 6) & 0xf) + 1; + *buf++ = static_cast<char>(0xf0 | (high_bits >> 2)); + *buf = + static_cast<char>(0x80 | static_cast<uint8_t>((high_bits & 0x3) << 4) | + static_cast<uint8_t>((v >> 2) & 0xf)); + return 2; + } else if (v < 0xe000 && s.saw_high_surrogate) { + *buf++ = static_cast<char>(0x80 | static_cast<uint8_t>(s.bits << 4) | + static_cast<uint8_t>((v >> 6) & 0xf)); + *buf = static_cast<char>(0x80 | (v & 0x3f)); + s.saw_high_surrogate = false; + s.bits = 0; + return 2; + } else { + return static_cast<size_t>(-1); + } +} + +inline bool ConvertStringArg(const wchar_t *v, + size_t len, + const FormatConversionSpecImpl conv, + FormatSinkImpl *sink) { + FixedArray<char> mb(len * 4); + ShiftState s; + size_t chars_written = 0; + for (size_t i = 0; i < len; ++i) { + const size_t chars = WideToUtf8(v[i], &mb[chars_written], s); + if (chars == static_cast<size_t>(-1)) { return false; } + chars_written += chars; + } + return ConvertStringArg(string_view(mb.data(), chars_written), conv, sink); +} + +bool ConvertWCharTImpl(wchar_t v, const FormatConversionSpecImpl conv, + FormatSinkImpl *sink) { + char mb[4]; + ShiftState s; + const size_t chars_written = WideToUtf8(v, mb, s); + return chars_written != static_cast<size_t>(-1) && !s.saw_high_surrogate && + ConvertStringArg(string_view(mb, chars_written), conv, sink); +} + } // namespace bool ConvertBoolArg(bool v, FormatSinkImpl *sink) { @@ -316,11 +406,14 @@ bool ConvertIntArg(T v, FormatConversionSpecImpl conv, FormatSinkImpl *sink) { // This odd casting is due to a bug in -Wswitch behavior in gcc49 which causes // it to complain about a switch/case type mismatch, even though both are - // FormatConverionChar. Likely this is because at this point + // FormatConversionChar. Likely this is because at this point // FormatConversionChar is declared, but not defined. switch (static_cast<uint8_t>(conv.conversion_char())) { case static_cast<uint8_t>(FormatConversionCharInternal::c): - return ConvertCharImpl(static_cast<char>(v), conv, sink); + return (std::is_same<T, wchar_t>::value || + (conv.length_mod() == LengthMod::l)) + ? ConvertWCharTImpl(static_cast<wchar_t>(v), conv, sink) + : ConvertCharImpl(static_cast<char>(v), conv, sink); case static_cast<uint8_t>(FormatConversionCharInternal::o): as_digits.PrintAsOct(static_cast<U>(v)); @@ -372,6 +465,8 @@ template bool ConvertIntArg<signed char>(signed char v, template bool ConvertIntArg<unsigned char>(unsigned char v, FormatConversionSpecImpl conv, FormatSinkImpl *sink); +template bool ConvertIntArg<wchar_t>(wchar_t v, FormatConversionSpecImpl conv, + FormatSinkImpl *sink); template bool ConvertIntArg<short>(short v, // NOLINT FormatConversionSpecImpl conv, FormatSinkImpl *sink); @@ -403,16 +498,29 @@ StringConvertResult FormatConvertImpl(const std::string &v, return {ConvertStringArg(v, conv, sink)}; } +StringConvertResult FormatConvertImpl(const std::wstring &v, + const FormatConversionSpecImpl conv, + FormatSinkImpl *sink) { + return {ConvertStringArg(v.data(), v.size(), conv, sink)}; +} + StringConvertResult FormatConvertImpl(string_view v, const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertStringArg(v, conv, sink)}; } -ArgConvertResult<FormatConversionCharSetUnion( - FormatConversionCharSetInternal::s, FormatConversionCharSetInternal::p)> -FormatConvertImpl(const char *v, const FormatConversionSpecImpl conv, - FormatSinkImpl *sink) { +#if defined(ABSL_HAVE_STD_STRING_VIEW) +StringConvertResult FormatConvertImpl(std::wstring_view v, + const FormatConversionSpecImpl conv, + FormatSinkImpl* sink) { + return {ConvertStringArg(v.data(), v.size(), conv, sink)}; +} +#endif + +StringPtrConvertResult FormatConvertImpl(const char* v, + const FormatConversionSpecImpl conv, + FormatSinkImpl* sink) { if (conv.conversion_char() == FormatConversionCharInternal::p) return {FormatConvertImpl(VoidPtr(v), conv, sink).value}; size_t len; @@ -427,6 +535,30 @@ FormatConvertImpl(const char *v, const FormatConversionSpecImpl conv, return {ConvertStringArg(string_view(v, len), conv, sink)}; } +StringPtrConvertResult FormatConvertImpl(const wchar_t* v, + const FormatConversionSpecImpl conv, + FormatSinkImpl* sink) { + if (conv.conversion_char() == FormatConversionCharInternal::p) { + return {FormatConvertImpl(VoidPtr(v), conv, sink).value}; + } + size_t len; + if (v == nullptr) { + len = 0; + } else if (conv.precision() < 0) { + len = std::wcslen(v); + } else { + // If precision is set, we look for the NUL-terminator on the valid range. + len = static_cast<size_t>(std::find(v, v + conv.precision(), L'\0') - v); + } + return {ConvertStringArg(v, len, conv, sink)}; +} + +StringPtrConvertResult FormatConvertImpl(std::nullptr_t, + const FormatConversionSpecImpl conv, + FormatSinkImpl* sink) { + return FormatConvertImpl(static_cast<const char*>(nullptr), conv, sink); +} + // ==================== Raw pointers ==================== ArgConvertResult<FormatConversionCharSetInternal::p> FormatConvertImpl( VoidPtr v, const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { @@ -461,6 +593,11 @@ CharConvertResult FormatConvertImpl(char v, const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertIntArg(v, conv, sink)}; } +CharConvertResult FormatConvertImpl(wchar_t v, + const FormatConversionSpecImpl conv, + FormatSinkImpl* sink) { + return {ConvertIntArg(v, conv, sink)}; +} // ==================== Ints ==================== IntegralConvertResult FormatConvertImpl(signed char v, diff --git a/absl/strings/internal/str_format/arg.h b/absl/strings/internal/str_format/arg.h index 3ce30feb..309161d5 100644 --- a/absl/strings/internal/str_format/arg.h +++ b/absl/strings/internal/str_format/arg.h @@ -19,8 +19,9 @@ #include <wchar.h> #include <algorithm> +#include <cstddef> +#include <cstdint> #include <cstdio> -#include <iomanip> #include <limits> #include <memory> #include <sstream> @@ -28,13 +29,18 @@ #include <type_traits> #include <utility> -#include "absl/base/port.h" +#include "absl/base/config.h" +#include "absl/base/optimization.h" #include "absl/meta/type_traits.h" #include "absl/numeric/int128.h" -#include "absl/strings/internal/has_absl_stringify.h" +#include "absl/strings/has_absl_stringify.h" #include "absl/strings/internal/str_format/extension.h" #include "absl/strings/string_view.h" +#if defined(ABSL_HAVE_STD_STRING_VIEW) +#include <string_view> +#endif + namespace absl { ABSL_NAMESPACE_BEGIN @@ -97,6 +103,9 @@ extern template bool ConvertIntArg<signed char>(signed char v, extern template bool ConvertIntArg<unsigned char>(unsigned char v, FormatConversionSpecImpl conv, FormatSinkImpl* sink); +extern template bool ConvertIntArg<wchar_t>(wchar_t v, + FormatConversionSpecImpl conv, + FormatSinkImpl* sink); extern template bool ConvertIntArg<short>(short v, // NOLINT FormatConversionSpecImpl conv, FormatSinkImpl* sink); @@ -158,6 +167,7 @@ template <typename T> auto FormatConvertImpl(const T& v, FormatConversionSpecImpl, FormatSinkImpl* sink) -> std::enable_if_t<!std::is_enum<T>::value && + !std::is_same<T, absl::Cord>::value && std::is_void<decltype(AbslStringify( std::declval<FormatSink&>(), v))>::value, ArgConvertResult<FormatConversionCharSetInternal::v>> { @@ -202,30 +212,49 @@ constexpr FormatConversionCharSet ExtractCharSet(ArgConvertResult<C>) { return C; } -using StringConvertResult = ArgConvertResult<FormatConversionCharSetUnion( - FormatConversionCharSetInternal::s, FormatConversionCharSetInternal::v)>; ArgConvertResult<FormatConversionCharSetInternal::p> FormatConvertImpl( VoidPtr v, FormatConversionSpecImpl conv, FormatSinkImpl* sink); // Strings. +using StringConvertResult = ArgConvertResult<FormatConversionCharSetUnion( + FormatConversionCharSetInternal::s, + FormatConversionCharSetInternal::v)>; StringConvertResult FormatConvertImpl(const std::string& v, FormatConversionSpecImpl conv, FormatSinkImpl* sink); +StringConvertResult FormatConvertImpl(const std::wstring& v, + FormatConversionSpecImpl conv, + FormatSinkImpl* sink); StringConvertResult FormatConvertImpl(string_view v, FormatConversionSpecImpl conv, FormatSinkImpl* sink); -#if defined(ABSL_HAVE_STD_STRING_VIEW) && !defined(ABSL_USES_STD_STRING_VIEW) +#if defined(ABSL_HAVE_STD_STRING_VIEW) +StringConvertResult FormatConvertImpl(std::wstring_view v, + FormatConversionSpecImpl conv, + FormatSinkImpl* sink); +#if !defined(ABSL_USES_STD_STRING_VIEW) inline StringConvertResult FormatConvertImpl(std::string_view v, FormatConversionSpecImpl conv, FormatSinkImpl* sink) { return FormatConvertImpl(absl::string_view(v.data(), v.size()), conv, sink); } -#endif // ABSL_HAVE_STD_STRING_VIEW && !ABSL_USES_STD_STRING_VIEW - -ArgConvertResult<FormatConversionCharSetUnion( - FormatConversionCharSetInternal::s, FormatConversionCharSetInternal::p)> -FormatConvertImpl(const char* v, const FormatConversionSpecImpl conv, - FormatSinkImpl* sink); +#endif // !ABSL_USES_STD_STRING_VIEW +#endif // ABSL_HAVE_STD_STRING_VIEW + +using StringPtrConvertResult = ArgConvertResult<FormatConversionCharSetUnion( + FormatConversionCharSetInternal::s, + FormatConversionCharSetInternal::p)>; +StringPtrConvertResult FormatConvertImpl(const char* v, + FormatConversionSpecImpl conv, + FormatSinkImpl* sink); +StringPtrConvertResult FormatConvertImpl(const wchar_t* v, + FormatConversionSpecImpl conv, + FormatSinkImpl* sink); +// This overload is needed to disambiguate, since `nullptr` could match either +// of the other overloads equally well. +StringPtrConvertResult FormatConvertImpl(std::nullptr_t, + FormatConversionSpecImpl conv, + FormatSinkImpl* sink); template <class AbslCord, typename std::enable_if<std::is_same< AbslCord, absl::Cord>::value>::type* = nullptr> @@ -279,6 +308,9 @@ FloatingConvertResult FormatConvertImpl(long double v, // Chars. CharConvertResult FormatConvertImpl(char v, FormatConversionSpecImpl conv, FormatSinkImpl* sink); +CharConvertResult FormatConvertImpl(wchar_t v, + FormatConversionSpecImpl conv, + FormatSinkImpl* sink); // Ints. IntegralConvertResult FormatConvertImpl(signed char v, @@ -333,7 +365,7 @@ IntegralConvertResult FormatConvertImpl(T v, FormatConversionSpecImpl conv, template <typename T> typename std::enable_if<std::is_enum<T>::value && !HasUserDefinedConvert<T>::value && - !strings_internal::HasAbslStringify<T>::value, + !HasAbslStringify<T>::value, IntegralConvertResult>::type FormatConvertImpl(T v, FormatConversionSpecImpl conv, FormatSinkImpl* sink); @@ -440,6 +472,7 @@ class FormatArgImpl { // Anything with a user-defined Convert will get its own vtable. // For everything else: // - Decay char* and char arrays into `const char*` + // - Decay wchar_t* and wchar_t arrays into `const wchar_t*` // - Decay any other pointer to `const void*` // - Decay all enums to the integral promotion of their underlying type. // - Decay function pointers to void*. @@ -447,20 +480,23 @@ class FormatArgImpl { struct DecayType { static constexpr bool kHasUserDefined = str_format_internal::HasUserDefinedConvert<T>::value || - strings_internal::HasAbslStringify<T>::value; + HasAbslStringify<T>::value; using type = typename std::conditional< !kHasUserDefined && std::is_convertible<T, const char*>::value, const char*, - typename std::conditional<!kHasUserDefined && - std::is_convertible<T, VoidPtr>::value, - VoidPtr, const T&>::type>::type; + typename std::conditional< + !kHasUserDefined && std::is_convertible<T, const wchar_t*>::value, + const wchar_t*, + typename std::conditional< + !kHasUserDefined && std::is_convertible<T, VoidPtr>::value, + VoidPtr, + const T&>::type>::type>::type; }; template <typename T> - struct DecayType<T, - typename std::enable_if< - !str_format_internal::HasUserDefinedConvert<T>::value && - !strings_internal::HasAbslStringify<T>::value && - std::is_enum<T>::value>::type> { + struct DecayType< + T, typename std::enable_if< + !str_format_internal::HasUserDefinedConvert<T>::value && + !HasAbslStringify<T>::value && std::is_enum<T>::value>::type> { using type = decltype(+typename std::underlying_type<T>::type()); }; @@ -585,7 +621,7 @@ class FormatArgImpl { E template bool FormatArgImpl::Dispatch<T>(Data, FormatConversionSpecImpl, \ void*) -#define ABSL_INTERNAL_FORMAT_DISPATCH_OVERLOADS_EXPAND_(...) \ +#define ABSL_INTERNAL_FORMAT_DISPATCH_OVERLOADS_EXPAND_NO_WSTRING_VIEW_(...) \ ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(str_format_internal::VoidPtr, \ __VA_ARGS__); \ ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(bool, __VA_ARGS__); \ @@ -611,7 +647,19 @@ class FormatArgImpl { ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(long double, __VA_ARGS__); \ ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(const char*, __VA_ARGS__); \ ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(std::string, __VA_ARGS__); \ - ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(string_view, __VA_ARGS__) + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(string_view, __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(const wchar_t*, __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(std::wstring, __VA_ARGS__) + +#if defined(ABSL_HAVE_STD_STRING_VIEW) +#define ABSL_INTERNAL_FORMAT_DISPATCH_OVERLOADS_EXPAND_(...) \ + ABSL_INTERNAL_FORMAT_DISPATCH_OVERLOADS_EXPAND_NO_WSTRING_VIEW_( \ + __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(std::wstring_view, __VA_ARGS__) +#else +#define ABSL_INTERNAL_FORMAT_DISPATCH_OVERLOADS_EXPAND_(...) \ + ABSL_INTERNAL_FORMAT_DISPATCH_OVERLOADS_EXPAND_NO_WSTRING_VIEW_(__VA_ARGS__) +#endif ABSL_INTERNAL_FORMAT_DISPATCH_OVERLOADS_EXPAND_(extern); diff --git a/absl/strings/internal/str_format/arg_test.cc b/absl/strings/internal/str_format/arg_test.cc index 1261937c..f663d7c5 100644 --- a/absl/strings/internal/str_format/arg_test.cc +++ b/absl/strings/internal/str_format/arg_test.cc @@ -14,9 +14,10 @@ #include "absl/strings/internal/str_format/arg.h" -#include <ostream> +#include <limits> #include <string> #include "gtest/gtest.h" +#include "absl/base/config.h" #include "absl/strings/str_format.h" namespace absl { @@ -93,6 +94,21 @@ TEST_F(FormatArgImplTest, CharArraysDecayToCharPtr) { FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(kMyArray))); } +extern const wchar_t kMyWCharTArray[]; + +TEST_F(FormatArgImplTest, WCharTArraysDecayToWCharTPtr) { + const wchar_t* a = L""; + EXPECT_EQ(FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(a)), + FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(L""))); + EXPECT_EQ(FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(a)), + FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(L"A"))); + EXPECT_EQ(FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(a)), + FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(L"ABC"))); + EXPECT_EQ( + FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(a)), + FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(kMyWCharTArray))); +} + TEST_F(FormatArgImplTest, OtherPtrDecayToVoidPtr) { auto expected = FormatArgImplFriend::GetVTablePtrForTest( FormatArgImpl(static_cast<void *>(nullptr))); @@ -124,6 +140,22 @@ TEST_F(FormatArgImplTest, WorksWithCharArraysOfUnknownSize) { } const char kMyArray[] = "ABCDE"; +TEST_F(FormatArgImplTest, WorksWithWCharTArraysOfUnknownSize) { + std::string s; + FormatSinkImpl sink(&s); + FormatConversionSpecImpl conv; + FormatConversionSpecImplFriend::SetConversionChar( + FormatConversionCharInternal::s, &conv); + FormatConversionSpecImplFriend::SetFlags(Flags(), &conv); + FormatConversionSpecImplFriend::SetWidth(-1, &conv); + FormatConversionSpecImplFriend::SetPrecision(-1, &conv); + EXPECT_TRUE( + FormatArgImplFriend::Convert(FormatArgImpl(kMyWCharTArray), conv, &sink)); + sink.Flush(); + EXPECT_EQ("ABCDE", s); +} +const wchar_t kMyWCharTArray[] = L"ABCDE"; + } // namespace } // namespace str_format_internal ABSL_NAMESPACE_END diff --git a/absl/strings/internal/str_format/bind.cc b/absl/strings/internal/str_format/bind.cc index 77a42223..87e23b56 100644 --- a/absl/strings/internal/str_format/bind.cc +++ b/absl/strings/internal/str_format/bind.cc @@ -14,10 +14,24 @@ #include "absl/strings/internal/str_format/bind.h" +#include <algorithm> +#include <cassert> #include <cerrno> +#include <cstddef> +#include <cstdio> +#include <ios> #include <limits> +#include <ostream> #include <sstream> #include <string> +#include "absl/base/config.h" +#include "absl/base/optimization.h" +#include "absl/strings/internal/str_format/arg.h" +#include "absl/strings/internal/str_format/constexpr_parser.h" +#include "absl/strings/internal/str_format/extension.h" +#include "absl/strings/internal/str_format/output.h" +#include "absl/strings/string_view.h" +#include "absl/types/span.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -90,6 +104,8 @@ inline bool ArgContext::Bind(const UnboundConversion* unbound, } else { FormatConversionSpecImplFriend::SetFlags(unbound->flags, bound); } + + FormatConversionSpecImplFriend::SetLengthMod(unbound->length_mod, bound); } else { FormatConversionSpecImplFriend::SetFlags(unbound->flags, bound); FormatConversionSpecImplFriend::SetWidth(-1, bound); @@ -215,7 +231,7 @@ std::string& AppendPack(std::string* out, const UntypedFormatSpecImpl format, return *out; } -std::string FormatPack(const UntypedFormatSpecImpl format, +std::string FormatPack(UntypedFormatSpecImpl format, absl::Span<const FormatArgImpl> args) { std::string out; if (ABSL_PREDICT_FALSE(!FormatUntyped(&out, format, args))) { diff --git a/absl/strings/internal/str_format/bind.h b/absl/strings/internal/str_format/bind.h index 5e2a43d5..120bc355 100644 --- a/absl/strings/internal/str_format/bind.h +++ b/absl/strings/internal/str_format/bind.h @@ -15,16 +15,19 @@ #ifndef ABSL_STRINGS_INTERNAL_STR_FORMAT_BIND_H_ #define ABSL_STRINGS_INTERNAL_STR_FORMAT_BIND_H_ -#include <array> +#include <cassert> #include <cstdio> -#include <sstream> +#include <ostream> #include <string> -#include "absl/base/port.h" +#include "absl/base/config.h" #include "absl/container/inlined_vector.h" #include "absl/strings/internal/str_format/arg.h" #include "absl/strings/internal/str_format/checker.h" +#include "absl/strings/internal/str_format/constexpr_parser.h" +#include "absl/strings/internal/str_format/extension.h" #include "absl/strings/internal/str_format/parser.h" +#include "absl/strings/string_view.h" #include "absl/types/span.h" #include "absl/utility/utility.h" @@ -203,7 +206,7 @@ bool FormatUntyped(FormatRawSinkImpl raw_sink, UntypedFormatSpecImpl format, std::string& AppendPack(std::string* out, UntypedFormatSpecImpl format, absl::Span<const FormatArgImpl> args); -std::string FormatPack(const UntypedFormatSpecImpl format, +std::string FormatPack(UntypedFormatSpecImpl format, absl::Span<const FormatArgImpl> args); int FprintF(std::FILE* output, UntypedFormatSpecImpl format, diff --git a/absl/strings/internal/str_format/constexpr_parser.h b/absl/strings/internal/str_format/constexpr_parser.h index b70a16e4..8f593870 100644 --- a/absl/strings/internal/str_format/constexpr_parser.h +++ b/absl/strings/internal/str_format/constexpr_parser.h @@ -17,17 +17,18 @@ #include <cassert> #include <cstdint> +#include <cstdio> #include <limits> +#include "absl/base/config.h" #include "absl/base/const_init.h" +#include "absl/base/optimization.h" #include "absl/strings/internal/str_format/extension.h" namespace absl { ABSL_NAMESPACE_BEGIN namespace str_format_internal { -enum class LengthMod : std::uint8_t { h, hh, l, ll, L, j, z, t, q, none }; - // The analyzed properties of a single specified conversion. struct UnboundConversion { // This is a user defined default constructor on purpose to skip the @@ -306,7 +307,6 @@ constexpr const char* ConsumeConversion(const char* pos, const char* const end, if (ABSL_PREDICT_FALSE(!tag.is_length())) return nullptr; // It is a length modifier. - using str_format_internal::LengthMod; LengthMod length_mod = tag.as_length(); ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR(); if (c == 'h' && length_mod == LengthMod::h) { @@ -322,6 +322,11 @@ constexpr const char* ConsumeConversion(const char* pos, const char* const end, if (ABSL_PREDICT_FALSE(c == 'v')) return nullptr; if (ABSL_PREDICT_FALSE(!tag.is_conv())) return nullptr; + + // `wchar_t` args are marked non-basic so `Bind()` will copy the length mod. + if (conv->length_mod == LengthMod::l && c == 'c') { + conv->flags = conv->flags | Flags::kNonBasic; + } } #undef ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR diff --git a/absl/strings/internal/str_format/convert_test.cc b/absl/strings/internal/str_format/convert_test.cc index 16ff9879..7f222778 100644 --- a/absl/strings/internal/str_format/convert_test.cc +++ b/absl/strings/internal/str_format/convert_test.cc @@ -12,24 +12,43 @@ // See the License for the specific language governing permissions and // limitations under the License. -#include <errno.h> +#include <assert.h> +#include <locale.h> #include <stdarg.h> #include <stdio.h> -#include <cctype> +#include <algorithm> +#include <climits> #include <cmath> +#include <cstdlib> +#include <cstring> +#include <cwctype> #include <limits> +#include <set> +#include <sstream> #include <string> #include <thread> // NOLINT +#include <type_traits> +#include <vector> #include "gmock/gmock.h" #include "gtest/gtest.h" #include "absl/base/attributes.h" #include "absl/base/internal/raw_logging.h" #include "absl/log/log.h" +#include "absl/numeric/int128.h" +#include "absl/strings/ascii.h" +#include "absl/strings/internal/str_format/arg.h" #include "absl/strings/internal/str_format/bind.h" #include "absl/strings/match.h" +#include "absl/strings/str_format.h" +#include "absl/strings/string_view.h" #include "absl/types/optional.h" +#include "absl/types/span.h" + +#if defined(ABSL_HAVE_STD_STRING_VIEW) +#include <string_view> +#endif namespace absl { ABSL_NAMESPACE_BEGIN @@ -48,36 +67,103 @@ size_t ArraySize(T (&)[N]) { return N; } -std::string LengthModFor(float) { return ""; } -std::string LengthModFor(double) { return ""; } -std::string LengthModFor(long double) { return "L"; } -std::string LengthModFor(char) { return "hh"; } -std::string LengthModFor(signed char) { return "hh"; } -std::string LengthModFor(unsigned char) { return "hh"; } -std::string LengthModFor(short) { return "h"; } // NOLINT -std::string LengthModFor(unsigned short) { return "h"; } // NOLINT -std::string LengthModFor(int) { return ""; } -std::string LengthModFor(unsigned) { return ""; } -std::string LengthModFor(long) { return "l"; } // NOLINT -std::string LengthModFor(unsigned long) { return "l"; } // NOLINT -std::string LengthModFor(long long) { return "ll"; } // NOLINT -std::string LengthModFor(unsigned long long) { return "ll"; } // NOLINT +template <typename T> +struct AlwaysFalse : std::false_type {}; + +template <typename T> +std::string LengthModFor() { + static_assert(AlwaysFalse<T>::value, "Unsupported type"); + return ""; +} +template <> +std::string LengthModFor<char>() { + return "hh"; +} +template <> +std::string LengthModFor<signed char>() { + return "hh"; +} +template <> +std::string LengthModFor<unsigned char>() { + return "hh"; +} +template <> +std::string LengthModFor<short>() { // NOLINT + return "h"; +} +template <> +std::string LengthModFor<unsigned short>() { // NOLINT + return "h"; +} +template <> +std::string LengthModFor<int>() { + return ""; +} +template <> +std::string LengthModFor<unsigned>() { + return ""; +} +template <> +std::string LengthModFor<long>() { // NOLINT + return "l"; +} +template <> +std::string LengthModFor<unsigned long>() { // NOLINT + return "l"; +} +template <> +std::string LengthModFor<long long>() { // NOLINT + return "ll"; +} +template <> +std::string LengthModFor<unsigned long long>() { // NOLINT + return "ll"; +} + +// An integral type of the same rank and signedness as `wchar_t`, that isn't +// `wchar_t`. +using IntegralTypeForWCharT = + std::conditional_t<std::is_signed<wchar_t>::value, + // Some STLs are broken and return `wchar_t` from + // `std::make_[un]signed_t<wchar_t>` when the signedness + // matches. Work around by round-tripping through the + // opposite signedness. + std::make_signed_t<std::make_unsigned_t<wchar_t>>, + std::make_unsigned_t<std::make_signed_t<wchar_t>>>; + +// Given an integral type `T`, returns a type of the same rank and signedness +// that is guaranteed to not be `wchar_t`. +template <typename T> +using MatchingIntegralType = std::conditional_t<std::is_same<T, wchar_t>::value, + IntegralTypeForWCharT, T>; std::string EscCharImpl(int v) { - if (std::isprint(static_cast<unsigned char>(v))) { - return std::string(1, static_cast<char>(v)); - } char buf[64]; - int n = snprintf(buf, sizeof(buf), "\\%#.2x", - static_cast<unsigned>(v & 0xff)); - assert(n > 0 && n < sizeof(buf)); - return std::string(buf, n); + int n = absl::ascii_isprint(static_cast<unsigned char>(v)) + ? snprintf(buf, sizeof(buf), "'%c'", v) + : snprintf(buf, sizeof(buf), "'\\x%.*x'", CHAR_BIT / 4, + static_cast<unsigned>( + static_cast<std::make_unsigned_t<char>>(v))); + assert(n > 0 && static_cast<size_t>(n) < sizeof(buf)); + return std::string(buf, static_cast<size_t>(n)); } std::string Esc(char v) { return EscCharImpl(v); } std::string Esc(signed char v) { return EscCharImpl(v); } std::string Esc(unsigned char v) { return EscCharImpl(v); } +std::string Esc(wchar_t v) { + char buf[64]; + int n = std::iswprint(static_cast<wint_t>(v)) + ? snprintf(buf, sizeof(buf), "L'%lc'", static_cast<wint_t>(v)) + : snprintf(buf, sizeof(buf), "L'\\x%.*llx'", + static_cast<int>(sizeof(wchar_t) * CHAR_BIT / 4), + static_cast<unsigned long long>( + static_cast<std::make_unsigned_t<wchar_t>>(v))); + assert(n > 0 && static_cast<size_t>(n) < sizeof(buf)); + return std::string(buf, static_cast<size_t>(n)); +} + template <typename T> std::string Esc(const T &v) { std::ostringstream oss; @@ -100,7 +186,7 @@ void StrAppendV(std::string *dst, const char *format, va_list ap) { if (result < kSpaceLength) { if (result >= 0) { // Normal case -- everything fit. - dst->append(space, result); + dst->append(space, static_cast<size_t>(result)); return; } if (result < 0) { @@ -111,7 +197,7 @@ void StrAppendV(std::string *dst, const char *format, va_list ap) { // Increase the buffer size to the size requested by vsnprintf, // plus one for the closing \0. - int length = result + 1; + size_t length = static_cast<size_t>(result) + 1; char *buf = new char[length]; // Restore the va_list before we use it again @@ -119,9 +205,9 @@ void StrAppendV(std::string *dst, const char *format, va_list ap) { result = vsnprintf(buf, length, format, backup_ap); va_end(backup_ap); - if (result >= 0 && result < length) { + if (result >= 0 && static_cast<size_t>(result) < length) { // It fit - dst->append(buf, result); + dst->append(buf, static_cast<size_t>(result)); } delete[] buf; } @@ -230,11 +316,15 @@ void TestStringConvert(const T& str) { TEST_F(FormatConvertTest, BasicString) { TestStringConvert("hello"); // As char array. + TestStringConvert(L"hello"); TestStringConvert(static_cast<const char*>("hello")); + TestStringConvert(static_cast<const wchar_t*>(L"hello")); TestStringConvert(std::string("hello")); + TestStringConvert(std::wstring(L"hello")); TestStringConvert(string_view("hello")); #if defined(ABSL_HAVE_STD_STRING_VIEW) TestStringConvert(std::string_view("hello")); + TestStringConvert(std::wstring_view(L"hello")); #endif // ABSL_HAVE_STD_STRING_VIEW } @@ -242,6 +332,10 @@ TEST_F(FormatConvertTest, NullString) { const char* p = nullptr; UntypedFormatSpecImpl format("%s"); EXPECT_EQ("", FormatPack(format, {FormatArgImpl(p)})); + + const wchar_t* wp = nullptr; + UntypedFormatSpecImpl wformat("%ls"); + EXPECT_EQ("", FormatPack(wformat, {FormatArgImpl(wp)})); } TEST_F(FormatConvertTest, StringPrecision) { @@ -251,10 +345,19 @@ TEST_F(FormatConvertTest, StringPrecision) { UntypedFormatSpecImpl format("%.1s"); EXPECT_EQ("a", FormatPack(format, {FormatArgImpl(p)})); + wchar_t wc = L'a'; + const wchar_t* wp = &wc; + UntypedFormatSpecImpl wformat("%.1ls"); + EXPECT_EQ("a", FormatPack(wformat, {FormatArgImpl(wp)})); + // We cap at the NUL-terminator. p = "ABC"; UntypedFormatSpecImpl format2("%.10s"); EXPECT_EQ("ABC", FormatPack(format2, {FormatArgImpl(p)})); + + wp = L"ABC"; + UntypedFormatSpecImpl wformat2("%.10ls"); + EXPECT_EQ("ABC", FormatPack(wformat2, {FormatArgImpl(wp)})); } // Pointer formatting is implementation defined. This checks that the argument @@ -277,16 +380,25 @@ TEST_F(FormatConvertTest, Pointer) { char *mcp = &c; const char *cp = "hi"; const char *cnil = nullptr; + wchar_t wc = L'h'; + wchar_t *mwcp = &wc; + const wchar_t *wcp = L"hi"; + const wchar_t *wcnil = nullptr; const int *inil = nullptr; using VoidF = void (*)(); VoidF fp = [] {}, fnil = nullptr; volatile char vc; volatile char *vcp = &vc; volatile char *vcnil = nullptr; + volatile wchar_t vwc; + volatile wchar_t *vwcp = &vwc; + volatile wchar_t *vwcnil = nullptr; const FormatArgImpl args_array[] = { - FormatArgImpl(xp), FormatArgImpl(cp), FormatArgImpl(inil), - FormatArgImpl(cnil), FormatArgImpl(mcp), FormatArgImpl(fp), - FormatArgImpl(fnil), FormatArgImpl(vcp), FormatArgImpl(vcnil), + FormatArgImpl(xp), FormatArgImpl(cp), FormatArgImpl(wcp), + FormatArgImpl(inil), FormatArgImpl(cnil), FormatArgImpl(wcnil), + FormatArgImpl(mcp), FormatArgImpl(mwcp), FormatArgImpl(fp), + FormatArgImpl(fnil), FormatArgImpl(vcp), FormatArgImpl(vwcp), + FormatArgImpl(vcnil), FormatArgImpl(vwcnil), }; auto args = absl::MakeConstSpan(args_array); @@ -312,30 +424,49 @@ TEST_F(FormatConvertTest, Pointer) { EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%-30.20p"), args), MatchesPointerString(&x)); + // const int* + EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%1$p"), args), + MatchesPointerString(xp)); // const char* EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%2$p"), args), MatchesPointerString(cp)); - // null const int* + // const wchar_t* EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%3$p"), args), + MatchesPointerString(wcp)); + // null const int* + EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%4$p"), args), MatchesPointerString(nullptr)); // null const char* - EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%4$p"), args), + EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%5$p"), args), + MatchesPointerString(nullptr)); + // null const wchar_t* + EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%6$p"), args), MatchesPointerString(nullptr)); // nonconst char* - EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%5$p"), args), + EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%7$p"), args), MatchesPointerString(mcp)); - - // function pointers - EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%6$p"), args), - MatchesPointerString(reinterpret_cast<const void*>(fp))); + // nonconst wchar_t* + EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%8$p"), args), + MatchesPointerString(mwcp)); + // function pointer + EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%9$p"), args), + MatchesPointerString(reinterpret_cast<const void *>(fp))); + // null function pointer + EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%10$p"), args), + MatchesPointerString(nullptr)); + // volatile char* EXPECT_THAT( - FormatPack(UntypedFormatSpecImpl("%8$p"), args), + FormatPack(UntypedFormatSpecImpl("%11$p"), args), MatchesPointerString(reinterpret_cast<volatile const void *>(vcp))); - - // null function pointers - EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%7$p"), args), + // volatile wchar_t* + EXPECT_THAT( + FormatPack(UntypedFormatSpecImpl("%12$p"), args), + MatchesPointerString(reinterpret_cast<volatile const void *>(vwcp))); + // null volatile char* + EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%13$p"), args), MatchesPointerString(nullptr)); - EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%9$p"), args), + // null volatile wchar_t* + EXPECT_THAT(FormatPack(UntypedFormatSpecImpl("%14$p"), args), MatchesPointerString(nullptr)); } @@ -435,12 +566,15 @@ TYPED_TEST_P(TypedFormatConvertTest, AllIntsWithFlags) { // as printf can't do that conversion properly. For those // cases, we do expect agreement with printf with a "%u" // and the unsigned equivalent of 'val'. - UnsignedT uval = val; - old_fmt += LengthModFor(uval); + UnsignedT uval = + static_cast<std::remove_volatile_t<UnsignedT>>(val); + old_fmt += LengthModFor< + MatchingIntegralType<std::remove_cv_t<decltype(uval)>>>(); old_fmt += "u"; old_result = StrPrint(old_fmt.c_str(), uval); } else { - old_fmt += LengthModFor(val); + old_fmt += LengthModFor< + MatchingIntegralType<std::remove_cv_t<decltype(val)>>>(); old_fmt += conv_char; old_result = StrPrint(old_fmt.c_str(), val); } @@ -458,6 +592,47 @@ TYPED_TEST_P(TypedFormatConvertTest, AllIntsWithFlags) { } } +template <typename T> +absl::optional<std::string> StrPrintChar(T c) { + return StrPrint("%c", static_cast<int>(c)); +} +template <> +absl::optional<std::string> StrPrintChar(wchar_t c) { + // musl libc has a bug where ("%lc", 0) writes no characters, and Android + // doesn't support forcing UTF-8 via setlocale(). Hardcode the expected + // answers for ASCII inputs to maximize test coverage on these platforms. + if (static_cast<std::make_unsigned_t<wchar_t>>(c) < 0x80) { + return std::string(1, static_cast<char>(c)); + } + + // Force a UTF-8 locale to match the expected `StrFormat()` behavior. + // It's important to copy the string returned by `old_locale` here, because + // its contents are not guaranteed to be valid after the next `setlocale()` + // call. + std::string old_locale = setlocale(LC_CTYPE, nullptr); + if (!setlocale(LC_CTYPE, "en_US.UTF-8")) { + return absl::nullopt; + } + const std::string output = StrPrint("%lc", static_cast<wint_t>(c)); + setlocale(LC_CTYPE, old_locale.c_str()); + return output; +} + +template <typename T> +typename std::remove_volatile<T>::type GetMaxForConversion() { + return static_cast<typename std::remove_volatile<T>::type>( + std::numeric_limits<int>::max()); +} + +template <> +wchar_t GetMaxForConversion<wchar_t>() { + // Don't return values that aren't legal Unicode. For wchar_t conversions in a + // UTF-8 locale, conversion behavior for such values is unspecified, and we + // don't care about matching it. + return (sizeof(wchar_t) * CHAR_BIT <= 16) ? wchar_t{0xffff} + : static_cast<wchar_t>(0x10ffff); +} + TYPED_TEST_P(TypedFormatConvertTest, Char) { // Pass a bunch of values of type TypeParam to both FormatPack and libc's // vsnprintf("%c", ...) (wrapped in StrPrint) to make sure we get the same @@ -474,28 +649,50 @@ TYPED_TEST_P(TypedFormatConvertTest, Char) { // std::numeric_limits::max(), too, but vsnprintf("%c", ...) can't handle // anything larger than an int. Add in the most extreme values we can without // exceeding that range. + // Special case: Formatting a wchar_t should behave like vsnprintf("%lc"). + // Technically vsnprintf can accept a wint_t in this case, but since we must + // pass a wchar_t to FormatPack, the largest type we can use here is wchar_t. + using ArgType = + std::conditional_t<std::is_same<T, wchar_t>::value, wchar_t, int>; static const T kMin = - static_cast<remove_volatile_t>(std::numeric_limits<int>::min()); - static const T kMax = - static_cast<remove_volatile_t>(std::numeric_limits<int>::max()); - vals.insert(vals.end(), {kMin + 1, kMin, kMax - 1, kMax}); + static_cast<remove_volatile_t>(std::numeric_limits<ArgType>::min()); + static const T kMax = GetMaxForConversion<T>(); + vals.insert(vals.end(), {static_cast<remove_volatile_t>(kMin + 1), kMin, + static_cast<remove_volatile_t>(kMax - 1), kMax}); + static const auto kMaxWCharT = + static_cast<remove_volatile_t>(GetMaxForConversion<wchar_t>()); for (const T c : vals) { + SCOPED_TRACE(Esc(c)); const FormatArgImpl args[] = {FormatArgImpl(c)}; UntypedFormatSpecImpl format("%c"); - EXPECT_EQ(StrPrint("%c", static_cast<int>(c)), - FormatPack(format, absl::MakeSpan(args))); + absl::optional<std::string> result = StrPrintChar(c); + if (result.has_value()) { + EXPECT_EQ(result.value(), FormatPack(format, absl::MakeSpan(args))); + } + + // Also test that if the format specifier is "%lc", the argument is treated + // as if it's a `wchar_t`. + const T wc = + std::max(remove_volatile_t{0}, + std::min(static_cast<remove_volatile_t>(c), kMaxWCharT)); + SCOPED_TRACE(Esc(wc)); + const FormatArgImpl wide_args[] = {FormatArgImpl(wc)}; + UntypedFormatSpecImpl wide_format("%lc"); + result = StrPrintChar(static_cast<wchar_t>(wc)); + if (result.has_value()) { + EXPECT_EQ(result.value(), + FormatPack(wide_format, absl::MakeSpan(wide_args))); + } } } REGISTER_TYPED_TEST_SUITE_P(TypedFormatConvertTest, AllIntsWithFlags, Char); -typedef ::testing::Types< - int, unsigned, volatile int, - short, unsigned short, - long, unsigned long, - long long, unsigned long long, - signed char, unsigned char, char> +typedef ::testing::Types<int, unsigned, volatile int, short, // NOLINT + unsigned short, long, unsigned long, // NOLINT + long long, unsigned long long, // NOLINT + signed char, unsigned char, char, wchar_t> AllIntTypes; INSTANTIATE_TYPED_TEST_SUITE_P(TypedFormatConvertTestWithAllIntTypes, TypedFormatConvertTest, AllIntTypes); @@ -510,6 +707,22 @@ TEST_F(FormatConvertTest, VectorBool) { FormatArgImpl(cv[0]), FormatArgImpl(cv[1])}))); } +TEST_F(FormatConvertTest, UnicodeWideString) { + // StrFormat() should be able to convert wide strings containing Unicode + // characters (to UTF-8). + const FormatArgImpl args[] = {FormatArgImpl(L"\u47e3 \U00011112")}; + // `u8""` forces UTF-8 encoding; MSVC will default to e.g. CP1252 (and warn) + // without it. However, the resulting character type differs between pre-C++20 + // (`char`) and C++20 (`char8_t`). So deduce the right character type for all + // C++ versions, init it with UTF-8, then `memcpy()` to get the result as a + // `char*`. + using ConstChar8T = std::remove_reference_t<decltype(*u8"a")>; + ConstChar8T kOutputUtf8[] = u8"\u47e3 \U00011112"; + char output[sizeof kOutputUtf8]; + std::memcpy(output, kOutputUtf8, sizeof kOutputUtf8); + EXPECT_EQ(output, + FormatPack(UntypedFormatSpecImpl("%ls"), absl::MakeSpan(args))); +} TEST_F(FormatConvertTest, Int128) { absl::int128 positive = static_cast<absl::int128>(0x1234567890abcdef) * 1979; @@ -684,7 +897,11 @@ TEST_F(FormatConvertTest, Float) { } // Remove duplicates to speed up the logic below. - std::sort(floats.begin(), floats.end()); + std::sort(floats.begin(), floats.end(), [](const float a, const float b) { + if (std::isnan(a)) return false; + if (std::isnan(b)) return true; + return a < b; + }); floats.erase(std::unique(floats.begin(), floats.end()), floats.end()); TestWithMultipleFormatsHelper(floats, {}); @@ -758,7 +975,11 @@ TEST_F(FormatConvertTest, Double) { } // Remove duplicates to speed up the logic below. - std::sort(doubles.begin(), doubles.end()); + std::sort(doubles.begin(), doubles.end(), [](const double a, const double b) { + if (std::isnan(a)) return false; + if (std::isnan(b)) return true; + return a < b; + }); doubles.erase(std::unique(doubles.begin(), doubles.end()), doubles.end()); TestWithMultipleFormatsHelper(doubles, skip_verify); @@ -1059,7 +1280,7 @@ TEST_F(FormatConvertTest, LongDoubleRoundA) { // We don't actually store the results. This is just to exercise the rest of the // machinery. struct NullSink { - friend void AbslFormatFlush(NullSink *sink, string_view str) {} + friend void AbslFormatFlush(NullSink *, string_view) {} }; template <typename... T> @@ -1236,9 +1457,16 @@ TEST_F(FormatConvertTest, ExpectedFailures) { // Sanity check to make sure that we are testing what we think we're testing on // e.g. the x86_64+glibc platform. TEST_F(FormatConvertTest, GlibcHasCorrectTraits) { -#if !defined(__GLIBC__) || !defined(__x86_64__) - return; +#if defined(__GLIBC__) && defined(__x86_64__) + constexpr bool kIsSupportedGlibc = true; +#else + constexpr bool kIsSupportedGlibc = false; #endif + + if (!kIsSupportedGlibc) { + GTEST_SKIP() << "Test does not support this platform"; + } + const NativePrintfTraits &native_traits = VerifyNativeImplementation(); // If one of the following tests break then it is either because the above PP // macro guards failed to exclude a new platform (likely) or because something diff --git a/absl/strings/internal/str_format/extension.h b/absl/strings/internal/str_format/extension.h index 8de42d2c..173284c6 100644 --- a/absl/strings/internal/str_format/extension.h +++ b/absl/strings/internal/str_format/extension.h @@ -16,16 +16,14 @@ #ifndef ABSL_STRINGS_INTERNAL_STR_FORMAT_EXTENSION_H_ #define ABSL_STRINGS_INTERNAL_STR_FORMAT_EXTENSION_H_ -#include <limits.h> #include <cstddef> #include <cstdint> #include <cstring> #include <ostream> +#include <string> #include "absl/base/config.h" -#include "absl/base/port.h" -#include "absl/meta/type_traits.h" #include "absl/strings/internal/str_format/output.h" #include "absl/strings/string_view.h" @@ -34,6 +32,7 @@ ABSL_NAMESPACE_BEGIN enum class FormatConversionChar : uint8_t; enum class FormatConversionCharSet : uint64_t; +enum class LengthMod : std::uint8_t { h, hh, l, ll, L, j, z, t, q, none }; namespace str_format_internal { @@ -139,7 +138,8 @@ enum class Flags : uint8_t { kAlt = 1 << 3, kZero = 1 << 4, // This is not a real flag. It just exists to turn off kBasic when no other - // flags are set. This is for when width/precision are specified. + // flags are set. This is for when width/precision are specified, or a length + // modifier affects the behavior ("%lc"). kNonBasic = 1 << 5, }; @@ -285,6 +285,8 @@ class FormatConversionSpecImpl { bool has_alt_flag() const { return FlagsContains(flags_, Flags::kAlt); } bool has_zero_flag() const { return FlagsContains(flags_, Flags::kZero); } + LengthMod length_mod() const { return length_mod_; } + FormatConversionChar conversion_char() const { // Keep this field first in the struct . It generates better code when // accessing it when ConversionSpec is passed by value in registers. @@ -310,6 +312,7 @@ class FormatConversionSpecImpl { friend struct str_format_internal::FormatConversionSpecImplFriend; FormatConversionChar conv_ = FormatConversionCharInternal::kNone; Flags flags_; + LengthMod length_mod_ = LengthMod::none; int width_; int precision_; }; @@ -318,6 +321,9 @@ struct FormatConversionSpecImplFriend final { static void SetFlags(Flags f, FormatConversionSpecImpl* conv) { conv->flags_ = f; } + static void SetLengthMod(LengthMod l, FormatConversionSpecImpl* conv) { + conv->length_mod_ = l; + } static void SetConversionChar(FormatConversionChar c, FormatConversionSpecImpl* conv) { conv->conv_ = c; diff --git a/absl/strings/internal/str_format/parser.h b/absl/strings/internal/str_format/parser.h index 35b6d49c..b1d6d5fd 100644 --- a/absl/strings/internal/str_format/parser.h +++ b/absl/strings/internal/str_format/parser.h @@ -15,22 +15,23 @@ #ifndef ABSL_STRINGS_INTERNAL_STR_FORMAT_PARSER_H_ #define ABSL_STRINGS_INTERNAL_STR_FORMAT_PARSER_H_ -#include <limits.h> #include <stddef.h> #include <stdlib.h> #include <cassert> -#include <cstdint> +#include <cstring> #include <initializer_list> -#include <iosfwd> -#include <iterator> #include <memory> #include <string> +#include <utility> #include <vector> +#include "absl/base/config.h" +#include "absl/base/optimization.h" #include "absl/strings/internal/str_format/checker.h" #include "absl/strings/internal/str_format/constexpr_parser.h" #include "absl/strings/internal/str_format/extension.h" +#include "absl/strings/string_view.h" namespace absl { ABSL_NAMESPACE_BEGIN diff --git a/absl/strings/internal/str_format/parser_test.cc b/absl/strings/internal/str_format/parser_test.cc index 021f6a87..e2225c60 100644 --- a/absl/strings/internal/str_format/parser_test.cc +++ b/absl/strings/internal/str_format/parser_test.cc @@ -15,10 +15,18 @@ #include "absl/strings/internal/str_format/parser.h" #include <string.h> +#include <algorithm> +#include <initializer_list> +#include <string> +#include <utility> #include "gmock/gmock.h" #include "gtest/gtest.h" +#include "absl/base/config.h" #include "absl/base/macros.h" +#include "absl/strings/internal/str_format/constexpr_parser.h" +#include "absl/strings/internal/str_format/extension.h" +#include "absl/strings/string_view.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -303,7 +311,7 @@ TEST_F(ConsumeUnboundConversionTest, BasicFlag) { } // Flag is off - for (const char* fmt : {"3d", ".llx", "-G", "1$#X"}) { + for (const char* fmt : {"3d", ".llx", "-G", "1$#X", "lc"}) { SCOPED_TRACE(fmt); EXPECT_TRUE(Run(fmt)); EXPECT_NE(o.flags, Flags::kBasic); |