Export of internal Abseil changes

--
87cdfd6aa40941e116cd79ef70f9a7a8271db163 by Abseil Team <absl-team@google.com>:

Fix a typo in random.h API documentation.

PiperOrigin-RevId: 305176308

--
8a38e1df49a18a954daca3ce617fd69045ff4c19 by Derek Mauro <dmauro@google.com>:

Import GitHub #647: Allow external add_subdirectory for using GoogleTest

PiperOrigin-RevId: 305156797

--
b1a2441536d4964fbe4e2329e74c322e6c41a4e6 by Gennadiy Rozental <rogeeff@google.com>:

temporary roll back.

PiperOrigin-RevId: 305149619

--
c78767577264348d2f881893f9407aadfe73ab75 by CJ Johnson <johnsoncj@google.com>:

Rollback update to linux_clang-latest container while investigating
a compiler bug.

PiperOrigin-RevId: 304897689

--
3c6fd38f53d2e982569fdba4043f75271c7b5de4 by Derek Mauro <dmauro@google.com>:

Update linux_clang-latest container to one based on Ubuntu 18.04,
which has libstdc++-8.

PiperOrigin-RevId: 304885120
GitOrigin-RevId: 87cdfd6aa40941e116cd79ef70f9a7a8271db163
Change-Id: Iefa6efee93907ec0eecb8add804c5cc2f052b64d

1 files changed, 72 insertions, 160 deletions

diff --git a/absl/strings/cord.h b/absl/strings/cord.h
index d5b9363f..5136f926 100644
--- a/absl/strings/cord.h
+++ b/absl/strings/cord.h
@@ -123,132 +123,12 @@ H HashFragmentedCord(H, const Cord&);
 // Additionally, the API provides iterator utilities to iterate through Cord
 // data via chunks or character bytes.
 //
