Improve error messages when comparing swisstable iterators.

We check for comparisons of swisstable iterators from different heap allocations, which can indicate either iterators from different containers or that there was a rehash between when the iterators were initialized.

PiperOrigin-RevId: 487304602
Change-Id: I5c596c5ea07948d66e048f99937f9032a630344f

1 files changed, 37 insertions, 4 deletions

diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 676cebd7..1aa89204 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -809,12 +809,44 @@ size_t SelectBucketCountForIterRange(InputIter first, InputIter last,
         "the table might have rehashed.");                                    \
   } while (0)
 
-inline void AssertIsValid(ctrl_t* ctrl) {
+// Note that for comparisons, null/end iterators are valid.
+inline void AssertIsValidForComparison(const ctrl_t* ctrl) {
   ABSL_HARDENING_ASSERT((ctrl == nullptr || IsFull(*ctrl)) &&
-                        "Invalid operation on iterator. The element might have "
+                        "Invalid iterator comparison. The element might have "
                         "been erased or the table might have rehashed.");
 }
 
+// If the two iterators come from the same container, then their pointers will
+// interleave such that ctrl_a <= ctrl_b < slot_a <= slot_b or vice/versa.
+// Note: we take slots by reference so that it's not UB if they're uninitialized
+// as long as we don't read them (when ctrl is null).
+inline bool AreItersFromSameContainer(const ctrl_t* ctrl_a,
+                                      const ctrl_t* ctrl_b,
+                                      const void* const& slot_a,
+                                      const void* const& slot_b) {
+  // If either control byte is null, then we can't tell.
+  if (ctrl_a == nullptr || ctrl_b == nullptr) return true;
+  const void* low_slot = slot_a;
+  const void* hi_slot = slot_b;
+  if (ctrl_a > ctrl_b) {
+    std::swap(ctrl_a, ctrl_b);
+    std::swap(low_slot, hi_slot);
+  }
+  return ctrl_b < low_slot && low_slot <= hi_slot;
+}
+
+// Asserts that two iterators come from the same container.
+// Note: we take slots by reference so that it's not UB if they're uninitialized
+// as long as we don't read them (when ctrl is null).
+inline void AssertSameContainer(const ctrl_t* ctrl_a, const ctrl_t* ctrl_b,
+                                const void* const& slot_a,
+                                const void* const& slot_b) {
+  ABSL_HARDENING_ASSERT(
+      AreItersFromSameContainer(ctrl_a, ctrl_b, slot_a, slot_b) &&
+      "Invalid iterator comparison. The iterators may be from different "
+      "containers or the container might have rehashed.");
+}
+
 struct FindInfo {
   size_t offset;
   size_t probe_length;
@@ -1067,8 +1099,9 @@ class raw_hash_set {
     }
 
     friend bool operator==(const iterator& a, const iterator& b) {
-      AssertIsValid(a.ctrl_);
-      AssertIsValid(b.ctrl_);
+      AssertSameContainer(a.ctrl_, b.ctrl_, a.slot_, b.slot_);
+      AssertIsValidForComparison(a.ctrl_);
+      AssertIsValidForComparison(b.ctrl_);
       return a.ctrl_ == b.ctrl_;
     }
     friend bool operator!=(const iterator& a, const iterator& b) {