From 8cfc1500f894c07995abf25c2ad31f38982432cf Mon Sep 17 00:00:00 2001
From: Evan Brown <ezb@google.com>
Date: Wed, 9 Nov 2022 11:40:57 -0800
Subject: 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
---
 absl/container/internal/raw_hash_set.h       | 41 +++++++++++++++++++++++++---
 absl/container/internal/raw_hash_set_test.cc | 26 ++++++++++++++----
 2 files changed, 58 insertions(+), 9 deletions(-)

(limited to 'absl/container')

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) {
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index 6478d3fc..daa32814 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -2082,13 +2082,29 @@ TEST(TableDeathTest, IteratorInvalidAssertsEqualityOperator) {
   ASSERT_NE(iter2, t.end());
   t.erase(iter1);
   // Extra simple "regexp" as regexp support is highly varied across platforms.
-  const char* const kDeathMessage =
-      "Invalid operation on iterator. The element might have .*been erased or "
+  const char* const kErasedDeathMessage =
+      "Invalid iterator comparison. The element might have .*been erased or "
       "the table might have rehashed.";
-  EXPECT_DEATH_IF_SUPPORTED(void(iter1 == iter2), kDeathMessage);
-  EXPECT_DEATH_IF_SUPPORTED(void(iter2 != iter1), kDeathMessage);
+  EXPECT_DEATH_IF_SUPPORTED(void(iter1 == iter2), kErasedDeathMessage);
+  EXPECT_DEATH_IF_SUPPORTED(void(iter2 != iter1), kErasedDeathMessage);
   t.erase(iter2);
-  EXPECT_DEATH_IF_SUPPORTED(void(iter1 == iter2), kDeathMessage);
+  EXPECT_DEATH_IF_SUPPORTED(void(iter1 == iter2), kErasedDeathMessage);
+
+  IntTable t1, t2;
+  t1.insert(0);
+  t2.insert(0);
+  iter1 = t1.begin();
+  iter2 = t2.begin();
+  const char* const kContainerDiffDeathMessage =
+      "Invalid iterator comparison. The iterators may be from different "
+      ".*containers or the container might have rehashed.";
+  EXPECT_DEATH_IF_SUPPORTED(void(iter1 == iter2), kContainerDiffDeathMessage);
+  EXPECT_DEATH_IF_SUPPORTED(void(iter2 == iter1), kContainerDiffDeathMessage);
+
+  for (int i = 0; i < 10; ++i) t1.insert(i);
+  // There should have been a rehash in t1.
+  EXPECT_DEATH_IF_SUPPORTED(void(iter1 == t1.begin()),
+                            kContainerDiffDeathMessage);
 }
 
 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
-- 
cgit v1.2.3