Export of internal Abseil changes

--
9e8b4a286d70df9487bff080816bd07ae38af5f8 by Evan Brown <ezb@google.com>:

Add btree_node::transfer_n/transfer_n_backward and replace usage of uninitialized_move_n and value_destroy_n.

PiperOrigin-RevId: 314600027

--
6c452aa1ee7e46ab941ba7d1fa636da8ea3d7370 by Laramie Leavitt <lar@google.com>:

Remove the MockingBitGenBase base class in favor of type-erasure in BitGenRef.

In Abseil random, mocking was split across two different classes,
MockingBitGenBase and MockingBitGen. This split existed because Google Mock is a
test-only library that we don't link into production, so MockingBitGenBase
provided a low-overhead scaffold used to lookup mocks when in test code, but
which is unused in production code.

That has been replaced by type-erasure which looks for a method named
CallImpl with the correct signature.

Weaken the coupling between MockingBitGen, DistributionCaller, and MockOverloadSet.

Rename CallImpl to InvokeMock()

Previously, the implementation of DistributionCaller was also split across different files using explicit instantiation of the DistributionCaller struct and some details in the Mocking classes. Now Distribution caller uses the presence of the InvokeMock() method to choose whether to use the mockable call path or the default call path.

PiperOrigin-RevId: 314584095

--
07853c47dc98698d67d65a3b9b662a65ab9def0a by Abseil Team <absl-team@google.com>:

Add PC / backtrace / symbolization support for Apple platforms.

Full backtrace support requires iOS 9+

PiperOrigin-RevId: 314415072

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

Consolidate all reflection interface in the new module 'reflection' and expose interface to locate reflection handle by name.

PiperOrigin-RevId: 314390358
GitOrigin-RevId: 9e8b4a286d70df9487bff080816bd07ae38af5f8
Change-Id: I8e0910437740cf9ea9da5000adddfcef127e1158

1 files changed, 61 insertions, 90 deletions

diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index b23138f0..f52fe235 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -817,33 +817,52 @@ class btree_node {
     absl::container_internal::SanitizerPoisonObject(slot(i));
   }
 
