Export of internal Abseil changes

--
3b43586da865534cf86401d2cae09c65c60b8474 by Abseil Team <absl-team@google.com>:

Introduce CordRepRingReader class

PiperOrigin-RevId: 353070937

--
0bff6e4bcca34fdd1e6610da5fb3c37fd49b2940 by Abseil Team <absl-team@google.com>:

Fix docstring typo "Exmaple" -> "Example"

PiperOrigin-RevId: 352927688

--
1ef4e0a1100cfa7bc9d9e8f155acf0e469348b56 by Abseil Team <absl-team@google.com>:

Refactor tree initialization of ChunkIterator and CordReader

PiperOrigin-RevId: 352916786

--
919c3eb175b87294184a405785eef4fab520d47e by Abseil Team <absl-team@google.com>:

Disable `preserve_most` when compiling with sanitizers.

PiperOrigin-RevId: 352890630
GitOrigin-RevId: 3b43586da865534cf86401d2cae09c65c60b8474
Change-Id: I8a733494b353af69a46862a4019a7f9b40148f49

6 files changed, 342 insertions, 2 deletions

diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel
index d7c322f..794cf43 100644
--- a/absl/strings/BUILD.bazel
+++ b/absl/strings/BUILD.bazel
@@ -275,6 +275,7 @@ cc_library(
         "internal/cord_internal.h",
         "internal/cord_rep_flat.h",
         "internal/cord_rep_ring.h",
+        "internal/cord_rep_ring_reader.h",
     ],
     copts = ABSL_DEFAULT_COPTS,
     visibility = [
@@ -371,6 +372,21 @@ cc_test(
 )
 
 cc_test(
+    name = "cord_ring_reader_test",
+    size = "medium",
+    srcs = ["cord_ring_reader_test.cc"],
+    copts = ABSL_TEST_COPTS,
+    visibility = ["//visibility:private"],
+    deps = [
+        ":cord_internal",
+        ":strings",
+        "//absl/base:core_headers",
+        "//absl/debugging:leak_check",
+        "@com_google_googletest//:gtest_main",
+    ],
+)
+
+cc_test(
     name = "substitute_test",
     size = "small",
     srcs = ["substitute_test.cc"],
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt
index a6204bf..12f322a 100644
--- a/absl/strings/CMakeLists.txt
+++ b/absl/strings/CMakeLists.txt
@@ -560,6 +560,7 @@ absl_cc_library(
     "internal/cord_internal.h"
     "internal/cord_rep_ring.h"
     "internal/cord_rep_ring.cc"
+    "internal/cord_rep_ring_reader.h"
     "internal/cord_rep_flat.h"
   COPTS
     ${ABSL_DEFAULT_COPTS}
@@ -630,3 +631,18 @@ absl_cc_test(
     absl::raw_logging_internal
     gmock_main
 )
+
+absl_cc_test(
+  NAME
+    cord_ring_reader_test
+  SRCS
+    "cord_ring_reader_test.cc"
+  COPTS
+    ${ABSL_TEST_COPTS}
+  DEPS
+    absl::cord
+    absl::strings
+    absl::base
+    absl::core_headers
+    gmock_main
+)
diff --git a/absl/strings/cord.h b/absl/strings/cord.h
index 9d8764a..abef98f 100644
--- a/absl/strings/cord.h
+++ b/absl/strings/cord.h
@@ -367,9 +367,15 @@ class Cord {
     // the inlined vector size (47 exists for backward compatibility).
     using Stack = absl::InlinedVector<absl::cord_internal::CordRep*, 47>;
 
+    // Constructs a `begin()` iterator from `tree`. `tree` must not be null.
+    explicit ChunkIterator(cord_internal::CordRep* tree);
+
     // Constructs a `begin()` iterator from `cord`.
     explicit ChunkIterator(const Cord* cord);
 
+    // Initializes this instance from a tree. Invoked by constructors.
+    void InitTree(cord_internal::CordRep* tree);
+
     // Removes `n` bytes from `current_chunk_`. Expects `n` to be smaller than
     // `current_chunk_.size()`.
     void RemoveChunkPrefix(size_t n);
@@ -1100,11 +1106,20 @@ inline bool Cord::StartsWith(absl::string_view rhs) const {
   return EqualsImpl(rhs, rhs_size);
 }
 
+inline void Cord::ChunkIterator::InitTree(cord_internal::CordRep* tree) {
+  stack_of_right_children_.push_back(tree);
+  operator++();
+}
+
+inline Cord::ChunkIterator::ChunkIterator(cord_internal::CordRep* tree)
+    : bytes_remaining_(tree->length) {
+  InitTree(tree);
+}
+
 inline Cord::ChunkIterator::ChunkIterator(const Cord* cord)
     : bytes_remaining_(cord->size()) {
   if (cord->contents_.is_tree()) {
-    stack_of_right_children_.push_back(cord->contents_.as_tree());
-    operator++();
+    InitTree(cord->contents_.as_tree());
   } else {
     current_chunk_ =
         absl::string_view(cord->contents_.data(), bytes_remaining_);
@@ -1155,6 +1170,7 @@ inline void Cord::ChunkIterator::RemoveChunkPrefix(size_t n) {
 }
 
 inline void Cord::ChunkIterator::AdvanceBytes(size_t n) {
+  assert(bytes_remaining_ >= n);
   if (ABSL_PREDICT_TRUE(n < current_chunk_.size())) {
     RemoveChunkPrefix(n);
   } else if (n != 0) {
diff --git a/absl/strings/cord_ring_reader_test.cc b/absl/strings/cord_ring_reader_test.cc
new file mode 100644
index 0000000..585616f
--- /dev/null
+++ b/absl/strings/cord_ring_reader_test.cc
@@ -0,0 +1,173 @@
+// 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 <cstdlib>
+#include <ctime>
+#include <memory>
+#include <random>
+#include <sstream>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/debugging/leak_check.h"
+#include "absl/strings/internal/cord_internal.h"
+#include "absl/strings/internal/cord_rep_ring.h"
+#include "absl/strings/internal/cord_rep_ring_reader.h"
+#include "absl/strings/string_view.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace cord_internal {
+namespace {
+
+using testing::Eq;
+
+// Creates a flat for testing
+CordRep* MakeFlat(absl::string_view s) {
+  CordRepFlat* flat = CordRepFlat::New(s.length());
+  memcpy(flat->Data(), s.data(), s.length());
+  flat->length = s.length();
+  return flat;
+}
+
+CordRepRing* FromFlats(Span<absl::string_view const> flats) {
+  CordRepRing* ring = CordRepRing::Create(MakeFlat(flats[0]), flats.size() - 1);
+  for (int i = 1; i < flats.size(); ++i) {
+    ring = CordRepRing::Append(ring, MakeFlat(flats[i]));
+  }
+  return ring;
+}
+
+std::array<absl::string_view, 12> TestFlats() {
+  return {"abcdefghij", "klmnopqrst", "uvwxyz",     "ABCDEFGHIJ",
+          "KLMNOPQRST", "UVWXYZ",     "1234567890", "~!@#$%^&*()_",
+          "+-=",        "[]\\{}|;':", ",/<>?",      "."};
+}
+
+TEST(CordRingReaderTest, DefaultInstance) {
+  CordRepRingReader reader;
+  EXPECT_FALSE(static_cast<bool>(reader));
+  EXPECT_THAT(reader.ring(), Eq(nullptr));
+#ifndef NDEBUG
+  EXPECT_DEATH_IF_SUPPORTED(reader.length(), ".*");
+  EXPECT_DEATH_IF_SUPPORTED(reader.consumed(), ".*");
+  EXPECT_DEATH_IF_SUPPORTED(reader.remaining(), ".*");
+  EXPECT_DEATH_IF_SUPPORTED(reader.Next(), ".*");
+  EXPECT_DEATH_IF_SUPPORTED(reader.Seek(0), ".*");
+#endif
+}
+
+TEST(CordRingReaderTest, Reset) {
+  CordRepRingReader reader;
+  auto flats = TestFlats();
+  CordRepRing* ring = FromFlats(flats);
+
+  absl::string_view first = reader.Reset(ring);
+  EXPECT_THAT(first, Eq(flats[0]));
+  EXPECT_TRUE(static_cast<bool>(reader));
+  EXPECT_THAT(reader.ring(), Eq(ring));
+  EXPECT_THAT(reader.index(), Eq(ring->head()));
+  EXPECT_THAT(reader.length(), Eq(ring->length));
+  EXPECT_THAT(reader.consumed(), Eq(flats[0].length()));
+  EXPECT_THAT(reader.remaining(), Eq(ring->length - reader.consumed()));
+
+  reader.Reset();
+  EXPECT_FALSE(static_cast<bool>(reader));
+  EXPECT_THAT(reader.ring(), Eq(nullptr));
+
+  CordRep::Unref(ring);
+}
+
+TEST(CordRingReaderTest, Next) {
+  CordRepRingReader reader;
+  auto flats = TestFlats();
+  CordRepRing* ring = FromFlats(flats);
+  CordRepRing::index_type head = ring->head();
+
+  reader.Reset(ring);
+  size_t consumed = reader.consumed();
+  size_t remaining = reader.remaining();
+  for (int i = 1; i < flats.size(); ++i) {
+    consumed += flats[i].length();
+    remaining -= flats[i].length();
+    absl::string_view next = reader.Next();
+    ASSERT_THAT(next, Eq(flats[i]));
+    ASSERT_THAT(reader.index(), Eq(ring->advance(head, i)));
+    ASSERT_THAT(reader.consumed(), Eq(consumed));
+    ASSERT_THAT(reader.remaining(), Eq(remaining));
+  }
+
+#ifndef NDEBUG
+  EXPECT_DEATH_IF_SUPPORTED(reader.Next(), ".*");
+#endif
+
+  CordRep::Unref(ring);
+}
+
+TEST(CordRingReaderTest, SeekForward) {
+  CordRepRingReader reader;
+  auto flats = TestFlats();
+  CordRepRing* ring = FromFlats(flats);
+  CordRepRing::index_type head = ring->head();
+
+  reader.Reset(ring);
+  size_t consumed = 0;
+  size_t remaining = ring->length;;
+  for (int i = 0; i < flats.size(); ++i) {
+    size_t offset = consumed;
+    consumed += flats[i].length();
+    remaining -= flats[i].length();
+    for (int off = 0; off < flats[i].length(); ++off) {
+      absl::string_view chunk = reader.Seek(offset + off);
+      ASSERT_THAT(chunk, Eq(flats[i].substr(off)));
+      ASSERT_THAT(reader.index(), Eq(ring->advance(head, i)));
+      ASSERT_THAT(reader.consumed(), Eq(consumed));
+      ASSERT_THAT(reader.remaining(), Eq(remaining));
+    }
+  }
+
+  CordRep::Unref(ring);
+}
+
+TEST(CordRingReaderTest, SeekBackward) {
+  CordRepRingReader reader;
+  auto flats = TestFlats();
+  CordRepRing* ring = FromFlats(flats);
+  CordRepRing::index_type head = ring->head();
+
+  reader.Reset(ring);
+  size_t consumed = ring->length;
+  size_t remaining = 0;
+  for (int i = flats.size() - 1; i >= 0; --i) {
+    size_t offset = consumed - flats[i].length();
+    for (int off = 0; off < flats[i].length(); ++off) {
+      absl::string_view chunk = reader.Seek(offset + off);
+      ASSERT_THAT(chunk, Eq(flats[i].substr(off)));
+      ASSERT_THAT(reader.index(), Eq(ring->advance(head, i)));
+      ASSERT_THAT(reader.consumed(), Eq(consumed));
+      ASSERT_THAT(reader.remaining(), Eq(remaining));
+    }
+    consumed -= flats[i].length();
+    remaining += flats[i].length();
+  }
+#ifndef NDEBUG
+  EXPECT_DEATH_IF_SUPPORTED(reader.Seek(ring->length), ".*");
+#endif
+  CordRep::Unref(ring);
+}
+
+}  // namespace
+}  // namespace cord_internal
+ABSL_NAMESPACE_END
+}  // namespace absl
diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h
index 011b49d..7a1ef6b 100644
--- a/absl/strings/internal/cord_internal.h
+++ b/absl/strings/internal/cord_internal.h
@@ -203,10 +203,15 @@ struct CordRep {
   // platforms; we intentionally allow LLVM to ignore the attribute rather than
   // attempting to hardcode the list of supported platforms.
 #if defined(__clang__) && !defined(__i386__)
+#if !(defined(ABSL_HAVE_MEMORY_SANITIZER) ||  \
+      defined(ABSL_HAVE_THREAD_SANITIZER) ||  \
+      defined(ABSL_HAVE_ADDRESS_SANITIZER) || \
+      defined(UNDEFINED_BEHAVIOR_SANITIZER))
 #pragma clang diagnostic push
 #pragma clang diagnostic ignored "-Wattributes"
   __attribute__((preserve_most))
 #pragma clang diagnostic pop
+#endif  // *_SANITIZER
 #endif
   static void Destroy(CordRep* rep);
 
diff --git a/absl/strings/internal/cord_rep_ring_reader.h b/absl/strings/internal/cord_rep_ring_reader.h
new file mode 100644
index 0000000..396c0e2
--- /dev/null
+++ b/absl/strings/internal/cord_rep_ring_reader.h
@@ -0,0 +1,114 @@
+// 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 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_