-
-namespace cord_internal {
-
-// It's expensive to keep a Cord's tree perfectly balanced, so instead we keep
-// trees approximately balanced.  A tree node N of depth D(N) that contains a
-// string of L(N) characters is considered balanced if L >= Fibonacci(D + 2).
-// The "+ 2" is used to ensure that every balanced leaf node contains at least
-//  one character. Here we presume that
-//   Fibonacci(0) = 0
-//   Fibonacci(1) = 1
-//   Fibonacci(2) = 1
-//   Fibonacci(3) = 2
-//   ...
-// The algorithm is based on paper by Hans Boehm et al:
-// https://www.cs.rit.edu/usr/local/pub/jeh/courses/QUARTERS/FP/Labs/CedarRope/rope-paper.pdf
-// In this paper authors shows that rebalancing based on cord forest of already
-// balanced subtrees can be proven to never produce tree of depth larger than
-// largest Fibonacci number representable in the same integral type as cord size
-// For 64 bit integers this is the 93rd Fibonacci number. For 32 bit integrals
-// this is 47th Fibonacci number.
-constexpr size_t MaxCordDepth() { return sizeof(size_t) == 8 ? 93 : 47; }
-
-// This class models fixed max size stack of CordRep pointers.
-// The elements are being pushed back and popped from the back.
-template <typename CordRepPtr, size_t N>
-class CordTreePath {
- public:
-  CordTreePath() {}
-  explicit CordTreePath(CordRepPtr root) { push_back(root); }
-
-  bool empty() const { return size_ == 0; }
-  size_t size() const { return size_; }
-  void clear() { size_ = 0; }
-
-  CordRepPtr back() { return data_[size_ - 1]; }
-
-  void pop_back() {
-    --size_;
-    assert(size_ < N);
-  }
-  void push_back(CordRepPtr elem) { data_[size_++] = elem; }
-
- private:
-  CordRepPtr data_[N];
-  size_t size_ = 0;
-};
-
-// Fixed length container for mutable "path" in cord tree, which can hold any
-// possible valid path in cord tree.
-using CordTreeMutablePath = CordTreePath<CordRep*, MaxCordDepth()>;
-// Variable length container for mutable "path" in cord tree. It starts with
-// capacity for 15 elements and grow if necessary.
-using CordTreeDynamicPath =
-    absl::InlinedVector<absl::cord_internal::CordRep*, 15>;
-}  // namespace cord_internal
-
-// A Cord is a sequence of characters.
 class Cord {
  private:
   template <typename T>
   using EnableIfString =
       absl::enable_if_t<std::is_same<T, std::string>::value, int>;
 
-  //----------------------------------------------------------------------------
-  // Cord::GenericChunkIterator
-  //----------------------------------------------------------------------------
-  //
-  // A `Cord::GenericChunkIterator` provides an interface for the standard
-  // `Cord::ChunkIterator` as well as some private implementations.
-  template <typename StorageType>
-  class GenericChunkIterator {
-   public:
-    using iterator_category = std::input_iterator_tag;
-    using value_type = absl::string_view;
-    using difference_type = ptrdiff_t;
-    using pointer = const value_type*;
-    using reference = value_type;
-
-    GenericChunkIterator() = default;
-
-    GenericChunkIterator& operator++();
-    GenericChunkIterator operator++(int);
-    bool operator==(const GenericChunkIterator& other) const;
-    bool operator!=(const GenericChunkIterator& other) const;
-    reference operator*() const;
-    pointer operator->() const;
-
-    friend class Cord;
-    friend class CharIterator;
-
-   private:
-    // Constructs a `begin()` iterator from `cord`.
-    explicit GenericChunkIterator(const Cord* cord);
-
-    // Removes `n` bytes from `current_chunk_`. Expects `n` to be smaller than
-    // `current_chunk_.size()`.
-    void RemoveChunkPrefix(size_t n);
-    Cord AdvanceAndReadBytes(size_t n);
-    void AdvanceBytes(size_t n);
-    // Iterates `n` bytes, where `n` is expected to be greater than or equal to
-    // `current_chunk_.size()`.
-    void AdvanceBytesSlowPath(size_t n);
-
-    // A view into bytes of the current `CordRep`. It may only be a view to a
-    // suffix of bytes if this is being used by `CharIterator`.
-    absl::string_view current_chunk_;
-    // The current leaf, or `nullptr` if the iterator points to short data.
-    // If the current chunk is a substring node, current_leaf_ points to the
-    // underlying flat or external node.
-    cord_internal::CordRep* current_leaf_ = nullptr;
-    // The number of bytes left in the `Cord` over which we are iterating.
-    size_t bytes_remaining_ = 0;
-    StorageType stack_of_right_children_;
-  };
-  template <typename IteratorType>
-  class GenericChunkRange {
-   public:
-    explicit GenericChunkRange(const Cord* cord) : cord_(cord) {}
-
-    IteratorType begin() const { return IteratorType(cord_); }
-    IteratorType end() const { return IteratorType(); }
-
-   private:
-    const Cord* cord_;
-  };
-
  public:
   // Cord::Cord() Constructors
 
@@ -464,8 +344,51 @@ class Cord {
   //   * The iterator keeps state that can grow for Cords that contain many
   //     nodes and are imbalanced due to sharing. Prefer to pass this type by
   //     const reference instead of by value.
-  using ChunkIterator =
-      GenericChunkIterator<cord_internal::CordTreeDynamicPath>;
+  class ChunkIterator {
+   public:
+    using iterator_category = std::input_iterator_tag;
+    using value_type = absl::string_view;
+    using difference_type = ptrdiff_t;
+    using pointer = const value_type*;
+    using reference = value_type;
+
+    ChunkIterator() = default;
+
+    ChunkIterator& operator++();
+    ChunkIterator operator++(int);
+    bool operator==(const ChunkIterator& other) const;
+    bool operator!=(const ChunkIterator& other) const;
+    reference operator*() const;
+    pointer operator->() const;
+
+    friend class Cord;
+    friend class CharIterator;
+
+   private:
+    // Constructs a `begin()` iterator from `cord`.
+    explicit ChunkIterator(const Cord* cord);
+
+    // Removes `n` bytes from `current_chunk_`. Expects `n` to be smaller than
+    // `current_chunk_.size()`.
+    void RemoveChunkPrefix(size_t n);
+    Cord AdvanceAndReadBytes(size_t n);
+    void AdvanceBytes(size_t n);
+    // Iterates `n` bytes, where `n` is expected to be greater than or equal to
+    // `current_chunk_.size()`.
+    void AdvanceBytesSlowPath(size_t n);
+
+    // A view into bytes of the current `CordRep`. It may only be a view to a
+    // suffix of bytes if this is being used by `CharIterator`.
+    absl::string_view current_chunk_;
+    // The current leaf, or `nullptr` if the iterator points to short data.
+    // If the current chunk is a substring node, current_leaf_ points to the
+    // underlying flat or external node.
+    absl::cord_internal::CordRep* current_leaf_ = nullptr;
+    // The number of bytes left in the `Cord` over which we are iterating.
+    size_t bytes_remaining_ = 0;
+    absl::InlinedVector<absl::cord_internal::CordRep*, 4>
+        stack_of_right_children_;
+  };
 
   // Cord::ChunkIterator::chunk_begin()
   //
@@ -504,7 +427,16 @@ class Cord {
   //
   // Implementation note: `ChunkRange` is simply a convenience wrapper over
   // `Cord::chunk_begin()` and `Cord::chunk_end()`.
-  using ChunkRange = GenericChunkRange<ChunkIterator>;
+  class ChunkRange {
+   public:
+    explicit ChunkRange(const Cord* cord) : cord_(cord) {}
+
+    ChunkIterator begin() const;
+    ChunkIterator end() const;
+
+   private:
+    const Cord* cord_;
+  };
 
   // Cord::Chunks()
   //
@@ -800,14 +732,6 @@ class Cord {
   static bool GetFlatAux(absl::cord_internal::CordRep* rep,
                          absl::string_view* fragment);
 
-  // Iterators for use inside Cord implementation
-  using InternalChunkIterator =
-      GenericChunkIterator<cord_internal::CordTreeMutablePath>;
-  using InternalChunkRange = GenericChunkRange<InternalChunkIterator>;
-
-  InternalChunkIterator internal_chunk_begin() const;
-  InternalChunkRange InternalChunks() const;
-
   // Helper for ForEachChunk()
   static void ForEachChunkAux(
       absl::cord_internal::CordRep* rep,
@@ -842,11 +766,6 @@ class Cord {
   void AppendImpl(C&& src);
 };
 
-extern template class Cord::GenericChunkIterator<
-    cord_internal::CordTreeMutablePath>;
-extern template class Cord::GenericChunkIterator<
-    cord_internal::CordTreeDynamicPath>;
-
 ABSL_NAMESPACE_END
 }  // namespace absl
 
@@ -1186,9 +1105,7 @@ inline bool Cord::StartsWith(absl::string_view rhs) const {
   return EqualsImpl(rhs, rhs_size);
 }
 
-template <typename StorageType>
-inline Cord::GenericChunkIterator<StorageType>::GenericChunkIterator(
-    const Cord* cord)
+inline Cord::ChunkIterator::ChunkIterator(const Cord* cord)
     : bytes_remaining_(cord->size()) {
   if (cord->empty()) return;
   if (cord->contents_.is_tree()) {
@@ -1199,50 +1116,37 @@ inline Cord::GenericChunkIterator<StorageType>::GenericChunkIterator(
   }
 }
 
-template <typename StorageType>
-inline Cord::GenericChunkIterator<StorageType>
-Cord::GenericChunkIterator<StorageType>::operator++(int) {
-  GenericChunkIterator tmp(*this);
+inline Cord::ChunkIterator Cord::ChunkIterator::operator++(int) {
+  ChunkIterator tmp(*this);
   operator++();
   return tmp;
 }
 
-template <typename StorageType>
-inline bool Cord::GenericChunkIterator<StorageType>::operator==(
-    const GenericChunkIterator<StorageType>& other) const {
+inline bool Cord::ChunkIterator::operator==(const ChunkIterator& other) const {
   return bytes_remaining_ == other.bytes_remaining_;
 }
 
-template <typename StorageType>
-inline bool Cord::GenericChunkIterator<StorageType>::operator!=(
-    const GenericChunkIterator<StorageType>& other) const {
+inline bool Cord::ChunkIterator::operator!=(const ChunkIterator& other) const {
   return !(*this == other);
 }
 
-template <typename StorageType>
-inline typename Cord::GenericChunkIterator<StorageType>::reference
-Cord::GenericChunkIterator<StorageType>::operator*() const {
+inline Cord::ChunkIterator::reference Cord::ChunkIterator::operator*() const {
   ABSL_HARDENING_ASSERT(bytes_remaining_ != 0);
   return current_chunk_;
 }
 
-template <typename StorageType>
-inline typename Cord::GenericChunkIterator<StorageType>::pointer
-Cord::GenericChunkIterator<StorageType>::operator->() const {
+inline Cord::ChunkIterator::pointer Cord::ChunkIterator::operator->() const {
   ABSL_HARDENING_ASSERT(bytes_remaining_ != 0);
   return &current_chunk_;
 }
 
-template <typename StorageType>
-inline void Cord::GenericChunkIterator<StorageType>::RemoveChunkPrefix(
-    size_t n) {
+inline void Cord::ChunkIterator::RemoveChunkPrefix(size_t n) {
   assert(n < current_chunk_.size());
   current_chunk_.remove_prefix(n);
   bytes_remaining_ -= n;
 }
 
-template <typename StorageType>
-inline void Cord::GenericChunkIterator<StorageType>::AdvanceBytes(size_t n) {
+inline void Cord::ChunkIterator::AdvanceBytes(size_t n) {
   if (ABSL_PREDICT_TRUE(n < current_chunk_.size())) {
     RemoveChunkPrefix(n);
   } else if (n != 0) {
@@ -1256,6 +1160,14 @@ inline Cord::ChunkIterator Cord::chunk_begin() const {
 
 inline Cord::ChunkIterator Cord::chunk_end() const { return ChunkIterator(); }
 
+inline Cord::ChunkIterator Cord::ChunkRange::begin() const {
+  return cord_->chunk_begin();
+}
+
+inline Cord::ChunkIterator Cord::ChunkRange::end() const {
+  return cord_->chunk_end();
+}
+
 inline Cord::ChunkRange Cord::Chunks() const { return ChunkRange(this); }
 
 inline Cord::CharIterator& Cord::CharIterator::operator++() {