-  // Transfers value from slot `src_i` in `src` to slot `dest_i` in `this`.
-  void transfer(const size_type dest_i, const size_type src_i, btree_node *src,
-                allocator_type *alloc) {
+  // Transfers value from slot `src_i` in `src_node` to slot `dest_i` in `this`.
+  void transfer(const size_type dest_i, const size_type src_i,
+                btree_node *src_node, allocator_type *alloc) {
     absl::container_internal::SanitizerUnpoisonObject(slot(dest_i));
-    params_type::transfer(alloc, slot(dest_i), src->slot(src_i));
-    absl::container_internal::SanitizerPoisonObject(src->slot(src_i));
+    params_type::transfer(alloc, slot(dest_i), src_node->slot(src_i));
+    absl::container_internal::SanitizerPoisonObject(src_node->slot(src_i));
   }
 
-  // Move n values starting at value i in this node into the values starting at
-  // value j in dest_node.
-  void uninitialized_move_n(const size_type n, const size_type i,
-                            const size_type j, btree_node *dest_node,
-                            allocator_type *alloc) {
+  // Transfers `n` values starting at value `src_i` in `src_node` into the
+  // values starting at value `dest_i` in `this`.
+  void transfer_n(const size_type n, const size_type dest_i,
+                  const size_type src_i, btree_node *src_node,
+                  allocator_type *alloc) {
     absl::container_internal::SanitizerUnpoisonMemoryRegion(
-        dest_node->slot(j), n * sizeof(slot_type));
-    for (slot_type *src = slot(i), *end = src + n, *dest = dest_node->slot(j);
+        slot(dest_i), n * sizeof(slot_type));
+    for (slot_type *src = src_node->slot(src_i), *end = src + n,
+                   *dest = slot(dest_i);
          src != end; ++src, ++dest) {
-      params_type::construct(alloc, dest, src);
+      params_type::transfer(alloc, dest, src);
     }
+    // We take care to avoid poisoning transferred-to nodes in case of overlap.
+    const size_type overlap =
+        this == src_node ? (std::max)(src_i, dest_i + n) - src_i : 0;
+    assert(n >= overlap);
+    absl::container_internal::SanitizerPoisonMemoryRegion(
+        src_node->slot(src_i + overlap), (n - overlap) * sizeof(slot_type));
   }
 
-  // Destroys a range of n values, starting at index i.
-  void value_destroy_n(const size_type i, const size_type n,
-                       allocator_type *alloc) {
-    for (int j = 0; j < n; ++j) {
-      value_destroy(i + j, alloc);
+  // Same as above, except that we start at the end and work our way to the
+  // beginning.
+  void transfer_n_backward(const size_type n, const size_type dest_i,
+                           const size_type src_i, btree_node *src_node,
+                           allocator_type *alloc) {
+    absl::container_internal::SanitizerUnpoisonMemoryRegion(
+        slot(dest_i), n * sizeof(slot_type));
+    for (slot_type *src = src_node->slot(src_i + n - 1), *end = src - n,
+                   *dest = slot(dest_i + n - 1);
+         src != end; --src, --dest) {
+      params_type::transfer(alloc, dest, src);
     }
+    // We take care to avoid poisoning transferred-to nodes in case of overlap.
+    assert(this != src_node || dest_i >= src_i);
+    const size_type num_to_poison =
+        this == src_node ? (std::min)(n, dest_i - src_i) : n;
+    absl::container_internal::SanitizerPoisonMemoryRegion(
+        src_node->slot(src_i), num_to_poison * sizeof(slot_type));
   }
 
   template <typename P>
@@ -1531,10 +1550,8 @@ inline void btree_node<P>::emplace_value(const size_type i,
   // Shift old values to create space for new value and then construct it in
   // place.
   if (i < finish()) {
-    value_init(finish(), alloc, slot(finish() - 1));
-    for (size_type j = finish() - 1; j > i; --j)
-      params_type::move(alloc, slot(j - 1), slot(j));
-    value_destroy(i, alloc);
+    transfer_n_backward(finish() - i, /*dest_i=*/i + 1, /*src_i=*/i, this,
+                        alloc);
   }
   value_init(i, alloc, std::forward<Args>(args)...);
   set_finish(finish() + 1);
@@ -1564,7 +1581,9 @@ template <typename P>
 inline void btree_node<P>::remove_values_ignore_children(
     const int i, const int to_erase, allocator_type *alloc) {
   params_type::move(alloc, slot(i + to_erase), finish_slot(), slot(i));
-  value_destroy_n(finish() - to_erase, to_erase, alloc);
+  for (int j = finish() - to_erase; j < finish(); ++j) {
+    value_destroy(j, alloc);
+  }
   set_finish(finish() - to_erase);
 }
 
@@ -1579,22 +1598,17 @@ void btree_node<P>::rebalance_right_to_left(const int to_move,
   assert(to_move <= right->count());
 
   // 1) Move the delimiting value in the parent to the left node.
-  value_init(finish(), alloc, parent()->slot(position()));
+  transfer(finish(), position(), parent(), alloc);
 
   // 2) Move the (to_move - 1) values from the right node to the left node.
-  right->uninitialized_move_n(to_move - 1, right->start(), finish() + 1, this,
-                              alloc);
+  transfer_n(to_move - 1, finish() + 1, right->start(), right, alloc);
 
   // 3) Move the new delimiting value to the parent from the right node.
-  params_type::move(alloc, right->slot(to_move - 1),
-                    parent()->slot(position()));
-
-  // 4) Shift the values in the right node to their correct position.
-  params_type::move(alloc, right->slot(to_move), right->finish_slot(),
-                    right->start_slot());
+  parent()->transfer(position(), right->start() + to_move - 1, right, alloc);
 
-  // 5) Destroy the now-empty to_move entries in the right node.
-  right->value_destroy_n(right->finish() - to_move, to_move, alloc);
+  // 4) Shift the values in the right node to their correct positions.
+  right->transfer_n(right->count() - to_move, right->start(),
+                    right->start() + to_move, right, alloc);
 
   if (!leaf()) {
     // Move the child pointers from the right to the left node.
@@ -1629,54 +1643,19 @@ void btree_node<P>::rebalance_left_to_right(const int to_move,
   // Lastly, a new delimiting value is moved from the left node into the
   // parent, and the remaining empty left node entries are destroyed.
 
-  if (right->count() >= to_move) {
-    // The original location of the right->count() values are sufficient to hold
-    // the new to_move entries from the parent and left node.
-
-    // 1) Shift existing values in the right node to their correct positions.
-    right->uninitialized_move_n(to_move, right->finish() - to_move,
-                                right->finish(), right, alloc);
-    for (slot_type *src = right->slot(right->finish() - to_move - 1),
-                   *dest = right->slot(right->finish() - 1),
-                   *end = right->start_slot();
-         src >= end; --src, --dest) {
-      params_type::move(alloc, src, dest);
-    }
-
-    // 2) Move the delimiting value in the parent to the right node.
-    params_type::move(alloc, parent()->slot(position()),
-                      right->slot(to_move - 1));
+  // 1) Shift existing values in the right node to their correct positions.
+  right->transfer_n_backward(right->count(), right->start() + to_move,
+                             right->start(), right, alloc);
 
-    // 3) Move the (to_move - 1) values from the left node to the right node.
-    params_type::move(alloc, slot(finish() - (to_move - 1)), finish_slot(),
-                      right->start_slot());
-  } else {
-    // The right node does not have enough initialized space to hold the new
-    // to_move entries, so part of them will move to uninitialized space.
-
-    // 1) Shift existing values in the right node to their correct positions.
-    right->uninitialized_move_n(right->count(), right->start(),
-                                right->start() + to_move, right, alloc);
+  // 2) Move the delimiting value in the parent to the right node.
+  right->transfer(right->start() + to_move - 1, position(), parent(), alloc);
 
-    // 2) Move the delimiting value in the parent to the right node.
-    right->value_init(to_move - 1, alloc, parent()->slot(position()));
-
-    // 3) Move the (to_move - 1) values from the left node to the right node.
-    const size_type uninitialized_remaining = to_move - right->count() - 1;
-    uninitialized_move_n(uninitialized_remaining,
-                         finish() - uninitialized_remaining, right->finish(),
-                         right, alloc);
-    params_type::move(alloc, slot(finish() - (to_move - 1)),
-                      slot(finish() - uninitialized_remaining),
-                      right->start_slot());
-  }
+  // 3) Move the (to_move - 1) values from the left node to the right node.
+  right->transfer_n(to_move - 1, right->start(), finish() - (to_move - 1), this,
+                    alloc);
 
   // 4) Move the new delimiting value to the parent from the left node.
-  params_type::move(alloc, slot(finish() - to_move),
-                    parent()->slot(position()));
-
-  // 5) Destroy the now-empty to_move entries in the left node.
-  value_destroy_n(finish() - to_move, to_move, alloc);
+  parent()->transfer(position(), finish() - to_move, this, alloc);
 
   if (!leaf()) {
     // Move the child pointers from the left to the right node.
@@ -1716,10 +1695,7 @@ void btree_node<P>::split(const int insert_position, btree_node *dest,
   assert(count() >= 1);
 
   // Move values from the left sibling to the right sibling.
-  uninitialized_move_n(dest->count(), finish(), dest->start(), dest, alloc);
-
-  // Destroy the now-empty entries in the left node.
-  value_destroy_n(finish(), dest->count(), alloc);
+  dest->transfer_n(dest->count(), dest->start(), finish(), this, alloc);
 
   // The split key is the largest value in the left sibling.
   --mutable_finish();
@@ -1746,11 +1722,7 @@ void btree_node<P>::merge(btree_node *src, allocator_type *alloc) {
   value_init(finish(), alloc, parent()->slot(position()));
 
   // Move the values from the right to the left node.
-  src->uninitialized_move_n(src->count(), src->start(), finish() + 1, this,
-                            alloc);
-
-  // Destroy the now-empty entries in the right node.
-  src->value_destroy_n(src->start(), src->count(), alloc);
+  transfer_n(src->count(), finish() + 1, src->start(), src, alloc);
 
   if (!leaf()) {
     // Move the child pointers from the right to the left node.
@@ -2474,9 +2446,8 @@ inline auto btree<P>::internal_emplace(iterator iter, Args &&... args)
       // Transfer the values from the old root to the new root.
       node_type *old_root = root();
       node_type *new_root = iter.node;
-      for (int i = old_root->start(), f = old_root->finish(); i < f; ++i) {
-        new_root->transfer(i, i, old_root, alloc);
-      }
+      new_root->transfer_n(old_root->count(), new_root->start(),
+                           old_root->start(), old_root, alloc);
       new_root->set_finish(old_root->finish());
       old_root->set_finish(old_root->start());
       delete_leaf_node(old_root);