Make default-constructed swisstable iterators use EmptyGroup() for ctrl_ so that we can distinguish between end() iterators and default-constructed iterators in debug mode.

PiperOrigin-RevId: 509606271
Change-Id: I77b68590b3904a4cf7809b75d814d74cb89603b6

1 files changed, 33 insertions, 20 deletions

diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index a2ada0cb..33e05736 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -816,6 +816,10 @@ class CommonFieldsGenerationInfoEnabled {
   // the code more complicated, and there's a benefit in having the sizes of
   // raw_hash_set in sanitizer mode and non-sanitizer mode a bit more different,
   // which is that tests are less likely to rely on the size remaining the same.
+  // TODO(b/254649633): Currently, we can't detect when end iterators from
+  // different empty tables are compared. If we allocate generations separately
+  // from control bytes, then we could do so. Another option would be to have N
+  // empty generations and use a random one for empty hashtables.
   GenerationType* generation_ = EmptyGeneration();
 };
 
@@ -853,9 +857,6 @@ class HashSetIteratorGenerationInfoEnabled {
   void set_generation_ptr(const GenerationType* ptr) { generation_ptr_ = ptr; }
 
  private:
-  // TODO(b/254649633): use a different static generation for default
-  // constructed iterators so that we can detect when default constructed
-  // iterators are compared to iterators from empty tables.
   const GenerationType* generation_ptr_ = EmptyGeneration();
   GenerationType generation_ = *generation_ptr_;
 };
@@ -1040,10 +1041,10 @@ size_t SelectBucketCountForIterRange(InputIter first, InputIter last,
 #define ABSL_INTERNAL_ASSERT_IS_FULL(ctrl, generation, generation_ptr,         \
                                      operation)                                \
   do {                                                                         \
-    ABSL_HARDENING_ASSERT(                                                     \
-        (ctrl != nullptr) && operation                                         \
-        " called on invalid iterator. The iterator might be an end() "         \
-        "iterator or may have been default constructed.");                     \
+    ABSL_HARDENING_ASSERT((ctrl != nullptr) && operation                       \
+                          " called on end() iterator.");                       \
+    ABSL_HARDENING_ASSERT((ctrl != EmptyGroup()) && operation                  \
+                          " called on default-constructed iterator.");         \
     if (SwisstableGenerationsEnabled() && generation != *generation_ptr)       \
       ABSL_INTERNAL_LOG(FATAL, operation                                       \
                         " called on invalidated iterator. The table could "    \
@@ -1058,9 +1059,10 @@ size_t SelectBucketCountForIterRange(InputIter first, InputIter last,
 inline void AssertIsValidForComparison(const ctrl_t* ctrl,
                                        GenerationType generation,
                                        const GenerationType* generation_ptr) {
-  ABSL_HARDENING_ASSERT((ctrl == nullptr || IsFull(*ctrl)) &&
-                        "Invalid iterator comparison. The element might have "
-                        "been erased or the table might have rehashed.");
+  ABSL_HARDENING_ASSERT(
+      (ctrl == nullptr || ctrl == EmptyGroup() || IsFull(*ctrl)) &&
+      "Invalid iterator comparison. The element might have "
+      "been erased or the table might have rehashed.");
   if (SwisstableGenerationsEnabled() && generation != *generation_ptr) {
     ABSL_INTERNAL_LOG(FATAL,
                       "Invalid iterator comparison. The table could have "
@@ -1095,16 +1097,27 @@ inline void AssertSameContainer(const ctrl_t* ctrl_a, const ctrl_t* ctrl_b,
                                 const void* const& slot_b,
                                 const GenerationType* generation_ptr_a,
                                 const GenerationType* generation_ptr_b) {
+#if defined(ABSL_SWISSTABLE_ENABLE_GENERATIONS) || \
+    ABSL_OPTION_HARDENED == 1 || !defined(NDEBUG)
+  const bool a_is_default = ctrl_a == EmptyGroup();
+  const bool b_is_default = ctrl_b == EmptyGroup();
+  if (a_is_default != b_is_default) {
+    ABSL_INTERNAL_LOG(
+        FATAL,
+        "Invalid iterator comparison. Comparing default-constructed iterator "
+        "with non-default-constructed iterator.");
+  }
+  if (a_is_default && b_is_default) return;
+#endif
+
   if (SwisstableGenerationsEnabled() && generation_ptr_a != generation_ptr_b) {
-    // TODO(b/254649633): use a different static generation for default
-    // constructed iterators so that we can split the empty/default cases.
-    const bool a_is_empty_or_default = generation_ptr_a == EmptyGeneration();
-    const bool b_is_empty_or_default = generation_ptr_b == EmptyGeneration();
-    if (a_is_empty_or_default != b_is_empty_or_default) {
+    const bool a_is_empty = generation_ptr_a == EmptyGeneration();
+    const bool b_is_empty = generation_ptr_b == EmptyGeneration();
+    if (a_is_empty != b_is_empty) {
       ABSL_INTERNAL_LOG(FATAL,
                         "Invalid iterator comparison. Comparing iterator from "
                         "a non-empty hashtable with an iterator from an empty "
-                        "hashtable or a default-constructed iterator.");
+                        "hashtable.");
     }
     const bool a_is_end = ctrl_a == nullptr;
     const bool b_is_end = ctrl_b == nullptr;
@@ -1509,7 +1522,7 @@ class raw_hash_set {
     }
     // For end() iterators.
     explicit iterator(const GenerationType* generation_ptr)
-        : HashSetIteratorGenerationInfo(generation_ptr) {}
+        : HashSetIteratorGenerationInfo(generation_ptr), ctrl_(nullptr) {}
 
     // Fixes up `ctrl_` to point to a full by advancing it and `slot_` until
     // they reach one.
@@ -1524,9 +1537,9 @@ class raw_hash_set {
       if (ABSL_PREDICT_FALSE(*ctrl_ == ctrl_t::kSentinel)) ctrl_ = nullptr;
     }
 
-    // TODO(b/254649633): use non-null control for default-constructed iterators
-    // so that we can distinguish between them and end iterators in debug mode.
-    ctrl_t* ctrl_ = nullptr;
+    // We use EmptyGroup() for default-constructed iterators so that they can
+    // be distinguished from end iterators, which have nullptr ctrl_.
+    ctrl_t* ctrl_ = EmptyGroup();
     // To avoid uninitialized member warnings, put slot_ in an anonymous union.
     // The member is not initialized on singleton and end iterators.
     union {